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) | |
| 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 |
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
- Chapter 2 · Annealing, Restarts and the Metropolis Rule: Classical Recipes for Escaping Local Optima
- Chapter 3 · The Burden of Proof for a Speedup: Time to Solution, Scaling Laws and Dequantisation
- Chapter 4 · Amplifying Samples by Value: Importance Sampling and Upper Confidence Bounds
- Chapter 5 · Shared Structure: Spectral Fingerprints, Exhaustive Mappings and the Typicality of Combinations
- Chapter 6 · A Pipeline for Ramanujan-Style Conjectures: Abundant Generation, Exhaustive Refutation and Exact Bounds
- Chapter 7 · Following the Natural Joints and Reasoning to Hypotheses: Cook Ding, Shen Kuo, Peirce and Hardy
- Chapter 8 · Closing the Empirical Loop: Standard Operating Templates and Checker Specification