量子コンピュータって計算速度が早いというけれど、本当に早いのか気になったのでグローバー探索アルゴリズムというのを勉強しました。間違いやご指摘、質問があればいつでも言ってください。一生懸命考えます。
概要
１枚だけ「当たり」がある、裏返しにランダムに並んでいるトランプがあり、１回で当たりを引く問題を解きたい。
古典アルゴリズムでは問い合わせ量は$O(N)$かかるが、グローバーの探索アルゴリズムでは$O(\sqrt{N})$で探索できるとのこと。基本的な原理は振幅増幅手法というものらしい。
探索解の振幅増幅手法
探索解の振幅増幅手法というのをステップごとに見ていきたいと思う。
先に出した図のように「４つの状態」から「１つ当たり」の問題を考えていきたいと思う。
(0)問題設定
整列されていない４つの状態$\ket{00}=\ket{0}, \ket{01}=\ket{1}, \ket{10}=\ket{2}, \ket{11} = \ket{3}$の中から当たりである$\ket{3}$を探し出す状況を考える。
(1) 全状態の確率振幅が同じ状態を作り出す。
まず全状態ベクトルの確率振幅が同じになるよう重ね合わせ状態を作る。
重ね合わせ状態はアダマールゲートで作れるので、全量子ビットにアダマール変換を課す。
実装は以下。
# qiskitでの実装
from qiskit import *
from qiskit.tools.visualization import *
# --回路生成----------------------------------------------------------
# n = 4のとき２量子ビットあれば４状態表せる
bn = 2 # 量子ビット
q = QuantumRegister(bn, 'q') # bn個のレジスタを生成
c = ClassicalRegister(bn, 'c') # bn個の古典レジスタも観測用に生成
qc = QuantumCircuit(q, c) # 量子、古典レジスタをもとに量子回路を生成
for i in range(bn):
qc.h(q[i]) # 全量子ビットにアダマールゲートを課すことで重ね合わせ状態を作り出す
for i in range(bn):
qc.measure(q[bn - 1 - i], c[i]) # 測定するために各量子ビットを古典レジスタと結びつける
# --実行--------------------------------------------------------------
r = execute(qc, Aer.get_backend('qasm_simulator')).result() # qasm_simulatorで実行する。
rc = r.get_counts() # 各状態に対して回数をカウント
print(rc)
plot_histogram(rc)
出力は以下。全状態が等確率（誤差はあるが）で観測できているので、重ね合わせはできているようですね。
(2)探索解を位相反転でマーキング
次に、探索解である$\ket{3}$に目印をつける。目印は位相反転(制御Zゲート)で行う。
位相反転は確率振幅を操作するわけではないので、このままではまだ$O(N)$の探索となっている。
# qiskitでの実装
from qiskit import *
from qiskit.tools.visualization import *
# --回路生成----------------------------------------------------------
bn = 2
q = QuantumRegister(bn, 'q')
c = ClassicalRegister(bn, 'c')
qc = QuantumCircuit(q, c)
for i in range(bn):
qc.h(q[i])
# 追加点
# 探索解|3>をマーキング。
# q[0]=1のときにq[1]の符号を反転する。
# つまり|11> → -|11> となる。(|3>のみ位相反転が起きる。)
qc.cz(q[0], q[1])
for i in range(bn):
qc.measure(q[bn - 1 - i], c[i])
# --実行--------------------------------------------------------------
r = execute(qc, Aer.get_backend('qasm_simulator')).result()
rc = r.get_counts()
print(rc)
plot_histogram(rc)
結果は以下。位相変えただけなので、確率振幅は変わっていないですね。
(3)確率振幅の平均値の周りでの反転（拡散変換）
最後に、この状態の”確率振幅の平均値”を求め、この平均値周りに確率振幅を反転させることで、効率化される。
現在の重ね合わせ状態は
$$
\frac{1}{2}\ket{0} + \frac{1}{2}\ket{1} + \frac{1}{2}\ket{2} - \frac{1}{2}\ket{3}
$$
なので、確率振幅の平均$\left\langle{av}\right\rangle$は
$$
\left\langle{av}\right\rangle = \frac{1}{4}\left(\frac{1}{2} + \frac{1}{2} + \frac{1}{2} - \frac{1}{2}\right) = \frac{1}{4}
$$
である。各確率振幅を$\alpha_i$とすると、
平均値回りで反転させるには、平均値$\left\langle{av}\right\rangle$から各$\alpha_i$を引き、さらに$\left\langle{av}\right\rangle$を足せば良いので、反転した状態は
$$
\ket{\phi} = \sum_{i = 0}^{3}\left[\left\langle{av}\right\rangle - \alpha_i + \left\langle{av}\right\rangle \right] = \ket{3}
$$
が得られる。
平均値回りでの反転は拡散変換と呼ばれ、HゲートとXゲート、CZゲートで実現できるらしい。実装参照。
# qiskitでの実装
from qiskit import *
from qiskit.tools.visualiacion import *
# --回路生成----------------------------------------------------------
bn = 2
q = QuantumRegister(bn, 'q')
c = ClasscalRegister(bn, 'c')
qc = QuantumCircuit(q, c)
for i in range(bn):
qc.h(q[i])
qc.cz(q[0], q[1])
# 追加点
# 拡散変換
for i in range(bn):
qc.h(q[i])
for i in range(bn):
qc.x(q[i])
qc.cz(q[0], q[1])
for i in range(bn):
qc.x(q[i])
for i in range(bn):
qc.h(q[i])
for i in range(bn):
qc.measure(q[bn - 1 - i], c[i])
# --実行--------------------------------------------------------------
r = execute(qc, Aer.get_backend('qasm_simulator')).result()
rc = r.get_counts()
print(rc)
plot_histogram(rc)
結果は以下。当たりの状態$\ket{11} = \ket{3}$が確率$1$で観測されてくれました！すごい！！
まとめ
グローバーの探索アルゴリズムの初歩をまとめました。少し理解できた気がします。より状態数が多い場合のグローバーの探索アルゴリズムもそのうちやりたいと思っていますが、今回はここまでにします。
量子コンピュータの肝は複数の状態を一度に持てるということなんだな〜、これが重ね合わせということか〜、と再認識しました。まだまだ勉強に励みたいと思います。
参考
勉強に使用した書籍です。
$$\newcommand{\ket}[1]{\left|{#1}\right\rangle}$$
$$\newcommand{\bra}[1]{\left\langle{#1}\right|}$$
$$\newcommand{\braket}[2]{\left\langle{#1}\middle|{#2}\right\rangle}$$
$$\newcommand{\bk}[1]{\left\langle{#1}\right\rangle}$$