Optical breadboard with yellow fiber patch cords in an empty lab, no logos or text
AI-generated image

Research

DeepMind and Google Quantum AI use Lean 4 to discover formally verified quantum algorithms

Published · Last updated

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:

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.

← All news