跳轉到

6.2 Grover 迭代與擴散算子#

概念說明#

Grover 迭代 \(G = D \cdot O_f\) 由兩個操作組成：

1. 相位反轉 oracle \(O_f\) ：對解 \(|w\rangle\) 反射（上一節）。

2. 擴散算子（diffusion operator，對平均值的反射）：

\[ D = 2|\psi\rangle\langle\psi| - I, \qquad |\psi\rangle = \frac{1}{\sqrt N}\sum_x |x\rangle \]

作用是「把每個振幅關於全體平均值反射」： \(a_i \mapsto 2\bar a - a_i\) ，其中 \(\bar a\) 是平均振幅。電路實作：

\[ D = H^{\otimes n}\,(2|0\rangle\langle 0| - I)\,H^{\otimes n} \]

即「H 之後對 \(|0\rangle\) 做條件相位反轉再 H 回來」。

幾何圖像：在由 \(|w\rangle\) （解）與 \(|r\rangle\) （其餘的均勻疊加）張成的二維平面裡，初態 \(|\psi\rangle = \sqrt{\tfrac{N-M}{N}}|r\rangle + \sqrt{\tfrac{M}{N}}|w\rangle\) 與 \(|r\rangle\) 夾一個小角 \(\theta\) ， \(\sin\theta = \sqrt{M/N}\) 。oracle 是對 \(|r\rangle\) 軸的反射、擴散是對 \(|\psi\rangle\) 軸的反射，兩個反射合成一次旋轉，每次旋轉把狀態朝 \(|w\rangle\) 轉 \(2\theta\) 。 \(r\) 次迭代後狀態角 \(\approx (2r+1)\theta\) ，當它接近 \(\pi/2\) 時測得解的機率最大。

演算法步驟#

  1. \(|\psi\rangle \leftarrow H^{\otimes n}|0\rangle\) ；
  2. 重複 \(r\) 次： \(|\psi\rangle \leftarrow D\,O_f\,|\psi\rangle\) ；
  3. 測量，得解的機率 \(\sin^2((2r+1)\theta)\) 。

Python 範例#

import numpy as np

def grover_search(f, n, r=None, shots=1000, seed=0):
    N = 2**n
    O = np.diag(np.array([(-1)**f(x) for x in range(N)], dtype=complex))
    H1 = np.array([[1,1],[1,-1]], dtype=complex)/np.sqrt(2)
    Hn = np.eye(1, dtype=complex)
    for _ in range(n): Hn = np.kron(Hn, H1)
    psi0 = Hn @ np.eye(N, dtype=complex)[:, 0]
    D = 2*np.outer(psi0, psi0.conj()) - np.eye(N)     # 擴散算子
    M = sum(f(x) for x in range(N))
    theta = np.arcsin(np.sqrt(M/N))
    if r is None:
        r = max(1, int(round(np.pi/(4*theta) - 0.5)))
    psi = psi0
    for _ in range(r):
        psi = O @ psi
        psi = D @ psi
    p = np.abs(psi)**2
    rng = np.random.default_rng(seed)
    return rng.choice(N, size=shots, p=p), r, p

n, w = 4, 11
f = lambda x: 1 if x == w else 0
res, r, p = grover_search(f, n, shots=1000, seed=1)
print(f"n={n}, N={2**n}, 解 w={w}（古典平均查詢 {2**n/2:.0f} 次）")
print(f"Grover 迭代 {r} 次（理論 π/4·√N ≈ {np.pi/4*np.sqrt(2**n):.1f}）")
print("量測到解的頻率:", np.mean(res == w))
print("振幅演化前 3 次迭代的目標機率:")
H1 = np.array([[1,1],[1,-1]], dtype=complex)/np.sqrt(2)
Hn = np.eye(1, dtype=complex)
for _ in range(n): Hn = np.kron(Hn, H1)
psi = Hn @ np.eye(16, dtype=complex)[:, 0]
O = np.diag(np.array([(-1)**f(x) for x in range(16)], dtype=complex))
D = 2*np.outer(psi, psi.conj()) - np.eye(16)
for k in range(4):
    print(f"  迭代 {k}: P(w) = {abs(psi[w])**2:.4f}")
    psi = D @ O @ psi

複雜度分析#

每次迭代 = 1 次 oracle 查詢 + \(O(n)\) 個基本閘（擴散），狀態向量模擬每次 \(O(2^n)\) 。總查詢複雜度 \(r = O(\sqrt{N/M})\) ： \(N=2^{20}\) 、單解時 \(r\approx 806\) （古典最壞 \(10^6\) ）。

練習#

  1. 手算 \(n=2\) 、 \(w=3\) 時第一次迭代後的振幅，驗證目標振幅從 \(0.5\) 升到 \(1\) 。
  2. （程式）把迭代次數設為理論值的 2 倍，觀察成功率為什麼反而下降（過轉，overshooting）。
  3. （觀念）說明為什麼擴散算子是「對平均值的反射」，並用 \(n=2\) 的數字驗證 \(a_i \mapsto 2\bar a - a_i\) 。