ショアのアルゴリズムの感覚的理解


日経サイエンス2020年2月号

日経サイエンスの2020年2月号に量子コンピューターの凄さを直観的に理解できる素晴らしい説明がありましたので御紹介いたします。

「例えば素因数分解を高速で解く「ショアのアルゴリズム」は、重ね合わせになった状態どうしを干渉させることで、ビットパターンの間に生じた周期性を抽出し、そこから素因数を算出する」

これを読んでピンと来ました!そうか、量子フーリエ変換というのは、瞬時に約数を見つけることができる操作なのか!量子フーリエ変換をやって周波数特性のグラフを見た時に、どこにも飛び出た周波数が見つからない時(f特がフラットな場合)、そのデータは約数を持たず素数になる、というわけなのです!N量子ビットの重ね合わせの威力に驚きました!

これは古典コンピューターでしらみつぶしに割り算することを繰り返して素数かどうかを判定していったり、多少高速化するアルゴリズムを使って計算するのとは、桁が違う計算方法です。指数関数的に計算量が違うのです。まあ、計算というよりは、観測結果を計算に見立てている、という感じなのでしょうけど!

これは現在使われている暗号の強度(暗号資産の価値)に関する重大問題ですが、実際に暗号を解読しようとすると、エラー無く素数の有無を確定させなければなりませんので、物理量子ビットは論理ビットの数千倍以上の量が必要とされています。ビットコインの楕円曲線暗号と同程度の強度を持つ2048bitRSA暗号を解読するのに、2千万物理QBIT以上が必要になるのではないかと見積りされています。

https://cacm.acm.org/magazines/2013/10/168172-a-blueprint-for-building-a-quantum-computer/fulltext ビットコイン相当の2048ビット素因数分解に必要な規模は60億物理QBITと見積もった論文。

https://arxiv.org/pdf/1010.5022.pdf Nbit素因数分解には6倍の論理QBITが必要であること、エラー訂正のために論理QBITの6240倍の仮想QBITが必要であることを報告した論文。つまり2048bit素因数分解なら、7667万仮想QBITが必要。

https://arxiv.org/pdf/1905.09749.pdf  2048bit素因数分解には2千万物理QBITで足りるとする論文。

※参考記事

耐量子暗号


コメントを残す

メールアドレスが公開されることはありません。