# Design Patterns for Optimizing Quantum Circuits, Dispatch 1

By Siddharth Lalwani, Almond. Published 2026-11-11. Interactive version: https://almond.org/writing/quantum-circuit-design-patterns-1

Twenty-six small rewrites that contestants used in two public quantum-circuit contests, 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: Most of a circuit's cost is cleanup, and cleanup can be made nearly free.

Two public contests opened in 2026 that ask the same question: here is a quantum subroutine, make it cheaper. [ecdsa.fail](https://ecdsa.fail) asks for one elliptic-curve point addition, the inner loop of Shor's algorithm against Bitcoin and Ethereum signatures. Google Quantum AI's [Kaggle contest](https://www.kaggle.com/competitions/google-verifiable-quantum-circuit-compilation) asks for three subroutines from physics simulation, optimization and chemistry.

Thousands of teams, many of them working with AI coding agents, pushed those circuits down by large factors. When you read what they actually did, the same few dozen moves come up again and again. This dispatch collects twenty-six of them as design patterns: a small block of circuit, a cheaper block that does the same job, and the conditions under which the swap is safe.

Each pattern below has an animated before and after, the same block written in Qiskit, a plain statement of what it does to every cost function the contests use, and a proof checked by the Lean theorem prover. Three short sections first explain what is being counted and why.

## The Scoreboard: Two numbers decide everything: Toffolis and qubits.

Neither contest scores speed on a real device. Both score two counts taken from the circuit itself: **how many Toffoli gates** it runs and **how many qubits** it needs at its widest point. Toffolis stand for running time, qubits stand for the size of the machine, and their product is roughly machine size times running time.

A product has one practical virtue: it sets an exchange rate. Almost any circuit can trade a scratch qubit for fewer Toffolis or the reverse, and a product only rewards trades that are a real net gain. Google's own two reference designs for point addition show it: one is narrow and slow, one is wide and fast, and their scores are within 7% of each other.

Two details of these formulas shape the patterns. First, both contests count the Toffolis **actually executed, averaged over runs**. A gate that is applied only when a measurement came out 1 costs half. Second, the weighting is a choice: in the DQI task qubits are squared, so, in the paper's words, "a 1% reduction in qubits improves the score as much as a 2% reduction in Toffoli gates". A trade that pays on one scoreboard can lose on another.

## Why One Gate Is Expensive: Error correction can do most gates directly. Not this one.

These circuits are meant for an error-corrected machine, where each logical qubit is spread over many physical ones and constantly checked. On such a machine the gates split into two classes. **Clifford gates** (X, CNOT, CZ, measurement) turn simple errors into simple errors, so the code can keep tracking them, and they are cheap. The gates that complete the set, T and Toffoli, do not have that property, and a theorem says no code can do every gate the safe way.

So a Toffoli is done indirectly. A helper qubit is prepared in a special "magic" state, many noisy copies are distilled into a few clean ones, and the gate is transferred onto the data using only Clifford gates and a measurement. The ecdsa.fail README states the consequence in one line:

Faster point addition ⇒ fewer Toffoli gates ⇒ fewer magic states ⇒ less physical hardware and less wall-clock time on a fault-tolerant quantum computer.

That is why the scoreboards charge for Toffolis and for nothing else. It is also the opening every pattern in the next section walks through: if a Toffoli can be replaced by a measurement and a Clifford gate, the scoreboard sees it as free.

## How A Laptop Referees: No Hadamards, so an ordinary program can check every step.

A general quantum circuit cannot, in practice, be checked on a classical computer once it is more than a few dozen qubits wide. These can, because of what they leave out. The contest circuits contain reversible logic, sign and phase gates, and a "measure in the X basis and reset" step, but no Hadamard. Without it a circuit never branches: give it a definite input and every gate maps one bit string to one bit string, possibly with a sign attached.

So the referee runs the circuit like an ordinary program, keeping one bit per qubit and one running sign. If the bits and the sign are right on every input, the circuit is right on every superposition of inputs, because quantum mechanics is linear. A saving that comes from skipping cleanup or leaving a stray sign fails this check instead of scoring.

Try it on the simplest pattern in this dispatch. A scratch qubit t receives a AND b, is measured, and a repair gate fires when the outcome is 1. Flip the inputs and the outcome: the sign always comes back to plus.

The Lean proofs in this dispatch use exactly this model: a state is a list of bits, a sign, and a record of measurement outcomes. A pattern is proved by showing that the rewritten block and the original agree on bits and sign for every input and every outcome.

## Part 1 · Erase By Measurement: Forgetting does not need the expensive gate.

Quantum circuits are full of scratch values: a carry, a flag, a table entry, a product. Each one has to be returned to zero before its qubit can be reused, and the textbook way is to run the computation backwards, paying for it a second time.

The seven patterns in this part all rest on one observation. Measuring a scratch qubit in the X basis reveals nothing about its value, so the data survives. It only leaves a possible minus sign, and that sign can be cancelled by a gate the scoreboard does not charge for.

The code under each figure is Qiskit. Two idioms recur. "Measure in the X basis and reset" is written `qc.h(q); qc.measure(q, c); qc.reset(q)`, and a gate that fires only when a measurement came out 1 sits inside `with qc.if_test((c, 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 on random inputs.

### P01 Erase a temporary AND by measurement

A scratch qubit t holds a AND b. The textbook cleanup applies the same Toffoli again, so every temporary AND costs two Toffolis.

Measure t in the X basis and reset it. If the outcome m is 1, the branches where t was 1 picked up a minus sign; a CZ on a and b puts a second minus sign on exactly those branches, and the two cancel.

- Before: Uncompute with a second Toffoli: 2. After: Measure and fix: 1 (toffolis per temporary and).
- Toffolis: lower. 2 → 1 per temporary AND.
- Qubits: same. Same scratch qubit; adds one classical bit.
- Toffoli × qubit scores: lower. Falls by the share of Toffolis that were cleanup; close to half in adder-heavy circuits.
- Q² × Toffoli (DQI): lower. Same Toffoli gain; width is untouched.
- Needs: a and b unchanged since the compute; mid-circuit measurement and classical control
- Seen in: Throughout the public circuits of both contests (Gidney 2018)
- Proof: QCP.P01.correct, all inputs and both outcomes

Qiskit, before:

```python
from qiskit import QuantumCircuit

def before():
    a, b, t = 0, 1, 2
    qc = QuantumCircuit(3)
    qc.ccx(a, b, t)  # t = a AND b
    # ... use t ...
    qc.ccx(a, b, t)  # uncompute with a second Toffoli
    return qc
```

Qiskit, after:

```python
def after():
    a, b, t = 0, 1, 2
    qc = QuantumCircuit(3, 1)
    qc.ccx(a, b, t)  # t = a AND b
    # ... use t ...
    # measure in X, reset
    qc.h(t); qc.measure(t, 0); qc.reset(t)
    with qc.if_test((qc.clbits[0], 1)):
        qc.cz(a, b)  # repair the sign
    return qc
```

### P04 Ripple-carry adder with measured carries

An n-bit adder computes n−1 carries, each a majority of three bits, and must remove them again. Doing both with Toffolis costs 2(n−1).

Each carry is one temporary AND, so P01 applies to every one of them. The reverse sweep is still there, but it is made of CNOTs, measurements and conditional CZs. The animation shows one bit position.

- Before: Carries removed with Toffolis: 2(n−1). After: Carries measured away: n−1 (toffolis, n-bit adder).
- Toffolis: lower. 2(n−1) → n−1: every adder halves.
- Qubits: same. n−1 carry qubits either way.
- Toffoli × qubit scores: lower. Up to 2× on adder-heavy circuits such as point addition.
- Q² × Toffoli (DQI): depends. Lower if the carries fit under the peak width; otherwise see P12.
- Needs: n−1 clean carry qubits for the duration of the addition
- Seen in: Adders throughout both contests (Gidney 2018)
- Proof: QCP.P04.correct8, 8 bits, every input and record

Qiskit, before:

```python
from qiskit import QuantumCircuit

def before():  # one bit position of the adder
    # c = carry in, c2 = carry out
    a, b, c, c2 = 0, 1, 2, 3
    qc = QuantumCircuit(4)
    qc.cx(c, a); qc.cx(c, b)
    # c2 = majority(a, b, c)
    qc.ccx(a, b, c2); qc.cx(c, c2)
    # ... higher bits use c2 ...
    # remove the carry: a Toffoli
    qc.cx(c, c2); qc.ccx(a, b, c2)
    qc.cx(c, a); qc.cx(a, b)  # b = a + b + c
    return qc
```

Qiskit, after:

```python
def after():
    a, b, c, c2 = 0, 1, 2, 3
    qc = QuantumCircuit(4, 1)
    qc.cx(c, a); qc.cx(c, b)
    qc.ccx(a, b, c2); qc.cx(c, c2)
    # ... higher bits use c2 ...
    qc.cx(c, c2)
    # measure the carry away
    qc.h(c2); qc.measure(c2, 0); qc.reset(c2)
    with qc.if_test((qc.clbits[0], 1)):
        qc.cz(a, b)
    qc.cx(c, a); qc.cx(a, b)
    return qc
```

### P05 Erase a bilinear product by measurement

A register holds c = a·b, where the product is bilinear over GF(2): a carry-less product or a finite-field product. Uncomputing it means running the multiplier a second time.

Measure every bit of c in the X basis. The leftover sign is a sum of terms aᵢ·bⱼ with classically known coefficients, which is exactly what a set of CZ gates cancels. The multiplier runs once.

- Before: Uncompute with the multiplier: 2r. After: Measure, then CZ pairs: r (toffolis, r = multiplier rank).
- Toffolis: lower. Uncompute costs 0 instead of the multiplier rank r (42 for GF(4096)).
- Qubits: same. No extra qubits.
- Toffoli × qubit scores: lower. Halves every multiply-then-erase.
- Q² × Toffoli (DQI): lower. Used throughout the public DQI decoders.
- Needs: Both factors still present and unchanged at repair time (or defer the repair, P06)
- Seen in: Kaggle DQI decoders erase GF(4096) words this way throughout
- Proof: QCP.P05.correct4, 4×4 product, all inputs and 2⁷ records

Qiskit, before:

```python
from qiskit import QuantumCircuit
# c = a * b, carry-less, 2 x 2 bits
A, B, C = [0, 1], [2, 3], [4, 5, 6]

def multiply(qc):
    for i in range(2):
        for j in range(2):
            qc.ccx(A[i], B[j], C[i + j])

def before():
    qc = QuantumCircuit(7)
    multiply(qc)
    # ... use c ...
    multiply(qc)  # uncompute: the multiplier again
    return qc
```

Qiskit, after:

```python
def after():
    qc = QuantumCircuit(7, 3)
    multiply(qc)
    # ... use c ...
    for k in range(3):
        qc.h(C[k]); qc.measure(C[k], k); qc.reset(C[k])
        with qc.if_test((qc.clbits[k], 1)):
            # CZ for every term a_i b_j of c_k
            for i in range(2):
                if 0 <= k - i < 2:
                    qc.cz(A[i], B[k - i])
    return qc
```

### P07 Multi-controlled X through an AND ladder

A flag that depends on n controls (an equality test, a zero test, a lookup address match) is built as a ladder of ANDs and then taken down again: 2n−3 Toffolis.

Take the ladder down from the top with P01. Each rung is erased while the two qubits it was made from are still alive, so every repair is a CZ.

- Before: Ladder down with Toffolis: 5. After: Ladder measured away: 3 (toffolis, 4 controls (2n−3 → n−1)).
- Toffolis: lower. 2n−3 → n−1 (5 → 3 in the animation).
- Qubits: same. Same n−2 ladder qubits.
- Toffoli × qubit scores: lower. Applies to every test and address decode.
- Q² × Toffoli (DQI): lower. If the ladder is kept across its use: 11 instead of 24 for a 12-bit zero test.
- Needs: n−2 clean ladder qubits; erase in reverse order of computation
- Seen in: Kaggle DQI scan: an 11-AND zero test at each of 4,025 positions
- Proof: QCP.P07.correct6, 6 controls

Qiskit, before:

```python
from qiskit import QuantumCircuit

def before():  # target ^= c0 c1 c2 c3
    c0, c1, c2, c3, tgt, u1, u2 = range(7)
    qc = QuantumCircuit(7)
    qc.ccx(c0, c1, u1)
    qc.ccx(u1, c2, u2)
    qc.ccx(u2, c3, tgt)
    qc.ccx(u1, c2, u2)  # ladder down: two more Toffolis
    qc.ccx(c0, c1, u1)
    return qc
```

Qiskit, after:

```python
def after():
    c0, c1, c2, c3, tgt, u1, u2 = range(7)
    qc = QuantumCircuit(7, 2)
    qc.ccx(c0, c1, u1)
    qc.ccx(u1, c2, u2)
    qc.ccx(u2, c3, tgt)
    qc.h(u2); qc.measure(u2, 0); qc.reset(u2)
    with qc.if_test((qc.clbits[0], 1)):
        qc.cz(u1, c2)  # u1 is still alive
    qc.h(u1); qc.measure(u1, 1); qc.reset(u1)
    with qc.if_test((qc.clbits[1], 1)):
        qc.cz(c0, c1)
    return qc
```

### P10 Measure-first peephole

A Toffoli writes into a qubit that is X-measured and reset before anything else reads it.

Swap the order. Measuring first and applying a conditional CZ afterwards gives the same state, with no condition on what the target held. P01 is the special case where the target held a·b.

- Before: Toffoli, then measure: 1. After: Measure, then conditional CZ: 0 (toffolis per site).
- Toffolis: lower. 1 → 0 at each site.
- Qubits: same. Unchanged.
- Toffoli × qubit scores: lower. Small: only where generators left such a pair.
- Q² × Toffoli (DQI): lower. Same.
- Needs: Nothing reads the target between the Toffoli and the measurement
- Seen in: Clean-up passes on Kaggle circuits
- Proof: QCP.P10.ccx_then_measure, any wires

Qiskit, before:

```python
from qiskit import QuantumCircuit

def before():
    a, b, t = 0, 1, 2
    qc = QuantumCircuit(3, 1)
    qc.ccx(a, b, t)
    qc.h(t); qc.measure(t, 0); qc.reset(t)
    return qc
```

Qiskit, after:

```python
def after():
    a, b, t = 0, 1, 2
    qc = QuantumCircuit(3, 1)
    # measure first
    qc.h(t); qc.measure(t, 0); qc.reset(t)
    with qc.if_test((qc.clbits[0], 1)):
        qc.cz(a, b)  # the Toffoli became a CZ
    return qc
```

### P16 A controlled swap before two measurements is free

Two wires are conditionally swapped and then both measured in the X basis. The swap costs one Toffoli per pair of wires.

Write a XOR b onto the second wire with a CNOT, measure the first wire, apply a conditional CZ between the control and the second wire, then measure it. The original outcomes are recovered as r = u XOR v and s = v.

- Before: Swap, then measure both: 1. After: CNOT, measure, CZ, measure: 0 (toffolis per swapped pair).
- Toffolis: lower. 1 → 0 per swapped pair.
- Qubits: same. Unchanged.
- Toffoli × qubit scores: lower. Applies wherever a swap feeds a readout.
- Q² × Toffoli (DQI): lower. 48 Toffolis per run in the DQI frontier, as reported in those write-ups.
- Needs: Both wires measured with nothing in between; later repairs read the relabelled bits
- Seen in: Kaggle DQI frontier: 48 controlled swaps removed (public write-ups)
- Proof: QCP.P16.correct and .record

Qiskit, before:

```python
from qiskit import QuantumCircuit

def before():
    c, a, b = 0, 1, 2
    qc = QuantumCircuit(3, 2)
    qc.cswap(c, a, b)
    qc.h(a); qc.measure(a, 0); qc.reset(a)  # outcome r
    qc.h(b); qc.measure(b, 1); qc.reset(b)  # outcome s
    return qc
```

Qiskit, after:

```python
def after():
    c, a, b = 0, 1, 2
    qc = QuantumCircuit(3, 2)
    qc.cx(a, b)  # b holds a XOR b
    qc.h(a); qc.measure(a, 0); qc.reset(a)  # outcome u
    with qc.if_test((qc.clbits[0], 1)):
        qc.cz(c, b)
    qc.h(b); qc.measure(b, 1); qc.reset(b)  # outcome v
    # downstream: use r = u XOR v and s = v
    return qc
```

### P25 Measurement-based unlookup

A register holds the table entry T[address] for an L-entry table. Clearing it by running the lookup again costs as much as the lookup, L−2 Toffolis.

Measure the register. The leftover sign is one classical bit per address. Split the address in two halves, make a one-hot code of each, and apply CZ between them wherever that bit is 1. Only the two one-hot codes cost Toffolis.

- Before: Unload by a second lookup: 28. After: Measure, then phase fix: 16 (toffolis, 16-entry table, load + unload).
- Toffolis: lower. L−2 → about 2√L, whatever the word width (14 → 2 for 16 entries).
- Qubits: same. Scratch for the one-hot code reuses the freed register when it is wide enough.
- Toffoli × qubit scores: lower. Nearly halves every load-use-unload.
- Q² × Toffoli (DQI): lower. Same, if the one-hot code fits under the peak.
- Needs: Address unchanged; about √L scratch qubits, usually the ones just freed
- Seen in: Lookups in the Kaggle 1/√x and DQI circuits (Berry et al. 2019)
- Proof: QCP.P25.correct, 16 entries, 2¹⁸ records

Qiskit, before:

```python
from qiskit import QuantumCircuit
TABLE = [2, 1, 3, 0]  # 4 entries, 2-bit words

def lookup(qc):  # out ^= TABLE[address]
    for i, word in enumerate(TABLE):
        flip = [q for q in (0, 1) if not (i >> q) & 1]
        if flip: qc.x(flip)
        for j in (0, 1):
            if (word >> j) & 1:
                qc.ccx(0, 1, 2 + j)
        if flip: qc.x(flip)

def before():
    qc = QuantumCircuit(4)
    lookup(qc)
    # ... use out ...
    lookup(qc)  # unload: the lookup again
    return qc
```

Qiskit, after:

```python
def after():
    qc = QuantumCircuit(4, 2)
    lookup(qc)
    # ... use out ...
    for j in (0, 1):
        qc.h(2 + j); qc.measure(2 + j, j); qc.reset(2 + j)
        # bit j of every entry
        f = [(w >> j) & 1 for w in TABLE]
        # sign (-1)^f[address]
        with qc.if_test((qc.clbits[j], 1)):
            if f[0] ^ f[1]: qc.z(0)
            if f[0] ^ f[2]: qc.z(1)
            if f[0] ^ f[1] ^ f[2] ^ f[3]: qc.cz(0, 1)
    return qc
```

## Part 2 · Merge And Cancel: Some savings need no understanding of the circuit at all.

The next five are identities on gates that are already there. They do not need to know what the circuit computes, so they can run as an automatic pass over a finished gate list. Each site saves one or two Toffolis; a circuit with half a billion gates has a lot of sites.

We ran the first two as a post-pass on other teams' ecdsa.fail circuits. The cancellation rule alone took 1.35% off the official score of a 651-qubit entry. That is also roughly where local rewriting ends: larger gains need the kind of knowledge in Part 3.

### P02 Cancel a Toffoli pair across commuting gates

The same Toffoli appears twice with other gates in between. Generators produce this wherever one block's cleanup is followed by a neighbouring block's setup.

A Toffoli is its own inverse. If every gate between the two copies commutes with it, slide one copy next to the other and both disappear. A Toffoli commutes with any gate that does not write its controls or read its target.

- Before: Toffoli, commuting gates, same Toffoli: 2. After: Only the gates in between remain: 0 (toffolis per pair).
- Toffolis: lower. −2 per pair found.
- Qubits: same. Unchanged.
- Toffoli × qubit scores: lower. Measured on ecdsa.fail: −1.1% (652 qubits) and −1.35% (651 qubits) of the official score.
- Q² × Toffoli (DQI): lower. Proportional to the pairs found; frontier circuits have few left.
- Needs: Both copies under the same classical condition; everything in between commutes
- Seen in: Our ecdsa.fail post-pass: 6.1M and 8.4M Toffolis removed from a 652- and a 651-qubit circuit
- Proof: QCP.P02.cancel_across and three commutation lemmas, any wires

Qiskit, before:

```python
from qiskit import QuantumCircuit

def before():
    a, b, t, u = 0, 1, 2, 3
    qc = QuantumCircuit(4)
    qc.ccx(a, b, t)
    qc.cx(a, u)  # these commute with the Toffoli:
    qc.cz(b, u)  # they never write a, b or read t
    qc.ccx(a, b, t)
    return qc
```

Qiskit, after:

```python
def after():
    a, b, t, u = 0, 1, 2, 3
    qc = QuantumCircuit(4)
    qc.cx(a, u)
    qc.cz(b, u)
    return qc
```

### P03 Merge two Toffolis that share two wires

Two Toffolis write a·b and a·c into the same target.

a·b XOR a·c equals a·(b XOR c). Form b XOR c in place with a CNOT, apply one Toffoli, and undo the CNOT. The same works for two Toffolis with the same controls and different targets.

- Before: a·b and a·c into one target: 2. After: a·(b XOR c): 1 (toffolis).
- Toffolis: lower. 2 → 1 per merge.
- Qubits: same. Unchanged.
- Toffoli × qubit scores: lower. Measured on ecdsa.fail: a further −0.14%.
- Q² × Toffoli (DQI): lower. Proportional to merges found.
- Needs: No ancilla. Gates between the two must commute with both
- Seen in: Our ecdsa.fail post-pass: 832,694 merges on the 651-qubit circuit
- Proof: QCP.P03.merge_shared_control_target, any wires

Qiskit, before:

```python
from qiskit import QuantumCircuit

def before():
    a, b, c, t = 0, 1, 2, 3
    qc = QuantumCircuit(4)
    qc.ccx(a, b, t)  # t ^= a b
    qc.ccx(a, c, t)  # t ^= a c
    return qc
```

Qiskit, after:

```python
def after():
    a, b, c, t = 0, 1, 2, 3
    qc = QuantumCircuit(4)
    qc.cx(c, b)  # b holds b XOR c
    qc.ccx(a, b, t)  # t ^= a (b XOR c)
    qc.cx(c, b)
    return qc
```

### P13 One Toffoli for a product of sums

Four Toffolis add a·c, a·d, b·c and b·d into one target.

The four terms are (a XOR b)·(c XOR d). Two CNOTs form the sums in place, one Toffoli multiplies them, two CNOTs restore the inputs. The same conjugation delivers one product to several targets at once.

- Before: One Toffoli per term: 4. After: (a XOR b)·(c XOR d): 1 (toffolis).
- Toffolis: lower. 4 → 1 (and 3 → 1 for one product sent to three targets).
- Qubits: same. No ancilla.
- Toffoli × qubit scores: lower. The basis of the chemistry loaders' Toffoli counts.
- Q² × Toffoli (DQI): lower. Used inside field multipliers (P20).
- Needs: All four inputs alive together; target not read in between
- Seen in: Kaggle chemistry loaders: lookup compilers count products of sums, not monomials
- Proof: QCP.P13.paired_product and .fanout3, any wires

Qiskit, before:

```python
from qiskit import QuantumCircuit

def before():
    a, b, c, d, t = range(5)
    qc = QuantumCircuit(5)
    qc.ccx(a, c, t)
    qc.ccx(a, d, t)
    qc.ccx(b, c, t)
    qc.ccx(b, d, t)
    return qc
```

Qiskit, after:

```python
def after():
    a, b, c, d, t = range(5)
    qc = QuantumCircuit(5)
    # a holds a XOR b, c holds c XOR d
    qc.cx(b, a); qc.cx(d, c)
    qc.ccx(a, c, t)  # t ^= (a XOR b)(c XOR d)
    qc.cx(d, c); qc.cx(b, a)
    return qc
```

### P15 Phase fold through a dirty target

A Toffoli writes a·b into t, a CZ between c and t reads it, and the same Toffoli removes it again.

The CZ sees t XOR a·b, so its effect is a CZ on c and t plus a sign on a·b·c. That sign is a single CCZ. The qubit t can hold anything.

- Before: Toffoli, CZ, Toffoli: 2. After: CCZ and CZ: 1 (toffolis).
- Toffolis: lower. 2 → 1 per fold.
- Qubits: same. Unchanged.
- Toffoli × qubit scores: lower. Tiny in practice: few sites exist.
- Q² × Toffoli (DQI): lower. Seven Toffolis out of about 395,000.
- Needs: Nothing else touches t or c between the three gates
- Seen in: Kaggle DQI frontier: seven folds in a 395,000-Toffoli circuit (public write-up)
- Proof: QCP.P15.phase_fold, any wires

Qiskit, before:

```python
from qiskit import QuantumCircuit

def before():
    a, b, c, t = 0, 1, 2, 3
    qc = QuantumCircuit(4)
    qc.ccx(a, b, t)
    qc.cz(c, t)
    qc.ccx(a, b, t)
    return qc
```

Qiskit, after:

```python
def after():
    a, b, c, t = 0, 1, 2, 3
    qc = QuantumCircuit(4)
    qc.ccz(a, b, c)
    qc.cz(c, t)
    return qc
```

### P24 A quadratic form costs its rank, not its number of terms

Three Toffolis add a·b, b·c and c·a into a target: the majority of three bits, which is every adder carry.

The sum equals (a XOR c)·(b XOR c) XOR c. In general, k products added into one target can be rewritten as r products of sums, where r is the rank of the quadratic form (Dickson). P03 and P13 are rank-one cases.

- Before: One Toffoli per term: 3. After: (a XOR c)·(b XOR c) XOR c: 1 (toffolis).
- Toffolis: lower. 3 → 1 here; k terms → rank in general.
- Qubits: same. No ancilla.
- Toffoli × qubit scores: lower. Already built into good generators, so little is left for a post-pass.
- Q² × Toffoli (DQI): lower. Same.
- Needs: All operands alive at the same time
- Seen in: Adder carries everywhere; rank sweeps on Kaggle circuits found nothing left over
- Proof: QCP.P24.majority, any wires. The general theorem is not formalised

Qiskit, before:

```python
from qiskit import QuantumCircuit

def before():  # t ^= majority(a, b, c)
    a, b, c, t = 0, 1, 2, 3
    qc = QuantumCircuit(4)
    qc.ccx(a, b, t)
    qc.ccx(b, c, t)
    qc.ccx(a, c, t)
    return qc
```

Qiskit, after:

```python
def after():
    a, b, c, t = 0, 1, 2, 3
    qc = QuantumCircuit(4)
    qc.cx(c, a); qc.cx(c, b)
    qc.ccx(a, b, t)  # (a XOR c)(b XOR c)
    qc.cx(c, t)  # ... XOR c
    qc.cx(c, b); qc.cx(c, a)
    return qc
```

## Part 3 · Cheaper Building Blocks: The biggest savings come from knowing what the block is for.

A general-purpose optimizer sees gates. A circuit generator knows it is building a lookup, a shift, or a multiplication in a finite field, and can pick a better construction for exactly that job. These ten patterns are such constructions.

Several of them depend on a fact about the data: a wire that is known to be zero, a factor that is a known constant, an address that has not changed. That is why they live in generators and not in compilers.

### P08 Linear maps cost no Toffolis

Multiplying a field element by a known constant with a general multiplier means loading the constant into a scratch word and paying the full multiplier.

Multiplication by a constant is a linear map over GF(2), and so are squaring, basis changes and cyclic shifts. Any invertible linear map is a network of CNOTs and swaps, applied in place. The animation multiplies by x in GF(16).

- Before: General multiplier with a loaded constant: r. After: Three swaps and one CNOT, in place: 0 (toffolis, multiply by a known constant).
- Toffolis: lower. Multiplier rank r → 0.
- Qubits: lower. No scratch word for the constant.
- Toffoli × qubit scores: lower. Both factors fall.
- Q² × Toffoli (DQI): lower. Doubly useful: the saved word counts twice.
- Needs: One factor classical. Worth restructuring an algorithm so that it is
- Seen in: Kaggle DQI decoders: evaluation steps and constant multiplications
- Proof: QCP.P08.correct (one instance; the general fact is linear algebra)

Qiskit, before:

```python
from qiskit import QuantumCircuit
# GF(4): w^2 = w + 1; out ^= w * x
X, OUT, K = [0, 1], [2, 3], [4, 5]

def before():
    qc = QuantumCircuit(6)
    qc.x(K[1])  # load the constant w = (0, 1)
    qc.ccx(X[0], K[0], OUT[0]); qc.ccx(X[1], K[1], OUT[0])
    qc.ccx(X[0], K[1], OUT[1]); qc.ccx(X[1], K[0], OUT[1])
    # general multiplier: 5 Toffolis
    qc.ccx(X[1], K[1], OUT[1])
    qc.x(K[1])  # unload
    return qc
```

Qiskit, after:

```python
def after():
    qc = QuantumCircuit(6)
    # w * (x0 + x1 w) = x1 + (x0 + x1) w
    qc.cx(X[1], OUT[0])
    qc.cx(X[0], OUT[1]); qc.cx(X[1], OUT[1])
    # in place it is just: qc.swap(X[0], X[1]); qc.cx(X[0], X[1])
    return qc
```

### P09 Controlled swap from one Toffoli

A controlled swap is its own gate in both contests' gate sets and is counted as one Toffoli.

It equals a CNOT, a Toffoli and a CNOT. The count does not change, but once swaps are written this way the merge and cancel rules of Part 2 apply to them, and so does P17.

- Before: Controlled swap: 1. After: CNOT, Toffoli, CNOT: 1 (toffolis per bit · an enabling identity).
- Toffolis: same. 1 per swapped bit either way.
- Qubits: same. Unchanged.
- Toffoli × qubit scores: same. No gain alone; it exposes swaps to P02, P03, P13 and P17.
- Q² × Toffoli (DQI): same. Same.
- Needs: Nothing
- Seen in: Barrel shifters in the Kaggle 1/√x circuits
- Proof: QCP.P09.cswap_eq, any wires

Qiskit, before:

```python
from qiskit import QuantumCircuit

def before():
    c, a, b = 0, 1, 2
    qc = QuantumCircuit(3)
    qc.cswap(c, a, b)
    return qc
```

Qiskit, after:

```python
def after():
    c, a, b = 0, 1, 2
    qc = QuantumCircuit(3)
    qc.cx(b, a)
    qc.ccx(c, a, b)  # the one Toffoli inside a CSWAP
    qc.cx(b, a)
    return qc
```

### P11 Add or subtract under a control with one adder

A signed-digit multiplier or a modular step must compute b + a or b − a depending on a qubit s. Building a controlled adder and a controlled subtractor costs about two adders.

b − a equals NOT(NOT b + a). XOR s into every bit of b, run one ordinary adder, and XOR s in again. The control costs only CNOTs.

- Before: Two controlled blocks: ≈2n. After: Complement, add, complement: ≈n (toffolis, n-bit add or subtract).
- Toffolis: lower. The second adder disappears: about 2 adders → 1.
- Qubits: same. Unchanged.
- Toffoli × qubit scores: lower. Halves each selected add/subtract.
- Q² × Toffoli (DQI): not applicable. Not seen in the public DQI decoders.
- Needs: Nothing beyond the adder's own ancillas
- Seen in: Signed-digit multiplier rows in Kaggle 1/√x generators
- Proof: QCP.P11.correct8, 8 bits

Qiskit, before:

```python
from qiskit import QuantumCircuit
from qiskit.circuit.library import ModularAdderGate
# b = b + a if s = 0, b - a if s = 1
S, A, B = 0, [1, 2, 3], [4, 5, 6]
ADD = ModularAdderGate(3)  # b += a (mod 8)

def before():
    qc = QuantumCircuit(7)
    qc.x(S)
    # controlled add
    qc.append(ADD.control(1), [S, *A, *B])
    qc.x(S)
    # controlled subtract
    qc.append(ADD.inverse().control(1), [S, *A, *B])
    return qc
```

Qiskit, after:

```python
def after():
    qc = QuantumCircuit(7)
    qc.cx(S, B)  # complement b when s = 1
    qc.append(ADD, [*A, *B])  # one plain adder
    qc.cx(S, B)  # NOT(NOT b + a) = b - a
    return qc
```

### P14 Table lookup by unary iteration

Loading T[address] from an L-entry classical table by testing each address separately costs a multi-controlled gate per entry.

Walk a binary tree of flags meaning "the address starts with this prefix". The flag for a 1-branch comes from the flag of its 0-branch sibling with a single CNOT (the sawtooth step shown here), and flags are erased by measurement.

- Before: Rebuild the flag for each branch: L(n−1). After: Sawtooth: one CNOT to the next branch: L−2 (toffolis, l-entry table).
- Toffolis: lower. L(n−1) → L−2.
- Qubits: higher. One more flag qubit than the per-entry test.
- Toffoli × qubit scores: lower. A factor of about n−1 in Toffolis outweighs one qubit.
- Q² × Toffoli (DQI): lower. Still clearly lower.
- Needs: n−1 flag qubits for an n-bit address
- Seen in: The standard lookup the Kaggle baselines start from (Babbush et al. 2018)
- Proof: QCP.P14.sawtooth (any wires) and .correct (8 entries)

Qiskit, before:

```python
from qiskit import QuantumCircuit

def before():
    p, a, flag = 0, 1, 2  # p = "prefix matches so far"
    qc = QuantumCircuit(3)
    # flag = p AND NOT a
    qc.x(a); qc.ccx(p, a, flag); qc.x(a)
    # ... load the entries of branch 0 ...
    # take the flag down
    qc.x(a); qc.ccx(p, a, flag); qc.x(a)
    qc.ccx(p, a, flag)  # rebuild it: flag = p AND a
    # ... load the entries of branch 1 ...
    return qc
```

Qiskit, after:

```python
def after():
    p, a, flag = 0, 1, 2
    qc = QuantumCircuit(3)
    # flag = p AND NOT a
    qc.x(a); qc.ccx(p, a, flag); qc.x(a)
    # ... load the entries of branch 0 ...
    qc.cx(p, flag)  # sawtooth: flag = p AND a
    # ... load the entries of branch 1 ...
    return qc
```

### P17 Controlled swap into a wire known to be zero

A shift stage moves a bit into a neighbouring wire with a controlled swap and moves it back later: two Toffolis per bit.

If the destination is known to be zero, the swap is an AND into it followed by a CNOT. The way back is then a CNOT and a measured erase of that AND (P01), which is free.

- Before: Swap out, swap back: 2. After: AND-move out, measured move back: 1 (toffolis per bit, round trip).
- Toffolis: lower. 2 → 1 per bit for the round trip.
- Qubits: same. Unchanged.
- Toffoli × qubit scores: lower. Lower on the 1/√x task, where shifts are about a tenth of the Toffolis.
- Q² × Toffoli (DQI): not applicable. Not seen in the public DQI decoders.
- Needs: The destination wire is zero on every input that can occur: a fact the generator must track
- Seen in: Kaggle 1/√x barrel shifters (46 controlled swaps on the frontier)
- Proof: QCP.P17.move (any wires) and .roundTrip_correct

Qiskit, before:

```python
from qiskit import QuantumCircuit

def before():
    f, x, y = 0, 1, 2  # y is known to be 0
    qc = QuantumCircuit(3)
    qc.cswap(f, x, y)  # move x to y if f
    # ... use the shifted bits ...
    qc.cswap(f, x, y)  # move it back
    return qc
```

Qiskit, after:

```python
def after():
    f, x, y = 0, 1, 2
    qc = QuantumCircuit(3, 1)
    # same move, since y was 0
    qc.ccx(f, x, y); qc.cx(y, x)
    # ... use the shifted bits ...
    qc.cx(y, x)  # now y = f AND x again
    qc.h(y); qc.measure(y, 0); qc.reset(y)
    with qc.if_test((qc.clbits[0], 1)):
        qc.cz(f, x)
    return qc
```

### P18 GF(8) inversion with 3 Toffolis and a free erase

The inverse in the 8-element field is x⁶ = x²·x⁴: one field product to compute it and one more to uncompute it.

Each output bit of the inverse is a polynomial of degree 2 in the input bits, so three Toffolis compute it directly, and an in-place form needs no output register. Because the degree is 2, the result is erased by measurement with Z and CZ repairs only.

- Before: Inverse as a field product: 12. After: Degree-2 formulas, measured erase: 3 (toffolis, compute + erase).
- Toffolis: lower. 12 → 3 for compute plus erase.
- Qubits: lower. The in-place form saves the 3-qubit output register.
- Toffoli × qubit scores: lower. Both factors fall.
- Q² × Toffoli (DQI): lower. Inversion of GF(4096) is built on this leaf (66 Toffolis in public generators).
- Needs: Nothing. General rule: any register of degree ≤ 2 in live wires is erased for free
- Seen in: Leaf of tower-field inversion in Kaggle DQI decoders
- Proof: QCP.P18.compute_correct, .erase_correct, .inPlace_correct

Qiskit, before:

```python
from qiskit import QuantumCircuit
# y = 1/x in GF(8), x^3 = x + 1
X, Y = [0, 1, 2], [3, 4, 5]

def inverse(qc):  # three degree-2 formulas
    qc.cx(X[0], Y[0]); qc.cx(X[1], Y[0]); qc.cx(X[2], Y[0])
    qc.ccx(X[1], X[2], Y[0])
    qc.cx(X[2], Y[1]); qc.ccx(X[0], X[1], Y[1])
    qc.cx(X[1], Y[2]); qc.cx(X[2], Y[2]); qc.ccx(X[0], X[2], Y[2])

def before():
    qc = QuantumCircuit(6)
    inverse(qc)
    # ... use y ...
    inverse(qc)  # uncompute: 3 more Toffolis
    return qc
```

Qiskit, after:

```python
def after():
    qc = QuantumCircuit(6, 3)
    inverse(qc)
    # ... use y ...
    for k in range(3):
        qc.h(Y[k]); qc.measure(Y[k], k); qc.reset(Y[k])
    with qc.if_test((qc.clbits[0], 1)):
        qc.z(X); qc.cz(X[1], X[2])
    with qc.if_test((qc.clbits[1], 1)):
        qc.z(X[2]); qc.cz(X[0], X[1])
    with qc.if_test((qc.clbits[2], 1)):
        qc.z(X[1]); qc.z(X[2]); qc.cz(X[0], X[2])
    return qc
```

### P20 GF(8) multiplier with 6 Toffolis and no ancilla

Multiplying two 3-bit field elements term by term needs nine ANDs.

Six products of sums are enough: a₀c₀, a₁c₁, a₂c₂, (a₀+a₁)(c₀+c₁), (a₀+a₂)(c₀+c₂), (a₁+a₂)(c₁+c₂). Sums are formed in place with CNOTs and each product is delivered to its output bits by CNOT conjugation (P13). Six is the minimum.

- Before: Schoolbook: 9. After: Karatsuba-style products of sums: 6 (toffolis per gf(8) product).
- Toffolis: lower. 9 → 6.
- Qubits: same. No ancilla in either form.
- Toffoli × qubit scores: lower. A third off every field product.
- Q² × Toffoli (DQI): lower. The DQI decoders are built from field products.
- Needs: Nothing; the target may hold data
- Seen in: Leaf of the GF(4096) multiplier in Kaggle DQI: 7 × 6 = 42 Toffolis
- Proof: QCP.P20.correct, all inputs, dirty target

Qiskit, before:

```python
from qiskit import QuantumCircuit
# t ^= a * c in GF(8)
A, C, T = [0, 1, 2], [3, 4, 5], [6, 7, 8]

def before():  # one Toffoli per term
    qc = QuantumCircuit(9)
    for i, j, k in [(0, 0, 0), (0, 1, 1), (0, 2, 2), (1, 0, 1),
                    (1, 1, 2), (1, 2, 0), (1, 2, 1), (2, 0, 2),
                    (2, 1, 0), (2, 1, 1), (2, 2, 1), (2, 2, 2)]:
        qc.ccx(A[i], C[j], T[k])
    return qc
```

Qiskit, after:

```python
def after():  # six products of sums
    qc = QuantumCircuit(9)
    for bits, outs in [((0,), (0, 1, 2)), ((1,), (0, 2)), ((2,), (0,)),
                       ((0, 1), (1,)), ((0, 2), (2,)), ((1, 2), (0, 1))]:
        p, o = bits[0], outs[0]
        for q in bits[1:]:
            # sums in place
            qc.cx(A[q], A[p]); qc.cx(C[q], C[p])
        for r in outs[1:]:
            qc.cx(T[o], T[r])  # fan out
        qc.ccx(A[p], C[p], T[o])
        for r in outs[1:]:
            qc.cx(T[o], T[r])
        for q in bits[1:]:
            qc.cx(A[q], A[p]); qc.cx(C[q], C[p])
    return qc
```

### P21 Load the difference of two tables

A register holds T[address] and should next hold T′[address]. Unloading one table and loading the other is two lookups.

Loading XORs data into the register, so a single lookup of the table T XOR T′ turns one into the other. Planners then order the loads so that the difference tables are cheap.

- Before: Unload, then load: 2(L−2). After: One load of the difference: L−2 (toffolis, l-entry tables).
- Toffolis: lower. 2(L−2) → L−2.
- Qubits: same. Unchanged.
- Toffoli × qubit scores: lower. Loaders are over half the chemistry Toffolis.
- Q² × Toffoli (DQI): not applicable. Not seen in the public DQI decoders.
- Needs: The address is unchanged between the two loads
- Seen in: Kaggle chemistry loaders: consecutive angle words
- Proof: QCP.P21.correct, 8 entries

Qiskit, before:

```python
from qiskit import QuantumCircuit
# register holds T1[address]
T1, T2 = [2, 1, 3, 0], [1, 1, 0, 2]

def lookup(qc, table):  # reg ^= table[address]
    for i, word in enumerate(table):
        flip = [q for q in (0, 1) if not (i >> q) & 1]
        if flip: qc.x(flip)
        for j in (0, 1):
            if (word >> j) & 1:
                qc.ccx(0, 1, 2 + j)
        if flip: qc.x(flip)

def before():
    qc = QuantumCircuit(4)
    lookup(qc, T1)  # unload T1
    lookup(qc, T2)  # load T2
    return qc
```

Qiskit, after:

```python
def after():
    qc = QuantumCircuit(4)
    # one load
    lookup(qc, [x ^ y for x, y in zip(T1, T2)])
    return qc
```

### P23 Put the control on one operand

A product a·c should be added to the target only when a control qubit s is 1. Adding a control to every Toffoli of the multiplier roughly doubles it.

s·(a·c) equals (s·a)·c. Mask a with n temporary ANDs, run the plain multiplier on the masked copy, and erase the mask by measurement. The control can be injected wherever the data is narrowest.

- Before: Control every Toffoli: ≈2r. After: Mask one operand: n + r (toffolis, controlled product of rank r).
- Toffolis: lower. About 2r → n + r (12 → 9 for GF(8)).
- Qubits: higher. n mask qubits during the product.
- Toffoli × qubit scores: depends. Lower if the mask fits under the peak width.
- Q² × Toffoli (DQI): depends. Check the peak first: here a qubit is worth twice as much.
- Needs: n clean qubits for the masked operand while the product runs
- Seen in: Controlled products and reciprocals in Kaggle DQI decoders
- Proof: QCP.P23.correct, GF(8)

Qiskit, before:

```python
from qiskit import QuantumCircuit
S, A, C, T, MASK = 0, [1, 2], [3, 4], [5, 6, 7], [8, 9]
# t ^= s * (a * c), carry-less 2 x 2 product

def before():
    qc = QuantumCircuit(10)
    for i in range(2):
        # every Toffoli gains a control
        for j in range(2):
            qc.mcx([S, A[i], C[j]], T[i + j])
    return qc
```

Qiskit, after:

```python
def after():
    qc = QuantumCircuit(10, 2)
    for i in range(2):
        qc.ccx(S, A[i], MASK[i])  # mask = s * a
    for i in range(2):
        for j in range(2):
            # plain multiplier
            qc.ccx(MASK[i], C[j], T[i + j])
    for i in range(2):
        qc.h(MASK[i]); qc.measure(MASK[i], i); qc.reset(MASK[i])
        with qc.if_test((qc.clbits[i], 1)):
            qc.cz(S, A[i])
    return qc
```

### P26 Controlled GF(8) inverse with a partial mask

A decoder needs y ^= c·inv(x): the inverse added to the target only when a control is 1. Composing P23 and P18 literally masks all three bits of x and then inverts the masked copy: six Toffolis and three helper qubits.

Mask only x₀ and x₁. The three remaining products are built so that the ones carrying x₂ also supply its linear terms, and they are written straight into the output. Two helpers are measured away with CZ repairs. A separate chained program reaches 4 Toffolis with 4 helpers, so the two forms trade width against gates.

- Before: Mask everything, then invert: 6. After: Fused, partial mask: 5 (toffolis · helper qubits 3 → 2).
- Toffolis: lower. 6 → 5. The public chained form reaches 4.
- Qubits: lower. 3 → 2 helpers. The 4-AND form needs 4.
- Toffoli × qubit scores: lower. Block alone: 60 → 45 (the 4-AND form: 44).
- Q² × Toffoli (DQI): lower. Block alone: 600 → 405, ahead of the 4-AND form (484) when helpers set the peak.
- Needs: Two clean helpers; polynomial basis x³+x+1 with inv(0) = 0
- Seen in: Found by search in our component research (R01). A public Kaggle generator has the 4-AND form
- Proof: QCP.P26.fused_correct and .fourAnd_correct, all inputs and records

Qiskit, before:

```python
from qiskit import QuantumCircuit
C, X, Y, H = 0, [1, 2, 3], [4, 5, 6], [7, 8, 9]
# y ^= c * (1/x) in GF(8)

def before():  # mask all of x, then invert
    qc = QuantumCircuit(10, 3)
    for i in range(3):
        qc.ccx(C, X[i], H[i])
    qc.cx(H, Y[0]); qc.ccx(H[1], H[2], Y[0])
    qc.cx(H[2], Y[1]); qc.ccx(H[0], H[1], Y[1])
    qc.cx(H[1], Y[2]); qc.cx(H[2], Y[2]); qc.ccx(H[0], H[2], Y[2])
    for i in range(3):
        qc.h(H[i]); qc.measure(H[i], i); qc.reset(H[i])
        with qc.if_test((qc.clbits[i], 1)):
            qc.cz(C, X[i])
    return qc
```

Qiskit, after:

```python
def after():  # mask x0 and x1 only
    u, v = H[0], H[1]
    qc = QuantumCircuit(10, 2)
    qc.ccx(C, X[0], u); qc.ccx(C, X[1], v)
    qc.cx(u, C); qc.ccx(X[2], C, Y[2]); qc.cx(u, C)
    qc.cx(v, C); qc.cx(Y[0], Y[1])
    qc.ccx(X[2], C, Y[0])
    qc.cx(Y[0], Y[1]); qc.cx(v, C)
    qc.cx(X[2], X[0]); qc.ccx(v, X[0], Y[1]); qc.cx(X[2], X[0])
    qc.cx(u, Y[0]); qc.cx(v, Y[0]); qc.cx(v, Y[2])
    for i, h in enumerate((u, v)):
        qc.h(h); qc.measure(h, i); qc.reset(h)
        with qc.if_test((qc.clbits[i], 1)):
            qc.cz(C, X[i])
    return qc
```

## Part 4 · Fewer Qubits: Sometimes the right move is to pay Toffolis for width.

Everything so far lowered the Toffoli count. The last four work on the other factor. They free a qubit earlier or never allocate a register, sometimes at a small Toffoli price.

Whether such a trade pays depends on two things: the scoreboard, and whether the block sits at the circuit's widest point. Below the peak, a spare qubit is free and the cheap-in-Toffolis form wins. At the peak, one qubit is worth the circuit's total Toffolis divided by its width, and twice that when qubits are squared.

### P06 Repair order and deferred repair

A scratch qubit u = a·b is needed only to make t = u·c. Keeping u alive until t has been used and removed holds a qubit for the whole stretch.

Free u at once by measurement. Later, t is erased by measurement too; its repair would need u, which is gone, so it becomes a conditional CCZ on a, b and c. That gate runs only when the outcome is 1, so it costs half a Toffoli on average. The repair can also be postponed until some wire holds the value again.

- Before: u held until the end: 4. After: u freed before the use: 2.5 (mean toffolis · u is free during the use).
- Toffolis: lower. 4 → 2.5 on average in the animation.
- Qubits: lower. u is free during the use. In DQI decoders this frees whole 12-bit words early.
- Toffoli × qubit scores: lower. Both factors fall when the stretch sets the peak.
- Q² × Toffoli (DQI): lower. Qubits count twice here; a main reason the DQI forward pass is cheap.
- Needs: Classical bits kept until the repair; mean-executed gate counting for the half price
- Seen in: Kaggle DQI frontier: about 200 words measured without repair in the forward pass
- Proof: QCP.P06.lateCubic_correct and .deferred_correct

Qiskit, before:

```python
from qiskit import QuantumCircuit

def before():  # d ^= a b c
    a, b, c, d, u, t = range(6)
    qc = QuantumCircuit(6)
    qc.ccx(a, b, u)
    qc.ccx(u, c, t)
    qc.cx(t, d)  # use t (u is held all along)
    qc.ccx(u, c, t)
    qc.ccx(a, b, u)
    return qc
```

Qiskit, after:

```python
def after():
    a, b, c, d, u, t = range(6)
    qc = QuantumCircuit(6, 2)
    qc.ccx(a, b, u)
    qc.ccx(u, c, t)
    # free u right away
    qc.h(u); qc.measure(u, 0); qc.reset(u)
    with qc.if_test((qc.clbits[0], 1)):
        qc.cz(a, b)
    qc.cx(t, d)  # use t; u is available to others
    qc.h(t); qc.measure(t, 1); qc.reset(t)
    with qc.if_test((qc.clbits[1], 1)):
        qc.ccz(a, b, c)  # runs half the time
    return qc
```

### P12 In-place carries versus measured carries

The measured-carry adder of P04 is the cheapest in Toffolis but needs n−1 clean carry qubits. If the adder runs at the circuit's widest point, those qubits set the peak.

The Cuccaro adder stores each carry in the a register and needs one ancilla in total, at twice the Toffolis. Mixed forms hold k carries in place: k more Toffolis for k fewer qubits.

- Before: n−1 carry qubits: n−1. After: 1 ancilla: 1 (ancilla qubits, n-bit adder · toffolis double).
- Toffolis: higher. +k Toffolis for k carries held in place (up to 2× the adder).
- Qubits: lower. −k qubits, down to one ancilla.
- Toffoli × qubit scores: depends. Pays only at the peak: one qubit is worth (total Toffolis ÷ peak qubits) Toffolis.
- Q² × Toffoli (DQI): depends. A qubit is worth twice as much: 886 Toffolis in the DQI frontier (measured).
- Needs: A decision per adder: is it at the peak width or below it?
- Seen in: Kaggle 1/√x generators (carries kept in place for the low bits)
- Proof: QCP.P12.correct8 (Cuccaro) and QCP.P04.correct8

Qiskit, before:

```python
from qiskit import QuantumCircuit
N = 3
A, B = [0, 1, 2], [3, 4, 5]  # b += a (mod 8)

def before():  # measured carries: N-1 ancillas
    c = [6, 7]
    qc = QuantumCircuit(8, N - 1)
    qc.ccx(A[0], B[0], c[0])
    for i in range(1, N - 1):
        qc.cx(c[i - 1], A[i]); qc.cx(c[i - 1], B[i])
        qc.ccx(A[i], B[i], c[i]); qc.cx(c[i - 1], c[i])
    qc.cx(c[N - 2], B[N - 1]); qc.cx(A[N - 1], B[N - 1])
    for i in range(N - 2, 0, -1):
        qc.cx(c[i - 1], c[i])
        qc.h(c[i]); qc.measure(c[i], i); qc.reset(c[i])
        with qc.if_test((qc.clbits[i], 1)):
            qc.cz(A[i], B[i])
        qc.cx(c[i - 1], A[i]); qc.cx(A[i], B[i])
    qc.h(c[0]); qc.measure(c[0], 0); qc.reset(c[0])
    with qc.if_test((qc.clbits[0], 1)):
        qc.cz(A[0], B[0])
    qc.cx(A[0], B[0])
    return qc
```

Qiskit, after:

```python
def after():  # Cuccaro: carries live in a
    z = 6  # the only ancilla
    qc = QuantumCircuit(8)
    chain = [z] + A
    for i in range(N - 1):  # MAJ
        qc.cx(A[i], B[i]); qc.cx(A[i], chain[i])
        qc.ccx(chain[i], B[i], A[i])
    qc.cx(A[N - 1], B[N - 1]); qc.cx(A[N - 2], B[N - 1])
    for i in range(N - 2, -1, -1):  # UMA
        qc.ccx(chain[i], B[i], A[i])
        qc.cx(A[i], chain[i]); qc.cx(chain[i], B[i])
    return qc
```

### P19 Erase an adder carry after its source is freed

A multiplier adds a row bit a = s₁·s₂ into an accumulator. The carry out of that position depends on a, so a is normally held until the carry has been erased.

Free a right after the forward step. When the carry is measured later, the missing term is s₁·s₂ times a bit that is still on a wire, so the repair is one conditional CCZ: half a Toffoli on average.

- Before: a held across the higher bits: 2. After: a freed at once: 2.5 (mean toffolis · one qubit fewer held).
- Toffolis: higher. 2 → 2.5 on average per streamed position.
- Qubits: lower. −1 held product qubit per position.
- Toffoli × qubit scores: depends. Lower when the multiplier sets the peak, as in the 62-qubit 1/√x frontier.
- Q² × Toffoli (DQI): not applicable. Not seen in the public DQI decoders.
- Needs: s₁, s₂, the carry-in and the sum bit unchanged; mean-executed counting
- Seen in: Kaggle 1/√x generators (function phasefix in a public research dump)
- Proof: QCP.P19.correct, all inputs and records

Qiskit, before:

```python
from qiskit import QuantumCircuit

def step(qc, a, b, c, d):  # b = a + b + c, d = carry out
    qc.cx(c, a); qc.cx(c, b)
    qc.ccx(a, b, d); qc.cx(c, d)
    qc.cx(c, a); qc.cx(a, b)

def before():  # a = s1 s2 is held to the end
    s1, s2, b, c, a, d = range(6)
    qc = QuantumCircuit(6, 2)
    qc.ccx(s1, s2, a)
    step(qc, a, b, c, d)
    # ... higher bits use d ...
    qc.cx(c, d); qc.cx(a, b); qc.cx(c, a)
    qc.h(d); qc.measure(d, 1); qc.reset(d)
    with qc.if_test((qc.clbits[1], 1)):
        qc.cz(a, b)  # needs a
    qc.cx(c, a); qc.cx(a, b)
    qc.h(a); qc.measure(a, 0); qc.reset(a)
    with qc.if_test((qc.clbits[0], 1)):
        qc.cz(s1, s2)
    return qc
```

Qiskit, after:

```python
def after():  # a is freed right after the step
    s1, s2, b, c, a, d = range(6)
    qc = QuantumCircuit(6, 2)
    qc.ccx(s1, s2, a)
    step(qc, a, b, c, d)
    qc.h(a); qc.measure(a, 0); qc.reset(a)
    with qc.if_test((qc.clbits[0], 1)):
        qc.cz(s1, s2)
    # ... higher bits use d; a's qubit is free ...
    qc.cx(c, d)
    qc.h(d); qc.measure(d, 1); qc.reset(d)
    with qc.if_test((qc.clbits[1], 1)):
        qc.cz(c, b)
        qc.cx(c, b); qc.x(b)
        qc.ccz(s1, s2, b)  # runs half the time
        qc.x(b); qc.cx(c, b)
    return qc
```

### P22 Phase a shifted bit through one temporary qubit

A rotation must act on a bit of a register after a controlled shift. Shifting the whole register, rotating and shifting back costs two controlled swaps per bit and a full shifted copy.

A rotation only needs the value on some wire. Compute the selected bit z = r XOR f·(r XOR r′) onto one clean qubit with one Toffoli, rotate z, measure z, and repair the sign with Z and CZ. The same qubit serves every bit in turn.

- Before: Swap, rotate, swap back: 2. After: Select onto z, rotate, measure: 1 (toffolis per phased bit).
- Toffolis: lower. 2 → 1 per phased bit and shift stage.
- Qubits: lower. No shifted copy of the register; one temporary qubit in total.
- Toffoli × qubit scores: lower. Both factors fall on the 1/√x task.
- Q² × Toffoli (DQI): not applicable. The DQI task allows no rotations.
- Needs: One clean qubit; the shift flag and both source bits unchanged during the step
- Seen in: Kaggle 1/√x frontier (62 qubits): bit-serial phasing
- Proof: QCP.P22.correct, every rotation angle

Qiskit, before:

```python
from math import pi
from qiskit import QuantumCircuit
THETA = pi / 8

def before():  # rotate r if f = 0, r2 if f = 1
    f, r, r2 = 0, 1, 2
    qc = QuantumCircuit(4)
    qc.cswap(f, r, r2)
    qc.p(THETA, r)
    qc.cswap(f, r, r2)
    return qc
```

Qiskit, after:

```python
def after():
    f, r, r2, z = 0, 1, 2, 3
    qc = QuantumCircuit(4, 1)
    qc.cx(r, z)
    # z = the selected bit
    qc.cx(r2, r); qc.ccx(f, r, z); qc.cx(r2, r)
    qc.p(THETA, z)
    qc.h(z); qc.measure(z, 0); qc.reset(z)
    with qc.if_test((qc.clbits[0], 1)):
        qc.z(r)
        qc.cx(r2, r); qc.cz(f, r); qc.cx(r2, r)
    return qc
```

## What A Proof Buys: A test covers the inputs you tried. A proof covers the rest.

The contests check circuits on thousands of random inputs. That is strong evidence for a finished circuit, but it says nothing about the next size up, and rare inputs slip through: on one ecdsa.fail circuit we found that 92% of fresh runs fired some gate that 9,216 earlier runs never had.

Each pattern here is stated as a theorem instead. Eight 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. Qubit counts are stated but not machine-checked: the Lean model counts Toffolis and the wires a block touches, not peak width.

The Kaggle paper itself closes by suggesting that future submissions "could pair a circuit generator with a proof of its correctness and cost". The next dispatch takes the patterns that are only proved at fixed sizes and proves them for all sizes.

## Sources

01. Scoring rule, validation checks and reference numbers for point addition: the ecdsa.fail challenge README and harness, Layr-Labs/ecdsafail-challenge.
02. The three Kaggle benchmarks, their score formulas and the outlook on machine-checked proofs: Khattar, Rubin, Gidney, Broughton, Low and Babbush, Verifiable quantum circuit compilation, the paper distributed with the contest.
03. Temporary AND and measured carries (P01, P04): Gidney, Halving the cost of quantum addition, Quantum 2, 74 (2018).
04. Unary iteration (P14): Babbush, Gidney, Berry, Wiebe, McClean, Paler, Fowler and Neven, Encoding electronic spectra in quantum circuits with linear T complexity, arXiv:1805.03662.
05. Measurement-based unlookup (P25): Berry, Gidney, Motzoi, McClean and Babbush, arXiv:1902.02134.
06. In-place ripple-carry adder (P12): Cuccaro, Draper, Kutin and Moulton, arXiv:quant-ph/0410184.
07. Constructions seen in the Kaggle contest (P05 to P08, P15 to P23, the 4-AND form in P26): public notebooks, write-ups and research dumps by contestants, including gluzdov, syed3000, maoxin123, gengsr, atakanaldemir, kirilltym, marculera and manwithacat, under Apache-2.0 or CC0 where a licence is stated. Figures quoted from them are their authors' claims.
08. Measured ecdsa.fail figures in Part 2 and Section 09: our own scored submissions and replays on the public 651- and 652-qubit entries, 10 Nov 2026.
09. Background for Sections 03 and 04: Gottesman, The Heisenberg representation of quantum computers (1998); Eastin and Knill, Restrictions on transversal encoded quantum gate sets (2009); Bravyi and Kitaev, Universal quantum computation with ideal Clifford gates and noisy ancillas (2005).
10. Lean proofs, pattern cards and the tested Qiskit snippets for all 26 patterns: almond-lab/quantum-circuit-patterns.