『量子計算理論 量子コンピュータの原理』演習（第４章１節＆２節）

来るべき量子コンピュータ時代に備えて、『[量子計算理論 量子コンピュータの原理](https://www.amazon.co.jp/dp/4627854013/)』の輪読を始めました :muscle:

> 「人類がつくりうる究極の計算機は何だろうか？」
> ...
> 現在最も正しいと考えられている物理理論である量子論に基づく計算機が、その答えとなる。

という文章から始まるので、否が応でもテンション上がってしまいますね :raised_hands:
いくつか演習問題があるので解いていきます。間違ってたら、ごめんネ :pray: 

[『量子計算理論 量子コンピュータの原理』演習（第２章＆第３章）](https://qiita.com/piyo7/items/0e86f5054494876e63d3)
[『量子計算理論 量子コンピュータの原理』演習（第４章４節）混合状態](https://qiita.com/piyo7/items/6397a289b3cf5ef120e9)

# 4　量子計算（発展）

# 4.1　量子ゲートの例と量子回路

> パウリ演算子は以下の性質を満たすことを確認せよ。
> $X^2 = Y^2 = Z^2 = I$

```math
\begin{align}
X^2 = \begin{pmatrix}
0 & 1 \\
1 & 0 \\
\end{pmatrix}
\begin{pmatrix}
0 & 1 \\
1 & 0 \\
\end{pmatrix} &=
\begin{pmatrix}
1 & 0 \\
0 & 1 \\
\end{pmatrix} \\
Y^2 = \begin{pmatrix}
0 & -i \\
i & 0 \\
\end{pmatrix}
\begin{pmatrix}
0 & -i \\
i & 0 \\
\end{pmatrix} &=
\begin{pmatrix}
1 & 0 \\
0 & 1 \\
\end{pmatrix} \\
Z^2 = \begin{pmatrix}
1 & 0 \\
0 & -1 \\
\end{pmatrix}
\begin{pmatrix}
1 & 0 \\
0 & -1 \\
\end{pmatrix} &=
\begin{pmatrix}
1 & 0 \\
0 & 1 \\
\end{pmatrix} \\
I &=
\begin{pmatrix}
1 & 0 \\
0 & 1 \\
\end{pmatrix}
\end{align}
```

> $XY = -YX = iZ$

```math
\begin{align}
XY =
\begin{pmatrix}
0 & 1 \\
1 & 0 \\
\end{pmatrix}
\begin{pmatrix}
0 & -i \\
i & 0 \\
\end{pmatrix} &=
\begin{pmatrix}
i & 0 \\
0 & -i \\
\end{pmatrix} \\
-YX = -
\begin{pmatrix}
0 & -i \\
i & 0 \\
\end{pmatrix}
\begin{pmatrix}
0 & 1 \\
1 & 0 \\
\end{pmatrix} &=
\begin{pmatrix}
i & 0 \\
0 & -i \\
\end{pmatrix} \\
iZ &=
\begin{pmatrix}
i & 0 \\
0 & -i \\
\end{pmatrix}
\end{align}
```

> $YZ = -ZY = iX$

```math
\begin{align}
YZ =
\begin{pmatrix}
0 & -i \\
i & 0 \\
\end{pmatrix}
\begin{pmatrix}
1 & 0 \\
0 & -1 \\
\end{pmatrix} &=
\begin{pmatrix}
0 & i \\
i & 0 \\
\end{pmatrix} \\
-ZY =
\begin{pmatrix}
1 & 0 \\
0 & -1 \\
\end{pmatrix}
\begin{pmatrix}
0 & -i \\
i & 0 \\
\end{pmatrix} &=
\begin{pmatrix}
0 & i \\
i & 0 \\
\end{pmatrix} \\
iX &=
\begin{pmatrix}
0 & i \\
i & 0 \\
\end{pmatrix}
\end{align}
```

> $ZX = -XZ = iY$


```math
\begin{align}
ZX =
\begin{pmatrix}
1 & 0 \\
0 & -1 \\
\end{pmatrix}
\begin{pmatrix}
0 & 1 \\
1 & 0 \\
\end{pmatrix} &=
\begin{pmatrix}
0 & 1 \\
-1 & 0 \\
\end{pmatrix} \\
-XZ = -
\begin{pmatrix}
0 & 1 \\
1 & 0 \\
\end{pmatrix}
\begin{pmatrix}
1 & 0 \\
0 & -1 \\
\end{pmatrix} &=
\begin{pmatrix}
0 & 1 \\
-1 & 0 \\
\end{pmatrix} \\
iY &=
\begin{pmatrix}
0 & 1 \\
-1 & 0 \\
\end{pmatrix}
\end{align}
```

> また、パウリ演算子の固有値、固有ベクトルを求めよ。

```math
\begin{align}
X
\begin{pmatrix}
1 \\
1 \\
\end{pmatrix} &=
1
\begin{pmatrix}
1 \\
1 \\
\end{pmatrix} \\
X
\begin{pmatrix}
1 \\
-1 \\
\end{pmatrix} &=
-1
\begin{pmatrix}
1 \\
-1 \\
\end{pmatrix} \\
Y
\begin{pmatrix}
1 \\
i \\
\end{pmatrix} &=
1
\begin{pmatrix}
1 \\
i \\
\end{pmatrix} \\
Y
\begin{pmatrix}
1 \\
-i \\
\end{pmatrix} &=
-1
\begin{pmatrix}
1 \\
-i \\
\end{pmatrix} \\
Z
\begin{pmatrix}
1 \\
0 \\
\end{pmatrix} &=
1
\begin{pmatrix}
1 \\
0 \\
\end{pmatrix} \\
Z
\begin{pmatrix}
0 \\
1 \\
\end{pmatrix} &=
-1
\begin{pmatrix}
0 \\
1 \\
\end{pmatrix}
\end{align}
```

> さらに、n量子ビットパウリ演算子は掛け算について群をなすことを確かめよ。

1量子ビットパウリ演算子が群をなせば、そのテンソル積であるn量子ビットパウリ演算子も群をなす。
1量子ビットパウリ演算子が群であることは、次のように確かめられる。

- 演算が閉じていること：上記の計算式より
- 結合法則： 行列の結合法則より
- 単位元： $I$
- 逆元： $X, Y, Z$ の逆元は自身

```math
\newcommand{\bra}[1]{\left\langle #1 \right|}
\newcommand{\ket}[1]{\left| #1 \right\rangle}
\newcommand{\bracket}[2]{\left\langle #1 \middle| #2 \right\rangle}
\newcommand{\braccket}[3]{\left\langle #1 \middle| #2 \middle| #3 \right\rangle}
```

> CZゲートは、コントロールとターゲットを入れ替えても等価であることを示せ。つまり、
> $\ket{0}\bra{0} \otimes I + \ket{1}\bra{1} \otimes Z = I \otimes \ket{0}\bra{0} + Z \otimes \ket{1}\bra{1}$
> が成り立つことを示せ。

```math
\begin{align}
&\ket{0}\bra{0} \otimes I + \ket{1}\bra{1} \otimes Z \\
= \ &\ket{0}\bra{0} \otimes ( \ \ket{0}\bra{0} + \ket{1}\bra{1} \ ) \ + \ \ket{1}\bra{1} \otimes ( \ \ket{0}\bra{0} - \ket{1}\bra{1} \ ) \\
= \ &( \ \ket{0}\bra{0} + \ket{1}\bra{1} \ ) \otimes  \ket{0}\bra{0} \ + \ ( \ \ket{0}\bra{0} - \ket{1}\bra{1} \ ) \otimes  \ket{1}\bra{1} \\
= \ &I \otimes \ket{0}\bra{0} + Z \otimes \ket{1}\bra{1}
\end{align}
```

> また、図4.1(f)のようにCXゲートをコントロールとターゲットを入れ替えて3回作用させると、量子ビットを交換するゲート $\ket{\psi} \otimes \ket{\phi} \rightarrow \ket{\phi} \otimes \ket{\psi}$ になってることを示せ。

```math
\begin{align}
( \ &I \otimes \ket{0}\bra{0} + X \otimes \ket{1}\bra{1} \ ) \\
( \ &\ket{0}\bra{0} \otimes I + \ket{1}\bra{1} \otimes X \ ) \\
= \ &( \ I \ket{0}\bra{0} \otimes \ket{0}\bra{0} I \ ) \ + \ ( \ X \ket{0}\bra{0} \otimes \ket{1}\bra{1} I \ ) \ + \ ( \ I \ket{1}\bra{1} \otimes \ket{0}\bra{0} X \ ) \ + \ ( \ X \ket{1}\bra{1} \otimes \ket{1}\bra{1} X \ ) \\
= \ &\ket{0}\bra{0} \otimes \ket{0}\bra{0} + \ket{1}\bra{0} \otimes \ket{1}\bra{1} + \ket{1}\bra{1} \otimes \ket{0}\bra{1} + \ket{0}\bra{1} \otimes \ket{1}\bra{0} \\
\\
( \ &\ket{0}\bra{0} \otimes I + \ket{1}\bra{1} \otimes X \ ) \\
( \ &\ket{0}\bra{0} \otimes \ket{0}\bra{0} + \ket{1}\bra{0} \otimes \ket{1}\bra{1} + \ket{1}\bra{1} \otimes \ket{0}\bra{1} + \ket{0}\bra{1} \otimes \ket{1}\bra{0} \ ) \\
= \ &\ket{0}\bra{0} \otimes \ket{0}\bra{0} + \ket{1}\bra{0} \otimes \ket{0}\bra{1} + \ket{1}\bra{1} \otimes \ket{1}\bra{1} + \ket{1}\bra{1} \otimes \ket{1}\bra{0} \\
= \ &\ket{00}\bra{00} + \ket{10}\bra{01} + \ket{11}\bra{11} + \ket{01}\bra{10}
\end{align}
```

> CCZゲートは、図4.2の回路と等価であることを確認せよ。

```math
\begin{align}
( \ &\ket{0}\bra{0} \otimes I \otimes I + \ket{1}\bra{1} \otimes X \otimes I \ ) \\
( \ &\ket{0}\bra{0} \otimes I \otimes I + \ket{1}\bra{1} \otimes I \otimes R_{\pi/2} \ ) \\
= \ &\ket{0}\bra{0} \otimes I \otimes I + \ket{1}\bra{1} \otimes X \otimes R_{\pi/2} \\
\\
( \ &I \otimes \ket{0}\bra{0} \otimes I + I \otimes \ket{1}\bra{1} \otimes R_{\pi/2}^\dagger \ ) \\
( \ &\ket{0}\bra{0} \otimes I \otimes I + \ket{1}\bra{1} \otimes X \otimes R_{\pi/2} \ ) \\
= \ &\ket{0}\bra{0} \otimes \ket{0}\bra{0} \otimes I + \ket{0}\bra{0} \otimes \ket{1}\bra{1} \otimes R_{\pi/2}^\dagger + \ket{1}\bra{1} \otimes \ket{0}\bra{1} \otimes  R_{\pi/2} + \ket{1}\bra{1} \otimes \ket{1}\bra{0} \otimes R_{\pi/2}^\dagger R_{\pi/2} \\
= \ &\ket{0}\bra{0} \otimes \ket{0}\bra{0} \otimes I + \ket{0}\bra{0} \otimes \ket{1}\bra{1} \otimes R_{\pi/2}^\dagger + \ket{1}\bra{1} \otimes \ket{0}\bra{1} \otimes  R_{\pi/2} + \ket{1}\bra{1} \otimes \ket{1}\bra{0} \otimes I \\
\\
( \ &\ket{0}\bra{0} \otimes I \otimes I + \ket{1}\bra{1} \otimes X \otimes I \ ) \\
( \ &\ket{0}\bra{0} \otimes \ket{0}\bra{0} \otimes I + \ket{0}\bra{0} \otimes \ket{1}\bra{1} \otimes R_{\pi/2}^\dagger + \ket{1}\bra{1} \otimes \ket{0}\bra{1} \otimes  R_{\pi/2} + \ket{1}\bra{1} \otimes \ket{1}\bra{0} \otimes I \ ) \\
= \ &\ket{0}\bra{0} \otimes \ket{0}\bra{0} \otimes I + \ket{0}\bra{0} \otimes \ket{1}\bra{1} \otimes R_{\pi/2}^\dagger + \ket{1}\bra{1} \otimes \ket{1}\bra{1} \otimes R_{\pi/2} + \ket{1}\bra{1} \otimes \ket{0}\bra{0} \otimes I \\
\\
( \ &I \otimes \ket{0}\bra{0} \otimes I + I \otimes \ket{1}\bra{1} \otimes R_{\pi/2} \ ) \\
( \ &\ket{0}\bra{0} \otimes \ket{0}\bra{0} \otimes I + \ket{0}\bra{0} \otimes \ket{1}\bra{1} \otimes R_{\pi/2}^\dagger + \ket{1}\bra{1} \otimes \ket{1}\bra{1} \otimes R_{\pi/2} + \ket{1}\bra{1} \otimes \ket{0}\bra{0} \otimes I \ ) \\
= \ &\ket{0}\bra{0} \otimes \ket{0}\bra{0} \otimes I + \ket{0}\bra{0} \otimes \ket{1}\bra{1} \otimes R_{\pi/2} R_{\pi/2}^\dagger + \ket{1}\bra{1} \otimes \ket{1}\bra{1} \otimes R_{\pi/2} R_{\pi/2} + \ket{1}\bra{1} \otimes \ket{0}\bra{0} \otimes I \\
= \ &\ket{0}\bra{0} \otimes \ket{0}\bra{0} \otimes I + \ket{0}\bra{0} \otimes \ket{1}\bra{1} \otimes I + \ket{1}\bra{1} \otimes \ket{1}\bra{1} \otimes Z + \ket{1}\bra{1} \otimes \ket{0}\bra{0} \otimes I \\
= \ &( \ I \otimes I - \ket{11} \bra{11} \ ) \otimes I + \ket{11} \bra{11} \otimes Z
\end{align}
```

> 図4.3の回路において、一番上の量子ビットを測定したときに0が得られる確率は
> $\frac{2 + \braccket{\psi}{U}{\psi} + \braccket{\psi}{U^\dagger}{\psi}}{4}$
> であることを確認せよ。ただし、Uは任意のユニタリ演算子である。このような回路はアダマールテスト（Hadamard test）とよばれ、よく使われる。

```math
\begin{align}
&( \ H \otimes I \ ) \ \ ( \ \ket{0}\bra{0} \otimes I + \ket{1}\bra{1} \otimes U \ ) \ \ ( \ H \otimes I \ ) \ \ ( \ \ket{0} \otimes \ket{\psi} \ ) \\
= \ &( \ H \otimes I \ ) \ \ ( \ \ket{0}\bra{0} \otimes I + \ket{1}\bra{1} \otimes U \ ) \ \ ( \ \frac{1}{\sqrt{2}} \ket{0} \otimes \ket{\psi} + \frac{1}{\sqrt{2}} \ket{1} \otimes \ket{\psi} \ ) \\
= \ &( \ H \otimes I \ ) \ \ ( \ \frac{1}{\sqrt{2}} \ket{0} \otimes \ket{\psi} + \frac{1}{\sqrt{2}} \ket{1} \otimes U \ket{\psi} \ ) \\
= \ &\frac{1}{2} \ket{0} \otimes \ket{\psi} + \frac{1}{2} \ket{1} \otimes \ket{\psi} + \frac{1}{2} \ket{0} \otimes U \ket{\psi} - \frac{1}{2} \ket{1} \otimes U \ket{\psi} \\
\end{align}
```

一番上の量子ビットを測定したときに0が得られる確率は、

```math
\begin{align}
&( \ \frac{1}{2} \bra{0} \otimes \bra{\psi} + \frac{1}{2} \bra{1} \otimes \bra{\psi} + \frac{1}{2} \bra{0} \otimes \bra{\psi} U^\dagger - \frac{1}{2} \bra{1} \otimes \bra{\psi} U^\dagger \ ) \\
&( \ \ket{0}\bra{0} \otimes I \ ) \\
&( \ \frac{1}{2} \ket{0} \otimes \ket{\psi} + \frac{1}{2} \ket{1} \otimes \ket{\psi} + \frac{1}{2} \ket{0} \otimes U \ket{\psi} - \frac{1}{2} \ket{1} \otimes U \ket{\psi} \ ) \\
= \ &( \ \frac{1}{2} \bra{0} \otimes \bra{\psi} + \frac{1}{2} \bra{0} \otimes \bra{\psi} U^\dagger) \ \
( \ \frac{1}{2} \ket{0} \otimes \ket{\psi} + \frac{1}{2} \ket{0} \otimes U \ket{\psi} \ ) \\
= \ &\frac{1}{4} \bracket{0}{0} \bracket{\psi}{\psi} + \frac{1}{4} \bracket{0}{0} \braccket{\psi}{U^\dagger}{\psi} + \frac{1}{4} \bracket{0}{0} \braccket{\psi}{U}{\psi} + \frac{1}{4} \bracket{0}{0} \braccket{\psi}{U^\dagger U}{\psi} \\
= \ &\frac{1}{4} + \frac{1}{4} \braccket{\psi}{U^\dagger}{\psi} + \frac{1}{4} \braccket{\psi}{U}{\psi} + \frac{1}{4} \\
= \ &\frac{2 + \braccket{\psi}{U}{\psi} + \braccket{\psi}{U^\dagger}{\psi}}{4}
\end{align}
```

# 4.2　ユニバーサルな量子ゲートセット

> 複素係数表示における $\Lambda(R_{\pi/2})$ は、実係数表示において
> $T(I \otimes I \otimes H)T(I \otimes I \otimes H)$
> を作用させることによりシミュレートできることを示せ。

```math
\begin{align}
\Lambda(R_{\pi/2}) \ket{\phi}
&= ( \ \ket{0} \bra{0} \otimes I \ + \ \ket{1} \bra{1}  \otimes ( \ \ket{0} \bra{0} + i \ket{1} \bra{1} \ ) \ ) \ \sum_{z \in \{0, 1\}^2} c_z \ket{z} \\
&= \left( \sum_{z \in \{0, 1\}^2  \setminus \{11\}} c_z \ket{z} \right) + i c_{11} \ket{11} \\
&= \left( \sum_{z \in \{0, 1\}^2  \setminus \{11\}} (\alpha_z + i \beta_z) \ket{z} \right) - \beta_{11} \ket{11} + i \alpha_{11} \ket{11} \\
\end{align}
```

これを実係数表示をすると

```math
\left( \sum_{z \in \{0, 1\}^2 \setminus \{11\}} \alpha_z \ket{z} \ket{0} + \beta_z \ket{z} \ket{1} \right) - \beta_{11} \ket{11} \ket{0} + \alpha_{11} \ket{11} \ket{1}
```

また、

```math
\begin{align}
T(I \otimes I \otimes H)
&= ( \ ( \ I \otimes I - \ket{11} \bra{11} \ ) \otimes I + \ket{11} \bra{11} \otimes X \ ) \ ( \ I \otimes I \otimes H \ ) \\
&= ( \ I \otimes I - \ket{11} \bra{11} \ ) \otimes H + \ket{11} \bra{11} \otimes X H
\end{align}
```

よって、

```math
\begin{align}
T(I \otimes I \otimes H)T(I \otimes I \otimes H)
&= ( \ I \otimes I - \ket{11} \bra{11} \ ) \otimes H H + \ket{11} \bra{11} \otimes X H X H \\
&= ( \ I \otimes I - \ket{11} \bra{11} \ ) \otimes I + \ket{11} \bra{11} \otimes
\begin{pmatrix}
0 & -1 \\
1 & 0 \\
\end{pmatrix}

\end{align}
```

すなわち、

```math
\begin{align}
&T(I \otimes I \otimes H)T(I \otimes I \otimes H) \ket{\tilde{\phi}} \\
= \ &\left( ( \ I \otimes I - \ket{11} \bra{11} \ ) \otimes I + \ket{11} \bra{11} \otimes
\begin{pmatrix}
0 & -1 \\
1 & 0 \\
\end{pmatrix}
\right) \left( \sum_{z \in \{0, 1\}^2} \alpha_z \ket{z} \ket{0} + \beta_z \ket{z} \ket{1} \right) \\
= \ &\left( \sum_{z \in \{0, 1\}^2 \setminus \{11\}} \alpha_z \ket{z} \otimes I \ket{0} + \beta_z \ket{z} \otimes I \ket{1} \right) + \left( \sum_{z \in \{11\}} \alpha_z \ket{z} \otimes 
\begin{pmatrix}
0 & -1 \\
1 & 0 \\
\end{pmatrix}
\ket{0} + \beta_z \ket{z} \otimes 
\begin{pmatrix}
0 & -1 \\
1 & 0 \\
\end{pmatrix}
\ket{1} \right) \\
= \ &\left( \sum_{z \in \{0, 1\}^2 \setminus \{11\}} \alpha_z \ket{z} \ket{0} + \beta_z \ket{z} \ket{1} \right) - \beta_{11} \ket{11} \ket{0} + \alpha_{11} \ket{11} \ket{1}
\end{align}
```