◇◇Microsoft Q# Coding Contest - Winter 2019 - Warmup G3 - Palindrome checker oracle◇◇

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

$N$桁の量子状態$\ket{x}$とqubit$\ket{y}$が与えられる。$\ket{y}$をオラクルqubitとして、$\ket{x}$がpalindromeである場合に$f(\vec{x})=1$、そうでない場合に$f(\vec{x})=0$で定義されるオラクルを作成せよ。

palindromeとは回文のことですが、ここでは$x_i=x_{N-i-1}\;(i=0,1,\dots,N-1)$であるような状態を指します。

$x_i=x_{N-i-1}$は$x_i \oplus x_{N-i-1}=0$と言い換えられるので、各qubitの組の排他的論理和を保持しておくための補助qubit列($\ket{z}$とする)を定義し、$\ket{z}=\ket{0\dots0}$である場合にオラクルqubitを反転させればよいです。

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

また、With(WithA)演算を利用した実装もあります。With演算は、ユニタリ演算$U, V$に対して$U^\dagger VU$で表される演算を定義することができ、今回の場合は最後に$\ket{z}$を$\ket{0\dots0}$に戻す必要があるので、WithA演算を利用すると便利です。

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

    operation Solve (x : Qubit[], y : Qubit) : Unit {
        body (...) {
            let N=Length(x);
            using(z=Qubit[N/2]){
                for(i in 0..N/2-1){
                    CNOT(x[i],z[i]);
                    CNOT(x[N-i-1],z[i]);
                }

                (ControlledOnInt(0,X))(z,y);

                for(i in 0..N/2-1){	//zを戻してからリリース！
                    CNOT(x[i],z[i]);
                    CNOT(x[N-i-1],z[i]);
                }
            }
        }
        adjoint auto;
    }
}
                
            

WithAを使った実装

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

    operation calcXor(x : Qubit[], z : Qubit[]) : Unit{
        body (...) {
            let N=Length(x);
            for(i in 0..N/2-1){
                CNOT(x[i],z[i]);
                CNOT(x[N-i-1],z[i]);
            }
        }
        adjoint auto;
    }
    
    operation Solve (x : Qubit[], y : Qubit) : Unit {
        body (...) {
            let N=Length(x);
            using(z=Qubit[N/2]){
                WithA(calcXor(x,_),(ControlledOnInt(0,X))(_,y),z);
            }
        }
        adjoint auto;
    }
}
                
            

戻る