关于「平方根之墙:振幅放大的经典模拟与无结构搜索的下界」,《量子启发与猜想证伪》给出的定量结论是什么?

结论:无结构搜索的经典代价与 N 成正比,量子代价与 √N 成正比,这是已被证明的上下界,不是工程上暂时的差距。程序 p11 在普通计算机上逐轮模拟振幅,确认了 sin²((2k + 1)θ) 的闭式解,也显示了转过头会让概率回落。程序 p12 说明平方根之墙把 2 的 n 次方变成 2 的 n/2 次方,指数还在;p13 说明不知道解的个数时,代价约翻一倍,轮数调错可能一无所获。

数据口径:书中参数为示意,全部计算由书中程序生成。 本书不构成投资、学术评审或量子硬件方面的建议。

English version

对照数据表

下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 12

A. simulated rounds versus the closed form
N M k_best P_sim P_formula pi/4*sqrt(N/M)
641 6 0.99659 0.99659 6.28
2561 12 0.99995 0.99995 12.57
2564 6 0.99659 0.99659 6.28
10241 25 0.99946 0.99946 25.13
102416 6 0.99659 0.99659 6.28
B. over-rotation for N1024, M = 1: P after k rounds
k5: P = 0.1136
k12: P = 0.4960
k25: P = 0.9995
k30: P = 0.8914
k37: P = 0.5121
k50: P = 0.0002
k60: P = 0.3569
C. classical expected draws without replacement (N+1)/(M+1)
N1,024 M = 1: 512.50 draws
N1,024 M = 16: 60.29 draws
查看完整验算程序
# Chapter 1. p11: classical simulation of Grover amplitude amplification.
# This is a CLASSICAL simulation on an ordinary computer: a list of N
# complex amplitudes (cmath) is updated by the phase oracle (marked items
# get a factor exp(i pi) = -1) and by inversion about the mean. No quantum
# hardware, no quantum speedup is claimed. Sizes are illustrative.
# Closed form (Boyer et al. 1998): after k rounds the success probability
# is sin^2((2k + 1) theta), sin(theta) = sqrt(M / N).
import cmath
import math


def mean(vec):
    re = math.fsum(z.real for z in vec)
    im = math.fsum(z.imag for z in vec)
    return complex(re, im) / len(vec)


def simulate(n, marked, rounds):
    amp = [complex(1.0 / math.sqrt(n), 0.0)] * n
    flip = cmath.exp(1j * math.pi)
    probs = []
    for _ in range(rounds + 1):
        probs.append(math.fsum(abs(amp[i]) ** 2 for i in marked))
        amp = [a * flip if i in marked else a for i, a in enumerate(amp)]
        mu = mean(amp)
        amp = [2 * mu - a for a in amp]
    return probs


def best_round(probs):
    k = 0
    while k + 1 < len(probs) and probs[k + 1] >= probs[k]:
        k += 1
    return k


if __name__ == "__main__":
    print("A. simulated rounds versus the closed form")
    print("     N   M  k_best  P_sim    P_formula  pi/4*sqrt(N/M)")
    for n, m in ((64, 1), (256, 1), (256, 4), (1024, 1), (1024, 16)):
        marked = set(range(m))
        probs = simulate(n, marked, int(math.sqrt(n / m)) + 2)
        k = best_round(probs)
        th = math.asin(math.sqrt(m / n))
        pf = math.sin((2 * k + 1) * th) ** 2
        print("  {:>4} {:>3}  {:>6}  {:.5f}  {:.5f}    {:>6.2f}".format(
            n, m, k, probs[k], pf, math.pi / 4 * math.sqrt(n / m)))
    print("B. over-rotation for N = 1024, M = 1: P after k rounds")
    probs = simulate(1024, {0}, 60)
    for k in (5, 12, 25, 30, 37, 50, 60):
        print("  k = {:>2}: P = {:.4f}".format(k, probs[k]))
    print("C. classical expected draws without replacement (N+1)/(M+1)")
    for n, m in ((1024, 1), (1024, 16)):
        draws = (n + 1) / (m + 1)
        print("  N = {:,} M = {}: {:.2f} draws".format(n, m, draws))

唯一数据源与引用

范雅福(Fan, Y.). (2026). 《量子启发式组合寻优、拉马努金式直觉猜想与突破性著作推演母典》第 1 章「平方根之墙:振幅放大的经典模拟与无结构搜索的下界」(版本 1.0.0). 5D Library. DOI 待发布

DOI 待发布 · 专著页正式发布后上线(本站暂无专著页) · 5DL-B-364 · v1.0.0 · CC-BY-NC-ND-4.0

BibTeX
@book{fan2026364,
  author    = {Fan, Yafu},
  title     = {Quantum-Inspired Combinatorial Search, Abductive Intuition and Computationally Verified Breakthrough Monograph Engineering},
  year      = {2026},
  publisher = {5D Library},
  edition   = {1.0.0},
  note      = {DOI pending}
}

本书其他章节结论