PaperlayerView exact revision on arXiv

Source-linked AI summary

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

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

arXiv:2610.22367v1quant-phcs.AI

TL;DR

Reversible quantum circuits must meet coherence constraints that can complicate the use of classical computational primitives. This paper uses evaluator-guided LLM search to discover circuits, reducing both Toffoli and qubit counts in seven of eight tasks and finding a new reversible architecture for modular inversion.

  • Problem

    Compiling classical functions into quantum circuits requires reversible, coherent implementations, and existing optimizers often restrict searches to rewrites of predefined designs.

    Source: Circuit model and validity · p. 9

  • Method

    The framework uses evaluator-guided LLM search to go beyond refining a fixed circuit and discover reversible algorithms and representations.

    Source: DISCUSSION AND OUTLOOK · p. 8

  • Results

    In seven of eight tasks, discovered circuits use fewer Toffolis and fewer qubits than their corresponding baselines.

    Source: DISCUSSION AND OUTLOOK · p. 6

  • Takeaways & Limitations

    Jointly choosing the algorithm, representation, and uncomputation can recover classical algorithmic efficiency under quantum computation’s constraints.

    Source: DISCUSSION AND OUTLOOK · p. 7

    The search is bounded by the chosen task interface and resource objective, whose hardware-specific priorities require application judgment.

    Source: DISCUSSION AND OUTLOOK · p. 7

Abstract

from arXiv · show

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.

DESIGN PRINCIPLES

The design principles reduce coherent-circuit overhead by routing data through shared arithmetic, recovering branch information during uncomputation, and localizing resources for rare inputs. Together, these choices let circuits exploit classical algorithmic efficiency while meeting reversibility constraints.

DESIGN PRINCIPLES

  • Conditional routing replaces separately controlled branch arithmetic with cheap swaps around one shared, unconditional expensive operation.For the schoolbook multiply-add example, it halves the Toffoli count relative to the naïve implementation.Source: DESIGN PRINCIPLES · p. 3
  • Branch decisions can be recovered during uncomputation from distinguishable register patterns, avoiding an explicit history stack.The decoder may rely on relations among registers in states reachable from the prescribed initialization, even when a single-register update is ambiguous.Source: DESIGN PRINCIPLES · p. 3
  • Localizing circuitry for rare inputs lets a circuit omit their extra iterations, stack entries, or arithmetic lanes while confining failure to those low-probability cases.A rare supported input can otherwise determine the Toffoli count or peak qubit count of the whole circuit.Source: DESIGN PRINCIPLES · p. 3

REVERSIBLE SYNDROME DECODING FOR DQI

The search replaces a synchronized Euclidean locator solve with Berlekamp–Massey, retaining its arithmetic savings while avoiding most history storage. It achieves this by exploiting the locator’s scale freedom and recovering overwritten discrepancies from register values.

REVERSIBLE SYNDROME DECODING FOR DQI

  • Approximately 1.9 million to 140,000 Toffolis reduces the locator-solve cost with Berlekamp–Massey, while conditional routing avoids most history storage.The figure compares the synchronized Euclidean construction with the BM-based circuit; its block widths are proportional to Toffoli count.Source: REVERSIBLE SYNDROME DECODING FOR DQI · p. 4
  • The studied Reed–Solomon instance uses 70 syndrome values to determine an error pattern containing at most 35 errors.DQI uses Reed–Solomon decoding coherently as a subroutine in optimization applications.Source: REVERSIBLE SYNDROME DECODING FOR DQI · pp. 3–4
  • The locator is needed only up to a nonzero scale because rescaling preserves its roots, allowing both update branches to use one shared arithmetic path.This removes the need to store the displaced polynomial template.Source: REVERSIBLE SYNDROME DECODING FOR DQI · p. 4
  • The circuit recovers the overwritten discrepancy from the updated locator’s constant coefficients, so replace updates add no history-stack entry.Retain updates still store the current discrepancy; under the DQI input distribution, the circuit allocates one 19-qubit entry rather than 665 qubits and permits failure when a second entry is needed, with probability 1.0 × 10^-4.Source: REVERSIBLE SYNDROME DECODING FOR DQI · p. 4
  • These transformations make the arithmetically efficient Berlekamp–Massey algorithm suitable for reversible computation.A naïve reversible implementation would accumulate a history of whole polynomials after replace updates overwrite the prior template and discrepancy.Source: REVERSIBLE SYNDROME DECODING FOR DQI · p. 4

REVERSIBLE MODULAR INVERSION

The modular-inversion circuit makes divsteps reversible by recovering branch decisions from the evolving arithmetic state and bounding resources for rare inputs. It combines these choices to reduce history storage and support a complete benchmark circuit.

REVERSIBLE MODULAR INVERSION

  • Divsteps replaces division with conditional additions, subtractions, and halving to reduce the input pair while preserving its greatest common divisor.Auxiliary integers track the input’s contribution in a scaled form, keeping coefficient updates free of division.Source: REVERSIBLE MODULAR INVERSION · pp. 4–5
  • The circuit recovers branch decisions from updated arithmetic registers instead of storing every update choice in a history stack.Distinctive register patterns recover some choices directly; the LLM-derived invariant supports recovery of ambiguous choices during uncomputation.Source: REVERSIBLE MODULAR INVERSION · pp. 5–6
  • A tunable depth cutoff trades Toffoli cost against qubit use by decoding shallow ambiguous decisions and storing deeper ones.The decoding circuit for small depths is compiled from truth tables; the cutoff determines which decisions go to the history stack.Source: REVERSIBLE MODULAR INVERSION · p. 6
  • With jstore = 5, 12.4% of ambiguous decisions go to the stack; allocating 60 history qubits saves 203 qubits versus the 263-qubit worst case, with overflow probability 2.4 × 10^-6 per inversion.The circuit schedules 533 steps and checks for termination only from step 499 onward, allowing failure for inputs terminating outside that window.Source: REVERSIBLE MODULAR INVERSION · p. 6
  • 4.0 million Toffolis and 935 qubits are used by the complete benchmark circuit built on the discovered modular inversion.The circuit limits its history stack to 60 qubits and schedules 533 steps, allowing failure on rare inputs outside the supported resource limits.Source: REVERSIBLE MODULAR INVERSION · p. 6

DISCUSSION AND OUTLOOK

Across seven of eight tasks, discovered circuits use fewer Toffolis and qubits than their baselines. The discussion connects these gains to reversible redesign, identifies boundaries set by task choices, and points toward broader evaluator-guided co-design.

DISCUSSION AND OUTLOOK

  • The modular-inversion circuit assumes termination between steps 499 and 533 and storage for at most 60 branch decisions, with respective failure probabilities of ∼10^-5 and 2.4 × 10^-6.Only 12.4% of ambiguous decisions reach the j ≥ 5 storage cutoff.Source: Figure 3 · p. 7
  • In seven of eight tasks, discovered circuits use fewer Toffolis and qubits than their corresponding baselines.Table I summarizes the Toffoli–qubit comparisons across all eight tasks.Source: DISCUSSION AND OUTLOOK · p. 6, Table I · p. 7
  • Jointly redesigning algorithms, representations, and uncomputation can recover classical efficiency under reversibility constraints.The authors suggest some apparent quantum-arithmetic costs reflect limits of existing reversible constructions rather than the algorithms themselves.Source: DISCUSSION AND OUTLOOK · pp. 6–7
  • The search is bounded by its resource objective and fixed computational-basis interface, excluding advantages that require changing the encoding.Resource priorities depend on hardware and application; coset representations are one example of an encoding outside this framework.Source: DISCUSSION AND OUTLOOK · pp. 7–8
  • Within those boundaries, evaluator-guided LLM search can uncover reversible algorithms and representations beyond refinements of a fixed circuit.The authors propose extending the approach where task interfaces are expressive and correctness and resource costs are cheap enough to evaluate across many search rounds.Source: DISCUSSION AND OUTLOOK · p. 8
  • An evaluator that tracks costs across algorithms, error-correcting codes, magic states, and hardware could support joint fault-tolerant co-design.The authors present this as a potential opportunity rather than a demonstrated result.Source: DISCUSSION AND OUTLOOK · p. 8

METHODS

The methods use an LLM to propose task-specific circuit redesigns within evolutionary search, with correctness tests and a combined resource objective guiding optimization.

METHODS

  • A classical function is embedded as a reversible map that preserves |x⟩ and XORs f(x) into the output register.The kickmix model adds measurement-based uncomputation and diagonal sign gates while remaining efficiently classically simulable for evaluator testing.Source: METHODS · p. 9
  • The TQ-cost multiplies Toffoli count by peak qubit count to compare logical work and processor footprint together.Toffoli count tracks much of the non-Clifford work, while peak qubits approximate the required logical processor footprint.Source: METHODS · p. 9
  • An LLM proposes coordinated task-specific redesigns in evolutionary search, optimizing candidates against correctness tests and TQ-cost.The tests and cost together define a constrained optimization problem over circuit-generating programs.Source: METHODS · p. 9

Circuit model and validity

The circuit model specifies reversible basis-state actions with clean ancillas and permits reversible gates, diagonal signs, and destructive X-basis measurements. Its measurement-based uncomputation can clear temporary work while preserving coherent correctness under stated trajectory constraints.

Circuit model and validity

  • A compilation task specifies a basis-state permutation and optional Boolean phase, while every ancilla must return to |0⟩.For numerical approximations, the output may have an error bound, but interface preservation, phase correctness, and ancilla uncomputation remain exact.Source: Circuit model and validity · p. 9
  • Kickmix circuits allow reversible classical gates, diagonal sign gates, and destructive X-basis measurements, with failure permitted only on a bounded fraction of inputs from a stated distribution.The allowed gates include X, CNOT, Toffoli, swap, Z, CZ, CCZ, and global sign flips.Source: Circuit model and validity · p. 9
  • Measurement-based uncomputation clears a temporary AND using one Toffoli instead of the two needed to compute and uncompute it conventionally.A random X-basis measurement outcome is handled by a cheap phase correction, releasing the ancilla in |0⟩.Source: Circuit model and validity · p. 9
  • In the simulator, an X-basis measurement gives a uniform random outcome and updates the phase record; a conditioned diagonal correction cancels the resulting sign.The measured function is retained through its syndrome, and the retained state remains coherent.Source: Circuit model and validity · pp. 9–10
  • Exact coherent correctness requires every measurement record to induce the same basis permutation and factor from the logical output.Measurement outcomes may control diagonal corrections, but not basis-changing gates, which could correlate the output with the measurement environment.Source: Circuit model and validity · p. 10

Validation and statistical guarantees

The evaluator checks complete basis-trajectory states, including output, preserved inputs, clean ancillas, and phase. Passing trajectories support coherent correctness, while sampling provides statistical guarantees for large input domains.

Validation and statistical guarantees

  • Each trajectory test checks the target output, unchanged required inputs, zeroed ancillas, and exact phase, not merely the classical output bits.Dirty ancillas can retain input-dependent information, and incorrect signs can alter later interference.Source: Validation and statistical guarantees · p. 10
  • If every input-record pair passes, the measurement record factors from the logical output and linearity extends correctness to coherent inputs.For large input domains, the evaluator samples trajectories rather than checking them all.Source: Validation and statistical guarantees · p. 10
  • The defective set B consists of input-record pairs where the candidate trajectory differs from the target, and ε is its probability under D and uniform records.The evaluator samples inputs from D and measurement outcomes uniformly to estimate this trajectory error.Source: Validation and statistical guarantees · p. 10
  • For trajectory errors of probability ε, the stated bounds are fidelity at least (1 − 2ε)^2 and total-variation change at most 2√ε.The failure probability is measured over inputs drawn from D and uniformly sampled measurement records.Source: Validation and statistical guarantees · p. 10

Cost model and scoring

The search scores circuits using TQ-cost, the product of Toffoli count and peak qubit count. This equal weighting is a simplifying choice, and the framework can optimize other computable objectives.

Cost model and scoring

  • TQ-cost multiplies Toffoli count T by peak logical-qubit count Q.T counts Toffoli and CCZ gates equally; Q is the largest number of logical qubits allocated at once.Source: Cost model and scoring · p. 11
  • The model weights time and space equally for simplicity, although hardware and application can make their relative importance differ.When qubits are scarce, a qubit-weighted cost may be more appropriate; Toffoli count, Toffoli depth, or active volume may also better represent resources in some settings.Source: Cost model and scoring · p. 11
  • The search accepts any computable objective, and modular inversion illustrates selecting a lower-qubit circuit by weighting qubit count more heavily.That search yields a family along a Toffoli–qubit frontier.Source: Cost model and scoring · p. 11

Evolutionary search

The evolutionary search represents circuits as structured Python programs, which lets the LLM revise algorithmic organization as well as operations. Independent candidate families preserve different approaches, while evaluator feedback and resource-based selection guide their development.

Evolutionary search

  • Python functions, loops, and named registers let the LLM make coordinated changes to arithmetic subroutines and their composition.Revisions can alter when intermediate values are computed, retained, and uncomputed.Source: Evolutionary search · p. 11
  • The LLM proposes architectures from a task specification, and later sessions revise parent programs using evaluator feedback and limited archive context.The evaluator rejects invalid circuits and scores valid ones by TQ-cost; sessions do not share a continuously growing conversation.Source: Evolutionary search · p. 11
  • Separate candidate families develop distinct architectures before periodically sharing leading programs so successful ideas can combine.Each family begins from an architecture proposed during ideation.Source: Evolutionary search · p. 11
  • MAP-Elites retains low-TQ-cost circuits in resource-plane cells, preserving different Toffoli–qubit trade-offs; progress need not improve monotonically in either resource.The reported search result is the lowest TQ-cost reached across all families.Source: Evolutionary search · p. 11

EXTENDED DATA

The extended data illustrates the search process and reports benchmark-resource fields across eight tasks. It also documents a feedback-driven repair example and notes limits on interpreting modular-inversion comparisons.

EXTENDED DATA

  • A finite-field inversion rewrite with five nonlinear products was rejected for leaving an ancilla uncleared; adding MBU produced a valid circuit with T = 5, Q = 10, and TQ-cost 50.The example depicts a feedback-and-repair cycle.Source: Figure 1 · p. 15
  • The Gaussian search-lineage figure marks the discovered circuit at T = 1,583 and Q = 139, with arrows showing parent-to-mutant links and contours of constant TQ-cost.The contours indicate decreasing cost toward the lower left.Source: Figure 2 · p. 16
  • The extended table reports baseline and discovered Toffoli count and peak qubit count across eight tasks, alongside input/output sizes and correctness-test fields.Its caption identifies GT Q as the ratio of baseline to discovered TQ-cost; the supplied passage gives no table cell values.Source: Table 1 · p. 17
  • For the complete benchmark circuit dominated by modular inversion, prior implementations trade Toffolis against qubits, so the authors report no single baseline or gain.Separately, specializing Luo’s space-efficient construction cuts its Toffoli count by a factor of 3.4 at the cost of five additional qubits.Source: EXTENDED DATA · p. 17

SUPPLEMENTARY INFORMATION

The DQI supplement examines decoding-dependent phase correction in two finite-field optimization instances. Under the stated testing framework, the accepted failure rate bounds the loss in satisfied fraction for both instances.

I. SYNDROME DECODING FOR DQI

  • DQI turns certain optimization problems into classical decoding problems, using quantum interference to favor assignments satisfying more constraints.The section describes optimal polynomial intersection and Hermitian optimal polynomial intersection instances.Source: §I · pp. 18–19
  • In the DQI state-preparation sequence, the error e must be erased while its syndrome s = He is retained; uncomputing e is the dominant cost because it requires classical decoding.The inverse QFT then produces amplitudes favoring assignments satisfying more constraints.Source: §I · p. 18
  • The space-efficient construction generates error symbols one at a time and removes them with X-basis measurements, leaving a phase that a reversible decoder must remove using the syndrome.The section calls the measurement bit string c the mask and expresses the phase as (−1)^⟨c,e⟩2.Source: §I · p. 18
  • The two instances are OPI over a Reed–Solomon code and HOPI over a Hermitian code, with Table S1 listing their parameters and expected satisfied fractions.The table compares ideal DQI with a single trial of Prange’s information-set decoding.Source: §I · pp. 18–19, Table S1 · p. 19
  • At ε ≤ 2.434 × 10^-3, Equation (25) bounds satisfied-fraction loss by 5.6 × 10^-3 for Reed–Solomon and 7.0 × 10^-3 for Hermitian, at most 7.4% and 4.9% of their respective advantages over single-trial Prange.The bound follows from accepting at most 100 failures in 100,000 tests at 97.5% confidence.Source: §I · p. 19

I.1. Reed–Solomon decoding for OPI

For the Reed–Solomon decoding subroutine, the discovered circuit replaces the baseline Euclidean solve with a reversible Berlekamp–Massey decoder and computes only the phase bit required by DQI. It reduces Toffoli and qubit costs relative to the Reed–Solomon baseline, while allowing a small probability of failure on the DQI input distribution.

I.1. Reed–Solomon decoding for OPI

  • The Reed–Solomon task uses 70 twelve-bit syndromes and assumes at most 35 errors, which bounds the locator degree by 35.The baseline identifies error positions by scanning roots of the locator, then recovers error values using Forney’s formula.Source: §I.1 · pp. 19–20
  • The baseline uses a 222-cycle synchronized Euclidean solve and costs 5.1 million Toffolis and 1,938 peak qubits; the discovered circuit replaces that solve with Berlekamp–Massey.The baseline’s forward Euclidean solve and reversal account for 3.8 million Toffolis.Source: §I.1 · p. 20
  • Instead of constructing all 49,140 decoded error bits, the circuit computes DQI’s required phase bit directly from the locator and syndromes.It precomputes one reciprocal polynomial so that field division is not performed during the scan.Source: §I.1 · pp. 20, 22
  • Reversible history reconstruction avoids storing every BM discrepancy, but the one-entry stack allows rare overflow and coefficient-cutoff failures.The stack costs 19 qubits; two failure modes occurred with a combined probability of 1.4 × 10−4 across 400 million DQI-distribution samples.Source: §I.1 · pp. 21–22
  • The evaluator polynomial is constructed in place by overwriting syndrome symbols, avoiding a separate 420-qubit register for its coefficients.On a correct decode, the final 35 syndrome symbols become zero workspace and are restored when the map is reversed.Source: §I.1 · p. 22
  • The 4,024-position scan costs 93,000 Toffolis, while the reciprocal-polynomial Euclidean pass costs 44,000 in each direction, versus 1.3 million for the baseline scan.A half-degree construction reduces the reciprocal-polynomial Euclidean computation to degree-17 operands.Source: §I.1 · p. 23
  • 440,000 Toffolis and 1,837 qubits give the discovered circuit a TQ-cost of 8.1×10^8; relative to the baseline, Toffolis fall 12× and qubits 5.2%.The TQ-cost is reduced by 12× relative to the Reed–Solomon baseline; seven of 100,000 complete-circuit tests produced the wrong sign.Source: §I.1 · p. 23

I.2. Hermitian-code decoding for HOPI

This section presents circuits for HOPI decoding and prime-field point addition, focusing on their resource costs, reversible techniques, and implementation limits.

I.2. Hermitian-code decoding for HOPI

  • The HOPI decoder finds a locator as a null vector of a symmetric syndrome-derived matrix without storing the matrix, then scans phase contributions in small stripes.The locator walk processes vectors incrementally, with scheduled repair rounds for rare breakdowns; the phase scan computes and clears temporary data stripe by stripe.Source: §I.2 · pp. 24–27
  • 930,000 Toffolis, 2,395 qubits, and a TQ-cost of 2.2 × 10^9 reduce the Feng–Rao baseline’s Toffoli count by 110×, qubit count by 81×, and TQ-cost by 9,100×.On 100,000 random inputs, 30 produce the wrong sign.Source: §I.2 · pp. 24, 27

II. PRIME-FIELD MODULAR INVERSION

  • In reversible elliptic-curve point addition, modular inversion dominates the cost because its input-dependent arithmetic transitions must later be recovered to clear ancillas.Prior constructions use binary gcd and a two-pass dialog to replay recorded choices, avoiding stored growing coefficients but requiring hundreds of additional qubits.Source: §II · pp. 27–28

II.1. Divsteps

  • The new reversible prime-field inversion architecture uses divsteps whose decisions can be recomputed from updated registers or stored as single history bits; point addition uses four walks.Unlike quotient-based EEA, divsteps avoid multi-bit quotients and full-register multiply-adds, but require more steps; the paper describes this as the first reversible divstep inversion circuit over a prime field.Source: II.1. Divsteps · p. 28
  • 3.6 million Toffolis and 1,031 qubits to 7.9 million Toffolis and 893 qubits span the divstep circuit family; another configuration uses 3.3 million Toffolis and 1,191 qubits.The discovered circuit uses cutoff jstore = 5, reducing the history stack from 198 to 60 qubits for the 533-step schedule.Source: II.1. Divsteps · p. 28
  • The decoder uses two Toffolis at depth two, XORs of q bits at depths three and four, and products of q bits from depth five onward.Every reverse step includes decoders below jstore, with each register-reading term costing at least one Toffoli; sampled ambiguous decisions cluster at depth two (50.1%), then depths three (25.0%) and four (12.5%).Source: II.1. Divsteps · p. 29
  • Freezing the walk when g = 0 handles input-dependent stopping times, while modular halving of r on each active reverse step removes the resulting power-of-two scale without retaining the step count.The circuit marks the freeze step in a register so the reverse walk can clear the frozen flag; it sets r = affv ≡ 2^t aw^-1 (mod p) and finishes with r = aw^-1 and the input w restored.Source: II.1. Divsteps · pp. 29–30
  • Two 256-qubit registers hold f, g, fv, and gv by letting growing coefficients occupy positions vacated by shrinking remainders, rather than using four permanent registers.The width and position assigned to each value are fixed when the circuit is built; a value exceeding its assigned width causes failure.Source: II.1. Divsteps · p. 30
  • The circuit forms a 256-bit square from three products of 128-bit halves, adds them directly to the coordinate register, and uses sparse-prime corrections instead of general modular reduction.Each temporary product is cleared before the next is computed, avoiding a completed-square register and the second full multiplication used by the usual approach.Source: II.1. Divsteps · p. 30
  • The circuit uses 2.5 million Toffolis for four divstep walks (63%), 1.4 million for field multiplications (35%), 0.10 million for fused square and coordinate additions, and peaks at 935 qubits.The algebraic identities behind the recurrence, branch decoders, fused square, and sparse-prime reductions are exact; failures arise from finite stopping-time, integer-size, history, carry, and comparison limits.Source: II.1. Divsteps · p. 30
  • Four of 100,000 full-circuit tests fail; carry truncation after 58 bits (60 for the fused square) has about 2^-26 failure probability per reduction.The comparison limit checks only the top 27 bits, and Table S4 collects the per-use failure contributions multiplied by the number of uses in one point addition.Source: II.1. Divsteps · p. 30

II.2. Specialized Euclidean construction

The specialized Euclidean construction reduces Toffoli cost by fitting the schedule to sampled walks, while preserving the baseline’s packed-register layout. The numerical circuits retain piecewise-polynomial approximations but reorganize lookup and arithmetic for reversible execution, reducing resource costs across HHL rotation-angle, Coulomb-potential, and Gaussian evaluation.

II.2. Specialized Euclidean construction

  • The specialized Euclidean circuit uses fitted windows and test-free positions to shorten the schedule from 1,616 to 1,432 steps, with rare-input failures charged to a 2 × 10^-4 per-point-addition budget.It also merges scans to share intermediate results exactly; the two inversions together account for 98% of Toffolis.Source: II.2. Specialized Euclidean construction · pp. 31–33
  • 843 qubits versus 838 for the baseline accompany a reduction from 69.5 million to 20.5 million Toffolis, a factor of 3.4.The circuits use the same inputs and outputs, input distribution, and failure budget; Figure S2(d) shows the cumulative Toffoli reduction.Source: II.2. Specialized Euclidean construction · p. 31, Figure S2 · p. 32

HHL rotation angle

  • 1,348 Toffolis and 115 qubits achieve a worst-case HHL angle error of 9.95 × 10^-8 radians, reducing TQ-cost by 32× versus tuned HRS.Dyadic intervals and a cyclic shift feed one shared 15-bit polynomial-evaluation stage.Source: HHL rotation angle · p. 34

Coulomb potential

  • 1,140 Toffolis and 142 qubits achieve a worst-case inverse-distance error of 1.91 × 10^-6, reducing TQ-cost by 9.9× versus tuned HRS.The circuit accumulates squared distance directly and uses a finer table of lines instead of quadratics.Source: Coulomb potential · pp. 35–36

Fixed-point Gaussian

  • 1,583 Toffolis and 139 qubits achieve a worst-case error of 9.99×10^-8, reducing TQ-cost by 39× versus tuned HRS.The circuit folds the input onto the nonnegative axis and prunes constant and zero regions of its lookup.Source: Fixed-point Gaussian · p. 36

III. NUMERICAL FUNCTION EVALUATION

  • Across the three numerical tasks, the discovered circuits reduce TQ-cost by 9.9×–39× relative to tuned HRS baselines.They retain piecewise-polynomial approximations while reorganizing interval selection, arithmetic, and coefficient cleanup for reversible execution.Source: §III · p. 33, Fixed-point Gaussian · p. 36

IV. QUANTUM CHEMISTRY SIMULATION

For the Fe2S2 sparse-Pauli simulation, preprocessing exploits Hamiltonian structure to shorten both Select and QROM, reducing the discovered circuit’s Toffoli count, qubit count, and TQ-cost relative to the baseline. The compression depends on available structure and is specific in amount to this Hamiltonian.

Circuit-aware table preprocessing

  • Preprocessing groups Pauli operators related by fixed Clifford transformations and rearranges alias-table pairings to create repeated patterns, shortening Select and QROM while preserving the rounded distribution.The two freedoms are term permutation and choosing among alias tables realizing the same rounded distribution.Source: §IV · pp. 38–39

Frame-block Select

  • Frame-block Select represents related Pauli operators using one block representative plus controlled frames, rather than selecting every operator independently.The 41,052 terms form 3,221 blocks; selecting representatives costs 3,327 Toffolis and applying seven frames costs 534.Source: §IV · p. 38

Alias-table QROM

  • Repeated alias-word subtrees let QROM skip irrelevant address bits, reducing its cost to 10,000 Toffolis from 41,000 for row-by-row traversal.The baseline lookup costs 13,000 Toffolis.Source: §IV · p. 39

Results

  • 15,000 Toffolis and 126 qubits yield a TQ-cost of 1.9 × 10^6, reducing baseline Toffolis by 3.7×, qubits by 9.4%, and TQ-cost by 4.1×.The circuit was tested on every table row and 224 additional uniformly random inputs.Source: §IV · p. 39

Scope

  • The compression amount is Hamiltonian-specific; preprocessing falls back to conventional Select and QROM costs when it finds no useful relations, and spin-symmetry-breaking terms reduce the opportunity.The text identifies Zeeman terms and spin–orbit coupling as cases that break spin symmetries.Source: §IV · p. 39

V. NONABELIAN LATTICE-GAUGE SIMULATION

For a nonabelian lattice-gauge magnetic layer, the discovered circuit combines a specialized running-product representation, loop-product reuse, and direct trace readout. On the stated 4 × 4 × 4 lattice, it reduces Toffolis and TQ-cost substantially relative to the baseline, with a smaller qubit reduction.

Circuit design

  • Three optimizations drive the circuit: different factor orders make running-product updates cheaper, shared loop products are reused, and trace values are read directly from product coordinates instead of QROM.The magnetic layer applies the weighted trace contributions from plaquettes and rectangles across the lattice.Source: §V · pp. 40–41

Specialized running-product representation

  • The specialized representation reduces each running-product update from 146 Toffolis to 35 and makes inverse-link multiplication cost the same, avoiding a separate link-inversion circuit.One-hot storage for the running product’s three-valued coordinates enables controlled qubit permutations.Source: §V · p. 42

Reusing loop products

  • Cyclic rotation and inversion preserve the real trace, allowing a classical dynamic program to choose loop representatives and an evaluation order that reuse shared factors.The schedule uses 3,136 link multiplications and 480 running-product inversions for 576 loops, about 5.4 multiplications per loop.Source: §V · p. 42

Reading the trace directly

  • Direct trace readout computes six flags from the specialized coordinates, avoiding storage of a 51-bit lookup result; readout, addition, and cleanup cost 76 Toffolis per plaquette and 75 per rectangle, versus 478 for baseline QROM.At most one of the six nonzero-trace flags is set.Source: §V · p. 42

Results

  • 170,000 Toffolis and 1,859 qubits give a TQ-cost of 3.2 × 10^8, reducing baseline Toffolis by 7.4×, qubits by 3.5%, and TQ-cost by 7.7×.The complete circuit was tested on 100,000 random inputs, and each group operation on all its inputs.Source: §V · p. 42

Appendix A: Exact branch recovery for divstep inversion

The appendix establishes an exact rule for recovering divstep branch decisions from the updated state. It derives locally visible cases and a finite low-bit window for ambiguous decisions.

Appendix A: Exact branch recovery for divstep inversion

  • Induction establishes determinant and parity invariants, while every step preserves gcd(f, g); at termination with g = 0, |f| = gcd(p, w).When gcd(p, w) = 1, termination gives f = ±1 and gv = fp.Source: Appendix A · p. 44
  • For the specified prime p, every 0 ≤ w < p reaches g = 0 within 590 active steps.The walk starts frozen when w = 0.Source: Appendix A · p. 45
  • The swap s and b in special cases are locally visible: a swap implies b = 1, a nonswap with z′ ≥ 1 implies b = 0, and g′ = 0 implies b = 1.Here b records whether the two values are combined before halving; the walk freezes when g first becomes zero.Source: Appendix A · pp. 44–45
  • For negative-counter nonswaps, earlier tests leave b ambiguous, but a low-order-bit window accumulates successive b decisions during an excursion.The window contains 1 immediately after the initiating swap, with each subsequent ambiguous decision placed in the next higher position.Source: Appendix A · pp. 45–46
  • For fixed odd p, an ambiguous b is determined by j, f′ mod 2^j, and q mod 2^j, requiring at most 2j updated-state bits.The residues of f′ and q each use j bits.Source: Appendix A · p. 46

Related papers

Loading 2610.22367v1…