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

AI summary

Overview

Research area: Quantum algorithms and quantum circuit compilation, specifically the automated design of reversible circuits that compute classical functions coherently, using large language models (LLMs) as search operators.

Technical level: Advanced. The paper assumes familiarity with Toffoli counts, ancilla management, reversible computation, and algorithmic primitives such as Reed–Solomon decoding and the extended Euclidean algorithm.

Scope: The paper introduces an evolutionary, evaluator-guided LLM framework that proposes and refines quantum circuit designs in a high-level Python interface, and applies it to eight compilation tasks spanning numerical computation, chemistry, optimization, quantum simulation, and number theory.

What This Paper Is About

Many quantum algorithms depend on compiling ordinary classical functions (decoders, arithmetic routines, numerical functions, QROM) into reversible circuits that run coherently on superposed inputs. Doing this well is hard: every branch of a computation must be paid for in gates, and intermediate values must be uncomputed rather than discarded, which bloats qubit counts. The paper asks whether an LLM, guided by a fast programmatic checker that verifies correctness and scores circuit cost, can discover genuinely new reversible architectures rather than merely tweaking existing ones.

Key Contributions

1. An evaluator-guided LLM search framework. A hand-written task specification and a blank program are given to an LLM, which proposes circuits through a high-level Python interface; an independent evaluator verifies correctness and scores each candidate. An initial ideation stage forces the model to propose several distinct "algorithm families," which are optimized in parallel, with strong candidates periodically shared across families to cross-pollinate ideas.

2. A cheap, exact-style correctness and cost evaluator. Because every allowed operation maps computational-basis states to computational-basis states (possibly with a phase), candidate circuits can be checked by tracking a bit string and a phase instead of 2^n amplitudes. Costs are summarized by the Toffoli count T, the peak qubit count Q, and their product, the TQ-cost, which serves as the single ranking objective.

3. Three reusable co-design principles extracted from the discovered circuits: conditional routing (replace controlled arithmetic with cheap controlled swaps around one shared arithmetic block), branch recovery during uncomputation (decode which branch was taken from register contents instead of storing a history stack), and exploitation of a failure budget (localize the resources needed only by rare inputs and omit them).

4. Seven of eight tasks improved on both resources, plus one new architecture. Discovered circuits use both fewer Toffolis and fewer qubits than the corresponding baselines in seven of eight tasks. In the eighth, prime-field modular inversion, the search produced a new reversible architecture that makes divsteps—previously impractical for reversible integer arithmetic—viable.

Main Findings

• Seven of eight tasks improve on both Toffoli and qubit counts. The reported TQ-cost gains G_TQ = (TQ)_baseline / (TQ)_ours are: Reed–Solomon DQI decoder 12; HHL rotation angle 32; Coulomb potential 9.9; fixed-point Gaussian 39; Fe2S2 alias–Select 4.1; nonabelian lattice-gauge simulation 7.7. The Hermitian DQI decoder has no prior reversible compilation, so its baseline is a naïve reversible implementation.

• Reed–Solomon DQI decoder: 12× TQ gain. For the instance where 70 syndrome values uniquely determine an error pattern of at most 35 errors, the baseline (5.1·10^6 Toffolis, 1,938 qubits) is replaced by (4.4·10^5, 1,837). The search replaced the synchronized extended-Euclidean solve—approximately 1.9 million Toffolis for the locator solve—with the Berlekamp–Massey recurrence, which costs approximately 140,000 Toffolis but naïvely accumulates polynomial history.

• A rescaling trick removes the polynomial history. Because the locator polynomial is only needed up to a nonzero multiplicative factor, both Berlekamp–Massey branches can be rewritten so one shared arithmetic path suffices: the replace branch produces τ − α^{-1}σ = −α^{-1}(σ − ατ), which differs from the unrescaled locator only by a nonzero scale factor and therefore has the same roots.

• Discrepancies are decoded, not stored. The old discrepancy can be recovered from constant coefficients of the updated locator registers via δ_old = σ_0 τ_0^{-1} δ_new, so the circuit never stores δ at all. Only the retain branch adds a stack entry; the worst case would need 35 entries (665 qubits), but under the DQI input distribution a second stack entry is required with probability 1.0 × 10^-4, so the circuit allocates one entry (19 qubits instead of 665).

• Prime-field modular inversion: a new reversible divsteps architecture. The circuit uses 4.0 million Toffolis and 935 qubits for the complete benchmark circuit. Divsteps replaces division with conditional additions, subtractions, and halvings, but reversing it requires knowing which of three updates was applied at each step.

• Branch decisions are recovered from the arithmetic state. Swaps are always cheaply identifiable because a swap sets f_v′ = 2g_v (exactly one trailing zero bit) while a nonswap gives f_v′ = 2f_v (divisible by four). About two thirds of decisions in a typical walk are recovered by simple tests; the remaining ambiguous nonswaps ("excursions") are decoded with a bit-extraction rule, b = bit_{j−1}(g_v′ q^{-1} mod 2^j), where j is the excursion depth and q is recovered by stripping trailing zeros from f_v′.

• A tunable cutoff trades Toffolis against qubits. With j_store = 5, only 12.4% of ambiguous decisions are written to the history stack. The average required stack size is 21 history qubits with a worst case of 263; the circuit reserves 60 and accepts overflow with probability 2.4 × 10^-6 per inversion, saving 203 history qubits.

• A stopping-time window exploits the failure budget. Although 590 divsteps suffice in the worst case, the circuit schedules 533 steps and tests for termination only from step 499 onward; this assumption fails with probability ∼10^-5.

• Conditional routing has a clean analytic benefit. For the worked example of choosing between x + cy and x + cz, routing swaps y and z, applies one uncontrolled multiply-add, and undoes the swap, reducing the schoolbook Toffoli count from 3n² + 17n − 2 to (3n² + 17n − 2)/2.

• Largest reported TQ gain is 39×, on fixed-point Gaussian computation, from (2.4·10^4, 362) to (1,583, 139).

Methodology in Plain English

The researchers defined each task by writing a specification of the required input–output behavior, with no hints about implementation, and gave it to an LLM along with an empty program. The LLM writes Python code that constructs a circuit using a restricted set of operations: reversible classical gates (X, CNOT, Toffoli, swap), diagonal sign gates (Z, CZ, CCZ, global sign flips), and destructive X-basis measurements, following the "kickmix" circuit model of Babbush et al.

An automated evaluator then does three things. It checks correctness by simulating the circuit on computational-basis inputs—tracking only the current bit string and phase, which is cheap—and by requiring every ancilla to return to zero. It permits a stated failure budget on a bounded fraction of inputs drawn from a specified distribution. And it counts Toffolis and peak qubits, ranking candidates by their product. Measurement-based uncomputation (Gidney's MBU) is available, so a temporary AND can be computed with one Toffoli and cleared with a measurement plus a Clifford correction instead of a second Toffoli.

The LLM receives this feedback and iterates. To avoid getting stuck in a local optimum, the search begins with an ideation stage that generates several different algorithmic approaches per problem, optimizes each independently in parallel, and periodically shares the best candidates between them.

Why This Matters

The results suggest that some apparent costs of quantum arithmetic are artifacts of existing reversible constructions rather than intrinsic to the algorithms, and that LLM-driven search with a trustworthy cheap evaluator can find representations and uncomputation strategies that human redesign has missed. The paper also proposes a practical criterion for when the approach applies: a sufficiently expressive task interface plus correctness and cost checks cheap enough to sustain many rounds of search.

Real-world applications implied by the tasks studied:

• Cryptography and number theory: efficient reversible modular inversion and modular arithmetic, subroutines in Shor-style and number-theoretic quantum algorithms.
• Quantum chemistry: cheaper compilation of the Coulomb potential and the Fe2S2 alias–Select primitive, both directly relevant to molecular energy estimation.
• Optimization: coherent Reed–Solomon and Hermitian decoders, the dominant cost in decoded quantum interferometry for optimal polynomial intersection.
• Quantum simulation and numerical computation: lower-cost fixed-point Gaussian evaluation, HHL rotation angles, and nonabelian lattice-gauge simulation.

Industry relevance: the work sits at the intersection of frontier LLM research and fault-tolerant quantum computing resource estimation, with authors affiliated with Anthropic, the Anthropic STEM Fellows Program, Harvard, and QuEra Computing. Reductions in TQ-cost translate directly into relaxed requirements on logical qubit counts and non-Clifford gate factories, which are the binding constraints in fault-tolerant hardware roadmaps.

Future Directions

• Replacing the TQ-cost objective with hardware-aware objectives. The authors note that the relative importance of qubit count, depth, routing, and measurements depends on hardware constraints, decoder performance, and error-correction architecture, and that the scoring function can be swapped for a hardware-appropriate combination—but choosing that objective remains a matter of judgment.

• Extending the framework beyond a fixed computational-basis interface. The current interface excludes optimizations that change the encoding itself, such as coset representations that encode each residue as a superposition of congruent integers to make modular addition cheaper at the cost of an exponentially small error.

• End-to-end fault-tolerant co-design. The authors propose an evaluator that propagates logical errors, resource demand, and hardware requirements across algorithm, logical circuit, error-correcting code, universal logic, magic-state supply, and physical architecture, so that layers usually optimized separately can be redesigned together.

• Broadening the class of tasks. The stated criterion—expressive task interface plus cheap, reliable evaluation—suggests the same search could be applied wherever those conditions hold, extending beyond the eight compilation tasks studied here.

Target Audience

Quantum computing researchers working on algorithms, compilation, and fault-tolerant resource estimation; practitioners of reversible arithmetic who need concrete constructions for decoders and modular inversion; and AI researchers interested in LLM-guided scientific discovery where a programmatic evaluator supplies the reward signal. The paper is best suited to readers comfortable with Toffoli-count accounting and reversible circuit design, since the central arguments concern ancilla lifetimes, uncomputation history, and branch recovery rather than broad conceptual background.

Authors’ 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.