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


## 前書き

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

## 各 Task の解説

### Task 1. Plus state

> 入力: $|0 \rangle$

> ゴール: $|+⟩ = \frac{| 0 \rangle + | 1 \rangle}{\sqrt 2}$ を作る。

既に BasicGates を終えた人なら、すでに実施済みの問題ですね。これも答えが書いてあります。


```cs
operation PlusState (qs : Qubit[]) : ()
{
    body
    {
        H(qs[0]);
    }
}
```



### Task 2. Minus state

> 入力: $|0 \rangle$

> ゴール: $|-⟩ = \frac{| 0 \rangle - | 1 \rangle}{\sqrt 2}$ を作る。

この問題も BasicGates で通ってきた問題ですね。ゴールは $|1⟩$ をアダマール ゲートで処理した結果なので、入力を X ゲートで処理してからアダマール ゲートに通せばよさそうです。回答は以下です。

```cs
operation MinusState (qs : Qubit[]) : ()
{
    body
    {
        X(qs[0]);
        H(qs[0]);
    }
}
```

### Task 3*. Unequal superposition

> 入力: $|0 \rangle$, 角度 $\alpha$ (Double 型)

> ゴール: $\cos \alpha |0⟩ + \sin \alpha |1⟩$ を作る。

この問題もそのまま BasicGates でやりました。$R_y(\theta)$ を使えばいいんでしたね。回答は以下です。

```cs
operation UnequalSuperposition (qs : Qubit[], alpha : Double) : ()
{
    body
    {
        Ry(alpha*2.0, qs[0]);
    }
}
```

### Task 4. Bell state

> 入力: $|00 \rangle$

> ゴール: $|\phi^+⟩ = \frac{| 00 \rangle + | 11 \rangle}{\sqrt 2}$ を作る。

これも BasicGates でやった内容ほぼそのままです。片方の量子ビットをアダマール ゲートで重ね合わせ状態にした後で、重ね合わせた量子ビットを制御ビットとして $\rm CNOT$ ゲートで処理すればできそうです。

```cs
operation BellState (qs : Qubit[]) : ()
{
    body
    {
        H(qs[0]);
        CNOT(qs[0], qs[1]);
    }
}
```

### Task 5. All Bell states

> 入力: $|00 \rangle$, および 整数値 $\rm index$

> ゴール:  整数値 $\rm index$ の値に応じて、以下の状態を作る。
> 1. $|\phi^+⟩ = \frac{| 00 \rangle + | 11 \rangle}{2}$ 
> 2. $|\phi^-⟩ = \frac{| 00 \rangle - | 11 \rangle}{2}$ 
> 3. $|\psi^+⟩ = \frac{| 01 \rangle + | 10 \rangle}{2}$ 
> 4. $|\psi^-⟩ = \frac{| 01 \rangle - | 10 \rangle}{2}$ 

ちょっとずつ作るべき状態が複雑になってきました。ここでは、整数値によって上記の 4 つの状態 （これをベル状態といいます）を作り分けることとなります。が、よくよく見てみると 1 つ目の $|\phi^+⟩$ は既に先ほどの Task で作成したので、これはそのままでよさそうです。また、$|\phi^+⟩$ が与えられたときに $|\phi^-⟩$ や $|\psi^+⟩$、そして $|\psi^+⟩$ を作る方法については BasicGates でやりましたね。$|\phi^+⟩$ さえ作ってしまえば、あとは BasicGates と同じ内容で回答が完了します。

```cs
operation AllBellStates (qs : Qubit[], index : Int) : ()
{
    body
    {
        H(qs[0]);
        CNOT(qs[0], qs[1]);  // ここで  $|\phi^+⟩$ ができる

        if (index == 1) {
            Z(qs[0]);
        } 
        elif (index == 2) {
            X(qs[0]);
        }
        elif (index == 3) {
            X(qs[0]);
            Z(qs[0]);
        }
    }
}
```

ようやく `if` 文が出てきましたね。

### Task 6. Greenberger–Horne–Zeilinger state

> 入力: $n$ 個の量子ビット $|00\dots0⟩$

> ゴール: GHZ 状態 $\frac{|00\dots0⟩ +|11\dots1⟩ }{\sqrt 2}$ を作る。

ベル状態に続き、GHZ 状態という名称が登場しました。全ての量子ビットが $|0⟩$、またはすべての量子ビットが $|1⟩$ という状態が重ねあわされた状態を GHZ 状態といいます。先の問題にあった $|\phi^+⟩$ のベル状態は 2 ビットの GHZ 状態とも言えそうです。

どうやって作りましょうか？作り方のアプローチも、$|\phi^+⟩$ の作成方法が参考になりそうです。$|\phi^+⟩$ は 2 ビットだったので $\rm CNOT$ を一度処理するだけでしたが、他の量子ビットに対しても同じように $\rm CNOT$ で処理を行っていけば、GHZ 状態が作成できそうです。回答は以下となります。

```cs
operation GHZ_State (qs : Qubit[]) : ()
{
    body
    {
        H(qs[0]);
        for(index in 1..(Length(qs) - 1)){
            CNOT(qs[0], qs[index]);
        } 
    }
}
```

今回は `for` 文が登場しました。

### Task 7. Superposition of all basis vectors

> 入力: $n$ 個の量子ビット $|00\dots0⟩$

> ゴール: 全ての量子ビットの重ね合わせ $\frac{|00\dots00⟩ +|00\dots01⟩ +\dots +|11\dots10⟩ +|11\dots11⟩ }{\sqrt 2^n}$ を作る。

GHZ 状態と問題が似ている気もしますが、この問題ではすべての量子ビットの組み合わせ （すなわち $2^n$ 個） を作ります。全ての確率は同じでよいので、深く考えずともすべての量子ビットをアダマール ゲートで処理すればよさそうです。先ほどと同じように `for` 文を使ってもよいのですが、Q# には `ApplyToEach` というオペレーションが用意されており、名称通り与えられた量子ビット全てに同じ操作を実施することが可能となります。`ApplyToEach` を使った回答は以下となります。


```cs
operation AllBasisVectorsSuperposition (qs : Qubit[]) : ()
{
    body
    {
        ApplyToEach(H, qs); 
    }
}
```

とってもすっきりかけていい感じですね。

### Task 8. Superposition of |0...0⟩ and given bit string

> 入力: $n$ 個の量子ビット $|00\dots0⟩$、同じ長さ $n$ を持つ古典ビット

> ゴール: $|00\dots0⟩$ と古典ビットで記されたビット列と同じ量子ビットの重ね合わせを同じ確率で作る。例えば、古典ビットが $11\dots11$ だった場合は、ゴールは  $\frac{|00\dots0⟩ +|11\dots1⟩ }{\sqrt 2}$ となる。また、古典ビットの先頭ビットは 1 であることが保証されているものとする。

外部から与えられた古典ビットに基づいて、量子ビットの状態を変化させよという問題です。何やらややこしそうな気がしますが、`古典ビットの先頭ビットは 1 であることが保証されている` という点が問題を非常に簡単化してくれています。順番に考えていきましょう。

まず、古典ビットの先頭ビットは必ず 1 なので、重ね合わせ状態を作るためには先頭の量子ビットにアダマール ゲートをつかえばよさそうです。アダマール処理後の状態は、$|00\dots0⟩$ と $|10\dots0⟩$ の重ね合わせとなります。あとは $|00\dots0⟩$ の状態を変えずに $|10\dots0⟩$ の方を入力された古典ビットと同じになるように操作をしていくことになります。先頭ビットが $1$ という状況が分かっているので、古典ビットの $i$ ビット目が 1 なら、先頭の量子ビットを制御ビットにして $i$ ビット目の（現在は $|0⟩$ である）量子ビットに $\rm CNOT$ の処理をすれば $|1⟩$ の状態が作れますね。あとはこの処理を繰り返せば回答となります。実際には、古典ビットは Bool で与えられる点に注意してください。


```cs
operation ZeroAndBitstringSuperposition (qs : Qubit[], bits : Bool[]) : ()
{
    body
    {
        H(qs[0]);   // 先頭の量子ビットをアダマールで処理
        for (index in 1..(Length(qs)-1)) {
            if(bits[index]) {           // 古典ビットが 1 の時に CNOT の処理を実施
                CNOT(qs[0], qs[index]);
            }
        }
    }
}
```

### Task 9. Superposition of two bit strings

> 入力: $n$ 個の量子ビット $|00\dots0⟩$、同じ長さ $n$ を持つ 2 つの古典ビット

> ゴール: 2 つの古典ビットで記されたビット列と同じ量子ビットの重ね合わせを作る。例えば、古典ビットが $10\dots00$ と $01\dots11$ と だった場合は、ゴールは  $\frac{|10\dots0⟩ +|01\dots1⟩ }{\sqrt 2}$ となる。2 つの古典ビットは、最低でも 1 ビットの差異があるとする。

先ほどの Task と似たような問題に見えるのですが、先ほどと比べるとこの問題はかなり面倒です。先ほどよりも面倒になってしまうポイントは 3 つあります。

1. 初期状態との重ね合わせを作るわけではないので、状態を 2 つ作らなければいけない。
2. どのビットが変わるかがわからないので、まずは差分を探さないといけない。
3. ビットの変化が $0 \rightarrow 1$ か $1\rightarrow 0$ かを考慮しないといけない。

例を挙げてみましょう。例えば古典ビットが 111 と 100 だったとします。まずは最初の古典ビットに従って $|000⟩$ を $|111⟩$ に変化させる必要があります。これは X ゲートで実現できそうです。続いて、差異が生じるビットを確認する必要があります。この例の場合は 2 ビット目が差分となるため、2 ビット目にアダマール ゲートを使いたいのですが、$|111⟩$ の 2 ビット目にアダマールゲートを使うと $|111⟩$ と $-|101⟩$ の重ね合わせとなり、位相が反転してしまいます。さらに、$-|101⟩$ を $|111⟩$ に影響を与えずに $-|100⟩$ に変化させるためには $\rm CNOT$ の逆 （制御ビットが 0 の時に作用させる）の処理を行う必要があるのですが、こうしたファンクタは現状 Q# では提供されていないため、一度対象の量子ビットを X ゲートで反転し、$\rm CNOT$ を作用させてから再度 X ゲートで反転して状態を戻すという面倒な手続きが必要となります。また、位相がずれてしまっている点も修正する必要があります。

まとめると、以下のような処理を行う必要があることがわかります。

1. 与えられた古典ビットどちらかに従って量子ビットの状態を変化させる。
2. 古典ビットの差分と変化の方向を記録する。
3. 差分が生じた点にアダマール ゲートを適用する。
4. 変化の方向に応じて以下の処理を実行する。
    - $0 \rightarrow 1$ の場合は、その他の差分に対して $\rm CNOT$ を適用する。
    - $1 \rightarrow 0$ の場合は、
        1. X ゲートで対象のビットを反転する
        2. その他の差分に対して $\rm CNOT$ を適用する
        3. 再度 X ゲートで対象のビットを反転して元に戻す
        4. Z ゲートで位相のずれを治す

回答は以下となります。

```cs
operation TwoBitstringSuperposition (qs : Qubit[], bits1 : Bool[], bits2 : Bool[]) : ()
{
    body
    {
        // 変化の生じたビットと変化の方法を保存する変数
        mutable diff = 0;
        mutable positive = false;

        // bits1 に従って量子ビットを変化させる
        for(i in 0..(Length(bits1)-1)) {
            if(bits1[i] == true) {
                X(qs[i]);
            }
        }

        // 変化の生じたビットと変化の方法を保存する
        for (i in 0..(Length(bits2)-1)) {
            if(bits1[i] != bits2[i]) {
                set diff = i;
                set positive = bits2[i];
            }
        }
        // 変化の生じたビット diff をアダマールゲートで処理し、変化が 1 -> 0 なら反転する
        H(qs[diff]);
        if(!positive) {
            X(qs[diff]);
        }

        // bits2 に従って処理する
        for (i in 0..(Length(bits2)-1)) {
            if((bits1[i] != bits2[i]) && i != diff) {
                CNOT(qs[diff], qs[i]);
            }
        }

        //後処理
        if(!positive) {
            X(qs[diff]);
            Z(qs[diff]);
        }
    }
}
```

Q# で変数を使う場合は、`mutable` で宣言し、変更時には `set` を使う必要があります。型の宣言は必要ありませんが、現時点では暗黙のキャストは行われず、型が異なる場合はすべて明示的にキャストする必要があります。また、宣言時以外に変更せずに定数として使う場合は `let` で宣言+初期化することも可能です。

### Task 10**. W state on 2^k qubits


> 入力: $n = 2^k$ 個の量子ビット $|00\dots0⟩$

> ゴール: W 状態を作る。W 状態とは、ハミング距離が 1 である（＝ どれが 1 つの量子ビットだけが 1 で、その他は 0） n 個の量子ビットが同じ確率で重ねあわされた状態をいう。例えば $n=4$ のときは
> $$ \frac {|1000⟩ + |0100⟩ + |0010⟩ +|0001⟩}{2} $$
> となる。

小手先の処理で作ることは難しそうです。8 量子ビットの時を例に地道に考えていきましょう。


```math
\begin{aligned}
00000000& \\
&\downarrow X(q[0]) \\
10000000 \\
&\downarrow H(q[1]) \\
10000000 \\
11000000 \\
&\downarrow CNOT(q[1], q[0]) \\
10000000 \\
01000000 \\ 
&\downarrow H(q[2]) \\
10000000 \\
01000000 \\ 
10100000 \\
01100000 \\ 
&\downarrow CNOT(q[2], q[0]) \\
10000000 \\
01000000 \\ 
00100000 \\
11100000 \\ 
&\downarrow CCNOT([q[0], q[1]], q[3]) \\
10000000 \\
01000000 \\ 
00100000 \\
11110000 \\ 
&\downarrow CNOT(q[3], q[0]) \\
&\downarrow CNOT(q[3], q[1]) \\
&\downarrow CNOT(q[3], q[3]) \\
10000000 \\
01000000 \\ 
00100000 \\
00010000 \\ 
&\downarrow H(q[4]]) \\
10000000 \\
01000000 \\ 
00100000 \\
00010000 \\ 
10001000 \\
01001000 \\ 
00101000 \\
00011000 \\
&\downarrow \\
\dots
\end{aligned}
```

言葉で書くと、以下の手順で W 状態が作れそうです。
1. $i$ ビット目までが W state になっているとする
2. $i+1$ ビット目をアダマール ゲートで処理する
3. $i+1$ ビット目を制御ビットとして、先頭ビットを CNOT で処理する （この時点で $i+1$ ビット目までが W State になる）
4. $i+1$ ビット目と $0<j<i$ ビットを制御ビットとして、$i+j$ ビットを CCNOT で処理する （この時点では、$i+j$ ビットは |1⟩ となるが、$i+1$ ビット目と $0<j<i$ ビット、0 ビット目にごみが残る）
5. $i+j$ ビットを制御ビットとして $i+1$ ビット目と $0<j<i$ ビット、0 ビット目 を CNOT してごみを消す
6. $2i$ ビットまでが W State になる


```cs
operation WState_PowerOfTwo (qs : Qubit[]) : ()
{
    body
    {
        let k = Floor(Log(ToDouble(Length(qs)))/Log(2.0));
        X(qs[0]);
        for(i in 0..k-1) {
            let p = Floor(PowD(2.0, ToDouble(i)));
            H(qs[p]);
            CNOT(qs[p], qs[0]);
            for(j in 1..p-1) {
                CCNOT(qs[j], qs[p], qs[p+j]);
                CNOT(qs[p+j], qs[0]);
                CNOT(qs[p+j], qs[j]);
                CNOT(qs[p+j], qs[p]);
            }
        }
    }
}
```

また、本質的な内容ではありませんが、上記では $k$ を取得するために底の変換公式を使っています。（Q# でそのまま $\log_2$ をとる方法はなさそうでした。）

### Task 11**. W state on arbitrary number of qubits

> 入力: $n$ 個の量子ビット $|00\dots0⟩$、ただし $n \in \mathbb N$

> ゴール: W 状態 $\frac{|10\dots 00⟩ + |01\dots 00⟩ + \dots + |00\dots 10⟩ +|00\dots 01⟩}{\sqrt n}$を作る。

先の問題の一般化です。先の問題は地道に変換していくアプローチで解決できましたが、この問題は難しそうです。なぜなら、アダマールゲートなどを単純に使うだけでは $\frac{1}{\sqrt n}$ という確率を作ることも ($n=2k$ という条件がない場合は) 難しいからです。

ではどういうアプローチが有効でしょうか？この問題は自力では解けなかったので `ReferenceImplementaion.qs` にある回答の解説になるのですが、Quantum Katas 全体を通じて最もエレガントといっても過言ではない回答ではないかと思います。（考えるのが好きな方は以下を読まないことをお勧めします！）

結論から言えば、この問題では再起呼び出しと $\rm Controlled$ ファンクタを組み合わせて利用します。そう、Q# では自分を再起呼び出しする際に $\rm Controlled$ ファンクタを使うということができるのです。私は思いつきませんでした。。。

一方、$\frac{1}{\sqrt n}$という確率を実現する方法は若干力業です。先の Task でやった通り、$R_y$ ゲートを使えば、$|0⟩$ を $\cos \alpha |0⟩ + \sin \alpha |1⟩$に変化させることが可能でした。今回は $\sin \alpha = \frac{1}{\sqrt n}$となればよいので、$\alpha = \sin^{-1} \frac{1}{\sqrt n}$ としてやればよさそうです。たとえば ５ ビットの場合で考えてみましょう。

$$
\begin{aligned}
|00000⟩ \rightarrow \frac{1}{\sqrt n}|10000⟩ + \sqrt{\frac{n-1}{n}}|00000⟩
\end{aligned}
$$

まずは $|10000⟩$ という状態ができました。あとは残り 4 ビットをそろえればいいのですが、せっかく作った$\frac{1}{\sqrt n}|10000⟩$という状態は触りたくありません。この状態を崩さずに $\sqrt{\frac{n-1}{n}}|00000⟩$ を処理するためにはどうすればよいでしょうか？先の問題と同様に、先頭ビットが 0 の時だけ再起処理を行えばよさそうですが、これは X ゲートで一時的に反転 → 制御ビットとして利用 → X ゲートで元に戻すということをすればいいんでしたね。この処理を行って先頭ビット以外の 4 ビットに対して同じ処理を適用すると、以下の通りとなります。

```math
\begin{align}
\sqrt{\frac{n-1}{n}}|0000⟩ &\rightarrow \sqrt{\frac{n-1}{n}}\left(\frac{1}{\sqrt{n-1}}|1000⟩ + \sqrt{\frac{n-2}{n-1}}|0000⟩\right) \\
&= \frac{1}{\sqrt n}|1000⟩ + \sqrt{\frac{n-2}{n}}|0000⟩
\end{align}
```

再起処理を行った結果、$|1000⟩$ (先頭ビットを加えれば $|01000⟩$) についても $\frac{1}{\sqrt n}$ という確率振幅を実現できました。あとは同様ですね。回答は以下になります。

```cs
operation WState_Arbitrary (qs : Qubit[]) : ()
{
    body
    {
        let N = Length(qs);
        if (N == 1) {
            // 1 ビットの場合は問答無用で |1⟩ にすればよい
            X(qs[0]);
        } else {
            // Ry で回転させて、|1⟩ となる確率を \frac{1}{\sqrt n} にする
            let theta = ArcSin(1.0 / Sqrt(ToDouble(N)));
            Ry(2.0 * theta, qs[0]);

            // |10..00⟩ という状態の確率振幅は \frac{1}{\sqrt n} にできたので、|0..00⟩ も再起処理で確率振幅を変える
            X(qs[0]);
            (Controlled WState_Arbitrary)([qs[0]], qs[1..N-1]);
            X(qs[0]);
        }
    }
    controlled auto;
}
```

ちなみに、自分で作成したオペレーションが $\rm Controlled$ ファンクタを受け付けるためには最終行にある `controlled auto;` という宣言が必要になります。これは Q# オペレーションにおいて Variant と呼ばれ、$\rm Controlled$ 以外に $\rm Adjoint$ (あるオペレーションのエルミート転置をとった操作を行う) があります。とりあえずは何か制御を行う必要があるときは宣言がいる、と覚えておきましょう。

## 最後に

これで SuperPosition は終了です。ここまでは無味乾燥とした問題が多かったですが、最後の問題なんかはぐっとくる良問でしたね。SuperPosition まで終われば、なんとなくブロッホ球上の量子ビットを操作していく感覚が身についているのでは、と思います。

次回は Measurement でお会いしましょう。