Simulated-annealing extremal search — Metropolis local search for rare, structured witness/counterexample objects

Statement

The method. Simulated annealing (Kirkpatrick–Gelatt–Vecchi, *Science* 220:671–680, 1983) treats an optimization problem as a physical system seeking a low-energy state: define an energy / fitness function on configurations, propose local moves, and accept each move by the Metropolis rule — always accept an improvement, accept a worsening move of size $\Delta E$ with probability $\exp(-\Delta E / T)$ — while slowly lowering a temperature $T$. High $T$ lets the walk cross fitness barriers (escape local optima); cooling $T\to 0$ freezes it into a deep basin. The acceptance rule is the 1953 Metropolis Monte-Carlo step; the 1983 contribution is the annealing schedule and the reframing of combinatorial optimization as statistical mechanics.

Extremal-search specialization (this wiki's usage). Here the target is not a generic optimum but a rare, structured extremal object — a witness or counterexample certifying (or refuting) a combinatorial claim. The specialization has three fixed choices:

1. Configuration space = the constraint-respecting objects, so that *every* visited configuration is already a legal candidate. For graphs: the moves are degree-preserving 2-edge-swaps (delete edges $\{a,b\},\{c,d\}$, add $\{a,d\},\{c,b\}$) with a connectivity guard, so the walk stays inside "connected, fixed-degree-sequence" the whole time. 2. Fitness = distance from the forbidden property, i.e. count / severity of the structures you are trying to eliminate. For Erdős-64: fitness penalizes the presence of cycles of the banned lengths, driving the search toward a graph whose cycle spectrum *skips* them. 3. Metropolis acceptance over that fitness, so the walk can climb out of "stuck at one stubborn forbidden substructure" configurations that a pure greedy descent would never escape.

The output is a concrete object to be independently certified (see Dual-oracle verification — certify every claimed object by two independent oracles, count-certify exhaustive runs, and scan all prior-art branches before claiming novelty) — annealing *finds* candidates; it does not *prove* them.

Facts

- In-house provenance — Erdős-64. The 2026-07-02/03 Track-B campaign on Erdős #64 — min-degree-3 graphs contain a power-of-2 cycle used exactly this: annealer = "degree-preserving 2-edge-swaps + connectivity guard + Metropolis," fitness = "avoid cycle-lengths {4,8} only," with the exact-length cycle oracle inside the fitness function validated against networkx (0 mismatches). It found the first C4+C8-free min-degree-3 specimens it was aimed at — three cubic connected graphs (n=24, 24, 26) whose cycle spectra skip exactly 4 and 8 — reproducible from graph6 in seconds. (Source: Erdős #64 — unconditional 4-or-8 dichotomy ≤19, first C4+C8-free specimens (n=24), Pt-line ceiling at P17.) - The "irreducible obstruction" signature. A revealing empirical fact from that campaign: warm-start runs seeded from the n=24 specimens with fitness retargeted to "avoid {4,8,16}" all stalled at exactly 'C16 present, C4/C8 absent' — the C16 never fell — mirroring how random-start n=30 runs stalled at an irreducible C8. Annealing thus does double duty: when it *succeeds* it yields a witness; when it *reproducibly stalls at the same residual structure*, that stall is itself evidence (here, consistent with Erdős #64 — min-degree-3 graphs contain a power-of-2 cycle being TRUE at δ=3 — you cannot anneal the last power-of-2 cycle away). A stall is data, not just a failure. - Guided, not blind — this is the whole point. Extremal witnesses are, by construction, rare and structured, so uniform random sampling finds them with probability → 0. The annealer beats sampling because its fitness gradient *steers* toward the forbidden-property boundary and its Metropolis moves *tunnel* past local traps, while degree/constraint-preserving moves keep it on the thin manifold of legal objects. Blind enumeration is the complementary tool (exhaustive scans proved the 4-or-8 dichotomy for n ≤ 19 over tens of billions of graphs), but for *finding a single deep witness* in a large space, the guided walk is what works. - **Cross-domain edge — retarget to PPT² conjecture (Christandl 2012) — composition of two PPT channels is entanglement-breaking; open for dimension ≥ 4.** The identical idea transplants to the quantum-channel setting, and this is one of the wiki's flagged bisociations (Bisociation (Koestler 1964) — creative insight as the collision of two habitually unrelated frames of thought): search the cone of Choi matrices for a structured PPT-but-not-EB composition $\Phi\circ\Psi$. Configuration space = pairs of Choi matrices constrained to be PSD with PSD partial transpose (the PPT cone — the exact analogue of "fixed degree sequence + connected"); local moves = constraint-preserving perturbations that stay inside that cone; fitness = distance from entanglement-breaking, e.g. the most negative eigenvalue attainable by an Entanglement witness — a Hermitian W with Tr(Wσ)≥0 on all separable states but Tr(Wρ)<0 on some entangled ρ against the composition's Choi state, so the walk is driven toward "composition is *not* separable." The design constraint is the same lesson as Erdős-64, and it is forced by the physics: random/blind search is doomed — Collins–Yin–Zhong (arXiv:1803.00143) prove random PPT states are entanglement-breaking with probability → 1, and Jin (arXiv:2010.15554) reports blind Choi-matrix + witness search as "extremely difficult... the genuine part of the separability problem," finding nothing. A counterexample must be a rare structured extremal object — precisely what *guided* extremal search, seeded from known bound-entangled families, is built to reach. (Source: var/openproblems/ppt2-scan.md §4, §6.) - Seeding matters. The Erdős campaign's most productive runs were warm-started from near-miss objects (specimens, or hand-built partial constructions). The PPT² analogue is to seed the annealer from known bound-entangled states (Tang/Horodecki-style constructions) that already sit near the EB boundary, rather than from a random cone point — the scan explicitly flags "ML/SDP-assisted structured (not blind-random) search targeting the region where bound entanglement is hardest to detect" as an untried fresh angle. - Failure modes / honesty. Annealing gives no optimality certificate, no lower bound, and can be fooled by a fitness that is flat far from the target (no gradient to follow) or by moves that cannot reach the target's manifold. It complements — never replaces — exhaustive search (for definitive small-n statements) and independent verification (for correctness of any found object). Its claims are always existential and always require Dual-oracle verification — certify every claimed object by two independent oracles, count-certify exhaustive runs, and scan all prior-art branches before claiming novelty.

Related

- Erdős #64 — min-degree-3 graphs contain a power-of-2 cycle — the target problem where the method was executed in-house (find power-of-2-cycle-free min-degree-3 graphs). - Erdős #64 — unconditional 4-or-8 dichotomy ≤19, first C4+C8-free specimens (n=24), Pt-line ceiling at P17 — the concrete run: annealer spec, fitness, dual-oracle-verified specimens, and the C16-irreducibility stall signature. Primary in-house provenance for this page. - PPT² conjecture (Christandl 2012) — composition of two PPT channels is entanglement-breaking; open for dimension ≥ 4 — the cross-domain retarget: anneal the Choi cone toward a PPT-but-not-EB composition; its own cross-domain-edges section already cites this page as the natural transplant against the blind-search-is-doomed obstruction. - Covariance / symmetry reduction of quantum channels — THE WALL: the one recipe every partial PPT² result reuses, and nobody has escaped to the general case — the PPT² wall this search-import is meant to bypass: instead of restricting to a symmetry class and analyzing its invariant cone, search the *full* (or bound-entanglement-seeded) cone directly. - Entanglement witness — a Hermitian W with Tr(Wσ)≥0 on all separable states but Tr(Wρ)<0 on some entangled ρ — supplies the fitness signal for the PPT² version: the witness's most-negative expectation value on the composition's Choi state is the "distance from entanglement-breaking" the annealer descends. - Bisociation (Koestler 1964) — creative insight as the collision of two habitually unrelated frames of thought — the meta-frame: annealing is the archetypal *foreign matrix* (statistical mechanics) imported first into extremal combinatorics and now proposed for quantum information; this page is step 2 of that page's worked template. - Dual-oracle verification — certify every claimed object by two independent oracles, count-certify exhaustive runs, and scan all prior-art branches before claiming novelty — the mandatory downstream step: annealing produces candidates; two independent oracles certify them (as the Erdős specimens were verified vs a gold C oracle *and* networkx). - Cycle-length spectrum C(G) of a graph as the core combinatorial object — the $C(G)$ framework defining the "forbidden lengths" the Erdős-64 fitness function targets.