QQA correctness verification report

Summary: 29/29 checks passed (100.0%).

Generated by scripts/verify_all_problems.py on 2026-04-18 22:25:08

This report runs QQA on every built-in problem and compares its best objective against a ground truth or a strong baseline. Each block contains the reference used, per-instance numbers, runtime, and a boolean ok flag that must hold for the sweep to be considered successful.

Maximum Independent Set

Reference: NetworkX degree-greedy MIS (independent-set size)

instance	QQA	greedy	delta	ok	runtime
3-regular N=50 seed=0	22	22	0	True	6.5339
3-regular N=50 seed=1	22	22	0	True	3.4446
3-regular N=50 seed=2	22	21	1	True	2.4752

MaxCut

Reference: Random-partition best-of-400 baseline

instance	QQA	random	delta	ok	runtime
G(n=30, p=0.2) seed=0	64	58	6	True	2.7183
G(n=40, p=0.15) seed=1	90	74	16	True	2.5735
G(n=60, p=0.1) seed=2	128	101	27	True	2.8928

MaxClique

Reference: NetworkX approximation.max_clique

instance	QQA	nx_approx	delta	ok	runtime
G(n=30, p=0.5) seed=0	6	5	1	True	2.4455
G(n=40, p=0.4) seed=1	6	5	1	True	2.3896
G(n=50, p=0.3) seed=2	5	4	1	True	4.9354

Graph coloring

Reference: Welsh–Powell greedy (nx.greedy_color)

instance	QQA_conflicts	greedy_conflicts	QQA_feasible	ok	runtime
3-regular N=40 K=3 seed=0	0	0	True	True	5.4027
3-regular N=40 K=3 seed=1	0	0	True	True	6.2761
3-regular N=40 K=3 seed=2	0	1	True	True	9.1869

Ising 1D (ferromagnet)

Reference: exact E_0 = -N for J=1, h=0, periodic

instance	QQA_E	target_E	gap	ok	runtime
FM periodic N=16	-16.0000	-16.0000	0.0000	True	0.7954
FM periodic N=32	-32.0000	-32.0000	0.0000	True	0.8107
FM periodic N=64	-64.0000	-64.0000	0.0000	True	1.0410

Edwards–Anderson spin glass

Reference: Brute force (L=3, 2D); N/A for 3D L=4

instance	QQA_E	exact_E	gap	ok	runtime
EA 2D L=3 seed=0	-9.9200	-9.9200	0.0000	True	1.9504
EA 2D L=3 seed=1	-6.5128	-6.5128	0.0000	True	1.9469
EA 2D L=3 seed=2	-9.7231	-9.7231	0.0000	True	1.9815
EA 3D L=4 seed=0	-103.2382	—	-1.6131	True	3.9846
EA 3D L=4 seed=1	-95.6024	—	-1.4938	True	4.4201

Sherrington–Kirkpatrick

Reference: Parisi typical e_0 = -0.7632

instance	QQA_e0	Parisi_e0	gap_%	ok	runtime
SK N=50 seed=0	-0.6753	-0.7632	11.5090	True	6.4533
SK N=100 seed=0	-0.6870	-0.7632	9.9784	True	11.5341
SK N=200 seed=0	-0.7388	-0.7632	3.1954	True	10.3478

Binary perceptron

Reference: Teacher solution exists with 0 errors

instance	QQA_errors	teacher_errors	ok	runtime
α=0.3 N=40	0	0	True	3.7873
α=0.5 N=40	0	0	True	3.8520
α=0.7 N=40	0	0	True	3.7912

Hopfield memory

Reference: Recovery criterion: max |overlap| ≥ 0.95 with a stored pattern

instance	max_overlap	ok	runtime
N=32 P=2 α=0.06	1.0000	True	2.4509
N=64 P=3 α=0.05	1.0000	True	2.9255
N=128 P=4 α=0.03	1.0000	True	3.8455