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

## 前書き

本記事では、[Quantum Katas の BasicGates](https://github.com/Microsoft/QuantumKatas/tree/master/BasicGates) について解説します。Q# や Quantum Katas って何よという方は [Quantum Katas で始める量子コンピュータ入門 |0⟩](https://qiita.com/stwhabout/items/195b93a194c24ba5fb73) をご参照ください。

## 各 Task の解説

### Task 1.1. State flip: |0⟩ to |1⟩ and vice versa

> 入力: $|\psi \rangle = \alpha | 0 \rangle + \beta | 1 \rangle$

> ゴール: $\alpha | 1 \rangle + \beta | 0 \rangle$ を作る。

この問題は答えがかいてあります。記事 |0⟩ でも述べた通り、$X$ ゲートを使えばよさそうです。答えは以下。

```cs
operation StateFlip (q : Qubit) : ()
{
    body
    {
        X(q);
    }
    adjoint self;
}
```

### Task 1.2. Basis change: |0⟩ to |+⟩ and |1⟩ to |-⟩ (and vice versa)

> 入力: $|\psi \rangle = \alpha | 0 \rangle + \beta | 1 \rangle$

> ゴール: $|0⟩$ なら $\frac{|0 \rangle + | 1 \rangle}{\sqrt{2}}$ を、$|1⟩$ なら $\frac{|0 \rangle - | 1 \rangle}{\sqrt{2}}$ となるように量子ビットを変化させる。

重ね合わせ状態を作る問題です。[Primitive のページ](https://docs.microsoft.com/en-us/qsharp/api/prelude/microsoft.quantum.primitive?view=qsharp-preview) を見てもらえば、アダマール ゲートの定義そのものであることが確認できます。答えは以下。

```cs
operation BasisChange (q : Qubit) : ()
{
    body
    {
        H(q);
    }
    adjoint self;
}
```

### Task 1.3. Sign flip: |+⟩ to |-⟩ and vice versa.

> 入力: $|\psi \rangle = \alpha | 0 \rangle + \beta | 1 \rangle$

> ゴール: $|\psi⟩ = \alpha |0⟩ - \beta |1⟩$ となるように量子ビットを変化させる。

位相を変化させる問題です。これも [Primitive のページ](https://docs.microsoft.com/en-us/qsharp/api/prelude/microsoft.quantum.primitive?view=qsharp-preview) を見てもらえば、Z ゲートの定義そのものであることが確認できます。答えは以下。

```cs
operation SignFlip (q : Qubit) : ()
{
    body
    {
        Z(q);
    }
    adjoint self;
}
```

### Task 1.4*. Amplitude change: |0⟩ to cos(alpha)*|0⟩ + sin(alpha)*|1⟩.

> 入力: $|\psi \rangle = \beta | 0 \rangle + \gamma | 1 \rangle$、角度$\alpha$ (Double 型)

> ゴール: $|0⟩$ を $\cos \alpha |0⟩ + \sin \alpha |1⟩$, $|1⟩$ を $-\sin \alpha |0⟩ + \cos \alpha |1⟩$ となるように量子ビットを変化させる。


個人的には手こずりました。$|0⟩$ を $\cos \alpha |0⟩ + \sin \alpha |1⟩$, $|1⟩$ を $-\sin \alpha |0⟩ + \cos \alpha |1⟩$ に変換するので、必要な行列 $\Theta (\alpha)$ は

```math
\Theta(\alpha) =  
\begin{pmatrix}
\cos \alpha & -\sin \alpha \\
\sin \alpha & \cos \alpha \\
\end{pmatrix}
```

となり、いわゆる回転行列になります。しかしながら、[Primitive のページ](https://docs.microsoft.com/en-us/qsharp/api/prelude/microsoft.quantum.primitive?view=qsharp-preview) をみても、そのような行列はパッと見では見当たりません。

数学が得意な方なら気が付くのかもしれませんが、この回転行列は Q# の Primitive に含まれる $R_y(\theta)$ に他ならないことがわかります。定義が $R_y(\theta):= e^{-i\theta \sigma_{y}/2}$ と角度が半分になっている所に注意すると、回答は以下となります。

```cs
operation AmplitudeChange (q : Qubit, alpha : Double) : ()
{
    body
    {
        Ry(alpha*2.0, q);
    }
    adjoint auto;
}
```

#### Task 1.4 の補足

以下は  $R_y(\theta):= e^{-i\theta \sigma_{y}/2}$ が本当に回転行列になるのか？ と疑問を持った方向けの補足です。一般的に、$e$ の行列乗は、実数 $x$ に対するマクローリン展開が
 
 $$e^x = \sum_k \frac {x^k}{k!}$$ 

であるため、任意の行列 $\mathbb A$ に対して

 $$e^{\mathbb A} = \sum_k \frac {\mathbb A^k}{k!}$$

と定義されます。 今、$\mathbb A =-i\theta \sigma_{y}/2$ で、$\sigma_y^2 = \mathbb I$ に注意して、$\alpha = \frac \theta 2$ とすると

```math
\begin{aligned}
e^{-i\theta \sigma_{y}/2} 
&= 
     I + (-i\alpha) \sigma_y + \frac{(-i\alpha)^2}{2!}I + \frac{(-i\alpha)^3}{3!}\sigma_y + \frac{(-i\alpha)^4}{4!}I  +\frac{(-i\alpha)^5}{5!}\sigma_y + \frac{(-i\alpha)^6}{6!}I  \dots
 \\
&= 
 \left(
     1 - \frac{\alpha^2}{2!} + \frac{\alpha^4}{4!} - \frac{\alpha^6}{6!} + \dots
   \right)I - 
 i\left(
     \alpha - \frac{\alpha^3}{3!} + \frac{\alpha^5}{5!} - \frac{\alpha^7}{7!} + \dots
   \right)\sigma_y  \\
&= 
    \begin{pmatrix}
    \cos \alpha & 0 \\
    0 & \cos \alpha \\
    \end{pmatrix} +
    \begin{pmatrix}
    0 & i^2 \sin \alpha \\
    -i^2 \sin \alpha & 0 \\
  \end{pmatrix} \\
& =
    \begin{pmatrix}
    \cos \alpha & -\sin \alpha \\
    \sin \alpha & \cos \alpha \\
    \end{pmatrix}
\end{aligned}
```

となり、回転行列であることが確認できました。途中、以下の定義を使っているところにご注意ください。

```math
\begin{aligned}
    \sin \theta &= \sum_{n=0}^{\infty} \frac{(-1)^n}{(2n+1)!}\theta^{2n+1} = \theta - \frac{\theta^3}{3!} + \frac{\theta^5}{5!} - \frac{\theta^7}{7!} + \dots\\
    \cos \theta &= \sum_{n=0}^{\infty} \frac{(-1)^n}{(2n)!}\theta^{2n} = 1 - \frac{\theta^2}{2!} + \frac{\theta^4}{4!} - \frac{\theta^6}{6!} + \dots
\end{aligned}
```


### Task 1.5. Phase flip

> 入力: $|\psi \rangle = \alpha | 0 \rangle + \beta | 1 \rangle$

> ゴール: $|\psi⟩ = \alpha |0⟩ + i\beta |1⟩$ となるように量子ビットを変化させる。

先ほどのヘビーな問題から一転、この問題は [Primitive のページ](https://docs.microsoft.com/en-us/qsharp/api/prelude/microsoft.quantum.primitive?view=qsharp-preview) とにらめっこすれば、$S$ ゲートを使うことで実現できそうです。回答は以下。

```cs
operation PhaseFlip (q : Qubit) : ()
{
    body
    {
        S(q);
    }
    adjoint auto;
}
```

### Task 1.6*. Phase change

> 入力: $|\psi \rangle = \beta | 0 \rangle + \gamma | 1 \rangle$

> ゴール: $|0⟩$ はそのまま、$|1⟩$ は $e^{i\alpha}|1⟩$ となるように量子ビットを変化させる。

この問題も [Primitive のページ](https://docs.microsoft.com/en-us/qsharp/api/prelude/microsoft.quantum.primitive?view=qsharp-preview) とにらめっこすれば、$R_1$ ゲートを使うことで実現できそうです。

```math
R_1(\theta) = \rm diag(1, e^{i\theta}) = 
    \begin{pmatrix}
        1 & 0 \\
        0 & e^{i\theta}
    \end{pmatrix}
```

回答は以下となります。Task 1.4 とは異なり、定義からも角度を倍にするような操作は不要です。

```cs
operation PhaseChange (q : Qubit, alpha : Double) : ()
{
    body
    {
        R1(alpha, q);
    }
    adjoint auto;
}
```

### Task 1.7. Bell state change - 1

> 入力: 2 つの量子ビット $|\phi^+⟩ = \frac{|00⟩ + |11⟩}{\sqrt 2}$

> ゴール: $|\phi^+⟩ = \frac{|00⟩ - |11⟩}{\sqrt 2}$ に変換する。

2 量子ビットに対する問題が始まりましたが、あまり難しく考える必要はありません。1 量子ビットの場合は、Z ゲートを使うことで位相の反転は実現できたのでした。この場合も、どちらかの量子ビットを対象に Z ゲートを使えば位相の反転が実現できます。回答は以下です。

```cs
operation BellStateChange1 (qs : Qubit[]) : ()
{
    body
    {
        Z(qs[1]);
    }
    adjoint auto;
}
```

### Task 1.8. Bell state change - 2

> 入力: 2 つの量子ビット $|\phi^+⟩ = \frac{|00⟩ + |11⟩}{\sqrt 2}$

> ゴール: $|\psi^+⟩ = \frac{|01⟩ + |10⟩}{\sqrt 2}$ に変換する。

引き続き 2 量子ビットの問題です。どちらかの量子ビットを反転すればよさそうです。回答は以下。

```cs
operation BellStateChange2 (qs : Qubit[]) : ()
{
    body
    {
        X(qs[0]);
    }
    adjoint auto;
}
```

### Task 1.9. Bell state change - 3

> 入力: 2 つの量子ビット $|\phi^+⟩ = \frac{|00⟩ + |11⟩}{\sqrt 2}$

> ゴール: $|\psi^-⟩ = \frac{|01⟩ - |10⟩}{\sqrt 2}$ に変換する。

同じような問題ですが、先の 2 つの Task を組み合わせれば実現できそうです。まず、Task 1.8 と同様に X ゲートを使って $|\psi^+⟩ = \frac{|01⟩ + |10⟩}{\sqrt 2}$ を作ります。続いて、先頭ビットの位相を反転してやれば目的の状態が作れそうです。回答は以下。

```cs
operation BellStateChange3 (qs : Qubit[]) : ()
{
    body
    {
        X(qs[0]);
        Z(qs[0]);
    }
    adjoint auto;
}
```


### Task 2.1. Two-qubit gate - 1

> 入力: 2 つの量子ビット $|\psi \rangle = \alpha | 0 \rangle + \beta | 1 \rangle$ と $|0⟩$

> ゴール: $\alpha | 00 \rangle + \beta | 11 \rangle$ に変換する。

このタスク以降は、2 つ以上の量子ビットを入力として扱う量子ゲートに関する操作を学んでいきます。この問題は片方の量子ビットは重ねあわされているものの、他方は重ね合わせとなっていないときに、量子もつれ状態を作る問題となっています。

先頭の量子ビットが $|0⟩$ なら 2 量子ビット目も $|0⟩$ のまま、先頭の量子ビットが $|1⟩$ なら 2 量子ビットは $|1⟩$ にとする問題なので、1 ビット目を制御ビット、2 ビット目を標的ビットとして $\rm CNOT$ ゲートを利用してやればよさそうです。回答は以下。

```cs
operation TwoQubitGate1 (qs : Qubit[]) : ()
{
    body
    {
        CNOT(qs[0], qs[1]);
    }
    adjoint self;
}
```




### Task 2.2. Two-qubit gate - 2

> 入力: $\frac{|0 \rangle + | 1 \rangle}{\sqrt{2}}$ という状態の 2 つの量子ビット。言い換えると、$\frac{|00⟩ +|01⟩ +|10⟩ +|11⟩}{2}$。

> ゴール: $\frac{|00⟩ +|01⟩ +|10⟩ -|11⟩}{2}$ に変換する。

$|11⟩$ のときだけ位相を反転するという問題です。こういうときは Q# ではどう書けばいいのでしょう？

結論から言えば、Q# には $\rm Controlled$ というファンクタが存在し、これを使うことで、任意の量子ゲートを制御ビットによって制御することが可能となります。（詳しくは [Q# type model](https://docs.microsoft.com/en-us/quantum/quantum-qr-typemodel?view=qsharp-preview#controlled)をご参照ください。）先のほどの Task で当たり前のように使った $\rm CNOT$ ゲートも、内部ではこの $\rm Controlled$ ファンクタを使って実装されているようです。

先頭ビットが 1 の時に Z ゲートを通せばよさそうなので、回答は以下となります。$\rm Controlled$ ファンクタの第一引数は量子ビットの配列となり、複数の制御ビットが全て 1 の時だけ動作するという記述が可能です。今回は制御ビットは 1 ビットだけですが、要素数 1 の配列として認識させるため、`[]` が必要となります。

```cs
operation TwoQubitGate2 (qs : Qubit[]) : ()
{
    body
    {
        (Controlled Z)([qs[0]], (qs[1]));
    }
    adjoint self;
}
```

### Task 2.3. Two-qubit gate - 3

> 入力: $\alpha|00⟩ + \beta|01⟩ + \gamma|10⟩ + \delta|11⟩$ という状態の 2 つの量子ビット

> ゴール: $\alpha|00⟩ + \gamma|01⟩ + \beta|10⟩ + \delta|11⟩$ に変換する。

問題から、2 つの量子ビットの状態を入れ替えればよさそうに見えます。[Primitive のページ](https://docs.microsoft.com/en-us/qsharp/api/prelude/microsoft.quantum.primitive?view=qsharp-preview) をみると、量子ビットを入れ替える $\rm SWAP$ というゲートがあるのですが、この問題のヒントとして「1 ゲートでも実現できるが、複数のゲートを組み合わせて実現してみろ」という但し書きがあります。

この操作は $\rm CNOT$ を使えば実現できます。定義を再度振り返りましょう。


```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⟩$なら何もしないが、$|10⟩$や $|11⟩$ なら標的ビットを反転する。）では、制御ビットと標的ビットが入れ替わったらどういう行列になるでしょう？これも難しいわけではないのですが、$|00⟩$や$|10⟩$なら何もしないが、$|01⟩$や $|11⟩$ なら標的ビットを反転するという操作となるため、行列で書くと以下のようになります。（ここでは仮に $\rm CNOT'$ と呼ぶことにします）

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

上記の制御ビットと標的ビットが入れ替わった $\rm CNOT'$ を含め、$\rm CNOT \rightarrow \rm CNOT' \rightarrow \rm CNOT$ という処理を行ってみましょう。

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

結論ありきの計算ではありましたが、上記の通り制御ビットと標的ビットを入れ替えながら 3 回 $\rm CNOT$ で処理をすることで問題の要件は満たせそうです。なので回答は以下。

```cs
operation TwoQubitGate3 (qs : Qubit[]) : ()
{
    body
    {
        // Hint: this task can be solved using one primitive gate;
        // as an exercise, try to express the solution using several 
        // (possibly controlled) Pauli gates.
        CNOT(qs[0], qs[1]);
        CNOT(qs[1], qs[0]);
        CNOT(qs[0], qs[1]);
    }
    adjoint self;
}
```

これは個人的にはさらっとすごいことを言っているなと思いました。現在のコンピュータではビット操作に限らず、変数の SWAP をやるときは余分な変数が必要となるということが当たり前だと思っていたのですが、量子コンピュータでは交換したい 2 ビット以外の余剰ビットがなくても状態の交換を行うことができるんですね。すごいぜ量子コンピュータ！！

### Task 2.4. Toffoli gate

> 入力: 
> $$\alpha|000⟩ + \beta|001⟩ + \gamma|010⟩ + \delta|011⟩ + \epsilon|100⟩ + \zeta|101⟩ + \eta|110⟩ + \theta|111⟩$$
>  という状態の 3 つの量子ビット

> ゴール: 
> $$\alpha|000⟩ + \beta|001⟩ + \gamma|010⟩ + \delta|011⟩ + 
\epsilon|100⟩ + \zeta|101⟩ + \theta|110⟩ + \eta|111⟩$$
> に変換する。

問題から、先頭の 2 ビットが $|11⟩$ の時に末尾のビットを入れ替えれば要件を満たせそうです。 Toffoli gate という名前が付いたゲートだそうです。
先の問題でもあった、$\rm Controlled$ ファンクタを使って末尾のビットを X ゲートで反転してやればよいでしょう。
回答は以下。

```cs
operation ToffoliGate (qs : Qubit[]) : ()
{
    body
    {
        (Controlled X)([qs[0]; qs[1]], qs[2]);
    }
    adjoint self;
}
```


### Task 2.5. Fredkin gate


> 入力: 
> $$\alpha|000⟩ + \beta|001⟩ + \gamma|010⟩ + \delta|011⟩ + \epsilon|100⟩ + \zeta|101⟩ + \eta|110⟩ + \theta|111⟩$$ 
> という状態の 3 つの量子ビット

> ゴール: 
> $$\alpha|000⟩ + \beta|001⟩ + \gamma|010⟩ + \delta|011⟩ + \epsilon|100⟩ + \eta|101⟩ + \zeta|110⟩ + \theta|111⟩$$
>  に変換する。

同じような問題が続きますが、先頭ビットを制御ビットとして、残り 2 ビットの状態を交換すれば実現できそうです。
Task 2.3 では使わなかった $\rm SWAP$ ゲートと $\rm Controlled$ ファンクタを組み合わせればよいでしょう。
回答は以下。

```cs
operation FredkinGate (qs : Qubit[]) : ()
{
    body
    {
        (Controlled SWAP)([qs[0]], (qs[1], qs[2]));
    }
    adjoint self;
}
```

## 最後に

これで BasicGates は終了です。次は $|2⟩$ Superposition でお会いしましょう。