Gates and Circuits

A qubit's state is a unit vector. Whatever we do to it between preparation and measurement must keep it a unit vector — total probability cannot leak away or be manufactured. The linear maps that preserve the length of every vector are precisely the unitary ones: a matrix $U$ is unitary when

where $U^{†}$ is the conjugate transpose. The one line of algebra that earns this: if $|{\psi }^{\prime }⟩=U|\psi ⟩$, then $⟨{\psi }^{\prime }|{\psi }^{\prime }⟩=⟨\psi |U^{†}U|\psi ⟩=⟨\psi |\psi ⟩$, so the norm is unchanged for every input exactly when $U^{†}U=I$. A quantum gate is just such a matrix, and unitarity has a free bonus: every gate is invertible, with inverse $U^{-1}=U^{†}$. Quantum computation is reversible.

The workhorses on one qubit start with the three Pauli matrices, met informally in Chapter 1 and defined properly now:

$X$ is the quantum NOT ($X|0⟩=|1⟩$); $Z$ flips the sign of $|1⟩$ and so writes phase; $Y=iXZ$ does both. Each squares to the identity and is its own inverse. Next the Hadamard, which makes superpositions, and the phase gates $S$ and $T$, which rotate the relative phase by a quarter- and an eighth-turn:

Note $S=T^2$ and $Z=S^2$: the phase gates form a ladder. Finally, the continuous families — the rotations about the three Bloch axes, generated by the Paulis,

with $R_x,R_y$ the analogous exponentials of $X$ and $Y$. These are exactly the moves that steer the Bloch vector of Chapter 1: $R_z$ spins it about the pole, $R_x,R_y$ tip it. A physical control knob — a laser pulse, a microwave burst — is, in the mathematics, one of these rotations.

One qubit is a vector in ${\mathbb{C}}^2$. Two qubits are not two separate vectors — they live together in the tensor product ${\mathbb{C}}^2\otimes {\mathbb{C}}^2={\mathbb{C}}^4$, spanned by the four basis states

For $n$ qubits the pattern continues: the state space is $({\mathbb{C}}^2{)}^{\otimes n}={\mathbb{C}}^{2^n}$, and a general state is a superposition over all $2^n$ bitstrings,

This is the exponential that defines the field: n qubits carry $2^n$ amplitudes. Thirty qubits already need a billion complex numbers; three hundred would need more numbers than there are atoms in the visible universe. That is the whole promise and the whole difficulty at once — and it is why §2.5 stores a state as a flat array of $2^n$ amplitudes and stops at $n=16$ on a laptop.

A single-qubit gate $U$ applied to qubit $q$ of an $n$-qubit register is, formally, the tensor product of $U$ on that slot with the identity everywhere else — e.g. $I\otimes U\otimes I$. You never build that $2^n\times 2^n$ matrix. Because $U$ touches only bit $q$ of the index, it mixes amplitudes strictly in pairs $(i,i\oplus 2^q)$ that differ in that one bit, leaving the other $n-1$ bits as spectators. That single observation is the engine of the whole simulator.

Single-qubit gates never entangle: applied to a product state they return a product state. To bind qubits we need gates that act on two at once. The fundamental one is the controlled-NOT (CNOT): pick a control qubit and a target, and flip the target if and only if the control is $|1⟩$. In the basis $\{00,01,10,11\}$ (control first),

CNOT is one instance of a general recipe: a controlled-$U$ applies the single-qubit gate $U$ to the target only on the branch where the control is set, and does nothing on the other branch — $|0⟩⟨0|\otimes I+|1⟩⟨1|\otimes U$. Taking $U=Z$ gives CZ; three CNOTs in a row (alternating control and target) give SWAP, which exchanges two qubits. Every one of these is unitary, so every one is reversible.

A quantum circuit draws a computation as a diagram: each qubit is a horizontal wire, each gate a box (or a control dot joined to a target $\oplus$) sitting on the wires it touches, and time runs left to right. At the right edge, a measurement meter turns each qubit into a classical bit by the Born rule of Chapter 1. The most famous small circuit is two gates long:

Build it yourself. Toggle the gates below and watch the four output probabilities, ordered $|00⟩,|01⟩,|10⟩,|11⟩$ by the convention of §2.2: $H$ alone spreads q0 over two outcomes; adding the CNOT ties the two wires together so only $|00⟩$ and $|11⟩$ survive — the Bell state. The two $X$ toggles let you start from a different corner of the basis; the readout tells you, from the determinant of the amplitude matrix, whether what you have built factors.

The output of $H$ then CNOT cannot be factored as $(\alpha |0⟩+\beta |1⟩)\otimes (\gamma |0⟩+\delta |1⟩)$ for any amplitudes — expand that product and you always get a $|01⟩$ or $|10⟩$ term unless one qubit is trivial. That un-factorability is entanglement, and it is the whole subject of Chapter 3; here we only note that two ordinary gates produce it.

How many kinds of gate must a machine physically build? Astonishingly few. A set of gates is universal if any unitary on any number of qubits can be built (or approximated as closely as you like) from gates in the set. The discrete set

is universal. CNOT supplies entanglement between qubits; $H$ and $T$ together generate a dense set of single-qubit rotations (their product is an irrational rotation of the Bloch sphere, so repeated application lands arbitrarily near any target). “Dense” is the key word: you cannot hit most unitaries exactly with a finite gate set, only approach them. The Solovay–Kitaev theorem makes that approach cheap — any single-qubit unitary can be approximated to accuracy $\epsilon$ using only $O\left({\log }^c(1/\epsilon )\right)$ gates from the set, with a small constant $c$. We state it without proof; the practical upshot is that the finiteness of a real machine's gate menu costs only polylogarithmic overhead, not an exponential one.

Linearity giveth reversibility; it also taketh away a power you might expect. The no-cloning theorem: there is no unitary $U$ that copies an arbitrary unknown qubit. Suppose one existed, with $U(|\psi ⟩\otimes |0⟩)=|\psi ⟩\otimes |\psi ⟩$ for every $|\psi ⟩$. Apply it to $|0⟩$ and to $|1⟩$: it must give $|00⟩$ and $|11⟩$. Now feed it $|+⟩=(|0⟩+|1⟩)/\sqrt{2}$. Linearity forces

but a genuine copy would have to be $|+⟩|+⟩=\frac{1}{2}(|00⟩+|01⟩+|10⟩+|11⟩)$. These are different states, so no such $U$ exists. You cannot photocopy an unknown quantum state. The proof is a single use of linearity, yet the consequence is enormous: it forbids the obvious classical error-correction trick (Chapter 10 must be cleverer), and it secures quantum key distribution against a copying eavesdropper. What (2.9) also shows, in passing, is that our copier does not fail quietly — it entangles the two qubits instead. That output is exactly the Bell state of §2.3, and the reason it is not a copy is the reason Chapter 3 exists.

Now we cash in §2.2. A state is a flat vector of $2^n$ complex amplitudes; a one-qubit gate on qubit $q$ sweeps the amplitude pairs that differ in bit $q$, leaving the rest untouched:

1/// An n-qubit pure state: 2^n complex amplitudes, indexed so that qubit q is
2/// bit q of the index (qubit 0 is the least-significant bit).
3#[derive(Clone)]
4struct State {
5    n: usize,
6    amps: Vec<C>,
7}
8
9impl State {
10    // … basis(), dim(), norm_sqr() …
11
12    /// Apply a 1-qubit gate to qubit q: sweep the 2^(n-1) amplitude pairs
13    /// (i, i|2^q) that differ only in bit q, mixing each by the 2x2 matrix.
14    fn apply_1q(&mut self, u: &Gate1, q: usize) {
15        let bit = 1usize << q;
16        for i in 0..self.dim() {
17            if i & bit == 0 {
18                let j = i | bit;
19                let a = self.amps[i];
20                let b = self.amps[j];
21                self.amps[i] = u[0][0] * a + u[0][1] * b;
22                self.amps[j] = u[1][0] * a + u[1][1] * b;
23            }
24        }
25    }
26
27    // … apply_ctrl(), swap(), prob0(), measure(), expect_z() …
28}

A controlled gate is the same sweep, gated by the control bit — do the mix only on the pairs whose control is set. CNOT and CZ fall straight out:

1/// Apply a controlled 1-qubit gate: run `u` on qubit `tgt` only for the
2    /// amplitude pairs whose control bit `ctrl` is set.
3    fn apply_ctrl(&mut self, u: &Gate1, ctrl: usize, tgt: usize) {
4        assert!(ctrl != tgt, "control and target must differ");
5        let cbit = 1usize << ctrl;
6        let tbit = 1usize << tgt;
7        for i in 0..self.dim() {
8            if i & tbit == 0 && i & cbit != 0 {
9                let j = i | tbit;
10                let a = self.amps[i];
11                let b = self.amps[j];
12                self.amps[i] = u[0][0] * a + u[0][1] * b;
13                self.amps[j] = u[1][0] * a + u[1][1] * b;
14            }
15        }
16    }
17
18    fn cnot(&mut self, ctrl: usize, tgt: usize) {
19        self.apply_ctrl(&g_x(), ctrl, tgt);
20    }
21    fn cz(&mut self, ctrl: usize, tgt: usize) {
22        self.apply_ctrl(&g_z(), ctrl, tgt);
23    }

The strongest referee runs one fixed three-qubit circuit two independent ways: the fast per-qubit simulator above, and a plodding reference that assembles the full $8\times 8$ unitary of every gate by explicit Kronecker products and multiplies them in time order. Sharing no application code — only the nine 2×2 gate-matrix constants themselves — the two must still agree. Note that they are compared on all eight basis inputs, not just $|000⟩$: one input only ever probes one column of the $8\times 8$ matrix, and it is easy to write a circuit whose error hides in the other seven — the $T$ on q1, for instance, does nothing at all to $|000⟩$, so a wrong phase there would pass a single-input check untouched.

1/// The circuit the cross-check referee runs: nine gates on three qubits,
2/// chosen to touch every primitive (1-qubit gates, a controlled-X, a
3/// controlled-Z, a SWAP, and an irrational-angle rotation so no amplitude is
4/// exactly representable). Path (a) — the fast simulator — is this function;
5/// path (b) rebuilds the same nine gates as dense 8x8 Kronecker products.
6fn fixed_circuit(s: &mut State) {
7    s.apply_1q(&g_h(), 0);
8    s.apply_1q(&g_t(), 1);
9    s.apply_1q(&g_ry(0.9), 2);
10    s.cnot(0, 1);
11    s.cz(1, 2);
12    s.apply_1q(&g_rz(0.7), 0);
13    s.swap(0, 2);
14    s.cnot(2, 1);
15    s.apply_1q(&g_x(), 0);
16}
17
18// … in main(): …
19
20    // --- Referee 6: the cross-check (strongest) ---------------------------
21    // Path (a): the fast per-qubit simulator runs a fixed 9-gate circuit.
22    // Path (b): dense 8x8 operators, Kronecker-built, multiplied in TIME order
23    // (each new gate multiplies on the LEFT: U_k · … · U_1). The two paths
24    // share no application code — only the nine 2x2 gate-matrix constants, so
25    // a mis-defined gate ENTRY is out of this referee's reach (Bell/GHZ/truth
26    // tables cover H and X; T/S entries rest on the definitions) — and we
27    // compare them on ALL EIGHT basis inputs — one input would only exercise a
28    // single column of the 8x8 unitary.
29    let ops: Vec<Dense> = vec![
30        full_1q(3, 0, &g_h()),
31        full_1q(3, 1, &g_t()),
32        full_1q(3, 2, &g_ry(0.9)),
33        full_ctrl(3, 0, 1, &g_x()),
34        full_ctrl(3, 1, 2, &g_z()),
35        full_1q(3, 0, &g_rz(0.7)),
36        full_swap(3, 0, 2),
37        full_ctrl(3, 2, 1, &g_x()),
38        full_1q(3, 0, &g_x()),
39    ];
40    let mut full = Dense::ident(8);
41    for op in &ops {
42        full = op.matmul(&full);
43    }
44    let mut worst_cross: f64 = 0.0;
45    for b in 0..8 {
46        let mut fast = State::basis(3, b);
47        fixed_circuit(&mut fast);
48        let dense_vec = full.apply(&State::basis(3, b).amps);
49        for i in 0..8 {
50            worst_cross = worst_cross.max((fast.amps[i] - dense_vec[i]).norm());
51        }
52    }
53    assert!(worst_cross.is_finite()); // FINITE before small
54    // … the referee's tolerance and the JSON it writes …

Each referee's achieved value and the tolerance it was gated at are written to JSON, which the panel below reads live — no number in this section is hardcoded. Between them the referees cover unitarity (the norm survives a long random circuit), the CNOT truth table written out by hand, the Bell and GHZ states amplitude by amplitude, collapse and correlation under actual measurement, the Kronecker cross-check, and GHZ built at every register size the sweep reaches. A few are gated at exactly zero rather than at a tolerance, because their arithmetic is exact; the panel says which.

Run it yourself with cargo run --release in Rust-QML/ch02-simulator. This simulator is not a one-chapter prop: it is the laboratory bench for the rest of the book. Every algorithm in Part II — the oracles, the Fourier transform, Grover's search — will be built and refereed on exactly this engine.