◇◇Microsoft Q# Coding Contest - Summer 2018 E1-Bernstein-Vazirani algorithm◇◇

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

$N+1$桁のqubit（$N$桁の入力qubitと1桁のオラクルqubit）に作用するオラクルが与えられる。オラクルは 、あるbit列$\vec{b}\in\{0,1\}^N$を用いて $$f(x)=\vec{b}\cdot\vec{x}\; {\rm mod}\;2=\sum^{N-1}_{k=0}b_kx_k\; {\rm mod}\;2$$ で定義されている（D1と同様）。このオラクルを1度だけ呼び出して、bit列$\vec{b}$を特定せよ。

タイトルのとおり、Bernstein-Vaziraniのアルゴリズムを使え、という問題です。以下、Bernstein-Vaziraniのアルゴリズムについて説明します。

Bernstein-Vaziraniのアルゴリズムによって$\vec{b}$を特定する手順は、以下のようになっています。

1. 初期状態 \begin{align*} \ket{\psi_0}&= \ket{x}\otimes\ket{y}\\ &=\ket{0}^{\otimes N}\otimes\ket{1}\\ &=\ket{0...0}\otimes\ket{1} \end{align*} を用意する。
2. 初期状態のすべてのqubitにアダマール・ゲートを作用させ \begin{align*} \ket{\psi_1}&= H^{\otimes (N+1)}\ket{\psi_0}\\ &=H^{\otimes N}\ket{x}\otimes H\ket{y}\\ &=H^{\otimes N}\ket{0}^{\otimes N}\otimes H\ket{1}\\ &=\ket{+}^{\otimes N}\otimes\ket{-} \end{align*} とする。
3. 与えられたオラクルゲート$U_f$に状態を通す。 \begin{align*} \ket{\psi_2}&=U_f\ket{\psi_1}\\ &=U_fH^{\otimes (N+1)}\ket{\psi_0} \end{align*}
4. もう一度すべてのqubitにアダマール・ゲートを作用させる。 \begin{align*} \ket{\psi_3}&=H^{\otimes (N+1)}\ket{\psi_2}\\ &=H^{\otimes (N+1)}U_fH^{\otimes (N+1)}\ket{\psi_0} \end{align*}
5. $\ket{\psi_3}$の上位$N$桁のqubitが$\vec{b}$になっている。

なんと、手順がDeutsch-Jozsaのアルゴリズムと全く同じです。このことは、以下のような問題を考えることでわかります。

ある単一のbit $b$が存在して、これを用いて定義されたオラクル $$f(x)=b\cdot x \;{\rm mod}\;2$$ を考える。このオラクルを一度だけ呼び出して、$b$が0または1のどちらであるか特定せよ。

これは今解こうとしている問題（Bernstein-Vazirani問題）の1bitの場合ですが、同時にDeutsch-Jozsa問題の1bitの場合として考えることもできます。なぜならば、$b=0$の場合には$b\cdot x$はxの値によらず0になるため$f(x)$はConstantであり、$b=1$の場合には$f(x)$は$x=0$のとき0、$x=1$のとき1を返すためBalancedであるといえるので、$f(x)$がConstantであるかBalancedであるかを判定することは$b$を特定することと同値だからです。

Deutsch-Jozsaのアルゴリズムにおいては、はじめにアダマール・ゲートに状態を通してから最後にもう一度通すまで、オラクルqubitは一貫して状態$\ket{-}$のままでした。これは、1つのオラクルqubitを利用して複数のDeutsch-Jozsaのアルゴリズムを同時に行えることを意味しています。そして、Bernstein-Vaziraniのアルゴリズムは複数の1qubit Deutsch-Jozsaのアルゴリズムを同時に行うアルゴリズムであると考えることができます。

1qubitのDeutsch-Jozsaのアルゴリズムでは、$f(x)$がConstantであるときには$\ket{x}$が$\ket{0}$に、$f(x)$がBalancedであるときには$\ket{1}$に変化します。よって、$N$個のDeutsch-Jozsaアルゴリズムを同時に行うBernstein-Vaziraniアルゴリズムでは、操作後の$\ket{x}$はbit列$\vec{b}$そのものになっています。

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

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

    operation Solve (N : Int, Uf : ((Qubit[], Qubit) => ())) : Int[]
    {
        body
        {
            mutable b=new Int[N];
            using(qs=Qubit[N+1]){
                let x=qs[0..N-1];
                let y=qs[N];
                X(y);
                H(y);
                ApplyToEach(H,x);
                Uf(x,y);
                ApplyToEach(H,x);
                for(i in 0..Length(x)-1){
                    if(M(x[i])==Zero){
                        set b[i]=0;
                    }
                    else{
                        set b[i]=1;
                    }
                }
                ResetAll(qs);
            }
            return b;
        }
    }
}
                
            

• 中山 茂(2014)『量子アルゴリズム』技報堂出版

戻る