Structure of Shor’s algorithm／Shorのアルゴリズムの構造

Peter Shorの素因数分解アルゴリズムについて見ていきましょう。

私たちが見たように、”量子”アルゴリズムというのは実際は、量子と古典のハイブリッドアルゴリズムです。初めは古典計算機で用いられていたものが、その後量子コンピュータによってアルゴリズムの特定の部分を実行（繰り返しや関数）することに用いられ、その結果を計測しています。それらの結果が用いられ、古典的な後処理に用いられています。量子コンピューターは、古典コンピュータの補助的なプロセッサとして活躍するのです。

Shorのアルゴリズムにおいては、量子的な繰り返し作業は、繰り返しの単位を見つける上で利用されます。これは、量子フーリエ変換(Quantum Fourier Transform)と呼ばれる手法などにおいて、単位を与える波の干渉を作り出す上で用いられます。私たちはその上で、 N の素因数を見つけるために、ユークリッドのアルゴリズム（ユークリッドの互除法）を用います。これらのステップを簡単に見ていき、一つ一つの細かい記事を見ていきましょう。

^{Fig.1. Block structure of Shor’s algorithm}

モジュロ演算

モジュロ演算（modなどと呼ばれる)とは、法（基準となる数(N)）に対して等しい、またはどれだ け大きい数になっても、その数が0から(N – 1)までの間になるまで、(N)引き続けるものであったと いうことを思い出してください。

このmodにおいては、どのような加法、乗法においても、最後の桁を見るだけで演算が可能です。例えば、(9 times 9 bmod 10 equiv 1( neq 81))となります。

(bmod 7)で、毎回４を足していくという関数を考えてみましょう。０から初めたとすると、0, 4そして8というように増えていきますが、8は7より大きいので、7を引いて、1に戻ります。そして再び4を足して5となります。(bmod 7)というのは、7を基準とした数学となり、最終桁だけを追っていけば良いのです。

関数の周期

多くの数学的関数は周期的です。つまりこれは、ある地点で関数を評価しつつ、段々と先へ進んでいくと、結果は評価し始めた点に近づいていくということです。実際は、シーケンス全体で、その繰り返しが行われています。この繰り返しにかかる時間の大きさを、周期と呼びます。

私たちは波について、様々に話してきました。そのため、関数の周期とは、波の周期のようなものと考えるかもしれません。実際、そのようなものなのです！

^{Fig.2. A simple sine wave}

正弦波のような、連続関数ではなく、モジュロ演算のような離散的な関数について見ていきましょう。(bmod 7)で、４を加えていく関数について見ていきましょう。それを表すとこのようになります。(x_{i+1} = x_i + 4 bmod 7)数字の順番としては、

[0,4,1,5,2,6,3,0]

というようになります。 7段階踏んだあと、初めと同じ0に戻ります。これを繰り返していくと、下のように、同じ数字の繰り返しが現れます。

[0,4,1,5,2,6,3,0,4,1,5,2,6,3,0,4,1,5,2,6,3,…]

0も4も全ての数字が、7つおきに出てきています。そのため、この関数の周期は7であると言うことができます。そしてこれを表すと、

[f(x+7)=f(x)]

というように書くことができます。

量子フーリエ変換

(a < N)を満たす素数を一つ選びます。その数について(f(x) = a^x bmod N)という関数(r)の周期を発見できた場合、(N)素因数を知ることができます。最も単純な方法はもちろん、(f(x))を2つの同じ結果が得られるまで計算し続けることです。確実に周期までの段階で終わらせることが可能です。これは理論的には可能ですが、現実的ではありません。なぜなら、数が大きくなるに連れて、周期は指数関数的に大きくなっていくからです。これは、すでにあるような数のふるいと呼ばれる手法よりも、効率的ではありません。他の手法が必要となります。

関数の周期を見つけるために、反転しやすい信号の周波数を見つけるための、古典的手法として、フーリエ変換が用いられます。もしこれらの結果の連続値のフーリエ変換の値を得ることができれば、周期を得ることができます。不運にも、あまりに古典的に行うと、私たちが描いたような結果のシーケンスからデータを取らなければならなくなってしまいます。

しかし量子コンピューターにおいては、関数の周期を見つけることは非常に現実的になってきます。全ての可能な値(x)を重ね合わせ状態とし、(f(x))を計算します。そうすることで、関数の結果の全ての重ね合わせ状態を得ることができます。もし2つの異なる値(x)が同じ(f(x))値を返したとき、それがその関数の周期となります。

不運にも、私たちはそれを直接行うことはできません。今まで見てきたように、重ね合わせの状態を観測しようとすると、量子的確率の振幅に依存する、ランダムな値が出てきてしまいます。(x)の値一つだけでは全く役に立ちません。そのかわり、フーリエ変換を量子形式に応用して、(x)の全ての間で干渉を作成することで、曲がりなりにも周期(r)を直接得ることができます。

もちろん、これは(f(x))の計算や、量子フーリエ変換が、技術的に厳しいと役には立ちません。冪剰余と量子フーリエ変換は、数の大きさによって、多項式時間での計算コストがかかり、古典的方法で周期を見つける超多項式的な時間に比べると、計算時間を非常に削減できます。

これはShorのアルゴリズムの中心で、今後数十年で最も技術的結果の出そうな分野の一つになると思います。

ユークリッドのアルゴリズム

最後の古典的段階は、周期(r)を発見し、それを用いて素因数を発見することです。これは古典コンピュータで、2つの数の最大公約数を見つけるための、ユークリッドのアルゴリズムを用いて行われます。ユークリッドのアルゴリズムは数字の大きさによって多項式時間的に計算時間が変化し、実際、古典コンピュータと計算速度は変化しないため、このステップは難しく考える必要はありません。

周期(r)を正しく見つけられたとすると、(N)と(a^{(r/2)}+1)と(a^{(r/2)}-1)の最小公倍数を見つけることで、(N)の素因数を導くことができます。

以上のまとめ

(n)bitで表される、(N)の素因数の求め方をおさらいしてみましょう。アルゴリズムは以下のステップで構成されています。

1. (N)より小さい素数(a)を選ぶ
2. (a)が、(N)の素因数であるかを確かめます。もしそうであればそれで終わりです。
3. そうでない場合、量子コンピュータとプログラムを用いて、周期を求めます。
4. 量子コンピュータにおける最も重要なステップは、全ての(x)に対する(a^x)重ね合わせ状態を計算することです。全て(bmod N) によって行われます。(vert xrangle)とあまりはどちらも量子レジスタの中に現れます。
5. 余りを計算します。（技術的には必要ありませんが、説明を簡単にするために、この手法を用いていきます。)
6. (vert xrangle)に対して量子フーリエ変換を行います。
7. レジスタ(vert xrangle)測定します。この結果は、冪剰余の周期の実数倍となっています。
8. もし(r)が0より大きければ(a^{(r/2)}+1)と(a^{(r/2)}-1)を計算し、0または0より小さいのならば、新しい(r)を見つけるために再び量子計算へ戻ります。
9. ユークリッドのアルゴリズムを用いて、各値と(N)の最大公約数を求めることで、(N)の素因数である2つの数字を得ることができます。

個々の技術について、より詳しく見ていきましょう。