Quantum Katas で始める量子コンピュータ入門 |0⟩

## 前書き

みなさーん、**量子プログラミングやってますかー？** 量子コンピューターって夢がありますよね。超高速計算ができるとか、今普及している暗号方式が危殆化してしまうとか言われていますが、正直よくわからないと思いませんか？どの解説にも書いてある「1 と 0 の重ね合わせを同時に計算するから速い」という説明はすごく嘘くさいなと個人的には感じていました。

そんな折に、量子コンピューターの開発を進めると発表したマイクロソフトから、量子プログラミングを行う言語である Q# が発表され、Q# の個人学習を行うための問題集である Quantum Katas が公開されました。Quantum Katas には回答もついているのですが、それだけだとよくわからないところも多いと感じたため、全問解説をやってみようかと思います。

## TL;DR

各 Kata の解説は以下にあります。（随時更新予定）

[Quantum Katas で始める量子コンピュータ入門 |1⟩: BasicGates](https://qiita.com/stwhabout/items/4bae12310a5670cab199)
[Quantum Katas で始める量子コンピュータ入門 α|1⟩+β|2⟩: UnitaryPatterns](https://qiita.com/tehishik/items/7771a6daa4dc34f8f455)
[Quantum Katas で始める量子コンピュータ入門 |2⟩: SuperPosition](https://qiita.com/stwhabout/items/f0df8cb8dd5f1062ec15)
[Quantum Katas で始める量子コンピュータ入門 |3⟩: Measurement](https://qiita.com/stwhabout/items/d4235b0cfa2f9dffb439)
[Quantum Katas で始める量子コンピュータ入門 |4⟩: Deutsch-Jozsa Algorithm](https://qiita.com/stwhabout/items/1e68c6e2ee0605b3cd16)
[Quantum Katas で始める量子コンピュータ入門 |5⟩: Superdense Coding](https://qiita.com/stwhabout/items/0eae11cade7bbbb67563)
[Quantum Katas で始める量子コンピュータ入門 |6⟩: Simon's Algorithm](https://qiita.com/stwhabout/items/04105d054b739914d478)
[Quantum Katas で始める量子コンピュータ入門 |7⟩: Teleportation](https://qiita.com/stwhabout/items/8d1d9bae93a722ed24df)
[Quantum Katas で始める量子コンピュータ入門 |8⟩: Joint Measurement](https://qiita.com/tehishik/items/770b3d894b1850b4c703)
[Quantum Katas で始める量子コンピュータ入門 |9⟩: quantum error-correction](https://qiita.com/tehishik/items/f0bd1a3b5a4a09880699)
[Quantum Katas で始める量子コンピュータ入門 |10⟩: Grover's algorithm](https://qiita.com/tehishik/items/2e780724bd7e5ad2f1bb)
[Quantum Katas で始める量子コンピュータ入門 |11⟩: Quantum Phase Estimation](https://qiita.com/tehishik/items/831433600ea2361adbd1)
[Quantum Katas で始める量子コンピュータ入門 |12⟩: Solve SAT with Grover](https://qiita.com/tehishik/items/f888cf97c8323f1bd23a)
[Quantum Katas で始める量子コンピュータ入門 |13⟩: CHSH game](https://qiita.com/tehishik/items/9a745514133fcda1c0b5)
[Quantum Katas で始める量子コンピュータ入門 |14⟩: GHZ game](https://qiita.com/tehishik/items/c2f83cefb3fbaebb90c7)



## そもそも Quantum Katas って何よ

マイクロソフトが開発した Q# を利用して量子プログラミングについて学習するための問題集で、Github の [Microsoft/QuantumKatas](https://github.com/Microsoft/QuantumKatas) で公開されています。
各 Kata のフォルダー配下には `Task.qs` というファイルが存在し、このファイル内に解くべき複数の Task が含まれています。各 Task を進めていくと量子プログラミングに必要な知識が習得できるように構成されています。
（同じフォルダー配下に回答である `ReferenceImplementation.qs` も含まれています。）

さらに、各 Kata にはテスト ファイルも含まれているので、Task を埋めた後はテストを実行することで答え合わせをすることが可能です。最初の方は無味乾燥とした Task を淡々とこなす必要がありますが、名前がついているようなアルゴリズムの Task まで到達すると、量子コンピューターのすごさが垣間見えるようになっています。

## 前提知識

量子コンピューターは名前の通り量子力学で記述される物理現象を利用したコンピューターなので、量子力学やそれにまつわる数学の知識が必要そうに見えますが、量子プログラミングの勉強を始める前の私の仮説は以下でした。

> 仮説: 現在のコンピューターに詳しいエンジニアでも、トランジスタの動作や、トランジスタで計算ができる理由をちゃんと説明できる人は多くない。量子コンピューターも、量子力学をわからなくても概ね問題ないはず。

結論から言えば、上記の仮説はもろくも崩れ去りました。


### コンピュータ サイエンスは多少分かるが量子力学とかマジで知らない人間が量子プログラミングを学ぶ上で必要な知識

煽りみたいなタイトルですが、私が勉強したうえで躓いた点や、理解に至るのに時間がかかった点を書き出してみました。改めて書き出してみると量は多いですが、少なくとも以下の知識を「そういうものかな」と思えれば Quantum Katas で量子コンピューティングの学習を進めることはできるのではないかと思います。（ちゃんと理解したといえるためには量子力学の知識は必須そうです。）

1. 量子ビット $|\psi⟩$ はこれまでのコンピューターのビットとは違い、$|0⟩$ と $|1⟩$ の状態を重ね合わせて持つ。
2. 重ねあわされた量子ビットを観測した場合は、どちらかの状態 ($|0⟩$ か $|1⟩$) に確定され、重ねあわされた状態は壊れる。
3. 重ね合わせは単純な確率では表現できない。例えば、最終的に観測した際に確率 0.5 で $|0⟩$ が観測されるような二つの量子ビットがあった場合でも、異なる複数の状態が存在しうる。この状態を表現するために、量子ビットの係数（確立振幅）には複素数が用いられる。

    $$
    |\psi \rangle = \alpha | 0 \rangle + \beta | 1 \rangle
    $$

4. このとき、$\alpha$ と $\beta$ は複素数で、$|\alpha|^2 + |\beta|^2 = 1$ が成り立つ。
5. $\alpha$ と $\beta$ がそれぞれ 2 次元のパラメータを持つので、合計 4 次元のパラメータ空間を持つように見えるが、$|\alpha|^2 + |\beta|^2 = 1$ を考慮するとパラメータ空間は 3 次元になる。
6. 量子ビットの 3 次元のパラメータをうまく変形してやると、量子ビットの状態は単位球上に表現できることが導出される。この球表現をブロッホ球と呼び、量子ビットの状態は単位球上の位相として表現される。量子ビットに対する操作を行う量子ゲートによって量子ビットの状態がどうなるかを考える際も、ブロッホ球を思い浮かべる必要がある。
8. 重ね合わせ以外に、量子ビットは量子もつれという性質を持つ。例えば確率が 0.5 の量子ビット $|\psi⟩ = \frac{|0⟩ + |1⟩}{\sqrt 2}$が 2 つあった場合、一方が $|0⟩$ で他方が $|1⟩$ という状況も起こりうるが、二つの量子ビットをもつれさせることで、例えば 一方が $|0⟩$ なら他方も $|0⟩$ となるような状態も作ることができる。
9. 量子ビット $|\psi⟩$ の状態はベクトルで記述される。以下の二つの表現は等価である。

    ```math
    \begin{aligned}
    |\psi \rangle =& \alpha | 0 \rangle + \beta | 1 \rangle\\
    |\psi \rangle =&\alpha
        \begin{pmatrix}
            1 \\
            0  
        \end{pmatrix}
        + \beta
        \begin{pmatrix}
            0 \\
            1
        \end{pmatrix}

    \end{aligned}
    ```

10. 量子ビットはベクトルで表現されるので、量子ビットに対する操作 （言い換えると、量子ゲートの動作）は行列で記述される。

最初はなんじゃそらと思うところも多いと思いますが、Kata を進めていくうちになんとなくそういうものかと思えるようになるかと思います。

## Q# の基礎

Q# で使える量子ゲートについては [Microsoft.Quantum.Intrinsic](https://docs.microsoft.com/en-us/qsharp/api/qsharp/microsoft.quantum.intrinsic?view=qsharp-preview)  にて紹介されています。ここでは、絶対に避けては通れない 4 つの主要なゲートだけご紹介します。

### X ゲート 

X ゲートとか NOT ゲートとか言われます。定義は以下です。

```math
\sigma_x = 
\begin{pmatrix}
    0 & 1 \\
    1 & 0  
\end{pmatrix}
```

この定義からもすぐに確かめられますが、このゲートは $|0⟩$ と $|1⟩$ の状態を入れ替える動作を持ちます。このため NOT ゲートと呼ばれます。

```math
\sigma_x 
    \begin{pmatrix}
        \alpha \\
        \beta
    \end{pmatrix}
= 
\begin{pmatrix}
    0 & 1 \\
    1 & 0  
\end{pmatrix}
\begin{pmatrix}
    \alpha \\
    \beta
\end{pmatrix}
= 
\begin{pmatrix}
    \beta  \\
    \alpha
\end{pmatrix}
= \beta|0⟩ + \alpha|1⟩
```

### Z ゲート

Z ゲートの定義は以下です。

```math
\sigma_z = 
\begin{pmatrix}
    1 & 0 \\
    0 & -1  
\end{pmatrix}
```

このゲートは $|1⟩$ の位相を変化させる動作を持ちます。

```math
\sigma_z
    \begin{pmatrix}
        \alpha \\
        \beta
    \end{pmatrix}
= 
\begin{pmatrix}
    1 & 0 \\
    0 & -1  
\end{pmatrix}
\begin{pmatrix}
    \alpha \\
    \beta
\end{pmatrix}
= 
\begin{pmatrix}
    \alpha \\
    -\beta
\end{pmatrix}
= \alpha|0⟩ - \beta|1⟩
```

### H ゲート

アダマール ゲートと呼ばれます。定義は以下です。

```math
H = \frac{1}{\sqrt 2}
    \begin{pmatrix}
        1&1 \\
        1&-1
    \end{pmatrix}
```

このゲートは、現在の量子ビットの状態を踏まえて重ね合わせを実現する動作を持ちます。

```math
H
    \begin{pmatrix}
        \alpha \\
        \beta
    \end{pmatrix}
=  \frac{1}{\sqrt 2}
    \begin{pmatrix}
        1&1 \\
        1&-1
    \end{pmatrix}
\begin{pmatrix}
    \alpha \\
    \beta
\end{pmatrix}
= \frac{1}{\sqrt 2}
\begin{pmatrix}
    \alpha + \beta \\
    \alpha -\beta
\end{pmatrix}
= \frac{\alpha + \beta}{\sqrt 2}|0⟩ + \frac{\alpha - \beta}{\sqrt 2}|1⟩ 
```

急に複雑になった気がしますが、大したことはありません。イメージとしては、今の状態（$|0⟩$ と $|1⟩$ の確立振幅） を計算式に従って再分配したようなイメージを持っておけばいいでしょう。よく使われる利用方法としては、初期状態 $|\psi⟩ = |0⟩$ （確率 １ で$|0⟩$ をとる）から重ね合わせを作り出すときに利用されます。この時は $\alpha = 1, \beta = 0$ なので

```math
H(|0⟩)= \frac{1}{\sqrt 2}|0⟩ + \frac{1}{\sqrt 2}|1⟩ 
```

となり、それぞれの状態が観測される確率が $\frac{1}{2}$ であるような状態を実現できることがわかります。

### CNOT ゲート

CNOT ゲートとか、Controlled NOT ゲートとか呼ばれます。これまでのゲートとは異なり、2 つの量子ビットを利用するゲートとなります。定義は以下です。

```math
\rm CNOT = 
    \begin{pmatrix}
        1&0&0&0 \\
        0&1&0&0 \\
        0&0&0&1 \\
        0&0&1&0
    \end{pmatrix}
```

そのままですが、2 量子ビットの状態は $|00⟩$ や $|01⟩$ などの形式で記述します。今、2 量子ビットの状態が $\alpha|00⟩+\beta|01⟩+\gamma|10⟩+\delta|11⟩$ と表現されるとすると

```math
\rm CNOT
    \begin{pmatrix}
        \alpha \\
        \beta \\
        \gamma \\
        \delta
    \end{pmatrix}
    =
    \begin{pmatrix}
        1&0&0&0 \\
        0&1&0&0 \\
        0&0&0&1 \\
        0&0&1&0
    \end{pmatrix}
    \begin{pmatrix}
        \alpha \\
        \beta \\
        \gamma \\
        \delta
    \end{pmatrix}
    =
    \begin{pmatrix}
        \alpha \\
        \beta \\
        \delta \\
        \gamma \\
    \end{pmatrix}
    = \alpha|00⟩+\beta|01⟩+\delta|10⟩+\gamma|11⟩
```

これもややこしいことを言っているようにも見えますが、大したことはありません。要は、先頭ビット (これを制御ビットと言います) が 1 だった時に、2 ビット目 （これを標的ビットと言います）を NOT するというのが $\rm CNOT$ ゲートの動作です。先頭ビットが 0 のときは何も行われません。$\rm CNOT$ ゲートは先に記載した量子もつれを実現するのに使われます。（詳細は各 Kata をご覧ください。）

また、見方を変えればこのゲートは既存のデジタル回路の XOR と同じ動作を行う、ということもできます。標的ビットの最終的な状態を XOR の出力としてみなすと、標的ビットが $|1⟩$ となるのは初期状態が $|01⟩$ か $|10⟩$ の時であるためです。量子ゲートでは途中で量子ビットを増減させることができず、入力と出力が 1:1 となるためちょっとわかりにくいですが・・・。

## 参考文献

量子力学にさらに興味がある方は、神サイトである [ＥＭＡＮの物理学](http://eman-physics.net/) を参照されるのがよいかと思います。