先日みかけた、RSA 2048ビットの解読に必要な量子ビット数が100万未満となり、1週間での解読が可能になったのは、modの近似に触れられていたことから、おそらくQFTの近似にも成功しているのでしょう。 これにより、各演算の計算量が従来のO(n²)やO(n³)といった複雑度から、O(n)〜O(n log n)程度にまで最適化された結果、必要とされる量子ビット数が大幅に削減されたものと考えられます。
もちろん、近似して、求めるべき解そのものが変わってしまっては意味がありませんが、今回のような近似処理では、最終的な「解」は変わらず、変化するのは確率振幅だけです。つまり、従来よりも少ない量子ビット数であっても、繰り返し実行することで期待値の範囲内で正解が得られる――という発想です。 それでこの「1週間での解読」とは、1回の量子演算が1週間かかるという意味ではなく、1週間程度にわたり何度も連続して量子演算を行えば、期待値レベルで1回は正解が出るという統計的アプローチを指しているはずです。たとえそれが非常に低い期待値であっても、現実的な時間内で正解が導けるのなら、それは「暗号が破られた」ことになります。
ただし、この方式が成り立つためには、量子コンピュータが提示してきた「解」が正しいかどうかを迅速に判定できる必要があります。ところが、どんな公開鍵暗号方式であっても、提示された秘密鍵から対応する公開鍵を算出する処理は、一般的なパソコンでも即座に可能です（それにより第三者が検証できて、暗号として使えるためです）。したがって、候補の秘密鍵がターゲットの公開鍵と一致するかどうかを検証する作業は非常に高速であり、この「数撃てば当たる」戦略が実行可能となってしまうわけです。
量子演算の近似が解そのものではなく確率振幅のみに作用する、これが厄介ですね。ほんと、暗号にとって厄介過ぎ、です。今後もさらなるこの戦略の進化がきますので、脱ECDSA（周期性のある暗号をやめる）が重要ですね。
