Toffoli gate

In plain terms

Ordinary logic gates throw information away, as an AND gate takes two bits to one and you can't run it backwards. Quantum evolution never throws information away, so a quantum computer can't use an AND gate directly, and the classical parts of a quantum algorithm have to be rebuilt out of reversible pieces.

The Toffoli gate is the piece that makes that possible. It takes three bits, leaves the first two alone, and flips the third when both of the first two are set, which is reversible because applying it twice returns you to where you started. Set the third bit to zero beforehand and it computes the AND of the other two into it, so anything a classical circuit does can be done with Toffoli gates and a supply of spare bits.

In a fault-tolerant machine the Toffoli gate is also the expensive one. The cheap gates are the ones a code handles qubit by qubit, and Toffoli is not among them, so it has to be assembled from magic states. That's why resource estimates for quantum algorithms are quoted as Toffoli counts rather than as total gate counts, as the Toffoli count is what the hardware budget actually tracks.

In CSD

The corpus makes cost a function of a circuit's gate list rather than a number annotated onto an opaque operation, so a statement that an operation costs at most so many Toffoli gates is a theorem: you exhibit a circuit, prove it computes the operation, and prove its counted cost. That design decision is what makes the arithmetic layer's resource accounting machine-checked rather than trusted.

The cost record bundles the standard fault-tolerant fields, qubit width, ancilla, Toffoli count and depth, controlled-not count, T count and measurements, and the composition lemmas keep the additive and non-additive fields apart, as counts add exactly while width combines by taking a maximum. Every adder, multiplier and modular gadget in the reversible layer then carries a proved Toffoli count, which is what the elliptic-curve resource estimates downstream consume. The honest boundary is that genuine width and ancilla accounting is a later refinement, as the current model fixes the width to the register size.

Mathematically

The gate type has X, CX (controlled-not), CCX (Toffoli) and swap constructors, each denoted by an involution of the state (Circuit.lean). gateCost assigns one Toffoli at depth one to CCX, one controlled-not to CX, three to a swap and nothing to X, and circuitCost reads each additive field off the gate list. cost_comp_toffoli_count is exact additivity of the Toffoli count under composition, cost_comp_toffoli_depth_le bounds depth subadditively, and cost_inverse_toffoli says inverting a circuit preserves the count.

There's deliberately no AddMonoid instance on the cost record, since the width fields are not additive under composition. Derived counts include cuccaroAdd_toffoli (2n for an n-bit in-place addition) and the AndAdd family, and cprop_toffoli_le shows constant propagation never increases the count.

The name

Tommaso Toffoli described the gate in 1980, while at MIT, in work on reversible computing that grew out of Edward Fredkin's question of whether computation must dissipate energy. The answer, that it need not, connects the gate to Landauer's principle: only erasure has a thermodynamic cost, and reversible circuits don't erase.

The gate's second life came with quantum computing, where Toffoli counts became the standard unit of algorithmic cost, and papers now compete on the Toffoli count of modular arithmetic much as classical cryptography once competed on multiplication counts.

Related entries

• reversible adderA reversible adder has to return its scratch space clean, and the carry-clean ripple-carry design does it with a single spare qubit, which is what makes arithmetic affordable inside a quantum algorithm.
• Clifford plus TClifford plus T is the standard universal gate set, as the Clifford gates alone are classically simulable and adding the single eighth-turn phase gate makes every unitary reachable to any accuracy you ask for.
• magic stateA magic state is the fuel of quantum advantage, a single special state that, consumed by otherwise classically trackable Clifford circuits, unlocks the one gate the Gottesman-Knill theorem can't simulate.
• Landauer's principleForgetting costs heat at a rate set by temperature alone, and that's the point at which information stops being an abstraction and acquires a physical price.
• Shor's algorithmShor's algorithm factors large numbers in polynomial time on a quantum computer, and it turned quantum computing from a curiosity into a budget line and made every deployed cryptosystem provisional.