日々drdrする人のメモ

今日もdrdr、明日もdrdr

Microsoft Q# Coding Contest - Summer 2018 - Warmup

Codeforcesで行われたコンテスト
codeforces.com

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 operationH 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}状態が変化する。

  •  {P = |+ \rangle}
    •  {Q = |0 \rangle}なら、 {P \otimes Q}は状態 {|B_0 \rangle}に変化
    •  {Q = |1 \rangle}なら、 {P \otimes Q}は状態 {|B_2 \rangle}に変化
  •  {P = |- \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問題の一般化。
1つの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 = |+ \rangle}
    •  {P \otimes Q = |B_0 \rangle}なら、 {Q}は状態 {|0 \rangle}に変化
    •  {P \otimes Q = |B_2 \rangle}なら、 {Q}は状態 {|1 \rangle}に変化
  •  {P = |- \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により判定できるらしい。

  1. 状態 {|0 \rangle} {N}個のqubitを含む {x}、状態 {|1 \rangle}の1個のqubit  {y}を用意
  2. 全てのqubitにH operationを適用
  3.  {x}を入力、 {y}を出力としてquantum oracle  {f}に与える
  4.  {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;
        }
    }
}