最近、中国の24人の研究者がarXivに投稿した「Factoring integers with sublinear resources on a superconducting quantum processor(PDF)」という新しい論文によって、論争が巻き起こっている。
この論文では、量子コンピュータを使って2,048ビットの大きな半素数を因数分解するという新しいアプローチを提案しており、物理的な量子ビットが372個、ゲート深さが数千のNISQレベルのコンピュータで実現可能だと述べている。もしこれが実現すれば、現在のインターネットで非対称暗号として広く使われているRSA-2048暗号を危うくし、世界中のデジタル通信インフラを不安定にすることになる。ちなみに、よく知られているショアのアルゴリズムでは、誤り訂正を行うために約4,000個の論理的な量子ビットが必要で、これは物理的な量子ビットでは約2,000万個、誤り訂正に伴うオーバーヘッドによりゲート深さは数十億個になる。
昨年報告した論文で紹介したアプローチは、Claus Peter Schnoor博士が提案した古典的なアルゴリズムから始まり、整数の因数分解に格子縮小を用いる最短ベクトル問題（SVP）アルゴリズムを用いたアプローチに基づいている。今回の論文では、ショアのアルゴリズムをQAOA（Quantum Approximated Optimization Algorithm）と呼ばれる発見的量子最適化アルゴリズムと組み合わせて、ショアのアルゴリズムを高速化し、理論的にはもっと速く問題を解くことができるという新展開がなされているのだ。
このアプローチに対して、量子コンピュータの専門家からいくつかの反論が投稿されている。最初のものはScott Aaronson氏が自身のブログに投稿したもので、彼はQAOAが「いかなる高速化ももたらすという説得力のある議論はまだなされていない」と述べ、ただ一つの可能性のある例外を挙げている。また、この論文自体が、「QAOAの曖昧な収束のため、アルゴリズムの量子的な高速化は不明」と言及していることを指摘している。Moody’s Analyticsは、「Schnorr技法が適切にスケールすることが示されなかった」と指摘する論文を掲載している。その他にも、QAOAアルゴリズム自体がうまくスケールできない可能性があること、この手法を使ってもゲートレベルフィデリティ99.999%のNISQコンピュータが必要であることなどが明らかにされていないとのことだ。このレベルは、現在ある最高のマシンよりも2桁以上優れている。99.999%を達成するためには、まだ誤り訂正が必要かもしれない。最後に、QAOAは、ある問題に対して絶対的な最適化をもたらすことが保証されているわけではないことを指摘している。ユースケースによっては、たとえ2番目か3番目の最適解を提供したとしても、古典的なものよりも良い、あるいはより速い答えを提供できるのであれば、それはまだ有用なものだろう。しかし、因数分解ではそのようなことはない。答えは厳密でなければならず、2番手ではうまくいかない。
とはいえ、この論文が間違っていることが判明したとしても、それはこれから起こることへの警告であることは間違いない。米国政府は、実際の量子ブレークスルーに直面して、キー暗号化標準がいかに早く陳腐化するかについて、ますます懸念を強めている。昨年5月、ホワイトハウスは連邦政府機関に対し、運用において耐量子暗号化に迅速に移行するよう指示している。
Source
- The Register: Chinese researchers’ claimed quantum encryption crack looks unlikely
- South China Morning Post: Chinese scientists’ claims for new quantum code-breaking algorithm raise eyebrows in the US
- Moody’s Analytics: Are the RSA and Diffie-Hellman cryptosystems under threat sooner than previously thought?
- Shtetl-Optimized: Cargo Cult Quantum Factoring
コメント