# Design Patterns for Optimizing Quantum Circuits, Dispatch 2 By Siddharth Lalwani, Almond. Published 2026-11-12. Interactive version: https://almond.org/writing/quantum-circuit-design-patterns-2 Thirty-one circuit rewrites from the race for the fewest qubits on ecdsa.fail, each with an animated before and after circuit, Qiskit code, its effect on Toffoli and qubit counts, and a machine-checked Lean proof. ## The Short Version: When qubits run out, every helper has to earn its place. [Dispatch 1](https://almond.org/writing/quantum-circuit-design-patterns-1) collected twenty-six rewrites that mostly remove Toffoli gates. This one follows a different race. On [ecdsa.fail](https://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. ## 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. | 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. ## 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. | STEP | FIRST BY | WHAT WAS REMOVED | TOFFOLIS ON ARRIVAL | |---|---|---|---| | 676 → 675 | odinfree, 19 Oct | One lane of a ring dropped; the carry is read out of the middle of a sweep (P37). | 596.1M | | 666 → 660 | bulengerk, 21 to 22 Oct | Size codes, a payload cell left out where it is provably zero, and carry loans (P51 among others). | 545.4M | | 660 → 659 | odinfree, 8 Nov | A scratch role removed: every multi-controlled gate borrows busy lanes (P27). | 579.1M | | 659 → 658 | jackylee0424, 8 Nov | One lane evicted from every operation, then dropped. | 630.2M | | 657 → 653 | nasqret, 9 to 10 Nov | One 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 → 651 | jackylee0424, 10 Nov | Counter and rank bits hosted on idle wires or wires of known value (P41 among others). | 548.5M, then 608.5M | | 651 → 650 | Akashneelesh, 10 Nov; jackylee0424 the same afternoon | A counter bit parked, window by window, on lanes whose value is known. | 753.2M; 632.4M | | 650 → 649 | jackylee0424, 10 Nov | A tag relayed through zeros that the division itself creates. | 658.7M | | 649 → 648 | jackylee0424, 11 Nov; Akashneelesh six hours later | In Akashneelesh's entry, five small helper wires removed (P34 among others). | 713.6M; 674.9M | | 648 → 647 | jackylee0424, 11 Nov | The 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. ## 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: 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. - 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 Qiskit, before: ```python 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 ``` Qiskit, after: ```python 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 ``` ### P33 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. - 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 Qiskit, before: ```python 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 ``` Qiskit, after: ```python 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 ``` ### P29 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. - 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 Qiskit, before: ```python 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]) ``` Qiskit, after: ```python 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 ``` ### P51 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. - 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 Qiskit, before: ```python 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 ``` Qiskit, after: ```python 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 ``` ### P52 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. - 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 Qiskit, before: ```python 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 ``` Qiskit, after: ```python 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 ``` ### P56 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. - 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 Qiskit, before: ```python 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 ``` Qiskit, after: ```python 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 ``` ## 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 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. - 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 Qiskit, before: ```python 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 ``` Qiskit, after: ```python 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 ``` ### P37 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. - 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 Qiskit, before: ```python 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) ``` Qiskit, after: ```python 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 ``` ### P39 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. - 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 Qiskit, before: ```python 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 ``` Qiskit, after: ```python def after(): # skip the hole qc = QuantumCircuit(5) qc.cswap(C, X0, X1) qc.cswap(C, X0, X3) return qc ``` ### P41 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. - 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 Qiskit, before: ```python 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 ``` Qiskit, after: ```python 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 ``` ### P42 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. - 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 Qiskit, before: ```python 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 ``` Qiskit, after: ```python 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 ``` ### P43 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. - 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 Qiskit, before: ```python 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 ``` Qiskit, after: ```python 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 ``` ### P49 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. - 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 Qiskit, before: ```python 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 ``` Qiskit, after: ```python 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 ``` ## 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 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. - 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 Qiskit, before: ```python 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 ``` Qiskit, after: ```python 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 ``` ### P32 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. - 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 Qiskit, before: ```python 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 ``` Qiskit, after: ```python 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 ``` ### P36 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. - 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 Qiskit, before: ```python 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 ``` Qiskit, after: ```python 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 ``` ### P40 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. - 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 Qiskit, before: ```python 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 ``` Qiskit, after: ```python 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 ``` ### P44 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. - 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 Qiskit, before: ```python 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 ``` Qiskit, after: ```python 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 ``` ### P47 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. - 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 Qiskit, before: ```python 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 ``` Qiskit, after: ```python 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 ``` ### P50 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. - 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 Qiskit, before: ```python 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 ``` Qiskit, after: ```python 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 ``` ### P54 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. - 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 Qiskit, before: ```python 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 ``` Qiskit, after: ```python 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 ``` ## 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 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. - 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 Qiskit, before: ```python 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 ``` Qiskit, after: ```python 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 ``` ### P45 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. - 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 Qiskit, before: ```python 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 ``` Qiskit, after: ```python 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 ``` ### P55 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. - 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 Qiskit, before: ```python 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 ``` Qiskit, after: ```python 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 ``` ## 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 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. - 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 Qiskit, before: ```python 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 ``` Qiskit, after: ```python 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 ``` ### P35 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. - 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 Qiskit, before: ```python 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 ``` Qiskit, after: ```python 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 ``` ### P38 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. - 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 Qiskit, before: ```python 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 ``` Qiskit, after: ```python 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 ``` ### P46 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. - 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 Qiskit, before: ```python 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 ``` Qiskit, after: ```python 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 ``` ### P48 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. - 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 Qiskit, before: ```python 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 ``` Qiskit, after: ```python 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 ``` ### P53 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. - 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 Qiskit, before: ```python 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 ``` Qiskit, after: ```python 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 ``` ### P57 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. - 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 Qiskit, before: ```python 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 ``` Qiskit, after: ```python 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 ``` ## 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. 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. ## Sources 01. Scoring rule and validation checks for point addition: the ecdsa.fail challenge README and harness, Layr-Labs/ecdsafail-challenge. 02. Standings, dates and Toffoli counts in Sections 02 and 03: the contest's public submission data, read on 12 Nov 2026. 03. The 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. 04. Toggling 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). 05. Measured erasure, used throughout: Gidney, Halving the cost of quantum addition, Quantum 2, 74 (2018). 06. The ladder inside P52: Khattar and Gidney, Rise of conditionally clean ancillae for efficient quantum circuit constructions, arXiv:2407.17966. 07. Our own figures in Sections 02 and 09: our scored 647-qubit entry and replays on public entries, 10 and 11 Nov 2026. 08. The first twenty-six patterns, and the background on scoring and measured erasure: [Dispatch 1](https://almond.org/writing/quantum-circuit-design-patterns-1). 09. Lean proofs, pattern cards and the tested Qiskit snippets for all 31 patterns: almond-lab/quantum-circuit-patterns.