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
budgetgreedyrestartsannealing(mean final E)
3000.0600.3850.235(-42.39 -47.58 -46.05)
1,0000.0600.8400.340(-42.39 -48.68 -46.98)
3,0000.0600.9850.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