What does Quantum-Inspired Search and Verified Conjectures conclude, in numbers, about “The Square-Root Wall: a Classical Simulation of Amplitude Amplification and the Lower Bound for Unstructured Search”?

Answer: The classical cost of unstructured search is proportional to N and the quantum cost is proportional to √N. These are proved upper and lower bounds, not a temporary engineering gap. Program p11 simulated the amplitudes round by round on an ordinary computer, confirmed the closed form sin²((2k + 1)θ), and showed that rotating too far makes the probability fall back. Program p12 showed that the square-root wall turns 2 to the n into 2 to the n/2, leaving the exponent in place; p13 showed that an unknown number of solutions roughly doubles the cost, and that mistuned rounds can yield nothing at all.

Scope of the numbers: Parameters are illustrative and all calculations are generated by the book's programs. Marked boxes separate published evidence, runnable Python calculations (20 programs), classical sources and the author's hypotheses.

中文版

Data table

The numbers below are printed verbatim by the chapter's Python program and can be reproduced by running it. standard-library Python onlyprinted values that match the answer: 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
Show the full program
# 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))

Single source and citation

Fan, Y. (2026). Quantum-Inspired Combinatorial Search, Abductive Intuition and Computationally Verified Breakthrough Monograph Engineering (Version 1.0.0), Chapter 1: The Square-Root Wall: a Classical Simulation of Amplitude Amplification and the Lower Bound for Unstructured Search. 5D Library. DOI pending

DOI pending · monograph page goes live after publication · 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}
}

Other chapter answers in this book