◇◇Microsoft Q# Coding Contest - Summer 2018 - Warmup I- Deutsch-Jozsa algorithm◇◇

https://codeforces.com/contest/1001/problem/I

$N+1$桁のqubit（$N$桁の入力qubitと1桁のオラクルqubit）に作用するオラクルが与えられる。そのオラクルを定義する関数$f(x)$がconstant（Nbitの整数を入力したとき、いかなる入力に対しても0を返すか、いかなる入力に対しても1を返す）であるか、balanced（Nbitの整数のうち、半分に対しては0を返し、もう半分に対しては1を返す）であるかを判別し、constantであればtrueを、balancedであればfalseを返せ。ただし、オラクルは1度しか呼び出すことができないものとする。

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

Deutsch-Jozsaのアルゴリズムによってオラクルをconstantとbalancedに分類する手順は、以下のようになっています。

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に対してPauli Zを対角とする測定をして、すべて$\ket{0}$であればconstant、そうでなければbalancedと判断する。

順を追って見ていきます。

1. 初期状態 $$\begin{align*} \ket{\psi_0}&= \ket{x}\otimes\ket{y}\\ &=\ket{0}^{\otimes N}\otimes\ket{1}\\ \end{align*}$$ を用意します。
2. すべてのqubitにアダマール・ゲートを作用させたとき、状態は $$\begin{align*} \ket{\psi_1}&=\ket{+}^{\otimes N}\otimes\ket{-}\\ &=\ket{0...00}\otimes\ket{-}+\ket{0...01}\otimes\ket{-}+...+\ket{1...10}\otimes\ket{-}+\ket{1...11}\otimes\ket{-}\\ &=\ket{0}\otimes\ket{-}+\ket{1}\otimes\ket{-}+...+\ket{2^N-2}\otimes\ket{-}+\ket{2^N-1}\otimes\ket{-}\\ &=\sum_{x\in \{0,1\}^N}\frac{\ket{x}}{\sqrt{2^N}}\otimes\left[ \frac{\ket{0}-\ket{1}}{\sqrt{2}} \right] \end{align*}$$ となります。これは、$\ket{0}$から$\ket{2^N-1}$までのすべての状態の重ね合わせと状態$\ket{-}$の直積状態を意味します。
3. ここで、ある状態 $$\begin{align*} \ket{\phi}&=\ket{x}\otimes\ket{-}\\ &=\ket{x}\otimes\left[ \frac{\ket{0}-\ket{1}}{\sqrt{2}} \right] \end{align*}$$ が、オラクルの作用によってどのように変化するかということを考えます。オラクルを定義する$f(x)$が$x$の値によって0または1を返すとき、 $f(x)=0$であれば $$\begin{align*} U_f\ket{\phi}&=\ket{x}\otimes\ket{-\oplus 0}\\ &=\ket{x}\otimes\left[ \frac{\ket{0\oplus0}-\ket{1\oplus0}}{\sqrt{2}} \right]\\ &=\ket{x}\otimes\left[ \frac{\ket{0}-\ket{1}}{\sqrt{2}} \right]\\ &=\ket{\phi} \end{align*}$$ を、$f(x)=1$であれば $$\begin{align*} U_f\ket{\phi}&=\ket{x}\otimes\ket{-\oplus 1}\\ &=\ket{x}\otimes\left[ \frac{\ket{0\oplus1}-\ket{1\oplus1}}{\sqrt{2}} \right]\\ &=\ket{x}\otimes\left[ \frac{\ket{1}-\ket{0}}{\sqrt{2}} \right]\\ &=-\ket{\phi} \end{align*}$$ を得ます。つまり、オラクルbitが$\ket{-}$であるときには、オラクルは特定の状態の符号を反転するゲートとして作用することがわかります。よって、状態$\ket{\psi_1}$にオラクルゲート$U_f$を作用させると、一部の状態の符号が反転した状態 $$\begin{align*} \ket{\psi_2}&=U_f\ket{\psi_1}\\ &=\sum_{x\in \{0,1\}^N}\frac{(-1)^{f(x)}\ket{x}}{\sqrt{2^N}}\otimes\left[ \frac{\ket{0}-\ket{1}}{\sqrt{2}} \right] \end{align*}$$ を得ます。
4. 状態$\ket{0},\ket{1}$にアダマール・ゲートを作用させたとき、その状態は $$H\ket{0}=\frac{\ket{0}+\ket{1}}{\sqrt{2}}$$ $$H\ket{1}=\frac{\ket{0}-\ket{1}}{\sqrt{2}}$$ となるのでした。このことは $$H\ket{x}=\sum_{z\in\{0,1\}}\frac{(-1)^{x\cdot z}\ket{z}}{\sqrt{2}}$$ と一般化して書くことができて$(x,z\in\{0,1\}^N)$、 これを使えば、$N$桁のqubit状態に対しても $$H^{\otimes N}\ket{x}=\frac{\sum_{z\in\{0,1\}^N}(-1)^{x\cdot z}\ket{z}}{\sqrt{2^N}}$$ と表すことができます(状態$\ket{1}$から生まれた状態$\ket{1}$だけがマイナスの符号をもつことを考えればイメージできると思います)。ここで、 $$x\cdot z=x_0z_0+...+x_{N-1}z_{N-1}$$ です。以上のことから、それぞれの$x$について状態を足し合わせれば、状態$\ket{\psi_3}$を $$\ket{\psi_3}=\sum_{x\in\{0,1\}^N} \sum_{z\in\{0,1\}^N}\frac{(-1)^{x\cdot z+f(x)}\ket{z}}{\sqrt{2^N}}\otimes\left[ \frac{\ket{0}-\ket{1}}{\sqrt{2}} \right]$$ と表すことができました。
5. ここで、$f(x)$がconstantおよびbalancedであるとき、状態$\ket{0}^{\otimes N}\otimes\ket{-}$を測定する確率がどのようになっているかを考えます。$f(x)$がconstantであるとき、$\ket{0}^{\otimes N}\otimes\ket{-}$の振幅は $$\sum_{x\in\{0,1\}^N}\frac{(-1)^{f(x)}\ket{0}^{\otimes N}}{\sqrt{2^N}}\otimes\left[ \frac{\ket{0}-\ket{1}}{\sqrt{2}} \right]=\pm\ket{0}^{\otimes N}\otimes\left[ \frac{\ket{0}-\ket{1}}{\sqrt{2}} \right]$$ より1もしくは-1になります（$f(x)=0$のとき1、$f(x)=1$のとき-1）。このことは、オラクルがconstantであるとき、$U_f\ket{\psi_1}=\pm\ket{\psi_1}$であること、およびアダマール・ゲートが自分自身の逆操作であることからも理解できると思います。ここから、オラクルがconstantであれば必ず$\ket{0}^{\otimes N}\otimes\ket{-}$が測定されることを示せたので、オラクルがbalancedであるときに決して$\ket{0}^{\otimes N}\otimes\ket{-}$が測定されないことを示せば終了です。このことは簡単に示すことができて、$f(x)$がすべての$x$のうち半分に0を、半分に1を返すことから $$\sum_{x\in\{0,1\}^N}\frac{(-1)^{f(x)}\ket{0}^{\otimes N}}{\sqrt{2^N}}\otimes\left[ \frac{\ket{0}-\ket{1}}{\sqrt{2}} \right]=0$$ となります。

よって、この問題が解けました。

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

    operation Solve (N : Int, Uf : ((Qubit[], Qubit) => ())) : Bool
    {
        body
        {
            mutable ret=true;
            using(qs=Qubit[N+1]){
                X(qs[N]);
                ApplyToEach(H,qs);
                Uf(qs[0..N-1],qs[N]);
                ApplyToEach(H,qs[0..N-1]);
                for(i in 0..N-1){
                    if(M(qs[i])!=Zero){
                        set ret=false;
                    }
                }
                ResetAll(qs);
            }
            return ret;
        }
    }
}
                
            

• Michael A. Nielsen, Isaac L.Chuang(2004)『量子コンピュータと量子通信Ⅰ-量子力学とコンピュータ科学-』（木村達也訳）オーム社

戻る