Controlled Gates and Reversible Classical Computation

Classical logic erases; quantum gates may not

An AND gate takes four possible input pairs to two possible outputs, and three of the four inputs collapse to output 0. Which input you started with is gone. Ordinary hardware gets away with this because the erased bit is dumped as heat and nobody looks back.

A closed quantum system has no such option. Its evolution is unitary, and every unitary has an inverse, so a gate that merged two different inputs into the same output would break the mathematics the whole circuit model stands on. If you want classical logic inside a coherent quantum computation, you have to embed it in a transformation that keeps enough information to run backward.

Controlled gates are the tool for that embedding. CNOT leaves its control qubit untouched and flips the target only when the control is 1. Toffoli extends the pattern to two controls, flipping its target only when both are 1. Add one spare output wire — an ancilla — and Toffoli gives you a reversible AND: the inputs survive, and the answer lands on the spare.

The exact basis action

Everything about CNOT is in one line:

Read out over the computational basis, that rule is:

Every input pair maps to a distinct output pair, which is exactly what makes the gate reversible: given the output, you can reconstruct the input. Notice also what the line does not say — the control is never read or measured. The gate applies a branch-dependent rule to the amplitudes.

Toffoli is the same idea one level up:

The inputs $a$ and $b$ pass through unchanged; their AND is XORed into $z$. Start $z$ at 0 and the target ends up holding exactly $a\wedge b$, with nothing erased.

Worked example: a superposition through a controlled gate

First the four basis inputs, with the first qubit as control:

control  target  ->  output
0        0            0 0
0        1            0 1
1        0            1 1
1        1            1 0

Nothing surprising yet — on basis states, CNOT behaves like a conditional classical XOR. Now feed it a superposition:

Apply the basis rule to each term separately — linearity demands it — and you get:

That output is the Bell state of Chapter 20's preparation circuit, one Hadamard earlier. The controlled gate did not copy a hidden classical value from control to target. It acted on every branch of the superposition at once, and the branches came out correlated in a way that no factoring into separate qubits can describe.

Where the copy story breaks

The most common misstatement about CNOT is that it copies the control onto the target. That sentence survives only in one narrow case: a known computational-basis input with the target initialized to 0. For an unknown qubit it fails outright — Chapter 21 shows why no gate can do that job — and even for superpositions it describes the wrong thing, because what the gate produces is entanglement, not a duplicate.

The second trap is reaching for an irreversible function directly. If your subroutine computes something like AND by overwriting its inputs, it cannot be the whole quantum operation. The fixes are mechanical but easy to skip under deadline: add ancilla registers, embed the function reversibly, and uncompute the scratch when you are done with it.

The engineering view: compute, use, uncompute

If you write software, think of reversibility as a compiler restriction: every function you emit must be invertible from its outputs. No overwriting variables you still owe, no dropping temporaries on the floor. The standard pattern for classical logic inside a quantum algorithm has three steps:

1. Compute the function into ancilla registers, leaving the inputs intact.
2. Use the result — as a phase, as a control, or as output.
3. Uncompute the scratch, returning the ancillas to their initial state.

The last step is not hygiene for its own sake. If scratch registers stay entangled with the answer, the later interference — the mechanism every quantum speedup depends on — comes out wrong. Oracles, arithmetic, phase estimation, and error-correction circuits all lean on this pattern, which is why serious resource estimates count ancillas and cleanup gates, not just the headline logic.

What to audit in a quantum software stack

When you evaluate a quantum SDK or compiler, ask how it handles reversible arithmetic, ancilla allocation, and uncomputation. A demo that counts only high-level logical functions can hide most of its real cost in controls, temporary registers, and cleanup — and the hidden part is often what blows the error budget on hardware.

A credible toolchain shows you the compiled circuit, not just the source-level sketch. If you cannot audit reversibility and gate counts at the level the device will execute, you are reviewing a brochure.

Exercise

Reversible AND, by hand. Write out the full truth table for CNOT from its basis action, then build the Toffoli-based reversible AND for all four input pairs with the target initialized to 0.

• Submit: the truth table for ordinary irreversible AND, the table for the Toffoli version, and one sentence marking where each table preserves information.
• Check: confirm every row of the reversible table has a unique output tuple — if two inputs shared an output, the gate could not be undone.
• Repair: if a row loses an input bit, or you caught yourself treating CNOT as a measurement of the control, rework Chapter 16 (Circuit Notation as a Programming Language) before continuing.

Check your understanding

Without notes: trace CNOT on all four computational-basis inputs, state the control-target convention you used, and explain in one sentence why the gate is reversible.

Oral defense: explain to a colleague why a quantum AND needs a third wire, and what goes wrong later in the algorithm if the scratch qubits are never uncomputed.

If you get stuck

If your traces drift on which wire is the control, or your explanations lean on copying or measuring the control, go back to Chapter 16 (Circuit Notation as a Programming Language) and rework the gate conventions there. This chapter assumes that vocabulary cold.