Deutsch-Jozsa 演算法存在誤差（probability of error）嗎？

12-31

就是那個最早的量子演算法，判斷一個函數是把所有輸入變為０，還是一半輸入變為０一半變為１的演算法。
　　我看了覺得這個演算法是準確沒有誤差的。但因為前文舉了一個隨機演算法（隨機取ｋ個數看是否一樣，有 $2^{-k}$ 的誤差）的例子作為類比，導致我有點混淆了（英文閱讀能力較差），不敢確信。

謝邀. Deutsch-Jozsa 演算法是沒有誤差的. (這一點不同於基於 Quantum Fourier Transform 的 Phase Estimation 的演算法). Deutsch-Jozsa 演算法設計了一個場景, 使得量子計算相對經典計算能夠進行指數級加速:

考慮黑箱(oracle)函數 $f:{0,1}^n ightarrow{0,1}$ , 設法確定 $f$ 是 balanced 還是 constant, 即

balanced $f$ : 對 $f$ 的 $2^n$ 個可能的輸入 $s$ (就是一個 $n$ 位 $01$ 字元串), 恰巧有一半 $f(s)=1$ ,剩下一半 $f(s)=0$ ;
constant $f$ : 對 $f$ 的 $2^n$ 個可能的輸入 $s$ , $f(s)=0$ 或者 $f(s)=1$ .

下面我簡單地做一些分析.

1. 確定性的經典演算法

注意到 balanced 就是有一半的輸入 $s$ 結果一樣, 那我們直接試 $2^{n-1}+1$ 個不就好了(抽屜原理). 所以確定性的經典演算法的時間複雜度是 $O(2^n)$ .

2. 非確定性的經典演算法

但是這樣的嘗試次數還是太多了, 如果我們減少嘗試次數, 那麼我們是否可以給出對此時結果正確的概率的估計呢? 具體來說, 對於嘗試 $k$ 個 $n$ 位不同 $01$ 字元串的情況, 那麼錯誤幾率是 $epsilon leq frac{1}{2^{k-1}}$ . 怎麼理解呢?

嘗試 $1$ 個字元串, 我們不知道 $f$ 的任何信息.
嘗試 $2$ 個字元串 $s_1$ 和 $s_2$ . 如果 $f(s_1) eq f(s_2)$ 自然好辦, 肯定是 balanced. 否則, $f$ 是constant 的可能只是比剛才大了一點, 即 $epsilon < 1/2=P(f constant|s_1 = s_2)$ .

$vdots$

嘗試 $k$ 個字元串 $s_1, s_2, cdots, s_k$ , 如果存在 $s_i eq s_j (i eq j)$ , 顯然 $f$ 是 balanced. 否則, $f$ 是 constant 的可能只是比之前大了一些, 即 $epsilon < 1/2^{k-1} = P(f constant|s_1 = s_2 = cdots = s_k)$ .

很明顯, 這時候的時間複雜度是 $O(k)$ . 當 $k geq 2^{k-1}+1$ 時, 演算法就變成確定性的了.

3. 確定性的量子演算法

下面討論量子演算法情形. 借用 Wikipedia 上的圖:

考慮自左向右的純態的時間演化, 記 $|0 angle=egin{pmatrix} 1\0\ end{pmatrix}, |1 angle=egin{pmatrix} 0\1\ end{pmatrix}$ , 對於每一條豎線:

初態為 $psi_1=|0 angle^{otimes n} otimes |1 angle$
這裡用到了 Hadamard Gate 的性質: $psi_2=H^{otimes n}|0 angle otimes H|1 angle=frac{1}{2^{n/2}}(|0 angle+|1 angle)^{otimes n} otimes frac{1}{sqrt 2}(|0 angle -|1 angle)=frac{1}{2^n}sum_x|x angle otimes frac{1}{sqrt{2}}(|0 angle-|1 angle)$
這裡的酉變換為 $U_f : |x angle|y angle ightarrow |x angle|yoplus f(x) angle$ , 為了使得線路可逆. 張量積的第二部分為ancilla qubit, 對結果事實上沒有貢獻. $psi_3 = frac{1}{2^{n/2}}sum_x|x angle frac{1}{sqrt 2}(|f(x) angle -|overline{f(x)} angle)=(frac{1}{2^{n/2}}sum_x(-1)^{f(x)}|x angle)otimes frac{1}{sqrt2}(|0 angle - |1 angle)$
再次利用 Hadamard Gate 的性質: $psi_4 = (frac{1}{2^{n/2}}sum_{x,y} (-1)^{f(x)oplus xcdot y}|y angle)|1 angle$ , 那麼:

constant $f$ : $|x angle = pm |0 angle ^n$ ;
balanced $f$ : $langle 0|x angle ^{otimes n}=frac{1}{2^n} sum_{x} (-1) ^{f(x)} = 0$ .

從而, 預處理(準備初態)需要 $O(n)$ , 而執行演算法只需要一次計算. 總的時間複雜度是 $O(n)$ .

看起來這是個並沒有什麼用的例子 (也許是暫時如此, 就跟 Simons 演算法一樣, 見評論區討論). Deutsch-Jozsa 演算法的重要性, 純粹是因為它是第一個表明量子計算在某些情形下具有指數級加速(相對經典計算)能力的例子. 此外, 這裡的討論其實相當樸素, 並沒有用到對量子可計算性和量子計算複雜性理論中對量子圖靈機的一般定義, 不過這一問題還是屬於 $BQP$ 的(類似 $Psubseteq BPP$ ).

Reference

[1] Wikipedia. Deutsch-Jozsa Algorithm.

[2] Michael Nielsen et al. Quantum Computation and Quantum Information. Cambridge. 2010.