第 14 回 量子アルゴリズム

本日の内容

• 14-1. 簡単な量子アルゴリズム
• 14-2. 素因数分解
• 14-3. 量子探索
• 14-4. 量子コンピュータの基礎
• 14-5. 量子コンピュータのプログラミング
• 14-6. 有名なアルゴリズム
• 14-7. 参考文献

14-1. 簡単な量子アルゴリズム

14-2. 素因数分解

量子Fourier変換

複素数ベクトル $x_0,...,x_{N-1}$ の離散Fourier変換 $y_0,...,y_{N-1}$ は次式で与えられる

量子Fourier変換は正規直交基底 $\left|0\right.⟩,...,\left|N-1\right.⟩$ に対して 次の線形オペレータになる。

ゲート $R_k$ を次のように定義する

位数発見

14-3. 量子探索

コンピュータとは、計算をさせる装置である以上、何らかの物理法則にした がっています。 我々の世界を支配している物理法則は相対論的量子力学ですから、この力学 に基づいた計算原理を考える必要があります。 現在の電子コンピュータは、シャノンが示したbool演算を実現する電子回路を 原理として動作しています。 しかし、これらと異なる原理による計算が不可能というわけではありません。 ここでは、量子力学を原理とした計算について紹介します。

量子 bit

量子コンピュータで行う計算も情報処理に違いありませんので、情報の単位 は bit になります。 量子状態でbitを保持できるとします。 量子状態は人間による観測によって確定して、情報を取り出すことができま す。 但し、量子状態は通常は確率的な値になります。つまり 1 bit を表す量子 状態を観測すると、確率 a で 0 が取り 出せ、確率 b で 1 が取り出せる ということになります。 この量子bit(q bit)の実現方法も色々議論されてい ますが、ここでは実現法ではな く、数学モデルについて説明します。

量子状態には、重ね合わせという概念があります。 これは複数の状態が同時に重ね合わさっていて、人間が観測することにより、 一つの状態に収束しそれが観測されるという概念です。 これをコペンハーゲン解釈といいます。

量子力学の問題点を指摘するための、「シュレーディンガーの猫」という思考 実験があります。これは、箱の中に猫を綴じ込め、α線の発生源、 観測器、毒ガス発生器を仕組み、α線が観測されたら毒ガスが発生し、猫が 死ぬように作られた装置を考えます。 一時間以内にα線が観測される確率が 50% であるとします。すると、コペンハーゲ ン解釈によると、箱の中の猫は、生きている猫と死んでいる猫が量子状態で 重ね合わさっていると考えることができます。 この生きている猫と死んでいる猫の重ね合わせの状態というのは、人間の思 考として俄に受け入れがたいものですが、コペンハーゲン解釈ではそう考え るもので、しかも、実際に見ようとすると一つの状態に収束してしまうので、 決して重ね合わせ状態を観測することはできません。

ここで、Dirac の記号を導入します。 行ベクトルを $\left.⟨\mathit{\phi }\right|$ と書き、ブラベクトルと呼びます。 一方、 列ベクトルを $\left|\mathit{\psi }\right.⟩$ と書き、ケットベクトルと呼びます。 すると、内積は $⟨\mathit{\phi }|\mathit{\psi }⟩$ と書けます。

さて、量子ビット(q bit) に関しての数学モデルを考えます。0 の状態と 1 の状態をそれぞれ線形代数の位置ベクトルとし、正規直交基底であるとしま す。 0状態の基底を $\left|\mathit{0}\right.⟩$ で表し、 1状態の基底を $\left|\mathit{1}\right.⟩$ で表すと、これは二次元の正規直交基底なので次が成り立ちます。

これの重ね合わせは $a\left|\mathit{0}\right.⟩+b\left|\mathit{1}\right.⟩$ と書けます(a,bは複素数)。 状態ベクトルが常に大きさが１であるとすると、 ${\left|a\right|}^2+{\left|b\right|}^2=1$ という制約が必要です。 この時、 0, 1 がそれぞれ観測される確率は、 ${\left|a\right|}^2，{\left|b\right|}^2$ になります。

多 q bit

さて、複数の量子ビットの取扱いをどうするかですが、基本的には同じ考え 方をします。 2 bit の場合、取りうる状態は 00, 01, 10, 11 です。 この 4 状態はそれぞれ別の状態なので、正規直交基底になります。 4次元の正規直交基底なので次のようになります。

これらの状態の重ね合わせを次のように書きます。

つまり、これは4次元単位球の表面の位置ベクトルを意味します。 $\left|\mathit{\phi }\right.⟩$ を観測して、 00, 01, 10, 11 が観測される確率は、それぞれ ${\left|{\alpha }_{00}\right|}^2,{\left|{\alpha }_{01}\right|}^2,{\left|{\alpha }_{10}\right|}^2,{\left|{\alpha }_{11}\right|}^2$ になります。

このように単純にビット数が増えると、次元が増えます。 これを演算として扱う、テンソル積を導入します。 これは、内積空間 V, W に対して、それぞれの基底が $\left\{\left|{\mathit{\xi }}_1\right.⟩,...,\left|{\mathit{\xi }}_n\right.⟩\right\}$ , $\left\{\left|{\mathit{\eta }}_1\right.⟩,...,\left|{\mathit{\eta }}_m\right.⟩\right\}$ である時、 $\left|\mathit{\phi }\right.⟩\otimes \left|\mathit{\psi }\right.⟩=\left|\mathit{\phi }\mathit{\phi }\right.⟩$ の意味は前述した通り、次元を拡張するだけです。

n個の q bit はこの様に2n次元の基底の重ね合わせで表現されます。

量子計算

さて、この q bit を物理現象に基づいて計算させることを考えます。 これは量子力学に従います。 先ほども述べたように、大きさ 1 で正規化するので、実際にこの量子計算 は q bit に対するユニタリ行列の積になります。

さらに、研究により、複雑なユニタリ行列は以下のような基本的なユニタリ 行列を多次元に拡張(0を挿入)の積で表せることが分かっています。

Hadamard

$\frac{1}{\sqrt{2}}\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right)$

位相

$\left(\begin{array}{cc}1& 0\\ 0& \mathrm{i}\end{array}\right)$

制御NOT

$\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 0& 1\\ 0& 0& 1& 0\end{array}\right)$

π/8ゲート

$\left(\begin{array}{cc}1& 0\\ 0& {\mathrm{e}}^{\mathrm{i}\mathrm{\pi }/4}\end{array}\right)$

従って、これらのユニタリ行列と対応した物理現象が起きるような装置を作 成すれば、量子コンピュータが実現できるようになります。 一つのq bit を実現するのに、2次元のベクトルが必要で、 上記のユニタリ行列が2または4次元なので、これは従来のコンピュータの概 念では論理ゲートにあたります。 つまり、ある q bit の列、 $\left|\mathit{\phi }\right.⟩$に対して上記のユニタリ行列 U1, U2,...,Un があって、 $U_1{U}_2...U_n\left|\mathit{\phi }\right.⟩$ を計算するのに、実際は個々の特定の q bit に対して、上記の定めら れた演算を行う回路のようなものを考えれば良いことになります。

14-4. 量子コンピュータの基礎

二次元複素ベクトル空間

また、複素数 $c=x+y\mathrm{i}$ に対して、共役 を $c^{*}=x-y\mathrm{i}$ で表します。 また、大きさは $\left|c\right|=\sqrt{a^2+b^2}$ とします。

行列 $\widehat{A}=\left(a_{i⁣j}\right)$ に対して、転置行列を ${\hat{A}}^t=\left(a_{j⁣i}\right)$ で表します。 また、エルミート行列 は ${\widehat{A}}^{*}=\left({a^{*}}_{j⁣i}\right)$ で表します。 さらに、単位行列を I としたとき、ユニタリ行列 U は下記を満たす 正方行列です。

一様な磁場の中での陽子などの スピンを考えると、 特定の量子が重ね合わさっている状態で、観測すると 0 の情報か 1 の情報が 得られます。 このように、行列力学的な解釈として現象が二現象の重ね合わせになるような ものをデータの保存を行う単位として選びます。 この時、状態として、二つの現象を区別する単位ベクトルを $\left|0\right.⟩=\left(\begin{array}{c}1\\ 0\end{array}\right)$ と $\left|1\right.⟩=\left(\begin{array}{c}0\\ 1\end{array}\right)$ とし、これの重ね合わせを計算の単位(1bit)とすることとします。 これを Qbit と呼びます。 φ=φ0 (1,0) + φ1 (0,1) $\mathit{\psi }={\psi }_0\left(\begin{array}{c}1\\ 0\end{array}\right)+{\psi }_1\left(\begin{array}{c}0\\ 1\end{array}\right)={\psi }_0\left|0\right.⟩+{\psi }_1\left|1\right.⟩$ となっているような状態の時、 $\left(\begin{array}{c}1\\ 0\end{array}\right)$ に対応した現象が実際に観測される確率は、 $\frac{{{\psi }_0}^2}{{{\psi }_0}^2+{{\psi }_1}^2}$ |φ1^2/(φ1^2+φ2^2) となります。

さらにこの現象が複数存在し、直積的な関係のあるような状況を考える。 つまり、 $\left|{\mathit{\psi }}_1\right.⟩={\psi }_{1⁣0}\left(\begin{array}{c}1\\ 0\end{array}\right)+{\psi }_{1⁣1}\left(\begin{array}{c}0\\ 1\end{array}\right)$ と $\left|{\mathit{\psi }}_2\right.⟩={\psi }_{2⁣0}\left(\begin{array}{c}1\\ 0\end{array}\right)+{\psi }_{2⁣1}\left(\begin{array}{c}0\\ 1\end{array}\right)$ の直積 $\left|{\mathit{\psi }}_1\right.⟩\otimes \left|{\mathit{\psi }}_2\right.⟩=\left|{\mathit{\psi }}_1,{\mathit{\psi }}_2\right.⟩$ を考える。

最初の2現象と次の2現象に関して、起きうる現象は 最初が　　で、次が 最初が　で、次が など4通りの組み合わせがある。 これに対して、それぞれ単位ベクトルを用意し、 と単位ベクトル同士の直積を定義する。 $\left|0\right.⟩\otimes \left|1\right.⟩=\left|0,1\right.⟩$ などと定義します。

これは、 |φ1> = φ10(1,0)+φ11(0,1) |φ2> = φ20(1,0)+φ21(0,1) 単位ベクトル (1,0,0,0), (0,1,0,0), (0,0,1,0), (0,0,0,1) $\left(\begin{array}{c}1\\ 0\\ 0\\ 0\end{array}\right)$ , $\left(\begin{array}{c}0\\ 1\\ 0\\ 0\end{array}\right)$ , $\left(\begin{array}{c}0\\ 0\\ 1\\ 0\end{array}\right)$ , $\left(\begin{array}{c}0\\ 0\\ 0\\ 1\end{array}\right)$ に対し て、

これを |φ1,φ2> と書くと

を意味します。 同様の意味で 以下を |φ1,...,φn> のような表記をします。

n 個の 2x2 の正方行列 $A_1,...,A_n$ について、下記の様に積を定義する。特に $A_1\otimes ...\otimes A_n$ をテンソル積と言う。 (n Qbit に対して、 2ⁿ 個の計算があることに注意)

量子チューリング機械

量子チューリング機械はテープとして、 Qbit が連続してあるようなものを考 えます。 また、状態遷移関数は $\delta \left(p,a,b,q,d\right)=c$ δ(p,a,b,q,d)=c という 状態が p, ヘッドが a を読んでいるとき(観測ではなく)、新たに b を書き込 み、状態を q に移し、ヘッドの方向を d に移動する事象の確率振幅を |c|² と定義する。 このとき、行列 M_δ のc1 行 c2 列は、 c2 から c1 への 1 ステッ プの遷移と対応したδの値になる。 ただし、ここでも M_δ はユニタリ行列になる。

14-5. 量子コンピュータのプログラミング

NOT

$\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)\left|\mathit{\psi }\right.⟩={\psi }_{1,0}\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)\left(\begin{array}{c}1\\ 0\end{array}\right)+{\psi }_{1,1}\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)\left(\begin{array}{c}0\\ 1\end{array}\right)$ |x> → |1-x>

AND

f(x,y,0)=x,y, x and y

|0> <0| x |0> <0| x I + |0> <0| x |1> <1| x I + |1> <1| x |0> <0| x I + |1> <1| x |1> <1| x (0 1 ; 1 0)

14-6. 有名なアルゴリズム

Shor のアルゴリズム

実は、 n Qbit のベクトルに対して、離散フーリエ変換を行ったときの nQbit の関数表は量子多項式時間で求めることができます。

Shor は量子コンピュータを使って、多項式時間で高い確率で、因数分解と、 離散対数問題が解けることを示しました。

y^r = 1 mod n となるようなもっとも小さい r を y の mod n のオーダーと言います。 もし、非自明な r が求まると、 n の素因数分解ができます。

1. 入力を n とします
2. n²≤q≤2n² となる「なめらかな整数」q を 選びます
3. n と互いに素な整数 x をランダムに選びます
4. 同じ x を用いてオーダー log q 回繰り返す
   1. 二つの量子変数 reg1, reg2 を用意する
   2. reg1 は 0 から q-1 までの全ての値の重ね合わせとする
   3. reg1 の各値 a に対して、x^a mod n の値の重ね合わせを reg2 に入れる
   4. reg2 を観測する。 k' が観測されると、reg1 には x^a' = k mod n となるような a' が観測できる
   5. この、 a' を離散フーリエ変換する
   6. フーリエ変換の結果を観測すると、ある値 c' が得られる。 これは、 q/r の λ 倍になっている
   7. c'/q の連分数展開を行うと λ/r が求められる
5. これによりサンプルがいくつか分かり、最終的に r が求まる。
6. gcd(x^r/2-1,n) と gcd(x^r/2+1,n) より n を素因 数分解する

Groover の選択問題

関数 f(x) が特定の x=x0 で f(x0)=1 になり、他の x では f(x)=0 となるよ うなことを考えます。

14-7. 参考文献

1. 清水明 「新版量子論の基礎　その本質のやさしい理解のために」新物理学ライブラリ別巻2, サイエンス社(2003)
2. Michael A. Nielsen, Isaac L. Chuang 著、木村達也訳「量子コンピュータと量子通信 I 量子力学とコンピュータ科学」オーム社(2004)
3. Michael A. Nielsen, Isaac L. Chuang 著、木村達也訳「量子コンピュータと量子通信 II 量子コンピュータとアルゴリズム」オーム社(2005)
4. Michael A. Nielsen, Isaac L. Chuang 著、木村達也訳「量子コンピュータと量子通信 III 量子通信・情報処理と誤り訂正」オーム社(2005)
5. 上坂 吉則 著「量子コンピュータの基礎数理」コロナ社(2000)
6. ランダウ、リフシッツ著、広重徹、水戸巌訳「力学」増訂第3版、 ランダウ＝リフシッツ理論物理学教程、東京図書(1974)
7. 高橋康「解析力学を学ぶための解析力学入門」増補第2版、講談 社サイエンティフィック(2000)