Discovering state-of-the-art quantum circuits with large language models
Andi Gu, Alek H. Kemeny, Susanne F. Yelin, Mikhail D. Lukin
Large verified resource reductions across eight tasks plus a new reversible divstep architecture, in a timely intersection of LLM-driven discovery and fault-tolerant resource estimation; limited by lack of search ablations and proprietary-model reproducibility.
Abstract
Significant efforts are currently being directed toward the implementation of large-scale quantum information processors, but realizing useful quantum advantage also requires the development of efficient quantum algorithms. While for many practical problems the dominant resource costs are associated with a small set of computational primitives, optimizing them in the quantum setting presents unique challenges, including a reversibility constraint absent from ordinary classical computation. Here we introduce an evolutionary framework in which large language models (LLMs) propose circuit designs and an independent evaluator verifies and scores them. We apply this framework to tasks spanning numerical computation, chemistry, optimization, quantum simulation, and number theory. In seven of the eight tasks, the discovered circuits significantly reduce both Toffoli and qubit counts relative to the state of the art. In the eighth, the search discovers a new reversible architecture for prime-field modular inversion. By handling reversibility differently, the architecture makes divsteps -- a classical algorithm previously impractical for reversible integer arithmetic -- viable and substantially improves the Toffoli-qubit trade-off for modular inversion. These results open the door for evaluator-guided LLM co-design of new algorithmic structures for quantum computation.
AI Impact Assessments
(1 model)Paper type: Empirical/tool-and-method paper with new algorithmic constructions in quantum compilation.
Core Contribution
The paper presents an evaluator-guided evolutionary search in which an LLM (OpenEvolve with MAP-Elites, plus an ideation stage producing separate "algorithm families") writes Python circuit-generating programs. A programmatic evaluator checks them. The checker relies on the "kickmix" model, in which classical reversible gates, diagonal phase gates and X-measurements can be simulated on basis states, so correctness is tested exactly on sampled inputs. Candidates are scored by Toffoli count × peak qubits (TQ-cost).
Across eight tasks, the discovered circuits beat published baselines in the TQ-cost metric by roughly 4× to 39×. The tasks are:
The paper distills three reusable design principles:
1. Conditional routing instead of conditional arithmetic.
2. Branch-history recovery from the evolving state instead of a stored history stack.
3. Spending a failure budget to remove resources devoted to rare inputs.
The most intellectually significant result is the reversible divstep architecture for 256-bit modular inversion. It rests on a decoding rule with a proved invariant (Appendix A), which the paper says the LLM identified and proved. It reaches 4.0M Toffolis and 935 qubits for a full elliptic-curve point adder. This is competitive in qubits with the prior state of the art and a different point on the frontier. The Berlekamp–Massey reversible decoder, with its rescaling trick to avoid a polynomial history stack, is also a clean, human-comprehensible algorithmic insight.
Methodological Rigor
The evaluation design is strong for this problem. Correctness checks the full final state (outputs, ancilla cleanliness, exact phase) over sampled basis trajectories. The paper gives a fidelity bound from sampled failure rate (Eqs. 17–21). Failure budgets are quantified empirically. Examples are 10^8-scale sampling for walk statistics and 100,000 full-circuit tests with a handful of failures. Union bounds are tabulated (Table S4).
Weaknesses:
Potential Impact
The paper has high relevance for fault-tolerant resource estimation. Reductions of 10× in Toffoli count at similar qubit counts for DQI decoders matter for assessing verifiable quantum advantage. Elliptic-curve modular inversion directly informs cryptanalysis timelines. Efficient function-evaluation circuits (Gaussian, Coulomb, arcsin) are reusable primitives in chemistry and simulation. Methodologically, this is a convincing demonstration that LLM-driven search can produce genuinely new algorithmic structure beyond local rewrites. That is a meaningful extension of FunSearch and AlphaEvolve to quantum circuits. The framing as "co-design" and the clear exposition of principles make it likely to be cited by both the quantum-algorithms and AI-for-science communities. Applicability is limited to classical-function-style (basis-state-simulable) circuits. The authors acknowledge that coset representations and non-classical amplitudes are out of scope.
Timeliness
Timing is very good. Resource estimates for quantum advantage and RSA/ECC are a hot topic, as are agentic LLM discovery systems. Their combination, with verifiable evaluators, fits current momentum.
Strengths
Limitations
Overall
This is a high-impact applied-methods paper at the intersection of quantum algorithms and AI-driven discovery. It combines strong concrete results with a methodological template other groups will likely copy. Its main weaknesses are weak attribution and ablations for the search procedure and limited reproducibility.
Generated Oct 16, 2026
Comparison History (0)
Large verified resource reductions across eight tasks plus a new reversible divstep architecture, in a timely intersection of LLM-driven discovery and fault-tolerant resource estimation; limited by lack of search ablations and proprietary-model reproducibility.