グローバーのアルゴリズムがいまいちわからない
量子ビットや量子ゲートはブロッホ球で視覚的になんとなくわかるけれども、グローバーのアルゴリズムあたりになると数式中心の説明で脳が理解を拒否する、ということはありませんか？
2量子ビット以上でもつれ状態にあるものはブロッホ球で表現ができなくなる1というのも直感的な理解の妨げになっている気がします。
量子回路上でどんな値がどう変化しているのかを追っていけばアルゴリズムの理解の助けになるかも、ということでこの記事ではグローバーのアルゴリズムの各ステップの量子ビットの状態ベクトル2を追ってみようと思います。
この記事は、Qiskitで提供されている学習テキストを参考にしています。
Qiskitを使った量子計算の学習
Qiskitを使った量子計算の学習 - グローバーのアルゴリズム
2量子ビットで試す
from qiskit import QuantumCircuit, Aer, execute
from qiskit.quantum_info import Statevector
from qiskit.visualization import plot_histogram
# 2量子ビットを作成して重ね合わせ
grover_circuit = QuantumCircuit(2)
grover_circuit.h([0,1])
grover_circuit.draw(output="mpl")
# 状態ベクトルを見てみる
state = Statevector.from_instruction(grover_circuit)
state.draw("text")
[0.5+0.j,0.5+0.j,0.5+0.j,0.5+0.j]
ここまでは初期設定。
次に「オラクル」というものを追加するんですが、このオラクルとは探したいモノそのものや探したいモノの条件を満たすものをマーキングする（そいつだけ位相を反転させる）、という役割のもののようです。
今回は|11>を探したいとして、制御Zゲートでマーキングします。
# オラクルを追加。（正解にマークをつける）
# |11>を正解として、制御Zゲートで|11>の位相を反転させる。
grover_circuit.cz(0,1)
grover_circuit.draw(output="mpl")
state = Statevector.from_instruction(grover_circuit)
state.draw("text")
[ 0.5+0.j, 0.5+0.j, 0.5+0.j,-0.5+0.j]
状態ベクトルで見ると|11>だけマイナスになりました。これが|11>の位相を反転した状態らしい。制御Zゲートの行列表記は下のものなので、掛け算したら4つ目（|11>）がプラマイが反転するということなんでしょう。
\begin{bmatrix}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 \\
0 & 0 & 0 & -1
\end{bmatrix}
最後に、先ほどマーキングしたやつの位相を再度反転させつつ、確率振幅を増幅するゲートを追加します。
# 振幅増幅。
# 正解のマークがついているヤツの位相を反転して増幅する、らしい。
grover_circuit.h([0,1])
grover_circuit.x([0,1])
grover_circuit.cz(0,1)
grover_circuit.x([0,1])
grover_circuit.h([0,1])
grover_circuit.draw(output="mpl")
state = Statevector.from_instruction(grover_circuit)
state.draw("text")
[-1.26316153e-34+0.j,-2.36158002e-17+0.j,-9.52420783e-18+0.j,-1.00000000e+00+0.j]
初期状態の状態ベクトルと比べて、|11>だけが確率振幅が大きくなり、他は振幅が小さくなりました。このあたりは元記事（Qiskitを使った量子計算の学習 - 振幅増幅）の図を見た方がわかりやすいです。
backend = Aer.get_backend('statevector_simulator')
result = execute(grover_circuit, backend).result()
counts = result.get_counts()
plot_histogram(counts)
というわけで、これで探したいもの（|11>）がほぼ100%で出力される回路ができました。
3量子ビットを試す
同じように3量子ビットの場合もやってみましょう。
from qiskit import QuantumCircuit, Aer, execute
from qiskit.quantum_info import Statevector
from qiskit.visualization import plot_histogram, plot_bloch_vector
# 3量子ビットを作成して重ね合わせ
grover_circuit = QuantumCircuit(3)
grover_circuit.h([0,1,2])
grover_circuit.draw(output="mpl")
# 状態ベクトルを見てみる
state = Statevector.from_instruction(grover_circuit)
state.draw("text")
[0.35355339+0.j,0.35355339+0.j,0.35355339+0.j,0.35355339+0.j,
0.35355339+0.j,0.35355339+0.j,0.35355339+0.j,0.35355339+0.j]
|111>を探したいとして、制御Zゲートでマーキングします。
# オラクルを追加。（正解にマークをつける）
# |111>を正解として、制御Zゲートで|111>の位相を反転させる。
grover_circuit.ccz(0,1,2)
grover_circuit.draw(output="mpl")
state = Statevector.from_instruction(grover_circuit)
state.draw("text")
[ 0.35355339+0.j, 0.35355339+0.j, 0.35355339+0.j, 0.35355339+0.j,
0.35355339+0.j, 0.35355339+0.j, 0.35355339+0.j,-0.35355339+0.j]
2量子ビットの時と同様、探したいもの（|111>）だけマイナスになりました。
最後に、先ほどマーキングしたやつの位相を再度反転させつつ、確率振幅を増幅するゲートを追加します。
# 振幅増幅。
# 正解のマークがついているヤツの位相を反転して増幅する、らしい。
grover_circuit.h([0,1,2])
grover_circuit.x([0,1,2])
grover_circuit.ccz(0,1,2)
grover_circuit.x([0,1,2])
grover_circuit.h([0,1,2])
grover_circuit.draw(output="mpl")
state = Statevector.from_instruction(grover_circuit)
state.draw("text")
[-0.1767767 +0.j,-0.1767767 +0.j,-0.1767767 +0.j,-0.1767767 +0.j,
-0.1767767 +0.j,-0.1767767 +0.j,-0.1767767 +0.j,-0.88388348+0.j]
初期状態の状態ベクトルと比べて、|111>だけが確率振幅が大きくなり、他は振幅が小さくなりました。
backend = Aer.get_backend('statevector_simulator')
result = execute(grover_circuit, backend).result()
counts = result.get_counts()
plot_histogram(counts)
探したいもの（|111>）が78%くらいで出力される回路ができました。
実際には振幅を増幅させるゲートは複数回（総数がN個のものから探すなら√N回くらい）繰り返すべしということなので、3量子ビットで8状態から1つを探すのであれば√8≒3回くらい繰り返すと正解の確率もあがるんでしょう。
さいごに
というわけで、グローバーのアルゴリズムの計算過程を状態ベクトルで追ってみる、でした。
グローバーのアルゴリズムについて自分なりの理解としては、
- 探したいものをうまくマーキングできるような回路（オラクル）が組めれば
- 確率振幅の増幅使って短い回数で探索できるよ
というところでしょうか。
2は汎用性が高そうですが、実際何かの問題を解く場合には1が肝になりそうですね。