A Forgotten 1980 Reversible Computer, and the AI That Just Cut Quantum Costs 17x

The Gate That Costs Forever: A Forgotten 1980 Reversible Computer, And The AI That Just Cut Quantum Circuit Costs Seventeenfold.

In February 1980, a researcher at the MIT Laboratory for Computer Science put a typed memo into the lab's technical series. It was numbered MIT/LCS/TM-151, it was titled "Reversible Computing," and its author was Tommaso Toffoli. The abstract opens with one plain sentence: "The theory of reversible computing is based on invertible primitives and composition rules that preserve invertibility."

A three-bit switch now carries his name. The Toffoli gate flips a target bit only when two control bits are both 1, and it can always be run backward. Today most serious cost estimates for quantum algorithms are written in Toffoli gates, plus the qubits needed at peak.

On October 15, 2026, four researchers posted a paper to arXiv showing that an AI model, working in a closed loop with an automatic checker, redesigned eight of those circuits. On seven of the eight tasks it cut both Toffoli count and qubit count below the best published designs. For elliptic-curve point addition, one new design uses 17 times fewer gates than the smallest previous circuit.

This free article covers the 1973 and 1980 story, the 2026 paper with its numbers checked, a SuperPrompt, a tested weekend build, ways to profit, and the risks.

1961 And 1973: The Price Of Forgetting

In 1961, Rolf Landauer of IBM argued in the IBM Journal of Research and Development that throwing information away has a physical price. As Charles Bennett later summarized it, about kT ln 2 of energy is a lower bound on the dissipation of a machine that discards a bit per step.

In November 1973, Bennett, also at IBM, published "Logical Reversibility of Computation" in the same journal. He showed that a general-purpose machine "may be made logically reversible at every step, while retaining their simplicity and their ability to do general computations."

His recipe has three stages. First, the machine runs the computation while it "saves all intermediate results, thereby avoiding the irreversible operation of erasure." Second, it prints the output. Third, it "reversibly disposes of all the undesired intermediate results by retracing the steps of the first stage in backward order."

Compute, copy the answer, uncompute. Quantum programmers live by that rule, because leftover scratch data in a quantum computer stays tangled with the answer and spoils it.

1980 And 1982: Toffoli's Gate And The Billiard Balls

Toffoli's 1980 memo built the theory into a toolkit of reversible parts. Under a physical interpretation, its abstract says, the central result is that "it is ideally possible to build sequential circuits with zero internal power dissipation." The controlled-controlled-NOT gate credited to Toffoli's 1980 work can build any reversible logic circuit.

In 1982, Edward Fredkin and Toffoli published "Conservative Logic," which includes the billiard-ball computer, an idealized machine where elastic balls bouncing off fixed walls carry out reversible logic.

I have been dumpster diving for forgotten computing papers for decades. Bennett's 1973 paper and Toffoli's 1980 memo have been sitting in the open literature the whole time.

Why does a 1980 gate still set the price? Toffoli gates need expensive extra resources in a fault-tolerant machine, so the paper notes their count "tracks a large part of the logical work and often the runtime." Saving scratch results costs qubits; recomputing them costs Toffolis. Bennett's compute-and-uncompute rule drives the daily budget fight of quantum design.

Eight Years Of Hand Work

Anthropic's public post gives a good example of how hard that fight has been. In 2017, researchers estimated that computing the ground-state energy of FeMoco, the iron-sulfur cluster bacteria use to turn nitrogen from the air into ammonia, would take about 50 trillion Toffoli gates. Through a series of redesigns, the estimate fell to about 340 million, roughly a 150,000-fold reduction. Anthropic notes that this took many research groups eight years.

The 2026 Paper: An AI In A Closed Loop

The paper is "Discovering state-of-the-art quantum circuits with large language models," by Andi Gu (Harvard and the Anthropic STEM Fellows Program), Alek H. Kemeny (Anthropic), Susanne F. Yelin (Harvard) and Mikhail D. Lukin (Harvard and QuEra Computing). Anthropic published its public account on October 16, and Technology.org covered it on October 19.

How it works:

1. Each task starts from a hand-written specification, with no implementation hints, and a blank program.

2. Claude Mythos 5 proposes several distinct "algorithm families," developed in parallel and sharing strong ideas from time to time.

3. Each candidate is a Python program that builds a circuit. An independent evaluator checks outputs, unchanged inputs, clean scratch qubits and phase, then scores it by TQ-cost: Toffoli count times peak qubit count.

4. The search runs on OpenEvolve, an open-source evolutionary coding agent, with MAP-Elites keeping good designs at different tradeoffs.

An ordinary computer can run the checker, since each test input is one bit string plus a phase. According to the paper, Claude worked from a blank program "without substantive human intervention." Anthropic adds that the elliptic-curve run lasted 53 hours, with human input limited to the initial brief and occasional prompts to think more broadly.

Three Tricks The AI Kept Finding

1. Conditional routing. A quantum circuit pays for every branch of an if-then. The discovered circuits swap the right data into place with cheap controlled swaps, run one shared expensive block, and swap back. In the paper's simple example this halves the Toffoli count.

2. Decoding the history. The new circuits often read past branch decisions back out of the numbers still in the registers, so far less history needs storing.

3. Spending the failure budget. Most quantum algorithms tolerate a tiny chance of failure, so circuit parts needed only for extremely rare inputs can go.

Store the history, or decode it. The AI kept choosing to decode.

Two Results In Detail

The first is a decoder for decoded quantum interferometry, or DQI, a quantum optimization method Anthropic calls one of the strongest candidates for a superpolynomial speedup. Per Google Quantum AI estimates that Anthropic cites, one benchmark problem would take about three months on the Frontier supercomputer and roughly an hour on a future quantum computer, mostly spent on Reed-Solomon decoding.

Khattar and colleagues' previous circuit used the extended Euclidean algorithm. Claude switched to Berlekamp-Massey, which the paper says cuts the core step from about 1.9 million Toffolis to about 140,000, then rebuilt most temporary values from the live state. The worst case would need 35 saved entries, or 665 qubits. Anthropic says Claude wrote a fast simulator and ran 403 million sample decodings, which showed that a second saved entry is needed only about once in 10,000 runs. So the circuit keeps one entry, 19 qubits, and accepts those rare failures inside the task's error allowance. The full decoder needs about 12 times fewer Toffolis than Google's earlier construction.

The second is elliptic-curve point addition on the curve y² = x³ + 7 over a 256-bit prime, the core step in quantum algorithms for the elliptic-curve discrete logarithm problem. Most of the cost is modular inversion. Claude built a reversible version of divsteps, a fast classical inversion method from Bernstein and Yang, by decoding most branch decisions from the live numbers. Anthropic reports that Claude proved new algebraic identities, checked the formula in large simulations, and formalized the claim in Lean, a proof assistant. Varying when to store and when to decode produced a family of designs. In Anthropic's words, compared with the smallest previous design, one circuit "uses 12% more qubits but 17x fewer gates."

The Results, Annotated

Numbers checked against the arXiv PDF. T is Toffolis, Q is peak qubits, gain is baseline TQ-cost over new TQ-cost.

Task Baseline (T, Q) Discovered (T, Q) Gain Note

---------------------------- ----------------------- -------------------- ----- -----------------------------

Reed-Solomon DQI decoder 5.1 million, 1,938 440,000, 1,837 12x vs Khattar et al. (Google)

Hermitian DQI decoder 100 million, 190,000 930,000, 2,395 n/a baseline is a naive version;

no prior compilation exists

HHL rotation angle 16,000, 300 1,348, 115 32x numerical function

Coulomb potential 6,355, 252 1,140, 142 9.9x numerical function

Fixed-point Gaussian 24,000, 362 1,583, 139 39x largest gain of the eight

Fe2S2 alias-Select 55,000, 139 15,000, 126 4.1x chemistry; exact on all inputs

Lattice-gauge simulation 1.3 million, 1,927 170,000, 1,859 7.7x nonabelian; exact on all inputs

Modular inversion several prior designs 4.0 million, 935 n/a new divsteps architecture

Point addition detail (paper Table S3) Toffolis Qubits

Schrottenloher 2026 (prior) 1.9 million 1,446

Luo et al. 2026 (prior, fewest qubits) 70 million 838

Divstep circuit (new) 4.0 million 935 Specialized Euclidean (new) 21 million 843

How to read it. The 17-times figure compares the divstep circuit with Luo and colleagues' 838-qubit design: 4.0 million against 70 million Toffolis, with about 12% more qubits. Against Schrottenloher's design, the divstep circuit uses about 35% fewer qubits and roughly twice the Toffolis, which is why the paper reports a new set of tradeoffs for this task and no single gain. The headline's seventeenfold is that gate-count cut. The biggest TQ gains were 39x and 32x.

What These Numbers Mean

These are resource estimates. The circuits were checked and counted on classical computers, and none of them has run on a quantum processor. Anthropic frames the work as bringing useful quantum computations "closer to the capabilities of real hardware."

The paper is a preprint. Technology.org reports that no outside group has reproduced the results yet. The Lean formalization comes from Anthropic's post, and the arXiv paper's text does not mention it, so as far as public sources show, no independent group has checked those proofs. Big tasks are checked by sampling: the elliptic-curve circuit allows up to 2 failures in 10,000 point additions, and 4 of 100,000 tests failed.

The authors list their own limits. TQ-cost weights time and space equally, and they note other objectives "are equally reasonable" depending on hardware. Tasks are fixed in one computational basis, which excludes tricks that change the encoding itself. Anthropic also reports that Claude was "conservative by nature" and leaned toward familiar methods, so the team required parallel families and sometimes prompted it to search more broadly.

Back in 2020 I wrote "A Quantum Computer Future." Cheaper circuits are one of the quiet ways that future arrives sooner.

The Crypto Angle, Calmly

Point addition sits inside quantum attacks on elliptic-curve signatures such as ECDSA, used across the web and in cryptocurrencies. Cheaper point addition lowers the bar for any future machine that tries. Anthropic published no attack estimate, and no such machine exists today.

Defenders have tools. In August 2024, NIST approved three post-quantum standards: FIPS 203 (ML-KEM) for key establishment, and FIPS 204 (ML-DSA) and FIPS 205 (SLH-DSA) for signatures. NIST's transition plan, IR 8547, still a draft, describes deprecating and removing quantum-vulnerable algorithms from its standards by 2035. The practical move is an orderly migration plan.

The Circuit-Evolve SuperPrompt

This SuperPrompt copies the paper's structure: separate algorithm families, an outside evaluator as ground truth, one cost score, and DISCOVERY notes that travel with each program. Treat every result as unproven until your evaluator passes it.

----- CIRCUIT-EVOLVE SUPERPROMPT ----- You are a reversible-circuit designer. Only the evaluator decides what is valid.

TASK: [paste a plain-language specification: inputs, outputs, exact behavior on every input, allowed failure rate, and which registers must be left unchanged]

GATES: X, CNOT, Toffoli (CCX), and controlled swaps built from them.

RULES: every scratch bit must return to 0 before it is freed. Inputs must be unchanged.

SCORE: Toffoli count x peak qubit count (TQ). Lower is better.

STEP 1, IDEATION: before writing code, propose three to five distinct algorithm families,

each a different way to compute the function. One short paragraph each. Merge any two

families that share the same main datapath.

STEP 2, BUILD: for each family, write one complete Python design function for the

evaluator interface pasted after this prompt. Return the full program every time.

STEP 3, IMPROVE: when evaluator output arrives, rewrite only the named family's program

to lower TQ. Try three moves first: route data with controlled swaps so one shared block

does the expensive work; recover branch decisions from register contents during

uncompute in place of storing them; and, only if a failure budget is allowed, drop

machinery used by rare inputs and state the failure rate you expect.

STEP 4, NOTES: end every answer with up to three lines starting with DISCOVERY: that

record what you learned. They will be pasted back next round.

----- END -----

----- BROADEN-SEARCH NUDGE -----

Your last several rewrites were small variations of one family. Set them aside. Propose

one genuinely different algorithm for this task, using a method from another area of

mathematics or classical computing, and build it from a blank program.

----- END ----- The nudge copies Anthropic's occasional prompts to think more broadly.

A Weekend Build: A Toffoli Evaluator On Your Laptop

You need only Python 3. The script is a tiny evaluator in the spirit of the paper's: it tests a circuit on every input, rejects any design that leaves a scratch bit dirty, and prints Toffoli count, peak qubits and TQ. The sample task borrows the routing idea at bit scale: for each of four positions, flip target bit t when control bit c is 1 and the selected input is 1, where select bit b picks register z when 1 and register y when 0.

Status: the evaluator and three sample designs were run for this article on October 19, 2026, producing the output shown. The AI loop in steps 3 to 6 is an untested outline.

import itertools

class B:

def __init__(s): s.ops, s.live, s.peak, s.n = [], 0, 0, 0

def alloc(s, k=1):

ids = list(range(s.n, s.n + k)); s.n += k

s.live += k; s.peak = max(s.peak, s.live)

s.ops += [("alloc", i) for i in ids]; return ids

def free(s, q): s.ops.append(("free", q)); s.live -= 1

def x(s, a): s.ops.append(("x", a))

def cx(s, a, t): s.ops.append(("cx", a, t))

def ccx(s, a, b, t): s.ops.append(("ccx", a, b, t))

def cswap(s, c, a, b): # Fredkin gate = 1 Toffoli + 2 CNOTs

s.cx(b, a); s.ccx(c, a, b); s.cx(b, a)

def run(b, bits):

v = dict(bits)

for op in b.ops:

k = op[0]

if k == "alloc": v[op[1]] = 0

elif k == "free":

if v[op[1]]: return None # dirty scratch bit: reject

elif k == "x": v[op[1]] ^= 1

elif k == "cx": v[op[2]] ^= v[op[1]]

elif k == "ccx": v[op[3]] ^= v[op[1]] & v[op[2]]

return v

def evaluate(design, n=4):

b = B(); bb = b.alloc(1)[0]; c, y, z, t = (b.alloc(n) for _ in range(4))

b.ops = [] # inputs carry data; skip their zero reset

design(b, bb, c, y, z, t, n)

T = sum(op[0] == "ccx" for op in b.ops)

for vals in itertools.product((0, 1), repeat=1 + 4 * n):

bits = dict(zip([bb] + c + y + z + t, vals))

out = run(b, bits)

if out is None: return f"INVALID: ancilla not returned to 0 (T={T}, Q={b.peak})"

for i in range(n):

sel = bits[z[i]] if bits[bb] else bits[y[i]]

if out[t[i]] != bits[t[i]] ^ (bits[c[i]] & sel): return "INVALID: wrong output"

if any(out[q] != bits[q] for q in [bb] + c + y + z): return "INVALID: input changed"

return f"VALID T={T} Q={b.peak} TQ={T * b.peak}"

def naive(b, bb, c, y, z, t, n): # one controlled block per branch

for i in range(n):

a = b.alloc(1)[0]

b.ccx(bb, z[i], a); b.ccx(a, c[i], t[i]); b.ccx(bb, z[i], a)

b.x(bb)

b.ccx(bb, y[i], a); b.ccx(a, c[i], t[i]); b.ccx(bb, y[i], a)

b.x(bb); b.free(a)

def dirty(b, bb, c, y, z, t, n): # skips the uncompute step: must be rejected

for i in range(n):

b.cswap(bb, y[i], z[i]); a = b.alloc(1)[0]

b.ccx(y[i], c[i], a); b.cx(a, t[i]); b.free(a)

b.cswap(bb, y[i], z[i])

def routed(b, bb, c, y, z, t, n): # swap in, one shared Toffoli, swap back

for i in range(n):

b.cswap(bb, y[i], z[i]); b.ccx(y[i], c[i], t[i]); b.cswap(bb, y[i], z[i])

for name, d in [("naive", naive), ("dirty", dirty), ("routed", routed)]:

print(f"{name:7s}", evaluate(d))

Output from the test run:

naive VALID T=24 Q=18 TQ=432

dirty INVALID: ancilla not returned to 0 (T=12, Q=18)

routed VALID T=12 Q=17 TQ=204

Routing halves Toffolis, saves a qubit and cuts TQ 2.1 times. The dirty design shows Bennett's rule enforced by code.

The weekend plan:

1. Save the script as toffoli_eval.py, run it, and confirm the three lines above.

2. Freeze your tests. Where trying every input is too slow, write 20 fixed test inputs, edge cases included, before searching.

3. Pick a small task, such as a 4-bit reversible incrementer, and write a plain-language specification.

4. Give your AI model the SuperPrompt, the specification and the evaluator interface. Run each design and paste the output back.

5. After about five rounds of small changes, send the nudge.

6. Log every valid design with its T, Q and TQ to map your own small frontier.

Ways To Profit From Cheaper Circuits

None of this is financial advice. These are possibilities to research and test on your own terms.

1. Circuit-cost consulting. Anthropic notes that hand redesigns typically took months per step. Someone who can run evaluator-guided search and explain Toffoli-qubit tradeoffs has a useful skill to offer.

2. Post-quantum migration literacy. Many businesses have no list of where they use elliptic-curve or RSA cryptography. Helping a firm build that inventory and plan an orderly move to ML-KEM and ML-DSA is calm, practical work whatever the hardware timeline.

3. Verified circuit libraries as data products. Small reversible circuits shipped with evaluators, test inputs and T and Q counts are high-quality data for coding agents. I laid out how to get paid when AI agents buy your data in my July 11 guide to x402 payments, and a verified circuit pack could be one such product, within the licenses of anything you build on.

4. A research watchlist. Follow neutral-atom hardware companies such as QuEra, open quantum-compiler and resource-estimation tools, and post-quantum cryptography vendors. Do your own research before any decision.

Risks To Keep In View

1. No hardware speedup yet. These are counts from classical simulators. Say so whenever you share them.

2. Not yet reproduced. The paper is a preprint; outside review is still ahead.

3. Proofs need auditors. Treat the Lean work as pending until independent experts confirm the formal statement matches the claim.

4. Evaluators can be gamed. Search optimizes exactly what you score, and sampled tests can miss rare failures. Freeze test sets and check exhaustively where you can.

5. The score is a choice. Real machines may weight qubits and Toffolis differently, which can change the best design.

6. Keep the crypto story factual. Cheaper point addition is a reason to migrate on schedule.

The Gate That Keeps Its Promise

In 1973, Charles Bennett showed that a computer can keep every step and walk itself back to a clean slate. In 1980, Tommaso Toffoli built a toolkit around a three-bit gate. Forty-six years later, an AI model working against an honest evaluator found ways to keep fewer of those steps, making key quantum routines many times cheaper on paper.

Run the evaluator this weekend and watch your Toffoli count fall.

References

1. Andi Gu, Alek H. Kemeny, Susanne F. Yelin and Mikhail D. Lukin, "Discovering state-of-the-art quantum circuits with large language models," arXiv:2610.22367v1, October 15, 2026. https://arxiv.org/abs/2610.22367

2. Anthropic, "Designing more efficient quantum circuits with Claude," October 16, 2026. https://www.anthropic.com/research/designing-efficient-quantum-circuits

3. Vytautas Valinskas, "Claude Mythos 5 Trims Quantum Circuit Gate Counts," Technology.org, October 19, 2026. https://www.technology.org/2026/10/19/claude-quantum-circuits-point-addition-dqi-decoder/

4. Charles H. Bennett, "Logical Reversibility of Computation," IBM Journal of Research and Development 17(6):525-532, November 1973. https://doi.org/10.1147/rd.176.0525

5. Bennett 1973, open text. https://www.cs.princeton.edu/courses/archive/fall04/cos576/papers/bennett73.html

6. Tommaso Toffoli, "Reversible Computing," MIT/LCS/TM-151, February 1980. https://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TM-151.pdf

7. Rolf Landauer, "Irreversibility and Heat Generation in the Computing Process," IBM Journal of Research and Development 5(3):183-191, 1961. https://doi.org/10.1147/rd.53.0183

8. Edward Fredkin and Tommaso Toffoli, "Conservative Logic," International Journal of Theoretical Physics 21:219-253, 1982. https://www.cs.princeton.edu/courses/archive/fall06/cos576/papers/fredkin_toffoli82.pdf

9. Toffoli gate, Wikipedia. [https://en.wikipedia.org/wiki/Toffoli_gate](https://en.wikipedia.org/wiki/Toffoli_gate)

10. Billiard-ball computer, Wikipedia. [https://en.wikipedia.org/wiki/Billiard-ball_computer](https://en.wikipedia.org/wiki/Billiard-ball_computer)

11. NIST, "Announcing Approval of Three Federal Information Processing Standards (FIPS) for Post-Quantum Cryptography," August 13, 2024. https://www.nist.gov/news-events/news/2024/08/announcing-approval-three-federal-information-processing-standards-fips

12. NIST Post-Quantum Cryptography project page, including the IR 8547 transition timeline. https://csrc.nist.gov/Projects/post-quantum-cryptography/

13. NIST IR 8547 initial public draft, "Transition to Post-Quantum Cryptography Standards," November 2024. https://nvlpubs.nist.gov/nistpubs/ir/2024/NIST.IR.8547.ipd.pdf

14. "A Quantum Computer Future." ReadMultiplex, October 21, 2020. https://readmultiplex.com/2020/10/21/a-quantum-computer-future/

15. "x402 Payments: How To Get Paid For Your Data By Selling It To AI Agents. The New Agentic Economy," ReadMultiplex, July 11, 2026. https://readmultiplex.com/2026/07/11/x402-payments-how-to-get-paid-for-your-data-by-selling-it-to-ai-agents-the-new-agentic-economy/

source & further reading

x.com — original article