Discovering state-of-the-art quantum circuits with large language models

Andi Gu; Alek H. Kemeny; Susanne F. Yelin; Mikhail D. Lukin

quant-phOct 15, 2026

Discovering state-of-the-art quantum circuits with large language models

Authors: Andi Gu, Alek H. Kemeny, Susanne F. Yelin, Mikhail D. Lukin

Organizations: Harvard Quantum Initiative for Science and Engineering, Cambridge, MA 02138, USA · Department of Physics, Harvard University, Cambridge, MA 02138, USA · Anthropic STEM Fellows Program · Anthropic ·

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.

Figures & tables

Figure 1: Overview of the circuit-discovery framework. (a) A hand-written task specification defines the circuit design task (for example, Reed–Solomon decoding) and is given to an LLM. The LLM proposes architecturally different approaches ( algorithm families ; here extended Euclidean, Berlekamp–Massey, and Peterson–Gorenstein–Zierler (PGZ) decoders), which are then developed and optimized in parallel. Strong candidates are periodically shared between families to allow for cross-pollination of useful ideas. (b) Conditional routing reduces the cost of coherent control flow: for instance, two controlled multiply-adds (MADDs) become inexpensive controlled swaps and one shared arithmetic block. (c) Branch decisions that a naïve reversible computation stores during the forward pass (red) can instead be decoded from the current state during uncomputation. (d) When an application permits bounded error, allowing rare failures on atypical, costly inputs reduces resource requirements.

Figure 2: Reversible Reed–Solomon decoding. (a) The synchronized extended-Euclidean construction of Khattar et al. [13] requires approximately

1.9

million Toffolis for the locator solve. (b) Berlekamp–Massey reduces this cost to approximately

140{,}000

Toffolis but naïvely accumulates intermediate information (red). DIV forms

\alpha=\Delta/\delta

, MADD applies the multiply-add, and the flag marks the replace case. (c) Conditional routing preserves this arithmetic advantage while avoiding most history storage. Block widths are proportional to Toffoli count. (d) Locator construction as convolution with the syndrome sequence. The discrepancy

\Delta

is the convolution at the next syndrome; a nonzero value requires updating the locator.

Figure 3: Making divsteps reversible with minimal overhead. (a) Excursion depth

j

in one representative walk. Dots mark ambiguous decisions. We use a cutoff

j_{\mathrm{store}}=5

, so all ambiguous decisions with

j\geq 5

are stored rather than decoded. The histogram shows the distribution of excursion depths over uniformly sampled walks: only 12.4% of ambiguous decisions reach

j\geq 5

. (b) Empirical stopping-time and history-size distributions. The discovered circuit assumes that every walk terminates between steps

499

and

533

; this assumption fails with probability

\sim 10^{-5}

. It also allocates enough qubits to store at most 60 branch decisions, which is sufficient for all but a

2.4\times 10^{-6}

fraction of walks.

Task	Baseline $\boldsymbol{(T,Q)}$	Ours $\boldsymbol{(T,Q)}$	$\boldsymbol{G_{TQ}}$
Reed–Solomon DQI decoder	$(5.1{\cdot}10^{6},\,1{,}938)$	$(4.4{\cdot}10^{5},\,1{,}837)$	$12$
Hermitian DQI decoder	$(1.0{\cdot}10^{8},\,1.9{\cdot}10^{5})$ †	$(9.3{\cdot}10^{5},\,2{,}395)$	— †
HHL rotation angle	$(1.6{\cdot}10^{4},\,300)$	$(1{,}348,\,115)$	$32$
Coulomb potential	$(6{,}355,\,252)$	$(1{,}140,\,142)$	$9.9$
Fixed-point Gaussian	$(2.4{\cdot}10^{4},\,362)$	$(1{,}583,\,139)$	$39$
Fe 2 S 2 alias– Select	$(5.5{\cdot}10^{4},\,139)$	$(1.5{\cdot}10^{4},\,126)$	$4.1$

Table 1: Toffoli–qubit results across the eight compilation tasks, comparing baselines against our discovered circuits (see for details);

G_{TQ}=(TQ)_{\mathrm{baseline}}/(TQ)_{\mathrm{ours}}

. Where a baseline contains free parameters, we choose them to minimize its

TQ

-cost. HHL: Harrow–Hassidim–Lloyd.

Panel of Figure 1 — Figure 1: Sample inputs and outputs for inversion in $\mathbb{F}_{2^{4}}$ . (a) During ideation, the LLM is given the complete task specification but no prior implementation and returns distinct candidate architectures. (b) During evolution, the input additionally contains a selected parent program, its evaluator feedback, and limited archive context; the LLM returns a proposed rewrite. (c) One such rewrite computes the inverse with five nonlinear products but fails to return an ancilla to $\ket{0}$ , so the evaluator rejects it. Seeing this feedback, the LLM adds MBU; the resulting circuit is valid with $T=5$ , $Q=10$ , and a $TQ$ -cost of 50.

Figure 2: Search lineage for the Gaussian circuit in the resource plane. Each marker is a distinct valid circuit, colored by the iteration in which it was discovered; arrows point from each parent to its mutated child. Dashed curves are contours of constant

TQ

-cost, which decreases toward the lower left. The ring marks the discovered circuit at

T=1{,}583

and

Q=139

Problem	Code field	Positions	Syndrome input	$\boldsymbol{\ell}$	DQI/Prange
OPI	$\mathbb{F}_{2^{12}}$	$4{,}095$	$70\times 12$	$35$	$0.5763/0.5009$
HOPI	$\mathbb{F}_{64}$	$512$	$123\times 6$	$47$	$0.7145/0.5726$

Table S1: Parameters of the two DQI decoding instances. The syndrome-input column gives the number of syndrome symbols and the bits per symbol;

\ell

is the maximum decoded error weight. The last column compares expected satisfied fractions for ideal DQI and a single trial of Prange’s information-set decoding [ 42 ] , which is the best known efficient classical algorithm for these instances.

Figure S1: The Reed–Solomon decoder. (a) Measured forward Toffoli cost per step: one cycle of the 222-cycle synchronized EEA baseline of Khattar et al. [13] , or one round of our 70-round BM decoder. (b) Locator degree (top) and number of stored discrepancies (bottom) by round, across 20,000 samples drawn from the DQI input distribution, with one sample highlighted; the dashed line is the worst-case degree bound $\min(r,35)$ . The right-hand panels show the final locator-degree distribution and the distribution of maximum discrepancy-stack depth. Inputs in the hatched region need more than the one allocated stack entry and may produce a wrong sign; this occurs with probability $1.0\times 10^{-4}$ .

	Reed–Solomon	Hermitian
Positions	4,095 nonzero field elements	512 points $(x,y)$ on the curve
Symbol size	12 bits	6 bits
Check functions	$z^{i}$	$x^{a}y^{b}$
Ordered by	degree $i$	weighted degree $8a+9b$
Syndromes	70	123
Locator	polynomial $\sigma(z)$	function $\sigma(x,y)$

Table S2: Correspondence between the Reed–Solomon and Hermitian decoders.

Construction	Inversion strategy	Toffolis	Qubits	$\boldsymbol{TQ}$
Schrottenloher [38]	Binary gcd and dialog trick [ 13 ]	$1.9{\cdot}10^{6}$	1,446	$2.7{\cdot}10^{9}$
Divstep circuit, SI II.1	Divsteps with decoding	$\boldsymbol{4.0{\cdot}10^{6}}$	935	$\boldsymbol{3.7{\cdot}10^{9}}$
Luo et al. [40]	Packed Euclidean walk	$7.0{\cdot}10^{7}$	838	$5.8{\cdot}10^{10}$
Specialized Euclidean, SI II.2	Specialized packed walk	$\boldsymbol{2.1{\cdot}10^{7}}$	843	$\boldsymbol{1.7{\cdot}10^{10}}$

Table S3: Resource comparison for point addition. All circuits use the same affine-coordinate input and output; counts include reversible cleanup but exclude application-specific storage or lookup used to supply the classical addend.

Failure source	Probability (upper bound)
Multiplier carry and comparison limits	$7.07\times 10^{-5}$
Stopping-time and integer-size limits	$7.56\times 10^{-5}$
Early-stopping and $z$ -register limits	$6.18\times 10^{-6}$
Branch-history storage	$6.8\times 10^{-6}$
Fused-square carry limit	$6\times 10^{-7}$
Union bound	$1.599\times 10^{-4}$

Table S4: Contributions to the union bound on the point-addition failure probability. Each entry is per point addition, which contains two inversions. Probabilities for the walk limits are estimated from 200 million independent random 256-bit walks.

Figure S2: Specializing the Euclidean schedule and its contribution to the Toffoli reduction. (a) Two 259-qubit registers store coefficients

t,t^{\prime}

from their low ends and remainders

r,r^{\prime}

from their high ends. Four counters mark the boundaries of these values as the coefficients grow and the remainders shrink. (b) Each thin curve traces the moving boundary between the shrinking remainder

r

and growing coefficient

t

for one sampled walk. Light shading shows the fitted windows retained by the discovered circuit, dashed curves show the exact worst-case bounds, and dark shading marks the test-free positions, processed without first testing the counters. The hatched region is removed by the schedule cut from 1,616 to 1,432 steps. (c) Executed Toffolis per step. The gray profile is the baseline schedule; the discovered circuit’s profile splits into the fixed overhead of a step, arithmetic at test-free positions, and arithmetic at tested positions. (d) Cumulative ablation from 70 million to 21 million Toffolis. Blue changes are exact, whereas brown changes count against the failure budget.

Figure S3: Co-designed HHL rotation-angle circuit. (a) Complete reversible dataflow: a dyadic lookup selects a local quadratic and a cyclic shift, the input is mapped into a shared local coordinate, and the quadratic is accumulated directly into

k

. The inverse shift restores

X

; measurement and a shared phase correction clear the consumed coefficients without reversing the lookup. (b) Dyadic leaves and the shared coordinate. Power-of-two-aligned leaves are selected by the leading input bits. Shifting each leaf’s varying bits

\delta

to a common scale allows leaves of different widths to feed one 15-bit polynomial-evaluation stage without subtraction or arithmetic rescaling. (c) Arithmetic consequence: the circuit multiplies the 15-bit coordinate by a 16-bit slope, compared with

44\times 44

bits for each multiplication in the general HRS Horner polynomial-evaluation stage.

Figure S4: Frame structure of the $\mathrm{Fe_{2}S_{2}}$ alias table. (a) The preprocessing places Pauli operators related by fixed Clifford frames into contiguous blocks. This groups the 41,052 table rows into 3,221 blocks that Select handles as units. Band height gives the number of terms in each block, and the labels give the frames used to generate them. Inset: the $\mathrm{Fe_{2}S_{2}}$ cluster core (thiolate substituents omitted); the dashed line marks the iron-site reflection $\sigma_{\mathrm{Fe}}$ . (b) One block of 32 Pauli operators generated from a representative operator using five frames. Each row of the left matrix specifies which frames are applied; a dark cell means that the frame named below its column is included. The center shows the resulting Pauli operator on the 40 system qubits, and the bar on the right gives its coefficient magnitude. The spin frames $\sigma_{\alpha\beta}$ and $\sigma_{XY}$ , shown in the first two columns, preserve coefficient magnitudes and therefore produce equal-weight groups of four. The other three frames need not preserve the coefficients.

Figure S5: Loop geometry and trace accumulation in the nonabelian lattice-gauge circuit. (a) The blue, orange, and green paths are cyclic or inverted representatives of

P_{ij}

R_{ij}

, and

R_{ji}

whose trace values equal those of Equation 76 by Equation 86 ; the dark segment is shared after these symmetry choices. (b) The baseline lookup, modular addition, and unlookup for a completed loop product. (c) The trace readout, drawn as a truth table over the coordinates

(\widetilde{P},M,\upsilon,Q,R)

of the specialized representation, followed by the controlled addition. Rows encode

(M,\upsilon)

, columns encode

(Q,R)

, and the highlighted cell and stripes show how

(M,\upsilon,Q,R)

and then

\widetilde{P}

determine the trace value.

Large Language Model-Guided Optimization

Large Language Model-Guided Optimization uses language models to propose, steer, and refine solutions to hard search and design problems.

See all 574 papers

Sep 4, 2026

LLM-Driven Algorithm Design for Quantum Circuit Synthesis based on Binary Decision Diagrams

Quantum circuits are central to implementing quantum algorithms on quantum devices, where quantum gates must be reversible. Many quantum algorithms rely on Boolean functions, which must therefore be implemented reversibly within quantum circuits. Reversible circuit synthesis provides a way to translate such Boolean functions into reversible circuits. Binary decision diagrams (BDDs) offer a scalable approach to this task, but the resulting BDDs and circuits depend heavily on variable ordering. Existing ordering heuristics commonly minimize BDD size because it is closely tied to the circuit size. However, BDD size is an imperfect proxy for the quantum cost of the synthesized circuit (QCC). We propose QuantumEvo, an evolutionary framework that uses an LLM as a heuristic generator for QCC-aware BDD variable ordering. Instead of predicting orderings directly, QuantumEvo searches over ordering heuristics initialized from multiple heuristic families. Candidate heuristics directly manipulate variable orderings using standard BDD operations and are selected by downstream QCC. The discovered heuristic, HGA-QE, modifies the sifting step inside a genetic algorithm so that the procedure is better aligned with QCC. Across the benchmark set, HGA-QE achieves a 70.9% tie-or-win rate against the per-function best baseline and is strictly best on 13.5% of the functions. The results demonstrate broadly competitive QCC performance, with HGA-QE showing a clearer relative advantage in strict wins on the two benchmark suites drawn from sources different from the data used for heuristic discovery.

Yoonju Sim, Federico Berto, Chuanbo Hua +2

Department of Industrial and Systems Engineering, KAIST, Daejeon, 34141, Republic of Korea · Radical Numerics, California, USA · Omelet, Inc., Daejeon, 34051, Republic of Korea

Quantum Circuit Compilation Automated Algorithm Discovery

Ask PDF

Aug 4, 2026

Separating quantum circuits from classical LLMs

Modern large language models - transformers and diffusion language models - are built around two canonical algorithmic tasks: prediction and generation. We prove unconditional separations between low-depth quantum computation and the corresponding bounded-resource classical language-model architectures in both regimes. Concretely, we exhibit the following: 1. Distributional separation. We give a distribution that is sampleable by

\textsf{QNC}^0

circuits (i.e., a family of constant-depth quantum circuits consisting of bounded fan-in gates) that no constant-round diffusion language model (

\textsf{DLM}

) with shallow scheduling and denoising can sample within constant distance, even when allowed sublinear chain-of-thought and output-token revision/remasking events, the very features modern

\textsf{DLM}

s rely on. 2. Functional separation. We exhibit a function computable in

\land \circ \textsf{QNC}^0[\log\log n]

(i.e., a family of O

(\log\log n)

-depth

\textsf{QNC}^0

circuits, where

n

is the input length, followed by a single classical

\mathsf{AND}

gate) such that any constant-depth decoder-only transformer computing the function must be large: it would have to have width

n^{Ω(1)}

. Together, our work initiates the study of quantum advantage in the era of large language models.

Srinivasan Arunachalam, Arkopal Dutt, Hari Krovi +1

IBM Research

Decoder-Only Language Models Diffusion Language Models

Ask PDF

Jun 11, 2026

An LLM System for Autonomous Variational Quantum Circuit Design

The design of high performing quantum circuits remains largely dependent on human expertise. We introduce an autonomous agentic framework that employs large language models (LLMs) to conduct iterative quantum circuit designs under explicit design constraints. Our system integrates seven components: Exploration, Generation, Discussion, Validation, Storage, Evaluation, and Review. These components form a closed-loop workflow that combines web-based knowledge acquisition, literature-grounded critique, executable code generation, and experimental feedback. We evaluate the framework on two tasks: quantum feature map construction for quantum machine learning and ansatz generation for variational quantum eigensolver applications in quantum chemistry. In image classification benchmarks, the best generated feature map outperforms representative quantum feature maps and, when scaled to larger qubit counts, surpasses the classical radial basis function kernel. In molecular ground state estimation across seven molecules, the generated ansatz attains competitive accuracy with widely used chemically inspired and hardware-efficient constructions while satisfying the imposed scaling constraints. These results establish LLM driven agentic system as a viable paradigm for automated quantum circuit design and illustrate how AI systems can participate in iterative scientific optimization workflows across scientific domains.

Kenya Sakka, Wataru Mizukami, Kosuke Mitarai

Center for Quantum Information and Quantum Biology, The University of Osaka, 1-2 Machikaneyama, Toyonaka 560-0043, Japan · Graduate School of Engineering Science, The University of Osaka 1-3 Machikaneyama, Toyonaka, Osaka 560-8531, Japan

Quantum Chemistry Quantum Kernel Methods Variational Quantum Circuits Large Language Model-Guided Scientific Discovery

Ask PDF

Abstract

Large Language Model-Guided Optimization

Explore similar work

LLM-Driven Algorithm Design for Quantum Circuit Synthesis based on Binary Decision Diagrams

Separating quantum circuits from classical LLMs

An LLM System for Autonomous Variational Quantum Circuit Design