Microsoft Q# Coding Contest - Winter 2019 - その2

前回与太話だけで終わってしまったので、今回はちゃんと解説していきます。

$$ \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}} $$

A1. Generate state |00⟩ + |01⟩ + |10⟩

Aのカテゴリーは、指定されたQubitの状態を生成せよという問題になります。 これはその1問目です。

問題のタイトルで説明が完了している感じがしますが、 タイトルの通り、入力として2 Qubitの状態 $\ket{00}$ が与えられるので、 出力として $\frac{1}{\sqrt{3}}(\ket{00}+\ket{01}+\ket{10})$ を生成せよという問題です。

いわゆる3状態のW stateに似たものを作ればいいのですが、 前回のA4の問題が $2^{k}$ 状態のW stateを作れというもので、 これが2のべき乗の場合は割と簡単にできるのですが、3状態というのは案外作りづらくなっています。 前回のAのラストの問題よりも難しいのが今回の最初の問題に投入されたことで、 今回の難易度の向上が見て取れます。

ところで僕は個人的に前回の問題を$2^{k}$ 状態を作れというところを$k$ 状態を作れという風に読み間違いをしていて、 なぜかすでに問題が解けていたので、そこから答えを持ってきました。

やり方としてはいくつかあると思いますが、まず簡単な方法から。 この問題では測定が制限されていない(ほかの問題には測定が行えないものもある)ので、 測定を行うとシンプルに解くことができます。

まず、3状態の重ね合わせ作らなければならないので、入力の2つのQubitそれぞれにHadamardゲート(H)を使います。 そうすればとりあえず4状態の重ね合わせが得られます。

$$H(\ket{0}) H(\ket{0}) = \frac{1}{2}(\ket{00}+\ket{01}+\ket{10}+\ket{11})$$

operation Solve (qs : Qubit[]) : Unit {
    H(qs[0]);
    H(qs[1]);
}

ここからなんとか右端の $\ket{11}$ を消すことを考えます。 qs[0]qs[1]の状態を確定させずに$\ket{11}$の状態を判別するために、もう1 Qubit導入して、 そのQubitと$\ket{11}$の状態をToffoli(CCNOT)ゲートを用いてentangleさせます。

operation Solve (qs : Qubit[]) : Unit {
    H(qs[0]);
    H(qs[1]);
    using (r = Qubit()) {
        CCNOT(qs[0], qs[1], r);
        Reset(r); // Qubit解放前に |0> にしておく必要があるのでこれがいる
    }
}

r はqs=${\ket{11}}$の時のみ$\ket{1}$になるので、CCNOT後の状態は $$ \frac{1}{2}(\ket{000}+\ket{010}+\ket{100}+\ket{111}) $$ になります。

ここでrを測定します。0が得られれば、qsの状態は、$ \ket{00}$, $\ket{01}$, $\ket{10} $ の等確率な重ね合わせになるので、 これはまさに求めたい結果になります。 1が得られてしまった場合、qs=$\ket{11}$で確定してしまうので、これは望まぬ状態です。 望まないので、もう一度やり直します。

1回の試行あたり$\frac{3}{4}$の確率で正解が得られるので、これを繰り返せば、TLEまでには十分な確率で答えが得られるはず、ということになります。 全体のコードは次の通り。

operation Solve (qs : Qubit[]) : Unit {
    repeat {
        ResetAll(qs);
        H(qs[0]);
        H(qs[1]);
        mutable ok = false;
        using (r = Qubit()) {
            CCNOT(qs[0], qs[1], r);
            set ok = M(r) == Zero;
            Reset(r);
        }
    } until(ok)
    fixup{}
}

これが測定を用いた解法になりますが、測定を用いてしますとadjointにできなくなったりあんまり嬉しくないみたいなので、 測定を用いない解法も示しておきます。測定に頼らないので、余計なQubitを使わず、必ず1回で望みの状態が作れます。

まず状態 $\ket{0}$ から、$\sqrt{\frac{2}{3}}\ket{0}+\sqrt{\frac{1}{3}}\ket{1}$ を作り出します。 このためには、ブロッホ球でいうところのY軸方向に回転させればよさそうです。 $\ket{0}$をY軸方向にΘ回転させると$\cos{\frac{\theta}{2}} \ket{0}-\sin{\frac{\theta}{2}}\ket{1}$になるので、$ \theta = \cos^{-1}({\sqrt{\frac{2}{3}}}) * 2$ とすれば そうなりそうです。

そこから、$\ket{0}$の部分を均等に分割すれば、等確率な3状態が作れそうです。 Controlled Hゲートを使えばよいですが、$\ket{1}$ ではなく、$\ket{0}$でコントロールしたいので、 (ControlledOnInt(0, H))([qs[0]], qs[1]) とします。

この時点で $ \frac{1}{\sqrt{3}}(\ket{00}+\ket{01}+\ket{10}) $ の状態が出来上がるので、これで完成です。

operation Solve (qs : Qubit[]) : Unit {
    Ry(ArcCos(Sqrt(2.0/3.0))*2.0, qs[0]);
    (ControlledOnInt(0, H))([qs[0]], qs[1]);
}

コードとしてはこちらの方が短いですね。

A2. Generate equal superposition of four basis states

N Qubitのゼロ状態 $\ket{0...0}$ と、basis stateを表す4つの古典ビットのベクトルが与えられるので、

$$ \ket{S} = \frac{1}{2}(\ket{\psi_0}+\ket{\psi_1}+\ket{\psi_2}+\ket{\psi_3}) $$

という状態を作れ、という問題。こちらの方がA1よりも簡単な気がしますね。

とりあえず4つの状態を重ね合わせを作らないといけないので、なにはなくともHadamardゲートを2回使います。 使うのですが、そのまま使うと面倒なので、Hadamardゲートを使う用の余分なQubitを2つ作ることにします。

operation Solve (qs : Qubit[], bits : Bool[][]) : Unit {
    using (rs = Qubit[2]) {
        H(rs[0]);
        H(rs[1]);
        ...
    }
}

これで状態は $$ \frac{1}{2}(\ket{0...000} + \ket{0...001} + \ket{0...010} + \ket{0...011}) $$ になるので、後ろ2 Qubitでコントロールすれば前のQubitは好きなようにいじれるようになります。

operation Solve (qs : Qubit[], bits : Bool[][]) : Unit {
    using (rs = Qubit[2]) {
        H(rs[0]);
        H(rs[1]);

        for (i in 0..n-1) {
            for (j in 0..3) {
                if (bits[j][i]) {
                    (ControlledOnInt(j, X))(rs, qs[i]);
                }
            }
        }
        ...
    }
}

末尾の2 Qubit(= rs) がjの時にbits[j][i]が立っているなら、qs[i]Xをかけるというコードになります。

これで状態は $$ \frac{1}{2}(\ket{\psi_0 00} + \ket{\psi_1 01} + \ket{\psi_2 10} + \ket{\psi_3 11}) $$ になるのですが、 うしろに余計なものがくっついてしまっているので、すべて $\ket{00}$にしてやる必要があります。 測定などを行ってしまうとエンタングルしている部分が台無しになってしまうので、 コントロールゲートで何とかします。

といっても、$\psi_i$はすべて異なることが保証されているので、今度は$\ket{\psi_i}$の部分でコントロールして後ろの部分を消してやればよいです。

operation Solve (qs : Qubit[], bits : Bool[][]) : Unit {
    using (rs = Qubit[2]) {
        H(rs[0]);
        H(rs[1]);

        for (i in 0..n-1) {
            for (j in 0..3) {
                if (bits[j][i]) {
                    (ControlledOnInt(j, X))(rs, qs[i]);
                }
            }
        }

        (ControlledOnBitString(bits[1], X))(qs, rs[0]);
        (ControlledOnBitString(bits[2], X))(qs, rs[1]);
        (ControlledOnBitString(bits[3], X))(qs, rs[0]);
        (ControlledOnBitString(bits[3], X))(qs, rs[1]);
    }
}

ControlledOnBitString というおあつらえ向きな関数があるので、これを使えばすっきり書けます。 これで状態が $$ \frac{1}{2}(\ket{\psi_0 00} + \ket{\psi_1 00} + \ket{\psi_2 00} + \ket{\psi_3 00}) $$ になって、余分に確保したQubitはすべて$\ket{00}$になったので、解放されて、消えて、求める状態が残ります。