You now know CNOT and the single-qubit gates (X, Y, Z, H, S, T). But which combinations are enough to build any quantum computation? This is the universality question — the quantum analogue of asking whether NAND gates are enough for classical circuits.
The answer comes in layers: first understand how any matrix can be written in terms of Pauli matrices (decomposition), then understand which gates merely shuffle Paulis around (Clifford gates — classically simulable), and finally see why adding one non-Clifford gate (T) breaks out of the simulable box and gives universality.
The set \(\{H, T, \text{CNOT}\}\) is universal: any unitary operation on any number of qubits can be approximated to arbitrary precision using only these three gates. H and CNOT alone are not enough — they generate only "Clifford" operations, which a classical computer can simulate efficiently. The T gate is the ingredient that makes quantum computation genuinely powerful.
The four Pauli matrices \(\{I, X, Y, Z\}\) form a basis for all \(2 \times 2\) matrices. Any \(2 \times 2\) matrix \(M\) can be written as a linear combination of Paulis:
$$M = \begin{pmatrix} a & b \\ c & d \end{pmatrix} = \frac{a+d}{2}\,I + \frac{b+c}{2}\,X + i\frac{b-c}{2}\,Y + \frac{a-d}{2}\,Z$$
There are four complex numbers in a \(2 \times 2\) matrix, and four Pauli matrices. The Paulis are linearly independent (no Pauli can be written as a combination of the others), so they span the full space. This is exactly like how \(\{\hat{x}, \hat{y}, \hat{z}\}\) spans \(\mathbb{R}^3\), except here it's \(\{I, X, Y, Z\}\) spanning \(\mathbb{C}^{2 \times 2}\).
$$H = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} \qquad\text{so } a = d^{-1} = \frac{1}{\sqrt{2}},\; b = \frac{1}{\sqrt{2}},\; c = \frac{1}{\sqrt{2}},\; d = \frac{-1}{\sqrt{2}}$$
$$\frac{a+d}{2} = \frac{\frac{1}{\sqrt{2}} + \frac{-1}{\sqrt{2}}}{2} = 0 \qquad \frac{b+c}{2} = \frac{\frac{1}{\sqrt{2}} + \frac{1}{\sqrt{2}}}{2} = \frac{1}{\sqrt{2}}$$
$$i\frac{b-c}{2} = i \cdot \frac{0}{2} = 0 \qquad \frac{a-d}{2} = \frac{\frac{1}{\sqrt{2}} - \frac{-1}{\sqrt{2}}}{2} = \frac{1}{\sqrt{2}}$$
Therefore:
$$H = \frac{1}{\sqrt{2}}X + \frac{1}{\sqrt{2}}Z = \frac{1}{\sqrt{2}}(X + Z)$$
This makes geometric sense: H is a rotation about the axis midway between X and Z on the Bloch sphere, which is exactly the \(X + Z\) direction.
$$Y = \begin{pmatrix} 0 & -i \\ i & 0 \end{pmatrix} \qquad a = 0,\; b = -i,\; c = i,\; d = 0$$
$$\frac{a+d}{2} = 0, \quad \frac{b+c}{2} = \frac{-i+i}{2} = 0, \quad i\frac{b-c}{2} = i\frac{-2i}{2} = 1, \quad \frac{a-d}{2} = 0$$
$$Y = 1 \cdot Y \quad\checkmark$$
Not surprising — Y is already a Pauli! But it confirms the formula works.
Consider \(R_z(\theta) = \begin{pmatrix} e^{-i\theta/2} & 0 \\ 0 & e^{i\theta/2} \end{pmatrix}\):
$$\frac{a+d}{2} = \frac{e^{-i\theta/2} + e^{i\theta/2}}{2} = \cos\frac{\theta}{2} \qquad \frac{a-d}{2} = \frac{e^{-i\theta/2} - e^{i\theta/2}}{2} = -i\sin\frac{\theta}{2}$$
$$R_z(\theta) = \cos\frac{\theta}{2}\,I - i\sin\frac{\theta}{2}\,Z$$
This is the standard Euler-type decomposition of a Z-rotation, and it generalizes: any rotation about axis \(\hat{n}\) by angle \(\theta\) is \(\cos\frac{\theta}{2}\,I - i\sin\frac{\theta}{2}(n_x X + n_y Y + n_z Z)\).
For \(n\) qubits, the basis consists of all Pauli strings: Kronecker products of \(n\) Pauli matrices (including \(I\)).
A Pauli string on \(n\) qubits is \(P_1 \otimes P_2 \otimes \cdots \otimes P_n\) where each \(P_i \in \{I, X, Y, Z\}\).
There are \(4^n\) Pauli strings, and they form a basis for all \(2^n \times 2^n\) matrices. Any \(n\)-qubit operator can be written as a linear combination of Pauli strings.
Examples for \(n = 2\): \(I \otimes I\), \(I \otimes X\), \(X \otimes Z\), \(Y \otimes Y\), etc. — 16 matrices forming a basis for \(\mathbb{C}^{4 \times 4}\).
The single-qubit formula \(M = \frac{a+d}{2}I + \frac{b+c}{2}X + \ldots\) only works for \(2 \times 2\) matrices. For multi-qubit gates (like CNOT, which is \(4 \times 4\)), you decompose into Pauli strings instead. The approach below uses the outer-product form of CNOT — something you already know from W3 — and rewrites the projectors in terms of Paulis.
Step 1: Start from the outer-product form of CNOT (from W3):
$$\text{CNOT} = \ket{0}\bra{0} \otimes I + \ket{1}\bra{1} \otimes X$$
"If control is |0⟩, do nothing to target. If control is |1⟩, apply X to target." You already know this.
Step 2: Replace the projectors with Pauli expressions. These are standard identities:
$$\ket{0}\bra{0} = \frac{1}{2}(I + Z) \qquad \ket{1}\bra{1} = \frac{1}{2}(I - Z)$$
Why? \(\frac{1}{2}(I + Z) = \frac{1}{2}\left(\begin{smallmatrix}1&0\\0&1\end{smallmatrix}\right) + \frac{1}{2}\left(\begin{smallmatrix}1&0\\0&-1\end{smallmatrix}\right) = \left(\begin{smallmatrix}1&0\\0&0\end{smallmatrix}\right) = \ket{0}\bra{0}\). Same idea for \(\ket{1}\bra{1}\).
Step 3: Substitute and expand:
$$\text{CNOT} = \frac{I+Z}{2} \otimes I + \frac{I-Z}{2} \otimes X$$
$$= \frac{1}{2}(\underbrace{I \otimes I}_{\text{always do } I} + \underbrace{Z \otimes I}_{\text{Z on control, I on target}} + \underbrace{I \otimes X}_{\text{I on control, X on target}} - \underbrace{Z \otimes X}_{\text{Z on control, X on target}})$$
Each term is a Pauli string (a tensor product of single-qubit Paulis). That's the decomposition:
$$\text{CNOT} = \frac{1}{2}(I \otimes I + I \otimes X + Z \otimes I - Z \otimes X)$$
Now we get to the key classification. A gate is Clifford if it maps Pauli strings to Pauli strings (up to a phase of \(\pm 1\) or \(\pm i\)).
A unitary \(U\) is a Clifford gate if for every Pauli string \(P\):
$$UPU^\dagger = \text{(phase)} \times \text{(Pauli string)}$$
where the phase is \(\pm 1\) or \(\pm i\). In other words, conjugating any Pauli by \(U\) gives back another Pauli (up to phase).
All Pauli gates are Clifford. For instance, \(XZX^\dagger = XZX = -Z\) (a Pauli times a phase). More generally, Paulis either commute or anticommute with each other, so conjugation just introduces a sign.
H is Clifford:
$$HXH^\dagger = HXH = Z \qquad HZH^\dagger = HZH = X \qquad HYH^\dagger = -Y$$
Every Pauli maps to another Pauli (times a phase). H is Clifford.
S is Clifford:
$$SXS^\dagger = Y \qquad SZS^\dagger = Z \qquad SYS^\dagger = -X$$
Again, Paulis in, Paulis out. S is Clifford.
CNOT is Clifford: You can verify that CNOT maps every two-qubit Pauli string to another single two-qubit Pauli string:
$$\text{CNOT}(X \otimes I)\text{CNOT}^\dagger = X \otimes X \quad\text{✓ single Pauli string}$$
$$\text{CNOT}(Z \otimes I)\text{CNOT}^\dagger = Z \otimes I \quad\text{✓ single Pauli string}$$
$$\text{CNOT}(I \otimes X)\text{CNOT}^\dagger = I \otimes X \quad\text{✓ single Pauli string}$$
$$\text{CNOT}(I \otimes Z)\text{CNOT}^\dagger = Z \otimes Z \quad\text{✓ single Pauli string}$$
Every result is one Pauli string — not a sum of multiple. That's the Clifford test. Compare this to the T gate later, where \(TXT^\dagger = \frac{1}{\sqrt{2}}(X + Y)\) — a sum of two Paulis, which fails the test.
It suffices to check the generators \(\{X \otimes I, Z \otimes I, I \otimes X, I \otimes Z\}\) — all other Pauli strings are products of these.
Circuits built entirely from Clifford gates (H, S, CNOT, Paulis), starting from computational basis states and ending with computational basis measurements, can be efficiently simulated on a classical computer.
This is surprising: Clifford circuits can create entanglement (H + CNOT makes Bell states!), can create superposition, can do many "quantum-looking" things. But they are not computationally powerful. They merely permute the Pauli group, and tracking this permutation is classically easy.
The T gate breaks out of the Clifford group. Let's see why:
$$T = \begin{pmatrix} 1 & 0 \\ 0 & e^{i\pi/4} \end{pmatrix} \qquad TXT^\dagger = \begin{pmatrix} 1 & 0 \\ 0 & e^{i\pi/4} \end{pmatrix}\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}\begin{pmatrix} 1 & 0 \\ 0 & e^{-i\pi/4} \end{pmatrix}$$
$$= \begin{pmatrix} 0 & e^{-i\pi/4} \\ e^{i\pi/4} & 0 \end{pmatrix} = \cos\frac{\pi}{4}\,X + \sin\frac{\pi}{4}\,Y = \frac{1}{\sqrt{2}}(X + Y)$$
This is not a Pauli string times a phase. It's a linear combination of two different Paulis. The T gate does not preserve the Pauli group — it rotates within the space of Paulis, creating superpositions of Pauli strings. That's what makes it non-Clifford.
Clifford gates permute Paulis. The T gate creates superpositions of Paulis. This is the qualitative difference. Permutations are classically easy to track. Superpositions are exponentially hard. Adding T to the Clifford set is what makes quantum circuits genuinely harder to simulate than classical ones.
A gate set is universal if any unitary operation on any number of qubits can be approximated to arbitrary precision by a finite circuit using only gates from this set.
Theorem: The set \(\{\text{CNOT}\} \cup \{\text{all single-qubit unitaries}\}\) is universal.
Any multi-qubit unitary can be decomposed into single-qubit gates and CNOTs. This is proven constructively: any unitary can be factored into "two-level unitaries" (act nontrivially on only 2 basis states), and each two-level unitary decomposes into CNOTs and single-qubit gates.
But "all single-qubit unitaries" is an infinite set. Can we do it with finitely many gates?
\(\{H, T, \text{CNOT}\}\) is universal. Here's why:
Other universal sets: \(\{H, T, \text{CNOT}\}\) can be replaced by \(\{H, R_z(\theta), \text{CNOT}\}\) for any irrational \(\theta/\pi\), or by the Toffoli + H, etc. The key: you need at least one non-Clifford element.
$$\underbrace{\{I, X, Y, Z\}}_{\text{Paulis}} \;\subset\; \underbrace{\{H, S, \text{CNOT}, \text{Paulis}\}}_{\text{Clifford group}} \;\subset\; \underbrace{\{H, T, \text{CNOT}\}}_{\text{Universal}}$$
Paulis: trivial operations. Clifford: entanglement + superposition, but classically simulable. Universal: adds T, breaks out of the simulable box.