Claude designs more efficient quantum circuits

The task

Qubits and runtime are both scarce on quantum computers, so algorithms have to be compiled into circuits that use as few qubits and gates as possible. The Toffoli gate is among the most expensive operations, which makes the Toffoli count the standard runtime estimate.

Anthropic gave Claude eight such tasks from chemistry, optimisation, physics simulation and number theory as plain-language specifications. It also got an automated evaluator that checks correctness and scores designs by qubits multiplied by gates. Claude worked in a closed loop: propose, receive a score, improve, with no human input between rounds (Anthropic).

The work was led by Andi Gu in Anthropic's STEM Fellows Program, mentored by Alek Kemeny, with Susanne Yelin and Mikhail Lukin (Harvard, QuEra). Details are in an arXiv paper (arXiv).

Source: Anthropic. Toffoli count versus peak qubits on seven tasks. Grey x: best previously published design; orange dot: Claude's design. The eighth task, point addition, is compared in a table in the paper.

Elliptic curves: a 53-hour run

The first task was elliptic-curve point addition, the step that dominates the cost of quantum algorithms for the elliptic-curve discrete logarithm, the ones that threaten ECC. The expensive part is modular inversion. Classical computers do this well with divsteps, but a quantum circuit must stay reversible, so a direct port has to store every branch decision, which costs a huge number of qubits.

After 53 hours with minimal human input, Claude found that this history does not need to be stored: it can be decoded from the pair of numbers after each step. It proved new algebraic identities to get there, then checked the formula with large simulations and formally in Lean. One design in the resulting family uses 12% more qubits than the smallest previous design but 17x fewer gates.

A faster decoder for DQI

Decoded quantum interferometry (DQI) is one of the strongest candidates for a quantum optimisation speedup, and its most expensive step is a Reed–Solomon decoder. Google Quantum AI estimates imply one target problem would take about three months on the Frontier supercomputer versus roughly an hour on a future quantum computer running DQI, most of it spent decoding.

Claude replaced the extended Euclidean algorithm with Berlekamp–Massey decoding, which runs the same kind of step a fixed number of times. It reconstructs most temporary values instead of storing them. Reserving for the worst case would have taken 665 qubits, but Claude ran 403 million simulated decodings and found that one saved value, 19 qubits, almost always suffices. About one run in 10,000 fails, within the task's error budget. The result needs 12x fewer gates than Google's prior construction.

Limitations

Anthropic says Claude was overly cautious early on, re-checking well-supported results and favouring familiar approaches. The setup therefore required it to develop several different approaches in parallel, and researchers occasionally prompted it to search more broadly.

These are the company's own results. The paper is public, independent checks are still to come. For scale: estimates for simulating the FeMoco enzyme fell from 50 trillion to 340 million Toffoli gates over eight years of work by many groups. Claude's elliptic-curve design came out of a single 53-hour run.