このワークシートは[url=https://www.geogebra.org/m/twxxx3yq]Math by Code[/url]の一部です。[br][br]これまで量子論理から量子回路へと進んできた。[br]3本ワイヤでゲートを並べることで、量子テレポーテーションまで到達できたね。[br][br]今世の中でさかんに行われているのは古典コンピュータではなく、物理的に量子を使ったコンピュータの開発と、量子プログラミングの2面でしょう。[br]物理的な量子コンピュータの開発は企業がお金と電力を使ってやるものだから、それはやれません。[br][br]ということで、[br]今回から、量子プログラミング方面を学ぼう。

[b][size=150]＜ワイヤ3本へ＞[/size][/b][br]2本ワイヤの回路ではCNOTが大活躍したね。中身は条件付きNOTゲートだった。[br]2本のワイヤを上からa,bとすると、[br]CNOT[a, b]＝[a, a⊗b ]で、4次行列を2次行列で区切るとdiag(I, X)という中身だったね。[br]CNOTの3本ワイヤ版というのがある。それがToffoliゲート。[br]3本ワイヤを上からa,b,cとすると、[br]Toffoli[a,b,c]= [a,b, c ⊗ab] で、aとbがともに１のときだけ、cを否定する。[br]だから、8次行列を2次行列で区切るとdiag(I,I,I,X)という中身になる。[br][br]実際に、どんなゲートを使うとToffoliゲートが作れるのだろうか。[br]それはそれで、面白い問題でしょう。[br]しかし、冒頭に掲げたように、今回からは回路図というよりも、[br]プログラミングに進みたいので、探求はしない。[br][br][b]関数と論理と空間[/b]の視点で進もう。[br][br][b][size=150]＜量子並列性のパワー＞[br][/size][/b][br]さっきのToffoliはa,b,c→ c ⊗abという関数と見たてることができるね。[br]ということは、Uxy：x,y → y⊗ f(x ）というq回路で実現できるでしょう。[br]だから、Uxy(|x), |0)) = f(|x) )という関数としてみることができるね。[br][br][b]H|0)=|+)=1/√２(|0) + |1))[/b] を入れると、[br]Uxy（|+), |0))＝1/√２([b]|0,f(0)) + |1,f(1))[/b]) が出る。[br][b]|+)⊗|+)=1/√2^2(|00)+|01)+|10)+|11))[/b][br]だから、２個のHを|0)に⊗だけで２の2乗次元になる。[br]H⊗H⊗H…⊗H|0)とアダマール行列Hをｎ回テンソルでかけるだけで、２のｎ乗次元の基底が作れる。[br]この考え方を拡張すれば、ｎ本のゲートと１本のデータゲートｙを用意すれば、[br]２のｎ乗個の基底の重ね合わせ状態ができて、1/√2^n( Σ [b]|x)[/b] )　[br]これをごっそり、ｘ→f（x）してしまえる。1//√2^n(Σ [b]|x,f(x))[/b] )。このプロセスを関数Ufと名付ける。[br]ｎビットに|0)を入れ[b]H|0)=|+)にしておく、これを[/b]Uｆで[b][color=#0000ff]同時並列でf(x)を求めるという夢のような計算[/color][/b]が[br]量子回路でできるということだ。[br][br]しかし、残念。[b]取り出せるの測定で1個の基底だから、[color=#0000ff]結果は1個しかわかりません[/color][/b]。[br]さてどうする？

[b][size=150]＜量子干渉性を使おう＞[/size][/b][br]たとえば、0か１を返す関数f(x)の値を比べたいとする。[br]古典論理では、f(0)とf(1)が同じ値になるか、別の値になるかは2回測らないとわからない。[br]これを1回で知りたい。[br]どうしたらよいだろうか。[br][br]量子情報の波としての向きを調節することで、状態が干渉しあい、結果が変わる。[br]基底の入れ方とHの使い方を上のようにしてみよう。[br][br]上の図で全体のようすをつかむためにテンソル積を使う。[br]f(0),f(1)の値の組を00,01,10,11の4通りにして求めた値で、数式の結果を{a,b,c,d}とかく。[br]順にf(0)⊕f(1)=0,1,1,0となる。[br]演算⊕が和のmod2だったから、[br]f(0)⊕f(1)=1はf(0)≠f(1)であり、f(0)⊕f(1)=0がf(0)＝f(1)ということになるね。[br][br]では、テンソル積で全体化して、さらに4通りを並列して調べてみよう。[br]力技スタート！[br][br][b]|ψ0)[/b]＝|0)⊗|1)[br][b]|ψ1)[/b]＝1/2| (|0)+|1)]⊗[(|0)-|1)]=1/2[|00)-|01)+|10)-|11) ][br][b]|ψ2)[/b]＝1/2[ |0,0⊕f(0))-|0,1⊕f(0))+|1,0⊕f(1))-|1,1⊕f(1)) ][br]={1/2[ |0,0⊕0))-|0,1⊕0)+|1,0⊕0)-|1,1⊕0) ],[br] 1/2[ |0,0⊕0))-|0,1⊕0)+|1,0⊕1)-|1,1⊕1) ],[br] 1/2[ |0,0⊕1)-|0,1⊕1)+|1,0⊕0)-|1,1⊕0) ], [br] 1/2[ |0,0⊕1)-|0,1⊕1)+|1,0⊕1)-|1,1⊕1) ] }[br]={1/2[ |0,0)-|0,1)+|1,0)-|1,1) ],1/2[ |0,0))-|0,1)+|1,1)-|1,0) ],[br] 1/2[ |0,1)-|0,0)+|1,0)-|1,1) ], 1/2[ |0,1)-|0,0)+|1,1)-|1,0) ] }[br]={1/2[ |0)(|0)-|1))+|1)(|0)-|1)) ],1/2[ |0)(|0)-|1))+|1)(|1)-|0)) ],[br] 1/2[ |0)(|1)-|0))+|1)(|0)-|1)) ], 1/2[ |0)(|1)-|0))+|1)(|1)-|0)) ] }[br][b]|ψ3)[/b][br][b]=[/b][b]{1/2√2[ (|0)+|1))(|0)-|1))+(|0)-|1))(|0)-|1)) ],[br] 1/2√2[ (|0)+|1))(|0)-|1))+(|0)-|1))(|1)-|0)) ],[/b][b] 1/2√2[ (|0)+|1))(|1)-|0))+(|0)-|1))(|0)-|1)) ],[br] 1/2√2[ (|0)+|1))(|1)-|0))+(|0)-|1))(|1)-|0)) ] }[br][/b][b]={1/2√2[ 2|0)(|0)-|1)) ],[br]　1/2√2[ 2|1))(|0)-|1)) ],[br]　1/2√2[ 2|1))(|1)-|0)) ],[br]　1/2√2[ 2|0)(|1)-|0)) ] }[br] =1/√2{ |0)(|0)-|1)) , |1)(|0)-|1)) , |1)(|1)-|0)) , |0)(|1)-|0)) }[br][/b]この結果とf(0)⊕f(1)=0,1,1,0を比べれば、第１ビットがf(0)⊕f(1)の値と同じであることがわかるね。[br][br][b]＜振り返り＞[/b][br]ψ0、ψ1、ψ2までは、単純な代入計算であり、どんどん項数が増え順調にすすむ。[br]ψ1、ψ2は次元は4次元だから、基底が４つあり、確率振幅が1/2で2乗して1/4でピッタリ。[br][br]ところが、ψ3で一瞬気持ち悪くなる！[br]Hを第１ビットにかけたあと、確率振幅が1/2の１/√2倍の1/2√2となり、このままでは、確率が1/8になってしまう。基底が8つに増えたわけではないから、見かけ上危険な数式状態になった。[br][br]しかし、太線の部分で奇跡的な現象がおきる。[br]f(0),f(1)=0,0の場合[br][b]1/2√2[ (|0)+|1))(|0)-|1))+(|0)-|1))(|0)-|1)) ]＝[b]1/2√2[ 2|0)(|0)-|1)) [/b][br][/b]こうなる。なぜか。[br]第１ビットが０に対して、第２ビットが同符号の[b](|0)-|1))があるから2倍になる波。[/b][br]第２ビットが１に対して、第２ビットが符号反転の[b](|0)-|1))、-[b](|0)-|1))で消滅する波。[br][/b][/b]さらに、このことで、基底が2個になるので、確率は1/2になるはず。[br]実際、確率振幅は1/√2だから、これも整合している。[br]これがｆ(0),f(1)の値の組み合わせがどうなっても同じ現象が起きる。[br][br]これが、[b]波の増幅と波の相殺という、正に量子状態の干渉性のたまもの[/b]ですね。[br]しかも、1個の測定で2個分美味しいという[b]高効率のアルゴリズム[/b]が実現したのです。[br]

[b]ドイチュの問題[br][br]「ブール値関数ｆ：x= {0, l}^n →｛0,1 ｝は「定」か「半」いずれかである。[br][/b]fは2値の[b]ｎビットに対して1ビットを答える関数[/b]でその具体的な作動はブラックボックスだが、[br]関数であるからには同じ入力には同じ出力をする。このように謎の関数をオラクルともいう。[br]そして、「定」はいつも０か１の片方だけを返す。「半」とは定義域の集合の半分で0,残り半分で１になる。[b]オラクルfが定か半か[/b]を求める手順はどうしますか。」[br]があります。[br][br]ドイチュ問題はさっきの1ビットから1ビットを答える関数問題の拡張版ですね。[br][br]上下のワイヤに入力ビット、出力ビットと名前をつけよう。[br]このネーミングにはあまりこだわらないでください。入力ビットは関数ｆのビット用くらいの意味です。[br][br][b][color=#0000ff]n=1のときを拡張しやすいように再表現してみよう。[br][/color][/b][br]|ψ0)＝|01)[br]|ψ1)＝|+)⊗|-)=[b] 1/√2(Σ|x)⊗ |-)　[/b]……　Σの中の｜x）は入力ワイヤの|+)の各基底|1),|0)のことです。[br]オラクルにより、xに対して|-)⊕f(x)は、f(x)=0なら|-) , f(x)=1なら-|-)を返すね。[br]だから、Ufは|x)|-)をf(x)=0なら(-1)^0倍 , f(x)=1なら(-1)^1倍して返しているもいえる。[br]すると、[br]|ψ2)=[b]1/√2(Σ |x)(-1)^f(x) ⊗ |-)[br] =1/√2(Σ |x)⊗(-1)^f(x) |-)[br][/b]|ψ3)=H [ 1/√2(Σ |x)⊗(-1)^f(x) |-) ][br]= 1/√2 Σ [ (H |x)⊗(-1)^f(x) |-) ][br]= 1/2 Σ [Σ(-1)^xz |z)⊗(-1)^f(x) |-) ] ......H|x)=1/√2[(-1)^0x|0)+(-1)^1x|1)]=1/√2[Σ(-1)^xz |z)]と言い換えた。[br]= 1/2 Σ [ {Σ(-1)^(xz +f(x)) |z) }⊗ |-) ][br]= Σ [1/2 {Σ(-1)^(xz +f(x)) ] [b]|z)⊗|-)[/b] [br][b]=........=[br]=>{ |0), -|0), -|1), |1)}⊗|-)[br][/b][br]fが定で、値が0なら(-1)^0を|1),|0)にかけるので、[b]|+)[/b]。[br]fが定で、値が1なら(-1)^1を|1),|0)にかけるので、[b]-|+)[/b]。[br]fが半で、Iなら|0)はそのまま|1)はマイナスで[b]|-)[/b]になる。[br]fが半で、Notなら上の逆だから、[b]-|-)[/b]。[br]H|0)＝|+)と枝分かれした[b]|+)に再度Hをかけると[/b]H|1)とH|0)と干渉によって、[b]H|+)=|0)[/b]とまとまる。[br]同じように、[b]H|-)=1/√2(H|0)-H|1))=|1)[/b]にまとまる。[b]ノイズキャンセリング[/b]だ。[br]入力ワイヤが０になるのはψ2で±|＋)のときだから、ｆが定のとき。[br]入力ワイヤが１になるのはψ2で±|-)のときだから、ｆが半のとき。[br][b]入力ワイヤが０なら定、そうでないなら半だ。[br][/b][br][b]このように数式化しておくと、ビット数が増えても同様にできるでしょう。[br][/b]入力ワイヤをｎビットにして、どのビットも0にセットし、出力ワイヤだけさっきと同じ１にしよう。[br]|ψ0)＝|000......01)[br]|ψ1)＝|+)⊗|+)⊗|+)........⊗|-)=[b] 1/√(2^n)(Σ|x)⊗ |-)[br][/b]……　Σの中の｜x）は[b]入力ワイヤのnビットの基底の積[/b]のどれかです。[br]|ψ2)=1/√(2^n)(Σ|x)(-1)^f(x) ⊗|-)[br] =1/√(2^n)(Σ|x)⊗(-1)^f(x) |-)[br]|ψ3)=H^⊗n [ 1/√(2^n)(Σ |x)⊗(-1)^f(x) |-) ][br]= 1/√(2^n) Σ [ (H^⊗n |x)⊗(-1)^f(x) |-) ][br]= 1/(2^n) Σ [Σ(-1)^xz |z)⊗(-1)^f(x) |-) ] ......|z)はｎビットの基底の積のどれか[br]= 1/(2^n) Σ [Σ(-1)^(xz +f(x)) [b]|z)⊗ |-)[/b] ][br]=..........=[br][b]=>{ |000...0), -|000...0),… -|111...1), |1111...1)}⊗|-)[br][/b][b][br]もしｆが定ならば、f(x)の値は一定となり、波の位相が一定の＋１かー１となる。それだけでψ３の振幅をカバーしてしまうから、他の振幅は０になりz＝オールゼロ。[br]もしｆが半ならば、位相の正と負が相殺して[b]z＝オールゼロの確率は０になる。[/b]それでも全体確率１をカバーするためには0以外のビットが１つはある基底ｚが生き残る必要がある。[br]だから、[br]入力ワイヤがすべて０なら定、それ以外なら半だ。[br][br][/b]ｎビットすべて調べるだけで、定か半が判定できるということだ。[br]古典コンピュータでは2^n/2+1回の調査が必要なのと段違いだね！[br][br]この量子アルゴリズムは「ドイチュ-ジョザ」のアルゴリズムと呼ばれている。[br][br][b][size=150]＜振り返り＞[br][/size][/b][br]ポイントは、Uf |x.-)　→　|x)⊗[b](-1)^f(x)[/b] |-)　→　[b](-1)^f(x)[/b] |x，-)[br][br]出力ビットのf(x) が０か１かによる符号情報を、[br]位相情報としての符号（＋か－か）として、入力ビットの先頭へと移動させることができたことだ。[br]これは、[b]位相キックバック、位相逆流[/b]と言われているね。[br][br]Ufがするはずの[b]出力ビット[/b]への反転を、[b]入力ビット[/b]の基底|x)の符号に[b][color=#0000ff]逆流させる[/color][/b]ことができたんだね。[br]この見事なテクニックによって、量子コンピュータは「答えそのもの」を探すのではなく、[br]「答えが引き起こした波の干渉パターン」を読み取ることで問題解決ができるようになったんだね。

量子プログラミングの３つの武器、並列性・干渉性・位相逆流を使って、[br]さらに進もう。[br][br]それは探索問題だ。[br][br][b][size=150]＜探索問題＞[br][/size][/b] 「整数 0～N-1で索引のついた N=2^n 件のデータベースがあり、探したいものが１個だけあります。正解を知らないが、正解かどうかの判定はできるブラックボックス（オラクル）f(x)が使えるものとします。このデータベースを探索したい。」[br][br]正解はwで、f(x)= if (x=w, 1,0)とします。[br]オラクルUは　|x,y)→|x, y⊗f(x))です。[br]索引ワイアn本に|0)をセット、[br]x={0,1,2,......, N-1} , y={0,1}[br]初期状態は |000......0)[br][br]索引ワイアｎ本すべてHをかけて、N個の基底|0)から|N-1)が等確率になる振幅1/√Nで重ね合わせ状態[br][b]|ψ)=1/√NΣ|x) [/b]にします。[br][br]ここで、ドイチュ問題のように、出力ワイヤ|-)を1本用意して、オラクルを1回やると正解の基底|w)のときだけ、(-1)^f(x)で|-)に作用させると、|0)と|1)が入れ替わるので、|-)でまとめなおすと、符号を反転させることができて、正解のビットだけ符号をつけられます。位相逆流でしたね。[br]しかし、[b]残念でした[/b]。[br]符号が反対なだけで、不正解のビットとは確率振幅が平等なので、観測してもN分の１の確率で[br]正解するだけです。[b]探索は成功してませんね[/b]。[br][br]そこで、オラクルはすぐはやりません。[b]|ψ)=1/√NΣ|x)[/b]からスタートします。[br]出力ワイヤ１本の代わりに、[b]作業ワイアｎ本にも|0)をセットします[/b]。[br][br]ここからが[b][color=#0000ff]グローバー回転[/color][/b]という手順でGという名前でひとくくりにしよう。[br]１．検索ワイヤと作業ワイヤでオラクルU|x,y)→|x, y⊗f(x))をします。[br]２．検索ワイヤにH^⊗nをします。[br]３．|0)以外の基底|x)の符号を逆にします。|0)→|0), |x)→-|x)。[br]　やり方は、検索ワイヤで条件付き位相逆流をします。|x)→[b]-(-1)^δx0[/b]|x)[br]　これをオペレータでかくと、[b]2|0)(0|-I　[/b]なる。[br]４．検索ワイヤにH^⊗nをします。[br][br]これをオペレータでかくと、H^⊗n（2|0)(0|-I）H^⊗n＝２|ψ)(ψ|- I [br]だから、[b][color=#0000ff]G=(２|ψ)(ψ|- I)U[/color][/b][br]この回転を繰り返すと|ψ)は|w)に近づく確率があがっていくのです。[br]どういうことでしょうか。[br][b][size=150][br]＜グローバー回転はベクトルの回転＞[/size][/b][br]|ψ)を2種類のベクトルの和で表します。[br]|a）が正解基底|w）以外の総和の状態ベクトルで確率振幅はどれも1/√(N-1)[br][b]|b)が正解基底|w)[/b]とする、確率振幅は１。|b)=|w)[br][b]|ψ)＝√(N-1)/N|a)+√(1/N)|b)[/b]で、複雑にみえるが、確率振幅は正規化のためにつけている。[br][br]グローバー回転のオラクルUをすると、[b]U(p|a)+q|b))=p|a)-q|b)[/b][br]係数はベクトル|a)はそのまま|b)方向に反転。だから、Uはベクトル|ψ)を|a)軸で鏡面反射している。[br]グローバー回転の２|ψ)(ψ|- Iは、逆にベクトル|ψ)でU|ψ)を鏡面反射している。[br]こうすることで、|a)と|b)の間にあった|ψ)が正解の|b)に近づくのです。[br][br]どのくらい近づくかというと、|a)と|ψ)の角をθ/2とすると、[br]|a)とG|ψ)の角は１回で3/2θに広がる。[br]逆に１回で[b]角θだけ正解|b)に近づく[/b]ということだね。[br][b]G^k|ψ)=cos(k+1/2)θ |a) + sin(1/2+k)θ |b)[br][/b][br]このステップをさらにコンパクトにまとめるとこうなります。[br]|ψ)＝|+)⊗|+)⊗|+)........⊗X|+)=[b] 1/√(2^n)(Σ|x)⊗ X|+)[br][/b]……　Σの中の｜x）は[b]入力ワイヤのnビットの基底の積[/b]のどれかです。[br][b]G^R[/b]|ψ)=（2|ψ)(ψ| - I )H[b]^R [/b] 1/√(2^n) Σ |x)|-)[b]≒|w)|-)[/b][br]　　指数のRは繰り返し回数です。 R＝[π/4√(2^n)]回[br]検索ワイアを測定するとｘ＝ｗになる。[br]

[color=#9900ff][b][u]課題：グローバー回転の効率のよさを実感する視覚化はどうやればよいでしょうか。[br][/u][/b][/color][br]#基本の設定[br]n=slider(1,10,1)[br]N=2^n[br]R＝ceil(pi/4 sqrt(N)) //切り上げ[br]k=slider(1, 2 R,1) //少しだけ多めにする[br]O=(0,0)[br]A=(1,0)[br]B=(0,1)[br]a=Vector(O,A)[br]b=Vector(O,B)[br]thp2=asin(1/sqrt(N))　　//sin(θ/2) = 1/√N[br]th = 2 * thp2 [br]c=cos(thp2)[br]s=sin(thp2)[br]angle_k = (k + 0.5) * th[br]c_k = cos(angle_k)[br]s_k = sin(angle_k)[br][br]＃回転前と回転後の描画[br]ps = c a+ s b [br]ps_k = c_k * A + s_k * B // [br]Vector(O, ps_k) // 現在の状態ベクトルを描画[br]text="データ件数N=" + N+ "\\回転数R=" + R