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
p0.001: 4,602.9
p0.01 : 458.2
p0.1 : 43.7
p0.5 : 6.6
p0.9 : 2.0
p0.99 : 1.0
B. log10 TTS = log10 a + b n (illustrative solvers)
n SA/dev heuristic/dev SA/dev-worse-slope
2001e+08 1e+00 4e+07
9451e+08 1e+00 1e+06
2,0001e+08 1e+00 1e+04
4,0001e+08 1e+00 1e+00
6,0001e+08 1e+00 1e-04
C. 1,000 instances, true speedup ratio1 on every instance
median ratio, all instances1.036
median ratio, the 241 'fast' ones 2.893
median ratio, top 100 by ratio4.359
share of instances with ratio > 10.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