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

はじめに

CodeforcesでQ#を使ったコンテスト、Microsoft Q# Coding Contest - Summer 2018 - Warmupが開催されたので早速問題を解いてみました。

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

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

以下はあるていど量子計算の勉強をした人向けの内容になっています。
自分は主に量子コンピュータ授業 #1　量子ビットと量子ゲートシリーズを見て学びました。非常にわかりやすかったのでおすすめです

$$
\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$を使って重ね合わせ状態を作る

は基本っぽいですね

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が公開してるサンプルの中に実装した例があるので参考になります。

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#コンテスト流行ればいいですね！！