一次查詢能揭示甚麼?
量子算法並不能透過測量疊加態獲得函數的每個取值。然而,它可以安排可逆預言機產生的相位,使後續干涉圖樣回答某個特定的整體問題。Deutsch–Jozsa 算法就是一個清晰例子:它只調用一次預言機,就能精確區分兩類受到承諾的 Boolean 函數。這個結論離不開承諾和查詢模型。
設 n≥1、N=2n,f:{0,1}n→{0,1}。常值函數在每個輸入處取相同值。平衡函數在恰好 N/2 個輸入處分別取每個值。任務是在保證輸入函數屬於這兩種情形之一的條件下判斷是哪種。對承諾之外的函數,此任務沒有指定正確答案。
標準可逆預言機作用於輸入寄存器和一個目標量子比特:
Uf∣x⟩∣z⟩=∣x⟩∣z⊕f(x)⟩.對每個固定的 x,它要麼保持目標不變,要麼翻轉目標,因此置換計算基,是酉算子。一次查詢計作使用一次 Uf;構造該預言機的物理成本不計入查詢次數。這個承諾不意味著任意 f 都有小規模電路。
從可逆查詢獲得相位
令 ∣+⟩=(∣0⟩+∣1⟩)/2、∣−⟩=(∣0⟩−∣1⟩)/2。由於 X∣−⟩=−∣−⟩,
Uf∣x⟩∣−⟩=(−1)f(x)∣x⟩∣−⟩.
目標回到同一狀態,輸入分支則獲得相位。這個相位回授由可逆預言機的線性性得到,並不是在所有輸入上測量 f(x)。
準備 ∣0n⟩∣1⟩,對每個量子比特施加 H,調用一次 Uf,再對第一寄存器施加 H⊗n。使用二進制內積 x⋅y=i∑xiyi(mod2) 和恆等式
H⊗n∣x⟩=N1y∈{0,1}n∑(−1)x⋅y∣y⟩,
最終態為
y∑Ay∣y⟩∣−⟩,Ay=N1x∑(−1)f(x)+x⋅y.
測量第一寄存器,當且僅當結果為 0n 時輸出「常值」。
常見錯誤
(用 ∣0⟩ 而不是 ∣−⟩ 作目標)
若目標為 ∣0⟩,預言機給出 ∣x⟩∣f(x)⟩,即把 f(x) 記錄在目標中,而不是產生相位。最後的 Hadamard 門之後,第一寄存器中 0n 的分量為 N−1x∑∣f(x)⟩,其長度平方為 (N02+N12)/N2,其中 N0,N1 分別是取值 0,1 的輸入個數。對平衡函數這個值是 1/2,所以有一半的機會測得 0n,判定規則失效。目標必須製備為 ∣−⟩,即先製備 ∣1⟩ 再施加 H。
算法使用一次預言機查詢,對每個常值或平衡的 f 都以概率一給出正確答案。
在 y=0n 處,振幅為 A0=N−1x∑(−1)f(x)。若 f 常值,A0=1 或 −1,因此測量以概率一給出 0n。若 f 平衡,正項與負項抵消,故 A0=0,永遠不會測得 0n。因此輸出規則在兩個承諾情形中均正確。□
證明透視
干涉實際計算了甚麼
第一組 Hadamard 門準備相等振幅;預言機按 f 改變它們的符號;最後的 Hadamard 門在每個輸出位置相加帶符號的貢獻。在 0n 處,額外的點積符號全為一,所以其振幅是 (−1)f(x) 的平均值。承諾判定只需要這個匯總量。電路不會在一次測量中揭示整個真值表。
當 n=2、f(x1,x2)=x1⊕x2 時,四個輸入中恰有兩個取值一。最終第一寄存器為 ∣11⟩,因此必然輸出「平衡」。對常一函數,最終第一寄存器為 −∣00⟩;負號是全局相位,所以必然輸出「常值」。
例題 2.1.5
(一個本身是特徵(character)的平衡函數)
令 n=2、f(x1,x2)=x1。它在四個輸入中恰有兩個取值一,所以是平衡的。振幅按兩個比特分解:
Ay=41(x1∑(−1)x1(1+y1))(x2∑(−1)x2y2),第一個因子在 y1=1 時為 2,否則為 0;第二個因子在 y2=0 時為 2,否則為 0。因此 A10=1,其餘振幅全為零。測量返回 10=00,所以輸出「平衡」,與預期一致。這個函數就是 s=10 的隱藏字符串函數。
對常一函數,A0=−1。有些讀者因這個負號而認為函數「不是常值」。測量概率取決於 ∣A0∣2=1,所以 0n 必然出現;負號是全局相位,對結果沒有影響。
承諾改變了甚麼?
反例模式
承諾之外,輸出不能完成分類
令 n=2,f 僅在 11 處取一。它既非常值也不平衡。這裏 A0=(3−1)/4=1/2,因此測量得到 00 的概率為 1/4,得到非零字符串的概率為 3/4。如果只允許「常值」和「平衡」兩個標籤,無論算法輸出哪一個都不能正確描述這個函數。精確保證只適用於承諾輸入;它並未聲稱每個 Boolean 函數都屬於這兩類之一。
對任意 f,得到 0n 的概率為 (N−1x∑(−1)f(x))2。它衡量兩種輸出值的不平衡量的平方。概率為零蘊含平衡,但在承諾之外,單次測得非零結果本身並不能證明恰好平衡。
下面的互動圖會為你編輯的真值表精確計算第一寄存器的每個振幅 Ay,讓你看到 0n 的振幅就是 f 的平均符號,以及在承諾之外有何不同。
經典查詢的比較
在承諾之下,任何始終正確的確定性經典算法,在某個輸入函數上至少需要 N/2+1 次查詢;而 N/2+1 個不同的查詢已經足夠。
對前 q≤N/2 個不同查詢全部回答零。這些答案既與常零函數相容,也與一個平衡函數相容:只需在尚未查詢的輸入中選 N/2 個賦值為一。重複查詢不會提供新資訊。因此,在這條回答記錄上,算法不能在至多 N/2 次查詢後安全停止。查詢 N/2+1 個不同輸入則足夠:如果兩種值都出現,函數平衡;如果全部相同,平衡函數不可能產生這些答案。
這是精確的確定性比較,不是對有界誤差隨機經典算法的指數分離。例如,無放回地均勻抽取 1≤k≤N 個不同輸入;若兩種值都出現則判為「平衡」,否則判為「常值」。對常值函數總是正確。對平衡函數,錯誤概率為
2(kN)(kN/2)≤21−k,
其中當 k>N/2 時規定 (kN/2)=0。只要該比值非零,(kN/2)/(kN) 中的每個因子都至多為 1/2。因此,輸入足夠多時,固定錯誤容忍度只需常數次隨機經典查詢。量子算法在此預言機模型中有一次查詢的精確優勢;這本身不能證明某個具體計算問題存在指數級的有界誤差運行時間分離。
令 n=3,即 N=8,並抽取 k 個不同輸入。當 k=3 時,平衡函數的錯誤概率為 2(34)/(38)=2⋅4/56=1/7≈0.14,低於上界 21−3=1/4。當 k=4 時為 2(44)/(48)=2/70=1/35。當 k=5 時 (54)=0,錯誤概率為 0:平衡函數的五個不同輸入不可能全取同一值。這是隨機測試變為精確的邊界情形,代價是和確定性下界一樣的 N/2+1 次查詢。
一個相關的隱藏字符串問題
改為假設 fs(x)=s⋅x(mod2),其中 s∈{0,1}n 未知。這是不同的承諾,包含 s=0。
對 fs(x)=s⋅x(mod2),同一相位查詢電路在一次查詢後以確定性方式測得 s。任何始終能找到 s 的確定性經典算法,在最壞情況下至少需要 n 次二值查詢,即使查詢可以自適應選擇也是如此。
同一相位查詢電路具有振幅
Ay=N1x∑(−1)(s⊕y)⋅x={1,0,y=s,y=s.最後的等式來自按座標分解求和:若 s⊕y 中有任一位為一,對應輸入位的兩種取值便使各項抵消。因此一次測量以確定性方式返回整個字符串 s。至於經典下界,深度為 q 的決策樹至多有 2q 條回答記錄,而算法必須區分 2n 個可能字符串,所以 q≥n。□
這就是 Bernstein–Vazirani 算法。此比較統計的是預言機查詢次數,而不是實現預言機的成本。
概念視角代數
振幅是 Walsh–Hadamard 變換
記 σ(x)=(−1)f(x)。則 Ay=N−1x∑σ(x)(−1)x⋅y 就是歸一化符號向量 σ/N 的 Walsh–Hadamard 變換,即從點 x 到特徵 x↦(−1)x⋅y 的酉基變換。在這個描述下,上面的幾種情形是同一個陳述。A0 是 σ 的平均值,所以常值的 σ 把全部權重放在 y=0n,平衡的 σ 在那裏沒有權重;特徵 σ(x)=(−1)s⋅x 則把全部權重放在 y=s。由於變換是酉的,對每個 f 都有 y∑∣Ay∣2=1:從 0n 移走的權重必然落在別處。
練習與解答
快速檢查
(當 n=1、f(0)=0、f(1)=1 時,寫出相位預言機對 ∣0⟩∣−⟩ 和 ∣1⟩∣−⟩ 的作用。最終第一寄存器測得甚麼?)
解答 · 答案
兩個分支分別獲得相位 +1 和 −1。查詢後第一寄存器為 ∣−⟩,施加 H 後變成 ∣1⟩,測得 1。
快速檢查
(當 n=2,令 f 僅在 11 處取一。計算測得 00 的概率,並解釋為甚麼承諾判定定理不適用。)
解答 · 答案
三個相位符號為正、一個為負,故 A00=1/2,概率為 1/4。該函數既非常值也不平衡。
快速檢查
(當 n=3,確定性經典算法在四個不同輸入處都看到零。在承諾下,它能否已經以確定性方式區分常值和平衡函數?)
解答 · 答案
不能。N=8 時,四個零既可擴展為常零函數,也可透過將全部四個未見輸入賦值為一,擴展為平衡函數。
快速檢查
(對 n=3 和隱藏字符串 s=101,隱藏字符串算法測得甚麼?為甚麼其他所有振幅都為零?)
解答 · 答案
以確定性方式測得 101。若 y=101,則 s⊕y 至少有一位為一;相應輸入位的兩個取值在相位和中相互抵消。