Modular Exponentiation／冪乗余

Shorのアルゴリズムにとって重要なポイントは、関数(f(x) = a^x bmod N)が周期的であり、量子フーリエ変換を用いるとその周期を抽出することができるという点にあります。しかし、これを求めるには重ね合わせ状態の(f(x))を計算することが必要になります。効率よく計算するにはどうすれば良いでしょうか？

状態について

ここで、取りうる全ての(x)に関する重ね合わせ状態(vert xranglevert f(x)rangle)が必要になります。

周期をうまく見つけるには(vert xrangle)の量子ビット数が(N)のビット数の2倍になる必要があります。例えば古典コンピュータが解ける最高数768ビット数よりも大きい、1024ビットの要素(vert xrangle)を表すためには2,048量子ビット必要になります。

これは、指数が(2^{2^{2049}-1})よりも大きいということを意味します。数字が非常に急速に伸びると推測でき、実際そうなっています。 例えば、(a=3)とすると(3^{1024} = 373391848741020043532959754184866588225409776783734…)となります。1,024ビットでいえば(3^{2^{2048}})もの膨大な数の計算が必要となり、これはなんと(10^{600})桁以上にものぼります！

しかしながら幸運なことにこの場合モジュロ演算で作業しているのですべての桁を書き留める必要はありません。(このような数を書き留めていくと宇宙のすべての原子の数より多くの数が取り込まれるため、各原子に10進数の1桁を書き込むこともできます）。つまり全体を計算するのではなく、代わりにモジュロを取ることで(N)を法としてすべての乗法を行うという方法にすれば膨大な計算もやりやすくなります。

したがって、状態を書き留めるには(N)が 1,024ビットの数であれば2,048量子ビット、(vert xrangle)を保持するには1,024が必要です。計算中には一時的に様々な変数が必要になるため、場合によっては最も速くで最も単純な形式の計算でも合計5〜6000量子ビットが必要になります。

アルゴリズムの発想

3の1024乗を計算する時、皆さんならどうするでしょうか？例えば(3^1, 3^2, 3^3, 3^4, …)が (3, 9, 27, 81, 243, …)という調子で1024回繰り返すという方法があるでしょう。しかしこの方法だとたとえ1000ほどの指数であったとしても非常に煩雑になりますし、大きな桁の指数を書くのもなかなか大変です。同様に我々はしばしばこの計算の指数関数的増加という問題によく悩まされます。上記の説明では空間的問題を解決しましたが今度は時間的問題を解決する必要があります。

ただし次のように計算を工夫することができます。毎回3を掛ける代わりに、毎回の計算の結果を2乗していくという方法です。

(3times 3 = 9 = 3^2)
(9times 9 = 81 = 3^4)
(81times 81 = 6561 = 3^8)
(vdots)
(3^{512}times3^{512} = 3^{1024})
(textrm{(a really big number)}timestextrm{(same really big number)})
(= textrm{(that enormous number above)})
(vdots)

この調子で(2^n)を(n)ビット分繰り返していきます。

数学的解釈

冪乗余では(2^n)のモジュロ演算をする必要があることがわかりました。つまり一度に1桁ずつすべての部分積を計算し合計するという、我々がすでに学校で学んだ内容で計算ができるのです。(n)個の量子ビットからなる(n)個の部分積をそれぞれ加算することで求めるわけですが、この計算を量子コンピュータ上で行うにはコースの前半で学習した CNOT と CCNOT ゲートを使用した(O(n))ゲートが必要になります。

しかし残念なことに実際にモジュロ演算を実行するには、計算結果が(N)より大きくなったかどうかを判断した後にもし大きければ レジスタから(N)減算するというかなり煩雑な行程が必要となってしまいます。もちろん実装しようとしているアルゴリズムにもよりますがこれでは計算量は5倍程度に増加してしまいます。

完全に冪乗余の計算をするのであれば次の式が必要になるということです。

(n)ビットの因数分解を指数関数ではなく多項式で行うアルゴリズムのこの段階での実行時間は (O(n^3))になります。

まとめ

特定のアプリケーションを実行するための量子コンピュータを構築していく際に我々が最も神経をすり減らすべき点は、主に空間（量子ビットの数）と実行時間、そしてフィデリティ（エラーが発生しない確率）の３点でしょう。

このコースの後半でも説明しますが、あらゆる最適化によって、(n)ビットの数の因数分解に必要な量子ビットは、(5n)以上の量子ビットから約(2n)量子ビットに減少しました。しかしながら、依然このプロセスは複雑でもちろん計算速度も十分に早いとは言えません。 そのためShorのアルゴリズムが古典的には解決できない問題を解決するためには何千もの非常に高品質な量子ビットが必要になってくるという重要な工学的課題をクリアしていく必要があります。

計算の効率は回路の深さ（いったいいくつのゲートを実行する必要があるか）によって決まります。実行しているアルゴリズムと量子コンピュータ自体の構造の両方に依存しますが、複数のゲートを並行して同時に実行することで必要な時間を短縮することもできます。いかに簡単に量子コンピュータ間で一方の側から他方へのデータのやりとりができるかにかかっています。

一方でフィデリティはというと、システム内の量子ビットの数と回路深度に依存して決まります。量子コンピュータの性能というのは量子ビットの数に時間ステップの数を掛けることで測ることができます。全操作のなかで平均して１つの誤差までは許容するとして、ここでは 量子ビットだったとしましょう。これだと約(5n^3 approx 5times 10^9)の時間ステップが必要なので、 (25n^4 approx 2.5times 10^{13})ゲートで1つ以下のエラー発生確率ということになります。これはかなり高い精度ですね！（もちろんこの計算は厳密ではありませんが）。もちろん多くのアルゴリズムがより少ない量子ビット、より少ないタイムステップ、エラーに対する耐性をを必要とします。こういった限界を見つけることも研究の大変重要な領域です。