Groverの増幅演算子における反転操作S0の符号の問題

Groverのアルゴリズムと増幅演算子

量子ゲートコンピュータで用いられるGroverのアルゴリズムでは、入力量子状態に含まれる解状態の振幅を
増幅する演算子$Q$が定義されます。

しかしこの増幅演算子$Q$の定義が曲者で、文献や実装によって$Q$そのものだったり、$-Q$が用いられたりします。
今回はこの問題を扱いたいと思います。
結論から言いますと、
「Groverアルゴリズムであればどっちでもいいが、QAEなどの応用例では、符号の定義の違いは問題となる」
と言えます。

増幅演算子Q

構成

参考サイト(https://whyitsso.net/physics/quantum_mechanics/AA_AE_Grover.html)
がよくまとまっています。

$Q$は、次のように構成されます。
$Q = -S_{\psi}S_{f}$

ここで、
$S_{f} |\psi_{0} \rangle = |\psi_{0} \rangle $
$S_{f} |\psi_{1} \rangle = -|\psi_{1} \rangle $
は、解状態$|\psi_{1} \rangle $だけ符号反転させるゲートです。(オラクルと呼ばれます）

また、
$-S_{\psi} = 2|\psi \rangle \langle \psi | - I$
は、状態を初期状態（＝Groverアルゴリズムの入力状態）$| \psi \rangle$を軸として反転させるゲートです。
更にシンプルな書き方ができて、
$-S_{\psi} = -US_{0}U^{\dagger}$
$S_{0} = I - 2|000 \rangle \langle 000|$
$|\psi \rangle = U|000 \rangle$
となります。(3qubitの場合)
初期状態$| \psi \rangle$は自分が用意するものですから、それを作り出す操作$U$は既知です。
$U$から$U^{\dagger}$を作るのは簡単で、ゲートの順番を逆にすればよいです。
よって、反転操作$-S_{0}$を構築すれば$-S_{\psi} = U(-S_{0})U^{\dagger} $は作れます。

反転操作 - S0

$Q$を構成する要素である反転操作$-S_{0}$を、具体的にどういう基本ゲートで作るかを考えます。
実はこれが意外と難しいようなのです（？）
代わりに、$+S_{0}$は比較的かんたんに作ることが出来ます。

3qubitの場合、
$S_{0} = I - 2|000 \rangle \langle 000|$

です。$|000 \rangle \langle 000|$の行列表示$a_{ij}$を考えると、最も左上の成分$a_{00}=1$であり、ほかは全て$0$となっています。
ここから$S_{0}$の行列表示$b_{ij}$は、

• 最も左上の成分$b_{00}=-1$
• それ以外の対角成分は$b_{ii} = 1$
• それ以外の全成分は$b_{ij} = 0$

となります。よって、$S_{0} = X^{\otimes 3} (CCZ)X^{\otimes 3}$ となることがわかります。
$CCZ$は制御制御$Z$です。ふつうは制御NOT(CX)あるいは制御制御NOT(CCX)しか使えないので、
$Z = HXH$の関係を使ってCXで表現すれば実装できます。
実際、このような構成方法が多くの場合に見られます。

Blueqatチュートリアル
(https://github.com/Blueqat/Blueqat-tutorials/blob/master/tutorial-ja/116_grover_ja.ipynb), typoあり

Qiskitチュートリアル(の、example3)¹
(https://qiskit.org/textbook/ch-algorithms/grover.html)

QiskitのGroverアルゴリズムのライブラリ ; $S_{0}$とGlobal phase について記載があります。
(https://qiskit.org/documentation/stubs/qiskit.circuit.library.GroverOperator.html)

しかしここで作ったのは$-S_{0}$ではなく$+S_{0}$です。

反転操作が +S0 か -S0か　で何が違うか

Groverのアルゴリズムの場合

反転操作が $+S_{0}$ か $-S_{0}$か　で何が違うか、困ったことが起こるのか、考えてみます。

それはつまり増幅演算子が$-Q$であるか$+Q$であるかということになります。
Groverのアルゴリズムの場合、増幅演算子$+Q$を掛けるたびに解状態の振幅が増幅されます。
$-Q$を掛けた場合、状態全体の符号が(掛けるたびに)反転します。
Groverのアルゴリズムでは振幅ではなく振幅の絶対値（確率）が高ければよいので、符号は問題になりません。
そもそも状態全体の符号というのはいわゆるグローバル位相ですので、これを検出するような測定は存在しません。

QAEアルゴリズムの場合

次にQAE(Quantum Amplitude Estimation) の場合を考えてみます。
QAEについては当ブログ参照。(https://qiita.com/notori48/items/2082be87eea0985b01ba)

QAEでは、増幅演算子$Q$の固有値の位相に興味があります。これをQPEで推定するというのがQAEです。

増幅演算子$Q$の固有値の位相を$\theta$とします。3 qubit精度で推定する場合は
$\theta = 2\pi(j_{0}/2+j_{1}/4+j_{2}/8) = 2\pi(0.j_{0}j_{1}j_{2})$ となる2進小数表示$j_{0,1,2}$を推定します。
$j_{0}$が$0$であるか$1$であるかは位相に$\pi$の項があるかないかに相当しています。

では、増幅演算子が符号の違っている$-Q$だった時、推定結果に影響はあるでしょうか？
$-Q = e^{j\pi}Q$ であることに注意します。つまり$-Q$の固有値の位相は$\theta$から$\theta' = \theta+\pi$へ移っています。
よって推定結果は
$\theta' = 2\pi( (\lnot j_{0})/2+j_{1}/4+j_{2}/8) = 2\pi(0.(\lnot j_{0})j_{1}j_{2}) \neq \theta$
となります。
$\lnot $ は$0$と$1$を反転する操作です。
位相が$\pi$ずれるということは、$j_{0}$が$0$であるか$1$であるかをひっくり返すことと同じだからです。²

ということで、
QPEの場合（ひいてはQAEの場合）には増幅演算子が$+Q$なのか$-Q$なのかは結果に影響を与えます。³

$-Q$を使ってしまった場合には、$j_{0}$を測定後にひっくり返すか、
測定前の量子状態$|j_{0} \rangle$に$X$ゲートを置いてやることで符号の違いを吸収できるかと思います。
(試していませんけども）

2021/02/25追記

過去記事; Qiskitで量子振幅推定(QAE)に
$+Q$の場合と$-Q$の場合を掲載しています。

• $+Q$の場合は$001, 110$
• $-Q$の場合は$101, 010$

となっています。
確かに$\pi$に対応する桁（左端の量子ビットです)が反転しています。

結論

• 「符号はグローバル位相なので気にしない」は危険かもしれない。
• 実装例を鵜呑みにはせずに、自分でひとつずつチェックすることが重要。

1. なぜかexample 2 では正しく$-S_{0}$を構成しています。おそらく2qubit程度であれば$-S_{0}$を作るのは大変ではないのでしょう。 ↩

2. $j_{0}$にだけ影響が出る理由は、ここだけ$Q$の作用する回数が奇数(1回)だからです。'-1'の因子が消えること無く制御ビットの相対位相に移っていきます（位相キックバック）。移った先はグローバル位相ではなく相対位相ですので、測定結果として区別されるわけです。 ↩

3. 私の過去記事で実際にこの問題が起きています。https://qiita.com/notori48/items/5bf7e43aa2c4d70aed36 ↩