跳轉到

8.2 量子週期尋找電路#

概念說明#

量子週期尋找是 Shor 演算法唯一的「量子核心」。目標：對 \(f(x) = a^x \bmod N\) （週期 \(r\) ），用多項式資源找出 \(r\) 。

電路結構（兩個暫存器）：

  • 計數暫存器： \(m\) 個位元， \(2^m \ge N^2\) （ \(m \approx 2\log N\) ，多取一倍是為了讓連分數提取 \(r\) 有足夠精度）；
  • 工作暫存器： \(n = \lceil\log N\rceil\) 個位元，存放 \(f\) 的值。

步驟：

  1. 計數暫存器 H： \(\frac{1}{\sqrt{2^m}}\sum_{k=0}^{2^m-1}|k\rangle|0\rangle\) ；
  2. 模冪黑箱 \(U_a\) ： \(|k\rangle|y\rangle \to |k\rangle|a^k y \bmod N\rangle\) ，得 \(\frac{1}{\sqrt{2^m}}\sum_k |k\rangle|a^k \bmod N\rangle\) ；
  3. （可省略的優化）測量工作暫存器，計數暫存器塌縮為週期 \(r\) 的梳狀態；
  4. 對計數暫存器做 QFT：振幅集中在 \(k \cdot r \approx s \cdot 2^m\) 的頻率上，即測得 \(k \approx s\,2^m/r\) ；
  5. 測量計數暫存器得 \(k\) ，交給 8.3 節的連分數提取 \(r\) 。

資源與難點：電路中最昂貴的部分是模冪 \(U_a\) ——需 \(O(\log N)\) 層模乘法電路，每層又是 \(O((\log N)^2)\) 個 Toffoli，合計數千到數百萬個邏輯閘；實務上還需要大量 ancilla 與糾錯。相對地 QFT 部分只佔 \(O(m^2)\) ，是「便宜的」部分。

Python 範例（狀態向量模擬，小 \(N\) ）#

import numpy as np
from math import gcd
from fractions import Fraction

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)

def quantum_period(a, N, m=None, shots=20, seed=0):
    """量子週期尋找（狀態向量模擬）：回傳多個 k 樣本"""
    m = m or 2*N.bit_length()           # 2^m >= N^2
    M = 2**m
    # 步驟 1+2：直接構造 sum_k |k>|a^k mod N>
    state = np.zeros(M, dtype=complex)
    for k in range(M):
        state[k] = 1/np.sqrt(M)         # 工作暫存器資訊已「隱含」：測量後才塌縮
    # 模擬「測工作暫存器」：等價於隨機固定 x0，計數態為 {x0 + j r}
    rng = np.random.default_rng(seed)
    x0 = rng.integers(0, N)
    comb = np.zeros(M, dtype=complex)
    js = np.arange(x0, M, r_true := None) if False else None
    # 真正的週期 r（模擬器內部用古典計算，實機上不需要）
    r, x = 1, a % N
    while x != 1:
        x = x * a % N; r += 1
    for j in range(x0, M, r): comb[j] = 1
    comb /= np.linalg.norm(comb)
    # 步驟 4：QFT
    spectrum = np.abs(qft_matrix(m) @ comb)**2
    samples = rng.choice(M, size=shots, p=spectrum)
    return samples, r

def extract_r_from_k(k, M, N):
    """8.3 節預告：連分數提取 r"""
    frac = Fraction(k, M).limit_denominator(N)
    return frac.denominator

N, a = 21, 2
samples, r = quantum_period(a, N, seed=7)
print(f"N={N}, a={a}, 真實週期 r={r}")
M = 2**(2*N.bit_length())
ks, cands = [], []
for k in samples:
    est = extract_r_from_k(k, M, N)
    ks.append(k); cands.append(est)
print("樣本 k:", ks)
print("對應 r 估計:", cands)
good = [c for c in cands if r % c == 0]
print("有效的估計（r 的因數）:", set(good), "-> 取多個樣本的最小公倍數逼近 r")

複雜度分析#

  • 量子閘數：模冪 \(O((\log N)^2 \log N)\) （以 Toffoli 計）＋ QFT \(O(m^2) = O((\log N)^2)\) ；
  • 樣本數： \(O(1)\) 次電路執行即可高機率取得可用的 \(k\) （失敗重跑，期望常數次）；
  • 模擬器： \(O(2^m) = O(N^2)\) 振幅，故只能模擬 \(N \lesssim 2^{12}\) 左右——真實的 Shor 在硬體上跑的正是這種「小 \(N\) 」演示（目前最大：15、21）。

練習#

  1. 說明為什麼計數暫存器需要 \(2^m \ge N^2\) 而非 \(2^m \ge N\) （提示：連分數的精度條件）。
  2. （程式）用 quantum_period 對 \(N=15\) 的所有 \(a\) 跑 20 個樣本，統計每個 \(a\) 需要多少樣本才能確定 \(r\) 。
  3. （觀念）為什麼步驟 3 的「測量工作暫存器」可以省略？（提示：不測量時 QFT 作用在 \(|k\rangle|a^k\rangle\) 上，對第一暫存器取偏跡後機率分佈相同。）