14. Multi-Qubit Gates
14.1Controlled operations and CNOT
A controlled-U applies U to the target qubit only when the control qubit is |1⟩: it is quantum conditional logic, and it is the entanglement-making operation. The canonical case is CNOT (controlled-NOT, controlled-X): control unchanged, target flipped if control is |1⟩. Its 4×4 matrix is block-diagonal: I for the control-0 rows, X for the control-1 rows. Crucial semantics: CNOT does not copy the control — applied to |+⟩⊗|0⟩ it produces (|00⟩+|11⟩)/√2, entanglement, not a clone (no-cloning is encoded in linearity itself). Also notable: CNOT is its own inverse, and control/target roles can be swapped by conjugating with H (H⊗H·CNOT·H⊗H = reversed CNOT) — a routing trick hardware compilers use constantly. In numpy, CNOT is the first 4×4 matrix worth typing by hand.
import numpy as np
CNOT = np.array([[1,0,0,0],
[0,1,0,0],
[0,0,0,1],
[0,0,1,0]], dtype=complex)
H = np.array([[1,1],[1,-1]], dtype=complex)/np.sqrt(2)
plus0 = np.kron(H @ np.array([1,0], dtype=complex), np.array([1,0], dtype=complex))
print(np.round(CNOT @ plus0, 3)) # [0.707, 0, 0, 0.707] -> Bell state, not a copy14.2Controlled-Z and controlled phase
CZ (controlled-Z) applies Z to the target when the control is |1⟩; as a diagonal matrix diag(1,1,1,−1) it adds a −1 phase only to |11⟩. Two engineering reasons CZ is beloved. First, it is symmetric: either qubit can be called the control — a real convenience when hardware connectivity is fixed. Second, on many platforms (superconducting, photonic) it is native or near-native, sometimes as a bus-mediated conditional phase. The identity CZ = (I⊗H)·CNOT·(I⊗H) means CNOT and CZ are interchangeable at the cost of two Hadamards, so gate libraries choose freely. Generalizing, the controlled-phase gate CRz(θ) = diag(1,1,1,e^{iθ}) gives an arbitrary conditional phase; two-qubit interactions in nature (couplers, collisions, cross-resonance drives) are naturally of this entangling-phase form, which is why synthesis tooling treats CRz as the primitive.
14.3SWAP
SWAP exchanges two qubits' states: |ψ⟩⊗|φ⟩ → |φ⟩⊗|ψ⟩, matrix form a 4×4 permutation with ones on the anti-diagonal. It does not create entanglement and is composed of three CNOTs (CNOT(a,b)·CNOT(b,a)·CNOT(a,b) — order matters, all three directions). Why care about a gate that "does nothing" computationally? Routing. Hardware gives you an interaction graph — superconducting chips connect neighbors; trapped ions connect more broadly but not freely — and when a two-qubit gate targets non-adjacent qubits, the compiler inserts SWAPs to bring them together, or moves states along the graph. On IBM-style heavy-hex layouts, routing overhead routinely multiplies circuit depth several-fold, and since every gate layer accumulates ~10⁻³ error, SWAP insertion is a first-order driver of whether an algorithm works at all (45.9). Depth counting below makes this cost visible.
14.4Toffoli and Fredkin
The Toffoli gate (CCNOT) flips the target iff both controls are |1⟩ — classical AND-with-uncompute, and the backbone of reversible classical logic: any Boolean circuit can be built from Toffoli plus X, with the garbage-output trick of uncomputing ancillas. Quantum mechanically it maps |a⟩|b⟩|c⟩ → |a⟩|b⟩|c⊕(a·b)⟩. The Fredkin gate (controlled-SWAP) swaps targets iff the control is |1⟩, used in reversible computing and in comparison/routing subroutines. Neither is native on any major platform: Toffoli decomposes into 6 CNOTs plus single-qubit gates (fewer with relative-phase Toffoli tricks, at the cost of a Z-on-phase-kickback ancilla), and arithmetic built from them inherits that multiplier. This is the honest cost of quantum arithmetic: Shor's modular exponentiation is thousands of Toffolis, each six-ish CNOTs, each error-prone — resource counts (Part VIII) add up exactly this way.
Toffoli = 6 CNOTs (standard decomposition, plus single-qubit gates):
c0: ──●────────────●──────────●──────
│ │ │
c1: ──┼────●───────┼────●─────┼──●───
│ │ │ │ │ │
t : ──X────X───H───X────H──X──X──H─── (exact up to global phase)14.5Controlled rotations
A controlled rotation CRθ applies Ry(θ) or Rz(θ) to the target conditioned on the control — the continuously-tunable cousin of CNOT, and the literal building block of the QFT and many variational ansätze. The construction generalizes a pattern you should internalize: any single-qubit U = e^{iα}·A·X·B·X·C (with A·X·B·X·C = I) converts into controlled-U by controlling only the middle X — meaning any controlled-U costs just two CNOTs plus the single-qubit A, B, C. That is a theorem worth knowing by name (Barenco et al. 1995). In circuits like QFT the rotations are multiply-controlled in later stages; the general rule is that a k-controlled U needs O(k) CNOTs with ancillas or O(2ᵏ) without — the constant factor that makes big controlled operations expensive, and the target of ongoing synthesis improvements.
14.6Universal gate sets
What is the minimal toolkit for arbitrary quantum computation? The standard answer: {H, T, CNOT} — one Clifford, one non-Clifford, one entangler — is universal, meaning any n-qubit unitary can be approximated to accuracy ε by a circuit over this set (with size polylogarithmic in 1/ε). Practical variants: {Rz(π/4), √X, CNOT} matches hardware pulses; ion traps use {Rx(π/2), Rz(θ), Mølmer–Sørensen}; and any single entangling two-qubit gate plus arbitrary one-qubit gates is universal (Brylinski's theorem) — even exotic ones like √SWAP or iSWAP. Note the negative space: the Clifford group alone is classically simulable (Gottesman–Knill), so universality hinges on one non-Clifford ingredient — precisely why T gates dominate fault-tolerance cost and why magic-state distillation exists (Part X). Choose your gate set like you choose an instruction set: by native support, not elegance.
14.7Gate synthesis
Gate synthesis is the compiler pass turning an arbitrary target unitary into a sequence of library gates. Single-qubit: exact ZYZ decomposition (10.5), three rotations. Two-qubit: any two-qubit unitary needs exactly 3 CNOTs plus single-qubit gates (worse, 14 for special classes; the number is a proven bound, not folklore). General n-qubit unitaries need O(4ⁿ) CNOTs — exponential, as they must be, since the unitary itself has 4ⁿ real parameters. The engineering reality: approximate synthesis. Because physical gates err at ~10⁻³ anyway, circuits are synthesized to accuracy ε over the native set, trading gate count against approximation error; Solovay–Kitaev gives O(log^c(1/ε)) overhead and modern number-theoretic methods do far better for the {H,T} set. Total error budget = synthesis error + gate errors + readout error; compilers (Part XII) exist to balance that equation automatically.
14.8Circuit depth and width
Two numbers characterize a circuit's cost. Width: qubits used. Depth: the longest chain of sequential gate layers, where a layer holds gates acting on disjoint qubits — depth is what determines runtime on hardware, since layers execute one after another, and it bounds how much decoherence accumulates before the measurement. A useful mental model from classical computing: width is memory, depth is critical-path latency. The tension is real: shrinking depth by parallelizing may cost ancilla width, and hardware limits both (≈10²–10⁴ qubits; coherence times of microseconds to seconds). The quantity to watch in any benchmark plot is depth × error rate — circuits deeper than ~1/(gate error) ≈ 1,000 layers at 10⁻³ error drown in noise before error correction exists. When this book says an algorithm "fits on current hardware", it is a claim about depth after routing, not about qubit count.