QQA correctness verification report¶
Summary: 29/29 checks passed (100.0%).
Generated by scripts/verify_all_problems.py on 2026-09-06 00:06:54
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 | 4.7258 |
| 3-regular N=50 seed=1 | 22 | 22 | 0 | True | 3.9831 |
| 3-regular N=50 seed=2 | 22 | 21 | 1 | True | 4.0138 |
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 | 3.9214 |
| G(n=40, p=0.15) seed=1 | 90 | 74 | 16 | True | 4.0801 |
| G(n=60, p=0.1) seed=2 | 128 | 101 | 27 | True | 4.4410 |
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 | 4.3777 |
| G(n=40, p=0.4) seed=1 | 6 | 5 | 1 | True | 4.7848 |
| G(n=50, p=0.3) seed=2 | 5 | 4 | 1 | True | 4.9685 |
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 | 6.0588 |
| 3-regular N=40 K=3 seed=1 | 0 | 0 | True | True | 6.0717 |
| 3-regular N=40 K=3 seed=2 | 0 | 1 | True | True | 6.0370 |
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.9909 |
| FM periodic N=32 | -32.0000 | -32.0000 | 0.0000 | True | 1.0315 |
| FM periodic N=64 | -64.0000 | -64.0000 | 0.0000 | True | 1.4100 |
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 | 2.4443 |
| EA 2D L=3 seed=1 | -6.5128 | -6.5128 | 0.0000 | True | 2.4564 |
| EA 2D L=3 seed=2 | -9.7231 | -9.7231 | 0.0000 | True | 2.4009 |
| EA 3D L=4 seed=0 | -103.2382 | — | -1.6131 | True | 5.1327 |
| EA 3D L=4 seed=1 | -95.6024 | — | -1.4938 | True | 5.1645 |
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 | 8.5810 |
| SK N=100 seed=0 | -0.6879 | -0.7632 | 9.8670 | True | 11.0961 |
| SK N=200 seed=0 | -0.7388 | -0.7632 | 3.1954 | True | 12.7232 |
Binary perceptron¶
Reference: Teacher solution exists with 0 errors
| instance | QQA_errors | teacher_errors | ok | runtime |
|---|---|---|---|---|
| α=0.3 N=40 | 0 | 0 | True | 4.7777 |
| α=0.5 N=40 | 0 | 0 | True | 4.3694 |
| α=0.7 N=40 | 0 | 0 | True | 4.4522 |
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.8423 |
| N=64 P=3 α=0.05 | 1.0000 | True | 3.3107 |
| N=128 P=4 α=0.03 | 1.0000 | True | 4.0397 |