量子コンピューターはどれくらい複雑な問題を解ける？ - ITpro

mungkinbelum.blogspot.com

全905文字

　解きたい問題がどれくらい複雑かを調べる手段として、計算にかかる時間を見積もる方法があります。この観点からすると、とりわけ複雑な問題には、考える範囲をちょっと増やしただけで、計算にかかる時間が爆発的に増える傾向があります。暗号を例として説明しましょう。

　現在インターネットで標準的に使われている「RSA暗号」は、大きな素数を2つ掛け合わせた数を鍵として使っています。掛け合わせた数を素因数分解して元の素数を見つけるのに非常に大きな計算量が必要なことで安全性を担保しています。鍵の大きさを2進数でnビットとすると、素因数分解を求めるのに知られている限り最も効率のいい計算方法を使っても計算時間はnの指数関数になります。今使われている2048ビットの鍵を破るには、スパコンでも1億年以上もかかるといわれています。

　ところが量子コンピューターが登場すると事情ががらりと変わります。十分な能力を備えた量子コンピューターには、このような暗号を1日もかからずに破る能力があるのです。では実際、どれくらいの時間が必要なのでしょうか。米グーグルの研究者などが2019年に試算した結果は、暗号関係者に冷水を浴びせました。たったの8時間で解けることがわかったのです^1）。

　量子コンピューターがこれだけの威力を発揮できるのは、原理上、答えを出すまでの時間をものすごく減らせるからです。RSA暗号の場合、量子コンピューターは多項式で表現できる時間で計算を終えるとされています。多項式とは、例えばn2といった形になります。n＝100としても、前者（2¹⁰⁰）が30桁もの数字になるのに対して、後者（100²）はたかだか1万です。この差が、1億年と8時間という計算時間のあぜんとする違いに反映されるわけです。

　RSA暗号の鍵のビット数に応じて、普通のコンピューターと量子コンピューターの計算時間がどう変わるかを示したのが次の図です。図の左にある「総当たり計算」が全ての「1」「0」の組み合わせを検討する場合、真ん中のラインが従来のスパコン、一番下のラインが量子コンピューターに対応します。圧倒的な差があることは一目瞭然です。

RSA暗号の解読に必要な時間

（出所：日経クロステック）

[画像のクリックで拡大表示]

参考文献1） G. Gidney et al., "How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits,"

次回の一問一答

• 量子アニーリングと量子コンピューターは同じ？

  2022.02.14公開予定

Adblock test (Why?)

からの記事と詳細 ( 量子コンピューターはどれくらい複雑な問題を解ける？ - ITpro )
https://ift.tt/0M2HOsv