What does Quantum-Inspired Search and Verified Conjectures conclude, in numbers, about “The Burden of Proof for a Speedup: Time to Solution, Scaling Laws and Dequantisation”?
Answer: The time to solution turns a hit rate into hours: a method that succeeds with probability 0.01 must be repeated 458.2 times for 99 % confidence. A constant-factor advantage does not change with size, while a slightly worse scaling law eventually swallows a lead of 10 to the 8. Among a thousand instances without any real speedup, picking the 241 on which the device did well turns a median of 1.036 into 2.893. Dequantisation shows that the input assumption of squared-value sampling carries much of the supposed speedup, and that classical algorithms can use it too.
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: 0.01, 1.036, 10, 2.893, 241, 458.2
| A. repetitions for 99 % confidence, TTS99 / t_run | |
| p | 0.001: 4,602.9 |
| p | 0.01 : 458.2 |
| p | 0.1 : 43.7 |
| p | 0.5 : 6.6 |
| p | 0.9 : 2.0 |
| p | 0.99 : 1.0 |
| B. log10 TTS = log10 a + b n (illustrative solvers) | |
| n SA/dev heuristic/dev SA/dev-worse-slope | |
| 200 | 1e+08 1e+00 4e+07 |
| 945 | 1e+08 1e+00 1e+06 |
| 2,000 | 1e+08 1e+00 1e+04 |
| 4,000 | 1e+08 1e+00 1e+00 |
| 6,000 | 1e+08 1e+00 1e-04 |
| C. 1,000 instances, true speedup ratio | 1 on every instance |
| median ratio, all instances | 1.036 |
| median ratio, the 241 'fast' ones 2.893 | |
| median ratio, top 100 by ratio | 4.359 |
| share of instances with ratio > 1 | 0.519 |
Show the full program
# Chapter 3. p31: what a speedup claim must show (time-to-solution).
# A. TTS99 = t_run * ln(1 - 0.99) / ln(1 - p): runs needed for 99 %
# confidence when one run succeeds with probability p.
# B. Constant factor versus scaling: two illustrative solvers with
# TTS = a * 10^(b n). A fixed factor of 10^8 (the order reported by
# Denchev et al. 2016 against single-core annealing on crafted
# instances) never changes the exponent b. The same paper notes that
# other classical heuristics solve most of those instances about as
# fast as the device, i.e. same b, similar a. Made-up parameters.
# C. Selection bias: 1,000 synthetic instances with NO true speedup
# (log10 ratio ~ Normal(0, 0.4), fixed seed). Reporting only a chosen
# subset manufactures an apparent speedup; Ronnow et al. 2014 warn
# against exactly this. Classical arithmetic and simulation only.
import math
import random
import statistics
def r99(p):
return math.log(0.01) / math.log(1.0 - p)
if __name__ == "__main__":
print("A. repetitions for 99 % confidence, TTS99 / t_run")
for p in (0.001, 0.01, 0.1, 0.5, 0.9, 0.99):
print(" p = {:<5}: {:>9,.1f}".format(p, max(1.0, r99(p))))
print("B. log10 TTS = log10 a + b n (illustrative solvers)")
sa = (0.0, 0.010) # single-core annealing
dev = (-8.0, 0.010) # 10^8 faster, same exponent
heur = (-8.0, 0.010) # classical heuristic, same exponent
alt = (-8.0, 0.012) # 10^8 faster but worse exponent
print(" n SA/dev heuristic/dev SA/dev-worse-slope")
for n in (200, 945, 2000, 4000, 6000):
def lt(s):
return s[0] + s[1] * n
print(" {:>5,} {:>7.0e} {:>13.0e} {:>15.0e}".format(
n, 10 ** (lt(sa) - lt(dev)), 10 ** (lt(heur) - lt(dev)),
10 ** (lt(sa) - lt(alt))))
print("C. 1,000 instances, true speedup ratio = 1 on every instance")
rng = random.Random(20261120)
logs = [rng.gauss(0.0, 0.4) for _ in range(1000)]
allmed = 10 ** statistics.median(logs)
picked = [x for x in logs if x > 0.3]
hardest = sorted(logs)[-100:]
print(" median ratio, all instances {:.3f}".format(allmed))
print(" median ratio, the {} 'fast' ones {:.3f}".format(
len(picked), 10 ** statistics.median(picked)))
print(" median ratio, top 100 by ratio {:.3f}".format(
10 ** statistics.median(hardest)))
share = len([x for x in logs if x > 0]) / len(logs)
print(" share of instances with ratio > 1: {:.3f}".format(share))Single source and citation
Fan, Y. (2026). Quantum-Inspired Combinatorial Search, Abductive Intuition and Computationally Verified Breakthrough Monograph Engineering (Version 1.0.0), Chapter 3: The Burden of Proof for a Speedup: Time to Solution, Scaling Laws and Dequantisation. 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 1 · The Square-Root Wall: a Classical Simulation of Amplitude Amplification and the Lower Bound for Unstructured Search
- Chapter 2 · Annealing, Restarts and the Metropolis Rule: Classical Recipes for Escaping Local Optima
- 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