A Machine-Verified Proof of a Quantum-Optimization Conjecture
2026-06-29 • Artificial Intelligence
Artificial IntelligenceMachine LearningLogic in Computer Science
AI summaryⓘ
The authors solved a long-standing quantum computing question about how well a specific algorithm called QAOA works on a certain problem setup. They used an AI language model together with a computer proof system named Lean 4 to create and fully verify the proof. The AI found a clever hidden pattern in the problem to complete the proof, requiring humans only to check that the setup was correct but not the proof details. This shows AI and formal tools can help prove difficult quantum science problems reliably.
Quantum Approximate Optimization Algorithm (QAOA)Farhi-Goldstone-Gutmann conjecturering of disagreesapproximation ratiomachine-verified proofLean 4 proof assistantformal verificationquantum informationdynamical symmetryAI-assisted theorem proving
Authors
Uri Kol, Maor Ben-Shahar, Kfir Sulimany, Dirk Englund
Abstract
We report a machine-verified resolution of a problem open for over a decade in quantum optimization: the Farhi, Goldstone and Gutmann (FGG) conjecture that depth-$p$ Quantum Approximate Optimization Algorithm (QAOA) on the ring of disagrees attains approximation ratio $(2p+1)/(2p+2)$ exactly. We found the proof using a large language model, Claude Fable 5, and verified its correctness end-to-end by the Lean 4 proof assistant. Our methodology includes several ingredients: building on a substantial Lean library of quantum information, we formalized the QAOA components and the known parts of the problem, and reduced the conjecture to a single open mathematical statement. The model was then handed the library and our agentic toolkit, and tasked with closing that gap by constructing a proof in Lean. The resulting process is a feedback loop between the model's natural-language reasoning and Lean's mechanical verification, which converged to a machine-verified proof. Human verification is required only for the structural scaffolding - that the formal statement faithfully encodes the intended claim - while the proof itself is supplied by the model and certified mechanically by Lean. The proof is nevertheless striking - the model uncovered a hidden dynamical symmetry of the problem and exploited it, borrowing tools and machinery from an adjacent field to turn a hard existence problem into an explicit construction. This work paves the way for resolving open conjectures in quantum information science and beyond.