Microsoft Q# Coding Contest - Summer 2018 - Warmupの問題を解いてみた

#はじめに

CodeforcesでQ#を使ったコンテスト、[Microsoft Q# Coding Contest - Summer 2018 - Warmup](https://codeforces.com/contest/1001)が開催されたので早速問題を解いてみました。

まだコンテスト期間中ですが、解答などをシェアしても良いようなのでこの記事を公開しています。
一応ジャッジは全部通ったのでコード自体はあってると思います。

私はこのコンテストが開催されると知ってから量子計算の勉強を始めた初心者なので、説明が適当だったり間違いも含んでいると思いますが参考になる方がいれば幸いです。


以下はあるていど量子計算の勉強をした人向けの内容になっています。
自分は主に[量子コンピュータ授業 #1　量子ビットと量子ゲート](https://www.youtube.com/watch?v=R2fyLl7KZXM&t=)シリーズを見て学びました。非常にわかりやすかったのでおすすめです:grinning:


$$
\def\bra#1{\mathinner{\left\langle{#1}\right|}}
\def\ket#1{\mathinner{\left|{#1}\right\rangle}}
\def\braket#1#2{\mathinner{\left\langle{#1}\middle|#2\right\rangle}}
$$

# A. Generate plus state or minus state

`sign`が与えられるので`1`なら$\frac{1}{\sqrt 2}(\ket{0}+\ket{1})$、`-1`なら$\frac{1}{\sqrt 2}(\ket{0}-\ket{1})$を`q`に
作る問題です。`q`の初期状態は$\ket{0}$です。

この問題は、
$H\ket{0}=\frac{1}{\sqrt 2}(\ket{0}+\ket{1})$
$H\ket{1}=\frac{1}{\sqrt 2}(\ket{0}-\ket{1})$
を知っていれば解くことが出来ます。

`sign`が`1`ならそのまま`H(q)`を、`-1`なら$X$を使って`q`を$\ket{1}$にしてから$H$に入れれば良いので`H(X(q))`をすればよいです。

* $X$を使って$\ket{0}$を$\ket{1}$にする
* $H$を使って重ね合わせ状態を作る

は基本っぽいですね:grinning:

```
namespace Solution {
    open Microsoft.Quantum.Primitive;
    open Microsoft.Quantum.Canon;

    operation Solve (q : Qubit, sign : Int) : ()
    {
        body
        {
            if (sign == 1) {
                H(q);
            } else {
                X(q);
                H(q);
            }
        }
    }
}
```

# B. Generate Bell state

`index`が与えられるので対応するBell Stateを`qs`＝$\ket{00}$に作る問題です。

* $\ket{B_0}=\frac{1}{\sqrt 2}(\ket{00}+\ket{11})$
* $\ket{B_1}=\frac{1}{\sqrt 2}(\ket{00}-\ket{11})$
* $\ket{B_2}=\frac{1}{\sqrt 2}(\ket{01}+\ket{10})$
* $\ket{B_3}=\frac{1}{\sqrt 2}(\ket{01}-\ket{10})$

Bell Stateでは**qubit**一つが確定するともう片方の**qubit**も確定します。

例えば、2つの**qubit**が$\ket{B_0}$だとわかっていて最初の**qubit**を観測したところ`1`だったとします。
$\ket{B_0}=\frac{1}{\sqrt 2}(\ket{00}+\ket{11})$より$\ket{B_0}$は$\ket{00}$と$\ket{11}$の等確率の重ね合わせですが最初の**qubit**が`1`だった場合$\ket{11}$しかありえません。よってもう片方の**qubit**は観測するまでもなく`1`であることがわかります。

まず、$H$を使って**1qubit**の重ね合わせを作ります。
そして$CNOT$を使ってもう片方の**qubit**との関係を作ってあげます。
最初に$X$を使って初期値を設定してやると`index`に対応する$Bell$状態になります。

```
namespace Solution {
    open Microsoft.Quantum.Primitive;
    open Microsoft.Quantum.Canon;

    operation Solve (qs : Qubit[], index : Int) : ()
    {
        body
        {
            let x = qs[0];
            let y = qs[1];

            if (index == 1) {
                X(x);
            }

            if (index == 2) {
                X(y);
            }

            if (index == 3) {
                X(x);
                X(y);
            }

            H(x);
            CNOT(x, y);
        }
    }
}
```

# C. Generate GHZ state

ある長さの**qubit**が与えられるのでその長さのGreenberger–Horne–Zeilinger Stateを作る問題です。
$\ket{GHZ}=\frac{1}{\sqrt 2}(\ket{0\dots0}+\ket{1\dots1})$です。

GHZ Stateは初耳でしたが、式からある一つの**qubit**が決まればほか全ての**qubit**も同じ値に決まる事がわかります。
$H$で重ね合わせを作り$CNOT$でどんどん残りの**qubit**をつなげていきます。

```
namespace Solution {
    open Microsoft.Quantum.Primitive;
    open Microsoft.Quantum.Canon;

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

# D. Distinguish plus state and minus state

$\frac{1}{\sqrt 2}(\ket{0}+\ket{1})$か$\frac{1}{\sqrt 2}(\ket{0}-\ket{1})$のである`q`が与えられるのでどちらか判定する問題です。操作が終わったあとに`q`がどうなっていてもかまいません。

`q`を測定して良いことに注意すると、何か操作をして`q`を$\ket{0}$か$\ket{1}$にして測定すれば判別できることがわかります。
ここで
$H\ket{0} = \frac{1}{\sqrt 2}(\ket{0}+\ket{1})$
$H\ket{1} = \frac{1}{\sqrt 2}(\ket{0}-\ket{1})$
$HH=1$
と言うことを思い出すと、`q`に$H$を通すと$\ket{0}$か$\ket{1}$になることがわかります。
あとは$M$で測定すればよいです。

* $H$で作った重ね合わせ状態はもう一回$H$を使うことでもとに戻すことができる

これも基本っぽいので覚えておきましょう。

```
﻿namespace Solution {
    open Microsoft.Quantum.Primitive;
    open Microsoft.Quantum.Canon;

    operation Solve (q : Qubit) : Int
    {
        body
        {
            H(q);
            let m = M(q);
            if (m == Zero) {
                return 1;
            } else {
                return -1;
            }
        }
    }
}
```

# E. Distinguish Bell states

Bell Stateの一つである`qs`が与えられるのでどのBell Stateか判定する問題です。

* $\ket{B_0}=\frac{1}{\sqrt 2}(\ket{00}+\ket{11})$
* $\ket{B_1}=\frac{1}{\sqrt 2}(\ket{00}-\ket{11})$
* $\ket{B_2}=\frac{1}{\sqrt 2}(\ket{01}+\ket{10})$
* $\ket{B_3}=\frac{1}{\sqrt 2}(\ket{01}-\ket{10})$

Bell Stateを作るのに$H$と$CNOT$を順に通したことを思い出すと、今度は逆に$CNOT$と$H$の順番で通すともとに戻りそうな感じがします。

1番目の**qubit**を$x$、2番目の**qubit**を$y$とします。

まず符号を無視して`qs`が$\frac{1}{\sqrt 2}(\ket{00}\pm\ket{11})$か$\frac{1}{\sqrt 2}(\ket{01}\pm\ket{10})$かを判別することを考えます。これは$x=y$か判別できればよいです。ここで$CNOT(x, y)$を考えると、`qs`が$\ket{B_0}$か$\ket{B_1}$のとき$0$,$\ket{B_2}$か$\ket{B_3}$のとき$1$になることがわかります。

つぎに符号が$+$か$-$かを判別します。これはD問題でもやりましたが$H$を使えばよいです。

```
﻿namespace Solution {
    open Microsoft.Quantum.Primitive;
    open Microsoft.Quantum.Canon;

    operation Solve (qs : Qubit[]) : Int
    {

        body
        {
            mutable sum = 0;
            let x = qs[0];
            let y = qs[1];
            
            CNOT(x, y);
            H(x);

            let s = M(x);
            let t = M(y);

            if (s == One) {
                set sum = sum + 1;
            }
            if (t == One) {
                set sum = sum + 2;
            }
            return sum;
        }
    }
}
```

# F. Distinguish multi-qubit basis states

`qs`は`bits0`か`bits1`のどちらかに収束しているのでどちらか判定する問題です。操作後の`qs`の状態は問いません。

実際にqsを測定して`bits0`,`bits1`どちらに等しいか普通に比較すれば大丈夫です。
なんか普通の競プロみたいですね。

```
namespace Solution {
    open Microsoft.Quantum.Primitive;
    open Microsoft.Quantum.Canon;

    operation Solve (qs : Qubit[], bits0 : Bool[], bits1 : Bool[]) : Int
    {
        body
        {
            mutable xs = new Bool[Length(qs)];

            for (i in 0..Length(qs)-1) {
                let m = M(qs[i]);
                if m == Zero {
                    set xs[i] = false;
                } else {
                    set xs[i] = true;
                }
            }

            mutable flag = true;

            for (i in 0..Length(qs)-1) {
                set flag = flag && (xs[i] == bits0[i]);
            }

            if flag {
                return 0;
            } else {
                return 1;
            }
        }
    }
}
```

# G. Oracle for f(x) = k-th element of x

$f(x)=x_k$であるOracleを作る問題です。

Oracleとは
$O\ket{x}\ket{y} = \ket{x}\ket{y\oplus f(x)}$
なので、代入してやると
$O\ket{x}\ket{y} = \ket{x}\ket{y\oplus x_k}$
です。
2の法の世界では$NOT$が$+1$になることを思い出すと$CNOT$を使えば良いことがわかります。


```
namespace Solution {
    open Microsoft.Quantum.Primitive;
    open Microsoft.Quantum.Canon;

    operation Solve (x : Qubit[], y : Qubit, k : Int) : ()
    {
        body
        {
            CNOT(x[k], y);
        }
    }
}
```

# H. Oracle for f(x) = parity of the number of 1s in x

$f(x)=\sum_i{x_i} \mod 2$であるOracleを作る問題です。

$CNOT$を使ってすべての$x$を$y$に足してやればいいです。

```
namespace Solution {
    open Microsoft.Quantum.Primitive;
    open Microsoft.Quantum.Canon;

    operation Solve (x : Qubit[], y : Qubit) : ()
    {
        body
        {
            for (i in 0..Length(x)-1) {
                CNOT(x[i], y);
            }
        }
    }
}
```

# I. Deutsch-Jozsa algorithm

入力サイズが`N`で出力が{0,1}でConstantもしくはBalancedのOracle、`Uf`が与えられるので、`Uf`がConstantか判定しなさい。ただし`Uf`を呼べるのは一回だけです。という問題です。

これはタイトルの通りDeutsch-Jozsaのアルゴリズムそのままです。
実はMicrosoftが公開してるサンプルの中に[実装した例](https://github.com/Microsoft/Quantum/blob/master/Samples/SimpleAlgorithms/SimpleAlgorithms.qs)があるので参考になります。

```
namespace Solution {
    open Microsoft.Quantum.Primitive;
    open Microsoft.Quantum.Canon;

    operation Solve (N : Int, Uf : ((Qubit[], Qubit) => ())) : Bool
    {
        body
        {
            mutable resultArray = new Result[N]; 

            using (qs = Qubit[N+1]) {
                let x = qs[0..N-1];
                let y = qs[N];

                X(y);
                ApplyToEach(H, x);
                H(y);

                Uf(x, y);

                ApplyToEach(H, x);

                for (idx in 0..(N - 1)) {
                    set resultArray[idx] = MResetZ(x[idx]);
                }

                Reset(y);
            }
            return ForAll(IsResultZero, resultArray);
        }
    }
}
```

# おわりに

Q#コンテスト流行ればいいですね！！