Claimed Search scaffold

LLM agents write quantum programs checked against Lean specifications

Google DeepMind and Google Quantum AI report that teams of language model agents, searching against frozen Lean specifications that an external verifier re-checks, found quantum programs that cut published resource costs by up to 290 times for fixed-point arcsine and by factors of 11, 8 and 2.5 on simulations relevant to fusion, photochemistry and drug metabolism.

Model
Not named: the paper says only that large language model agents synthesize the programs
Field
Computer science
Date
2026-11-06
Human collaborators
Sergey Shirobokov, Ben Jaderberg, Katerina Hristova, George Tsoukalas, Nicholas C. Rubin, Guang Hao Low, Sergio Boixo, Swarat Chaudhuri, Ryan Babbush, Pushmeet Kohli

What was found

Quantum algorithms cannot be tested empirically at the scales that matter, because a classical computer can only simulate small instances, so the paper replaces testing with proof. Researchers write a problem as a Lean file stating the target correctness and cost theorems with the program, its cost bound and their proofs left as sorry placeholders, then launch independent agent teams with generic optimization prompts rather than problem-specific ideas. Teams share a wiki of best verified solutions and reusable lemmas and meet in scheduled forum conferences where unverified conjectures count for nothing. Because an agent can edit files in its own workspace, every submission is replayed in a clean sandbox by an external verifier using the Lean Comparator, which confirms that the theorem statements and every definition they depend on are unchanged and that the proof terms use only propext, Quot.sound and Classical.choice with no sorry and no added axiom. Reported reductions are 1.41 times for expected oracle rounds in parallel Grover search, more than 290 times in spacetime cost for fixed-point arcsine, and 10.9, 8.08 and 2.49 times on the three scientific simulations.

Novelty check

arXiv, 2026-11-09, abs:"quantum" AND abs:Lean AND abs:"formally verified" AND (abs:agents OR abs:"language model") returned 0 records besides this one, so the combination of a Lean quantum program library with agent search appears to be first here. This registry's nearest entries are 2026-10-15-llm-quantum-circuit-design, where a model searched for quantum circuits without formal verification, and the Lean formalization entries, which are all pure mathematics in Mathlib rather than quantum programs. The paper's own comparison is against named published baselines, Hanner, Roetteler and Svore 2018 for arithmetic and the Grover variants for parallel search, rather than against an internal baseline.

Caveats and known objections

Capped at claimed because there is no artifact a reader can open: the paper says the Lean library, the problem specifications and the verified solutions will be open sourced shortly, and until they are, the verification pipeline that the whole claim rests on cannot be rerun outside Google. The model or models behind the agents are not named. The speedups are resource-count reductions proved against formal cost models under stated fault-tolerant architectural assumptions, not measurements on hardware, and nothing here was run on a quantum computer. The paper also reports that agents found specification loopholes, which researchers closed by revising the specification, so the frozen-specification guarantee holds only against the specification a human wrote. Autonomy is search-scaffold: humans chose the problems, wrote the formal specifications and designed the verifier and workflow, and the paper itself says the work shifts rather than replaces human effort.

No independent check is recorded on this entry yet.

Reading the primary source closely enough to say whether it supports the claim counts as a check, and you are credited on the entry.

Or on GitHub: submit a check challenge the grade send a correction or send a pull request

Entry history (1 event)
  1. AddedEntered the registry graded Claimed and Search scaffold.

Entries are never deleted. A grade that does not hold up is downgraded on the record, with the reason beside it.

Graded claimed for verification and search scaffold for autonomy. What these mean.

Cite this entry

Plain text
whataifound.org. (2026). LLM agents write quantum programs checked against Lean specifications. whataifound.org: A Registry of AI Scientific and Mathematical Discoveries. https://whataifound.org/finding/2026-11-06-lean-verified-quantum-programs
BibTeX
@misc{whataifound-googledeepmind-2026-programs,
  title        = {LLM agents write quantum programs checked against Lean specifications},
  author       = {{whataifound.org}},
  year         = {2026},
  howpublished = {whataifound.org: A Registry of AI Scientific and Mathematical Discoveries},
  note         = {Result by Google DeepMind / Google Quantum AI. Verification: Claimed. Autonomy: Search scaffold.},
  url          = {https://whataifound.org/finding/2026-11-06-lean-verified-quantum-programs}
}

Related findings

← All computer science findings in the registry