Useful quantum algorithms need far more qubits and gates than current machines provide, and much of the progress in bringing those requirements down has come from redesigning the circuits that carry out the computation rather than from better hardware. This post, published on 16 October 2026 under Anthropic's Science label, asks whether Claude can do that redesign when given only a plain-language specification of what a circuit must compute and an automated program that checks and scores each attempt. It summarizes the paper Discovering state-of-the-art quantum circuits with large language models by Andi Gu, Alek H. Kemeny, Susanne F. Yelin and Mikhail D. Lukin (arXiv:2610.22367v1, 15 October 2026), which is the version of record for the numbers below. The paper is a preprint and had not been peer reviewed as of 13 November 2026. The circuits, task definitions, evaluator and Lean proofs are released in the repository andigu/uncompute (read at commit 64b5a13, 16 October 2026). The work was led by Gu as an Anthropic STEM Fellow, mentored by Kemeny, in collaboration with Yelin and Lukin.
Why quantum circuits are hard to optimize
Two constraints ordinary programs do not have
The post and the paper's introduction explain why compiling a classical function into a quantum circuit is expensive:
- No branching. Because a quantum computer may act on a superposition of many inputs at once, a circuit cannot test a value and run only one branch. It must contain the operations for every branch, controlled on the relevant condition.
- Reversibility. A quantum circuit cannot discard intermediate results. Temporary values must be uncomputed, returned to zero by running the computation that produced them in reverse, which costs more gates. Keeping them instead costs more qubits.
This forces a trade-off between space (qubits) and time (gates). The cost measures used throughout are the Toffoli count T (the Toffoli gate is expensive in error-corrected machines, so its count is a standard proxy for runtime) and the peak qubit count Q. Circuits are ranked by their product, the TQ-cost (paper, Methods, "Cost model and scoring"). The paper notes that this weighting is a simplification: when qubits are scarce, weighting them more heavily may be more appropriate.
Why these tasks can be checked automatically
The tasks are circuits that compute a classical function. For such circuits, correctness on every basis input implies correctness on superpositions, and each test can be simulated by tracking a bit string and a sign rather than an exponentially large state (paper, introduction and Methods, "Circuit model and validity"). This is what makes a cheap, independent evaluator possible.
What the authors did
The search ran with OpenEvolve, an open-source evolutionary coding framework, using Claude Mythos 5 to propose and revise programs (paper, Methods, "Evolutionary search"). Each candidate is a Python program that builds a circuit. For each of eight tasks:
- A hand-written task specification states what the circuit must compute, the circuit model and the correctness criteria, with no implementation guidance. The search starts from a blank program.
- In an ideation stage the model proposes several distinct algorithm families, which are developed in parallel and periodically share strong candidates.
- Each iteration is a fresh agent session given the specification, a parent program, its evaluator feedback, some alternative programs and brief notes from earlier attempts. The agent can run drafts, query a classical oracle for the required function, and delegate subtasks before submitting a revised program.
- The evaluator rejects any circuit that fails the specification and scores valid ones by TQ-cost. It tests sampled inputs (for most tasks 10⁵ tests, for some 9×10³ or 2×10⁷; Extended Data Table 1) and checks the output, the sign, and that every helper qubit returns to zero. A MAP-Elites archive keeps circuits with different T and Q trade-offs.
The paper states that the model "produces the discovered circuits without substantive human intervention." The post adds detail for the hardest task: Claude received a one-paragraph brief, worked for 53 hours, and human input was "limited to the initial brief and occasional prompts to think more broadly" (section "A hard first test: modular inversion"). The 53-hour figure is in the post, not the paper.
Some tasks allow a failure budget: a small probability that the circuit fails on rare inputs, which most quantum algorithms tolerate. Several of the discovered savings come from spending this budget on rare, expensive inputs.
What it finds
Results across the eight tasks
The paper's Table I compares each discovered circuit with a baseline; Extended Data Table 1 gives the correctness criteria. Where a baseline has free parameters, the authors set them to minimize its TQ-cost. Baselines are the authors' reconstructions of published constructions in the same evaluator. G_TQ is the ratio of baseline to discovered TQ-cost.
| Task | Baseline (T, Q) | Discovered (T, Q) | G_TQ |
|---|---|---|---|
| Reed-Solomon decoder for DQI | 5.1×10⁶, 1,938 | 4.4×10⁵, 1,837 | 12 |
| HHL rotation angle | 1.6×10⁴, 300 | 1,348, 115 | 32 |
| Coulomb potential | 6,355, 252 | 1,140, 142 | 9.9 |
| Fixed-point Gaussian | 2.4×10⁴, 362 | 1,583, 139 | 39 |
| Fe2S2 alias-Select (chemistry) | 5.5×10⁴, 139 | 1.5×10⁴, 126 | 4.1 |
| Nonabelian lattice-gauge simulation | 1.3×10⁶, 1,927 | 1.7×10⁵, 1,859 | 7.7 |
| Hermitian-code decoder for DQI | 1.0×10⁸, 1.9×10⁵ | 9.3×10⁵, 2,395 | not given |
| Prime-field modular inversion (point addition) | no single baseline | 4.0×10⁶, 935 | not given |
The table restates numbers from the paper's Table I. For the Hermitian decoder the baseline is a naive reversible implementation, because no prior reversible compilation exists, and the paper reports no gain. For modular inversion, several earlier designs trade gates and qubits differently, so the paper reports no single baseline (see below).
The paper's abstract states that "in seven of the eight tasks, the discovered circuits significantly reduce both Toffoli and qubit counts relative to the state of the art." The post states it more broadly: across the eight primitives, Claude found designs "that used both fewer qubits and fewer gates than the best previously published algorithms." By the paper's own Table I, that holds against a published construction for six tasks; the seventh is compared with a naive implementation, and the eighth has no single baseline. The post's Figure 2 also plots the Hermitian decoder's naive baseline as "Prior work," under a caption that calls the gray marks "the best previously published designs," although the paper says no prior reversible compilation exists for that task (Table I, note).
Reed-Solomon decoding for DQI: about 12 times cheaper
Decoded quantum interferometry (DQI) is a quantum optimization algorithm that turns certain optimization problems into decoding problems for error-correcting codes; the decoder is its most expensive step. The baseline is Google Quantum AI's circuit (Khattar et al., arXiv:2510.10967), which uses the extended Euclidean algorithm. The discovered circuit switches to the Berlekamp-Massey algorithm, whose rounds have a fixed structure that suits a circuit, and avoids storing most intermediate history by rescaling the update (the locator polynomial is needed only up to a constant factor) and reconstructing values from the current state (paper, section "Reversible syndrome decoding for DQI").
The worst case would need 35 stored entries, 665 qubits. Under the DQI input distribution a second entry is needed with probability 1.0×10⁻⁴, so the circuit keeps one entry (19 qubits) and accepts failure on those rare inputs. Over 400 million sampled inputs, the combined failure probability of the circuit's two failure modes was 1.4×10⁻⁴ (Supplementary Information I.1); the post gives the sample as 403 million decodings. In the evaluator's 100,000 tests of the complete circuit, seven produced the wrong sign (SI I.1), within the task's failure budget of 10⁻³ (Extended Data Table 1). The locator step alone fell from about 1.9 million Toffolis (Euclidean) to about 140,000 (Berlekamp-Massey) (Figure 2 caption). The whole decoder's Toffoli count fell from 5.1×10⁶ to 4.4×10⁵, which the post rounds to "a factor of 12." The baseline agrees within about 2% in Toffoli count with an estimate recomputed from Google's released code (paper, note 45).
The post adds context from Google's estimates: one OPI instance would take about three months on the Frontier supercomputer and roughly an hour on a future quantum computer running DQI, most of that hour spent in decoding. These figures were not checked against the Google paper for this note.
Modular inversion with divsteps: a new design on the trade-off curve
Modular inversion (finding x with wx ≡ 1 mod p) is the costliest step of elliptic-curve point addition, the core of quantum attacks on elliptic-curve cryptography. Divsteps (Bernstein and Yang, 2019) is an efficient classical inversion method, but reversible versions had seemed to need a long record of which branch was taken at each step. The discovered circuit recovers most branch decisions from the registers as they stand after each step, so they need not be stored (paper, section "Reversible modular inversion"). A tunable cutoff decides which decisions are decoded and which are stored; at the chosen setting only 12.4% of ambiguous decisions are stored (Figure 3). The circuit also reserves room for 60 stored decisions rather than the worst case of 263, failing with probability 2.4×10⁻⁶, and schedules 533 steps instead of the proven worst case of 590. The paper calls this, to the authors' knowledge, "the first reversible divstep inversion circuit over a prime field" (SI II.1).
How it compares (paper, Table S3; the post's Table 1 gives the same Toffoli and qubit counts, without the TQ column):
| Design | Toffolis | Qubits | TQ |
|---|---|---|---|
| Schrottenloher (2026) | 1.9×10⁶ | 1,446 | 2.7×10⁹ |
| Discovered divsteps circuit | 4.0×10⁶ | 935 | 3.7×10⁹ |
| Luo et al. (2026) | 7.0×10⁷ | 838 | 5.8×10¹⁰ |
| Discovered specialized Euclidean | 2.1×10⁷ | 843 | 1.7×10¹⁰ |
The divsteps circuit uses about 12% more qubits than the smallest prior design (Luo et al.) and about 17 times fewer Toffolis, as the post says. It uses about twice the Toffolis of Schrottenloher's design and has a higher TQ-cost, so it is a new point on the trade-off between qubits and gates rather than an improvement on every measure; varying the cutoff gives a family from 3.6 million Toffolis and 1,031 qubits to 7.9 million and 893 (SI II.1). The post's description, that the designs "expand the Pareto frontier," matches the table. A second discovered circuit, specialized from Luo et al.'s, cuts that design's Toffoli count by a factor of 3.4 at a cost of five qubits.
What the authors say the gains came from
The paper identifies three recurring design principles in the discovered circuits: routing data through one shared operation instead of controlling separate operations for each branch, recovering branch decisions from the current state instead of storing them, and spending the failure budget to drop resources needed only by rare inputs (section "Design principles"). The authors suggest that "some apparent costs of quantum arithmetic reflect limitations of existing reversible constructions rather than of the algorithms themselves" (Discussion).
Who checked the results
- The evaluator. Every reported circuit passed the evaluator's sampled tests, and the paper derives a bound on the error that undetected failures could cause given the number of tests passed (Methods, "Validation and statistical guarantees"). The repository's README says the evaluator counts costs exactly and tests on random inputs drawn from a hash of the circuit, so any change draws new tests. Anyone can rerun the released circuits.
- Formal proofs. The post says Claude checked the divsteps decoding rule in large simulations and then formalized it in Lean. The repository's Lean development certifies that every input terminates within 590 steps and that each branch decision can be recovered from the state after the step. Its README states that it "does not formalize the complete quantum circuit or its resource count." The README also says that the 590-step certificate and its soundness proof follow Wuille's 2021 Coq development (the paper likewise credits the 590 bound to Wuille, Proposition A.3), that the branch-recovery proofs are new, and that the step bound relies on Lean's
native_decide, so it trusts the compiler for that computation. A second Lean development, according to the repository README, covers the decoder-error bound used by the DQI tasks. The paper's Appendix A gives a written proof of the decoding rule. - Human review. The paper acknowledges six people for feedback on the manuscript. It has not been through peer review, and no outside replication or published commentary was found for this note.
Limitations
- Bounded by the task definition (paper, Discussion). The TQ objective is one choice among several; the right weighting of qubits, depth and other costs depends on hardware. The fixed computational-basis interface excludes optimizations that change the encoding. Each task's input distribution and accuracy target encode assumptions about how the circuit is used in a larger algorithm.
- Failure budgets. Several savings rely on accepting small failure rates, estimated by sampling; whether a given budget is acceptable depends on the application.
- Baselines are reconstructions. The baselines were rebuilt by the authors in their own framework, with free parameters set to favor the baseline's TQ-cost; one was checked against the original authors' released code.
- Human input. The task specifications were written by hand, and the post reports occasional prompts to broaden the search. The paper calls this not "substantive"; neither document quantifies it.
- Model behavior. The post reports that Claude was "conservative by nature" in early experiments, repeatedly re-checking well-supported improvements and preferring known approaches. Requiring several approaches in parallel and occasional prompts to think more broadly were the remedies (section "What we learned"). This is the authors' observation, not a measured comparison.
- Search cost. Neither document reports the total compute or the number of iterations for each search, apart from the 53-hour figure for modular inversion in the post.
The task specifications and prompts
The written inputs that steered the search were the hand-written task specifications and the fixed instructions for ideation and rewriting. Extended Data Figure 1 shows a sample for a small field-inversion task. The ideation instruction begins "From the task specification alone, propose up to five distinct circuit architectures," and the rewrite instruction tells the model that "the evaluator is ground truth" and asks it to record up to three lines beginning "DISCOVERY:", notes that travel with the program to later sessions. The paper does not compare alternative wordings of these instructions. The post credits the requirement to propose several different approaches, and occasional prompts to broaden the search, with getting the model to pursue more ambitious ideas, without a controlled comparison.
Research questions
- How much does the ideation stage matter? The authors credit separate algorithm families with escaping local optima. Running the same searches with a single family, at equal budget, would measure its contribution.
- What did the searches cost? Reporting iterations, tokens and wall-clock time for each task would let readers compare this method with expert effort and with other automated searches.
- Are the gains robust to other objectives? Rerunning the searches with qubits weighted more heavily, or with Toffoli depth instead of count, would show whether the discovered principles hold under hardware-specific costs.
- How much did the occasional human prompts contribute? Logging every human message and repeating a task without them would test the paper's statement that there was no substantive intervention.
- Do the end-to-end resource estimates change? Substituting the discovered DQI decoder and divsteps inversion into full resource estimates for OPI and elliptic-curve attacks would show the effect on whole algorithms.
- Will outside groups confirm the circuits? Independent re-evaluation of the released circuits, or their adoption in later resource estimates, would be the strongest check beyond the authors' own evaluator.
How it connects
- Claude computes a nine-loop amplitude in N=4 super-Yang-Mills and LLMs are making formal software verification feasible at a much larger scale are other Science posts of autumn 2026 in which a result was checked by machine (internal cross-checks, an evaluator, a proof assistant); this connection is the note's own.
- How Claude is uplifting biomolecular modeling is linked by the post in its sentence on Claude's skill at optimizing classical algorithms.
- Long-running Claude for scientific computing describes another setup in which an agent works for long periods against an automated check; the post does not cite it.
- Introducing our Science Blog announced the Science label under which this post appears.
References
- Gu, A., Kemeny, A., Yelin, S., and Lukin, M. (2026, October 16). Designing more efficient quantum circuits with Claude. Anthropic. https://www.anthropic.com/research/designing-efficient-quantum-circuits record
- Gu, A., Kemeny, A. H., Yelin, S. F., and Lukin, M. D. (2026). Discovering state-of-the-art quantum circuits with large language models. arXiv:2610.22367v1 (15 October 2026). https://arxiv.org/abs/2610.22367 record
- Gu, A. uncompute [Code repository]. https://github.com/andigu/uncompute, README.md and lean/divsteps/README.md read at commit 64b5a13 (16 October 2026). record
- Khattar, T., et al. (2025). Verifiable Quantum Advantage via Optimized DQI Circuits. arXiv:2510.10967. Title from the arXiv record; cited as the paper and post describe it, not read for this note. record
- Jordan, S. P., et al. (2024). Optimization by Decoded Quantum Interferometry. arXiv:2408.08292. Title from the arXiv record; not read for this note. record