5.3 Bernstein–Vazirani 演算法#

概念說明#

問題：黑箱內藏 \(f(x) = a \cdot x \bmod 2\) （內積、逐位 AND 再求和 mod 2），其中 \(a \in \{0,1\}^n\) 是未知字串。請找出 \(a\) 。

古典（確定性）：需要 \(n\) 次查詢——每次詢問一個單位向量 \(e_i\) ，讀出 \(a_i\) 。
量子（Bernstein–Vazirani, 1993）：只需 1 次查詢。

演算法步驟：

\(|0\rangle^{\otimes n}\) 全部 H，輔助位元 \(|-\rangle\) ；
一次 \(U_f\) ，phase kickback 得 \(\frac{1}{\sqrt{2^n}}\sum_x (-1)^{a\cdot x}|x\rangle\) ；
再做一層 H。關鍵恆等式：

\[ H^{\otimes n}\left(\frac{1}{\sqrt{2^n}}\sum_x (-1)^{a\cdot x}|x\rangle\right) = |a\rangle \]

證明： \(H^{\otimes n}|z\rangle = \frac{1}{\sqrt{2^n}}\sum_x (-1)^{z\cdot x}|x\rangle\) ，把 \((-1)^{a\cdot x}\) 展開為 \(\frac{1}{\sqrt{2^n}}\sum_z (-1)^{a\cdot z}(-1)^{x\cdot z}\) 並對 \(x\) 求和，只剩 \(z=a\) 項存活（其他完全干涉抵消）。這是「干涉把振幅全部集中到答案」最乾淨的展示。

電路： \(n+1\) 位元，共 \(2n+1\) 個基本閘（ \(2n\) 個 H ＋ 1 次黑箱），一次測量直接讀出 \(a\) 。

Python 範例（用第 3 章的模擬器）#

import numpy as np

H = np.array([[1,1],[1,-1]], dtype=complex)/np.sqrt(2)
X = np.array([[0,1],[1,0]], dtype=complex)

def bv_run(a, n, shots=1000, seed=0):
    """a: 整數形式的隱藏字串，第 0 位是最低位"""
    N = 2**(n+1)
    # 狀態：|0^n>|1>，輔助位元放最高位（index n）
    psi = np.zeros(N, dtype=complex); psi[1] = 1
    # 輔助位元 H、X
    Hn = np.eye(1, dtype=complex)
    for _ in range(n): Hn = np.kron(Hn, H)
    psi = np.kron(Hn, H @ X) @ psi            # |+^n>|->
    # 一次黑箱：phase kickback -> sum (-1)^{a·x}|x>
    amps = psi.reshape(2**n, 2)[:, 0]         # 輔助位元=|-| 的部分
    for x in range(2**n):
        amps[x] *= (-1)**(bin(a & x).count("1") % 2)
    # 輸入暫存器再做 H
    new = Hn @ amps
    p = np.abs(new)**2
    rng = np.random.default_rng(seed)
    return rng.choice(2**n, size=shots, p=p)

for a_int, n in [(0b1011, 4), (0b110010, 6), (0b11111111, 8)]:
    res = bv_run(a_int, n, shots=1000, seed=42)
    got = np.bincount(res, minlength=2**n).argmax()
    print(f"隱藏 a={bin(a_int)} n={n} -> 演算法讀出 {bin(got)}，"
          f"一次查詢，正確率 {np.mean(res == got):.0%}")

# 古典對照：n 次查詢
def classical_find_a(f, n):
    a = 0
    for i in range(n):
        if f(1 << i): a |= (1 << i)
    return a
print("古典需要 n 次查詢；量子只要 1 次")

複雜度分析#

	查詢次數	閘數
古典確定性	\(n\)	\(O(n)\)
量子 BV	1	\(2n+1\)

這裡的加速是「 \(n \to 1\) 」，不如 DJ 的指數差距戲劇化，但 BV 的架構（H–oracle–H）就是 Grover 擴散算子的前身，值得牢牢記住。模擬成本 \(O(2^n)\) 。

練習#

證明 \(H^{\otimes n}|a\rangle = \frac{1}{\sqrt{2^n}}\sum_x (-1)^{a\cdot x}|x\rangle\) ，並說明為何 BV 中兩層 H 恰好互相抵消掉 \(a\) 的資訊反轉。
（程式）修改 bv_run，讓黑箱是 \(f(x)=a\cdot x \oplus b\) （多一個常數偏移 \(b\) ），觀察結果差一個全 1 字串，並解釋原因。
（觀念）為什麼古典演算法無法用 1 次查詢找出 \(a\) ？（提示：一次查詢只能得到 1 位元資訊。）