Help us understand the problem. What is going on with this article?

『量子計算理論 量子コンピュータの原理』演習(第2章&第3章)

More than 1 year has passed since last update.

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

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

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

『量子計算理論 量子コンピュータの原理』演習(第4章1節&2節)
『量子計算理論 量子コンピュータの原理』演習(第4章4節)混合状態

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}
piyo7
機械の言葉と、数学の言葉と、それから人間の言葉を喋るよ♪
https://piyo7.github.io/deep-sister/
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした