◇◇Microsoft Q# Coding Contest - Winter 2019 - Warmup G2 - OR oracle◇◇

https://codeforces.com/contest/1115/problem/G2

$N$桁の量子状態$\ket{x}$とqubit$y$が与えられる。$\ket{y}$をオラクルqubitとして $$f\left( \vec{x} \right)=x_0 \lor x_1 \lor \cdots \lor x_{N-1}$$ で定義されるオラクルを作成せよ。

ド・モルガンの法則より $$f\left( \vec{x} \right)=\lnot \left( \lnot x_0 \land \lnot x_1 \land \cdots \land \lnot x_{N-1} \right)$$ であるので、$\vec{x}$を全桁反転させてからAND oracleを適用し、最後に$y$を反転させればよいです。

Q#では、ApplyToEachにAdjointをサポートさせた演算としてApplytoEachAが用意されています。今回の問題ではAdjoint functorをサポートした演算を定義する必要があるので、こちらを使います。

また、ControlledOnInt演算を使った簡潔な実装が存在します。ControlledOnIntは、Controlledを任意の状態について適用できる関数であって、

(ControlledOnInt(numberState, oracle))(x, y);

のように書くことによって、制御qubit$\ket{x}$が整数numberStateに対応する状態になっている場合のみ演算oracleを$\ket{y}$に適用します（例えばnumberStateに3を指定すると、$\ket{x}=\ket{110...0}$の場合に適用される）。

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

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

    operation Solve (x : Qubit[], y : Qubit) : Unit {
        body (...) {
            ApplyToEachA(X,x);
            Controlled X(x,y);
            ApplyToEachA(X,x);
            X(y);
        }
        adjoint auto;
    }
}
                
            

ControlledOnIntを使用した実装

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

    operation Solve (x : Qubit[], y : Qubit) : Unit {
        body (...) {
            (ControlledOnInt(0,X))(x,y);
            X(y);
        }
        adjoint auto;
    }
}
                
            

戻る