跳轉到

8.3 連分數與答案提取#

概念說明#

週期尋找測得 \(k \approx s\,2^m/r\) ，其中 \(s \in \{0,1,\dots,r-1\}\) 未知且 \(k\) 有雜訊。如何從一個「接近」 \(s\,2^m/r\) 的整數反推 \(r\) ？答案是連分數（continued fractions）。

定理：若 \(\left|\frac{k}{2^m} - \frac{s}{r}\right| \le \frac{1}{2r^2}\) ，則 \(\frac{s}{r}\) 是 \(\frac{k}{2^m}\) 的連分數展開中某個收斂值（convergent）。由於 \(2^m \ge N^2 > r^2\) ，此條件以高機率滿足。

步驟：

  1. 對 \(k/2^m\) 做連分數展開：反覆取整數部分、取倒數餘數；
  2. 列出各階收斂值 \(p/q\) ，取分母 \(q \le N\) 者，即 \(r\) 的候選（ \(q\) 會等於 \(r\) 的某個因數，通常多次樣本取最小公倍數）；
  3. 驗證： \(a^q \equiv 1 \pmod N\) ？是的話 \(q\) （或其倍數）就是週期；不是則換樣本或取多樣本的 LCM；
  4. 拿到偶數 \(r\) 且 \(a^{r/2}\not\equiv -1\) ，算 \(\gcd(a^{r/2}\pm1, N)\) 完成分解（8.1 節）。

連分數範例： \(k/2^m = 341/1024\) ，展開 \([0;3,133,\dots]\) ，收斂值 \(1/3\) 、 \(341/1024\) ；取分母 \(\le 21\) 者得 \(q=3\) ……對 \(N=21, a=2\) 的真實情形 \(r=6\) ，樣本 \(k=683\) 時 \(683/2048 \approx 1/3\) ，兩個樣本 \(1/3\) 與 \(2/6\) 的 LCM 給出 \(6\) 。

後現代補充：Python 的 Fraction.limit_denominator 內建了連分數法，可直接使用；但在教科書中我們仍手寫展開以理解原理。

Python 範例：完整 Shor 模擬#

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

def continued_fraction_conv(k, M, N):
    """k/M 的連分數收斂值中，分母 <= N 的所有 (p, q)"""
    convs, h_prev, h, k_prev, k2 = [], 0, 1, 1, 0
    x = k / M
    a = [int(x)]
    x = 1/x - a[-1] if x != int(x) else 0
    x0 = k; y0 = M
    # 標準整數版輾轉
    p, q = x0, y0
    cf = []
    while q:
        cf.append(p // q); p, q = q, p % q
    h_prev, h, k_prev, k2 = 0, 1, 1, 0
    for a_i in cf:
        h, h_prev = a_i*h + h_prev, h
        k2, k_prev = a_i*k2 + k_prev, k2
        convs.append((h, k2))
    return [(p_, q_) for p_, q_ in convs if q_ <= N]

def shor(N, seed=0, max_tries=8):
    rng = np.random.default_rng(seed)
    m = 2*N.bit_length(); M = 2**m
    for t in range(max_tries):
        a = int(rng.integers(2, N))
        g = gcd(a, N)
        if g > 1:
            return g, N//g, f"a={a} gcd 命中"
        # 真實週期（模擬中由古典計算；真機上來自量子電路）
        r, x = 1, a % N
        while x != 1: x = x*a % N; r += 1
        # 模擬量子測量：k ≈ s*M/r（隨機 s）
        s = int(rng.integers(1, r))
        k = int(round(s*M/r)) + int(rng.integers(-2, 3))
        cands = [q for _, q in continued_fraction_conv(k, M, N)]
        cands = sorted(set(cands), reverse=True)
        for q in cands:
            if q > 0 and pow(a, q, N) == 1 and q % 2 == 0 and pow(a, q//2, N) != N-1:
                f1 = gcd(pow(a, q//2) - 1, N)
                if 1 < f1 < N:
                    return f1, N//f1, f"a={a}, r={r}, 連分數 q={q}"
    return None

for N in [15, 21, 33, 35, 55, 91]:
    print(f"分解 {N}: {shor(N, seed=int(N))}")

複雜度分析#

連分數展開是輾轉相除法， \(O(\log^2 N)\) 位元運算——完全多項式。整個 Shor 演算法的帳單：

部分 成本 量子?
隨機選 \(a\) 、gcd \(O(\log^2 N)\) 否
模冪黑箱 \(O((\log N)^3)\) 閘 是
QFT \(O((\log N)^2)\) 閘 是
連分數 + gcd \(O(\log^3 N)\) 否
總計 \(\tilde O((\log N)^3)\) ，成功率 > 1/2

練習#

  1. 手算 \(683/2048\) 的連分數展開與前兩個收斂值，驗證 \(1/3\) 是其一。
  2. （程式）修改 shor，統計 100 次執行中「量子測量樣本可成功提取 \(r\) 」的比例，驗證接近理論值 \(\ge 4/\pi^2\) 經放大後 > 1/2。
  3. （觀念）為什麼需要 \(q \le N\) 的限制？若連分數給出的分母是 \(r\) 的真因數（如 \(r=6\) 得 \(q=3\) ），演算法如何自救？