Discovering formally verified quantum programs with AI

Sergey Shirobokov, Ben Jaderberg, Katerina Hristova, George Tsoukalas, Johannes Bausch, Eric Wieser, Francisco J. H. Heras, Nicholas C. Rubin, Guang Hao Low, Sébastien Racanière, Nenad Tomašev, Lei M. Zhang, James Watson, Tanuj Khattar, Aws Albarghouthi, Stavan Jain, Harun Khan, Leopoldo Sarra, Andrew W. Senior, Michael Broughton, Hussain Masoom, Sergio Boixo, Ryan Babbush, Swarat Chaudhuri, Pushmeet Kohli

TL;DR

Google DeepMind researchers have developed a multi-agent AI system that uses the Lean theorem prover to discover and formally verify new, highly efficient quantum algorithms. By replacing classical simulation with rigorous mathematical proof, they achieved order-of-magnitude resource reductions for critical scientific simulations, including a 290x improvement in quantum arithmetic.

What Problem Does This Paper Address?

Designing quantum algorithms is a manual, multi-year process that relies on intense expert collaboration. A major hurdle is verification: once a quantum circuit exceeds a few dozen qubits, classical computers can no longer simulate it to check if it works correctly. This "simulation wall" has historically limited AI-driven discovery to small, toy-scale problems. To reach the era of practical, fault-tolerant quantum computing, we need a way to design and verify algorithms for thousands of qubits that today's computers cannot even test.

Methods

The authors introduced a research workflow that pairs Large Language Model (LLM) agents with the Lean theorem prover.

  • Formal Verification Library: They built a library in Lean based on Quantum Hoare Logic (QHL). This allows them to mathematically prove that a program meets a specification and to rigorously count its resource costs (defined as the spacetime volume: qubits $\times$ T-gates).
  • Multi-Agent "Lab": Heterogeneous teams of LLM agents collaborate to solve problems. They iterate based on error feedback from the Lean kernel, share partial results via a shared wiki, and "discuss" strategies in scheduled virtual conferences.
  • Specification-Driven Discovery: Human researchers define the problem and cost constraints as a Lean "specification" with placeholders (using Lean's sorry keyword). The AI agents' job is to fill in these placeholders with valid code and the accompanying mathematical proof.
Figure 1: Formally verified multi-agent quantum program discovery. a) Researchers write a Lean quantum Hoare logic specification of correctness and cost, then launch their agent team, which iterates on error feedback from the Lean kernel. Teams publish independently re-verified solutions, partial results and dead ends to a shared wiki, and exchange ideas and critiques in scheduled conferences. b) Bars indicate which problem each approach can reach. AI search checked by numerical tests can only produce solutions that can be simulated classically (dashed line), which for arcsin means a restricted gate set.7

Datasets

The system was evaluated on five diverse quantum computing benchmarks, representing both fundamental subroutines and large-scale applications:

  1. Parallel Grover Search: Finding marked items in an unstructured list using parallel queries.
  2. Fixed-Point Arcsin: A critical quantum arithmetic subroutine for loading data into wavefunctions.
  3. Electronic Stopping Power: Simulating alpha-particle energy loss in fusion fuel (warm-dense hydrogen).
  4. Non-Born–Oppenheimer Dynamics: Simulating photochemistry in complex molecules ($C_{23}H_{20}N_3O$).
  5. Cytochrome P450: Estimating energy levels for drug metabolism studies.

Key Insights and Ideas

  • Proof Over Simulation: By using formal proofs instead of numerical tests, the system can verify algorithms for thousands of qubits—regimes where classical simulation is physically impossible.
  • Emergent Collaboration: The best solutions often emerged from cross-team interactions rather than single agents. For example, one team's conference proposal might be refined and proved by another team, leading to significant cost drops.
  • AI-Discovered Mechanisms: The AI didn't just optimize; it found novel algorithmic tricks. In fusion simulations, it learned to exploit Pauli exclusion on a real-space grid to simplify electron interactions. For Cytochrome P450, it replaced complex table lookups with a more efficient one-hot register approach.
  • Safety at Scale: Machine-checked verification makes open collaboration safe; teams can build on each other's Lean proofs without needing manual code review, as the Lean kernel automatically rejects flawed logic.
Lean specifications for discovery tasks

Key Results

The workflow produced verified programs that significantly outperformed existing human-designed baselines:

  • Quantum Arithmetic (arcsin): A massive 290x reduction in spacetime cost.
  • Fusion Simulation: A 10.9x reduction in resources.
  • Photochemistry: An 8.08x reduction.
  • Drug Metabolism: A 2.49x reduction.
  • Parallel Grover Search: Up to a 1.41x speedup in query rounds.
Summary of verified results across application domains

Limitations and Future Work

  • Specification Constraints: Agents are limited by the human-written specification. If a spec is too rigid (e.g., fixing a specific mathematical representation), the AI cannot optimize beyond those initial bounds.
  • The Gap to Hardware: While these reductions are significant, the resource requirements for these simulations still exceed the projected capabilities of early fault-tolerant quantum computers. Further orders-of-magnitude improvements are needed.
  • Future Directions: The authors suggest extending formal specifications to include hardware-specific constraints like error-correcting codes, qubit routing, and physical layout to co-design algorithms and hardware architectures simultaneously.

Summary updated

Abstract

The timeline by which quantum computers can solve breakthrough problems in science depends on improved quantum algorithms as much as on better hardware. Such algorithmic advances are typically achieved through many years of expert human collaboration. In mathematics and computer science, large language models have accelerated progress through automated discovery loops. However, quantum algorithms can only be evaluated by classical computers on restricted or small instances. Here we demonstrate automated discovery of quantum programs beyond these regimes including order-of-magnitude improvements on scientific applications. To achieve this, we build a quantum program library in the Lean theorem prover in which large language model agents synthesize novel programs against formal problem specifications and verify their correctness and cost. Agent teams collaborate, sharing results and knowledge through wikis and discussing ideas at organized conferences. Our results improve on prior baselines for parallel search (up to 1.4x), quantum arithmetic (290x), and simulations relevant to fusion, photochemistry and drug-metabolism by 11x, 8x and 2.5x respectively. Combining human and artificial intelligence at scale, under the rigor of mathematical proof, lets researchers design algorithms that today's classical and quantum computers cannot test, shortening the path to practical quantum computation.
BibTeX
@misc{shirobokov2026discovering,
  author = {Sergey Shirobokov and Ben Jaderberg and Katerina Hristova and George Tsoukalas and Johannes Bausch and Eric Wieser and Francisco J. H. Heras and Nicholas C. Rubin and Guang Hao Low and Sébastien Racanière and Nenad Tomašev and Lei M. Zhang and James Watson and Tanuj Khattar and Aws Albarghouthi and Stavan Jain and Harun Khan and Leopoldo Sarra and Andrew W. Senior and Michael Broughton and Hussain Masoom and Sergio Boixo and Ryan Babbush and Swarat Chaudhuri and Pushmeet Kohli},
  title = {{Discovering formally verified quantum programs with AI}},
  year = {2026},
  eprint = {2611.09822},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.09822},
}
Figure