Chinese Scientists Report Using Quantum Computer to Hack Military-grade Encryption
こういう記事が出てましたのでちょっとチェックしてみました。
結論から言うとあまり進展はない感じなのと、ちょっと違うんじゃないかな。。。と思うところもあり微妙でした。
論文自体は、
The advance, led by Wang Chao of Shanghai University, poses a “real and substantial threat” to the security mechanisms used in banking and military sectors, as detailed in their peer-reviewed paper published on September 30 in the Chinese Journal of Computers, an academic journal run by the China Computer Federation (CCF)..
ここから手に入ります。
発端は中国のSouth China Morning Post (SCMP)の記事だそうです。
論文では組合せ最適化を利用した二つの方法を紹介していますが、これらはすでに既知の技術であってあまり革新性はなく、今回の論文に関してはその改善のようです。一つ目はN=pqの素因数分解を純粋に組合せ最適化問題として解くもので、結構前から行われているものです。主張の中では量子ゲートはサイズが小さいし、D-Waveの方がトンネル効果が使えて量子ビットが多いのでいいよと言ってますが、この主張は結構古い話で正直微妙かなと思いました。トンネル効果が抜けられるのは特定のスパイクだけと言われていてほとんどそれが起きる問題がありません。また、この論文ではD-Waveが2体までの相互作用までしか解けない一方、相互作用の分解を工夫して量子ビット数を減らせると言うことを改善したようです。
基本的な内容は昔下記のブログに書きました。
量子アニーリングとQAOAで素因数分解（組合せ最適化編）
量子ゲートのNISQ向け素因数分解アルゴリズム
基本的には量子ゲートでは多体問題を分解せずに解けるのでいいのですが、D-Waveはそれができないために一工夫必要で、そこを頑張ったと言う論文のようです。正直そのコースは今はあまりやられてないので、ちょっと微妙かなと思いました。D-Waveの利点が今回の問題に適しているかと言う優位性自体もかなり微妙かなと思います。
ただ、上記の中国の方法が不要になる新しいソルバーを最近個人的に提案したので、つながるかもしれないと言う点で検証は面白いかなとは思いました。
Tensor Network Based HOBO Solver
Yuichiro Minato
次にもう一つあります。こちらはQAOAをSchnorrの素因数分解アルゴリズムへ応用しています。フローは、事前準備として素因数分解したい整数Nから最初は格子上のCVP問題に落とし込みます。そこからBabaiのアルゴリズムを通じて得られるベクトルに関してより良い解を最適化問題で得ることによって、CVP問題の解を改善できるとおいうもので、それによってSchnorrのアルゴリズムを改善でき、最終的に素数のpとqを出力することができるというものです。
こちらも以前実行したことがあり、下記のブログを参照してみてください。
[レビュー]中国の暗号論文、NをCVPからBabaiのアルゴからコスト関数定式化ステップを確認
今回の論文は基本的にこのフローに沿っていますが、babaiのアルゴリズムで得られた結果を
のハミルトニアンで計算してサンプリングによって解を得たようです。合理的な計算かと思いますが、別にD-Waveでなくてもいいのでそれも微妙かと思います。普通の計算機でも計算できるかと思います。
と言うことで、なんかニュースになってたので気になって調べてみましたが、それぞれD-Waveを使って素因数分解で知られている手法を工夫して少し良くしたと言う感じですが、そもそものアプローチがそんなに有望視されていないのですが、それでも頑張って数字が伸ばせたのはすごいと思います。
以上です。