トフォリゲートが4種類のゲートで構成できることを手計算で確認する

量子ゲートを作用させて計算する過程を順番に見ていくだけの記事です。以前投稿した[制御トフォリゲートの構成](https://qiita.com/farcpan/items/9ccc300df7e6a3eadbfa)の補足記事という位置づけです。

$$
\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量子ビットゲートで以下の演算を実現します。

```math
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）の組み合わせで実現できると記述しました。

![toffoli.png](https://qiita-image-store.s3.amazonaws.com/0/152794/8303f4a1-0c9e-b924-bdf1-ebb109c697f0.png)

前述の記事内では上記結果を無条件で認めて利用しましたが、本記事で計算過程を追いながら確かめてみたいと思います。

# 確認
実際に確認してみたいと思います。

## 準備
計算過程を追う上で必要な内容をざっくりと押さえておきます。

### 記法
多量子ビット状態に対する演算は、どの量子ビットが演算対象であるかを明示する必要があります。まず、量子ビットに対して以下のようにインデックスを付与します。

```math
\ket{x} _{1} \ket{y} _{2} \ket{z} _{3} \equiv \ket{x} \ket{y} \ket{z}. 
```
以降はインデックスを省略しますが、左から順にインデックスを付与したことを覚えておいてください。次に、各量子ゲートがどの量子ビットに作用しているかを示すために、ゲート演算子に対してもインデックスを付与します。まずは1量子ビットゲート演算子については、

```math
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$を指定して、

```math
\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ゲートを例にすると、

```math
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$軸方向の固有状態の重ね合わせを作ります。

```math
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}}.  
```

行列表示すると、

```math
H = \frac{1}{\sqrt{2}} \left(
\begin{matrix}
1 & 1 \\
1 & -1
\end{matrix}
\right)
```
です。$H$はユニタリ演算子で、なおかつ要素が実数ですので、$H^{-1} = H^{\dagger} = H$が成立します。すなわち

```math
H^{2} = I
```
です。

#### Tゲート
$T$および$T^{\dagger}$は、位相ゲート$P_{\phi}$の一種です。具体的には、

```math
T = P_{\phi = \pi/4}, \quad T^{\dagger} = P_{\phi = -\pi / 4}
```
です。$P_{\phi}$は位相を$\phi$だけずらすゲート演算子です。

```math
P_{\phi} \ket{z} = e^{i \phi} \ket{z}. 
```
したがって、

```math
\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}$を行列表示すると、

```math
P_{\phi} = \left(
\begin{matrix}
1 & 0 \\
0 & e^{i\phi}
\end{matrix}
\right)
```
ですので、

```math
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）を代入したと見なすこともできます。

```math
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行列で表現できます。

```math
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)$

```math
\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)$

```math
\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)$

```math
\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)$

```math
\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)$

```math
\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)$

```math
\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)$

```math
\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)$

```math
\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)$

    異なる量子ビットへの演算のため、どちらを先に作用させても結果は同じです。

```math
\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)$

```math
\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)$

```math
\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)$

    異なる量子ビットへの演算のため、どちらを先に作用させても結果は同じです。

```math
\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)$

```math
\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$は整数）を使って、

```math
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}$を使うと、

```math
\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ゲートの組み合わせにより、トフォリゲートを構成できることが確認できました。