◇◇Microsoft Q# Coding Contest – Summer 2020 B2 - "Is the number divisible by 3?" oracle◇◇

https://codeforces.com/contest/1357/problem/B2

$N$桁の量子状態$\ket{x}$とqubit$\ket{y}$が与えられる。$\ket{y}$をオラクルqubitとして、$\ket{x}$を二進数で表示した場合に3の倍数となっている場合のみ$f(x)=1$となるようなオラクルを作成せよ。

ある十進数が3の倍数かどうかを判定するには桁和が3の倍数かどうかを調べればよいですが、二進数の場合の判定方法を考えます。

$x = 3n+1$であるような任意の整数$x$について、$2x = 6n+2$であり、$y = 3n+2$であるような任意の整数$y$について$2y = 3(2n+1) + 1$であることから、3の倍数でない整数では、2倍するごとに3で割った余りが$1\rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow \ldots$と変化していくことがわかります。

よって、ある二進数を3で割った余りを調べるためには、偶数桁めのbitが立っていれば1、奇数桁めのbitが立っていれば2をそれぞれ${\rm mod}\;3$でカウントすればよく、整数を${\rm mod}\;3$でインクリメントする演算は実装済なので、これを流用して実現できます。

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

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

    operation Count (qs : Qubit[]) : Unit is Adj+Ctl
    {
        (ControlledOnInt(0, X))([qs[0]], qs[1]);
        (ControlledOnInt(0, X))([qs[1]], qs[0]);
    }

    operation Solve (inputs : Qubit[], output : Qubit) : Unit is Adj+Ctl
    {
        using (cnt = Qubit[2])
        {
            within
            {
                //各状態の整数を3で割ったあまりをカウントする
                for (idx in 0..Length(inputs) - 1)
                {
                    (Controlled Count)([inputs[idx]], cnt);
                    if (idx % 2 == 1)
                    {
                        (Controlled Count)([inputs[idx]], cnt);
                    }
                }
            }
            apply
            {
                //余りが0の状態のみoutputを反転させる
                (ControlledOnInt(0, X))(cnt, output);
            }
        }
    }
}
                
            

戻る