7.3 週期偵測與相位估計#

概念說明#

QFT 最重要的應用是找出隱藏在函式中的週期——這正是 Shor 演算法的心臟（第 8 章）。

相位估計（phase estimation）問題：給定么正算子 \(U\) 與其本徵態 \(|u\rangle\) （ \(U|u\rangle = e^{2\pi i\varphi}|u\rangle\) ），估計相位 \(\varphi \in [0,1)\) 。

電路（ \(n\) 個計數位元 + 本徵態暫存器）：

1. 計數位元做 H： \(\frac{1}{\sqrt{2^n}}\sum_k |k\rangle \otimes |u\rangle\) ；
2. 受控 \(U^{2^j}\) ：得 \(\frac{1}{\sqrt{2^n}}\sum_k |k\rangle U^k|u\rangle = \frac{1}{\sqrt{2^n}}\sum_k e^{2\pi i k\varphi}|k\rangle|u\rangle\) ；
3. 對計數暫存器做逆 QFT：狀態變成 \(\approx |\varphi\, 2^n\rangle|u\rangle\) （當 \(\varphi\) 可用 \(n\) 位二進位精確表示時完全正確）；
4. 測量計數暫存器，讀出 \(\varphi\) 。

週期偵測：設函式 \(f(x+r)=f(x)\) （週期 \(r\) ， \(r | N\) ， \(N=2^n\) ）。準備疊加 \(\frac{1}{\sqrt N}\sum_x |x\rangle|f(x)\rangle\) ，測量第二暫存器後第一暫存器塌縮為

對它做 QFT，機率集中在 \(k \approx N/r\) 的倍數上（見 7.1 節）。量到某個 \(k = s\,N/r\) 後用連分數（8.3 節）還原 \(r\) 。

精度：相位估計用 \(n\) 個計數位元可把 \(\varphi\) 估到 \(n\) 位精度，成功機率 \(\ge 4/\pi^2\) ；加 \(m\) 個輔助位元可使成功機率 \(\ge 1 - 2^{-m}\) 。

Python 範例#

import numpy as np

def qft_matrix(n):
    N = 2**n
    j, k = np.meshgrid(np.arange(N), np.arange(N))
    return np.exp(2j*np.pi*j*k/N)/np.sqrt(N)

# ---- 相位估計：U = 相位旋轉 diag(1, e^{2πiφ})，本徵態 |1> ----
n = 5                                  # 計數位元數
phi = 0.375                            # 真實相位 = 0.011 (二進位)，可精確表示
N = 2**n
count = np.ones(N, dtype=complex)/np.sqrt(N)          # |+^n>
phi_state = np.array([0, 1], dtype=complex)           # |1>
# 受控 U^k：對 |1> 分量乘 e^{2πi k φ}
amps = np.array([np.exp(2j*np.pi*k*phi) for k in range(N)])
measured = (qft_matrix(n).conj().T) @ (count * amps)  # 逆 QFT
p = np.abs(measured)**2
best = p.argmax()
print(f"真實相位 {phi} = {phi}*{N} = {phi*N}")
print(f"相位估計最可能計數值: {best} -> φ ≈ {best/N}")
print("機率分佈尖峰:", np.round(np.sort(p)[-4:], 3))

# ---- 週期偵測：f(x) = 2^x mod 21 的週期 ----
N = 2**8
a, mod = 2, 21
vals = [pow(a, x, mod) for x in range(64)]
r = next(i+1 for i in range(1, 64) if vals[i:] == vals[:-i] and vals[i] == vals[0])
print(f"\n2^x mod 21 的真實週期 r = {r}")
x0 = 3
comb = np.zeros(N, dtype=complex)
for j in range(x0, N, r): comb[j] = 1
comb /= np.linalg.norm(comb)
sp = np.abs(qft_matrix(8) @ comb)**2
top = np.argsort(sp)[-5:][::-1]
print("QFT 後機率最高的頻率 k:", top, "（理論上 k = s·N/r）")
print("N/r =", N//r, "，k 值是否為其倍數:", top % (N//r) == 0)

複雜度分析#

相位估計： \(n\) 個計數位元 + 逆 QFT 的 \(O(n^2)\) 閘 + 受控 \(U^{2^j}\) （ \(U\) 的冪可由反覆平方實現，總成本 \(O(n)\) 次 \(U\) ）。週期偵測：一次 QFT \(O(n^2)\) 閘，重複 \(O(1)\) 次即可高機率取得好樣本——這就是 Shor 的多項式時間來源：古典部分（連分數）與量子部分（QFT）都只要多項式。

練習#

1. 用 \(n=3\) 個計數位元估計 \(\varphi = 0.5\) ，驗證測量結果必為 \(|100\rangle\) （ \(k=4\) ）。
2. （程式）把相位改成 \(\varphi = 1/3\) （無法用 5 位元精確表示），觀察測量分佈，驗證最可能值仍是最佳 \(n\) 位近似。
3. （觀念）週期偵測中為什麼要先測量 \(f(x)\) 暫存器？不測的話對第一暫存器做 QFT 會得到什麼？