Today’s best classical computers and algorithm would require the lifetime of the universe to factor a number that is 2000 bits long. Even the apparently exponential gain of Moore’s law does not get us a big improvement in the overall performance.

Can a quantum computer factor a large number in seconds? Ultimately we have these three big factors that impact the performance, we have the clock speed of the system itself, our ability to make good algorithm that executes the modular exponentiation part and finally the architecture of the quantum computer itself.

まとめ – パフォーマンスに影響を与える大きな要因

今存在している最高の古典コンピュータとアルゴリズムを持ってしても、2000ビット長の数字を因数分解をするためには、宇宙の年齢に相当する時間が必要になります。 ムーアの法則に則って、指数関数的にコンピュータの性能が向上しても、問題の根本的な解決策にはなりえません。

では、量子コンピューターは因数分解を瞬時に解くことができるのでしょうか？ システムのパフォーマンスに影響を与える主な要因は、システム自体のクロック速度、冪剰余を実行する優れたアルゴリズムと量子コンピュータのアーキテクチャの３点が主に挙げられます。