DeepMind and Google Quantum AI use Lean 4 to discover formally verified quantum algorithms
Researchers at Google DeepMind and Google Quantum AI have described an automated pipeline that uses large language model agents inside the Lean 4 theorem prover to discover and formally verify quantum algorithms, Quantum Computing Report wrote on 10 November.
The work is detailed in a paper titled "Discovering Formally Verified Quantum Programs with AI." According to the report, the system pairs multi-agent search with formal quantum Hoare logic, so candidate programs can be synthesised and then machine-checked, including at sizes that are beyond classical simulation.
The report says evaluating quantum subroutines with classical computers is limited to small qubit counts or restricted gate sets. When algorithms grow to thousands of logical qubits, classical checking becomes impractical. The Google team specified problems in Lean 4 as Hoare triples (precondition, program and postcondition) together with proofs of correctness and resource bounds. Heterogeneous Gemini agent teams iterate on candidates, share lemmas and code, and an independent Lean comparator checks that proofs meet frozen specifications without custom axioms or unproven placeholders, the report said.
Fault-tolerant cost is measured as Q · T, the peak logical qubit count multiplied by the non-Clifford T-gate count, used as a proxy for physical spacetime because magic-state preparation dominates many surface-code execution cycles. Quantum Computing Report summarised several benchmark improvements attributed to the paper:
- 25-bit fixed-point arcsin state preparation: Q · T reduced by more than 290 times, from more than 1.08 × 10^8 to 3.70 × 10^5, with non-Clifford T gates cut to 3,698 across 100 qubits.
- Alpha-particle electronic stopping power in warm dense hydrogen: Q · T lowered 10.9 times, from 5.42 × 10^15 to 4.98 × 10^14, using 4,374 logical qubits, with qubitised walk steps reduced 12.8 times.
- Non-Born-Oppenheimer molecular dynamics of C23H20N3O: Q · T reduced 8.08 times, from 4.98 × 10^15 to 6.16 × 10^14, across 6,057 logical qubits.
- Cytochrome P450 Compound I active-space states: Q · T improved 2.49 times, from 1.09 × 10^12 to 4.37 × 10^11, on 333 logical qubits.
- Multi-target parallel Grover search (m, k ≤ 1,024): up to 1.22 times speedup in expected oracle rounds for finding any target, and up to 2.55 times for finding all targets.
Those figures are as reported from the paper by Quantum Computing Report; they have not been independently re-run here. The report said the agents replaced some literature techniques, for example using measurement-based ancilla uncomputation and Bernstein polynomials in the photochemistry case, and one-hot orbital registers in the P450 case, which it said cut T-gate counts per walk step by 40%.
A preprint with technical specifications and proofs is linked from the report on arXiv. Formal verification of the discovered programs is a claim about machine-checked proofs in Lean, not a demonstration on current quantum hardware at those qubit counts.
