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

来るべき量子コンピュータ時代に備えて、『量子計算理論 量子コンピュータの原理』の輪読を始めました

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

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

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

2　古典計算：ベクトルと演算子による表現

2.1　決定的古典計算

チューリングマシンで実際に足し算と掛け算をしてみよ。

http://turingmaschine.klickagent.ch/einband/#6_+_7
http://turingmaschine.klickagent.ch/einband/#6_*_7

チューリングマシンのテープのビット列が01011、ヘッドの位置が3、内部状態が15であるような状態は、どうやってビット列で表すことができるか？

ゲーデル数 $2^{11(= 01011)} \times 3^3 \times 5^{15}$ を2進数で表す。

追記：輪読でアルファ符号、ガンマ符号、デルタ符号を教えてもらいました。

チューリングマシンが $1 + 1$ を計算する様子を、計算機の状態を表すビット列の変化のシーケンスで記述せよ。

テープ	内部状態	ゲーデル数	ビット列
$\underline{1}010$	0	$2^{10} \times 3^0 \times 5^{0}$	$0000000000000010000000000$
$1\underline{0}10$	1	$2^{10} \times 3^1 \times 5^{1}$	$0000000000011110000000000$
$11\underline{1}0$	2	$2^{14} \times 3^2 \times 5^{2}$	$0001110000100000000000000$
$111\underline{0}$	2	$2^{14} \times 3^2 \times 5^{3}$	$1000110010100000000000000$
$11\underline{1}0$	3	$2^{14} \times 3^3 \times 5^{2}$	$0101010001100000000000000$
$1\underline{1}00$	4	$2^{12} \times 3^4 \times 5^{1}$	$0000110010101000000000000$

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

$X\ket{0} = \ket{1}, X\ket{1} = \ket{0}$ となることを確認せよ。

X\ket{0} = 
\begin{pmatrix}
0 & 1 \\
1 & 0 \\
\end{pmatrix}
\begin{pmatrix}
1 \\
0 \\
\end{pmatrix} = 
\begin{pmatrix}
0 \\
1 \\
\end{pmatrix} =
\ket{1}

X\ket{1} = 
\begin{pmatrix}
0 & 1 \\
1 & 0 \\
\end{pmatrix}
\begin{pmatrix}
0 \\
1 \\
\end{pmatrix} = 
\begin{pmatrix}
1 \\
0 \\
\end{pmatrix} =
\ket{0}

任意の $a, b, c \in \lbrace 0, 1 \rbrace$ に対し、
$T\ket{a, b, c} = \ket{a, b, c \oplus ab}$
となっていることを確認せよ。

\begin{align}
T\ket{a, b, c}
&= ( \ ( \ I \otimes I - \ket{11}\bra{11} \ ) \otimes I \ + \ \ket{11}\bra{11} \otimes X \ ) \ \ket{a, b, c} \\
&= \ket{a, b, c} - \ket{11}\bracket{11}{a, b} \otimes \ket{c} + \ket{11}\bracket{11}{a, b} \otimes X \ket{c} \\
&= \begin{cases}
\ket{11} \otimes X \ket{c} & (a, b= 1) \\
\ket{a, b, c} & ({\rm otherwise})
\end{cases} \\
 &= \ket{a, b, c \oplus ab}
\end{align}

2.2 確率的古典計算

1. 今日晴れなら、明日晴れる確率は1/2、曇りの確率は1/2
2. 今日曇りなら、明日晴れる確率は1/2、雨の確率は1/2
3. 今日雨なら、明日曇りの確率は1/4、雨の確率は3/4 を表す3x3の確率行列を書け。

\begin{pmatrix}
1/2 & 1/2 & 0   \\
1/2 & 0   & 1/4 \\
0   & 1/2 & 3/4 \\
\end{pmatrix}

確率的古典計算機のある状態を表す状態ベクトルを
$\ket{\phi} \equiv \sum_{z \in {\lbrace 0, 1 \rbrace}^n} c_z \ket{z}$
と書いたとき、これは「確率 $c_z$ で状態 $\ket{z}$ にある」という意味なので、 $c_z \geq 0$ かつ $\sum_{z \in {\lbrace 0, 1 \rbrace}^n} c_z = 1$ を満たさなければならないのであった。この状態ベクトル $\ket{\phi}$ に、上記の演算子 $S(\lbrace p_{z', z} \rbrace)$ を作用させてつくられた新しい状態ベクトル $S(\lbrace p_{z', z} \rbrace) \ket{\phi}$ も、この条件を必ず満たすことを示せ。

\begin{align}
S(\lbrace p_{z', z} \rbrace) \ket{\phi}
&= \left( \sum_{z \in {\lbrace 0, 1 \rbrace}^n} \sum_{z' \in {\lbrace 0, 1 \rbrace}^n} p_{z', z} \ket{z'} \bra{z} \right) \left( \sum_{z \in {\lbrace 0, 1 \rbrace}^n} c_z \ket{z} \right) \\
&= \sum_{z' \in {\lbrace 0, 1 \rbrace}^n} \left( \sum_{\alpha \in {\lbrace 0, 1 \rbrace}^n} \sum_{\beta \in {\lbrace 0, 1 \rbrace}^n} p_{z', \alpha} c_{\beta} \ket{z'} \bracket{\alpha}{\beta} \right) \\
&= \sum_{z' \in {\lbrace 0, 1 \rbrace}^n} \left( \sum_{z \in {\lbrace 0, 1 \rbrace}^n} p_{z', z} c_z \right) \ket{z'}
\end{align}

確率ベクトルとしての性質を確認すると、

\begin{align}
\sum_{z' \in {\lbrace 0, 1 \rbrace}^n} \left( \sum_{z \in {\lbrace 0, 1 \rbrace}^n} p_{z', z} c_z \right)
&= \sum_{z \in {\lbrace 0, 1 \rbrace}^n} \left( \sum_{z' \in {\lbrace 0, 1 \rbrace}^n} p_{z', z} \right) c_z \\
&= \sum_{z \in {\lbrace 0, 1 \rbrace}^n} c_z \\
&= 1
\end{align}

3　量子計算（基礎）

3.1　古典計算の拡張としての量子計算

$\lbrace p_{z', z} \rbrace_{z, z' \in \lbrace 0, 1 \rbrace^n}$ が式(3.1)を満たすなら、演算子を作用させても状態ベクトルの条件 $\sum_{z \in \lbrace 0, 1 \rbrace^n} |c_z|^2 = 1$ が保存されることを示せ。

\begin{align}
&\left( \sum_{z \in {\lbrace 0, 1 \rbrace}^n} \sum_{z' \in {\lbrace 0, 1 \rbrace}^n} p_{z', z} \ket{z'} \bra{z} \right) \left( \sum_{z \in {\lbrace 0, 1 \rbrace}^n} c_z \ket{z} \right) \\
= \ &\sum_{z' \in {\lbrace 0, 1 \rbrace}^n} \left( \sum_{\alpha \in {\lbrace 0, 1 \rbrace}^n} \sum_{\beta \in {\lbrace 0, 1 \rbrace}^n} p_{z', \alpha} c_{\beta} \ket{z'} \bracket{\alpha}{\beta} \right) \\
= \ &\sum_{z' \in {\lbrace 0, 1 \rbrace}^n} \left( \sum_{z \in {\lbrace 0, 1 \rbrace}^n} p_{z', z} c_z \right) \ket{z'}
\end{align}

量子ベクトルとしての性質を確認すると、

\begin{align}
\sum_{z' \in {\lbrace 0, 1 \rbrace}^n} \left| \sum_{z \in {\lbrace 0, 1 \rbrace}^n} p_{z', z} c_z \right|^2
&= \sum_{\alpha \in \lbrace 0, 1 \rbrace^n} \sum_{\beta \in \lbrace 0, 1 \rbrace^n} \left( \sum_{z' \in \lbrace 0, 1 \rbrace} p_{z', \alpha}^* p_{z', \beta} \right) c_\alpha^* c_\beta \\
&= \sum_{\alpha \in \lbrace 0, 1 \rbrace^n} \sum_{\beta \in \lbrace 0, 1 \rbrace^n} \delta_{\alpha, \beta} c_\alpha^* c_\beta \\
&= \sum_{z \in \lbrace 0, 1 \rbrace^n} c_z^* c_z \\
&= \sum_{z \in \lbrace 0, 1 \rbrace^n} |c_z|^2 \\
&= 1
\end{align}

以下が成り立つことを確認せよ。
$\bra{\psi} \ ( \ \ket{z} \bra{z} \ ) \ \ket{\psi} = |c_z|^2$

\begin{align}
\bra{\psi} \ ( \ \ket{z} \bra{z} \ ) \ \ket{\psi}
&= \left( \sum_{z' \in {\lbrace 0, 1 \rbrace}^n} c_{z'}^* \bra{z'} \right) ( \ \ket{z} \bra{z} \ ) \left( \sum_{z' \in {\lbrace 0, 1 \rbrace}^n} c_{z'} \ket{z'} \right) \\
&= \left( \sum_{z' \in {\lbrace 0, 1 \rbrace}^n} c_{z'}^* \bracket{{z'}}{z} \right) \left( \sum_{z' \in {\lbrace 0, 1 \rbrace}^n} c_{z'} \bracket{z}{{z'}} \right) \\
&= c_z^* c_z \\
&= |c_z|^2
\end{align}

$\frac{\ket{z} \bracket{z}{\psi}}{\bracket{z}{\psi}} = \ket{z}$

\begin{align}
\frac{\ket{z} \bracket{z}{\psi}}{\bracket{z}{\psi}}
&= \frac{\ket{z} \bra{z} \ ( \ \sum_{z' \in {\lbrace 0, 1 \rbrace}^n} c_{z'} \ket{z'} \ )}{\bra{z} \ ( \ \sum_{z' \in {\lbrace 0, 1 \rbrace}^n} c_{z'} \ket{z'} \ )} \\
&= \frac{\ket{z} \ ( \ \sum_{z' \in {\lbrace 0, 1 \rbrace}^n} c_{z'} \bracket{z}{z'} \ )}{(\sum_{z' \in {\lbrace 0, 1 \rbrace}^n} c_{z'} \bracket{z}{{z'}})} \\
&= \frac{\ket{z} c_z}{c_z} \\
&= \ket{z}
\end{align}

$\bra{\psi} \ ( \ \ket{1} \bra{1} \otimes I^{\otimes^{n - 1}} \ ) \ \ket{\psi} = \sum_{z:z_1 = 1} |c_z|^2$

\begin{align}
\bra{\psi} \ ( \ \ket{1} \bra{1} \otimes I^{\otimes^{n - 1}} \ ) \ \ket{\psi}
&= \left( \sum_{z \in {\lbrace 0, 1 \rbrace}^n} c_{z}^* \bra{z} \right) ( \ \ket{1} \bra{1} \otimes I^{\otimes^{n - 1}} \ ) \left( \sum_{z \in {\lbrace 0, 1 \rbrace}^n} c_{z} \ket{z} \right) \\
&= \left( \sum_{z \in {\lbrace 0, 1 \rbrace}^n} c_{z}^* \bra{z} \right) \left( \sum_{y \in {\lbrace 0, 1 \rbrace}^{n-1}} c_{1y} \ket{1y} \right) \\
&= \sum_{z \in {\lbrace 0, 1 \rbrace}^n} \sum_{y \in {\lbrace 0, 1 \rbrace}^{n-1}} c_{z}^* c_{1y} \bracket{z}{1y} \\
&= \sum_{y \in {\lbrace 0, 1 \rbrace}^{n-1}} c_{1y}^* c_{1y} \\
&= \sum_{y \in {\lbrace 0, 1 \rbrace}^{n-1}} |c_{1y}|^2 \\
&= \sum_{z:z_1 = 1} |c_z|^2
\end{align}

$\frac{( \ \ket{1} \bra{1} \otimes I^{\otimes^{n - 1}} \ ) \ \ket{\psi}}{\sqrt{\bra{\psi} \ ( \ \ket{1} \bra{1} \otimes I^{\otimes^{n - 1}} \ ) \ \ket{\psi}}} = \frac{\sum_{z:z_1 = 1} c_z \ket{z}}{\sqrt{\sum_{z:z_1 = 1} |c_z|^2}}$

\begin{align}
\frac{( \ \ket{1} \bra{1} \otimes I^{\otimes^{n - 1}} \ ) \ \ket{\psi}}{\sqrt{\bra{\psi} \ ( \ \ket{1} \bra{1} \otimes I^{\otimes^{n - 1}} \ ) \ \ket{\psi}}}
&= \frac{\sum_{y \in {\lbrace 0, 1 \rbrace}^{n-1}} c_{1y} \ket{1y}}{\sqrt{( \ \sum_{z \in {\lbrace 0, 1 \rbrace}^n} c_{z}^* \bra{z} \ ) \ \sum_{y \in {\lbrace 0, 1 \rbrace}^{n-1}} c_{1y} \ket{1y}}} \\
&= \frac{\sum_{y \in {\lbrace 0, 1 \rbrace}^{n-1}} c_{1y} \ket{1y}}{\sqrt{\sum_{z \in {\lbrace 0, 1 \rbrace}^n} \sum_{y \in {\lbrace 0, 1 \rbrace}^{n-1}} c_{z}^* c_{1y} \bracket{z}{1y}}} \\
&= \frac{\sum_{y \in {\lbrace 0, 1 \rbrace}^{n-1}} c_{1y} \ket{1y}}{\sqrt{\sum_{y \in {\lbrace 0, 1 \rbrace}^{n-1}} c_{1y}^* c_{1y}}} \\
&= \frac{\sum_{y \in {\lbrace 0, 1 \rbrace}^{n-1}} c_{1y} \ket{1y}}{\sqrt{\sum_{y \in {\lbrace 0, 1 \rbrace}^{n-1}} |c_{1y}|^2}} \\
&= \frac{\sum_{z:z_1 = 1} c_z \ket{z}}{\sqrt{\sum_{z:z_1 = 1} |c_z|^2}}
\end{align}