Benchmarking Agents for Proving Theorems in Quantum Algorithms and Quantum Information
This paper introduces Lean-QuantumAlg-Bench and Lean-QIT-Bench, two Lean 4 benchmarks for evaluating AI agents on quantum theorem proving, demonstrating that library-augmented deduction significantly improves performance while revealing specific domain weaknesses and efficiency trade-offs across four leading models.
Original authors: Lei Zhang, Yusheng Zhao, Yimeng Cao, Ranyiliu Chen, Mingrui Jing, Jizhe Lai, Ziao Tang, Jingu Xie, Hongshun Yao, Xuanqiang Zhao, Guocheng Zhen, Chengkai Zhu, Xin Wang
Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer
Imagine a world where the laws of physics are written in a language so precise that a computer can check every single step of a scientist's reasoning, leaving no room for a "maybe" or a "I think this works." This is the realm of formal verification, a high-stakes game where mathematicians and computer scientists translate complex theories into code that a machine can read like a strict grammar teacher. In the specific corner of science called quantum computing, things get even wilder. Quantum computers don't just count; they dance with probabilities, using strange rules where particles can be in two places at once or instantly connected across the universe. Because these rules are so tricky, even the smartest human experts sometimes make tiny mistakes in their calculations. That's why we need "proof assistants"—computer programs that act like super-strict editors, ensuring that every claim about quantum magic is actually true before we build the machines. But here's the big question: Can Artificial Intelligence (AI) learn to be this strict editor? Can a robot read a quantum problem, figure out the steps, and write a proof that the computer accepts without any help?
This paper, titled "Benchmarking Agents for Proving Theorems in Quantum Algorithms and Quantum Information," sets out to answer that question by creating a rigorous test for AI. The researchers built two massive "exam halls" for AI agents: one called Lean-QuantumAlg-Bench with 36 tricky problems about quantum algorithms (like the famous Shor's algorithm for cracking codes), and another called Lean-QIT-Bench with 40 problems about quantum information theory (dealing with how information is stored and moved in quantum systems). They didn't just ask the AI to guess; they gave the problems to four different top-tier AI models and watched to see if the models could write a proof that the computer would accept as correct. The results were a mix of hope and reality checks. The AI models managed to solve some problems, with the best scores reaching about 60 out of 100 on the algorithm test and 59.6 out of 100 on the information theory test. However, the paper found that the AI struggled significantly in specific areas like simulating quantum systems and understanding entanglement. A key discovery was that giving the AI a "verified library"—a cheat sheet of already-proven facts to look at—significantly boosted its performance, improving scores by up to 15.9 points in some cases. This suggests that while AI isn't ready to be a fully independent quantum scientist yet, it can become much more capable if it has access to trusted, pre-checked knowledge to guide its reasoning. The study also highlighted that different AI models have very different "costs," with some being much cheaper or faster than others, showing that there is no single "best" robot for the job, but rather a trade-off between speed, cost, and smarts.
Technical Summary: Benchmarking Agents for Proving Theorems in Quantum Algorithms and Quantum Information
Problem Statement While formal verification is increasingly practical for quantum computing, the capability of AI agents to construct machine-checkable proofs within this domain remains unquantified. Quantum formalization presents unique challenges: quantum states and operators possess finite-dimensional, type-level structures; circuit calculations require linking syntactic transformations to linear-algebraic semantics; and information-theoretic inequalities depend on specific domains, support conditions, and positivity hypotheses. Furthermore, textbook notation often suppresses coercions, basis choices, and tensor-factor ordering, which must be explicit in a theorem prover like Lean. Existing benchmarks (e.g., miniF2F, PutnamBench) focus on general mathematics or competition problems, while domain-specific evaluations often lack controlled library access or rigorous semantic validation against the intended mathematical claims. There is a need for a reproducible baseline to evaluate how well AI agents can navigate the specific interfaces and typed structures required for quantum algorithms and quantum information theory (QIT).
Methodology The authors introduce two coordinated Lean 4 benchmark suites: Lean-QuantumAlg-Bench (QAlg-Bench) and Lean-QIT-Bench (QIT-Bench).
Benchmark Construction:
Scope: The suites contain 76 theorem-completion tasks in total (36 for QAlg-Bench, 40 for QIT-Bench).
Fields: Tasks are organized into six distinct fields:
Quantum Algorithms: State and Operator Methods (SOM), Circuit and Algebraic Algorithms (CAA), and Simulation, Signal Processing, and Learning (SSL).
Quantum Information: Quantum Channels and Representations (QCR), Operator and State Geometry/Symmetry/Distinguishability (GSD), and Quantum Information Measures and Entanglement (IME).
Validation Workflow: Problems are selected from established literature, translated into Lean by agents with researcher oversight, and subjected to automated checks. Every task must compile in a fixed Lean environment. For high-risk statements, a targeted manual semantic review ensures the formal signature faithfully captures the mathematical claim, checking for omitted hypotheses, incorrect type encodings, or weakened conclusions.
Task Format: Tasks provide theorem statements and supporting definitions but offer no hints. Success is defined strictly by whether the submitted theorem body compiles in the fixed environment without new axioms, sorry placeholders, or modifications to external files.
Evaluation Framework:
Models: Four models were evaluated: GPT-5.5, Kimi K3, DeepSeek V4-Pro, and MiniMax M3.
Settings: Two conditions were tested:
Task-only Baseline: The agent receives only the theorem statement and definitions.
Library-Augmented Deduction (LAD): The agent receives the task plus access to a verified domain library for consultation.
Metrics:
Difficulty-Weighted Score:100×∑di∑divi, where di is the pre-assigned difficulty (1–10) and vi is the binary acceptance indicator.
Completion Rate: The unweighted fraction of tasks solved.
Cost Efficiency: Economic cost (USD per score point) and time cost (seconds per score point).
Key Contributions
First Domain-Specific Benchmarks: The introduction of QAlg-Bench and QIT-Bench, the first benchmarks specifically designed to evaluate AI agents on machine-checkable proofs in quantum algorithms and information theory using Lean 4.
Rigorous Validation Protocol: A construction workflow that combines universal automated compilation checks with targeted semantic validation to ensure the formal tasks accurately reflect the underlying mathematics, addressing the "informal–formal fidelity" gap.
Empirical Analysis of Library Access: A systematic evaluation of the "Library-Augmented Deduction" (LAD) setting, demonstrating how access to verified domain libraries impacts agent performance.
Granular Performance Profiling: An analysis that decomposes performance by mathematical field, revealing specific strengths and weaknesses in agent capabilities across different quantum sub-domains.
Results
Performance Scores: The highest difficulty-weighted scores achieved were 60.4/100 on QAlg-Bench and 59.6/100 on QIT-Bench.
Impact of LAD: In all eight model–benchmark comparisons, the LAD setting improved both the score and the completion rate compared to the baseline. Gains ranged up to 15.9 points (e.g., DeepSeek V4-Pro on QAlg-Bench saw a +42.5% relative increase).
Model Variance: GPT-5.5 achieved the highest observed scores across all suite–condition combinations. However, cost efficiency varied significantly; DeepSeek V4-Pro exhibited the lowest economic cost per score point, while GPT-5.5 had the lowest time cost.
Field-Level Weaknesses: Performance was uneven across fields. Agents consistently struggled with Quantum Simulation, Signal Processing, and Learning (SSL) in QAlg-Bench and Quantum Information Measures and Entanglement (IME) in QIT-Bench. Conversely, performance was relatively stronger in areas like Quantum Channels (QCR) and Circuit Algebraic Algorithms (CAA).
Cost Trade-offs: The paper highlights significant capability–efficiency trade-offs. For instance, MiniMax M3 doubled its score on QAlg-Bench (from 6.4 to 12.8) under LAD, but this came from a low baseline, whereas GPT-5.5 achieved larger absolute gains.
Significance and Claims The paper claims that these benchmarks establish a reproducible baseline for developing more capable and reliable proof agents. By isolating the effects of library access and providing a controlled environment for evaluation, the work enables the measurement of progress in agentic proving for quantum science. The results suggest that verified libraries are a critical component for strengthening domain-specific proof agents, particularly in complex areas like quantum simulation and entanglement theory. The authors position this work as a step toward "self-evolving AI scientists" capable of advancing quantum information science, though they note that current agents still exhibit recurring weaknesses in specific sub-fields. The paper does not claim to have solved formal verification for all quantum problems but rather provides the necessary infrastructure to measure and improve agent performance in this domain.