誰か教えて!! 量子コンピュータ(ショアのアルゴリズム)でRSA暗号は破られるのか?

Last updated at 2023-12-07Posted at 2020-01-16

はじめに

今回の投稿は、誰かに何かを解説しようとするものではありません。

量子コンピュータ、量子力学の素人である私が、これを見た誰かが回答やヒントを教えて下さる事を期待して、現在の自分の知識・理解の範囲で思っている疑問を素直に記したものです。

量子コンピュータの勉強を始めてから最初にショアのアルゴリズムのサンプル回路を見たときに、位相回転ゲートに見えないほど小さく書かれたπ/2^n的な表現に気づいて**「えっ?こんなので実際にRSA2048の解読とか無理じゃない?」**と思った疑問が未だに解けていないので整理したいと思います。

記載内容には勉強不足、理解不足、誤解、不適切な表現、計算ミスなど多々あると思います。どのような些細なことでも結構ですので、遠慮なくご意見、ご指摘、ご指導をコメントしていただけると幸いです。

量子コンピュータでRSA暗号は破られるのか?

RSA暗号の安全性

RSA暗号の安全性は、現在のスーパーコンピュータをもってしても大きな素数の積(2048bitとか)の因数分解が現実的な時間でできないことに依拠しています。

なので将来、エラー訂正機能を持った量子コンピュータが完成すると、ショアのアルゴリズムを用いて解読が可能になると言われています。

ショアのアルゴリズム

非常に大雑把に言うと、量子コンピュータで(逆)量子フーリエ変換を用いて高速に因数分解をすることができるアルゴリズムと言えます。ショアのアルゴリズムで2048bitの因数分解を行えるようになれば、RSA2048が解けてしまうことになります。

残念ながら、現在の量子コンピュータは量子ビットの数も少なく、不安定な量子ビットに生じるエラーを訂正する機能を持たないためにショアのアルゴリズムやグローバーアルゴリズムをまともに実行することができません。

このアルゴリズムを実際の量子コンピュータで実行するには、エラー訂正機能が前提となります。

量子ビットのエラー訂正

訂正元となる量子状態にエラー訂正に必要な符号化が施せる前提で、デコヒーレンスやノイズにより発生する量子ビットのエラーを訂正するアルゴリズムとの理解です。|0>⇆|1>、|+>⇆|->、|i>⇆|-i>といった反転エラーを検出し補正することで計算結果を測定した時に正しい結果を得ることができるようになるようです。

エラー訂正についてはアルゴリズムの研究により前提となる物理量子ビットのエラー率が数%にまで引き上げられ、他方で物理量子ビットのエラー率も数%にまで引き下げられていて、実現の可能性が見えてきたと感じています。

(逆)量子フーリエ変換(=QFT†)

エラー訂正ができて安定的な量子ビットが使える前提のもと、ショアのアルゴリズムで2048bitの因数分解を実行するには、その(逆)量子フーリエ変換においてπ/2^2048の位相操作が必要になります。

量子ビットの位相操作に必要な分解能

π/2^2048の位相操作ということは、位相操作について半周期πに対して2^2048レベルの分解能が必要ということになります。言い換えると約10^616のオーダーでの分解能の制御が必要ということです。

例えば、超伝導量子ビットの制御には電磁波のパルスが用いられるようです。(πパルスとか)
この制御パルスに必要な分解能について、単純に時間や長さに置き換えた場合のスケール感を考えてみます。

時間のオーダーで考えると

・宇宙の年齢
　　137億年(1年は3×10^7秒)
　　10^17 秒
・フェムト秒
　　10^-15 秒
・アト秒
　　10^-18 秒
・γ線の周波数
　　10^24 Hz (周期10^-24秒)

宇宙の年齢をγ線の周波数レベルの時間分解能で見たとしても、分解能は僅か10^41程度にしかなりません。

長さ(波長)のオーダーで考えると

・(観測可能な)宇宙の大きさ
　　137億光年(1光年は約10^16m)
　　10^26 m
・原子の直径
　　10^-10 m
・γ線の波長
　　10^-16 m

(観測可能な)宇宙の大きさをγ線の波長レベルで見たとしても、分解能は僅か10^42程度にしかなりません。

量子状態の位相制御を宇宙規模の物差しで考えたとして、パルスを時間で制御するにしても長さで制御するにしても10^41〜10^42程度の分解能にしかならず、2048bitの因数分解に必要となる位相操作の分解能10^616には全く届きません。

(2020/1/17追記)
興味のある人は、こちらもどうぞ
数の比較 - Wikipedia

「1-qubitの任意の位相操作はH(アダマール)ゲートとT(π/8)ゲートで実現できる」らしい

理論上は「1-qubitの任意の回転は Hadamard演算とπ/8演算で効率よく構成(=必要精度で近似)できる．(Solovay-Kitaevの定理)」らしいです。

参考.
・Solovay-Kitaevの定理を「見える化?」する (2021/11/26追記)
・Exact and approximate synthesis of quantum circuits (2022/5/10追記)
・Optimal ancilla-free Clifford+T approximation of z-rotations (2022/5/10追記)
・量子コンピューターの計算精度とSolovay-Kitaevの定理 (2023/5/17追記)
・Solovay-Kitaevの定理〜Haskell実装例 gridsynth 〜 (2023/5/17追記)

つまり、実際の量子コンピュータでH(アダマール)ゲートとT(π/8)ゲートを十分に高い精度(できればエラーフリー)で実装できさえすれば、ここまでに述べた問題は解決できそうです。
しかし、これらのHゲートやT(π/8)ゲートといった基本操作に必要となる分解能(精度)は、やはりRSA2048を解くためには最低でも10^616のオーダーではないでしょうか?!

(2020/1/17追記)
位相制御の難しさにばかり頭が行って見落としていましたが、1-qubitの任意の回転はHとπ/8でできるそうですが、因数分解に必要な複数qubitの操作にはCNOT(制御X)のような制御ゲートも必要です。

その他の量子アルゴリズム

ショアのアルゴリズム以降、他にも因数分解の量子アルゴリズムが研究されているらしいのですが、そちらについては、まだどういったものがあるのか確認していません。
もし、それらが(逆)量子フーリエ変換に依存しているのであれば、基本的にはショアと同様の疑問が生じます。

(2020/1/17追記)
@TenninYan さんがコメントで論文を紹介くださったので、リンクを「関連情報」にも載せます。
・How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits

(2020/12/24追記)
素人(私)にはあまりに難しすぎる論文ですが、Shorのアルゴリズムをベースに、問題側の特性を生かした工夫(べき乗の剰余の計算を桁ごとに分割してQFTの桁数を2048bitから4bitに下げる(?)的な)を加え、さらにエラー率を下げるための様々な工夫がされているように見受けました。

(2022/5/25追記)
こちらの @shnchr さんの解説が素晴らしいです。(忘れないようにリンクを)
・量子コンピュータでRSAを解くのに必要な物は？

(心の叫び)誰か教えて!!

量子エラー訂正による安定した量子ビットが実現できるようになったとして、どのような工夫をすればπ/2^2048の位相操作を十分な精度(最低でも位相誤差π/2^2049未満)で実行できるのでしょうか?

例えば、誤差のないHゲートやT(π/8)ゲートはどのように実装すれば良いのでしょうか?

(2020/1/17追記)
今回の投稿をキッカケに、任意の回転を任意の精度でT(π/8)ゲートとHゲートで高速に近似できる方法(Solovay-Kitaev algorithm)や、Tゲートの精度を上げる「蒸留」という方法(Bravyi-Kitaev 15-to-1 magic state distillation protocol)があることを知りました。
また、勇気を出して問題提起したことに答えて @TenninYan さんがコメントでGoogleの論文を紹介して下さりました。
こちらの論文には、現時点の技術レベル(エラーとか)の延長上で私の疑問を始めさまざまな問題にどのように対応するかの過去の論文を含めた叡智が(引用を含めて)まとめられていそうです。
何分にもド素人なので、どのくらい先になるかは分かりませんが、何かについて理解がある程度できましたら整理して投稿し、共有したいと思います。

(2020/1/19追記)
@qope さんがコメントで教えて下さりました、回転ゲート(HやTなど)やCNOTのエラー訂正の方法(トラバーサル型ゲート?)の原理、位相誤差とエラー率の関係、エラー訂正のためのゲート増加とエラー率の減少および前提となるエラー率の閾値の関係などについてイメージできるように勉強を始めようと思います。(相変わらず数式とか見ただけではイメージができないので、時間はかかりそうですが)

(2020/12/24追記:コメント欄(@qupoさん)参照)
「しきい値定理」 (threshold theorem)、「p(n)個のゲートを含む量子回路は、部品の誤り確率がたかだかpであるハードウェアによるO(poly(log p(n)/ε)p(n))個のゲートを用いて、たかだかεの誤り確率でシュミレートできる。ここでpはある一定のしきい値より小さくp<p_th、使用するハードウェアの雑音に関しては合理的な過程が満たされるとするものとする」(ニールセン&チャン、木村達也訳「量子コンピュータと量子通信〈3〉量子通信・情報処理と誤り訂正」p178から引用)というものがあり、これにより理論的には一定条件をクリアできれば理論上π/2^2048精度の位相操作も実現できるそうです。
(ところで、π/2^2048精度(分解能10^616)の量子操作の正しさってどうやって確認(測定)するんだろう? 統計的な評価はできそうな気がしないし...)

参考文献

Cluster-based architecture for fault-tolerant quantum computation
量子計算超入門(p.236,pp76-93)

更新履歴

2020/1/15 初版
2020/1/16 関連情報追加
2020/1/17 @TenninYan さんにコメントを頂いての「追記」の追加と「その他の量子アルゴリズム」、「関連情報」に若干の追記
2020/1/17 T(π/8位相回転)ゲートの表記はT(π/8)ゲートと訂正させて頂きました。
2020/1/17 「数の比較」のリンク足しました。
2020/1/17 量子計算にはHや位相回転ゲート以外に制御ゲートが必要なのを見落としていたので追記しました。
2020/1/19 @qope さんにコメントを頂いて、今後勉強していくことについて追記しました。
2020/1/19 関連情報追加
2020/1/23 関連情報追加
2020/6/10 関連情報追加
2020/12/24 コメント追記
2021/4/9 関連情報 Quantum Computation and Quantum Informationにリンクを追加
2021/11/26 関連情報「Solovay-Kitaevの定理を「見える化?」する」へのリンク追加
2022/5/10 関連情報追加
2022/5/25 関連情報追加
2023/5/17 関連情報追加
2023/11/20 関連情報追加
2023/12/7 関連情報追加

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up