Discovering formally verified quantum programs with AI
Organizations: Google DeepMind · Google Quantum AI
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 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
Appendix figures & tables12 assets
Supplementary material from the paper’s appendix.
Appendix
| Program | Denotational semantics | Weakest precondition |
|---|---|---|
| skip | ||
| abort | ||
| qset | ||
| Capability regime | Midpoint | ceiling | ceiling | Benchmarks & references | |
|---|---|---|---|---|---|
| Medium-term FTQC (teraquop) | Cytochrome P450; compact catalysis & ECC [ 261 , 265 , 235 , 260 , 236 , 207 , 208 , 154 ] | ||||
| Application-scale FTQC (FASQ) | Stopping power, dynamics; catalysis, materials & RSA [ 150 , 269 , 174 , 148 , 262 , 267 , 266 , 195 , 149 , 205 ] |
| Method | Toffoli | Spacetime cost ( ) | |||
| Baseline [ 157 ] (lower bound) | |||||
| – on | — | — | |||
| – | — | — | |||
| Kickmix | |||||
| Non-kickmix (Lean 4) |
| Part of a walk step | Baseline | This work |
|---|---|---|
| Rotations and their angles | ||
| Index decoding | ||
| Spin swaps | ||
| Outer state preparation | ||
| Inner state preparation | ||
| Total |
Automated Algorithm Discovery
Automated algorithm discovery develops methods that generate and test executable algorithms for optimization, science, software, and machine learning.
See all 179 papers