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

今回はC1からです。

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

C1. Alternating bits oracle

問題

次のようなN($1\le N \le 7$) Qubitの量子オラクルを実装せよ。

• $\vec{x}の隣接するビットに00か11が含まれていないなら f(\vec{x}) = 1$

なお、adjoint autoでadjointが生成できなければならない。

解答

C問題シリーズは量子オラクルを実装するものです。 量子オラクルというのは、このあたりに詳しいです。 要するに、 $$O(\ket{x}\otimes\ket{y}) = \ket{x}\otimes\ket{y\oplus f(x)}$$ なる$O$を実装せよというものです。

問題の解き方ですが、隣接するビットに00か11が含まれていないものというのは、 0101010...か101010...のような、1と0が交互に現われるものの2通りしかありません。 なので、Nビットのそういうパターン2種類について、それぞれのビット列に対してControlled XすればOKです。

operation Solve (x : Qubit[], y : Qubit) : Unit {
    body (...)  {
        let n = Length(x);
        let pat = 0x55555555;
        (ControlledOnInt(pat % (1<<<n), X))(x, y);
        (ControlledOnInt((pat>>>1) % (1<<<n), X))(x, y);
    }
    adjoint auto;
}

C2. "Is the bit string periodic?" oracle

問題

次のようなN($1\le N \le 7$) Qubitの量子オラクルを実装せよ。

• $\vec{x}がperiodicなら、f(\vec{x}) = 1$

あるビット列がperiodicであるとは、ある$P (1 \le P \le N-1)$があって、 全ての$i\in[0,N-P-1]$に対して$x_i=x_{i+P}$であるようなものである。 $P$は$N$を割り切らなくても良い。例えば"01010"は$P=2$でperiodicである。

解答

いいんですかねこんなので。 通ってしまったものは仕方が無い。

operation Solve (x : Qubit[], y : Qubit) : Unit {
    body (...) {
        let tbl =
            [[1,2]
            ,[1,3,4,6]
            ,[1,3,7,8,12,14]
            ,[1,3,5,7,11,15,16,20,24,26,28,30]
            ,[1,3,5,7,11,13,15,19,23,31,32,40,44,48,50,52,56,58,60,62]
            ,[1,3,5,7,9,11,13,15,19,21,23,27,29,31,35,39,43,47,55,63,64,72,80,84,88,92,96,98,100,104,106,108,112,114,116,118,120,122,124,126]];
        X(y);
        let n = Length(x);
        for (i in 0..Length(tbl[n-2])-1) {
            (ControlledOnInt(tbl[n-2][i], X))(x, y);
        }
    }
    adjoint auto;
}

C3. "Is the number of ones divisible by 3?" oracle

問題

次のようなN($1\le N \le 9$) Qubitの量子オラクルを実装せよ。

• $\vec{x}$中の立っているビットの数が3で割り切れるなら$f(\vec{x})=1$、それ以外なら$f(\vec{x})=0$

解答

C2と同様にテーブルでやってみたところ、サイズが大きくて時間がかかりTLEになりました。 なのでまともに解きます。

立っているビットの数を数えるには、加算器を実装します。 加算結果は最大で9になるので、4ビット必要です。 なので、4ビット＋1ビットの加算器を実装することになります。

実装するものを、[a0, a1, a2, a3] + b = [c0, c1, c2, c3] とすれば、

c3 = a3 ^ (b & a0 & a1 & a2)
c2 = a2 ^ (b & a0 & a1)
c1 = a1 ^ (b & a0)
c0 = a0 ^ b

となります（桁上がりするにはそれより前の桁が全部1になっていないといけないので）。 これをもとに、xのうち立っているビットを数える操作をQ#で書くと、

// qs: 数えた結果
// x: 入力
operation Count(qs: Qubit[], x: Qubit[]): Unit {
    body(...) {
        let n = Length(x);
        let a0 = qs[0];
        let a1 = qs[1];
        let a2 = qs[2];
        let a3 = qs[3];

        for (i in 0..n-1) {
            let b = x[i];
            (ControlledOnBitString([true, true, true, true], X))([b, a0, a1, a2], a3);
            (ControlledOnBitString([true, true, true], X))([b, a0, a1]2);
            CCNOT(b, a0, a1);
            CNOT(b, a0);
        }
    }
    // 全体をAdjacentにしないといけないのでこれもAdjacentにしないといけない
    adjoint auto;
}

このようになります。カウントができれば、あとはこれが3の倍数かどうかチェックする関数を書きます。入力のレンジが0～9なので、べた書きすればよいでしょう。

// qsは使わないけど形合わせ（後述）
operation Check(qs: Qubit[], y: Qubit): Unit {
    body(...) {
        (ControlledOnInt(0, X))(qs, y);
        (ControlledOnInt(3, X))(qs, y);
        (ControlledOnInt(6, X))(qs, y);
        (ControlledOnInt(9, X))(qs, y);
    }
    adjoint auto;
}

これを組み合せれば、

operation Solve (x : Qubit[], y : Qubit) : Unit {
    body (...) {
        using (qs = Qubit[4]) {
            Count(qs, x);
            Check(qs, y);
        }
    }
    adjoint auto;
}

となりますが、usingブロックの終了時点で確保したQubitはゼロ状態に戻しておかなければならないので、Countの逆操作を行う必要がります。これを手で書くのは面倒ですが、Q#には逆操作をadjoint autoで自動で作る機能がありますし、しかも今回の問題はそれを要求されているので、それを使えばよさそうです。

operation Solve (x : Qubit[], y : Qubit) : Unit {
    body (...) {
        using (qs = Qubit[4]) {
            Count(qs, x);
            Check(x, y);
            Adjoint Count(qs, x);
        }
    }
    adjoint auto;
}

ところで、こういう何らかの操作Aを行って、別の操作Bを行って、それからAで行った操作を元に戻す、という一連の操作はよく出てくるみたいなので、それを行うためのWithAという関数が用意されています。これを使えば、全体のコードを次のように書けます（WithAを使うためにCountとCheckの引数をそろえています）。

operation Solve (x : Qubit[], y : Qubit) : Unit {
    body (...) {
        using (qs = Qubit[4]) {
            WithA(Count, Check, (qs, x, y));
        }
    }
    adjoint auto;
}

operation Count(qs: Qubit[], x: Qubit[], y: Qubit): Unit {
    body(...) {
        let n = Length(x);
        let a0 = qs[0];
        let a1 = qs[1];
        let a2 = qs[2];
        let a3 = qs[3];

        for (i in 0..n-1) {
            let b = x[i];
            (ControlledOnBitString([true, true, true, true], X))([b, a0, a1, a2], a3);
            (ControlledOnBitString([true, true, true], X))([b, a0, a1]2);
            CCNOT(b, a0, a1);
            CNOT(b, a0);
        }
    }
    adjoint auto;
}

operation Check(qs: Qubit[], x: Qubit[], y: Qubit): Unit {
    body(...) {
        (ControlledOnInt(0, X))(qs, y);
        (ControlledOnInt(3, X))(qs, y);
        (ControlledOnInt(6, X))(qs, y);
        (ControlledOnInt(9, X))(qs, y);
    }
    adjoint auto;
}

今回は割と簡単でした。