◇◇Microsoft Q# Coding Contest - Winter 2019 C3 - "Is the number of ones divisible by 3?" oracle◇◇

https://codeforces.com/contest/1116/problem/C3

N桁の量子状態$\ket{x}$とqubit$\ket{y}$が与えられる。$\ket{y}$をオラクルqubitとして、$\ket{x}$に含まれる$\ket{1}$の数が3で割り切れる場合のみ$f(x)=1$となるようなオラクルを作成せよ。

Summer 2018 Warmup - Hと非常に似ていますが、2ではなく3で割り切れるかどうかを判定してくださいという問題になっています。

今回はオラクルqubitをそのまま裏返すのではなく、2桁の追加qubit$\ket{a_0a_1}$を用意して、$\ket{x}$に$\ket{1}$を見つけるたびに追加qubitを $$\ket{00}\to\ket{01}\to\ket{10}\to\ket{00}$$ と遷移させることでカウントすることができます。

追加qubitの遷移方法は、以下のように表すことができます。

• $\ket{a_0}=\ket{0}$であれば、$\ket{a_1}$を反転させる
• 上の操作を行ったあと、$\ket{a_1}=\ket{0}$であれば、$\ket{a_0}$を反転させる。

最後に、追加qubitが$\ket{00}$となっている状態についてのみオラクルqubitを反転させればよいです。

これで、この問題が解けました。

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

    operation Count (x : Qubit[], a : Qubit[]) : Unit {
        body(...){
            let N=Length(x);
            for(i in 0..N-1){
                (ControlledOnBitString([true, false],X))([x[i],a[0]],a[1]);
                (ControlledOnBitString([true, false],X))([x[i],a[1]],a[0]);
            }
        }
        adjoint auto;
    }

    operation Solve (x : Qubit[], y : Qubit) : Unit {
        body (...) {
            let N=Length(x);
            using(a=Qubit[2]){
                WithA(Count(x,_),(ControlledOnInt(0,X))(_,y),a);
            }
        }
        adjoint auto;
    }
}
                
            

戻る