What does Quantum-Inspired Search and Verified Conjectures conclude, in numbers, about “Annealing, Restarts and the Metropolis Rule: Classical Recipes for Escaping Local Optima”?
Answer: Chapter 2 compares greedy descent, random restarts and annealing on a frustrated spin glass: greedy descent stalls at a hit rate of 0.060, random restarts rise to 0.985 with the budget, and several short anneals do as well.
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.060, 0.985
| instance: 20 spins, 40 couplings, ground energy -49 | ||||
| hit rate = share of 200 trials ending at the ground energy | ||||
| budget | greedy | restarts | annealing | (mean final E) |
| 300 | 0.060 | 0.385 | 0.235 | (-42.39 -47.58 -46.05) |
| 1,000 | 0.060 | 0.840 | 0.340 | (-42.39 -48.68 -46.98) |
| 3,000 | 0.060 | 0.985 | 0.530 | (-42.39 -48.97 -47.92) |
Show the full program
# Chapter 2. p22: greedy, random-restart and annealing on a spin glass.
# A frustrated Ising instance (equivalently a signed max-cut): 20 spins on
# a ring plus 20 random chords, couplings J in +-1, +-2, +-3 with a fixed
# seed (illustrative, not a benchmark). Energy E = -sum J_ij s_i s_j.
# The exact ground energy comes from a Gray-code sweep of all 2^19 states
# with spin 0 fixed. Each method gets the same budget of single-flip
# evaluations; the hit rate is the share of 200 seeded trials that end at
# the ground energy. Everything is a classical computation.
import math
import random
N, CHORDS, TRIALS = 20, 20, 200
WEIGHTS = (-3, -2, -1, 1, 2, 3)
BUDGETS = (300, 1000, 3000)
def build(rng):
edges = {}
for i in range(N):
edges[(i, (i + 1) % N)] = rng.choice(WEIGHTS)
while len(edges) < N + CHORDS:
a, b = sorted(rng.sample(range(N), 2))
if (a, b) not in edges and (b, a) not in edges:
edges[(a, b)] = rng.choice(WEIGHTS)
nb = [[] for _ in range(N)]
for (a, b), j in sorted(edges.items()):
nb[a].append((b, j))
nb[b].append((a, j))
return edges, nb
def energy(s, edges):
e = 0
for (a, b), j in edges.items():
e -= j * s[a] * s[b]
return e
def delta(s, nb, i):
# energy change if spin i flips
acc = 0
for k, j in nb[i]:
acc += j * s[k]
return 2 * s[i] * acc
def ground(edges, nb):
s = [1] * N
e = energy(s, edges)
best = e
for g in range(1, 2 ** (N - 1)):
i = (g & -g).bit_length() # spin 1 to N-1 flips
e += delta(s, nb, i)
s[i] = -s[i]
best = min(best, e)
return best
def descend(s, nb, rng, budget):
used = 0
while used < budget:
order = list(range(N))
rng.shuffle(order)
moved = False
for i in order:
used += 1
if delta(s, nb, i) < 0:
s[i] = -s[i]
moved = True
if used >= budget:
break
if not moved:
break
return used
def greedy(edges, nb, rng, budget):
s = [rng.choice((-1, 1)) for _ in range(N)]
descend(s, nb, rng, budget)
return energy(s, edges)
def restarts(edges, nb, rng, budget):
left, best = budget, 10 ** 9
while left > 0:
s = [rng.choice((-1, 1)) for _ in range(N)]
left -= descend(s, nb, rng, left)
best = min(best, energy(s, edges))
return best
def anneal(edges, nb, rng, budget, t0=2.0, t1=0.1):
s = [rng.choice((-1, 1)) for _ in range(N)]
e = energy(s, edges)
best = e
ratio = (t1 / t0) ** (1.0 / budget)
t = t0
for _ in range(budget):
i = rng.randrange(N)
d = delta(s, nb, i)
if d <= 0 or rng.random() < math.exp(-d / t):
s[i] = -s[i]
e += d
best = min(best, e)
t *= ratio
return best
if __name__ == "__main__":
edges, nb = build(random.Random(20261120))
e0 = ground(edges, nb)
print("instance: {} spins, {} couplings, ground energy {}".format(
N, len(edges), e0))
print("hit rate = share of {} trials ending at the ground energy".format(
TRIALS))
print(" budget greedy restarts annealing (mean final E)")
for budget in BUDGETS:
cells, means = [], []
for fn in (greedy, restarts, anneal):
rng = random.Random(7)
res = [fn(edges, nb, rng, budget) for _ in range(TRIALS)]
hits = 0
for r in res:
if r == e0:
hits += 1
cells.append(hits / TRIALS)
means.append(math.fsum(res) / TRIALS)
fmt = " {:>6,} {:.3f} {:.3f} {:.3f}"
fmt += " ({:.2f} {:.2f} {:.2f})"
print(fmt.format(budget, *cells, *means))Single source and citation
Fan, Y. (2026). Quantum-Inspired Combinatorial Search, Abductive Intuition and Computationally Verified Breakthrough Monograph Engineering (Version 1.0.0), Chapter 2: Annealing, Restarts and the Metropolis Rule: Classical Recipes for Escaping Local Optima. 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 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