Universal gate set: {H, T, CNOT} — every quantum gate can be built from these three.
Key decompositions:
Hadamard conjugation — H swaps the X and Z axes:
CNOT direction swap:
$$(H \otimes H) \cdot \text{CNOT}_{12} \cdot (H \otimes H) = \text{CNOT}_{21}$$
To flip the control and target of a CNOT, wrap both qubits in Hadamard gates.
The exam gives a circuit using gates like S, Z, X, CZ and asks which {H, T, CNOT} circuit is equivalent. Apply the rules above to decompose step by step.
| Gate | Decomposition | Notes |
|---|---|---|
| \(S\) | \(TT\) | Phase gate = two T gates |
| \(S^\dagger\) | \(T^\dagger T^\dagger = T^6\) | Since \(T^8 = I\), so \(T^\dagger = T^7\) and \(S^\dagger = T^6\) |
| \(Z\) | \(TTTT = T^4\) | Pauli Z = four T gates |
| \(X\) | \(HT^4H\) | Pauli X = conjugate Z by H |
| \(Y\) | \(HT^4H \cdot T^4\) | Up to global phase (\(Y = iXZ\)) |
| \(\text{CZ}\) | \((I \otimes H) \cdot \text{CNOT} \cdot (I \otimes H)\) | Hadamard on target before & after CNOT |
| \(\text{SWAP}\) | \(\text{CNOT}_{12} \cdot \text{CNOT}_{21} \cdot \text{CNOT}_{12}\) | Three CNOTs in alternating directions |
| \(\text{CNOT}_{21}\) | \((H \otimes H) \cdot \text{CNOT}_{12} \cdot (H \otimes H)\) | Direction swap via Hadamard on both qubits |
| \(\text{CS}, \text{CT}\) | — | Controlled-S and Controlled-T exist but are less common on exams |
The Clifford group is {H, S, CNOT}. Clifford gates map Pauli operators to Pauli operators under conjugation. By the Gottesman-Knill theorem, circuits using only Clifford gates are classically simulable — not universal for quantum computation.
The T gate is non-Clifford. Adding T to the Clifford set makes the gate set universal — capable of approximating any unitary to arbitrary precision.
This is why we decompose into {H, T, CNOT}: it's the minimal extension of the Clifford group that achieves universality. S is redundant because \(S = T^2\).
Decompose the single-qubit circuit \(S \cdot X\) (apply X first, then S) into {H, T, CNOT}.
Step 1 — Decompose X
$$X = HZH = HT^4H$$
Step 2 — Decompose S
$$S = T^2 = TT$$
Step 3 — Combine (right to left: X first, then S)
$$S \cdot X = TT \cdot HT^4H = TTHT^4H$$
Result
$$S \cdot X = T \cdot T \cdot H \cdot T \cdot T \cdot T \cdot T \cdot H$$
Reading right to left: H, then four T gates, then H, then two T gates. Total: 2 H gates + 6 T gates.
Decompose a Controlled-Z gate on qubits 1 and 2 into {H, T, CNOT}.
Step 1 — CZ decomposition
The CZ gate is a CNOT with Hadamard gates wrapping the target qubit:
$$\text{CZ}_{12} = (I \otimes H) \cdot \text{CNOT}_{12} \cdot (I \otimes H)$$
Step 2 — Verify
CZ flips the phase of \(\ket{11}\) and leaves all other basis states unchanged. Let's check:
Result
$$\text{CZ}_{12} = (I \otimes H) \cdot \text{CNOT}_{12} \cdot (I \otimes H)$$
Already in {H, T, CNOT} — no T gates needed.
CZ is symmetric: \(\text{CZ}_{12} = \text{CZ}_{21}\). Unlike CNOT, there is no "control" vs "target" distinction.
A circuit applies the following operations on a single qubit (in order): \(X\), then \(S\), then \(Z\). Which compiled circuit in {H, T, CNOT} is equivalent?
Step 1 — Write out the full operation
$$U = Z \cdot S \cdot X$$
Step 2 — Simplify algebraically first
$$Z \cdot S = T^4 \cdot T^2 = T^6$$
$$U = T^6 \cdot X = T^6 \cdot HT^4H$$
Step 3 — Evaluate the options
Suppose the exam gives four choices:
Answer
Option B: \(T^6 \cdot H \cdot T^4 \cdot H\)
Key technique: decompose each gate, then combine. Simplify consecutive T gates (add exponents mod 8). Watch the order — the gate applied first in the circuit is on the right in the matrix product.
Decompose the gate \(Z \cdot X\) into {H, T, CNOT}. How many T gates are needed?
Decompose each gate:
$$X = HT^4H, \qquad Z = T^4$$
Combine:
$$Z \cdot X = T^4 \cdot HT^4H$$
This requires 8 T gates and 2 H gates.
Note: \(ZX = -iY\) (up to global phase), so this also serves as the Y decomposition.
A circuit applies \(S^\dagger\) to a qubit. Write the compiled version using only T gates.
\(S = T^2\), so \(S^\dagger = (T^2)^\dagger = (T^\dagger)^2\).
Since \(T^8 = I\), we have \(T^\dagger = T^7\), so:
$$S^\dagger = T^7 \cdot T^7 = T^{14} = T^6$$
(Reducing mod 8: \(14 \bmod 8 = 6\).)
Answer: \(S^\dagger = T^6\), i.e., six consecutive T gates.
Decompose a SWAP gate on qubits 1 and 2 into {H, T, CNOT} only. How many CNOT gates and H gates are needed?
SWAP = three CNOTs with alternating directions:
$$\text{SWAP} = \text{CNOT}_{12} \cdot \text{CNOT}_{21} \cdot \text{CNOT}_{12}$$
The middle CNOT has reversed direction. Decompose it:
$$\text{CNOT}_{21} = (H \otimes H) \cdot \text{CNOT}_{12} \cdot (H \otimes H)$$
Substituting:
$$\text{SWAP} = \text{CNOT}_{12} \cdot (H \otimes H) \cdot \text{CNOT}_{12} \cdot (H \otimes H) \cdot \text{CNOT}_{12}$$
Total: 3 CNOT gates and 4 H gates (two pairs of \(H \otimes H\)). No T gates needed.
Which of the following {H, T, CNOT} circuits implements the single-qubit gate \(S \cdot Z\)?
Decompose:
$$S \cdot Z = T^2 \cdot T^4 = T^6$$
Option A: \(T^4 \cdot T^2 = T^6\). ✓
Option B: \(T^2 \cdot T^4 = T^6\). ✓
Option C: \(HT^6H\). This conjugates \(T^6 = S^\dagger\) by H, giving a different gate (not \(S \cdot Z\)). ✗
Answer: D (both A and B).
T gates commute with each other (\(T^a \cdot T^b = T^{a+b} = T^b \cdot T^a\)), so the order of consecutive T gates doesn't matter.
A 2-qubit circuit applies CZ followed by \(X \otimes I\) (X on qubit 1, identity on qubit 2). Write the full decomposition in {H, T, CNOT}.
Decompose CZ:
$$\text{CZ}_{12} = (I \otimes H) \cdot \text{CNOT}_{12} \cdot (I \otimes H)$$
Decompose \(X \otimes I\):
$$X \otimes I = (HT^4H) \otimes I$$
Full circuit (CZ first, then \(X \otimes I\)):
$$(X \otimes I) \cdot \text{CZ}_{12} = \bigl((HT^4H) \otimes I\bigr) \cdot (I \otimes H) \cdot \text{CNOT}_{12} \cdot (I \otimes H)$$
Since the first-qubit and second-qubit operations commute (they act on different qubits), we can rewrite the sequence in circuit order as:
Total: 1 CNOT, 4 H gates, 4 T gates.