Design Patterns for Optimizing Quantum Circuits, Dispatch 2

01 / THE SHORT VERSION

When qubits run out, every helper has to earn its place.

Dispatch 1 collected twenty-six rewrites that mostly remove Toffoli gates. This one follows a different race. On ecdsa.fail, next to the main leaderboard, contestants have been competing on a second number: the fewest qubits on which one elliptic-curve point addition can be done at all.

At the start of November that number was 660. By 11 November it was 647. Of those 647 qubits, 640 hold data: two 256-bit coordinates and a 128-bit working word. The rest are six helper qubits and one sign bit, and the whole race is over those last few.

Reading the entries, the same moves come up again and again. This dispatch collects thirty-one of them as patterns P27 to P57: a small block of circuit, a replacement, and the conditions under which the swap is safe. Many go the opposite way from Dispatch 1: they pay Toffolis to free a qubit.

Each pattern has an animated before and after, the same block in Qiskit, a plain statement of what it does to every cost function, and a proof checked by the Lean theorem prover. If Toffoli counts, measured erasure or the scoreboards are new to you, the first three sections of Dispatch 1 explain them.

02 / THE RACE

A qubit is removed at a high price, and then most of the price is won back.

ecdsa.fail scores a circuit by its mean Toffoli count times its peak qubit count. The best scores belong to wide, short circuits: about 1,200 qubits and under a million Toffolis. The narrow circuits are a different kind of object: about 650 qubits and hundreds of millions of Toffolis. On score they lose by a factor of several hundred, and the site marks them as rejected. It still measures them, and a second, unofficial race has formed around width alone.

The figure shows the last eleven widths. A ring marks the first entry to reach a width, and a filled dot marks the cheapest entry at that width today. The rhythm repeats: someone takes a qubit out at a cost of tens of millions of Toffolis, then the arithmetic is rebuilt for the new width and the cost falls back.

FIG. 1 / TOFFOLIS AT EACH WIDTH, 657 DOWN TO 647 QUBITS. HOVER OR TAP A COLUMN.

FIRST ENTRY AT THIS WIDTHCHEAPEST ENTRY TODAYMEAN EXECUTED TOFFOLIS, MILLIONS · STANDINGS OF 12 NOV 2026

THE SAME NUMBERS AS A TABLE

Qubits	First entry	By	Cheapest today	By
657	429.9M	nasqret, 9 Nov	429.9M	nasqret
656	415.4M	nasqret, 9 Nov	405.4M	RealAdii
655	416.6M	nasqret, 9 Nov	405.6M	RealAdii
654	439.7M	nasqret, 9 Nov	439.7M	nasqret
653	477.7M	nasqret, 10 Nov	420.1M	RealAdii
652	548.5M	jackylee0424, 10 Nov	475.4M	nasqret
651	608.5M	jackylee0424, 10 Nov	464.1M	nasqret
650	753.2M	Akashneelesh, 10 Nov	459.3M	RealAdii
649	658.7M	jackylee0424, 10 Nov	474.3M	RealAdii
648	713.6M	jackylee0424, 11 Nov	387.6M	RealAdii
647	808.1M	jackylee0424, 11 Nov	802.0M	almond-lab

At 648 qubits the rebuild has gone furthest: under 390 million Toffolis, fewer than any wider circuit in the figure. At 647 it has not happened yet.

The cheapest 647-qubit entry is ours, and it shows where gate-level rewriting ends. It is jackylee0424's construction with two automatic passes over the finished gate list: RealAdii's peephole, and the cancel and merge rules from Part 2 of Dispatch 1. Together they bring 808.1 million Toffolis down to 802.0 million, less than 1%. The next real step at that width will be a rebuild, not a rewrite.

03 / ONE WIRE AT A TIME

Where each removed qubit came from.

Every entry comes with a public note, and the notes say what was removed at each step. The table lists the steps whose notes we reviewed, with the Toffoli count of the first entry at the new width. It is not complete. Pattern numbers point to the sections below.

FIG. 2 / HOW THE WIDTH CAME DOWN, FROM THE AUTHORS' NOTES.

STEPFIRST BYWHAT WAS REMOVEDTOFFOLIS ON ARRIVAL

676 → 675odinfree, 19 OctOne lane of a ring dropped; the carry is read out of the middle of a sweep (P37).596.1M

666 → 660bulengerk, 21 to 22 OctSize codes, a payload cell left out where it is provably zero, and carry loans (P51 among others).545.4M

660 → 659odinfree, 8 NovA scratch role removed: every multi-controlled gate borrows busy lanes (P27).579.1M

659 → 658jackylee0424, 8 NovOne lane evicted from every operation, then dropped.630.2M

657 → 653nasqret, 9 to 10 NovOne helper per step moved onto a bit known to be one, or onto a pad that is provably zero.429.9M to 477.7M

653 → 651jackylee0424, 10 NovCounter and rank bits hosted on idle wires or wires of known value (P41 among others).548.5M, then 608.5M

651 → 650Akashneelesh, 10 Nov; jackylee0424 the same afternoonA counter bit parked, window by window, on lanes whose value is known.753.2M; 632.4M

650 → 649jackylee0424, 10 NovA tag relayed through zeros that the division itself creates.658.7M

649 → 648jackylee0424, 11 Nov; Akashneelesh six hours laterIn Akashneelesh's entry, five small helper wires removed (P34 among others).713.6M; 674.9M

648 → 647jackylee0424, 11 NovThe helper bank cut from seven clean qubits to six.808.1M

Two things stand out. Almost every step stores a bit somewhere that already exists: a wire known to be zero, a wire known to be one, or a qubit that is busy but can be borrowed. And every step has a price in Toffolis. It pays only because the freed qubit sets the circuit's peak width, and it would pay double on a score that squares the qubit count, as the Kaggle DQI task does.

04 / PART 1 · BORROW A BUSY QUBIT

A qubit that is in use can still serve as scratch.

When no clean qubit is left, a product can live on a qubit that is busy holding something else, as long as the block that reads it runs twice. Whatever the qubit held cancels between the two runs. The six patterns here are that one idea at several scales: a single gate, half an adder, a rotation, a pair of toggles, and the guard of a block used as its own scratch.

The code under each figure is Qiskit, as in Dispatch 1. Each snippet is the smallest instance that shows the idea, so its size can differ from the figure above it. Every before and after pair was simulated against each other.

P27 / BORROW A BUSY QUBIT

Borrow a busy qubit: toggle twice

A product of three bits, x ^= a·b·c, needs a scratch qubit to hold a·b on the way. At the circuit's widest point there is no clean qubit left to give it.

Use any busy qubit l instead, whatever it holds. Write a·b onto it, read it into x, write a·b again, read again. The two reads see d and d XOR a·b, so the unknown value d cancels and only the product arrives in x. The busy qubit ends as it started.

Before: A clean scratch qubit, erased by measurement, 2. After: A busy qubit, toggled twice, 4 (toffolis per product · clean qubits 1 → 0).

Toffolis: Higher. 2 → 4 per three-way product.
Qubits: Lower. One clean qubit fewer.
Toffoli × qubit scores: Depends. Pays only where that clean qubit sets the peak width.
Q² × Toffoli (DQI): Depends. Same test, and a peak qubit is worth twice as much.

from qiskit import QuantumCircuit

def before():  # x ^= a b c with a clean scratch t
    a, b, c, x, loan, t = range(6)
    qc = QuantumCircuit(6, 1)
    qc.ccx(a, b, t)
    qc.ccx(t, c, x)
    qc.h(t); qc.measure(t, 0); qc.reset(t)
    with qc.if_test((qc.clbits[0], 1)):
        qc.cz(a, b)
    return qc

def after():  # no clean qubit: borrow a busy one
    a, b, c, x, loan, t = range(6)
    qc = QuantumCircuit(6)
    qc.ccx(a, b, loan)  # loan holds d XOR ab
    qc.ccx(loan, c, x)
    qc.ccx(a, b, loan)  # loan holds d again
    qc.ccx(loan, c, x)  # the two reads differ by ab
    return qc

NEEDS: l is none of a, b, c, x, and nothing else touches l during the four gates
SEEN IN: Barenco et al. (1995). In ecdsa.fail, nasqret's 654-qubit step rewrites every clean product of three this way by matching the emitted gate list; odinfree's 824-qubit row uses the phase form to drop the one clean lane that set the peak
PROOF: QCP.P27.toggle_twice and .phase_toggle_twice, any wires

P33 / BORROW A BUSY QUBIT

The controlled half of an adder on one borrowed selector

The second half of a controlled adder writes the sum bits: b[i] ^= f·a[i] for every bit, where f is an AND of the controls. Normally f sits on a clean helper for the whole half.

This is P27 at the scale of a whole block. Do every write once with a busy wire d as the control, flip d by f, and do every write again. The carry-undo gates in between must not notice the first write, so each sum bit is masked with a CNOT first and unmasked at the end.

Before: The control f held on a clean helper, n + 2. After: Every write done twice around a busy wire, 2n + 2 (toffolis, n-bit half · clean helpers 1 → 0).

Toffolis: Higher. n + 2 → 2n + 2 for an n-bit half. Putting every write through a borrowed ladder instead would cost n(4m−4) for m controls.
Qubits: Lower. No clean helper.
Toffoli × qubit scores: Depends. Pays where the helper would set the peak.
Q² × Toffoli (DQI): Depends. Same test; the qubit counts twice.

from qiskit import QuantumCircuit
A, B, K1, K2, D, H = [0, 1, 2], [3, 4, 5], 6, 7, 8, 9
# second half of a controlled adder: b_i ^= (k1 AND k2) * a_i,
# interleaved with the carry-undo gates CCX(a_i, b_i, a_i+1)

def before():  # needs a clean helper h
    qc = QuantumCircuit(10)
    qc.ccx(K1, K2, H)
    qc.ccx(H, A[2], B[2])
    qc.ccx(A[1], B[1], A[2]); qc.ccx(H, A[1], B[1])
    qc.ccx(A[0], B[0], A[1]); qc.ccx(H, A[0], B[0])
    qc.ccx(K1, K2, H)
    return qc

def after():  # d is borrowed: any value, restored
    qc = QuantumCircuit(10)
    for i in range(3):
        qc.ccx(D, A[i], B[i])  # first write, with d
        # pre-mask: carries will not notice
        if i < 2: qc.cx(D, B[i])
    qc.ccx(K1, K2, D)  # d becomes d XOR f
    qc.ccx(D, A[2], B[2])  # second write
    for i in (1, 0):
        # carry undo sees its original product
        qc.ccx(A[i], B[i], A[i + 1])
        qc.ccx(D, A[i], B[i])
    qc.ccx(K1, K2, D)
    qc.cx(D, B[0]); qc.cx(D, B[1])  # remove the mask
    return qc

NEEDS: d is outside a, b and the controls; the controls are not written inside the half
SEEN IN: nasqret, ecdsa.fail (sharedRippleTail)
PROOF: QCP.P33.correct, 3 bits, two controls, every value of d

P29 / BORROW A BUSY QUBIT

Controlled rotation as two reflections on one borrowed selector

Rotate five wires by one place when a predicate f, an AND of two controls, holds. Built from four swaps that each carry both controls, it costs 16 Toffolis.

A rotation is two reflections, and a reflection is a layer of swaps on separate pairs. For one layer L and any busy wire d: apply L if d, flip d by f, apply L if d again. The net effect is L exactly when f holds, whatever d held. Two such sandwiches make the rotation and return d to its value.

Before: Four swaps, each with both controls, 16. After: Two reflections around a busy wire, 10 (toffolis, 5 wires, 2 controls).

Toffolis: Lower. 16 → 10 for five wires and two controls: 2 per swap plus two evaluations of f.
Qubits: Same. No clean qubit in either form.
Toffoli × qubit scores: Lower. Toffolis fall, width is untouched.
Q² × Toffoli (DQI): Lower. Same Toffoli gain.

from qiskit import QuantumCircuit
# rotate W by one place if K1 AND K2
W, K1, K2, D = [0, 1, 2, 3, 4], 5, 6, 7
# two reflections
FIRST, SECOND = [(1, 4), (2, 3)], [(0, 4), (1, 3)]

def before():  # four swaps, each under both controls
    qc = QuantumCircuit(8)
    for x, y in [(1, 4), (2, 3), (0, 4), (1, 3)]:
        qc.cx(W[x], W[y]); qc.mcx([K1, K2, W[y]], W[x]); qc.cx(W[x], W[y])
    return qc

# swap each pair if the selector is 1
def layer(qc, pairs):
    for x, y in pairs:
        qc.cswap(D, W[x], W[y])

def after():  # D is borrowed: any value, restored
    qc = QuantumCircuit(8)
    layer(qc, FIRST); qc.ccx(K1, K2, D); layer(qc, FIRST)
    layer(qc, SECOND); qc.ccx(K1, K2, D); layer(qc, SECOND)
    return qc

NEEDS: d is outside the word and the controls; the predicate does not read the rotated wires
SEEN IN: nasqret, ecdsa.fail (sharedControlledPermutation): on the rotations of the lower Euclid kernels it removed 16.7M of 480.9M Toffolis at 651 qubits (their count)
PROOF: QCP.P29.correct, 5 wires, all inputs, both values of d

P51 / BORROW A BUSY QUBIT

Two triply controlled toggles as a four-Toffoli commutator

Two toggles in a row: e ^= w·x·t, then t ^= w·x·e. Each has three controls, so the pair needs a helper to hold w·x, or a borrowed wire at 4 Toffolis per toggle.

Run B, A, B, A with B = Toffoli(x, e → t) and A = Toffoli(w, t → e). If w or x is 0, one of the two gates drops out and the other appears twice and cancels. If both are 1, the four gates act as CNOTs and compose to exactly the two toggles.

Before: A helper holds w·x, 1. After: B A B A, no helper, 0 (helper qubits · 4 toffolis either way).

Toffolis: Same. 4 with a clean helper, 4 without. On a borrowed wire the pair would cost 8.
Qubits: Lower. No helper and no borrowed wire.
Toffoli × qubit scores: Lower. One qubit off the peak at no Toffoli price.
Q² × Toffoli (DQI): Lower. The freed qubit counts twice.

from qiskit import QuantumCircuit

def before():  # e ^= w x t ; t ^= w x e, clean helper h
    w, x, e, t, h = range(5)
    qc = QuantumCircuit(5)
    qc.ccx(w, x, h)
    qc.ccx(h, t, e)
    qc.ccx(h, e, t)
    qc.ccx(w, x, h)
    return qc

def after():  # no helper: a commutator B A B A
    w, x, e, t, h = range(5)
    qc = QuantumCircuit(5)
    qc.ccx(x, e, t)  # B
    qc.ccx(w, t, e)  # A
    qc.ccx(x, e, t)  # B
    qc.ccx(w, t, e)  # A
    return qc

NEEDS: w, x, e and t are four different wires
SEEN IN: bulengerk, ecdsa.fail 660-qubit entry (maj_virtual_leading.rs)
PROOF: QCP.P51.correct, all inputs

P52 / BORROW A BUSY QUBIT

The guard of a block as its own clean scratch

A block is guarded by g: every gate in it is controlled by g. Around it, V writes a predicate of k controls into a cache wire and V⁻¹ removes it. With only a busy wire for scratch, V costs 4k−8 Toffolis each time.

Use the guard itself, complemented, as V's clean scratch. When g = 1 the scratch really is 0 and V is correct. When g = 0, V writes something wrong, but the block does nothing and V⁻¹ removes exactly what V wrote.

Before: Predicate built on a busy wire, 4k−8. After: The guard is the clean scratch, 2k−3 (toffolis per predicate write, k controls).

Toffolis: Lower. 4k−8 → 2k−3 for each write of the predicate.
Qubits: Same. No extra wire in either form.
Toffoli × qubit scores: Lower. Toffolis fall, width is untouched.
Q² × Toffoli (DQI): Lower. Same Toffoli gain.

from qiskit import QuantumCircuit
# cache w ^= c0 c1 c2 around a block guarded by g
C0, C1, C2, W, G, Y, H = range(7)

# 3-control toggle with clean scratch s
def ladder(qc, s):
    qc.ccx(C0, C1, s); qc.ccx(s, C2, W); qc.ccx(C0, C1, s)

def before():  # a separate clean scratch h
    qc = QuantumCircuit(7)
    ladder(qc, H)
    # the block: every gate controlled by g
    qc.ccx(G, W, Y)
    ladder(qc, H)
    return qc

def after():  # the guard itself is the scratch
    qc = QuantumCircuit(7)
    # g = 1: scratch is 0, the write is right
    qc.x(G); ladder(qc, G); qc.x(G)
    # g = 0: the write is wrong, but unused
    qc.ccx(G, W, Y)
    # ... and removed again
    qc.x(G); ladder(qc, G); qc.x(G)
    return qc

NEEDS: The block does not change g or V's controls; nothing else reads the cache between V and V⁻¹
SEEN IN: mochimodev and bulengerk, ecdsa.fail 794-qubit lane. The ladder is from Khattar and Gidney (2024)
PROOF: QCP.P52.correct, three controls, all inputs

P56 / BORROW A BUSY QUBIT

Two borrowed-wire gadgets that share a stage lose two Toffolis

Two toggle-twice gadgets (P27) in a row use the same busy wire and the same pair of controls. Written T U₁ T U₁ and then T U₂ T U₂, they cost 8 Toffolis.

A gadget works equally well written U T U T. Write the first one that way round: U₁ T U₁ T, then T U₂ T U₂. Two copies of T now sit next to each other and cancel.

Before: T U₁ T U₁, then T U₂ T U₂, 8. After: U₁ T U₁, then U₂ T U₂, 6 (toffolis per pair of gadgets).

Toffolis: Lower. 8 → 6 per pair of gadgets.
Qubits: Same. The same busy wire.
Toffoli × qubit scores: Lower. Toffolis fall, width is untouched.
Q² × Toffoli (DQI): Lower. Same Toffoli gain.

from qiskit import QuantumCircuit
# D is a borrowed wire in any state
C1, C2, D, X1, T1, X2, T2 = range(7)

def before():  # two borrowed-wire toggles, as emitted
    qc = QuantumCircuit(7)
    for x, t in ((X1, T1), (X2, T2)):
        qc.ccx(C1, C2, D); qc.ccx(D, x, t)  # T U
        qc.ccx(C1, C2, D); qc.ccx(D, x, t)  # T U
    return qc

def after():  # write the first one as U T U T
    qc = QuantumCircuit(7)
    # U1 T U1 (T ...
    qc.ccx(D, X1, T1); qc.ccx(C1, C2, D); qc.ccx(D, X1, T1)
    # ... T) U2 T U2
    qc.ccx(D, X2, T2); qc.ccx(C1, C2, D); qc.ccx(D, X2, T2)
    return qc

NEEDS: T commutes with whatever lies between the two gadgets
SEEN IN: RealAdii, ecdsa.fail (peephole.rs, detect_gadget): part of the pass that took the 650-qubit circuit to 459.3M Toffolis
PROOF: QCP.P56.correct, all inputs and any value on the borrowed wire

05 / PART 2 · HOST AND FREE WIRES

The narrow circuits are won one wire at a time.

Each of these seven removes a helper outright: an enable flag, a spare lane, a transfer wire, two search flags, a temporary, or a value that was being held when it could be recomputed or packed more densely.

Three of them (P39, P43 and P49) rest on a promise about the surrounding algorithm, such as "this position is always zero". The Lean proof then covers the promised inputs, and the promise itself still has to be proved for the circuit that uses the pattern.

P34 / HOST AND FREE WIRES

Drop an enable wire: a counter threshold as disjoint cubes

A block must run only while a counter s is above a constant i. The usual way computes the flag e = [s > i] onto a helper and holds it for the whole block.

Split the test into cases that cannot overlap: for each zero bit j of i, the case "s has a 1 at bit j and matches i on every bit above j". Control each gate of the block on each case directly. At most one case is true, so each gate fires at most once, and no flag is stored.

Before: Hold the flag e on a helper, 3. After: One gate per case, no flag, 5 (toffolis, 2-bit counter · helper qubits 1 → 0).

Toffolis: Higher. The block is repeated once per zero bit of i, with wider controls: 3 → 5 in the proved instance.
Qubits: Lower. The enable wire is gone.
Toffoli × qubit scores: Depends. Pays where the enable wire would set the peak.
Q² × Toffoli (DQI): Depends. Same test; the qubit counts twice.

from qiskit import QuantumCircuit

def before():  # t ^= u if the counter s > 0
    s0, s1, u, t, loan, e = range(6)
    qc = QuantumCircuit(6)
    # e = [s > 0]
    qc.x([s0, s1]); qc.ccx(s0, s1, e); qc.x(e); qc.x([s0, s1])
    qc.ccx(e, u, t)
    qc.x([s0, s1]); qc.x(e); qc.ccx(s0, s1, e); qc.x([s0, s1])
    return qc

def after():  # no enable wire: one gate per cube
    s0, s1, u, t, loan, e = range(6)
    qc = QuantumCircuit(6)
    qc.ccx(s1, u, t)  # cube: s1 = 1
    qc.x(s1)  # cube: s1 = 0 and s0 = 1
    # three controls through a
    qc.ccx(s0, s1, loan); qc.ccx(loan, u, t)
    # borrowed wire (P27)
    qc.ccx(s0, s1, loan); qc.ccx(loan, u, t)
    qc.x(s1)
    return qc

NEEDS: The block never writes s. The wider controls use a borrowed wire (P27)
SEEN IN: Akashneelesh, ecdsa.fail 648-qubit entry (p648-power.cjs)
PROOF: QCP.P34.correct, 2-bit counter, i = 0

P37 / HOST AND FREE WIRES

Read a carry from the middle of an in-place ripple

An in-place adder sweep leaves each carry on a wire of s, but only for a moment: the next cell XORs the next bit of s into it. To read a carry out, the lane above it had to be kept empty.

Before the sweep, copy the next bit onto a witness wire w. After the sweep the carry wire holds carry XOR that bit, so reading it into e and then reading w leaves exactly the carry. Undo the sweep and the copy.

Before: The lane above the carry is kept empty, 1. After: Save the next bit on a witness, take it back out, 0 (lanes kept empty for the read · toffolis unchanged).

Toffolis: Same. Two more CNOTs, which are free.
Qubits: Lower. One lane fewer; the witness comes from scratch that already exists.
Toffoli × qubit scores: Lower. One qubit off the peak at no Toffoli price.
Q² × Toffoli (DQI): Lower. The freed qubit counts twice.

from qiskit import QuantumCircuit
T, S, E, C0, W, K = [0, 1, 2], [3, 4, 5], 6, 7, 8, 9
# e ^= carry into lane 2 of t + s

def before():  # separate carry wire k
    qc = QuantumCircuit(10)
    qc.ccx(T[0], S[0], K)  # carry out of lane 0
    qc.cx(K, T[1]); qc.cx(K, S[1])
    # majority(t1, s1, k)
    qc.ccx(T[1], S[1], E); qc.cx(K, E)
    qc.cx(K, S[1]); qc.cx(K, T[1])
    qc.ccx(T[0], S[0], K)
    return qc

# in-place MAJ cells: carries live in s
def sweep(qc, back=False):
    cells = [(S[0], T[0], C0), (S[1], T[1], S[0]), (S[2], T[2], S[1])]
    for s, t, x in (reversed(cells) if back else cells):
        if back: qc.ccx(x, t, s); qc.cx(s, x); qc.cx(s, t)
        else:    qc.cx(s, t); qc.cx(s, x); qc.ccx(x, t, s)

def after():  # read the carry out of the sweep
    qc = QuantumCircuit(10)
    qc.cx(S[2], W)  # witness: save s2
    sweep(qc)  # now s1 = carry XOR (old s2)
    # read, and take s2 back out
    qc.cx(S[1], E); qc.cx(W, E)
    sweep(qc, back=True)
    qc.cx(S[2], W)  # witness returns to 0
    return qc

NEEDS: w is clean and outside t and s; the copied bit is unchanged between the two copies apart from the sweep
SEEN IN: odinfree, ecdsa.fail 676 → 675 qubit step (ripple_true_carry)
PROOF: QCP.P37.correct, 3 lanes, all inputs

P39 / HOST AND FREE WIRES

Rotate around an occupied wire

A controlled cyclic shift moves a word round by one place. One position of the word is known to be zero, so a foreign bit has been parked there. The plain fix moves the guest out, rotates, and moves it back, which needs a free wire.

Leave the parked position out of the cycle. If the word is zero at that position before and after the shift, the shorter cycle produces the same word and never touches the guest. It also needs one controlled swap fewer.

Before: Move the guest out, rotate, move it back, 3. After: Skip the occupied position, 2 (controlled swaps · no free wire needed).

Toffolis: Lower. One controlled swap fewer: 3 → 2 here.
Qubits: Lower. No free wire to move the guest out.
Toffoli × qubit scores: Lower. Both factors fall.
Q² × Toffoli (DQI): Lower. Both factors fall; the qubit counts twice.

from qiskit import QuantumCircuit
# promise: x1 = x2 = 0; x2 hosts a tag
C, X0, X3, X1, X2 = 0, 1, 2, 3, 4

def before():  # rotate all four positions
    qc = QuantumCircuit(5)
    qc.cswap(C, X0, X1)
    qc.cswap(C, X0, X2)  # touches the hosting wire
    qc.cswap(C, X0, X3)
    return qc

def after():  # skip the hole
    qc = QuantumCircuit(5)
    qc.cswap(C, X0, X1)
    qc.cswap(C, X0, X3)
    return qc

NEEDS: A promise: the word is zero at the hole and at the position that would shift into it. This is a fact about the surrounding algorithm and must be proved for the circuit at hand
SEEN IN: jackylee0424, ecdsa.fail 648-qubit entry (holeRot)
PROOF: QCP.P39.correct on the promised inputs, and .hole_untouched

P41 / HOST AND FREE WIRES

Recompute a value around each reader instead of holding it

A scratch value is read by two blocks, with a long stage in between that never looks at it. Holding it there costs a qubit for the whole stage.

Erase the value after the first reader and compute it again before the second. With measured erasure (P01) an erase is free, so the whole price of the freed wire is one more compute.

Before: Value held across the stage, 1. After: Erased, then computed again, 2 (toffolis · the wire is free during the stage).

Toffolis: Higher. One more compute: 1 → 2 here.
Qubits: Lower. The wire is free during the stage.
Toffoli × qubit scores: Depends. Pays when the stage is at the peak width and the value is cheap to recompute.
Q² × Toffoli (DQI): Depends. Same test; the qubit counts twice.

from qiskit import QuantumCircuit

def erase(qc, c, a, b, bit):
    qc.h(c); qc.measure(c, bit); qc.reset(c)
    with qc.if_test((qc.clbits[bit], 1)):
        qc.cz(a, b)

def before():  # c = a AND b is held across S
    a, b, y1, y2, y3, c = range(6)
    qc = QuantumCircuit(6, 2)
    qc.ccx(a, b, c)
    qc.cx(c, y1)  # first reader
    # S: a long stage that never reads c
    qc.ccx(a, y1, y2)
    qc.cx(c, y3)  # second reader
    erase(qc, c, a, b, 0)
    return qc

def after():  # c's wire is free during S
    a, b, y1, y2, y3, c = range(6)
    qc = QuantumCircuit(6, 2)
    qc.ccx(a, b, c); qc.cx(c, y1); erase(qc, c, a, b, 0)
    qc.ccx(a, y1, y2)  # S
    qc.ccx(a, b, c); qc.cx(c, y3); erase(qc, c, a, b, 1)
    return qc

NEEDS: The stage in between does not change the inputs the value is computed from
SEEN IN: jackylee0424, ecdsa.fail 652-qubit step (the carry of X + M in the multiply); nasqret measures a whole cofactor away and regenerates it later
PROOF: QCP.P41.correct; cost 2 → 3 counting the stage

P42 / HOST AND FREE WIRES

Priority search with one flag

Find the highest row j whose predicate p(j) is 1 and write j into an index register. The standard scan carries three flag lanes through every row: still searching, found, and hit.

Keep one flag S, "still searching". Row j writes j into the index when p(j) and S are both 1. Then S is switched off by testing whether the index now equals j. After the last row S equals [index = 0], so one more test returns it to 0.

Before: One row of the scan, three flags, 3. After: One row, one flag: write j, then switch S off, 1 (flag lanes held through the scan (row 3 shown)).

Toffolis: Higher. One index test per row is added; it grows with the width of the index.
Qubits: Lower. Two flag lanes fewer.
Toffoli × qubit scores: Depends. Pays when the scan runs at the peak width.
Q² × Toffoli (DQI): Depends. Same test; each lane counts twice.

from qiskit import QuantumCircuit
# jl = largest j with p_j = 1
P1, P2, P3, J0, J1, S, FOUND, HIT = range(8)

def before():  # three flag lanes: S, FOUND, HIT
    qc = QuantumCircuit(8, 3)
    qc.x(S)
    for bit, (p, j) in enumerate([(P3, 3), (P2, 2), (P1, 1)]):
        # first hit?
        qc.x(FOUND); qc.mcx([p, S, FOUND], HIT); qc.x(FOUND)
        if j & 1: qc.cx(HIT, J0)
        if j & 2: qc.cx(HIT, J1)
        qc.cx(HIT, FOUND)
        # erase HIT
        qc.h(HIT); qc.measure(HIT, bit); qc.reset(HIT)
        with qc.if_test((qc.clbits[bit], 1)):
            if not j & 1: qc.x(J0)
            if not j & 2: qc.x(J1)
            # sign of p AND [jl = j]
            qc.h(p); qc.mcx([J0, J1], p); qc.h(p)
            if not j & 1: qc.x(J0)
            if not j & 2: qc.x(J1)
    # clear FOUND
    qc.x([J0, J1]); qc.ccx(J0, J1, FOUND); qc.x([J0, J1]); qc.x(FOUND)
    qc.x(S)
    return qc

def after():  # one flag: "still searching"
    qc = QuantumCircuit(8)
    qc.x(S)
    qc.ccx(P3, S, J0); qc.ccx(P3, S, J1)
    qc.ccx(J0, J1, S)  # S off if jl = 3
    qc.ccx(P2, S, J1)
    # S off if jl = 2
    qc.x(J0); qc.ccx(J0, J1, S); qc.x(J0)
    qc.ccx(P1, S, J0)
    # S off if jl = 1
    qc.x(J1); qc.ccx(J0, J1, S); qc.x(J1)
    # S = [jl = 0]: clear it
    qc.x([J0, J1]); qc.ccx(J0, J1, S); qc.x([J0, J1])
    return qc

NEEDS: The index starts at 0; the predicates do not change during the scan; 0 is not one of the scanned rows
SEEN IN: SnehalRaj, ecdsa.fail (sweep_fwd_d1, on BitWonka's greedyfrog): part of an 809 → 807 qubit step
PROOF: QCP.P42.correct, three predicates, 2-bit index

P43 / HOST AND FREE WIRES

An OR of predicates that exclude each other is an XOR

The block computes t ^= a AND (p OR (q AND c)), where p and q are never both 1: for example "less than" and "equal" for the same two numbers. Built as written, it holds q·c and the OR on two temporaries at the same time.

When p and q exclude each other the OR equals an XOR, and the XOR splits into two independent toggles: t ^= a·p, then t ^= a·q·c. The first predicate can be computed, used and freed before the second is even allocated.

Before: q·c and the OR held together, 2. After: Two independent toggles, 1 (temporaries held at once · toffolis 5 → 3 as emitted).

Toffolis: Lower. 5 → 3 against the form in the source circuit. If that form already erased by measurement, the count is equal.
Qubits: Lower. 2 temporaries → 1.
Toffoli × qubit scores: Lower. One qubit off the peak.
Q² × Toffoli (DQI): Lower. The freed qubit counts twice.

from qiskit import QuantumCircuit
A, C, T, X0, X1, P, Q, EC, OR = range(9)
# t ^= a AND (p OR (q AND c)), with p = [x < 1], q = [x = 1]: never both

def flags(qc):  # p and q from a 2-bit number x
    # p = [x = 0]
    qc.x([X0, X1]); qc.ccx(X0, X1, P); qc.x([X0, X1])
    qc.x(X1); qc.ccx(X0, X1, Q); qc.x(X1)  # q = [x = 1]

def before():  # two temporaries live together
    qc = QuantumCircuit(9)
    flags(qc)
    qc.ccx(Q, C, EC)
    # or = p OR ec
    qc.x([P, EC]); qc.ccx(P, EC, OR); qc.x(OR); qc.x([P, EC])
    qc.ccx(A, OR, T)
    qc.x([P, EC]); qc.x(OR); qc.ccx(P, EC, OR); qc.x([P, EC])
    qc.ccx(Q, C, EC)
    flags(qc)
    return qc

def after():  # exclusive, so OR is XOR
    qc = QuantumCircuit(9, 1)
    flags(qc)
    qc.ccx(A, P, T)  # t ^= a p
    qc.ccx(Q, C, EC); qc.ccx(A, EC, T)  # t ^= a q c
    qc.h(EC); qc.measure(EC, 0); qc.reset(EC)
    with qc.if_test((qc.clbits[0], 1)):
        qc.cz(Q, C)
    flags(qc)
    return qc

NEEDS: A promise: p AND q = 0 on every input
SEEN IN: SnehalRaj, ecdsa.fail (swap_flag_lean): one lane each in two width steps (their claim)
PROOF: QCP.P43.correct, under the promise

P49 / HOST AND FREE WIRES

Divide by three on a sliding three-wire window

A stack of base-3 digits takes two wires per digit if each digit is stored on its own. Packed into one binary number Y = 3x + d it takes about 1.585 wires per digit, but then push and pop are a multiply or divide by 3.

Slide a three-wire window along the number. For a window value Z = a + 2b + 4h below 6, seven gates leave Z mod 3 in (a, b) and the quotient bit [Z ≥ 3] in h. Two of the seven are Toffolis, and no carry wire is needed.

Before: Each base-3 digit on its own two wires, 2. After: One window step of a divide by 3, 1.585 (wires per base-3 digit · 2 toffolis per window step).

Toffolis: Higher. 2 per bit of the packed number for each push or pop; separate digits need none.
Qubits: Lower. 1.585 wires per base-3 digit instead of 2.
Toffoli × qubit scores: Depends. Pays when the digit stack is at the peak width.
Q² × Toffoli (DQI): Depends. Same test; the wires count twice.

from qiskit import QuantumCircuit
from qiskit.quantum_info import Operator

def before():  # a base-3 digit kept in its own two wires
    # (nothing to do: 2 wires per digit)
    qc = QuantumCircuit(3)
    return qc

def after():  # pop one digit from a dense binary number:
    # window value Z = a + 2b + 4h, Z < 6
    a, b, h = 0, 1, 2
    qc = QuantumCircuit(3)
    qc.ccx(a, b, h)  # h = [Z >= 3]
    qc.cx(a, b); qc.x(a); qc.x(h)
    qc.cx(h, a); qc.ccx(h, a, b)  # (a, b) = Z mod 3
    qc.x(h)
    return qc

NEEDS: A promise: Z < 6 at every step, which follows from a tracked bound on the stored number
SEEN IN: gopikannappan, ecdsa.fail (dense_push, dense_pop_digit)
PROOF: QCP.P49.correct under the promise, and .spec_is_divmod

06 / PART 3 · CHEAPER ARITHMETIC CELLS

After a qubit is removed, the arithmetic is rebuilt around the gap.

These eight lower the Toffoli count of a small arithmetic cell without touching the width. They are part of how the price of a removed qubit is won back: an adder cell that shares a product, an increment made of two plain additions, a count read off with CNOTs.

P28 / CHEAPER ARITHMETIC CELLS

Share one product between the two halves of a controlled adder cell

One cell of a controlled ripple adder does two things: carry ^= ctrl·a·b, and a ^= ctrl·b. Built separately they cost 3 Toffolis, even with a measured erase.

ctrl·b is one factor of the carry term, and it is also exactly what must be added to a. Compute d = ctrl·b once, use it for the carry with one Toffoli, copy it into a with a CNOT, and erase d by measurement.

Before: Carry and sum built separately, 3. After: One product ctrl·b serves both, 2 (toffolis per adder cell).

Toffolis: Lower. 3 → 2 per cell (4 → 2 without a measured erase).
Qubits: Same. The same scratch qubit.
Toffoli × qubit scores: Lower. Toffolis fall, width is untouched.
Q² × Toffoli (DQI): Lower. Same Toffoli gain.

from qiskit import QuantumCircuit

def before():  # carry ^= ctrl a b ; a ^= ctrl b
    ctrl, a, b, carry, d = range(5)
    qc = QuantumCircuit(5, 1)
    qc.ccx(ctrl, a, d)  # d = ctrl a
    qc.ccx(b, d, carry)
    qc.h(d); qc.measure(d, 0); qc.reset(d)
    with qc.if_test((qc.clbits[0], 1)):
        qc.cz(ctrl, a)
    qc.ccx(ctrl, b, a)  # a third Toffoli for a ^= ctrl b
    return qc

def after():
    ctrl, a, b, carry, d = range(5)
    qc = QuantumCircuit(5, 1)
    qc.ccx(ctrl, b, d)  # d = ctrl b serves both updates
    qc.ccx(a, d, carry)
    qc.cx(d, a)  # a ^= ctrl b for free
    qc.h(d); qc.measure(d, 0); qc.reset(d)
    with qc.if_test((qc.clbits[0], 1)):
        qc.cz(ctrl, b)
    return qc

NEEDS: d is clean; the repair after measuring d is a CZ on ctrl and b
SEEN IN: odinfree's exact-rewrite lane on an 834-qubit ecdsa.fail circuit: 4,229,758 cells rewritten, 68.12M → 63.94M Toffolis (their count)
PROOF: QCP.P28.correct, all inputs and all outcomes

P32 / CHEAPER ARITHMETIC CELLS

Controlled increment from two plain additions

x += f adds one to a word when a control f is set. No clean carry chain is free, only a second word d that holds something else and must come back unchanged. Putting the control on every sum-writing gate of two additions costs about 2(3n−2) Toffolis.

If f is set, complement both x and d. Add d to x, complement again, and subtract d. With f set this computes x + d + 1 and then x + 1. With f clear the addition and the subtraction cancel. The control only ever sits on CNOTs.

Before: Two additions with the control on every write, ≈6n. After: Flip, add, flip, subtract, ≈4n (toffolis, n-bit controlled increment).

Toffolis: Lower. About 2(3n−2) → 4(n−1).
Qubits: Same. The same borrowed word.
Toffoli × qubit scores: Lower. Toffolis fall, width is untouched.
Q² × Toffoli (DQI): Lower. Same Toffoli gain.

from qiskit import QuantumCircuit
from qiskit.circuit.library import ModularAdderGate
# x += f (mod 8); d holds anything
F, D, X = 0, [1, 2, 3], [4, 5, 6]
ADD = ModularAdderGate(3)  # second word += first word

def before():  # every adder carries the control
    qc = QuantumCircuit(7)
    SUB = ADD.inverse().control(1)
    qc.append(SUB, [F, *D, *X])  # x -= d      if f
    qc.x(D)
    qc.append(SUB, [F, *D, *X])  # x -= NOT d  if f
    qc.x(D)  # d + NOT d = -1, so x += 1
    return qc

def after():  # two plain adders
    qc = QuantumCircuit(7)
    qc.cx(F, D); qc.cx(F, X)  # complement both words if f
    qc.append(ADD, [*D, *X])  # x += d
    qc.cx(F, D); qc.cx(F, X)  # f = 1: x is now x + d + 1
    qc.append(ADD.inverse(), [*D, *X])  # x -= d
    return qc

NEEDS: x, d and the control are separate wires. With several controls, the flip is one multi-controlled gate fanned out by CNOTs
SEEN IN: nasqret, ecdsa.fail (sharedConditionalIncrement): about 4.4M of 485M Toffolis at 651 qubits (their figures)
PROOF: QCP.P32.correct, n = 4, all inputs and outcomes

P36 / CHEAPER ARITHMETIC CELLS

Skip the carries that cannot happen

acc += ctrl·c adds a known constant c under a control. A ripple adder starts its carry chain at bit 0 and spends a Toffoli and a carry qubit on every position.

If the low j bits of c are zero and nothing carries in, every carry in that low run is zero for certain. Start the chain at the first position that can carry and skip the rest. The same idea shortens comparisons against a constant whose low bits are all ones.

Before: Carry chain from bit 0, n−1. After: Chain starts where a carry can first appear, n−1−j (toffolis, constant with j low zero bits).

Toffolis: Lower. n−1 → n−1−j.
Qubits: Lower. j fewer carry qubits.
Toffoli × qubit scores: Lower. Both factors fall when the adder is at the peak.
Q² × Toffoli (DQI): Lower. Both factors fall; the qubits count twice.

from qiskit import QuantumCircuit
from qiskit.circuit.library import ModularAdderGate
# acc += 4 if ctrl
CTRL, ACC, TMP = 0, [1, 2, 3, 4], [5, 6, 7, 8]

def before():  # full ripple from bit 0
    qc = QuantumCircuit(9)
    qc.cx(CTRL, TMP[2])  # tmp = ctrl * 4
    qc.append(ModularAdderGate(4), [*TMP, *ACC])
    qc.cx(CTRL, TMP[2])
    return qc

def after():  # bits 0 and 1 of the constant are 0:
    # no carry can arise below bit 2
    qc = QuantumCircuit(9)
    qc.ccx(CTRL, ACC[2], ACC[3])
    qc.cx(CTRL, ACC[2])
    return qc

NEEDS: The fact about c, or about the incoming carry, holds on every input. At the call sites it is structural
SEEN IN: odinfree, ecdsa.fail (dead_low_carry_run: modular halving, doubling, conditional negation); haotang1995 for the comparison form (t0_window.rs)
PROOF: QCP.P36.full_correct and .skipped_correct, 4 bits, c = 4; cost 3 → 1

P40 / CHEAPER ARITHMETIC CELLS

Read a parity of M − 1 from M without decrementing

A step needs a parity of M − 1 (an XOR of some of its bits) and needs M itself afterwards. The direct way decrements M, reads, and increments it back: two incrementers.

M and M − 1 differ only on the bits up to and including the lowest 1 of M. So bit j differs exactly when bits 0 to j−1 of M are all zero. Read the parity from M itself and correct it with one "low bits are zero" test per position.

Before: Decrement, read, increment, 2. After: Read M, then correct per position, 1 (toffolis, 3-bit m · no incrementer).

Toffolis: Lower. Two incrementers → a few zero tests: 2 → 1 for 3 bits.
Qubits: Same. No extra qubit.
Toffoli × qubit scores: Lower. Toffolis fall, width is untouched.
Q² × Toffoli (DQI): Lower. Same Toffoli gain.

from qiskit import QuantumCircuit
M, H = [0, 1, 2], 3  # h ^= parity of the bits of M - 1

def decrement(qc, back=False):
    ops = [lambda: qc.x(M[0]), lambda: qc.x(M[1]),
           lambda: qc.ccx(M[0], M[1], M[2]), lambda: qc.x(M[1]),
           lambda: qc.cx(M[0], M[1])]
    for op in (reversed(ops) if back else ops):
        op()

def before():  # decrement, read, increment
    qc = QuantumCircuit(4)
    decrement(qc)
    qc.cx(M, H)
    decrement(qc, back=True)
    return qc

def after():  # M and M - 1 differ up to the lowest 1
    qc = QuantumCircuit(4)
    qc.cx(M, H)  # parity of M
    qc.x(H)  # bit 0 always differs
    # bit 1 if M0 = 0
    qc.x(M[0]); qc.cx(M[0], H); qc.x(M[0])
    # bit 2 if M0 = M1 = 0
    qc.x(M[:2]); qc.ccx(M[0], M[1], H); qc.x(M[:2])
    return qc

NEEDS: Nothing for the identity; the tests need controls on the low bits of M
SEEN IN: jackylee0424, ecdsa.fail 648-qubit entry (lift step of the multiply)
PROOF: QCP.P40.xor_pred (16-bit words) and .correct (3-bit circuit); cost 2 → 1

P44 / CHEAPER ARITHMETIC CELLS

A signed two-bit multiple of a constant with one AND and one adder

lo += k·c adds a multiple of a known constant c, where the digit k is 0, 1, 2 or −1 and is held on two qubits (o, e₂). One controlled adder per case costs two to three adders.

Compute f = o AND e₂, which marks the −1 case. Load the operand c·o + 2c·(e₂ XOR f) with CNOTs. Complement lo if f, add once with a plain adder, and complement back: complement, add, complement is a subtraction.

Before: One controlled adder per case, 3. After: One AND, then one plain adder, 1 (adders per digit (plus one and)).

Toffolis: Lower. 2 to 3 adders → 1 AND and 1 adder.
Qubits: Same. The same operand register.
Toffoli × qubit scores: Lower. Toffolis fall, width is untouched.
Q² × Toffoli (DQI): Lower. Same Toffoli gain.

from qiskit import QuantumCircuit
from qiskit.circuit.library import ModularAdderGate
O, E2, LO, OP, F = 0, 1, [2, 3, 4, 5], [6, 7, 8, 9], 10
# lo += k * 3 (mod 16), k = o + 2 e2, (1,1) = -1
ADD = ModularAdderGate(4)

def before():  # one adder per case
    qc = QuantumCircuit(11)
    qc.cx(O, OP[0]); qc.cx(O, OP[1])  # +3 if o
    qc.append(ADD, [*OP, *LO])
    qc.cx(O, OP[0]); qc.cx(O, OP[1])
    qc.cx(E2, OP[1]); qc.cx(E2, OP[2])  # +6 if e2
    qc.append(ADD, [*OP, *LO])
    qc.cx(E2, OP[1]); qc.cx(E2, OP[2])
    qc.ccx(O, E2, F)  # both: 3 + 6 - 12 = -3
    qc.cx(F, OP[2]); qc.cx(F, OP[3])
    qc.append(ADD.inverse(), [*OP, *LO])
    qc.cx(F, OP[2]); qc.cx(F, OP[3])
    qc.ccx(O, E2, F)
    return qc

def after():  # one AND, one plain adder
    qc = QuantumCircuit(11, 1)
    qc.ccx(O, E2, F)
    load = [(O, 0), (O, 1), (E2, 1), (E2, 2), (F, 1), (F, 2)]
    # op = 3 o + 6 (e2 XOR f)
    for c, i in load: qc.cx(c, OP[i])
    qc.cx(F, LO)  # complement lo if f
    qc.append(ADD, [*OP, *LO])
    qc.cx(F, LO)  # NOT(NOT lo + 3) = lo - 3
    for c, i in reversed(load): qc.cx(c, OP[i])
    qc.h(F); qc.measure(F, 0); qc.reset(F)
    with qc.if_test((qc.clbits[0], 1)):
        qc.cz(O, E2)
    return qc

NEEDS: The operand register is clean; the result is taken modulo 2^W
SEEN IN: yashward001, ecdsa.fail (add_kappa_c); their note credits the fused cell to J. Long et al.
PROOF: QCP.P44.correct, W = 4, c = 3, all four digits

P47 / CHEAPER ARITHMETIC CELLS

Count a thermometer with CNOTs

Prefix flags p₀ ≥ p₁ ≥ … say "the first j+1 tested bits are all 1". Turning them into a binary count, such as a number of leading zeros, is usually done with a binary search and shifts, or with an increment per flag.

Bit k of a count flips each time the count passes a multiple of 2^k. So bit k of the answer is the XOR of the flags p(j) for which j+1 is a multiple of 2^k. After the one AND chain that makes the flags, the count costs only CNOTs.

Before: One increment per flag, 3. After: Each count bit is an XOR of flags, 0 (toffolis to count 3 flags, after the and chain).

Toffolis: Lower. The count itself costs 0; only the AND chain is paid.
Qubits: Same. No extra qubit.
Toffoli × qubit scores: Lower. Toffolis fall, width is untouched.
Q² × Toffoli (DQI): Lower. Same Toffoli gain.

from qiskit import QuantumCircuit
from qiskit.circuit.library import ModularAdderGate
Z, R, P1, P2, ONE = [0, 1, 2], [3, 4], 5, 6, [7, 8]
# r += number of leading ones of z (0..3)

# prefix flags: p0 = z0, p1 = z0 z1, p2 = p1 z2
def chain(qc):
    qc.ccx(Z[0], Z[1], P1); qc.ccx(P1, Z[2], P2)

def unchain(qc):
    qc.ccx(P1, Z[2], P2); qc.ccx(Z[0], Z[1], P1)

def before():  # add each flag with an adder
    qc = QuantumCircuit(9)
    chain(qc)
    for p in (Z[0], P1, P2):
        qc.cx(p, ONE[0])
        qc.append(ModularAdderGate(2), [*ONE, *R])
        qc.cx(p, ONE[0])
    unchain(qc)
    return qc

def after():  # R starts at 0: bits of the count are XORs
    qc = QuantumCircuit(9)
    chain(qc)
    # bit 0: all flags
    qc.cx(Z[0], R[0]); qc.cx(P1, R[0]); qc.cx(P2, R[0])
    qc.cx(P1, R[1])  # bit 1: every second flag
    unchain(qc)
    return qc

NEEDS: The flags are monotone, which a prefix AND chain guarantees
SEEN IN: gopikannappan, ecdsa.fail (prefix_seven): seven flags to a 3-bit count with 7 Toffolis in total
PROOF: QCP.P47.correct, three tested bits

P50 / CHEAPER ARITHMETIC CELLS

Move a control from two arithmetic blocks onto one swap

Under a control s the step does q → q + g − f and then exchanges the registers g and f. Done directly that is a controlled add, a controlled subtract and a controlled swap.

Add g to q with no control. Swap g and f under s. Subtract "g" from q with no control. If s was set, the wires called g now hold f, so the net effect is q + g − f. If not, the add and the subtract cancel. It works for any block that only reads g.

Before: Controlled add, controlled subtract, swap, ≈5n. After: Add, controlled swap, subtract, ≈3n (toffolis, n-bit registers).

Toffolis: Lower. Two controlled adders → two plain ones, roughly half each.
Qubits: Same. No extra qubit.
Toffoli × qubit scores: Lower. Toffolis fall, width is untouched.
Q² × Toffoli (DQI): Lower. Same Toffoli gain.

from qiskit import QuantumCircuit
from qiskit.circuit.library import ModularAdderGate
S, G, F, Q = 0, [1, 2, 3], [4, 5, 6], [7, 8, 9]
# if s: q += g - f, and swap g with f
ADD = ModularAdderGate(3)

def before():  # both adders carry the control
    qc = QuantumCircuit(10)
    qc.append(ADD.control(1), [S, *G, *Q])
    qc.append(ADD.inverse().control(1), [S, *F, *Q])
    for i in range(3): qc.cswap(S, G[i], F[i])
    return qc

def after():  # only the swap is controlled
    qc = QuantumCircuit(10)
    qc.append(ADD, [*G, *Q])  # q += g
    for i in range(3): qc.cswap(S, G[i], F[i])
    # q -= "g", which holds f if s
    qc.append(ADD.inverse(), [*G, *Q])
    return qc

NEEDS: The swap is exactly the controlled exchange of the two operand registers and does not touch q
SEEN IN: gopikannappan, ecdsa.fail (lq_codec_crossing_swap), there with multiplications by odd numbers as the blocks
PROOF: QCP.P50.correct, 3-bit registers

P54 / CHEAPER ARITHMETIC CELLS

Rotate by +1 or −1 with one controlled rotate-by-2

A ring of n lanes moves one place up if u = 1 and one place down if u = 0. Two controlled rotations, one each way, cost about 2(n−1) controlled swaps.

Every input moves by exactly one place, so first rotate everything down with no control: that is only a renaming of wires and costs nothing. Then rotate up by two under u. For even n that takes n−2 controlled swaps.

Before: Up if u, down if not u, 6. After: Down for free, then up by two if u, 2 (controlled swaps, 4 lanes (2(n−1) → n−2)).

Toffolis: Lower. 2(n−1) → n−2 controlled swaps.
Qubits: Same. No extra qubit.
Toffoli × qubit scores: Lower. Toffolis fall, width is untouched.
Q² × Toffoli (DQI): Lower. Same Toffoli gain.

from qiskit import QuantumCircuit
W, U = [0, 1, 2, 3], 4  # rotate up if u, down if not u

def before():
    qc = QuantumCircuit(5)
    # up by one if u
    for j in (1, 2, 3): qc.cswap(U, W[0], W[j])
    qc.x(U)
    # down by one if not u
    for j in (2, 1, 0): qc.cswap(U, W[j], W[3])
    qc.x(U)
    return qc

def after():
    qc = QuantumCircuit(5)
    # down by one: a free relabel
    for j in (2, 1, 0): qc.swap(W[j], W[3])
    # up by two if u
    qc.cswap(U, W[0], W[2]); qc.cswap(U, W[1], W[3])
    return qc

NEEDS: There is no "stay" case: every input moves by exactly one place
SEEN IN: BitWonka, ecdsa.fail (rot2_up): −157 Toffolis per slot at 314 lanes (their figure)
PROOF: QCP.P54.correct and .baseline_is_rotation, n = 4; cost 6 → 2

07 / PART 4 · USE WHAT IS ALREADY KNOWN

A value that is already known does not need a Toffoli.

Three more cases in the spirit of Part 1 of Dispatch 1. If analysis proves what a wire will hold, or a control is really a classical bit, or a digit can be read off a parity, the expensive gate has nothing left to compute.

P31 / USE WHAT IS ALREADY KNOWN

A Toffoli whose result is already known is free

A Toffoli writes a·b onto a wire t. At some sites, analysis of the circuit proves what t will hold afterwards: a constant, or the same value as another live wire r.

Then the gate has nothing to compute. Measure t away, repair the sign with a CZ on a and b and a Z on r, and write the known result back with a CNOT from r. P01 is the special case where the result is 0.

Before: A Toffoli whose result is known to equal r, 1. After: Measure, repair, copy r back, 0 (toffolis per site).

Toffolis: Lower. 1 → 0 per site.
Qubits: Same. No extra qubit; one classical bit.
Toffoli × qubit scores: Lower. Toffolis fall, width is untouched.
Q² × Toffoli (DQI): Lower. Same Toffoli gain.

from qiskit import QuantumCircuit

# the state the analysis proved:
def promised(qc, a, b, r, t):
    qc.ccx(a, b, t); qc.cx(r, t)  # t holds ab XOR r

def before():
    a, b, r, t = 0, 1, 2, 3
    qc = QuantumCircuit(4)
    promised(qc, a, b, r, t)
    qc.ccx(a, b, t)  # afterwards t = r: a known result
    return qc

def after():
    a, b, r, t = 0, 1, 2, 3
    qc = QuantumCircuit(4, 1)
    promised(qc, a, b, r, t)
    # forget the old value
    qc.h(t); qc.measure(t, 0); qc.reset(t)
    with qc.if_test((qc.clbits[0], 1)):
        qc.cz(a, b); qc.z(r)  # repair the sign
    qc.cx(r, t)  # write the known result back
    return qc

NEEDS: The claim "t ends equal to r" must hold on every reachable input. It comes from a symbolic pass over the circuit, so it is only as sound as that pass
SEEN IN: odinfree's exact-rewrite lane on an 834-qubit ecdsa.fail circuit: 257,462 executed Toffolis with a constant result removed, and more with a live-wire result (their counts)
PROOF: QCP.P31.correct, from the promised state, all inputs, both outcomes

P45 / USE WHAT IS ALREADY KNOWN

A control that is known classically costs nothing

t ^= q AND c is a Toffoli. But at some sites the wire q provably holds b₁ XOR b₂, where b₁ and b₂ are classical bits: the outcomes of earlier measurements.

Replace the quantum control by the classical bits: apply CNOT(c → t) if b₁, and once more if b₂. A gate switched by a classical bit is free on both scoreboards.

Before: A Toffoli whose control q is b₁ XOR b₂, 1. After: Two CNOTs switched by classical bits, 0 (toffolis per site).

Toffolis: Lower. 1 → 0 per site.
Qubits: Same. No extra qubit.
Toffoli × qubit scores: Lower. Toffolis fall, width is untouched.
Q² × Toffoli (DQI): Lower. Same Toffoli gain.

from qiskit import QuantumCircuit
C, T, Q, S1, S2 = range(5)

def known(qc):  # q holds b1 XOR b2, two earlier outcomes
    for s, bit in ((S1, 0), (S2, 1)):
        qc.h(s); qc.measure(s, bit); qc.reset(s)
        with qc.if_test((qc.clbits[bit], 1)):
            qc.x(Q)

def before():
    qc = QuantumCircuit(5, 2)
    known(qc)
    qc.ccx(Q, C, T)
    # (return q to 0)
    with qc.if_test((qc.clbits[0], 1)): qc.x(Q)
    with qc.if_test((qc.clbits[1], 1)): qc.x(Q)
    return qc

def after():  # the control is classical: no Toffoli
    qc = QuantumCircuit(5, 2)
    known(qc)
    with qc.if_test((qc.clbits[0], 1)): qc.cx(C, T)
    with qc.if_test((qc.clbits[1], 1)): qc.cx(C, T)
    with qc.if_test((qc.clbits[0], 1)): qc.x(Q)
    with qc.if_test((qc.clbits[1], 1)): qc.x(Q)
    return qc

NEEDS: The fact about q must be proved for the circuit at hand
SEEN IN: MonitSharma, ecdsa.fail (classical_xor_control.rs)
PROOF: QCP.P45.correct

P55 / USE WHAT IS ALREADY KNOWN

Erase a division digit with two CNOTs

One step of long division by an odd number d: T = 2R + g, the digit is f = [T ≥ d], and the new remainder is R′ = T − f·d. Afterwards f must be cleared or stored. Clearing it with a second comparison costs n Toffolis; storing it costs a qubit per step.

d is odd, so subtracting it flips the lowest bit. The lowest bit of R′ therefore equals g XOR f, and two CNOTs, one from that bit and one from g, return f to zero.

Before: A second comparison clears the digit, n. After: Two CNOTs clear it, 0 (toffolis to clear one quotient digit).

Toffolis: Lower. n → 0 per division step.
Qubits: Lower. No quotient register.
Toffoli × qubit scores: Lower. Both factors fall.
Q² × Toffoli (DQI): Lower. Both factors fall; the qubits count twice.

from qiskit import QuantumCircuit
from qiskit.quantum_info import Operator
# One restoring-division step by an odd d: T = 2R + g, f = [T >= d], R' = T - f d.
# Because d is odd, the low bit of R' is g XOR f.

def before():  # baseline: clear f with a second
    # n-bit comparison (not shown), or
    qc = QuantumCircuit(3)
    return qc  # keep it in a quotient register

def after():  # r0 = low bit of the new remainder
    r0, g, f = 0, 1, 2
    qc = QuantumCircuit(3)
    qc.cx(r0, f)
    qc.cx(g, f)  # f = f XOR r0 XOR g = 0
    return qc

NEEDS: d is odd and 0 ≤ R < d
SEEN IN: BitWonka, ecdsa.fail (frogdrop's streamed reciprocal): the reason the reciprocal is never stored in that family
PROOF: QCP.P55.digit_is_parity (the arithmetic fact, 8-bit) and .erase_correct

08 / PART 5 · REWRITES A TOOL CAN APPLY

Seven more identities for an automatic pass.

These need no knowledge of the algorithm and can run over a finished gate list, like Part 2 of Dispatch 1. Some need a fact proved about the circuit first, for example that two wires always hold the same value. The gains quoted for them are their authors' own measurements.

P30 / REWRITES A TOOL CAN APPLY

Swap two code words with one controlled toggle

Exchange two values L and R of a small register and leave every other value alone, for example when re-coding a counter. A Gray path from L to R and back takes 2d−1 controlled toggles when L and R differ in d bits.

Pick one bit where L and R differ as the pivot. XOR it into every other differing bit with CNOTs: now L and R differ only at the pivot. Toggle the pivot under a control on all the other bits, then undo the CNOTs.

Before: Gray path there and back, 3. After: Pivot bit, one toggle, 1 (controlled toggles, codes 011 and 101 (2d−1 → 1)).

Toffolis: Lower. 2d−1 → 1 controlled toggles.
Qubits: Same. No extra qubit.
Toffoli × qubit scores: Lower. Toffolis fall, width is untouched.
Q² × Toffoli (DQI): Lower. Same Toffoli gain.

from qiskit import QuantumCircuit

def before():  # exchange codes 011 and 101: Gray path
    qc = QuantumCircuit(3)
    qc.ccx(0, 1, 2)  # 011 <-> 111
    qc.ccx(0, 2, 1)  # 111 <-> 101
    qc.ccx(0, 1, 2)
    return qc

def after():
    qc = QuantumCircuit(3)
    qc.cx(1, 2)  # now the two codes differ in bit 1 only
    qc.ccx(0, 2, 1)  # one toggle of the pivot bit
    qc.cx(1, 2)
    return qc

NEEDS: Nothing beyond the register itself
SEEN IN: ecdsa.fail 793-qubit lane (odinfree's port; their note credits the idea to mochimodev): −22.8M and −23.7M Toffolis at two sites (their counts)
PROOF: QCP.P30.correct and .grayPath_correct, 3-bit register, codes 3 and 5; cost 3 → 1

P35 / REWRITES A TOOL CAN APPLY

Undo, measure, redo cancels across a measurement it never touches

Circuit generators often uncompute a block U before a flag f is measured and recompute U straight afterwards. If U does not touch f, that is twice the cost of U for nothing.

A gate that does not touch f commutes with the measurement and reset of f. So U⁻¹ and U meet across the measurement and cancel. This is the pair cancellation of P02, extended across a measurement.

Before: Undo U, measure f, redo U, 2. After: Only the measurement remains, 0 (toffolis per site, u = one toffoli).

Toffolis: Lower. 2 × cost(U) → 0.
Qubits: Same. No extra qubit.
Toffoli × qubit scores: Lower. Toffolis fall, width is untouched.
Q² × Toffoli (DQI): Lower. Same Toffoli gain.

from qiskit import QuantumCircuit

def before():
    a, b, t, f = 0, 1, 2, 3
    qc = QuantumCircuit(4, 1)
    qc.ccx(a, b, t)  # undo a block ...
    # ... measure a flag it never touches
    qc.h(f); qc.measure(f, 0); qc.reset(f)
    qc.ccx(a, b, t)  # ... and redo it
    return qc

def after():
    a, b, t, f = 0, 1, 2, 3
    qc = QuantumCircuit(4, 1)
    qc.h(f); qc.measure(f, 0); qc.reset(f)
    return qc

NEEDS: U neither reads nor writes f, and does not depend on the classical bit being written
SEEN IN: Akashneelesh, ecdsa.fail; also used by jackylee0424, who credits Akashneelesh
PROOF: QCP.P35.ccx_across_measure, any wires

P38 / REWRITES A TOOL CAN APPLY

Telescoping interval indicators

A sweep runs block j under a flag g that says "v lies in interval j". Each interval flag is the XOR of two endpoint tests, and neighbouring intervals share an endpoint. Setting g before each block and clearing it afterwards costs four endpoint tests per block.

Do not clear g between blocks. To move from one interval to the next, toggle only the endpoints that changed: the shared endpoint would be toggled twice, so it is skipped.

Before: Set and clear the flag around each block, 8. After: Keep the flag, toggle what changed, 6 (endpoint tests, two blocks).

Toffolis: Lower. 4 tests per block → each endpoint tested twice in the whole sweep.
Qubits: Same. The same flag wire.
Toffoli × qubit scores: Lower. Toffolis fall, width is untouched.
Q² × Toffoli (DQI): Lower. Same Toffoli gain.

from qiskit import QuantumCircuit
# P(k): low k bits of v are zero
V, G, T1, T2, H = [0, 1, 2], 3, 4, 5, 6

def p1(qc): qc.x(V[0]); qc.cx(V[0], G); qc.x(V[0])
def p2(qc): qc.x(V[:2]); qc.ccx(V[0], V[1], G); qc.x(V[:2])
def p3(qc):
    qc.x(V); qc.ccx(V[0], V[1], H); qc.ccx(H, V[2], G)
    qc.ccx(V[0], V[1], H); qc.x(V)

def before():  # set and clear the flag per block
    qc = QuantumCircuit(7)
    # block 1: P(1) XOR P(2)
    p1(qc); p2(qc); qc.cx(G, T1); p1(qc); p2(qc)
    # block 2: P(2) XOR P(3)
    p2(qc); p3(qc); qc.cx(G, T2); p2(qc); p3(qc)
    return qc

def after():  # keep the flag, toggle the difference
    qc = QuantumCircuit(7)
    p1(qc); p2(qc); qc.cx(G, T1)
    # the shared endpoint P(2) cancels
    p1(qc); p3(qc); qc.cx(G, T2)
    p2(qc); p3(qc)
    return qc

NEEDS: The tested register does not change between blocks; g is not needed clean in between
SEEN IN: nasqret, ecdsa.fail (lowValuationSweep): 1.02M static Toffolis at 655 qubits together with one more local change (their count)
PROOF: QCP.P38.correct, two blocks; cost 10 → 8

P46 / REWRITES A TOOL CAN APPLY

A held AND survives a flip of one of its inputs

A wire q holds a AND b. Later a is flipped and the circuit wants (NOT a) AND b. Uncompute, flip, recompute brings the total to 3 Toffolis.

(NOT a)·b equals a·b XOR b. So after a is flipped, one CNOT from b into q brings the held product up to date. More generally, after a ^= L for an XOR L of untouched wires, q is repaired by q ^= L·b.

Before: Uncompute, flip, recompute, 3. After: Flip, then one CNOT, 1 (toffolis).

Toffolis: Lower. 3 → 1 in total: the update goes from two Toffolis to one CNOT.
Qubits: Same. No extra qubit.
Toffoli × qubit scores: Lower. Toffolis fall, width is untouched.
Q² × Toffoli (DQI): Lower. Same Toffoli gain.

from qiskit import QuantumCircuit

def before():  # uncompute, flip, recompute
    a, b, q = 0, 1, 2
    qc = QuantumCircuit(3)
    qc.ccx(a, b, q)  # q = a AND b (held for a first use)
    qc.ccx(a, b, q)
    qc.x(a)
    # q = (NOT a) AND b for the second use
    qc.ccx(a, b, q)
    return qc

def after():
    a, b, q = 0, 1, 2
    qc = QuantumCircuit(3)
    qc.ccx(a, b, q)
    qc.x(a)
    qc.cx(b, q)  # (a + 1) b = a b + b
    return qc

NEEDS: b is untouched, and a is changed only by the X between the two uses
SEEN IN: gopikannappan, ecdsa.fail (apply_merge25): −359.8 executed Toffolis per shot although the gate list got longer (their measurement)
PROOF: QCP.P46.held_and_update, any wires

P48 / REWRITES A TOOL CAN APPLY

A Toffoli whose two controls are equal, or opposite

At some sites the two control wires of a Toffoli provably hold the same value, or provably hold opposite values.

a AND a is a, so with equal controls the Toffoli is a CNOT. a AND (NOT a) is 0, so with opposite controls the gate does nothing. The facts come from tracking each wire as a constant XOR a set of inputs through X, CNOT and swap gates.

Before: A Toffoli with two equal controls, 1. After: A CNOT (nothing at all if they are opposite), 0 (toffolis per site).

Toffolis: Lower. 1 → 0 per site.
Qubits: Same. No extra qubit.
Toffoli × qubit scores: Lower. Toffolis fall, width is untouched.
Q² × Toffoli (DQI): Lower. Same Toffoli gain.

from qiskit import QuantumCircuit

# a and b both hold x XOR y at this point
def setup(qc, x, y, a, b):
    qc.cx(x, a); qc.cx(y, a)
    qc.cx(y, b); qc.cx(x, b)

def before():
    x, y, t, a, b = range(5)
    qc = QuantumCircuit(5)
    setup(qc, x, y, a, b)
    qc.ccx(a, b, t)
    return qc

def after():  # equal controls: a AND a = a
    x, y, t, a, b = range(5)
    qc = QuantumCircuit(5)
    setup(qc, x, y, a, b)
    qc.cx(a, t)
    return qc

NEEDS: Only proved facts may be used. The source notes about 7,400 control pairs that looked opposite on sampled runs and could not be proved
SEEN IN: gopikannappan, ecdsa.fail (constprop.rs): 292 further Toffolis on a 1.41M-Toffoli stream
PROOF: QCP.P48.equal_controls and .opposite_controls, any wires

P53 / REWRITES A TOOL CAN APPLY

Cancel a Toffoli pair across gates that do not commute with it

Two copies of the same Toffoli A cancel when only commuting gates lie between them (P02). When a gate in between touches one of A's wires, that rule stops.

A is its own inverse, so A G A is the gate G as seen through A, and each blocking gate can be treated on its own. An X on a control becomes an X and a CNOT. A CNOT into a control becomes that CNOT and one Toffoli.

Before: A, a CNOT into its control, A again, 2. After: The CNOT and one Toffoli, 1 (toffolis (2 → 0 when the blocker is an x)).

Toffolis: Lower. 2 → 1 across a CNOT, 2 → 0 across an X.
Qubits: Same. No extra qubit.
Toffoli × qubit scores: Lower. Toffolis fall, width is untouched.
Q² × Toffoli (DQI): Lower. Same Toffoli gain.

from qiskit import QuantumCircuit

def before():
    a, b, c, d = range(4)
    qc = QuantumCircuit(4)
    qc.ccx(a, b, c)  # A
    qc.x(a)  # blockers: neither commutes with A
    qc.cx(d, a)
    qc.ccx(a, b, c)  # A again
    return qc

def after():  # conjugate each blocker by A
    a, b, c, d = range(4)
    qc = QuantumCircuit(4)
    qc.x(a); qc.cx(b, c)  # A X(a) A = X(a) CX(b,c)
    # A CX(d,a) A = CX(d,a) CCX(d,b,c)
    qc.cx(d, a); qc.ccx(d, b, c)
    return qc

NEEDS: Only X, CNOT and Toffoli gates in the interval; no measurement or reset
SEEN IN: gnuchev, ecdsa.fail (gap_correction): 2,453,920 Toffolis at 813 qubits after the single-blocker rules had found nothing more
PROOF: QCP.P53.across_x and .across_cx, any wires

P57 / REWRITES A TOOL CAN APPLY

A copy made between a Toffoli and its undo

A Toffoli puts a·b on top of t, a CNOT copies t into y, and the same Toffoli takes a·b off again. The value was copied out while a product sat on top of it.

The CNOT copied t XOR a·b. That is a plain copy of t, plus the product written straight into y. So: one CNOT from t to y, then one Toffoli from a and b into y. It is the bit-flip counterpart of the phase fold (P15).

Before: Toffoli, copy, Toffoli, 2. After: Copy, then one Toffoli into y, 1 (toffolis per site).

Toffolis: Lower. 2 → 1 per site.
Qubits: Same. No extra qubit.
Toffoli × qubit scores: Lower. Toffolis fall, width is untouched.
Q² × Toffoli (DQI): Lower. Same Toffoli gain.

from qiskit import QuantumCircuit

def before():
    a, b, t, y = range(4)
    qc = QuantumCircuit(4)
    qc.ccx(a, b, t)
    qc.cx(t, y)  # copies t XOR ab
    qc.ccx(a, b, t)
    return qc

def after():
    a, b, t, y = range(4)
    qc = QuantumCircuit(4)
    qc.cx(t, y)  # the copy of t ...
    # ... and the product, straight into y
    qc.ccx(a, b, y)
    return qc

NEEDS: a, b, t and y are four different wires; nothing else touches t or y in between
SEEN IN: RealAdii, ecdsa.fail (peephole.rs, the "copy" rule)
PROOF: QCP.P57.copy_sandwich, any wires

09 / WHAT IS NOT HERE

The largest gains are not gate-level rewrites.

A pattern in this series is small enough to state as a theorem. Most of what moved the contest is not. Three kinds of gain are left out on purpose.

Hosting at scale. Most of the descent from 653 to 647 stores a bit in a wire whose value is already known: zeros created by a shift or a division, a wire known to be one, a wire holding something that can be recomputed from live data. These are exact, but each rests on a promise that has to be stated and proved for the whole algorithm. P39, P43 and P49 are the first small cases.
Redesigns. The 648-qubit design did not get under 390 million Toffolis by local rewriting. Its author, nasqret, rebuilt the division itself, for example by keeping a shift count in the bits that the shift had just emptied. A change of that size cannot be found by looking at neighbouring gates.
Savings that accept failures. Truncated comparison windows, schedules cut to what inputs usually need, gates deleted because testing never saw them fire, and a test seed chosen so that nothing fails. On one circuit we measured that 92% of fresh runs fired a gate that 9,216 earlier runs never had, so deleting by screening is unsafe without a model of the tail.

FIG. 34 / LOOKING BACK: ALL 31, BY SHARE OF TOFFOLIS REMOVED AT THE SITE. HOVER A BAR.

SAVES TOFFOLIS OR LEAVES THEM UNCHANGEDPAYS TOFFOLIS TO SAVE QUBITSIN READING ORDER · MEASURED AT A REPRESENTATIVE SIZE

Of the thirty-one, six hold for any wires in a circuit of any size. The rest are proved at a fixed size, for every input and every measurement outcome, and several assume a fact about the surrounding circuit that must be proved separately. Qubit counts are stated but not machine-checked: the Lean model counts Toffolis and the wires a block touches, not peak width.

Savings quoted from contest entries are their authors' own figures. We did not re-measure them.

ABOUT THE AUTHOR

SSiddharth LalwaniFOUNDER, ALMOND LABS

Siddharth Lalwani is a quantum computing enthusiast building at the edge of adoption: bringing NISQ-era quantum solutions into real enterprise workflows. He is Co-Founder and CEO of Skate and was previously a Venture Partner at Nomad Capital.

X ↗Email ↗

10 / SOURCES

01Scoring rule and validation checks for point addition: the ecdsa.fail challenge README and harness, Layr-Labs/ecdsafail-challenge.

02Standings, dates and Toffoli counts in Sections 02 and 03: the contest's public submission data, read on 12 Nov 2026.

03The patterns and the steps in Section 03: public ecdsa.fail submissions, notes and code, reviewed read-only on 11 and 12 Nov 2026, by nasqret, jackylee0424, odinfree, Akashneelesh, RealAdii, gopikannappan, BitWonka, gnuchev, bulengerk, mochimodev, zuiris, mpjunior92, SnehalRaj, jieyilong, MonitSharma, haotang1995 and yashward001, and the authors of the circuit families they build on. Figures quoted from them are their authors' claims.

04Toggling a borrowed qubit twice (P27): Barenco, Bennett, Cleve, DiVincenzo, Margolus, Shor, Sleator, Smolin and Weinfurter, Elementary gates for quantum computation, Phys. Rev. A 52, 3457 (1995).

05Measured erasure, used throughout: Gidney, Halving the cost of quantum addition, Quantum 2, 74 (2018).

06The ladder inside P52: Khattar and Gidney, Rise of conditionally clean ancillae for efficient quantum circuit constructions, arXiv:2407.17966.

07Our own figures in Sections 02 and 09: our scored 647-qubit entry and replays on public entries, 10 and 11 Nov 2026.

08The first twenty-six patterns, and the background on scoring and measured erasure: Dispatch 1.

09Lean proofs, pattern cards and the tested Qiskit snippets for all 31 patterns: almond-lab/quantum-circuit-patterns.