FGG Conjecture for QAOA on the Ring of Disagrees
For an even cycle of size and depth with , is the optimal QAOA approximation ratio for MaxCut exactly , as Farhi, Goldstone and Gutmann conjectured?
- Result
- Proved
- Status
- Resolved
- AI contribution
- AI-discovered
- Method
- Argument
- Field
- Quantum optimization
- Posed by
- Edward Farhi, Jeffrey Goldstone & Sam Gutmann
- Year posed
- 2014
- Years open
- 12y
- Solved
- 2026-06-29
- Model
- Claude Fable 5
- Vendor
- Anthropic
- Collaborators
- —
- Verification
- Lean-verified
- Publication
- Preprint
- Significance
- 15 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What the AI did
Claude Fable 5 found a dynamical-symmetry and quantum-signal-processing argument; the complete proof is checked by the Lean 4 kernel. An independent group proved the same result simultaneously via Laurent-polynomial optimization (arXiv:2606.29562).
Verification
Machine-verified end to end in Lean 4, with an independent simultaneous human proof of the same theorem.
Sources
arXiv:2606.29687 - A machine-verified proof of a quantum-optimization conjecture