Part III. Circuit Model · Chapter 18
Controlled Gates and Reversible Classical Computation
Every classical program throws information away, and a quantum circuit is not allowed to. This chapter shows how controlled gates make classical logic reversible — CNOT and Toffoli, traced branch by branch — and why "the gate copies the control" is the first sentence to unlearn.
In this chapter 8 sections
Reader question. How does a controlled quantum gate apply different operations coherently without measuring its control?
A controlled-U is a block-diagonal unitary that applies identity on the control-0 subspace and U on the control-1 subspace; linearity applies both branches to a superposition, which can create entanglement while preserving reversibility.
- This chapter does not describe control wires as classical if their states may be superposed.
- It does not equate CNOT's basis-state copying behavior with cloning arbitrary states.
A branch rule encoded in one unitary
Write controlled-U as projectors on the control.
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.
Evidence boundary. Controlled unitary gates condition coherent evolution without measuring the control. [Michael A. Nielsen] [John Preskill]
CNOT on all four basis states
Establish the exact permutation and inverse.
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 and pass through unchanged; their AND is XORed into . Start at 0 and the target ends up holding exactly , with nothing erased.
Evidence boundary. CNOT is a reversible basis-state permutation and can entangle superposed inputs. [John Watrous] [Michael A. Nielsen]
A superposed control changes the joint state
Trace |+0> into a Bell pair without measurement.
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.
Evidence boundary. Toffoli supports reversible embeddings of classical logic. [Charles H. Bennett] [Michael A. Nielsen]
Notation contract: Control is the first qubit; basis order declared; C(U)=|0><0|⊗I+|1><1|⊗U; no implicit measurement.
Toffoli embeds a classical condition
Connect reversible Boolean logic to multi-control gates.
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:
- Compute the function into ancilla registers, leaving the inputs intact.
- Use the result; as a phase, as a control, or as output.
- 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.
Uncompute the condition
Use controlled operations without leaving branch information behind.
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.
Controlled-gate branch tracer
| Field | Reader-visible record |
|---|---|
| Format | Two-qubit simulator with block-matrix and basis-permutation views |
| Verification | Tests all basis inputs, a superposed input, inverse behavior, entanglement detection, and clean uncomputation. |
| Availability | Source-embedded acceptance record; no separate download is claimed |
{
"artifact": "Controlled-gate branch tracer",
"format": "Two-qubit simulator with block-matrix and basis-permutation views",
"acceptance_test": "Tests all basis inputs, a superposed input, inverse behavior, entanglement detection, and clean uncomputation.",
"publication_state": "source-embedded contract and worked fixture"
}Executable reference fixture
Run with Python 3.11 or later. The final assertion is the chapter-level pass condition for this small instance.
import math
def controlled_x(state, controls, target, qubits):
if target in controls or len(set(controls)) != len(controls) or any(not 0 <= wire < qubits for wire in (*controls, target)):
raise ValueError("controls and target must be distinct valid wires")
control_masks = tuple(1 << (qubits - 1 - wire) for wire in controls)
target_mask = 1 << (qubits - 1 - target)
output = [0j] * len(state)
for basis, amplitude in enumerate(state):
enabled = all(basis & mask for mask in control_masks)
output[basis ^ target_mask if enabled else basis] += amplitude
return output
def basis_state(bits):
state = [0j] * (1 << len(bits))
state[int(bits, 2)] = 1.0
return state
def purity_of_wire(state, wire, qubits):
mask = 1 << (qubits - 1 - wire)
rho = [[0j, 0j], [0j, 0j]]
for left, amplitude_left in enumerate(state):
for right, amplitude_right in enumerate(state):
if (left & ~mask) == (right & ~mask):
bit_left = 1 if left & mask else 0
bit_right = 1 if right & mask else 0
rho[bit_left][bit_right] += amplitude_left * amplitude_right.conjugate()
return sum(abs(value) ** 2 for row in rho for value in row).real
cnot_outputs = set()
for control in (0, 1):
for target in (0, 1):
bits = f"{control}{target}"
output = controlled_x(basis_state(bits), (0,), 1, 2)
observed = next(index for index, amplitude in enumerate(output) if abs(amplitude) > 0.9)
expected = 2 * control + (target ^ control)
assert observed == expected
cnot_outputs.add(observed)
assert len(cnot_outputs) == 4
toffoli_outputs = set()
for basis in range(8):
output = controlled_x(basis_state(format(basis, "03b")), (0, 1), 2, 3)
observed = next(index for index, amplitude in enumerate(output) if abs(amplitude) > 0.9)
a, b, target = (basis >> 2) & 1, (basis >> 1) & 1, basis & 1
assert observed == (basis & 0b110) | (target ^ (a & b))
toffoli_outputs.add(observed)
assert len(toffoli_outputs) == 8
scale = math.sqrt(0.5)
plus_zero = [scale, 0, scale, 0]
bell = controlled_x(plus_zero, (0,), 1, 2)
bell_purity = purity_of_wire(bell, 0, 2)
assert abs(bell_purity - 0.5) < 1e-12
controls_plus_target_zero = [0j] * 8
for index in (0b000, 0b010, 0b100, 0b110):
controls_plus_target_zero[index] = 0.5
computed = controlled_x(controls_plus_target_zero, (0, 1), 2, 3)
computed_purity = purity_of_wire(computed, 2, 3)
uncomputed = controlled_x(computed, (0, 1), 2, 3)
assert computed_purity < 1.0 and all(abs(a - b) < 1e-12 for a, b in zip(uncomputed, controls_plus_target_zero))
assert abs(purity_of_wire(uncomputed, 2, 3) - 1.0) < 1e-12
invalid_rejected = False
try:
controlled_x(basis_state("00"), (0,), 0, 2)
except ValueError:
invalid_rejected = True
assert invalid_rejected
unconditional = controlled_x(plus_zero, (), 1, 2)
assert abs(purity_of_wire(unconditional, 0, 2) - 1.0) < 1e-12 and unconditional != bell
print(f"PASS: 18 controlled-gate tracer verifies {len(cnot_outputs)} CNOT and {len(toffoli_outputs)} Toffoli branches; Bell purity={bell_purity:.3f}, computed-ancilla purity={computed_purity:.3f}, uncompute purity={purity_of_wire(uncomputed, 2, 3):.3f}")Scope boundary
- This chapter does not describe control wires as classical if their states may be superposed.
- It does not equate CNOT's basis-state copying behavior with cloning arbitrary states.
Depth commitment. One block derivation, one four-row table, one entangling trace, and one uncomputation sequence.
Practice problem
Trace (α|0>+β|1>)|0> through CNOT and determine exactly when the output is separable.
- Deliverable
- Symbolic output, coefficient factorization test, and conditions on α and β.
- Pass condition
- The solution proves separability only when one branch amplitude vanishes (up to edge cases) and the simulator samples test values.
Verification record
Expected solution form. Symbolic factorization argument plus parameterized numerical checks.
Model answer. CNOT produces alpha|00>+beta|11>. Its 2 by 2 coefficient matrix has determinant alpha beta, so the state is separable exactly when alpha=0 or beta=0; otherwise its Schmidt rank is two.
Model result and check. A rank test evaluates representative α,β pairs and agrees with the derived condition.
Acceptance test. The solution proves separability only when one branch amplitude vanishes (up to edge cases) and the simulator samples test values.
Companion work
Artifacts for this chapter
These entries resolve to checked-in local source. Commands are reproduced exactly from the chapter manifest, and source-embedded fixtures are exported as direct downloads.
Reproduce or test
python3 tools/validate_briefs.py --briefs data/editorial_briefs_00_35.json --from 0 --through 35 --check-rewritten-sources --execute-artifacts
Provenance
Sources and review
- Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press. 2010textbook
- John Preskill. Lecture Notes for Physics 219: Quantum Computation. California Institute of Technology. 2018graduate lecture notes
- John Watrous. The Theory of Quantum Information. Cambridge University Press / University of Waterloo. 2018textbook
- Charles H. Bennett. Logical reversibility of computation. IBM Journal of Research and Development. 1973primary paper
The load-bearing claims in the chapter are mapped inline to this registered source set. A citation supports only the bounded claim beside it.