目的
文献 [NC2] p.56 図 4.19 に RZ^{\otimes 4} ゲートの分解が書かれている・・・と思った結果、計算とシミュレーションからするとそれはそうであるらしきことを RZZZ ゲートの分解 (1) で扱った。しかし、[SRL12] や [GKZ20] を読むうちに、どうやら本来はそういう意図ではなく、
と解釈するべきだったようであることに気付いた。つまり、図でいう q_3 は補助量子ビット (ancilla qubit) ということだ。実際、[GKZ20] では以下のように書いてある:
Figure 3: On the left, two decompositions of exp(itZ1Z2Z3), a) without auxiliary qubit [28] (p.30), and b) with auxiliary qubit [29] (p.210).
今回はこれについて確認してみたい。
発見的考察
この補助量子ビットはどういう役割を担っているのかよく分からなかったので、ChatGPT と会話をしてみた。すると以下のような回答を得た。
- 具体的には、計算基底状態のパリティ（全ての Z の積）が偶数か奇数かによって、\pm i \Delta t の位相がつく。
- パリティ計算: アンシラ量子ビットを使って、対象の n 個の量子ビットのパリティ（1が何個あるかの偶奇）を計算する。
- 条件付き位相回転: パリティが偶数なら \exp (-i \Delta t) を適用し、奇数なら \exp (i \Delta t) を適用。
- アンシラリセット: 計算したパリティを元に戻して、アンシラを初期状態に戻す。
これはどういうことであろうか？n=1 の時を考えよう。補助量子ビットは \ket{0} で初期化するので、入力は \ket{\psi} = \ket{00} または \ket{10} である。RZ(\theta) = \exp \left( -i\frac{\theta}{2} Z \right) = \begin{pmatrix} e^{-i\frac{\theta}{2}} & 0 \\ 0 & e^{i\frac{\theta}{2}} \end{pmatrix} であるので、補助量子ビットのことを忘れると
\begin{align*}
RZ(\theta) \ket{0} = \begin{pmatrix} e^{-i\frac{\theta}{2}} \\ 0 \end{pmatrix} = e^{-i\frac{\theta}{2}} \ket{0}
\end{align*}
と
\begin{align*}
RZ(\theta) \ket{1} = \begin{pmatrix} 0 \\ e^{i\frac{\theta}{2}} \end{pmatrix} = e^{i\frac{\theta}{2}} \ket{1}
\end{align*}
を期待したい。0b0 と 0b1 に対するパリティを考えつつ量子回路に \ket{\psi} = \ket{00} または \ket{10} を与えてみると、確かに ChatGPT の回答のようになっていそうだ。例えば \ket{\psi} = \ket{10} のケースを計算すると以下のようになる:
\begin{align*}
CX_{01} (Z \otimes I) CX_{01} \ket{10} = CX_{01} (Z \otimes I) \ket{11} = CX_{01} e^{i\frac{\theta}{2}} \ket{11} = e^{i\frac{\theta}{2}} \ket{10}
\end{align*}
ここで補題を 1 つ用意する:
この補題を踏まえると、上図の場合、q_0, q_1, q_2 で表現される 2 進数 0bq₀q₁q₂ のパリティに応じた個数の X ゲートが補助量子ビットに適用され、それに応じて \exp (-i\frac{\theta}{2}) か \exp (i\frac{\theta}{2}) の位相が全体にかかりそうである。補助量子ビットは逆計算で \ket{0} に戻るので、位相キックバックの形で、位相 \exp (\pm i\frac{\theta}{2}) は q_0, q_1, q_2 にかかることになる。
n=2 の時は RZZ (\theta) = \begin{pmatrix} e^{i\frac{\theta}{2}} & 0 & 0 & 0 \\ 0 & e^{-i\frac{\theta}{2}} & 0 & 0 \\ 0 & 0 & e^{-i\frac{\theta}{2}} & 0 \\ 0 & 0 & 0 & e^{i\frac{\theta}{2}} \end{pmatrix} なので少しややこしいが、0b00, 0b01, 0b10, 0b11 のパリティと見比べると ChatGPT の回答が正しそうであることが分かる。
もう 1 つ補題を用意しておこう。
さて、ここまでの内容を踏まえて定理のステートメントを少し書き換えると以下のようになる:
主定理の証明
前半の数式を認めると、後半の主張は自動的に従う。何故なら CX を用いてパリティに応じた X ゲートの適用を補助量子ビットに施しており、Lemma 1 より e^{\pm i\frac{\theta}{2}} の符号が切り替わる形になるからである。よって数式部分を検証すれば良い。
上記で見たように、n=1（および n=2）の時は主張が成立する。n-1 の時まで主張が成立すると仮定して n の時を見よう。簡単のため、n=3 と n-1=2 の時を見比べる。0 を省略すると、
\begin{align*}
RZ^{\otimes n - 1} (\theta) = R(Z \otimes Z) (\theta) &= \exp \left(-i \frac{\theta}{2} \begin{pmatrix}
\textcolor{red}{1} & & & \\
& \textcolor{red}{-1} & & \\
& & \textcolor{red}{-1} & \\
& & & \textcolor{red}{1}
\end{pmatrix} \right) \\
&= \begin{pmatrix}
\textcolor{red}{e^{-i\frac{\theta}{2}}} & & & \\
& \textcolor{red}{e^{i\frac{\theta}{2}}} & & \\
& & \textcolor{red}{e^{i\frac{\theta}{2}}} & \\
& & & \textcolor{red}{e^{-i\frac{\theta}{2}}}
\end{pmatrix}
\end{align*}
と
\begin{align*}
RZ^{\otimes n} (\theta) = R(Z \otimes Z^{\otimes n-1}) (\theta) &= \exp \left(-i \frac{\theta}{2} \begin{pmatrix}
\textcolor{red}{1} & & & & & & & \\
& \textcolor{red}{-1} & & & & & & \\
& & \textcolor{red}{-1} & & & & & \\
& & & \textcolor{red}{1} & & & & \\
& & & & \textcolor{#5588FF}{-1} & & & \\
& & & & & \textcolor{#5588FF}{1} & & \\
& & & & & & \textcolor{#5588FF}{1} & \\
& & & & & & & \textcolor{#5588FF}{-1}
\end{pmatrix} \right) \\
&= \begin{pmatrix}
\textcolor{red}{e^{-i\frac{\theta}{2}}} & & & & & & & \\
& \textcolor{red}{e^{i\frac{\theta}{2}}} & & & & & & \\
& & \textcolor{red}{e^{i\frac{\theta}{2}}} & & & & & \\
& & & \textcolor{red}{e^{-i\frac{\theta}{2}}} & & & & \\
& & & & \textcolor{#5588FF}{e^{i\frac{\theta}{2}}} & & & \\
& & & & & \textcolor{#5588FF}{e^{-i\frac{\theta}{2}}} & & \\
& & & & & & \textcolor{#5588FF}{e^{-i\frac{\theta}{2}}} & \\
& & & & & & & \textcolor{#5588FF}{e^{i\frac{\theta}{2}}}
\end{pmatrix}
\end{align*}
である。RZ^{\otimes n - 1} (\theta) には入力 \ket{\psi} として
- \ket{00} \ (0b00)
- \ket{01} \ (0b01)
- \ket{10} \ (0b10)
- \ket{11} \ (0b11)
が入り得る。仮定よりこの時、入力量子ビットのパリティが偶数の時、\ket{\psi} に位相 e^{-i\frac{\theta}{2}} がかかり、パリティが奇数の時、\ket{\psi} に位相 e^{i\frac{\theta}{2}} がかかることになる。式で書くと RZ^{\otimes n} (\theta) \ket{\psi} = \exp \left( (-1)^{\operatorname{parity}(\ket{\psi}) + 1} \cdot i \frac{\theta}{2} \right) \ket{\psi} である。ここで、\operatorname{parity}(\ket{\psi}) で \ket{\psi} = \ket{x_0 \cdots x_{N}} に対する 0b x_1 \cdots x_{N} のパリティ \sum_{j=0}^N x_j \mod 2 を表すものとする。
n の時を見よう。この時、RZ^{\otimes n} (\theta) には入力 \ket{\psi^\prime} として
グループ 1
- \ket{\textcolor{red}{0}00} \ (0b\textcolor{red}{0}00)
- \ket{\textcolor{red}{0}01} \ (0b\textcolor{red}{0}01)
- \ket{\textcolor{red}{0}10} \ (0b\textcolor{red}{0}10)
- \ket{\textcolor{red}{0}11} \ (0b\textcolor{red}{0}11)
と
グループ 2
- \ket{\textcolor{#5588FF}{1}00} \ (0b\textcolor{#5588FF}{1}00)
- \ket{\textcolor{#5588FF}{1}01} \ (0b\textcolor{#5588FF}{1}01)
- \ket{\textcolor{#5588FF}{1}10} \ (0b\textcolor{#5588FF}{1}10)
- \ket{\textcolor{#5588FF}{1}11} \ (0b\textcolor{#5588FF}{1}11)
が入り得る。
グループ 1 の入力 \ket{\psi^\prime} は RZ^{\otimes n - 1} (\theta) の入力 \ket{\psi} を 0 拡張した形であり、拡張前と同じパリティを持つことに注意したい。また、\ket{\psi^\prime} = \ket{0} \otimes \ket{\psi} であるが、Lemma 2 とテンソル積の性質より、
\begin{align*}
RZ^{\otimes n} (\theta) \ket{\psi^\prime} &= \begin{pmatrix}
RZ^{\otimes n - 1} (\theta) & \boldsymbol{0} \\
\boldsymbol{0} & RZ^{\otimes n - 1} (-\theta)
\end{pmatrix} \begin{pmatrix}
\ket{\psi} \\ \boldsymbol{0}
\end{pmatrix} \\
&= \begin{pmatrix}
RZ^{\otimes n - 1} (\theta) \ket{\psi} \\ \boldsymbol{0}
\end{pmatrix} \\
&= \exp \left( (-1)^{\operatorname{parity}(\ket{\psi}) + 1} \cdot i \frac{\theta}{2} \right) \begin{pmatrix}
\ket{\psi} \\ \boldsymbol{0}
\end{pmatrix} \\
&= \exp \left( (-1)^{\operatorname{parity}(\ket{\psi^\prime}) + 1} \cdot i \frac{\theta}{2} \right) \ket{\psi^\prime}
\end{align*}
を得る。
グループ 2 の入力 \ket{\psi^\prime} は RZ^{\otimes n - 1} の入力 \ket{\psi} を 1 拡張した形であり、拡張前と異なるパリティ、つまり \operatorname{parity}(\ket{\psi^\prime}) = \operatorname{parity}(\ket{\psi}) - 1 を持つ。\ket{\psi^\prime} = \ket{1} \otimes \ket{\psi} に注意すると、
\begin{align*}
RZ^{\otimes n} (\theta) \ket{\psi^\prime} &= \begin{pmatrix}
RZ^{\otimes n - 1} (\theta) & \boldsymbol{0} \\
\boldsymbol{0} & RZ^{\otimes n - 1} (-\theta)
\end{pmatrix} \begin{pmatrix}
\boldsymbol{0} \\ \ket{\psi}
\end{pmatrix} \\
&= \begin{pmatrix}
\boldsymbol{0} \\ RZ^{\otimes n - 1} (-\theta) \ket{\psi}
\end{pmatrix} \\
&= \exp \left( (-1)^{\operatorname{parity}(\ket{\psi}) + 1} \cdot i \frac{-\theta}{2} \right) \begin{pmatrix}
\boldsymbol{0} \\ \ket{\psi}
\end{pmatrix} \\
&= \exp \left( (-1)^{\operatorname{parity}(\ket{\psi})} \cdot i \frac{\theta}{2} \right) \begin{pmatrix}
\boldsymbol{0} \\ \ket{\psi}
\end{pmatrix} \\
&= \exp \left( (-1)^{\operatorname{parity}(\ket{\psi^\prime}) + 1} \cdot i \frac{\theta}{2} \right) \ket{\psi^\prime}
\end{align*}
を得る。
故に、グループ 1 も 2 も RZ^{\otimes n} (\theta) \ket{\psi^\prime} = \exp \left( (-1)^{\operatorname{parity}(\ket{\psi^\prime}) + 1} \cdot i \frac{\theta}{2} \right) \ket{\psi^\prime} となることが示され、n の時の主張の成立が確かめられた。
ここでは見た目の分かりやすさのために n=3 としたが、一般の n \in \N で考えても同様であることは明らかである。以上より帰納法より主張が従う。{}_\blacksquare
まとめ
前回は定理のステートメントを勘違いしたまま証明してしまい焦ったが、図の意味を本来の意味で解釈しても本来の主張が示せることが分かった。多少不思議な気持ちである。
文献
[NC2] Michael A. Nielsen, Isaac L. Chuang, 量子コンピュータと量子通信 II, オーム社, 2005
[SRL12] Jacob T. Seeley, Martin J. Richard, Peter J. Love, The Bravyi-Kitaev transformation for quantum computation of electronic structure, arXiv:1208.5986
[GKZ20] Adam Glos, Aleksandra Krawiec, Zoltán Zimborás, Space-efficient binary optimization for variational computing, arXiv:2009.07309
Discussion