多伊奇-喬薩算法

多伊奇-喬薩算法（英語：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)$是否為常函數。