quant-phOct 15, 2026
SaveDiscovering state-of-the-art quantum circuits with large language models
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 million Toffolis for the locator solve. (b) Berlekamp–Massey reduces this cost to approximately Toffolis but naïvely accumulates intermediate information (red). DIV forms , 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 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 in one representative walk. Dots mark ambiguous decisions. We use a cutoff , so all ambiguous decisions with are stored rather than decoded. The histogram shows the distribution of excursion depths over uniformly sampled walks: only 12.4% of ambiguous decisions reach . (b) Empirical stopping-time and history-size distributions. The discovered circuit assumes that every walk terminates between steps and ; this assumption fails with probability . It also allocates enough qubits to store at most 60 branch decisions, which is sufficient for all but a fraction of walks.
| Task | Baseline | Ours | |
|---|---|---|---|
| Reed–Solomon DQI decoder | |||
| Hermitian DQI decoder | † | — † | |
| HHL rotation angle | |||
| Coulomb potential | |||
| Fixed-point Gaussian | |||
| Fe 2 S 2 alias– Select |
Table 1: Toffoli–qubit results across the eight compilation tasks, comparing baselines against our discovered circuits (see for details); . Where a baseline contains free parameters, we choose them to minimize its -cost. HHL: Harrow–Hassidim–Lloyd.
Figure 1: Sample inputs and outputs for inversion in . (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 , so the evaluator rejects it. Seeing this feedback, the LLM adds MBU; the resulting circuit is valid with , , and a -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 -cost, which decreases toward the lower left. The ring marks the discovered circuit at and .
| Problem | Code field | Positions | Syndrome input | DQI/Prange | |
|---|---|---|---|---|---|
| OPI | |||||
| HOPI |
Table S1: Parameters of the two DQI decoding instances. The syndrome-input column gives the number of syndrome symbols and the bits per symbol; 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 . 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 .
| Reed–Solomon | Hermitian | |
| Positions | 4,095 nonzero field elements | 512 points on the curve |
| Symbol size | 12 bits | 6 bits |
| Check functions | ||
| Ordered by | degree | weighted degree |
| Syndromes | 70 | 123 |
| Locator | polynomial | function |
Table S2: Correspondence between the Reed–Solomon and Hermitian decoders.
| Construction | Inversion strategy | Toffolis | Qubits | |
|---|---|---|---|---|
| Schrottenloher [38] | Binary gcd and dialog trick [ 13 ] | 1,446 | ||
| Divstep circuit, SI II.1 | Divsteps with decoding | 935 | ||
| Luo et al. [40] | Packed Euclidean walk | 838 | ||
| Specialized Euclidean, SI II.2 | Specialized packed walk | 843 |
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 | |
| Stopping-time and integer-size limits | |
| Early-stopping and -register limits | |
| Branch-history storage | |
| Fused-square carry limit | |
| Union bound |
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 from their low ends and remainders 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 and growing coefficient 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 . The inverse shift restores ; 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 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 bits for each multiplication in the general HRS Horner polynomial-evaluation stage.
Figure S4: Frame structure of the 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 cluster core (thiolate substituents omitted); the dashed line marks the iron-site reflection . (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 and , 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 , , and 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 of the specialized representation, followed by the controlled addition. Rows encode , columns encode , and the highlighted cell and stripes show how and then determine the trace value.
More in this topic
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