In computer science, the two most important classes of problems are P and NP. The P class stands for polynomial, that is, we can solve the problem in order of (N) to the (k) time ((O(N^k))) where (N) represents the size of the problem and (k) is some constant number. NP is non-deterministic polynomial.

The best known solutions to problems in NP and believed to be outside of P are exponential. Of course, any exponential grows very fast, so problems that take exponential time are considered to be hard to solve. So what about factoring, where does it fall?

Factoring is, so far as we know, harder than polynomial, but not as hard as exponential. Because Shor’s algorithm shows that a quantum computer can factor in polynomial time, it is exciting for three big reasons:

1. the problem is important;
2. the performance gains are exciting; and
3. techniques are exciting and valuable.

基本目標：素因数分解

計算機科学において最も重要な問題のクラスはPとNPの２つです。Pは多項式(Polynomial)を意味します。つまり、問題のサイズを(N)とし、(k)をある特定の定数とした場合、 Pクラスの問題は((O(N^k)))の多項式時間で解を計算できるあらゆる問題を指します。 NPは非決定性多項式(Non-deterministic Polynomial)です。

NPの問題の解法は指数関数的であり、Pに属さないと考えられていることはよく知られています。 言うまでもなく、どの指数関数も非常に速く値が増大していくため、指数関数的な時間を要する問題の解を計算することは一般的には困難であると考えられています。では、因数分解はどのクラスに属するのでしょうか？

素因数分解は、多項式以上、指数関数以下の計算量を必要とした問題であると現在考えられています。 量子コンピュータ上でShorのアルゴリズムを使えば、多項式時間で因数分解を解くことが出来ます。 これは、主に以下の3つの理由から、魅力的なことであると言えます。

1. 問題そのものが重要
2. 性能の向上が魅力的
3. 新しい技術の確立