关于「平方根之墙:振幅放大的经典模拟与无结构搜索的下界」,《量子启发与猜想证伪》给出的定量结论是什么?
结论:无结构搜索的经典代价与 N 成正比,量子代价与 √N 成正比,这是已被证明的上下界,不是工程上暂时的差距。程序 p11 在普通计算机上逐轮模拟振幅,确认了 sin²((2k + 1)θ) 的闭式解,也显示了转过头会让概率回落。程序 p12 说明平方根之墙把 2 的 n 次方变成 2 的 n/2 次方,指数还在;p13 说明不知道解的个数时,代价约翻一倍,轮数调错可能一无所获。
数据口径:书中参数为示意,全部计算由书中程序生成。 本书不构成投资、学术评审或量子硬件方面的建议。
对照数据表
下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 12
| A. simulated rounds versus the closed form | |
| N M k_best P_sim P_formula pi/4*sqrt(N/M) | |
| 64 | 1 6 0.99659 0.99659 6.28 |
| 256 | 1 12 0.99995 0.99995 12.57 |
| 256 | 4 6 0.99659 0.99659 6.28 |
| 1024 | 1 25 0.99946 0.99946 25.13 |
| 1024 | 16 6 0.99659 0.99659 6.28 |
| B. over-rotation for N | 1024, M = 1: P after k rounds |
| k | 5: P = 0.1136 |
| k | 12: P = 0.4960 |
| k | 25: P = 0.9995 |
| k | 30: P = 0.8914 |
| k | 37: P = 0.5121 |
| k | 50: P = 0.0002 |
| k | 60: P = 0.3569 |
| C. classical expected draws without replacement (N+1)/(M+1) | |
| N | 1,024 M = 1: 512.50 draws |
| N | 1,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}
}