◇◇Microsoft Q# Coding Contest - Summer 2018 D3-Oracle for majority function◇◇

https://codeforces.com/contest/1002/problem/D3

3桁の量子状態$\ket{x}$と1桁のqubit$\ket{y}$が与えられる。$\ket{x}$を構成する3つのqubitのうち$k$個が$\ket{1}$であるとき、$\ket{y}$をオラクルqubitとして $$f(x)=\left\{ \begin{array}{rr} 0\;\left( k\leq1 \right)\\1\;\left( 2\lt k \right) \end{array}\right.$$ で定義されるオラクルを作成せよ。

$f(x)$がいわゆる多数決回路であるようなオラクルを実装せよという問題です。$\ket{x}$には任意の状態が与えられるので、複数の基底状態の重ね合わせも当然含まれます。よって、Pauli Z演算子を対角とした測定を3回行って、固有値$-1$が2回以上測定されればNOTゲートを使って$\ket{y}$をひっくり返すといった実装では正解できません。

Toffoliゲート（CC-NOTゲート）を利用すると、この問題を解くことができます。Toffoliゲートは $$T=\left(\ket{00}\bra{00}+\ket{01}\bra{01}+\ket{10}\bra{10} \right)_{0,1}I_2+\left( \ket{11}\bra{11} \right)_{0,1}X_2$$ で表される演算であって、2つの制御bitがともに$\ket{1}$である場合にターゲットbitを反転させます。

制御bitを$\{x_0,x_1\},\{x_1,x_2\},\{x_2,x_0\}$、ターゲットbitを$\ket{y}$とした3つのToffoliゲートを考えます。$k\leq1$のとき、この3つのなかで両方の制御bitが1であるようなものはなく、$k=2$のときは1つ、$k=3$のときは3つそのようなゲートがあることになります。奇数回の反転は1回の反転と同値であるので、3つのToffoliゲートを使えば求めるオラクルを実装できることがわかります。

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

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

    operation Solve (x : Qubit[], y : Qubit) : ()
    {
        body
        {
            CCNOT(x[0],x[1],y);
            CCNOT(x[1],x[2],y);
            CCNOT(x[2],x[0],y);
        }
    }
}
                
            

戻る