Discovering formally verified quantum programs with AI
Authors: 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 D. 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
Organizations: Google DeepMind · Google Quantum AI
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 Gemini 4 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 2.55x), 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.
Figures & tables
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 [ 154 ] .
Figure 2: Lean specifications for discovery tasks. An abridged specification for electronic stopping power in warm-dense hydrogen [ 195 ] , where the goal is to construct a quantum program that simulates time evolution under the system Hamiltonian H . The agents fill in each sorry statement, which is Lean’s placeholder for an unfilled definition or proof: the ancilla qubit count, the circuit and its claimed cost, and the proofs of the correctness and cost theorems. ( 1 ) The system qubits store the momentum of every quantum particle. ( 2 ) A unitary matrix W on the system and ancilla qubits (extra qubits used to aid computation) must simulate time evolution e−iH(c)t for every physically allowed electron state, up to a specified error, and return the ancillas to ∣0⟩ . ( 3 ) The compiled program must act as W on grid states whenever the ancillas start in ∣0⟩ . ( 4 ) The cost is a function of the logical spacetime volume Q⋅T multiplied by the repeated runs of the stopping power routine: 50 repeats × 10 time steps ×Q⋅T (Sec. 2.3 ).
Figure 3: Summary of verified results. a) Quantum algorithm cost for baselines and solutions from this work across application domains. b) Logical-qubit and T -gate improvements on the three scientific applications, with feathered hardware horizons (dashed lines at geometric midpoints) for medium-term fault-tolerant quantum computing (FTQC † ; teraquop planar architectures [ 208 , 154 ] ) and application-scale FTQC ‡ (fault-tolerant application-scale quantum computers, FASQ [ 149 , 148 , 208 ] ). Grey points denote published baselines, red points denote refined baselines incorporating subsequent methodological improvements from the literature, and blue points denote this work. For cytochrome P450, the published ground-state estimate is extended to all eigenstates within 0.1 Ha of E0 , raising its cost by 0.85% . c) Cost for 25 -bit fixed-point arcsin ( ε≤1.25×10−7 ) against piecewise-polynomial evaluation [ 157 ] . d) Speedup in expected number of rounds for large N of our verified parallel Grover circuits over the strongest published baseline [ 209 , 210 , 211 , 212 , 213 ] for powers of two m,k≤210 when finding any one or all of k marked targets with m parallel queries per round (dashed contours: 1.00× boundary; ∗ markers: peak speedups of 1.22× and 2.55× ).
Figure 5: Cross-team collaboration and idea lineage. a) Lineage of verified circuits for non-Born–Oppenheimer dynamics across Teams 1–3 (of seven participating teams) from the baseline (seed) to the final circuit (star), with the Q⋅T reduction of each step. Within-team discoveries enter from below; cross-team conference and wiki ideas enter from above. b) Share of the logarithmic Q⋅T reduction from within-team ideas, cross-team wiki entries, and conference exchanges once both channels were active on each scientific application, with reduction factors over this window shown at right and the unweighted average at bottom. c) Cross-team evolution of one stopping-power idea across wiki records #1–#5 and conference critiques, narrowing the shared ancilla register from 288 to 231 qubits before the final space–time trade-off ( 246 qubits).
Appendix figures & tables12 assets
Supplementary material from the paper’s appendix.
Appendix
Figure S1: Verification library and specification stack. Built on Mathlib [ 192 ] , Physlib ’s Lean-QuantumInfo [ 194 , 193 ] in Lean, our quantum Hoare logic [ 189 , 244 ] formalizes classical–quantum states, weakest preconditions and resource costs, supporting problem specifications (correctness theorem and cost bound) across dynamic Clifford+ T circuits and black-box query algorithms.
Figure S2: A formal definition of the clean-ancilla property. Here, a program P implements the unitary U on register rTarget and returns the disjoint ancilla register rAnc to ∣0⋯0⟩ : for every predicate M , from any input with clean ancillas, P must end with clean ancillas and satisfy M at least as often as applying U would. Since M is arbitrary, P acts exactly as U on all such inputs.
Program P
Denotational semantics [[P]](Δ)
Weakest precondition wp(P,Ψ)
skip
Δ
Ψ
abort
0
0
x:=e
σ′↦∑σ:σ[x↦e(σ)]=σ′Δ(σ)
σ↦Ψ(σ[x↦e(σ)])
qset
σ↦Tr(Δ(σ))∣0⟩⟨0∣
σ↦⟨0∣Ψ(σ)∣0⟩I
applyU
σ↦UΔ(σ)U†
σ↦U†Ψ(σ)U
x:=measureM
σ′↦∑oMo[[x:=o]](Δ)Mo†
σ↦∑oMo†Ψ(σ[x↦o])Mo
Appendix
Figure S3: Inductive definitions of the denotational semantics [[P]](Δ) and weakest precondition wp(P,Ψ) . For a guard b , Δ∣b retains Δ(σ) where b(σ)=0 and sets all other branches to 0 (similarly for Ψ∣b and ¬b ). Loop unrollings start from W0(Δ)=0 and Ψ0=0 .
Figure S4: Layout of one problem directory in the shared wiki (stopping power). The best solution and the reusable partial Lean modules are checked by the external verifier against the frozen specification before merging, while idea notes are reviewed summaries labeled verified, promising, or dead-end. Each verified record in history.md lists the teams credited for it.
Figure S5: A cross-team conference exchange between two verified records in the stopping power problem (records #1 and #2 of Fig. 5 c). Each numbered post replies directly to the one above it, across two conference sessions. Colored bars mark the team, the italic line is an analysis summary, and quoted text is verbatim from the conference; “…” marks omitted text, and words in square brackets, such as [the subroutine], replace Lean code snippets used in the original posts.
Table S1: Fault-tolerant capability regimes and hardware horizons. Summary of the capability regimes referenced in Fig. 3 b, listing plotted dashed-line midpoints (Q,T) , nominal upper-bound ceilings (Qmax,Tmax) (rendered in Fig. 3 b with 14-step normal-quantile feathering spanning Q≈5.9×102–1.7×103 , T≈3.5×108–2.9×109 for teraquop planar and Q≈5.0×103–2.0×104 , T≈3.5×1010–2.9×1011 for FASQ), nominal spacetime volume Q⋅T , and representative benchmarks and references.
Figure S6: Parallel Grover query model. Workspace allocation ( qset , +0 query cost) initializes m query registers of n+1 qubits and w ancilla qubits in ∣0⟩⊗Q together with a classical state σ∈Σ . Unitary evolution ( step , +0 ) applies any S -independent unitary U∈U(2Q) across all Q qubits. Parallel oracle querying ( oracle , +1 ) applies OS⊗m (Eq. ( 5 )) simultaneously across m disjoint (n+1) -qubit subregisters. Projective measurement ( measure , +0 ) measures a subregister into classical variable y in σ while leaving unmeasured wires coherent. Classical control ( qif / qwhile ; Appendix A ) branches and loops on predicates of σ , weighting each oracle round by the active-branch probability ∑σ:b(σ)Tr(Δt(σ)) until ¬b(σ) outputs the result.
Figure S9: High-level circuit for the collective Johnson-graph walk. Registers hold m address slots ( ∣0⟩⊗mn ), m flag qubits ( ∣0⟩⊗m ), and a kn -qubit archive ∣F⟩ of found targets. (1) prep prepares the uniform superposition (mN)−1/2∑∣E∣=m∣E⟩ over m -subsets E⊆{0,…,N−1} . (2) For L<N/m rounds ( L× ), (XH)⊗m ( X then H ) and (HX)⊗m switch the flags between ∣0⟩⊗m and ∣−⟩⊗m ; OS⊗m is the parallel marking oracle; UF unmarks slots already in F , so the dotted block applies (−1)∣E∩(S∖F)∣ ; and RJ is an S -independent Johnson-graph reflection compiled via QSVT. (3) After one call to OS⊗m and UF , Ustore records new hits into ∣F′⟩ and measuring the flags outputs the hit count w=∣E∩(S∖F)∣ .
Figure S10: Baseline circuit to implement the arcsin function [ 157 ] , using n=35 , m=3 , d=3 . After restricting to the positive range, the approximation splits the calculation of arcsin between a degree- 3 polynomial in the interval [0,0.5] and a Newton iteration for the square root function in [0.5,1] . Number of T gates and number of qubits calculated as in their Appendix, for reversible computation.
Method
ε
Toffoli
T
Q
Spacetime cost ( Q⋅T )
Baseline [ 157 ] (lower bound)
∼10−6
110,144
440,576
245
1.08×108
– arcsin on [−0.5,0.5]
34,608
138,432
—
—
– 1/z
75,536
302,144
—
—
Kickmix
1.25×10−7
1,038
4,152
100
415,200
Non-kickmix (Lean 4)
1.25×10−7
776
3,698
100
369,800
Appendix
Table S2: Summary for fixed-point arcsin(y) on [−1,1] at k=25 . The baseline evaluates the (n,m,d)=(35,3,3) configuration [ 157 ] , assuming 4T per Toffoli [ 170 , 254 ] . We derive a lower bound on its spacetime cost by summing the two dominant reversible submodules on the 245 -qubit square-root workspace while neglecting persistent registers and the steps that combine the two parts. In the non-kickmix Lean 4 circuit, the 3,698T gates comprise 776 four- T temporary- AND gates ( 3,104T ) plus 594 single-qubit T / T† gates across 41 inner-product gadgets.
Figure S11: Sketch of the algorithm to implement the fixed-point arcsin module. (a) Full kickmix circuit. It uses 50 data qubits ( ∣y⟩ and ∣b⟩ , 25 each) and 50 ancilla qubits reused across stages, and a total of 4,152T gates. The bin index s has 9 bits but needs only 2 extra ancillas. After "shift ∣y∣→t ", 6 bits of s are simply the top 6 bits of t , which identify the bin within its group. A 7 th bit replaces the 21 bit of ∣y∣ , which can be recomputed from s and is erased. The remaining 2 bits use one ancilla each: one is stored directly, and the other replaces the top bit of ∣y⟩ , whose value is moved into an ancilla. t2 is computed into the ancillas freed by clearing A . At peak, the ancillas hold A ( 19 ), B and C ( 24 ), 5 lookup work qubits, 1 bit of s , and the moved bit of ∣y⟩ . (b) Improved block in the non-kickmix circuit. Algorithm verification with our formal quantum computation library allows further optimization of the circuit. Specifically, the coefficient lookup block can be replaced with a more efficient block, saving overall 454T gates. Each coefficient bit is computed by one inner-product block taking a variable number r∈{2,…,7} of product pairs and using 2r+2T gates. We have 26 blocks totaling 364T gates before +A , and 15 blocks totaling 230T gates on the freed qubits after clearing A . Each inner-product block leaves an extra sign phase that is then removed before returning the result. The whole circuit requires now 3,698T gates instead of 4,152T gates. (c) Example of the optimized inner-product block for two product pairs, using 6T gates, which could not be expressed in the kickmix framework.
Part of a walk step
Baseline
This work
Rotations and their angles
37,688
23,636
Index decoding
264
440
Spin swaps
928
464
Outer state preparation
1,032
598
Inner state preparation
5,888
2,264
Total
45,800
27,402
Appendix
Table S3: T gates per walk step for the baseline and for a step inside the first eight blocks ( 45,440 steps) of the best verified circuit. Reflections and phase-estimation control are counted separately in the text.
Scaling quantum computing toward practical quantum advantage is currently limited by the efficiency of circuits that operate on information encoded by quantum error-correcting codes. The full stack of quantum computing encompasses several tasks: preparation of logical code states, implementation of logical gates, logical routines on encoded qubits, etc. Yet, these circuits are largely designed by hand for individual cases, with some recent works incorporating machine learning for certain aspects. We formulate this problem as agentic evolutionary program synthesis, wherein a large language model, leveraging its pretraining knowledge and tool-use proficiency, and guided by a circuit verifier, evolves a program that defines a Clifford circuit for a wide range of curated tasks such as logical state preparation, logical gate design, and logical routines such as code-switching, code growth, etc. Our approach consistently finds fault-tolerant circuits for all of these tasks, each verified by an exhaustive check over faults.
Aritra Lahiri, Florian Marquardt
Max Planck Institute for the Science of Light, 91058 Erlangen, Germany · Department of Physics, Friedrich-Alexander University Erlangen-Nürnberg, 91058 Erlangen, Germany
AI scientists are expanding automated research across scientific domains, yet their ability to turn the scientific record into a foundation for autonomous discovery remains elusive. Here we uncover a fundamental barrier to this transition and demonstrate a route to overcome it in computational quantum science, where advances shape both what we can learn from complex quantum systems and what quantum computing can ultimately deliver. To identify this barrier, we introduce OmniQ, an expert-audited virtual research environment that converts published studies into executable reproduction tasks. Across 59 papers spanning classical simulation, quantum algorithms and quantum-property characterization, we systematically evaluate five agentic systems powered by large language models and six third-party agent harnesses. Our findings reveal that current AI scientists often fail to reproduce published results, exposing a fundamental mismatch between what scientific papers communicate and what autonomous agents require. By contrast, human expert intervention can turn these failures into successful reproductions, showing that the missing information can be identified and converted into reusable research experience. Guided by this observation, we develop Residual Agents (RA), a quantum-tailored self-improving AI scientist that distils externally verified workflow repairs into such experience. RA substantially improves research performance under fixed base models and limited adaptation budgets. For example, RA raises DeepSeek V4.1 Flash performance from 68% to 85%, matching Claude Code with Opus 5 at a third of its cost despite using a weaker base model. We integrate all reproduced results into an extensible platform built on the model context protocol, making verified research workflows directly accessible to AI scientists and allowing new scientific papers to be continuously incorporated.
Yuxuan Du, Hanqing Zhao, Xinbiao Wang +3
College of Computing and Data Science, Nanyang Technological University, Singapore 639798, Singapore · School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore 639798, Singapore
Designing quantum algorithms is a complex and counterintuitive task, making it an ideal candidate for AI-driven algorithm discovery. To this end, we employ the Hive, an AI platform for program synthesis, which utilises large language models to drive a highly distributed evolutionary process for discovering new algorithms. We focus on the ground state problem in quantum chemistry, and discover efficient quantum heuristic algorithms that solve it for molecules LiH, H2O, and F2 while exhibiting significant reductions in quantum resources relative to state-of-the-art near-term quantum algorithms. Further, we perform an interpretability study on the discovered algorithms and identify the key functions responsible for the efficiency gains. Finally, we benchmark the Hive-discovered circuits on the Quantinuum System Model H2 quantum computer and identify minimum system requirements for chemical precision. We envision that this novel approach to quantum algorithm discovery applies to other domains beyond chemistry, as well as to designing quantum algorithms for fault-tolerant quantum computers.