第46話 Shorのアルゴリズムのどこが凄いのか②？

これまでの話
第1話 量子の夜明け
...
第42話 Shor（ショア）のアルゴリズム
第43話 Shorが示した量子計算因数分解アルゴリズム
第44話 Shor量子計算因数分解アルゴリズム
第45話 Shorのアルゴリズムのどこが凄いのか①？

ショアのアルゴリズムは普通のパソコンでも実施できました。一体どこが凄いのでしょうか？ショアのアルゴリズムで最もコストのかかる計算はフーリエ変換部です。実際同じ事をパソコンでやると大きな数では計算が終わりません。

ビット数と計算コストの関係
（量子）ビットをqとするときフーリエ変換にかかる計算コストは大体次のような関係があることが知られています。

です。ここでFFTは高速フーリエ変換アルゴリズムです。これに対して重ね合わせによる量子フーリエ変換では

と見積もられています。まだピンと来ないですね。そこでインターネット上で使われる暗号で安全な128ビットでどれくらいの差があるのか見てみましょう。クロック数３ＧＨzのパソコンでショアのアルゴリズムを実施するとFFTを使う事になりますから、

３ＧＨzで浮動小数点演算ユニットは２とします。そうすると、理論上は大体、１秒間に6000000000回の演算が可能です。なのでおよそ

ほとんど不可能な計算だと分かりますね。では10310GFlopsのスーパーコンピュータではどうでしょうか？現在最高性能の10310GFlopsのスーパーコンピュータでは

やはり無理です。これでは効率の良い素因数分解アルゴリズムより一桁も遅い計算です。それでは量子計算による量子フーリエ変換ではどうでしょうか？仮に量子計算パソコンがあったと仮定して見ます。性能は先ほどのパソコンと同じ3GHzとします。（そういう数値で性能として良いのかはまだ量子計算パソコンが無いので分からないですが、あくまで仮定の話とします）。

なので、なんとパソコンレベルの量子計算パソコンでは

です。計算コストに桁違いの差があることが分かります。
ただし、これはQFTのビット計算だけに着目した比較です。実際にはスパコンは並列処理を行います（これは量子コンピュータの並列とは全く異なります）。なので様々な事を考慮すると概ねスパコンで１億年かかる計算が量子コンピュータでは 1日くらいの差になるようです。いずれにしてもこれは同時にRSA暗号の素因数分解が桁違いの速さで求められる事を意味しています。実際にはこれほどの高速計算まで到達できるのかは今後の研究成果に依存します。

量子計算はこれまで見てきたように重ね合わせを使って確率的に解を得ますがこれくらい高速だとそれでも良い事が分かります。つまり駄目だったらやり直せば良いだけですね。しかも量子アルゴリズムは解が観測される可能性を非常に高くしますから無節操なやり直しも無い訳です。

注1）1CPU辺り理論上Flops値は概ね「浮動小数点演算ユニットの数×クロック周波数」
として計算しました。
注2）FLOPSとは、コンピューターの処理速度をあらわす単位のことである。1秒間に処理可能な浮動小数点演算の回数
注3）スーパーコンピュータの性能Top500はhttp://www.top500.org/ で見る事ができる。
注4) 計算コスト http://www3.fed.or.jp/fedmeeting/sympo2003/pdf/ppt_fed2003takayanagi.pdf