量子プログラミングが速い理由
このワークシートはMath by Codeの一部です。
これまで量子論理から量子回路へと進んできた。
3本ワイヤでゲートを並べることで、量子テレポーテーションまで到達できたね。
今世の中でさかんに行われているのは古典コンピュータではなく、物理的に量子を使ったコンピュータの開発と、量子プログラミングの2面でしょう。
物理的な量子コンピュータの開発は企業がお金と電力を使ってやるものだから、それはやれません。
ということで、
今回から、量子プログラミング方面を学ぼう。
１．ワイヤ２本からワイヤｎ本へ
＜ワイヤ3本へ＞
2本ワイヤの回路ではCNOTが大活躍したね。中身は条件付きNOTゲートだった。
2本のワイヤを上からa,bとすると、
CNOT[a, b]＝[a, a⊗b ]で、4次行列を2次行列で区切るとdiag(I, X)という中身だったね。
CNOTの3本ワイヤ版というのがある。それがToffoliゲート。
3本ワイヤを上からa,b,cとすると、
Toffoli[a,b,c]= [a,b, c ⊗ab] で、aとbがともに１のときだけ、cを否定する。
だから、8次行列を2次行列で区切るとdiag(I,I,I,X)という中身になる。
実際に、どんなゲートを使うとToffoliゲートが作れるのだろうか。
それはそれで、面白い問題でしょう。
しかし、冒頭に掲げたように、今回からは回路図というよりも、
プログラミングに進みたいので、探求はしない。
関数と論理と空間の視点で進もう。
＜量子並列性のパワー＞
さっきのToffoliはa,b,c→ c ⊗abという関数と見たてることができるね。
ということは、Uxy：x,y → y⊗ f(x ）というq回路で実現できるでしょう。
だから、Uxy(|x), |0)) = f(|x) )という関数としてみることができるね。
H|0)=|+)=1/√２(|0) + |1)) を入れると、
Uxy（|+), |0))＝1/√２(|0,f(0)) + |1,f(1))) が出る。
|+)⊗|+)=1/√2^2(|00)+|01)+|10)+|11))
だから、２個のHを|0)に⊗だけで２の2乗次元になる。
H⊗H⊗H…⊗H|0)とアダマール行列Hをｎ回テンソルでかけるだけで、２のｎ乗次元の基底が作れる。
この考え方を拡張すれば、ｎ本のゲートと１本のデータゲートｙを用意すれば、
２のｎ乗個の基底の重ね合わせ状態ができて、1/√2^n( Σ |x) )
これをごっそり、ｘ→f（x）してしまえる。1//√2^n(Σ |x,f(x)) )。このプロセスを関数Ufと名付ける。
ｎビットに|0)を入れH|0)=|+)にしておく、これをUｆで同時並列でf(x)を求めるという夢のような計算が
量子回路でできるということだ。
しかし、残念。取り出せるの測定で1個の基底だから、結果は1個しかわかりません。
さてどうする？
＜量子干渉性を使おう＞
たとえば、0か１を返す関数f(x)の値を比べたいとする。
古典論理では、f(0)とf(1)が同じ値になるか、別の値になるかは2回測らないとわからない。
これを1回で知りたい。
どうしたらよいだろうか。
量子情報の波としての向きを調節することで、状態が干渉しあい、結果が変わる。
基底の入れ方とHの使い方を上のようにしてみよう。
上の図で全体のようすをつかむためにテンソル積を使う。
f(0),f(1)の値の組を00,01,10,11の4通りにして求めた値で、数式の結果を{a,b,c,d}とかく。
順にf(0)⊕f(1)=0,1,1,0となる。
演算⊕が和のmod2だったから、
f(0)⊕f(1)=1はf(0)≠f(1)であり、f(0)⊕f(1)=0がf(0)＝f(1)ということになるね。
では、テンソル積で全体化して、さらに4通りを並列して調べてみよう。
力技スタート！
|ψ0)＝|0)⊗|1)
|ψ1)＝1/2| (|0)+|1)]⊗[(|0)-|1)]=1/2[|00)-|01)+|10)-|11) ]
|ψ2)＝1/2[ |0,0⊕f(0))-|0,1⊕f(0))+|1,0⊕f(1))-|1,1⊕f(1)) ]
={1/2[ |0,0⊕0))-|0,1⊕0)+|1,0⊕0)-|1,1⊕0) ],
1/2[ |0,0⊕0))-|0,1⊕0)+|1,0⊕1)-|1,1⊕1) ],
1/2[ |0,0⊕1)-|0,1⊕1)+|1,0⊕0)-|1,1⊕0) ],
1/2[ |0,0⊕1)-|0,1⊕1)+|1,0⊕1)-|1,1⊕1) ] }
={1/2[ |0,0)-|0,1)+|1,0)-|1,1) ],1/2[ |0,0))-|0,1)+|1,1)-|1,0) ],
1/2[ |0,1)-|0,0)+|1,0)-|1,1) ], 1/2[ |0,1)-|0,0)+|1,1)-|1,0) ] }
={1/2[ |0)(|0)-|1))+|1)(|0)-|1)) ],1/2[ |0)(|0)-|1))+|1)(|1)-|0)) ],
1/2[ |0)(|1)-|0))+|1)(|0)-|1)) ], 1/2[ |0)(|1)-|0))+|1)(|1)-|0)) ] }
|ψ3)
={1/2√2[ (|0)+|1))(|0)-|1))+(|0)-|1))(|0)-|1)) ],
1/2√2[ (|0)+|1))(|0)-|1))+(|0)-|1))(|1)-|0)) ], 1/2√2[ (|0)+|1))(|1)-|0))+(|0)-|1))(|0)-|1)) ],
1/2√2[ (|0)+|1))(|1)-|0))+(|0)-|1))(|1)-|0)) ] }
={1/2√2[ 2|0)(|0)-|1)) ],
1/2√2[ 2|1))(|0)-|1)) ],
1/2√2[ 2|1))(|1)-|0)) ],
1/2√2[ 2|0)(|1)-|0)) ] }
=1/√2{ |0)(|0)-|1)) , |1)(|0)-|1)) , |1)(|1)-|0)) , |0)(|1)-|0)) }
この結果とf(0)⊕f(1)=0,1,1,0を比べれば、第１ビットがf(0)⊕f(1)の値と同じであることがわかるね。
＜振り返り＞
ψ0、ψ1、ψ2までは、単純な代入計算であり、どんどん項数が増え順調にすすむ。
ψ1、ψ2は次元は4次元だから、基底が４つあり、確率振幅が1/2で2乗して1/4でピッタリ。
ところが、ψ3で一瞬気持ち悪くなる！
Hを第１ビットにかけたあと、確率振幅が1/2の１/√2倍の1/2√2となり、このままでは、確率が1/8になってしまう。基底が8つに増えたわけではないから、見かけ上危険な数式状態になった。
しかし、太線の部分で奇跡的な現象がおきる。
f(0),f(1)=0,0の場合
1/2√2[ (|0)+|1))(|0)-|1))+(|0)-|1))(|0)-|1)) ]＝1/2√2[ 2|0)(|0)-|1))
こうなる。なぜか。
第１ビットが０に対して、第２ビットが同符号の(|0)-|1))があるから2倍になる波。
第２ビットが１に対して、第２ビットが符号反転の(|0)-|1))、-(|0)-|1))で消滅する波。
さらに、このことで、基底が2個になるので、確率は1/2になるはず。
実際、確率振幅は1/√2だから、これも整合している。
これがｆ(0),f(1)の値の組み合わせがどうなっても同じ現象が起きる。
これが、波の増幅と波の相殺という、正に量子状態の干渉性のたまものですね。
しかも、1個の測定で2個分美味しいという高効率のアルゴリズムが実現したのです。
２．ドイチュ-ジョザのアルゴリズム
ドイチュの問題
「ブール値関数ｆ：x= {0, l}^n →｛0,1 ｝は「定」か「半」いずれかである。
fは2値のｎビットに対して1ビットを答える関数でその具体的な作動はブラックボックスだが、
関数であるからには同じ入力には同じ出力をする。このように謎の関数をオラクルともいう。
そして、「定」はいつも０か１の片方だけを返す。「半」とは定義域の集合の半分で0,残り半分で１になる。オラクルfが定か半かを求める手順はどうしますか。」
があります。
ドイチュ問題はさっきの1ビットから1ビットを答える関数問題の拡張版ですね。
上下のワイヤに入力ビット、出力ビットと名前をつけよう。
このネーミングにはあまりこだわらないでください。入力ビットは関数ｆのビット用くらいの意味です。
n=1のときを拡張しやすいように再表現してみよう。
|ψ0)＝|01)
|ψ1)＝|+)⊗|-)= 1/√2(Σ|x)⊗ |-) …… Σの中の｜x）は入力ワイヤの|+)の各基底|1),|0)のことです。
オラクルにより、xに対して|-)⊕f(x)は、f(x)=0なら|-) , f(x)=1なら-|-)を返すね。
だから、Ufは|x)|-)をf(x)=0なら(-1)^0倍 , f(x)=1なら(-1)^1倍して返しているもいえる。
すると、
|ψ2)=1/√2(Σ |x)(-1)^f(x) ⊗ |-)
=1/√2(Σ |x)⊗(-1)^f(x) |-)
|ψ3)=H [ 1/√2(Σ |x)⊗(-1)^f(x) |-) ]
= 1/√2 Σ [ (H |x)⊗(-1)^f(x) |-) ]
= 1/2 Σ [Σ(-1)^xz |z)⊗(-1)^f(x) |-) ] ......H|x)=1/√2[(-1)^0x|0)+(-1)^1x|1)]=1/√2[Σ(-1)^xz |z)]と言い換えた。
= 1/2 Σ [ {Σ(-1)^(xz +f(x)) |z) }⊗ |-) ]
= Σ [1/2 {Σ(-1)^(xz +f(x)) ] |z)⊗|-)
=........=
=>{ |0), -|0), -|1), |1)}⊗|-)
fが定で、値が0なら(-1)^0を|1),|0)にかけるので、|+)。
fが定で、値が1なら(-1)^1を|1),|0)にかけるので、-|+)。
fが半で、Iなら|0)はそのまま|1)はマイナスで|-)になる。
fが半で、Notなら上の逆だから、-|-)。
H|0)＝|+)と枝分かれした|+)に再度HをかけるとH|1)とH|0)と干渉によって、H|+)=|0)とまとまる。
同じように、H|-)=1/√2(H|0)-H|1))=|1)にまとまる。ノイズキャンセリングだ。
入力ワイヤが０になるのはψ2で±|＋)のときだから、ｆが定のとき。
入力ワイヤが１になるのはψ2で±|-)のときだから、ｆが半のとき。
入力ワイヤが０なら定、そうでないなら半だ。
このように数式化しておくと、ビット数が増えても同様にできるでしょう。
入力ワイヤをｎビットにして、どのビットも0にセットし、出力ワイヤだけさっきと同じ１にしよう。
|ψ0)＝|000......01)
|ψ1)＝|+)⊗|+)⊗|+)........⊗|-)= 1/√(2^n)(Σ|x)⊗ |-)
…… Σの中の｜x）は入力ワイヤのnビットの基底の積のどれかです。
|ψ2)=1/√(2^n)(Σ|x)(-1)^f(x) ⊗|-)
=1/√(2^n)(Σ|x)⊗(-1)^f(x) |-)
|ψ3)=H^⊗n [ 1/√(2^n)(Σ |x)⊗(-1)^f(x) |-) ]
= 1/√(2^n) Σ [ (H^⊗n |x)⊗(-1)^f(x) |-) ]
= 1/(2^n) Σ [Σ(-1)^xz |z)⊗(-1)^f(x) |-) ] ......|z)はｎビットの基底の積のどれか
= 1/(2^n) Σ [Σ(-1)^(xz +f(x)) |z)⊗ |-) ]
=..........=
=>{ |000...0), -|000...0),… -|111...1), |1111...1)}⊗|-)
もしｆが定ならば、f(x)の値は一定となり、波の位相が一定の＋１かー１となる。それだけでψ３の振幅をカバーしてしまうから、他の振幅は０になりz＝オールゼロ。
もしｆが半ならば、位相の正と負が相殺してz＝オールゼロの確率は０になる。それでも全体確率１をカバーするためには0以外のビットが１つはある基底ｚが生き残る必要がある。
だから、
入力ワイヤがすべて０なら定、それ以外なら半だ。
ｎビットすべて調べるだけで、定か半が判定できるということだ。
古典コンピュータでは2^n/2+1回の調査が必要なのと段違いだね！
この量子アルゴリズムは「ドイチュ-ジョザ」のアルゴリズムと呼ばれている。
＜振り返り＞
ポイントは、Uf |x.-) → |x)⊗(-1)^f(x) |-) → (-1)^f(x) |x，-)
出力ビットのf(x) が０か１かによる符号情報を、
位相情報としての符号（＋か－か）として、入力ビットの先頭へと移動させることができたことだ。
これは、位相キックバック、位相逆流と言われているね。
Ufがするはずの出力ビットへの反転を、入力ビットの基底|x)の符号に逆流させることができたんだね。
この見事なテクニックによって、量子コンピュータは「答えそのもの」を探すのではなく、
「答えが引き起こした波の干渉パターン」を読み取ることで問題解決ができるようになったんだね。
３．グローパーの探索アルゴリズム
量子プログラミングの３つの武器、並列性・干渉性・位相逆流を使って、
さらに進もう。
それは探索問題だ。
＜探索問題＞
「整数 0～N-1で索引のついた N=2^n 件のデータベースがあり、探したいものが１個だけあります。正解を知らないが、正解かどうかの判定はできるブラックボックス（オラクル）f(x)が使えるものとします。このデータベースを探索したい。」
正解はwで、f(x)= if (x=w, 1,0)とします。
オラクルUは |x,y)→|x, y⊗f(x))です。
索引ワイアn本に|0)をセット、
x={0,1,2,......, N-1} , y={0,1}
初期状態は |000......0)
索引ワイアｎ本すべてHをかけて、N個の基底|0)から|N-1)が等確率になる振幅1/√Nで重ね合わせ状態
|ψ)=1/√NΣ|x) にします。
ここで、ドイチュ問題のように、出力ワイヤ|-)を1本用意して、オラクルを1回やると正解の基底|w)のときだけ、(-1)^f(x)で|-)に作用させると、|0)と|1)が入れ替わるので、|-)でまとめなおすと、符号を反転させることができて、正解のビットだけ符号をつけられます。位相逆流でしたね。
しかし、残念でした。
符号が反対なだけで、不正解のビットとは確率振幅が平等なので、観測してもN分の１の確率で
正解するだけです。探索は成功してませんね。
そこで、オラクルはすぐはやりません。|ψ)=1/√NΣ|x)からスタートします。
出力ワイヤ１本の代わりに、作業ワイアｎ本にも|0)をセットします。
ここからがグローバー回転という手順でGという名前でひとくくりにしよう。
１．検索ワイヤと作業ワイヤでオラクルU|x,y)→|x, y⊗f(x))をします。
２．検索ワイヤにH^⊗nをします。
３．|0)以外の基底|x)の符号を逆にします。|0)→|0), |x)→-|x)。
やり方は、検索ワイヤで条件付き位相逆流をします。|x)→-(-1)^δx0|x)
これをオペレータでかくと、2|0)(0|-I なる。
４．検索ワイヤにH^⊗nをします。
これをオペレータでかくと、H^⊗n（2|0)(0|-I）H^⊗n＝２|ψ)(ψ|- I
だから、G=(２|ψ)(ψ|- I)U
この回転を繰り返すと|ψ)は|w)に近づく確率があがっていくのです。
どういうことでしょうか。
＜グローバー回転はベクトルの回転＞
|ψ)を2種類のベクトルの和で表します。
|a）が正解基底|w）以外の総和の状態ベクトルで確率振幅はどれも1/√(N-1)
|b)が正解基底|w)とする、確率振幅は１。|b)=|w)
|ψ)＝√(N-1)/N|a)+√(1/N)|b)で、複雑にみえるが、確率振幅は正規化のためにつけている。
グローバー回転のオラクルUをすると、U(p|a)+q|b))=p|a)-q|b)
係数はベクトル|a)はそのまま|b)方向に反転。だから、Uはベクトル|ψ)を|a)軸で鏡面反射している。
グローバー回転の２|ψ)(ψ|- Iは、逆にベクトル|ψ)でU|ψ)を鏡面反射している。
こうすることで、|a)と|b)の間にあった|ψ)が正解の|b)に近づくのです。
どのくらい近づくかというと、|a)と|ψ)の角をθ/2とすると、
|a)とG|ψ)の角は１回で3/2θに広がる。
逆に１回で角θだけ正解|b)に近づくということだね。
G^k|ψ)=cos(k+1/2)θ |a) + sin(1/2+k)θ |b)
このステップをさらにコンパクトにまとめるとこうなります。
|ψ)＝|+)⊗|+)⊗|+)........⊗X|+)= 1/√(2^n)(Σ|x)⊗ X|+)
…… Σの中の｜x）は入力ワイヤのnビットの基底の積のどれかです。
G^R|ψ)=（2|ψ)(ψ| - I )H^R 1/√(2^n) Σ |x)|-)≒|w)|-)
指数のRは繰り返し回数です。 R＝[π/4√(2^n)]回
検索ワイアを測定するとｘ＝ｗになる。
課題：グローバー回転の効率のよさを実感する視覚化はどうやればよいでしょうか。
#基本の設定
n=slider(1,10,1)
N=2^n
R＝ceil(pi/4 sqrt(N)) //切り上げ
k=slider(1, 2 R,1) //少しだけ多めにする
O=(0,0)
A=(1,0)
B=(0,1)
a=Vector(O,A)
b=Vector(O,B)
thp2=asin(1/sqrt(N)) //sin(θ/2) = 1/√N
th = 2 * thp2
c=cos(thp2)
s=sin(thp2)
angle_k = (k + 0.5) * th
c_k = cos(angle_k)
s_k = sin(angle_k)
＃回転前と回転後の描画
ps = c a+ s b
ps_k = c_k * A + s_k * B //
Vector(O, ps_k) // 現在の状態ベクトルを描画
text="データ件数N=" + N+ "\\回転数R=" + R