arXiv:2606.29687quant-phcs.AI2026-06被引 7

用AI+形式化验证,证明了量子优化10年未解的猜想。

A Machine-Verified Proof of a Quantum-Optimization Conjecture

  • 借助大模型生成思路,用Lean系统机械验证,闭环完成证明。
  • 确认深度p的QAOA在环状反向问题上精确达到(2p+1)/(2p+2)逼近比。
  • 揭示隐藏对称性,跨领域借用工具,适合量子算法与形式化验证研究者。

我们报告了一个超过十年未解的量子优化问题的机器验证解决:Farhi、Goldstone和Gutmann(FGG)猜想,即在环状反向问题上,深度为p的量子近似优化算法(QAOA)能达到精确的逼近比(2p+1)/(2p+2)。该证明通过大语言模型Claude Fable 5生成,并由Lean 4证明助手端到端验证。方法包括构建大型量子信息形式化库,形式化QAOA组件与已知部分,将猜想归约为单一待证数学命题。模型在获得库与智能体工具包后,被任务以Lean语言构造证明。整个过程形成自然语言推理与机械验证的反馈循环,最终收敛至可验证证明。人类仅需验证形式陈述是否忠实表达原意,而证明内容由模型生成并由Lean机械认证。该证明极具洞察力:模型发现问题中的隐藏动力学对称性,借用邻近领域工具,将复杂存在性问题转化为显式构造。本工作为解决量子信息科学等领域开放猜想开辟新路径。

原文摘要 · Abstract (English)

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.

量子优化形式验证大模型证明生成

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。