Microsoft Q# Coding Contest - Summer 2018 - Warmup - 日々ｄｒｄｒする人のメモ

Microsoftによって作られた量子プログラミング言語Q#を使ったコンテスト

面白そうなので解いた。
Warmupなので練習コンテスト。本番は今週の土曜日1:00から3日間らしい(気が向いたら出よう)。

環境準備

今回の環境はUbuntu 16.04。Visual Studio Code上で書いた。

これを参考に環境準備

まず、CLI上に.NET環境(dotnet)を用意する
.NET and C# - Get started in 10 minutes

$ wget -q https://packages.microsoft.com/config/ubuntu/16.04/packages-microsoft-prod.deb
$ sudo dpkg -i packages-microsoft-prod.deb

$ sudo apt-get install apt-transport-https
$ sudo apt-get update
$ sudo apt-get install dotnet-sdk-2.1

次にMicrosoft Quantum Development Kitをインストール
Setting up the Q# development environment | Microsoft Docs

$ dotnet new -i "Microsoft.Quantum.ProjectTemplates::0.2.1806.2802-preview"

Visual Studio CodeにQ#拡張機能があるらしいので入れた。
Microsoft Quantum Development Kit - Visual Studio Marketplace

Q#のQuick Start
Write a quantum program | Microsoft Docs

コンテスト問題

基本の問題のみ。
ただし、量子プログラミング言語では量子ビット(qubit)を扱うため、量子ビットを少し理解しておく必要がある。
当然だけど、Q#の言語仕様がわからないのでリファレンスを参照しながら書いた。

あと、ローカルでテストしながら解いたけど、コードに特定の入力を与えるためにある程度コードを書かないといけないのが少しつらかった。

以下、かなり雑な解法説明。

公式解説はこれ

A問題: Generate plus state or minus state

状態 ${|0 \rangle}$ のqubitとsignが与えられ、

sign = 1 であれば ${| + \rangle = \frac{1}{\sqrt{2}}(|0 \rangle + |1 \rangle)}$
sign = -1 であれば ${| - \rangle = \frac{1}{\sqrt{2}}(|0 \rangle - |1 \rangle)}$

にqubitの状態を変化させる問題。

X operationとH operationを使えばできる。
${| 1 \rangle = X(| 0 \rangle)}$
${| 0 \rangle = X(| 1 \rangle)}$
${| + \rangle = H(|0 \rangle)}$
${| - \rangle = H(|1 \rangle)}$

提出コード: http://codeforces.com/contest/1001/submission/39794453

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

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

B問題: Generate Bell state

状態 ${|0 \rangle}$ の2個のqubitとindexが与えられ、

index = 0 であれば ${|B_0 \rangle = \frac{1}{\sqrt{2}} ( |00 \rangle + |11 \rangle )}$
index = 1 であれば ${|B_1 \rangle = \frac{1}{\sqrt{2}} ( |00 \rangle - |11 \rangle )}$
index = 2 であれば ${|B_2 \rangle = \frac{1}{\sqrt{2}} ( |01 \rangle + |10 \rangle )}$
index = 3 であれば ${|B_3 \rangle = \frac{1}{\sqrt{2}} ( |01 \rangle - |10 \rangle )}$

にqubitの状態を変化させる問題。

CNOT operationを使えば各状態に変化させられる。
${CNOT(P, Q)}$ を計算する場合、 ${P, Q}$ の状態によって以下のように ${Q}$ 状態が変化する。

- ${Q = |0 \rangle}$ なら、 ${P \otimes Q}$ は状態 ${|B_0 \rangle}$ に変化
- ${Q = |1 \rangle}$ なら、 ${P \otimes Q}$ は状態 ${|B_2 \rangle}$ に変化
- ${Q = |0 \rangle}$ なら、 ${P \otimes Q}$ は状態 ${|B_1 \rangle}$ に変化
- ${Q = |1 \rangle}$ なら、 ${P \otimes Q}$ は状態 ${|B_3 \rangle}$ に変化

提出コード: http://codeforces.com/contest/1001/submission/39796595

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

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

            if(index >= 2) {
                X(q1);
            }
            if(index % 2 == 1) {
                X(q0);
            }
            H(q0);
            CNOT(q0, q1);
        }
    }
}

C問題: Generate GHZ state

${N}$ 個のqubitが与えられ、これらの状態を ${|GHZ \rangle = \frac{1}{\sqrt{2}} ( |0...0 \rangle + |1...1 \rangle )}$ にする問題。A問題、B問題の一般化。
１つのqubitを ${|+ \rangle}$ にして、残りの ${|0 \rangle}$ をCNOTで状態を変化させるのみ。

提出コード: http://codeforces.com/contest/1001/submission/39797122

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

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

D問題: Distinguish plus state and minus state

与えられたqubitの状態が ${| + \rangle}$ か ${| - \rangle}$ かを判定する。
${H \circ H = I}$ であるため、 ${H(| + \rangle) = | 0 \rangle}$ 、 ${H(| - \rangle) = | 1 \rangle}$ で判別する。

提出コード: http://codeforces.com/contest/1001/submission/39797759

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

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

E問題: Distinguish Bell States

与えられた2個のqubitの状態が ${|B_0 \rangle }$ 、 ${|B_1 \rangle }$ 、 ${|B_2 \rangle }$ 、 ${|B_3 \rangle }$ かを判定する。
CNOT operationとH operationでうまく判別する。
${CNOT(P, Q)}$ を計算する場合、 ${P, Q}$ の状態によって以下のように ${Q}$ の状態が変化する。(B問題の逆)

- ${P \otimes Q = |B_0 \rangle}$ なら、 ${Q}$ は状態 ${|0 \rangle}$ に変化
- ${P \otimes Q = |B_2 \rangle}$ なら、 ${Q}$ は状態 ${|1 \rangle}$ に変化
- ${P \otimes Q = |B_1 \rangle}$ なら、 ${Q}$ は状態 ${|0 \rangle}$ に変化
- ${P \otimes Q = |B_3 \rangle}$ なら、 ${Q}$ は状態 ${|1 \rangle}$ に変化

${P}$ と状態が変化した ${Q}$ からindexを計算する。

提出コード: http://codeforces.com/contest/1001/submission/39798093

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

    operation Solve (qs : Qubit[]) : Int
    {
        body
        {
            mutable res = 0;
            let q0 = qs[0];
            let q1 = qs[1];
            CNOT(q0, q1);
            if (M(q1) == One) {
                set res = res + 2;
            }
            H(q0);
            if (M(q0) == One) {
                set res = res + 1;
            }
            return res;
        }
    }
}

F問題: Distinguish multi-qubit basis states

0もしくは1の基底状態を持つ ${N}$ 個のqubitと、 ${N}$ 個のbool値を持つbits0, bits1が与えられる。各 ${i}$ 番目のqubitはbits0[i], bits1[i]のどちらか一方のみの各bool値と一致する。どちらに一致するかを計算する。
これは各bool値とqubitを比較して一方が一致しなくなったら、正しい方を出力するだけ。

提出コード: http://codeforces.com/contest/1001/submission/39798458

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

    operation Solve (qs : Qubit[], bits0 : Bool[], bits1 : Bool[]) : Int {
        body {
            let n = Length(qs);
            for (i in 0..n-1) {
                if (bits0[i] != bits1[i]) {
                    if(M(qs[i]) == One) {
                        if(bits1[i]) {
                            return 1;
                        }
                        return 0;
                    } else {
                        if(bits1[i]) {
                            return 0;
                        }
                        return 1;
                    }
                }
            }
            return -1;
        }
    }
}

G問題: Oracle for f(x) = k-th element of x

${N}$ 個のqubitを引数に取るquantum oracleとして ${f(x) = x_k}$ (つまりk番目のqubitを返す)を計算する。
k番目の要素を返せばいいのかなと思ってReset -> CNOTで書いたらWA出まくって悩んで結局Editorialを見る。
Resetなしでただ単純にCNOTだけでよかったっぽい。

提出コード: http://codeforces.com/contest/1001/submission/39853159

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

    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

${N}$ 個のqubitを引数に取るquantum oracleとして ${f(x) = \sum_i x_i \text{mod} 2}$ を計算する。
G問題の応用問題みたいなものなので瞬殺。

提出コード: http://codeforces.com/contest/1001/submission/39853214

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

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

I問題: Deutsch-Jozsa algorithm

関数 ${f: \{0, 1\}^N \rightarrow \{0, 1\}}$ を計算するquantum oracleが与えられる。この関数を1回だけ呼び出して定数関数かbalancedに0,1になる関数かを判定する問題。
この問題は問題名のDeutsch-Jozsa algorithmにより判定できるらしい。

状態 ${|0 \rangle}$ の ${N}$ 個のqubitを含む ${x}$ 、状態 ${|1 \rangle}$ の1個のqubit ${y}$ を用意
全てのqubitにH operationを適用
${x}$ を入力、 ${y}$ を出力としてquantum oracle ${f}$ に与える
${x}$ に含まれるqubitにH operationを適用した上で、全て0か判定 (0であれば定数関数、そうでなければbalanced function)

提出コード: http://codeforces.com/contest/1001/submission/39871458

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

    operation Solve (N : Int, Uf : ((Qubit[], Qubit) => ())) : Bool
    {
        body
        {
            mutable v = true;
            using (register0 = Qubit[N]) {
                let qs = register0;
                for (i in 0..N-1) {
                    H(qs[i]);
                }
                using (register1 = Qubit[1]) {
                    let qn = register1[0];
                    X(qn);
                    H(qn);
                    Uf(qs, qn);

                    for (i in 0..N-1) {
                        H(qs[i]);
                        if (M(qs[i]) == One) {
                            set v = false;
                        }
                    }
                    Reset(qn);
                }
                ResetAll(register0);
            }
            return v;
        }
    }
}