◇◇Microsoft Q# Coding Contest – Summer 2020 B1 - "Is the bit string balanced?" oracle◇◇

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

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

量子状態をインクリメントする演算はWarmUpで既出なので、この問題ではその演算を用いて実際に$\ket{x}$に含まれる$\ket{1}$の数をカウントし、Controlled X演算を用いて条件を満たしている場合のみ$\ket{y}$を反転させればよいです。

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

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

    operation Increment (register : LittleEndian) : Unit is Adj+Ctl
    {
        let qs = register!;
        if (Length(qs) > 1)
        {
            (Controlled Increment)(qs[0..0], LittleEndian(qs[1...]));
        }
        X(qs[0]);
    }

    operation Solve (inputs : Qubit[], output : Qubit) : Unit is Adj+Ctl
    {
        using (cnt = Qubit[BitSizeI(Length(inputs))])
        {
            within
            {
                //1の数だけcntをIncrementする
                for (q in inputs)
                {
                    (Controlled Increment)([q], LittleEndian(cnt));
                }
            }
            apply
            {
                //cntがN/2のときだけoutputを反転する
                (ControlledOnInt(Length(inputs)/2, X))(cnt, output);
            }
        }
    }
}   
                
            

WarmupではIncrement演算を実装する際にControlledOnIntを用いていましたが、どうやら定数倍が重いらしくTLEになってしまいました。Controlled演算に入れ替えることでACできました。

within - apply構文は、ユニタリ演算$U, V$について、within節の内部に$U$を、apply節の内部に$V$を記述することで演算$U^{\dagger}VU$を行うことができる構文です。上記コードではこの構文を用いてqubitの初期化を行っています。

戻る