量子ゲートを作用させて計算する過程を順番に見ていくだけの記事です。以前投稿した制御トフォリゲートの構成の補足記事という位置づけです。
$$
\def\bra#1{\mathinner{\left\langle{#1}\right|}}
\def\ket#1{\mathinner{\left|{#1}\right\rangle}}
\def\braket#1#2{\mathinner{\left\langle{#1}\middle|#2\right\rangle}}
\def\ketround#1{\mathinner{\left|{\,#1\,}\right)}}
$$
トフォリゲート
復習になりますが、トフォリゲートは3量子ビットゲートで以下の演算を実現します。
CCNOT: \,\, \ket{x}\ket{y}\ket{z} \longmapsto \ket{x}\ket{y} \ket{z \oplus xy}.
$x$と$y$がともに1の場合のみ、$z$を反転させます。AND演算とXORの組み合わせになりますので、加算器を量子回路上で実装する場合などに使用します。
以前投稿した記事では、トフォリゲートは以下のように1量子ビットゲート（$H$, $T$, $T^{\dagger}$）と2量子ビットゲート（CNOT）の組み合わせで実現できると記述しました。
前述の記事内では上記結果を無条件で認めて利用しましたが、本記事で計算過程を追いながら確かめてみたいと思います。
確認
実際に確認してみたいと思います。
準備
計算過程を追う上で必要な内容をざっくりと押さえておきます。
記法
多量子ビット状態に対する演算は、どの量子ビットが演算対象であるかを明示する必要があります。まず、量子ビットに対して以下のようにインデックスを付与します。
\ket{x} _{1} \ket{y} _{2} \ket{z} _{3} \equiv \ket{x} \ket{y} \ket{z}.
以降はインデックスを省略しますが、左から順にインデックスを付与したことを覚えておいてください。次に、各量子ゲートがどの量子ビットに作用しているかを示すために、ゲート演算子に対してもインデックスを付与します。まずは1量子ビットゲート演算子については、
U(i) \left( \ket{x_{1}}_{1} \ket{x_{2}} \cdots \ket{x_{i}}_{i} \cdots \ket{x_{N}}_{N} \right)
= \ket{x_{1}}_{1} \ket{x_{2}} \cdots \left( U(i) \ket{x_{i}}_{i} \right) \cdots \ket{x_{N}}_{N}
です。次に2量子ビット演算子ですが、制御ビットのインデックス$i$と標的ビットのインデックス$j$を指定して、
\tilde{U} (i, j) \left( \ket{x_{1}}_{1} \ket{x_{2}} \cdots \ket{x_{i}}_{i} \cdots \ket{x_{j}} _{j} \cdots \ket{x_{N}}_{N} \right)
と記載します。具体的にCNOTゲートを例にすると、
CNOT(1,2) \ket{x} \ket{y}
= \ket{x} \ket{y\oplus x},
\quad
CNOT(2,1) \ket{x} \ket{y} = \ket{x\oplus y}\ket{y}
です。
ゲート演算の復習
トフォリゲートの構成に使用するゲート演算子の演算を復習しておきましょう。
アダマールゲート
アダマールゲートは$z$軸方向の固有状態の重ね合わせを作ります。
H \ket{z} = \frac{1}{\sqrt{2}} \left( \ket{0} + (-1)^{z} \ket{1} \right)
= \frac{1}{\sqrt{2}} \sum _{z^{\prime} = 0, 1} (-1) ^{zz^{\prime}} \ket{z^{\prime}}.
行列表示すると、
H = \frac{1}{\sqrt{2}} \left(
\begin{matrix}
1 & 1 \\
1 & -1
\end{matrix}
\right)
です。$H$はユニタリ演算子で、なおかつ要素が実数ですので、$H^{-1} = H^{\dagger} = H$が成立します。すなわち
H^{2} = I
です。
Tゲート
$T$および$T^{\dagger}$は、位相ゲート$P_{\phi}$の一種です。具体的には、
T = P_{\phi = \pi/4}, \quad T^{\dagger} = P_{\phi = -\pi / 4}
です。$P_{\phi}$は位相を$\phi$だけずらすゲート演算子です。
P_{\phi} \ket{z} = e^{i \phi} \ket{z}.
したがって、
\begin{align}
T \ket{z} &= e^{i z \pi/4} \ket{z} \\
T^{\dagger} \ket{z} &= e^{-i z \pi/4} \ket{z} \\
\end{align}
です。なお、$P_{\phi}$を行列表示すると、
P_{\phi} = \left(
\begin{matrix}
1 & 0 \\
0 & e^{i\phi}
\end{matrix}
\right)
ですので、
T = \left(
\begin{matrix}
1 & 0 \\
0 & e^{i\pi/4}
\end{matrix}
\right) = \left(
\begin{matrix}
1 & 0 \\
0 & \frac{1+i}{\sqrt{2}}
\end{matrix}
\right), \quad
T = \left(
\begin{matrix}
1 & 0 \\
0 & e^{-i\pi/4}
\end{matrix}
\right) = \left(
\begin{matrix}
1 & 0 \\
0 & \frac{1-i}{\sqrt{2}}
\end{matrix}
\right)
です。
制御NOTゲート
制御NOTゲートは、制御ビットが1のときだけ標的ビットを反転させます。標的ビットに対して、制御ビットと標的ビットの排他的論理和（XOR）を代入したと見なすこともできます。
CNOT (1,2) \ket{x} \ket{y} = \ket{x} \ket{y \oplus x}
= \ket{x} \ket{x+y \,\, {\rm mod} \,\, 2} = \ket{x} \ket{x+y-2xy}.
行列表示する場合、2×2行列で表現できます。
CNOT = \left(
\begin{matrix}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 0 & 1 \\
0 & 0 & 1 & 0 \\
\end{matrix}
\right) .
計算過程
それでは計算過程を追ってみましょう。
- $H(3)$
\ket{c_{1}} \ket{c_{2}} \ket{t} \xrightarrow{H(3)} \sum _{t^{\prime} = 0,1} (-1) ^{tt^{\prime}} \ket{c_{1}} \ket{c_{2}} \ket{t^{\prime}} \equiv \ket{\psi _{1}}.
- $CNOT(2,3)$
\ket{\psi _{1}} \xrightarrow{CNOT(2,3)}
\sum _{t^{\prime} = 0,1} (-1) ^{tt^{\prime}} \ket{c_{1}} \ket{c_{2}} \ket{c_{2} + t^{\prime} - 2c_{2}t^{\prime}} \equiv \ket{\psi _{2}}.
- $T^{\dagger} (3)$
\ket{\psi _{2}} \xrightarrow{T ^{\dagger}(3)}
\sum _{t^{\prime} = 0,1} (-1) ^{tt^{\prime}} e^{-i\pi (c_{2} + t^{\prime} - 2c_{2} t^{\prime})/4} \ket{c_{1}} \ket{c_{2}} \ket{c_{2} + t^{\prime} - 2c_{2}t^{\prime}} \equiv \ket{\psi _{3}}.
- $CNOT(1,3)$
\begin{align}
\ket{\psi _{3}} &\xrightarrow{CNOT(1,3)}
\sum _{t^{\prime} = 0,1} (-1) ^{tt^{\prime}} e^{-i\pi (c_{2} + t^{\prime} - 2c_{2} t^{\prime})/4}
\ket{c_{1}} \ket{c_{2}}
\ket{c_{1} + c_{2} + t^{\prime} - 2c_{2}t^{\prime} - 2c_{1}(c_{2} + t^{\prime} - 2c_{2}t^{\prime})} \\
&= \sum _{t^{\prime} = 0,1} (-1) ^{tt^{\prime}} e^{-i\pi (c_{2} + t^{\prime} - 2c_{2} t^{\prime})/4}
\ket{c_{1}} \ket{c_{2}}
\ket{c_{1} + c_{2} + t^{\prime} - 2\left( c_{1} c_{2} + c_{1}t^{\prime} + c_{2}t^{\prime} \right) + 4c_{1}c_{2}t^{\prime}} \\
&\equiv \ket{\psi _{4}} .
\end{align}
- $T(3)$
\begin{align}
\ket{\psi _{4}} &\xrightarrow{T(3)}
\sum _{t^{\prime} = 0,1} (-1) ^{tt^{\prime}} e^{-i\pi (c_{2} + t^{\prime} - 2c_{2} t^{\prime})/4}
e^{i\pi \left[
c_{1} + c_{2} + t^{\prime} - 2\left( c_{1} c_{2} + c_{1}t^{\prime} + c_{2}t^{\prime} \right) + 4c_{1}c_{2}t^{\prime}
\right]/4}
\ket{c_{1}} \ket{c_{2}}
\ket{c_{1} + c_{2} + t^{\prime} - 2\left( c_{1} c_{2} + c_{1}t^{\prime} + c_{2}t^{\prime} \right) + 4c_{1}c_{2}t^{\prime}} \\
&= \sum _{t^{\prime} = 0,1} (-1) ^{tt^{\prime}}
e^{-i\pi \left[ c_{1} - 2c_{1}\left( c_{2} + t^{\prime}\right) + 4c_{1} c_{2} t^{\prime} \right]/4}
\ket{c_{1}} \ket{c_{2}}
\ket{c_{1} + c_{2} + t^{\prime} - 2\left( c_{1} c_{2} + c_{1}t^{\prime} + c_{2}t^{\prime} \right) + 4c_{1}c_{2}t^{\prime}} \\
&\equiv \ket{\psi _{5}}.
\end{align}
- $CNOT(2,3)$
\begin{align}
\ket{\psi _{5}} &\xrightarrow{CNOT(2,3)}
\sum _{t^{\prime} = 0,1} (-1) ^{tt^{\prime}}
e^{-i\pi \left[ c_{1} - 2c_{1}\left( c_{2} + t^{\prime}\right) + 4c_{1} c_{2} t^{\prime} \right]/4}
\ket{c_{1}} \ket{c_{2}}
\ket{c_{2} + \left[ c_{1} + c_{2} + t^{\prime} - 2\left( c_{1} c_{2} + c_{1}t^{\prime} + c_{2}t^{\prime} \right) + 4c_{1}c_{2}t^{\prime} \right]
-2c_{2} \left[ c_{1} + c_{2} + t^{\prime} - 2\left( c_{1} c_{2} + c_{1}t^{\prime} + c_{2}t^{\prime} \right) + 4c_{1}c_{2}t^{\prime} \right]
} \\
&=
\sum _{t^{\prime} = 0,1} (-1) ^{tt^{\prime}}
e^{-i\pi \left[ c_{1} - 2c_{1}\left( c_{2} + t^{\prime}\right) + 4c_{1} c_{2} t^{\prime} \right]/4}
\ket{c_{1}} \ket{c_{2}}
\ket{c_{1} + t^{\prime} - 2c_{1} t^{\prime}} \\
&\equiv \ket{\psi _{6}}.
\end{align}
ただし、$c_{1}^{2} = c_{1}, \,\, c_{2}^{2} = c_{2}, \,\, {t^{\prime}} ^{2} = t^{\prime}$を使った。
- $T^{\dagger} (3)$
\begin{align}
\ket{\psi _{6}} &\xrightarrow{T^{\dagger} (3)}
\sum _{t^{\prime} = 0,1} (-1) ^{tt^{\prime}}
e^{-i\pi \left[ c_{1} - 2c_{1}\left( c_{2} + t^{\prime}\right) + 4c_{1} c_{2} t^{\prime} \right]/4}
e^{i\pi \left( c_{1} + t^{\prime} - 2c_{1}t^{\prime} \right)/4}
\ket{c_{1}} \ket{c_{2}}
\ket{c_{1} + t^{\prime} - 2c_{1} t^{\prime}} \\
&= \sum _{t^{\prime} = 0,1} (-1) ^{tt^{\prime}}
e^{i\pi \left( - t^{\prime} - 2c_{1}c_{2} + 4c_{1}c_{2}t^{\prime} \right)/4}
\ket{c_{1}} \ket{c_{2}}
\ket{c_{1} + t^{\prime} - 2c_{1} t^{\prime}} \\
&\equiv \ket{\psi _{7}}.
\end{align}
- $CNOT(1,3)$
\begin{align}
\ket{\psi _{7}} &\xrightarrow{CNOT(1,3)}
\sum _{t^{\prime} = 0,1} (-1) ^{tt^{\prime}}
e^{i\pi \left( - t^{\prime} - 2c_{1}c_{2} + 4c_{1}c_{2}t^{\prime} \right)/4}
\ket{c_{1}} \ket{c_{2}}
\ket{c_{1} + \left[ c_{1} + t^{\prime} - 2c_{1} t^{\prime} \right] - 2c_{1}\left[ c_{1} + t^{\prime} - 2c_{1} t^{\prime} \right]} \\
&= \sum _{t^{\prime} = 0,1} (-1) ^{tt^{\prime}}
e^{i\pi \left( - t^{\prime} - 2c_{1}c_{2} + 4c_{1}c_{2}t^{\prime} \right)/4}
\ket{c_{1}} \ket{c_{2}}
\ket{t^{\prime}} \\
&\equiv \ket{\psi _{8}}.
\end{align}
-
$T(2)T(3)$
異なる量子ビットへの演算のため、どちらを先に作用させても結果は同じです。
\begin{align}
\ket{\psi _{8}} &\xrightarrow{T(2)T(3)}
\sum _{t^{\prime} = 0,1} (-1) ^{tt^{\prime}}
e^{i\pi \left( - t^{\prime} - 2c_{1}c_{2} + 4c_{1}c_{2}t^{\prime} \right)/4}
e^{i\pi c_{2}/4}
e^{i\pi t^{\prime}/4}
\ket{c_{1}} \ket{c_{2}}
\ket{t^{\prime}} \\
&=
\sum _{t^{\prime} = 0,1} (-1) ^{tt^{\prime}}
e^{i\pi \left( c_{2} - 2c_{1}c_{2} + 4c_{1}c_{2}t^{\prime} \right)/4}
\ket{c_{1}} \ket{c_{2}}
\ket{t^{\prime}} \\
&\equiv \ket{\psi _{9}}.
\end{align}
- $CNOT(1,2)$
\begin{align}
\ket{\psi _{9}} &\xrightarrow{CNOT(1,2)}
\sum _{t^{\prime} = 0,1} (-1) ^{tt^{\prime}}
e^{i\pi \left( c_{2} - 2c_{1}c_{2} + 4c_{1}c_{2}t^{\prime} \right)/4}
\ket{c_{1}} \ket{c_{1} + c_{2} - 2c_{1}c_{2}}
\ket{t^{\prime}} \\
&\equiv \ket{\psi _{10}}.
\end{align}
- $H(3)$
\begin{align}
\ket{\psi _{10}} &\xrightarrow{H(3)}
\sum _{t^{\prime} = 0,1} \sum _{t^{\prime\prime} = 0,1}(-1) ^{tt^{\prime}} (-1) ^{t^{\prime} t^{\prime\prime}}
e^{i\pi \left( c_{2} - 2c_{1}c_{2} + 4c_{1}c_{2}t^{\prime} \right)/4}
\ket{c_{1}} \ket{c_{1} + c_{2} - 2c_{1}c_{2}}
\ket{t^{\prime \prime}} \\
&\equiv \ket{\psi _{11}}.
\end{align}
-
$T(1) T^{\dagger}(2)$
異なる量子ビットへの演算のため、どちらを先に作用させても結果は同じです。
\begin{align}
\ket{\psi _{11}} &\xrightarrow{T(1)T^{\dagger}(2)}
\sum _{t^{\prime} = 0,1} \sum _{t^{\prime\prime} = 0,1}(-1) ^{tt^{\prime}} (-1) ^{t^{\prime} t^{\prime\prime}}
e^{i\pi \left( c_{2} - 2c_{1}c_{2} + 4c_{1}c_{2}t^{\prime} \right)/4}
e^{i\pi c_{1}/4} e^{-i\pi \left( c_{1} + c_{2} - 2c_{1}c_{2}\right) /4}
\ket{c_{1}} \ket{c_{1} + c_{2} - 2c_{1}c_{2}}
\ket{t^{\prime \prime}} \\
&=
\sum _{t^{\prime} = 0,1} \sum _{t^{\prime\prime} = 0,1}(-1) ^{tt^{\prime}} (-1) ^{t^{\prime} t^{\prime\prime}}
e^{i\pi c_{1}c_{2}t^{\prime}}
\ket{c_{1}} \ket{c_{1} + c_{2} - 2c_{1}c_{2}}
\ket{t^{\prime \prime}} \\
&\equiv \ket{\psi _{12}}.
\end{align}
- $CNOT(1,2)$
\begin{align}
\ket{\psi _{12}} &\xrightarrow{CNOT(1,2)}
\sum _{t^{\prime} = 0,1} \sum _{t^{\prime\prime} = 0,1}(-1) ^{tt^{\prime}} (-1) ^{t^{\prime} t^{\prime\prime}}
e^{i\pi c_{1}c_{2}t^{\prime}}
\ket{c_{1}}
\ket{c_{1} + \left( c_{1} + c_{2} - 2c_{1}c_{2} \right) - 2c_{1}\left( c_{1} + c_{2} - 2c_{1}c_{2} \right) }
\ket{t^{\prime \prime}} \\
&=
\sum _{t^{\prime} = 0,1} \sum _{t^{\prime\prime} = 0,1}(-1) ^{tt^{\prime}} (-1) ^{t^{\prime} t^{\prime\prime}}
e^{i\pi c_{1}c_{2}t^{\prime}}
\ket{c_{1}}
\ket{c_{2}}
\ket{t^{\prime \prime}} \\
&\equiv \ket{\psi _{13}}
\end{align}
ここで、$e^{i2\pi k}=1$（ただし$k$は整数）を使って、
e^{i\pi c_{1}c_{2}t^{\prime}} = e^{i\pi c_{1}c_{2}t^{\prime}} e^{-i 2\pi c_{1}c_{2}tt^{\prime}}
とします。これを代入し、$e^{i\pi n} = \left( e^{i\pi} \right) ^{n} = (-1)^{n}$を使うと、
\begin{align}
\ket{\psi _{13}}
&=
\sum _{t^{\prime} = 0,1} \sum _{t^{\prime\prime} = 0,1}(-1) ^{tt^{\prime}} (-1) ^{t^{\prime} t^{\prime\prime}}
e^{i\pi c_{1}c_{2}t^{\prime}} e^{-i2\pi c_{1}c_{2}tt^{\prime}}
\ket{c_{1}}
\ket{c_{2}}
\ket{t^{\prime \prime}} \\
&= H(3) \sum _{t^{\prime} = 0,1} (-1) ^{tt^{\prime}}
e^{i\pi \left( c_{1}c_{2} -2c_{1}c_{2}t \right) t^{\prime} }
\ket{c_{1}}
\ket{c_{2}}
\ket{t^{\prime}} \\
&= H(3) \sum _{t^{\prime} = 0,1} (-1) ^{\left(t + c_{1}c_{2} -2c_{1}c_{2}t \right) t^{\prime}}
\ket{c_{1}}
\ket{c_{2}}
\ket{t^{\prime}} \\
&= H(3) H(3) \ket{c_{1}} \ket{c_{2}}
\ket{t+c_{1}c_{2} - 2c_{1}c_{2}t} \\
&= \ket{c_{1}} \ket{c_{2}}
\ket{t+c_{1}c_{2} - 2c_{1}c_{2}t} \quad \because H^{2} = I \\
&= \ket{c_{1}} \ket{c_{2}} \ket{t\oplus c_{1}c_{2}}
\end{align}
を得ます。したがって、上記計算により$H$, $T$, $T^{\dagger}$および制御NOTゲートの組み合わせにより、トフォリゲートを構成できることが確認できました。