量子コンピューター入門: 古典ビット v.s. 量子ビット

#はじめに
量子コンピューターを理解するためのメモ書き。
http://qiita.com/testnin2/items/6dc777a2517d608b8d9f
という記事を書いたけど、もうちょっと量子コンピューターをちゃんと学ぶための独習用メモ
QiitaでTexもどきで数式が書けることが分かってちょっと嬉しい。

#古典ビット

古典ビットは一般的には電圧の高い・低いという二つの異なる状態で、0と1という数値を表す。
ただし、この古典ビットが表現できるのは、

- 0もしくは1の**どちらか１つ**
- 4ビット並んでいた場合には、0000から1111までの16種類の値の**どれか１つ**を表現できる。
- それぞれのビットの値は、他のビットの値とは関係なく定まる。
- コピーできる

（注）古典ビットで一般に実用されているのはエラーが検出し易く操作が簡単なデジタルビット(取りうる値は0か1)だが、仮に0.3とか0.7とかのような小数第1位まで使えるアナログ型のビットであれば、0.0から0.9の10種類の値を1ビットで取り扱うことができる。その際、4ビット利用時に「0.3,0.5,0.2,0.7」のように4ビットで10000種類の値を表現できる。しかし、この4ビットのアナログ型電子素子が存在したとしても、この10000種の値の**どれか1つしか同時には利用できない**ことは、デジタルビットの時と同様である。

#量子ビット

量子ビットは量子力学的2準位系の状態ベクトルからなる二つの独立した状態をそれぞれ$\left|0\right>$と$\left|1\right>$とすると、１量子ビットは$\left|\psi\right>=\alpha\left|0\right>+\beta\left|1\right>$と書ける。ただし、$\alpha, \beta$は$|\alpha|^2+|\beta|^2=1$を満たす複素数である。ここで、

- 観測の結果、必ず$\left|0\right>$もしくは$\left|1\right>$のどちらかの状態になる。
- $\left|0\right>$になる確率は$|\alpha|^2$、$\left|1\right>$になる確率は$|\beta|^2$（量子力学の確率解釈）
- 観測されると$\left|0\right>$もしくは$\left|1\right>$になることから、観測されるまでもある時点では$\left|0\right>$もしくは$\left|1\right>$のどちらかの状態で存在しており単純にどちらであるかを我々が知り得ないだけではないかと考えがちだが、正確には観測されるまでは$\left|0\right>$の状態も$\left|1\right>$の状態も本当に同時に存在していると考えるのが正しい（コペンハーゲン解釈による量子力学の重ね合わせの原理）。この”同時に存在する”という考えは、[二重スリットの実験](http://www.h5.dion.ne.jp/~terun/doc/neko1.html)とかが分かりやすい。”同時に存在”しなければ、１粒子しかないのに干渉を起こしてスクリーンに干渉縞を生じさせることはできない。


この量子ビットを複数個並べる場合は、$\left|1つ目の量子ビット\right>\otimes\left|2つ目の量子ビット\right>\otimes\left|3つ目の量子ビット\right>...$という表記を使って各々の量子ビットの状態を表現することにする。例えば、$\left|1\right>\otimes\left|0\right>$は、１つ目の量子ビットの状態が$\left|1\right>$で2つ目の量子ビットの状態が$\left|0\right>$であることを指すと考える。
> 実はベクトルの直積で表すこともできるので$\otimes$という記号を使っている。毎回$\otimes$を書くと面倒なので、簡略化して書きたい場合は$\left|1\right>\otimes\left|0\right>ではなく\left|10\right>$のように表記する。

それぞれの量子ビットは独立に$\left|0\right>$であったり$\left|1\right>$であったりするので、各々の量子ビットの状態の組み合わせによって表現されると考えると、2量子ビットの場合には、

```math
\begin{align}
\left|0\right>\otimes\left|0\right>&=\left|00\right> 観測すると1つ目の量子ビットも2つ目の量子ビットも\left|0\right>になる状態\\
\left|0\right>\otimes\left|1\right>&=\left|01\right> 観測すると1つ目の量子ビットは\left|0\right>だが2つ目の量子ビットは\left|1\right>になる状態\\
\left|1\right>\otimes\left|0\right>&=\left|10\right> 観測すると1つ目の量子ビットは\left|1\right>だが2つ目の量子ビットは\left|0\right>になる状態\\
\left|1\right>\otimes\left|1\right>&=\left|11\right> 観測すると1つ目の量子ビットも2つ目の量子ビットも\left|1\right>になる状態\\
\end{align}
```

の4つの状態の組み合わせで表現可能だと考え、2量子ビットは一般的に$\left|\psi_1\psi_2\right>=\alpha\left|00\right>+\beta\left|01\right>+\gamma\left|10\right>+\delta\left|11\right> $（ただし、$\alpha, \beta, \gamma, \delta$は複素数）のように表現する。それぞれの状態は独立しており、$\left|00\right>, \left|01\right>, \left|10\right>, \left|11\right>$になる確率はそれぞれ$|\alpha|^2,|\beta|^2,|\gamma|^2,|\delta|^2 $であり、$|\alpha|^2+|\beta|^2+|\gamma|^2+|\delta|^2=1 $である。


量子ビットの特徴としては、

- １量子ビットでも$\left|\psi\right>=\alpha\left|0\right>+\beta\left|1\right>$と書けることから、$\left|0\right>$と$\left|1\right>$の無限の組み合わせの状態が表現可能。
- N個の量子ビットを用いることで、$2^N$個の状態が同時に存在可能。例えば、4量子ビットを利用した場合に、各量子ビットが全て$\left|\psi\right>=\frac{(\left|0\right>+\left|1\right>)}{\sqrt2}$であれば、以下のように$2^4=16$の状態が**同時に**存在していることが分かる。

```math
\begin{align}
\left|\psi\right>\otimes\left|\psi\right>\otimes\left|\psi\right>\otimes\left|\psi\right>
&=
\frac{(\left|0\right>+\left|1\right>)}{\sqrt2}\otimes\frac{(\left|0\right>+\left|1\right>)}{\sqrt2}\otimes\frac{(\left|0\right>+\left|1\right>)}{\sqrt2}\otimes\frac{(\left|0\right>+\left|1\right>)}{\sqrt2}  \\
&= \frac{(\left|0000\right>+\left|0001\right>+\left|0010\right>+\left|0011\right> \\ 
+\left|0100\right>+\left|0101\right>+\left|0110\right>+\left|0111\right> \\
+\left|1000\right>+\left|1001\right>+\left|1010\right>+\left|1011\right> \\
+\left|1100\right>+\left|1101\right>+\left|1110\right>+\left|1111\right>)}
{\sqrt2^n}
\end{align}
```

- [量子もつれ](https://ja.wikipedia.org/wiki/%E9%87%8F%E5%AD%90%E3%82%82%E3%81%A4%E3%82%8C)とかエンタングルメント（絡み合い）と呼ばれる「量子ビット間で依存関係が発生し、各々の量子ビットが独立で存在することができない状態」が存在する。例えば、$\frac{(\left|00\right>+\left|11\right>)}{\sqrt2}$は、エンタングルメントと呼ばれる状態になっている。もし各量子ビットが独立に存在できるのであれば、

```math
\begin{align}
\left|\psi_1\right>\otimes\left|\psi_2\right> &=(a\left|0\right>+b\left|1\right>)\otimes(c\left|0\right>+d\left|1\right>)\\
&=ac\left|00\right>+bc\left|10\right>+ad\left|01\right>+bd\left|11\right>\\
&= \frac{(\left|00\right>+\left|11\right>)}{\sqrt2}
\end{align}
```

となるような$a, b, c, d$が存在するはずだが、そんな数は存在しないことは容易に分かる。このエンタングルメントの例だと、

    - 1つ目の量子ビットが|0>になるか|1>になるかは観測されるまでは完全にランダム。
    - 1つ目の量子ビットが|0>と観測されれば、必ず２つ目の量子ビットも|0>になる。
    - 同様に、1つ目の量子ビットが|1>と観測されれば、必ず２つ目の量子ビットも|1>になる。
    
という相関関係があることが数式から読み取れる。

- コピーできない（ノークローニング定理とか量子複製不可能定理と呼ばれる）ことが証明されている。

- ある状態の量子ビットを別の場所に転送・移動することは可能（量子テレポーテーション）。ただし、この量子テレポーテーションの作業中に転送元の量子ビットを観測して状態を壊してしまう必要があるため、コピーにはならない。転送先には、観測までの量子ビットの状態が現れる。


#補足
量子コンピューターの超高速計算の源泉は、

1) 量子ビットという複素数で表現される計算リソースを用いて、
2) エンタングルメント状態の量子ビットがたくさん並列して存在する状態を作り出し、
3) 演算処理を行うことでこの同時に並列して存在する状態に対して並列計算を行い、
4) 計算結果が含まれている状態の絡み合いを解いて必要な部分だけを読み出せるようにしてから観測する

ことである。