グローバーのアルゴリズム基礎(2)：位相反転増幅回路

本日は前回の続きで、位相反転増幅回路について解説します。

シリーズ予定：

オラクル回路
位相反転増幅回路 << 今回
3量子ビット以上の場合
まとめと簡単な応用例

前回はオラクル回路によって正解の状態の位相(正負)を反転させてマーキング(目印)しました。
ただ、この段階では測定しても確率振幅の大きさ自体は変わっていないので、他の正解でない状態の確率とは等確率のため見分けがつきません。
今回の位相反転増幅回路はマーキングした状態の確率振幅の大きさを大きくし、他の状態の確率振幅の大きさを相対的に低くする手法です。

(余談ですが、確率振幅「の大きさ」と言っているのは、確率振幅は複素数だからです。
通常の水波・地震波・振り子などの振幅は実数ですから「の大きさ」は不要です。)

対象とする読者

量子プログラミング・量子計算に興味を持って勉強し始めたエンジニア・高校生・大学生
Groverのアルゴリズムについて改めて知りたい方など

前提とする知識

簡単な論理演算(AND, OR, NOT)が分かること
基本的な量子ゲート(H, X, CX, CCX, Z, CZ)が分かること
線形代数(行列・ベクトルの積、直積、あとできれば線形変換)が分かること
ベクトルのブラケット記法( $|0>, |1>$ など、もしくはDirac記法ともいう)が分かること

バージョン情報

Python 3.7.3
Qiskit 0.23.1

位相反転増幅回路の役割と仕組み
まとめ

位相反転増幅回路の役割と仕組み

役割と仕組み

Groverのアルゴリズムの概略は下記でした。

f:id:sakumadaisuke32:20210214150611p:plain — 図1. Grover回路の概要

前回のオラクル回路はこの図の $U_f$ で、今回は右側の $H^{\otimes n} (2 | 0 ^n \gt \lt 0 ^n | - I_n) H^{\otimes n}$ の「位相反転増幅回路」について解説します。

この回路の役割はオラクル回路でマーキングした状態に量子状態を近づけることです。

f:id:sakumadaisuke32:20210227161153p:plain — 図2. 位相反転増幅の概念図. マーキングした状態 $|\Psi_{t'} \gt$ から元の状態 $| s \gt$ を軸に反転する.(QuantumChallenge2020の問題より)

オラクル回路でターゲットの状態にマーキングした状態 $|\Psi_{t'} \gt$ に対して、元の状態 $| s \gt$ を軸に反転させる操作を行い、ターゲットの状態 $| w \gt$ に近づけます。

この操作 $U_s$ は数式で表すと下記です。

$\displaystyle{ U_s |\Psi_{t'} \gt = (2 |s \gt \lt s | - I ) |\Psi_{t'} \gt }$

数式からの理解は嶋田さんの本に記載がありますのでここでは図形的に理解を図ります。
このユニタリー変換 $U_s$ を日本語にすると、「ベクトル $| \Psi_{t'} \gt$ のうちベクトル $| s \gt$ に沿った成分を2倍して、反対向きのベクトルを加算する」なのですが図解すると、下図の通りひし形になります。
(4辺が等しい平行四辺形はひし形)

f:id:sakumadaisuke32:20210227170018p:plain — 図3. ユニタリー変換 $U_s$ の図解

これを最初に思いついた人はすごいとしか思えませんが、結果的にこの演算をすると、ベクトル $| \Psi_{t'} \gt$ を $|s>$ を軸に反転することになります。
そして $| s \gt$ と $| s' \gt$ の角度を $\theta$ としたときに $|s>$ から $2 \theta$ だけ目的の状態に近づきます。

オラクル回路と位相反転増幅回路の組み合わせを適切な回数繰り返すことによって少しずつターゲットの状態 $| w \gt$ に近づきます。
ただ、繰り返しすぎると通り過ぎてしまうのでちょうどいい回数で止めることに注意です。

実装例

この式の演算を量子ゲートに変換すると下記です。

qr = QuantumRegister(2, 'data')
cr = ClassicalRegister(2, 'output')
grover = QuantumCircuit(qr, cr)

# 重ね合わせ状態の生成
grover.h(qr)

# オラクル
grover.cz(qr[0], qr[1])

# 位相反転増幅
grover.h(qr)
grover.x(qr)
grover.h(qr[-1])
grover.cx(qr[0], qr[1])
grover.h(qr[-1])
grover.x(qr)
grover.h(qr)

# 測定
grover.measure(qr, cr)

f:id:sakumadaisuke32:20210214152132p:plain — 図4. Grover回路の全体図. 位相反転増幅回路は緑枠で囲った箇所.

位相反転増幅回路の中身

位相反転増幅 $U_s$ が何をしているのか分解していこうと思いますが、この式は次のように書き換えられます。
(簡単のために2量子ビット系にします。)

$\begin{aligned} U_s &= 2 |s >< s| - I \\ &= 2 H^{\otimes 2} | 00 >< 00 | H^{\dagger \otimes 2} - H^{\otimes 2} I H^{\dagger \otimes 2} \\ &= H^{\otimes 2} (2 | 00 >< 00 | - I ) H^{\dagger \otimes 2} \\ &= H^{\otimes 2} (2 | 00 >< 00 | - I ) H^{\otimes 2} \end{aligned}$

両サイドのHゲートはそのままHゲートで良いのですが、間の $2 | 00 \gt \lt 00 | - I$ の実装方法がミソです。
図4の内 $2 | 00 \gt \lt 00 | - I$ の操作に対応する箇所だけ抜き出したのが下記です。

f:id:sakumadaisuke32:20210227190437p:plain — 図5. $2 | 00 \gt \lt 00 | - I$ に対応する回路

例えば、今回の2量子ビットの場合、Hゲート通過後でこの回路に入る直前の状態は下記です。

$\displaystyle{ |s' > = \frac{1}{2} (|00> + |01> + |10> - |11>) }$

まず元の理論の確認をするため、ここに $2 | 00 \gt \lt 00 | - I$ を掛けます。

$\begin{aligned} (2 | 00 \gt \lt 00 | - I) |s' \gt &= (2 | 00 \gt \lt 00 | - I) \frac{1}{2} (|00 \gt + |01 \gt + |10 \gt - |11 \gt) \\ &= \frac{1}{2} (2 | 00 \gt - | 00 \gt - | 01 \gt - | 10 \gt + | 11 \gt ) \\ &= \frac{1}{2} (| 00 \gt - | 01 \gt - | 10 \gt + | 11 \gt ) \equiv |s'' \gt \end{aligned}$

一方、回路の挙動を確認するため図5の量子回路を通過した後の状態( $| 00 \gt$ のみ位相を反転)は下記です。

$\begin{aligned} |s''' > &= \frac{1}{2} (-|00> + |01> + |10> - |11>) \\ &= - \frac{1}{2} (|00> - |01> - |10> + |11>) \equiv - |s'' \gt \end{aligned}$

ということで、グローバル位相は $\pi$ だけ異なりますが、他は同一であることが分かります。

この実装になっている理由は僕は分かりませんが、元々実現したかった「 $| 00 >$ 以外の確率振幅の位相を反転する」という操作を量子回路で実装する方法が思い当たりませんでした。
もしかしたらあるのかもしれませんが、難しいのかもしれません。

ちなみに、仮にどうにかして「 $| 00 >$ 以外の確率振幅の位相を反転する」という回路が実現できたとして、その後の量子状態は $| s'' \gt$ です。

元々の数学上で行いたかった操作は下図の $U_s$ ですが、実装では $U'_s$ のような変換をしているのだと思います。
結果的に目的の状態 $| w \gt$ を取り出せているので良いです。

f:id:sakumadaisuke32:20210227192316p:plain — 図6. 図5の量子回路が行っている操作 $\hat{U'}_s$

最後に再びHゲートを全体に掛けます。

$\begin{aligned} H^{\otimes 2} |s'' \gt &= \frac{1}{2} H^{\otimes 2} (|00> - |01> - |10> + |11>) \\ &= \frac{1}{4} \{(| 0 \gt + | 1 \gt )(| 0 \gt + |1 \gt) - (| 0 \gt + | 1 \gt) (| 0 \gt - | 1 \gt) \\ &- (| 0 \gt - | 1 \gt) (| 0 \gt + | 1 \gt) + (| 0 \gt - | 1 \gt) (| 0 \gt - | 1 \gt)\}\\ &= \frac{1}{4} (| 00 \gt + | 01 \gt + | 10 \gt + | 11 \gt \\ &- | 00 \gt + | 01 \gt - | 10 \gt + | 11 \gt \\ &- | 00 \gt - | 01 \gt + | 10 \gt + | 11 \gt \\ &+ | 00 \gt - | 01 \gt - | 10 \gt + | 11 \gt ) \\ &= | 11 \gt \end{aligned}$