概要
格子暗号を勉強するモチベーションの１つとして、格子暗号が量子コンピュータ耐性をもつ暗号という事実も大きな要因の１つである。
SSL通信などに用いられている従来のRSAなどの通信は量子コンピュータによって破られるということは知っているが、実際にどうやって破られるのかよく知らなかったので調べてみた。備忘録的な要素あり。
注）専門書などはまだ読めておらず、にわか知識となります。
キーワード
- ショアのアルゴリズム
- 量子フーリエ変換
ショアのアルゴリズム
キータに素晴らしい記事があり、それらを参照すると大変わかりやすい。(例えばこれや、とかこれ)
簡単にまとめると、ショアのアルゴリズムは量子コンピュータを用いてある自然数 $N$の因数分解を多項式時間で解けるとされるアルゴリズムである。いくつかのステップに分かれており、実際に量子コンピュータを活用するのはそのうちの1ステップであり、古典コンピュータで行う演算と組み合わせることによって全てのプロセスを構成しています。
どこに量子コンピュータが使われるかというと、先ほどの$N$を法とした時のある自然数$a$の位数、つまりある$T$で、$a^T=1 ~ mod ~N$となるようなTを見つけるところに量子コンピュータを用います。この$T$は周期とも書いてあり、これを確率関数で量子コンピュータは返してくれるのですが、これが多項式時間で実行可能ということです。その他の古典コンピュータで行われるプロセスは全て多項式時間で行えるプロセスなので、ショアのアルゴリズム全体の実行も多項式時間で済むことになります。
この$T$の関する確率的分布（確率密度関数）を量子コンピュータで求めるところに、量子フーリエ変換が用いられています。
量子フーリエ変換
いくつかの素晴らしい記事を読みました。計算は全ては追えませんでしたが、フーリエ変換を行う際のプロセスを、基底ケットベクトルに対応した変換と置き直して進めていくところが素晴らしいなと思いました。
参考にしたのは、こことか、 こことか、このへんです。
ある時系列データがある時に、それを連続的な周波数を持つ正弦波で近似することをフーリエ変換と言いますが、もし分解する周波数が連続でない時、離散フーリエ変換と呼びます。
量子フーリエ変換は、この離散フーリエ変換を量子コンピュータで求めるときのやり方、計算アルゴリズのことを指しています。量子コンピュータの前提として、状態は量子ビットの重ね合わせ状態として書かれ、それらは基底ベクトルの重ね合わせでした。それらを実際に観測、つまり何らかの状態と掛け合わせることで、係数の２乗を確率として何らかの物理量が観測できました。量子フーリエ変換では、各基底ベクトルを離散フーリエ変換される要素とみなし、観測した時に出てくる値を、離散フーリエ変換後の値としています。
数式で追うと少しわかりやすいですが、入力$x$から離散フーリエ変換を施した$y$を求める際に、うまく式変形することで、この導出を、$x$の基底ベクトルの変換とみなしています。
導出は専門書なり、上の参考文献を追っていくと、この変換はアダマールゲートと、位相変換ゲートのを再帰的に入力状態に作用すればいいことがわかります。
n-qubitの入力に対する演算（ゲート）の数を数えると、$n^2$となるので、実質$2^n$個のサンプルに対して$O(n^2)$のオーダーで離散フーリエ変換を計算できたことになります。一方、高速フーリエ変換（バタフライ演算を利用したもの）では、仮に同じ$2^n$個のサンプルに対して$O(n\times 2^n)$の演算が必要なので、量子フーリエ変換の方が圧倒的に早くなるというわけです。
おまけ グローバーのアルゴリズム
いろいろブラウジングしていくとグローバーのアルゴリズムというのも有名な量子アルゴリズムだとわかったので追記。
参考にしたのはwikipediaと、このすぱらしい記事。
量子コンピュータを用いて、$N$個のなかから特定の１つの物を見つけたい時に、$O(N)$普通にかかるところを、$O(\sqrt{N})$で可能にするアルゴリズムで、たとえば128ビット長の共通鍵暗号の共通鍵を総当たりで求める際に、$2^64$の計算量で求めることができます。くわしくは書きませんが、意外と単純で、振幅増幅手法を入力状態に行うことでこれを可能にしています。
最後に
にわか記事となりましたが、いろいろ勉強していきたいとおもいます。
おわり。