China、Quantum、Factoringの暗号化キーを組み合わせれば、量子誇大広告マシンの燃料は膨大な量になる。最近、中国の24人の研究者が arXiv に投稿した 「Factoring integers with sublinear resources on a superconducting quantum processor(超伝導量子プロセッサ上の準線形リソースを持つ整数の素因数分解)」 と題された新しい論文で引き起こされた一般報道で多くの騒ぎがあった。
この論文は、量子コンピュータを使って 2,048ビットの大きな半素数を因数分解するという新しいアプローチを提案したもので、物理的な量子ビットが 372個、ゲート深さが数千の NISQコンピュータで実現が可能だという。これが本当であれば、今日のインターネットで非対称暗号化に広く使用されている RSA-2048 暗号コードが危険にさらされ、世界中のデジタル通信インフラが危険になるだろう。ちなみに、よく知られている Shor のアルゴリズムでは、誤り訂正を行うために約4,000個の論理量子ビットが必要で、これは物理量子ビットでは約2,000万個、誤り訂正に伴うオーバーヘッドのためにゲート深さは数十億に相当するものである。
我々が昨年報告した論文で説明したアプローチは、Claus Peter Schnoor博士によって提案された古典的なアルゴリズムから始まり、整数の因数分解に格子還元を使用する最短ベクトル問題 (SVP) アルゴリズムを使用するアプローチに基づいている。今回の論文では、SchnoorのアルゴリズムをQAOA (Quantum Approximate Optimization Algorithm) と呼ばれるヒューリスティック量子最適化アルゴリズムと組み合わせることで、高速化し、理論的に問題をはるかに高速に解決できるようにしたと述べている。
量子の専門家からは、このアプローチに対して幾つかの反論が投稿されている。1つ目は、Scott Aaronson氏が自身のブログで、QAOAが「高速化が可能であるという説得力のある議論はまだなされていない」と述べ、ただ1つの可能な例外を挙げている。彼はまた、論文自体が 「QAOAが曖昧な収束であるため、量子的高速化が不明瞭である」 と指摘している。他にムーディーズ・アナリティックスは、「シュノルの技法は、適切にスケーリングすることが示されなかった」と指摘する論文を掲載している。また、QAOAアルゴリズム自体がうまく拡張できない可能性があること、この技術を使うにしてもゲートレベルの忠実度が 99.999%のNISQコンピュータが必要であることなどのコメントがあった。現状では二桁の改善が必要だ。 99.999%のレベルに到達するだけでも、誤り訂正の使用は必要かもしれない。そして最後に、QAOAはある問題に対して絶対的な最適化を生み出すことを保証するものではないことを指摘しておく。
ユースケースによっては、たとえ2番目や3番目の答えを出したとしても、古典的な答えよりも良い、あるいは速い答えを出すことができれば、それはまだ有用であるかもしれない。しかしここでの問題は因数分解だ。答えは厳密でなければならない。
その他の情報は、原著論文 、Scott Aaronson氏のブログ記事 、Moody Analytics社の記事 で確認してほしい。
※参考
Claus Peter Schnoor：クラウス・ペーター・シュノル：ドイツの数学者で、暗号研究家。
=============================
原記事（Quantum Computing Report）
https://quantumcomputingreport.com/