量子計算

ここではあくまでも計算モデルとして量子計算を眺め、なにが実現出来るかを調べる. つまり物理学的な視点にはあまり興味がない.

INDEX

qbit (量子ビット, Qbit, qubit)

古典コンピュータにおける計算にはbitを用いる. これは 00 または 11 のいずれかの状態を取るものである. 一方で、qbit はこの2つの状態を重ねあわせて持つ. 具体的には2つの状態を線型結合として記述される.

qbit が 00 である状態を |0|0\rangle、 qbit が 11 である状態を |1|1\rangle と書く (bra-ket記法).

一般にはこれらの重ねあわせ (線型結合): α|0+β|1\alpha |0\rangle + \beta |1\rangle で表される. ここで α,β\alpha, \beta虚数. ただし物理学の要請から、 |α|2+|β|2=1|\alpha|^2 + |\beta|^2 = 1 という係数の制約がある.

実数 α\alpha について |α|2=α2|\alpha|^2 = \alpha^2. 虚数 α\alpha について |α|2=α*α|\alpha|^2 = \alpha^* \alpha.

観測

|α|2+|β|2=1|\alpha|^2 + |\beta|^2 = 1 とあるが、これらは確率を意味する. すなわち、 qbit α|0+β|1\alpha |0\rangle + \beta |1\rangle を実際に観測すると、 確率 |α|2|\alpha|^2|0|0\rangle を得、 確率 |β|2|\beta|^2|1|1\rangle を得る. 観測という行為は qbit に干渉する. 例えば |0|0\rangle を得たとき、 qbit α|0+β|1\alpha |0\rangle + \beta |1\rangle|0|0\rangle に変化するという性質を持つ. もちろん |0|0\rangle はそれ以降、いくら観測しても |0|0\rangle のままである.

nn qbit

bit と同様に nn 個の qbit を並べた場合を nn qbit として考える.

簡単に n=2n=2 とする. 1つ目が |0|0\rangle で 2つ目が |1|1\rangle であるとき、 それらを並べて出来る 2 qbit の状態を |01|01\rangle であると書く. すると 2 qbitは |00,|01,|10,|11|00\rangle, |01\rangle, |10\rangle, |11\rangle

の四通りの状態を取り得、これらの線型結合で一般には表される. すなわち、

α00|00+α01|01+α10|10+α11|11\alpha_{00} |00\rangle + \alpha_{01} |01\rangle + \alpha_{10} |10\rangle + \alpha_{11} |11\rangle

が一般の 2 qbit の表現である. 係数の制約は |α00|2+|α01|2+|α10|2+|α11|2=1|\alpha_{00}|^2 + |\alpha_{01}|^2 + |\alpha_{10}|^2 + |\alpha_{11}|^2 = 1 であって、それぞれがそれぞれを観測する確率になる.

それぞれが α1|0+β1|1\alpha_1 |0\rangle + \beta_1 |1\rangleα2|0+β2|1\alpha_2 |0\rangle + \beta_2 |1\rangle だったとする. 観測する確率は qbit 毎に独立だとすると、

であることが確認できて、実際そう.

部分的観測

nn qbit の内 1つの qbit (α|0+β|1\alpha |0\rangle + \beta |1\rangle) を観測した結果、 その qbit の状態は先述したとおり、観測された状態に確定して固定されるが、 残りの n1n-1 qbit についてはなおも重ね合わせの状態を保ったままで観測が干渉することはない.

例として、 2 qbit α00|00+α01|01+α10|10+α11|11\alpha_{00} |00\rangle + \alpha_{01} |01\rangle + \alpha_{10} |10\rangle + \alpha_{11} |11\rangle

の 1 qbit 目を観測した結果 |0|0\rangle を得たとする. 1 qbit 目は 00 で固定されるので、 |10|10\rangle, |11|11\rangle は最早得られない. 従って 2 qbit は、 α00|00+α01|01\alpha_{00}' |00\rangle + \alpha_{01}' |01\rangle

で表される.

α00\alpha_{00}', α01\alpha_{01}' はどうなるかと言うと、これらは結局、2 qbit 目が |0|0\rangle, |1|1\rangle で観測される確率 (の閉包根) であって、 (それは観測の前後で変化しない)

元の 2 qbit が α1|0+β1|1\alpha_1 |0\rangle + \beta_1 |1\rangleα2|0+β2|1\alpha_2 |0\rangle + \beta_2 |1\rangle だったとすると、

先ほど見た結果を使うと (絶対値などという細かなことを無視すると)

α1\alpha_1 の逆数を単に定数 κ\kappa と書いて以上を改めてまとめると、

観測の結果あり得ない状態を消して (係数をゼロにして) 他の係数は定数 κ\kappa 倍する. 係数の自乗和が 11 (全確率が 11) という制約から κ\kappa の値は決定する.

量子ゲート

量子に対する実現可能な操作で次のようなゲートを作成することが理論上可能.

量子NOT

次のような XX が存在する:

この2つは即ち、 X(α|0+β|1)=β|0+α|1X (\alpha |0\rangle + \beta |1\rangle) = \beta |0\rangle + \alpha |1\rangle であると言っている.

制御 (controlled) NOT

次のような 2 qbit に対する操作 XX が存在する:

\oplus は排他的論理で、 0β=β0 \oplus \beta = \beta1β=1β1 \oplus \beta = 1 - \beta.

アダマール (Hadamard) ゲート

次のような HH が存在する:

N.B.

ちょうど一つの量子を得ることができれば、観測してみることで |0|0\rangle, |1|1\rangle を得ることができる. アダマールゲートは観測した上で二種類重ね合わせの状態の量子を得られる. そのに種類は確かに異なるものだが、両者とも 「同確率で |0|0\rangle, |1|1\rangle が観測される」ような量子である.

また HH は二回通すことで恒等写像になることがわかる.

また HH を組み合わせることで、 全ての 2n2^n 状態が等確率で観測できる nn qbit を作ることができる.

量子並列性

古典回路で計算できるビット操作 ff について、同程度の効率で計算できる次のような量子ゲート UfU_f が存在する:

Uf|x,y=|x,yf(x)U_f |x,y\rangle = |x, y \oplus f(x) \rangle

アダマールは2つの状態を全く同等に含んだ量子を作れるから、UfU_f を用いて、 実質的に f(0)f(0)f(1)f(1) を並列に計算するようなことができる. 具体的には次を実行する.

  1. H|0H |0\rangle|0|0\rangle を並べる
  2. UfU_f に通す

一度の UfU_f の計算で f(0)f(0)f(1)f(1) が行われているのが分かる. この性質を量子並列性というが、これをこのまま観測するだけでは結局、一通りの結果 |x,f(x)|x, f(x)\rangle しか得られない. 並列性のメリットを享受するには工夫が必要である. その古典的な一例であるドイチュのアルゴリズムを次に見る.

ドイチュのアルゴリズム (Deutsch algorithm)

bit操作 ff について f(0)f(1)f(0) \oplus f(1) を一度の UfU_f (ff 相当の計算) で計算するアルゴリズム.

アルゴリズムは次の 4 step から成る.

  1. |+=H|0|+\rangle = H |0\rangle
  2. |=H|1|-\rangle = H |1\rangle
  3. |ϕ1,ϕ2=Uf|+|\phi_1, \phi_2 \rangle = U_f |+-\rangle
  4. H|ϕ1,ϕ2H |\phi_1, \phi_2 \rangle の 1 qbit 目を観測

具体的に計算を追う.

  1. |+=(|0+|1)/2(|0|1)/2=(|00|01+|10|11)/2|+-\rangle = (|0\rangle+|1\rangle)/\sqrt{2} \cdot (|0\rangle - |1\rangle)/\sqrt{2} = (|00\rangle - |01\rangle + |10\rangle - |11\rangle) / 2
  2. Uf|+=(|0,f(0)|0,1f(0)+|1,f(1)|1,1f(1))/2U_f |+-\rangle = (|0,f(0)\rangle -|0,1-f(0)\rangle +|1,f(1)\rangle -|1,1-f(1)\rangle)/2
  3. H(Uf|+)=(|H(0),H(f(0))|H(0),H(1f(0))+|H(1),H(f(1))|H(1),H(1f(1)))/2H(U_f |+- \rangle) = \left( |H(0),H(f(0))\rangle -|H(0), H(1-f(0))\rangle +|H(1), H(f(1))\rangle - |H(1), H(1-f(1))\rangle \right)/2

ここで H(|0)H(|0\rangle)H(0)H(0) などと略記した. (もちろん H(0)=|+H(0) = |+\rangle, H(1)=|H(1) = |-\rangle のことである.)

最期の式を更に詳細に調べる.

初めの2項 |H(0),H(f(0))|H(0),H(1f(0))|H(0),H(f(0))\rangle -|H(0), H(1-f(0))\rangle に注目する. f(0),1f(0)f(0), 1-f(0) はちょうど一方が 0 なら他方は 1 である.

であることを使うと

|H(f(0))|H(1f(0))=(1)f(0)2|1.|H(f(0))\rangle -|H(1-f(0))\rangle = (-1)^{f(0)} \sqrt{2}~|1\rangle. すなわち、 |H(0),H(f(0))|H(0),H(1f(0))=(1)f(0)2|H(0),1.|H(0),H(f(0))\rangle -|H(0), H(1-f(0))\rangle = (-1)^{f(0)} \sqrt{2}~|H(0), 1\rangle.

と書ける. 残りの2項についても同様に書きなおせば、

H(Uf|+)=12[(1)f(0)2|H(0),1+(1)f(1)2|H(1),1]H(U_f |+- \rangle) = \frac{1}{2} \left[ (-1)^{f(0)} \sqrt{2}~|H(0), 1\rangle + (-1)^{f(1)} \sqrt{2}~|H(1), 1\rangle \right] =12[(1)f(0)|H(0),1+(1)f(1)|H(1),1]= \frac{1}{\sqrt{2}}\left[ (-1)^{f(0)} ~|H(0), 1\rangle + (-1)^{f(1)} ~|H(1), 1\rangle \right]

1 qbit 目にだけ注目すると

12[(1)f(0)|H(0)+(1)f(1)|H(1)]\frac{1}{\sqrt{2}}\left[ (-1)^{f(0)} ~|H(0)\rangle + (-1)^{f(1)} ~|H(1)\rangle \right]

f(0),f(1)f(0), f(1) によって場合分けをすると

  1. case f(0)=0,f(1)=0f(0)=0, f(1)=0
  2. case f(0)=0,f(1)=1f(0)=0, f(1)=1
  3. case f(0)=1,f(1)=0f(0)=1, f(1)=0
  4. case f(0)=1,f(1)=1f(0)=1, f(1)=1

観測して得られる qbit は、符号は無視して、それぞれ、確率 11 で、 |0|0\rangle または |1|1\rangle が得られ、それはちょうど f(0)f(1)f(0) \oplus f(1) と一致している.

ユニタリ変換

複素正方行列 UU

UU=UU=IU^\dagger U = UU^\dagger = I

とあるような行列をユニタリ行列という. ここで UU^\dagger は成分の共役 (U*)(U^*) を取って転置した行列 (U*)T(U^*)^T.

簡単な性質として2つのユニタリ行列 U,VU,V の積 UVUV もユニタリ行列.

ベクトル vv の左から UU を掛ける操作をユニタリ変換という.

Thm.

任意のユニタリ変換を再現する量子ゲートが存在する.

ところでこの定理を証明する気は無いが、其の前に qbit のベクトル表記を説明しないと意味が分からない. nn qbit に関して

|0000,|0001,|0010,,|1111|0\ldots000\rangle,~ |0\ldots001\rangle,~ |0\ldots010\rangle,~ \ldots,~ |1\ldots111\rangle

という 2n2^n 個の (基底) 状態があり得、 これらに係数

α0000,α0001,α0010,,α1111\alpha_{0\ldots000},~ \alpha_{0\ldots001},~ \alpha_{0\ldots010},~ \ldots,~ \alpha_{1\ldots111}

を乗じた線型結合が一般の状態だが、 そう書く代わりに、

[α0000α0001α0010α1111]\left[\begin{array} \alpha_{0\ldots000}\\ \alpha_{0\ldots001}\\ \alpha_{0\ldots010}\\ \ldots\\ \alpha_{1\ldots111} \end{array}\right]

という列ベクトルだと思うことにする.

そうして先ほどの定理だが、これはこの列ベクトルに左からあるユニタリ行列 UU を掛けて

[β0000β0001β0010β1111]=U[α0000α0001α0010α1111] \left[\begin{array} \beta_{0\ldots000}\\ \beta_{0\ldots001}\\ \beta_{0\ldots010}\\ \ldots\\ \beta_{1\ldots111} \end{array}\right] = U \left[\begin{array} \alpha_{0\ldots000}\\ \alpha_{0\ldots001}\\ \alpha_{0\ldots010}\\ \ldots\\ \alpha_{1\ldots111} \end{array}\right]

という時に、左辺のベクトルに対応する qbit 状態を得るような量子ゲートが必ず存在すると言っている.

このような行列 UU の大きさは 2n×2n2^n \times 2^n と、2のべき乗でないといけないが、 実際には気にする必要はない. 一般の mm (2n1<m2n2^{n-1} < m \leq 2^n) について、 ユニタリー行列 Um×mU \in \mathbb{C}^{m\times m}2nm2^n-m 個、サイズを広げて、 U=[U11]U' = \left[\begin{array} & & & & \\ & U & & & \\ & & & & \\ & & & 1 & \\ & & & & 1 \end{array}\right]

広げた部分は対角に 11 を置いてできる行列 UU' も問題なくユニタリー行列.

nn qbit であるが実際には 2n2^n 状態の内 mm 状態しか取り得ないようなもの長さ mm の列ベクトルで表現でき、m×mm \times m 行列 UU で、操作を記述すればよい. 実際には余白を 00 で埋めた長さ 2n2^n の列ベクトルを 2n×2n2^n \times 2^n 行列 UU' で操作したものだとすれば問題ない.

例. 量子NOT

量子NOTというゲート XXα|0+β|1\alpha |0\rangle + \beta |1\rangleβ|0+α|1\beta |0\rangle + \alpha |1\rangle に写す.

即ち

[βα]=UX[αβ] \left[\begin{array} \beta\\ \alpha \end{array}\right] = U_X \left[\begin{array} \alpha\\ \beta \end{array}\right]

という行列 UXU_X である. これを満たすような行列は正しく

UX=[0110]U_X = \left[\begin{array} 0 & 1\\ 1 & 0 \end{array}\right]

で、これがユニタリ行列であることは明らか.

EXACT and THRESHOLD algorithm

論文

与えられた nn bit (qbit ではない) について立ってる (11 である) ビットの数を数えるアルゴリズム. 正確に述べると、 立ってるビットの数がちょうど kk であるか判定する EXACTkn\text{EXACT}^n_k と、 kk 以上であるか判定する THRESHOLDkn\text{THRESHOLD}^n_k の2つのアルゴリズムを与える.

notation

01を並べて |00010|00010\rangle などと書く代わりに |0,|1,,|n|0\rangle,~|1\rangle,~\ldots,~|n\rangle と書く. 実際にはこれは nn qbit だとして、 ii 番目のビットだけが立ってるものを |i|i\rangle と書いたと約束する (one-hot).

i<ji<j について、 |i|j=|i,j|i \rangle \cdot |j \rangle = |i,j\rangle (左辺は nn qbit、右辺は 2n2n qbit) と書く.

さらに冗長に、 |i|i|i\rangle \cdot |i\rangle を改めて、 |i|i \rangle とする. 即ちこれは実際には 2n2n qbit である.

N.B. 実際には、中身の表現はどうでもよくて、要するに区別できる状態であればよい. つまり || \cdot \rangle の中に書く数字は単なるラベルであるので実際には文字列だと思って見る.

1 qbit |x|x\rangle (x=0,1x=0,1) に対して (1)x(-1)^xx^\hat{x} と書く (x^=1,1\hat{x}=-1,1).

Query (量子クエリ)

これから EXACT と THRESHOLD という2つのアルゴリズムを説明するが、 共に QQ という操作が登場する. これは入力 x1,x2,,xnx_1, x_2,\ldots, x_n に依存する写像であって、

で定めるものである. このように入力に依存する操作をクエリと呼ぶ.

1回のクエリの処理 (QQ の適用) のたびに、入力 xix_i を一回読む必要がある. アルゴリズムの複雑性として、クエリを処理する回数を指標とする. これを量子クエリ計算量という.

EXACT

nn bit x0,x1,,xn1x_0, x_1, \ldots, x_{n-1} の内、ちょうど kk 個が立ってるか判定するアルゴリズムを EXACTkn\text{EXACT}^n_k とする.

EXACTkn:{0,1}n{true,false}\text{EXACT}^n_k : \{0,1\}^n \to \{\text{true}, \text{false}\}

今から述べる彼らのアルゴリズムでは 2n2n qbit を用意する. 取り得る状態は |i,|i,j|i\rangle, |i,j\rangle (0i<n,0j<n,i<j)( 0\leq i < n, 0\leq j < n, i < j)n+n(n1)/2=n(n+1)/2n + n(n-1)/2 = n(n+1)/2 個だけとし、初め |0|0\rangle だとする. 従って、長さ n(n+1)/2n(n+1)/2 の虚ベクトルで状態は表現される.

まず n=2kn=2k (EXACTk2k\text{EXACT}^{2k}_k) の場合を考える.

EXACTk2k{}^{2k}_k

ちょうど半分のビットが立ってるかだけを判定する. ビットそれぞれを xx^x \mapsto \hat{x} としたときに、 その和 ix^i\sum_i \hat{x}_i がゼロになるだろう. これを利用する.

次の3つの操作を用いる:

  1. U1|0=12ki=02k1|iU_1 |0\rangle = \frac{1}{\sqrt{2k}} \sum_{i=0}^{2k-1} |i\rangle
  2. QQ
  3. U2|i=12k(i<j|i,ji>j|j,i+|0)U_2 |i\rangle = \frac{1}{\sqrt{2k}} \left( \sum_{i<j} |i,j\rangle - \sum_{i>j} |j,i\rangle + |0\rangle \right)

ここで未定義な値 (e.g. U1|1U_1|1\rangle) はどう定義してもいいので U1,U2U_1, U_2 をユニタリー行列になるようにする.

|0|0\rangle にこれらを順に通す.

U212k((x^ix^j)|i,j+i=02k1x^i|0){}_\vec{~~U_2~~} ~~ \frac{1}{2k} \left( (\hat{x}_i - \hat{x}_j) |i,j\rangle + \sum_{i=0}^{2k-1} \hat{x}_i |0\rangle \right)

で、最後の量子を観測したときに得られうる状態は

  1. |i,j|i,j\rangle
  2. |0|0\rangle

の2種類ある. この2つ目を得た時、それは係数 ix^i\sum_i \hat{x}_i がゼロでないということ. なぜなら、ゼロなら観測できる確率はゼロだから. そして、それがゼロでないということは、n=2kn=2k の内ちょうど半分のビットが立っていることを 否定 している. すなわち、

EXACTk2k(x0,x1,,xn1)=false.\text{EXACT}^{2k}_k(x_0, x_1, \ldots, x_{n-1}) = \text{false}.

次に、1つ目の |i,j|i,j\rangle を得た時、これも同様に、その係数 x^ix^j\hat{x}_i - \hat{x}_j がゼロではないことを示してる. それはつまり、ビット xix_i とビット xjx_j とが異なることを示してる. すなわち、

EXACTk2k(x0,x1,,xn1)=EXACTk12k2(x0,x1,,xn1\{xi,xj}).\text{EXACT}^{2k}_k(x_0, x_1, \ldots, x_{n-1}) = \text{EXACT}^{2k-2}_{k-1}(x_0, x_1, \ldots, x_{n-1} \setminus \{x_i, x_j\}).

以上は kk に関する帰納法を示唆する. 基底状態として

EXACT00()=true\text{EXACT}^0_0() = \text{true}

である.

EXACTkn{}^{n}_k

入力 x0,,xn1x_0, \ldots, x_{n-1} に適当に付け足せば EXACTk2k\text{EXACT}^{2k}_k に出来る. 具体的には

クエリ計算量

EXACTk2k\text{EXACT}^{2k}_k のクエリ計算量は、再帰の回数なので、最悪 kk. したがって、EXACTkn\text{EXACT}^{n}_k のクエリ計算量は、最悪

max{k,nk}\max\{k, n-k\}

となる.

THRESHOLD

nn bit x0,x1,,xn1x_0, x_1, \ldots, x_{n-1} の内、kk以上 が立ってるか判定するアルゴリズムを THRESHOLDkn\text{THRESHOLD}^n_k とする.

THRESHOLDkn:{0,1}n{true,false}\text{THRESHOLD}^n_k : \{0,1\}^n \to \{\text{true}, \text{false}\}

THRESHOLDk+12k+1{}^{2k+1}_{k+1}

まず初めに THRESHOLDk+12k+1\text{THRESHOLD}^{2k+1}_{k+1} を考える. これは即ち過半数ビットが立ってるかを判定する手続きである.

入力は x0,x1,,x2kx_0, x_1, \ldots, x_{2k}2k+12k+1 個. これに関して

とする. それぞれのサイズ (個数) について #S0=#S1\#S_0 = \#S_1 であることはない. 今 #S0>#S1\#S_0 > \#S_1 とする. 逆の場合も同様であるので省略する.

まず、次のような性質がある.

THRESHOLD では次の3つの操作を用いる:

  1. U1U_1
  2. QQ
  3. U3U_3

EXACT と同様に |0|0\rangle から初めてこれらに順に通す.

U32k12k2k+1i<j(x^ix^j)|i,j+12k2k+1i=02kijx^i|j {}_\vec{~~U_3~~} ~~ \frac{\sqrt{2k-1}}{2k \sqrt{2k+1}} \sum_{i<j} (\hat{x}_i - \hat{x}_j) |i,j\rangle + \frac{1}{2k\sqrt{2k+1}} \sum_{i=0}^{2k} \sum_{i \ne j} \hat{x}_i |j\rangle

これを測定すると

  1. |i,j|i,j\rangle または
  2. |j|j\rangle

のいずれかを得る.

  1. |i,j|i,j\rangle を得た時、

x^ix^j0\hat{x}_i - \hat{x}_j \ne 0 であるから、xixjx_i \ne x_j. 従って

THRESHOLDk+12k+1(x)=THRESHOLDk+12k+1(x\{xi,xj}\text{THRESHOLD}^{2k+1}_{k+1}(x) = \text{THRESHOLD}^{2k+1}_{k+1}(x \setminus \{x_i, x_j\}

  1. |j|j\rangle を得た時、

ijx^i0\sum_{i \ne j} \hat{x}_i \ne 0. 先ほどの性質を思い出せば、

THRESHOLDk+12k+1(x)=THRESHOLDk+12k+1(x\{xi,xj}\text{THRESHOLD}^{2k+1}_{k+1}(x) = \text{THRESHOLD}^{2k+1}_{k+1}(x \setminus \{x_i, x_j\}

以上から、ちょうど kk 回、再帰的に U1,Q,U2U_1, Q, U_2 を適用することで

THRESHOLD01(x0)=x0\text{THRESHOLD}^1_0(x_0) = x_0

というわけで THRESHOLDk+12k+1\text{THRESHOLD}^{2k+1}_{k+1} はクエリ計算量 k+1k+1 で解ける.

THRESHOLDkn{}^{n}_k

EXACT と同じ感じでやる.

クエリ計算量は、

max{k+1,nk+1}.\max \{k+1, n-k+1\}.