Claude's quantum circuits explained: 17x fewer gates, found in 53 hours

Quantum computers do not exist yet in any useful form, but the programs they will run are being written, costed and argued over today. This week Anthropic and Harvard researchers reported that Claude Mythos 5, left alone in a loop with a grader, rewrote eight of those programs so that seven of them need fewer expensive operations and fewer qubits than the best prior designs the authors could compare against. The interesting part is not the headline multiple. It is why this particular kind of problem turned out to be one an AI could grind down on its own, and what the counts leave out.

The plain-English version

Imagine a kitchen where you are never allowed to throw anything away. Every bowl you use for mixing has to be washed and put back exactly where it came from before the meal is finished, and washing takes as long as cooking. That is roughly the situation inside a quantum computer. Ordinary computers overwrite scratch memory constantly. Quantum computers cannot, because the physics requires every step to be reversible. So any temporary value a quantum program produces has to be "uncomputed", meaning run backwards until the scratch qubits are clean again. Most of the cost of a quantum algorithm is not the clever quantum part. It is the washing-up.

The people who design these programs, called circuits, have spent years finding ways to use fewer bowls and wash them faster. The standard way to measure progress is to count two things: how many of the most expensive operations, called Toffoli gates, the circuit needs, and how many qubits it occupies at its peak. Anthropic's post gives the field's favourite example: in 2017 the estimated cost of simulating one important molecule, the nitrogenase cluster FeMoco, was about 50 trillion Toffoli gates. Years of human redesign brought that down to about 340 million, a 150,000-fold cut, with no change to the hardware at all.

What the new paper did was hand that redesign job to an AI. Lead author Andi Gu, a Harvard PhD student working through Anthropic's STEM Fellows Program with Anthropic physicist Alek Kemeny and Harvard's Susanne Yelin and Mikhail Lukin (Lukin is also co-founder of QuEra Computing), gave Claude Mythos 5 eight written task descriptions. Each described a small, reusable piece of a quantum algorithm: a function to compute, a decoder to run, a piece of chemistry to encode. Claude wrote a program that builds the circuit. A separate checker, running on an ordinary computer, tested whether the circuit gave the right answers and scored it by gates multiplied by qubits. The score went back to Claude, which tried again. Nobody edited anything between rounds.

The result, as reported by the authors: on seven of the eight tasks, the circuits Claude ended up with use both fewer Toffoli gates and fewer qubits than the baseline. For six of those the baseline is a previously published design and the cost score dropped by between 4 and 39 times; for the seventh, a decoder with no prior reversible implementation, the authors built their own baseline and report a 9,100-fold drop. On the eighth task, Claude found a new way of doing a piece of arithmetic that cryptographers care about, which at one setting uses 17 times fewer gates than the most compact prior design in exchange for 12% more qubits. That run took 53 hours.

Two things to hold onto. First, nothing ran on a quantum computer. These are paper estimates, checked by simulation, for machines that are still years away. Second, this does not mean AI has "cracked" quantum computing or broken any encryption. It means a specific kind of expert work, the slow shaving of gates and qubits from known algorithms, can now apparently be done by a model in a loop, because that work has a property most research does not: a classical computer can check the answer.

How it actually works

The method has three parts: a way to represent circuits, a way to check them, and a way to search.

Representation. Earlier automated circuit optimisers mostly worked on a circuit as a list of gates, applying rewrite rules that preserve its behaviour. That can tidy a design but cannot change the algorithm underneath. The paper's authors instead have the model write Python programs that construct circuits, using loops, functions and named registers through a shared circuit-building interface that the humans wrote once. This matters because the biggest wins in the paper are algorithmic, not local. In the Reed–Solomon decoder, for instance, Claude did not optimise Google's extended-Euclidean decoder. It replaced it with a different decoding algorithm, Berlekamp–Massey, which runs the same sequence of steps for every input and so fits a fixed quantum circuit better.

Checking. This is the part that makes everything else possible. General quantum circuits cannot be simulated classically at useful sizes. But the circuits in question, reversible arithmetic with some phase gates and measurement-based cleanup, fall into the "kickmix" circuit model, defined by Babbush et al. at Google and adopted by the paper, which a classical computer can simulate by tracking basis strings and phases. The evaluator feeds a candidate circuit tens of thousands of inputs and checks four things: the output is right, the inputs are unchanged, every scratch qubit is back to zero, and the phase is exact. For large input spaces it samples. A circuit that passes gets a score; one that fails gets a rejection and feedback.

Search. The loop runs inside OpenEvolve, an open-source implementation of the evolutionary program search popularised by DeepMind's AlphaEvolve. Each iteration starts a fresh Claude session with the task specification, a parent program, its evaluation feedback, a selection of archived programs and summaries of earlier attempts. The paper stresses that no session sees the complete history. The agent can run drafts, query a classical oracle for the correct answer, and spawn subagents for subproblems. Selection uses MAP-Elites: rather than keeping one best circuit, it divides the Toffoli-versus-qubit plane into cells and keeps the cheapest design in each, so the search naturally produces a family of trade-offs rather than a single winner. The authors also required Claude to develop several qualitatively different "algorithm families" in parallel, for example three different decoders for Reed–Solomon, and periodically shared strong candidates across families.

A worked example makes the loop concrete. Take modular inversion, the costliest step in adding two points on an elliptic curve, which is the inner loop of a quantum attack on elliptic-curve cryptography and a standard benchmark.

1. The classical algorithm of choice, divsteps, is simple and runs for a fixed number of steps, which is exactly what a quantum circuit wants. But at each step it branches on whether a number is odd or negative, and a reversible circuit has to remember every branch so it can be undone. For 256-bit numbers that is a long history, and storing it costs hundreds of qubits. So nobody used divsteps reversibly.
2. Claude's proposal: do not store the branches. Recover them. It conjectured that the branch taken at each step can be read back from the values still sitting in the registers during uncomputation, derived the algebraic identity, checked it numerically on 256-bit inputs, and, according to Anthropic's post, formalised the proof in Lean.
3. Decoding every decision is possible in principle, but the decoder gets expensive for deep cases, so the circuit uses a cutoff. According to the paper, 87.6% of the ambiguous branch decisions are decoded this way and the remaining 12.4% go on a 60-qubit stack.
4. The resulting circuit, for the complete point-addition benchmark, uses about 4.0 million Toffoli gates and 935 qubits. The prior space-efficient design from Luo et al. uses about 70 million Toffolis and 838 qubits. Hence the headline: 17 times fewer gates for 12% more qubits.

The same pattern, trade stored information for recomputed or decoded information, and trade worst-case guarantees for typical-case sizing with an explicit failure budget, recurs across the eight tasks.

The deep dive

The objective and the evaluator

The score is the product of Toffoli count $T$ (Toffoli and CCZ counted equally) and peak qubit count $Q$:

The authors say they weight space and time equally "for simplicity" and note the scoring function can be swapped for Toffoli depth, a qubit exponent or active volume. Everything downstream, including which designs MAP-Elites keeps, depends on this choice.

Verification is statistical for large domains. With $k$ passing random tests and confidence $1-\delta$, the per-input failure probability is bounded by

and the paper translates trajectory failures into state fidelity: if a fraction $\varepsilon$ of trajectories are defective, $\| |\Phi_V\rangle - |\Phi_U\rangle \| \le 2\sqrt{\varepsilon}$ and fidelity is at least $(1-2\varepsilon)^2$. A separate failure budget lets specified circuits fail on a bounded fraction of inputs from a stated distribution; the acceptance rule with $b$ allowed failures in $k$ tests is the usual binomial tail $P_{k,b}(\varepsilon)=\sum_{j=0}^{b}\binom{k}{j}\varepsilon^j(1-\varepsilon)^{k-j}$.

The kickmix restriction is a real limit. Measurement outcomes may correct phases but "cannot control gates that change the stored basis string", and encodings are fixed, so coset-style tricks that change the number representation are out of scope.

Results table

All numbers below are from Table 1 of the paper and its supplementary sections, as reported by the authors. "Baseline" is whatever the authors compared against; see the notes, because the baselines are not all of the same kind.

Point-addition constructions, from the paper's comparison table:

Note that on raw TQ, Schrottenloher's design still wins. The divsteps circuit is a new point on the frontier, not a dominating one, and that is exactly how the paper frames it: "a new reversible architecture" that "improves the Toffoli-qubit trade-off". The "17x fewer gates" compares to Luo et al., the smallest-qubit design. Claude also separately specialised Luo et al.'s own construction, cutting its Toffolis by a factor of 3.4 (69.5 million to 20.5 million) for five more qubits.

What the search actually found

The paper names three recurring principles, and each shows up as a concrete mechanism.

Conditional routing instead of conditional arithmetic. Where an algorithm does one of several arithmetic operations depending on a flag, the naïve reversible version builds each branch and controls it. Claude's designs instead route operands through controlled SWAPs into one shared arithmetic block. For the paper's $n$-bit example the naïve Toffoli count is $T_{\text{naive}}(n) = 3n^2 + 17n - 2$ and the routed count is exactly half.

Information recovery instead of history stacks. The divsteps result is the showcase. The branch-decoding rule in the paper reads $b = \mathrm{bit}_{j-1}(g_v' q^{-1} \bmod 2^j)$, where $j$ is the excursion depth and $q$ the odd factor in $f_v$. The inversion is over the secp256k1 prime $p = 2^{256} - 2^{32} - 977$, with a worst-case bound of 590 active steps cited from Wuille. The authors report a stack-overflow probability of about 2.4×10⁻⁶ per inversion, a schedule failure near 10⁻⁵, and four failures in 100,000 tests of the full circuit.

Failure budgets for rare inputs. The Reed–Solomon decoder is the clearest case. Berlekamp–Massey occasionally needs to save an intermediate value; worst case, 665 qubits of reserve. The authors simulated roughly 400 million decodings (Anthropic's post says 403 million) on the task's input distribution, found that almost every run needs at most one saved value, and reserved 19 qubits. Combined failure probability from the cutoffs is 1.4×10⁻⁴; in 100,000 tests, seven produced the wrong sign. The task's budget was 10⁻³. For context, Google's own Khattar et al. paper put a classically intractable optimal-polynomial-intersection instance at about 5.72 million Toffolis in total, dominated by this decoder, and already used in-place architectures and a "dialog" representation to get there. Claude's decoder takes that dominant term from 5.1 million to 440,000.

The Hermitian decoder's 9,100x figure deserves its own flag. There was no prior reversible implementation, so the baseline is the authors' straightforward Feng–Rao compilation at 100 million Toffolis and 190,000 qubits. The discovered circuit never stores the syndrome matrix it works with: it finds the error locator with a Lanczos recurrence that keeps only a few vectors at a time, then applies the phase in a striped scan over the curve points. That is a genuine engineering result (and Gu has published on algebraic-geometry codes for DQI before), but a 9,100x multiple against a strawman baseline is not the same claim as the 12x against Google's optimised Reed–Solomon decoder.

Chemistry and simulation

The Fe₂S₂ task is a Select oracle for a 30-electron, 20-orbital (40-qubit) active space with 41,052 Hamiltonian terms after discarding coefficients below 10⁻⁴ Ha. Claude's design organises the terms into 7 frames and 3,221 blocks and uses an alias-table QROM (10,000 Toffolis versus 41,000 for row-by-row traversal), exploiting the fact that of 20,374 spin-related row pairs, 18,463 store identical alias words. Tests covered every table row plus 2²⁴ random inputs. The lattice-gauge step, on a periodic 4×4×4 lattice with 192 links, breaks down as 110,000 Toffolis for the Wilson-loop updates, 43,000 for trace readout and addition, 10,000 for inversions and 8,832 for link recoding.

Relation to prior automated design

The closest prior work is DeepMind's AlphaTensor-Quantum, which cast T-count reduction as tensor decomposition and, notably, rediscovered measurement-based uncomputation on its own, halving the Toffoli count of ripple-carry adders. But it optimised a fixed circuit's gate structure rather than the algorithm. The Anthropic paper does not cite it; it positions itself against AlphaEvolve and FunSearch, the LLM-plus-evaluator lineage, and against rewrite-based optimisers, arguing that gate-sequence representations "can obscure the algorithmic structure of the circuit". The honest comparison is that this paper changes the level of abstraction at which the search operates, from gates to algorithms, at the price of needing a problem where correctness is classically checkable.

What the paper does not report

There is no iteration count, no number of LLM calls, no token or dollar figure, and no wall-clock time for any search except the 53 agent-hours for modular inversion that Anthropic's blog gives (the one lineage plot in the paper, for the Gaussian circuit, runs to 94 iterations). Code and circuit release are not stated beyond Gu's GitHub repository "uncompute" for the divsteps proof.

Why it matters

For the quantum field. Resource estimates are the currency of fault-tolerant quantum computing: they decide which applications look reachable and how many physical qubits a machine must have. The FeMoco history shows those estimates can move by orders of magnitude through circuit design alone. If a model-in-a-loop can reliably find 4x to 40x on well-specified subroutines, every published resource estimate for chemistry, simulation and DQI-style optimisation is now provisional in a new way, and groups will start re-running their own circuits through this kind of search before publishing.

For cryptography. The honest read is "watch, do not panic". The point-addition result improves one trade-off point in one component of an elliptic-curve discrete-log attack, and Schrottenloher's human design still uses fewer gates. But the pattern, an AI finding that a classical algorithm previously dismissed as impractical for reversible arithmetic actually works, is precisely the kind of surprise that resource estimates for breaking ECC and RSA do not budget for.

For AI research agents. This is a cleaner demonstration than most of what gets called "AI doing science". The task specifications and the interface were human-written, but the algorithmic ideas, the Berlekamp–Massey swap, the branch-decoding identity, the alias-table layout, came from the loop. The common thread with DeepMind's AlphaEvolve results and with OpenAI's Lean-checked mathematics is the same: progress arrives fastest where a cheap, trustworthy verifier exists. Quantum circuit design in the kickmix model happens to be such a place. Most of science is not.

For Anthropic. The company has been arguing that Mythos-class models are useful for real research and not just coding. A result with Harvard co-authors, a 46-page paper, and numbers against Google's own baselines is a better piece of evidence for that than a benchmark table. It is also, inevitably, marketing, and should be read with that in mind.

Second-order. The authors' stated next step is co-design: letting a search redesign algorithm, error-correcting code, magic-state supply and hardware layout together, with an evaluator that propagates logical error and resource demands across layers. If that works, the question of what a quantum computer should look like becomes partly an optimisation problem rather than a hardware tradition.

What to be skeptical of

Baselines are mixed. Three of the seven "state of the art" baselines (HHL, Coulomb, Gaussian) are the authors' own tuned versions of Häner et al.'s numerical constructions, not independently published optima. The Hermitian decoder has no prior reversible implementation at all, so its 9,100x is against a naïve compilation. The strongest claims are the ones against external, optimised designs: Google's Reed–Solomon decoder (12x), Babbush et al. (4.1x) and Osorio Perez et al. (7.7x).

The metric is a proxy. Toffoli count times peak qubits ignores Toffoli depth, routing on a real connectivity graph, measurement latency, magic-state distillation and the error-correcting code. The paper says so. A design that wins on TQ can lose on a particular machine.

Several circuits are allowed to be wrong. The Reed–Solomon decoder fails about once in 10,000 runs; the Hermitian decoder gave the wrong sign on 30 of 100,000 inputs; the divsteps circuit failed 4 of 100,000. These are within stated budgets and are standard engineering, but as Hacker News commenter adastra22 put it, "So it's not performing the same computation", and whether the budgets are acceptable depends on the enclosing algorithm. Another commenter, perching_aix, called it "a perfectly standard optimization strategy". Both are right.

Verification is sampled. No circuit was checked exhaustively on its full input domain. The Fe₂S₂ and lattice-gauge tasks require exact answers everywhere, and were tested on every table row plus 2²⁴ random inputs and on 100,000 random inputs respectively (with the lattice group operations checked on all their inputs). The rest rest on statistical bounds from roughly 9,000 to 100,000 tests. That is normal for the field but is not a proof.

No independent replication, and conflicts of interest are obvious. Two of four authors are Anthropic-affiliated, the model is Anthropic's, and the post is on Anthropic's site. None of the early coverage in The Quantum Insider, Unite.AI or Interesting Engineering quotes an independent expert, and we did not find any named quantum researcher weighing in within 48 hours either.

Not as autonomous as the headline. Anthropic's own post says Claude was "conservative", repeatedly re-verified settled results and preferred known approaches, and that the team had to require parallel families and prompt it to broaden its search before the divsteps idea appeared. "No human input between rounds" is true of the inner loop, not of the whole 53 hours.

Cost is undisclosed. Without iteration counts or compute figures, nobody can judge whether this is cheaper than paying a postdoc, or reproducible by a group without frontier-model access.

What to watch next

• Independent reproduction of the Reed–Solomon decoder. Google Quantum AI published its baseline data, and the DQI community is active. A confirmation or correction of the 440,000-Toffoli figure from outside Anthropic would be the first real test.
• Whether the evaluator and circuits are released. The paper cites Gu's GitHub repository for the divsteps proof only. If the full kickmix evaluator and the OpenEvolve configs appear, expect other groups to run their own primitives through it within weeks.
• Peer review. The preprint was posted 15 October; watch for a journal version and for whether the baseline choices survive review.
• Updated resource estimates. Any new ECDLP or RSA estimate that cites the divsteps construction, and any DQI advantage estimate below Khattar et al.'s 5.72 million Toffolis.
• Co-design papers. The authors' stated next step is joint search over algorithm, code and hardware. A first paper in that direction, from this group or from DeepMind's AlphaEvolve team, would show whether the approach scales beyond isolated primitives.
• Related earlier coverage. The same "cheap verifier, fast progress" logic ran through OpenAI's 722 maths papers explained, where Lean checked what humans could not, and through Memento 3 explained, another system that improves by rewriting its own programs against a fixed scorer.

How this was made: researched and written by an AI model (Claude) from the primary sources listed above, then checked claim-by-claim against those sources in a separate AI fact-check pass. Spotted an error? Email [email protected] and we correct it publicly. Our process.