Reversible Circuits and Cost Metrics

You now own a box of reversible parts — the NOT, the CNOT, the Toffoli — and you know from Bennett's uncompute trick how to clean up after a computation. This module is about the engineering question that follows: given a reversible function you want, how do you actually build a circuit for it — and how do you judge whether your circuit is any good? Before we can synthesise anything, we need two things every engineering discipline starts with: the rules of construction (what counts as a legal circuit) and a price list (what each design costs).

The circuit model: wires and a cascade

A reversible circuit on n wires is startlingly strict compared with the logic circuits you have met before:

n horizontal wires run left to right, one per bit. Every wire runs the whole way through — bits are never created or thrown away mid-circuit.
Gates are placed one after another in a cascade: a simple left-to-right sequence. Each gate touches only the wires it sits on and leaves the rest alone.
No fan-out. A wire may never split into two copies of itself.
No feedback. No wire may loop back to feed an earlier gate.

Both bans come straight from reversibility. Fan-out is copying: one bit goes in, two come out, and the map from the circuit's fixed set of n wires to itself is broken — a permutation must have exactly as many outputs as inputs. (If you want a copy of x, you must budget for it honestly: a CNOT writing onto a fresh 0 ancilla wire, (x, 0) \to (x, x) — a perfectly legal bijection.) Feedback is worse: with a loop, a wire's value at a given moment depends on itself, and the circuit no longer describes a clean function from inputs to outputs at all. A cascade with neither is guaranteed to compute a bijection — because it is a composition of bijections.

Reading a cascade: composed permutations

Each gate in the cascade is a small bijection on the 2^n possible states of the wires, so the whole circuit computes their composition, applied left to right. To evaluate a cascade on an input, just walk a state through it, one gate at a time. Step through the three-gate circuit below on the input abc = 100:

So this circuit sends 100 \to 110. Do that for all eight inputs and you have tabulated the permutation the circuit computes. Running the circuit right to left (each NCT gate is its own inverse) computes the inverse permutation — the whole point of building reversibly.

The NCT library

Almost all classical synthesis work uses one standard toolkit, the NCT library:

Gate	Wires	Action	Drawn as
NOT	1	a \to \bar a	a lone ⊕ on the wire
CNOT	2	(a,b) \to (a,\, b \oplus a)	control dot • joined to a target ⊕
Toffoli	3	(a,b,c) \to (a,\, b,\, c \oplus ab)	two dots joined to a target ⊕

The library is universal: with enough wires, every reversible function can be built from these three (the Toffoli alone is universal, in fact — it can simulate the other two on fixed inputs). Universality tells you a circuit exists; it says nothing about finding a good one. For that we need to agree what "good" means.

The price list: four cost metrics

Synthesis papers judge a circuit by four numbers, and they pull against each other:

Metric	What it counts	Why it matters
Gate count	the number of gates in the cascade	the crudest size measure — and the easiest to compare
Depth	the number of time-steps, where gates on disjoint wires may fire in the same step	latency: how long one pass through the circuit takes
Width / ancillas	total wires = data wires + extra ancilla wires	memory: every ancilla is a bit of workspace you must physically provide
Quantum cost	a weighted gate count, weighting each gate by how expensive it is on quantum hardware	reversible circuits are the skeleton of quantum ones, and there a Toffoli is far pricier than a CNOT

One number from the quantum-cost world is worth memorising now, as a teaser for where this course is heading: in fault-tolerant quantum accounting, a Toffoli costs about 7 T gates, while NOTs and CNOTs are nearly free. So a circuit with g NOTs, h CNOTs and k Toffolis has gate count g + h + k but T-flavoured quantum cost roughly 7k — which is why so much of synthesis is really a war on Toffolis.

Because gates on disjoint wires genuinely can fire at the same time. Picture a 6-wire circuit containing a NOT on wire 1, a CNOT on wires 2 and 3, and a Toffoli on wires 4, 5, 6: three gates, but no two share a wire, so all three can happen in a single tick — gate count 3, depth 1. Depth is the circuit-world version of parallel running time, and for physical reversible hardware (or a quantum computer, where every extra tick is extra decoherence) it can matter more than raw gate count. A long thin cascade and a short fat one may compute the same permutation at wildly different speeds.

In an ordinary schematic you split a wire with a dot and think nothing of it. In a reversible circuit that innocent dot is illegal: it duplicates a bit for free, and no permutation of a fixed set of wires can do that. The honest version costs real resources — one fresh ancilla wire prepared as 0, plus one CNOT: (x, 0) \to (x, x). So every "copy" in a reversible design shows up in the width metric and the gate count. This is not pedantry: charging honestly for copies is exactly what makes the energy accounting of reversible computing work, and (as you will see later in the course) it is also why quantum circuits — where even the ancilla-CNOT trick copies only classical values, never superpositions — inherit this rule so naturally.