多伊奇-喬薩演算法

多伊奇-喬薩演算法（英語：Deutsch–Jozsa algorithm）是戴維·多伊奇和理查德·喬薩於1992年提出的一種確定性量子演算法。1998年，理查德·克利夫、阿圖爾·埃克特、基婭拉·馬基亞韋洛（Chiara Macchiavello）與米凱萊·莫斯卡對其進行了改進。儘管該演算法目前在現實中基本沒有用途，但可以證明它比任何可能的確定性經典演算法都快指數級，是最早提出的有此特性的量子演算法之一。

問題描述

在多伊奇-喬薩問題中，我們有一個被稱為預言機的黑盒量子電腦，它能實現某一函數 $f\colon \{0,1\}^{n}\rightarrow \{0,1\}$。該函數以n位元值作為輸入，輸出結果則為0或1。問題承諾該函數要麼是常函數（即對任何輸入都輸出恆定值0或1），要麼是平衡（balanced）函數（即對一半的輸入返回1，另一半則返回0）。問題的任務是通過預言機確定$f$是常函數還是平衡函數。

問題背景

多伊奇-喬薩問題是專門為量子計算設計的一個問題，該問題對於量子演算法而言相對容易，但對任何確定性經典演算法來說都是十分困難的。其提出的動機是展示可以由量子電腦有效並且正確解決的一個黑盒問題，而同時確定性經典電腦則需要進行大量計算才能解決該問題。更準確地說，該問題表明了複雜度類別EQP（即可以由量子電腦在多項式時間內精確地解決）與P之間的預言分離（oracle separation）。

由於該問題在機率經典電腦上也很容易解決，因此它不會產生與複雜度類別BPP（即在機率經典電腦上以多項式時間解決且誤差有界）之間的預言分離。西蒙問題則是一個證明BQP和BPP之間產生預言分離的例子。

經典演算法

對於傳統的確定性演算法而言，假設n是位元數，則在最壞情況下需要$2^{n-1}+1$次對$f$的求值。為了證明$f$是常函數，必須對超過一半的輸入進行計算並且發現它們有相同的輸出。最好情況是$f$為平衡函數且恰好選擇的前兩個輸入值對應不同的輸出值。對於傳統的隨機演算法，$k$次求值足以產生高機率的正確答案（對$k\geq 1$ 錯誤機率為$\epsilon \leq 1/2^{k}$）。然而，如果想保證獲得正確答案的話，仍需要$k=2^{n-1}+1$次求值。多伊奇-喬薩量子演算法則僅需一次對$f$的求值就能獲得準確的答案。

歷史

多伊奇-喬薩問題是戴維·多伊奇早期工作（1985年）的推廣。當時他提出的演算法針對的是$n=1$的簡單情形，即有一個輸入為1位元的布林函數$f:\{0,1\}\rightarrow \{0,1\}$，需要確定該函數是否是常函數。

多伊奇最早提出的演算法實際上並不是確定性的。1992年，多伊奇與喬薩共同提出了一種確定性演算法，並將該演算法推廣到$n$位元的輸入值。與多伊奇的演算法不同，該演算法需要進行兩次而非一次函數求值。

後來克利夫等人又對多伊奇-喬薩演算法進行了改進，提出了一種既具有確定性又僅需一次$f$求值的演算法。不過為了紀念多伊奇和喬薩兩人開創性的貢獻，該演算法仍被稱為多伊奇-喬薩演算法。

演算法

多伊奇-喬薩演算法成立的前提之一是由$x$計算$f(x)$的預言機必須是一個不會將$x$去相干的量子預言機。此外，它也不能在演算法結束後留下任何$x$的拷貝。

多伊奇-喬薩演算法量子電路

假設我們有$n+1$位元量子態$|0\rangle ^{\otimes n}|1\rangle$ ，即前n比特分別處於$|0\rangle$而最後一位元則是$|1\rangle$ 。對每個位元應用阿達馬變換可以得到

${\frac {1}{\sqrt {2^{n+1}}}}\sum _{x=0}^{2^{n}-1}|x\rangle (|0\rangle -|1\rangle )$ .

$f$是由量子預言機實現的函數。預言機將量子態$|x\rangle |y\rangle$對映到$|x\rangle |y\oplus f(x)\rangle$，其中$\oplus$是模2加法（由受控非門實現，可以看作是量子版異或門）。於是該量子預言機可以將上述量子態轉換為

${\frac {1}{\sqrt {2^{n+1}}}}\sum _{x=0}^{2^{n}-1}|x\rangle (|f(x)\rangle -|1\oplus f(x)\rangle )$ .

對於每個$x,f(x)$的結果為0或1。為了檢驗這兩種可能性，我們注意到上面的量子態等價於

${\frac {1}{\sqrt {2^{n+1}}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}|x\rangle (|0\rangle -|1\rangle )$ .

此時可以忽略最後一個量子位元${\frac {|0\rangle -|1\rangle }{\sqrt {2}}}$，剩餘部分為：

${\frac {1}{\sqrt {2^{n}}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}|x\rangle$ .

再對每一量子位元進行阿達馬變換，得到

${\frac {1}{\sqrt {2^{n}}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}\left[{\frac {1}{\sqrt {2^{n}}}}\sum _{y=0}^{2^{n}-1}(-1)^{x\cdot y}|y\rangle \right]={\frac {1}{2^{n}}}\sum _{y=0}^{2^{n}-1}\left[\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}(-1)^{x\cdot y}\right]|y\rangle$

其中$x\cdot y=x_{0}y_{0}\oplus x_{1}y_{1}\oplus \cdots \oplus x_{n-1}y_{n-1}$是每一位元相應乘積之和。

最後，我們可以檢驗測量得到$|0\rangle ^{\otimes n}$ 的機率

${\bigg |}{\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}{\bigg |}^{2}$

當$f(x)$是常函數（建設性干涉）時此機率為1，當$f(x)$是平衡函數（破壞性干涉）時此機率為0。換句話說，如果$f(x)$是常函數的話測量結果為$|0\rangle ^{\otimes n}$ （即所有量子位元全為零），其他結果則表明$f(x)$是平衡函數。

多伊奇演算法

多伊奇演算法是一般多伊奇-喬薩演算法的特例。此時我們需要檢查$f(0)=f(1)$是否成立。這相當於檢查$f(0)\oplus f(1)$，當結果為零時表明$f$是常函數，否則則不是常函數。

我們從兩位元量子態$|0\rangle |1\rangle$開始，對每一量子位元應用阿達馬變換，結果為

${\frac {1}{2}}(|0\rangle +|1\rangle )(|0\rangle -|1\rangle ).$

函數$f$可以將$|x\rangle |y\rangle$對映為$|x\rangle |f(x)\oplus y\rangle$，將此函數應用於當前的量子態，可以得到

${\frac {1}{2}}(|0\rangle (|f(0)\oplus 0\rangle -|f(0)\oplus 1\rangle )+|1\rangle (|f(1)\oplus 0\rangle -|f(1)\oplus 1\rangle ))$

$={\frac {1}{2}}((-1)^{f(0)}|0\rangle (|0\rangle -|1\rangle )+(-1)^{f(1)}|1\rangle (|0\rangle -|1\rangle ))$

$=(-1)^{f(0)}{\frac {1}{2}}\left(|0\rangle +(-1)^{f(0)\oplus f(1)}|1\rangle \right)(|0\rangle -|1\rangle ).$

忽略最後一個位元與全域相位因子，可以得到量子態

${\frac {1}{\sqrt {2}}}(|0\rangle +(-1)^{f(0)\oplus f(1)}|1\rangle ).$

再次應用阿達馬變換，得到

${\frac {1}{2}}(|0\rangle +|1\rangle +(-1)^{f(0)\oplus f(1)}|0\rangle -(-1)^{f(0)\oplus f(1)}|1\rangle )$

$={\frac {1}{2}}((1+(-1)^{f(0)\oplus f(1)})|0\rangle +(1-(-1)^{f(0)\oplus f(1)})|1\rangle ).$

若且唯若測量結果為$|0\rangle$時有$f(0)\oplus f(1)=0$。反之，若且唯若測量結果為$|1\rangle$時有$f(0)\oplus f(1)=1$。因此我們可以肯定地知道$f(x)$是否為常函數。