Lesson 8: Multi-Qubit Gates, Entanglement and the Bell States¶
8.1 Learning Outcomes¶
By the end of this hour a student will be able to:
- Write the matrices of CNOT, CZ, SWAP, Toffoli and controlled-\(U\) and state their actions.
- Test a two-qubit state for separability versus entanglement.
- Construct the four Bell states and know their circuit.
- Compute a reduced density matrix by partial trace and use it to quantify entanglement.
- State the CHSH inequality and its quantum violation, and explain why entanglement does not permit signalling.
- State what makes a gate set universal.
8.2 Two-Qubit Systems¶
Basis: \(\{|00\rangle,|01\rangle,|10\rangle,|11\rangle\}\), and a general state is
Convention. We write \(|q_0 q_1\rangle\) with \(q_0\) the first/top qubit in the circuit (big-endian). Qiskit displays bitstrings in the reverse order — a persistent source of confusion, flagged again in L37.
8.3 Two-Qubit Gates¶
CNOT (controlled-NOT)¶
Flips the target iff the control is \(|1\rangle\):
(rows/columns ordered \(00,01,10,11\)). It is Hermitian and unitary, so \(\mathrm{CNOT}^2 = I\).
The crucial property: CNOT creates entanglement.
A separable input has become non-separable. No single-qubit gate can ever do this — products of local unitaries preserve separability.
Controlled-Z and general controlled-U¶
\(CZ\) is symmetric in control and target — swapping the roles gives the same gate. Useful identity:
which is how superconducting hardware that natively implements \(CZ\) realises a CNOT.
SWAP¶
SWAPs are inserted by the transpiler to move logical qubits around a limited hardware coupling map, and they are a major source of circuit-depth overhead on real devices.
Toffoli (CCNOT) and Fredkin¶
An \(8\times8\) permutation matrix. The Toffoli gate is universal for classical reversible computation: setting \(c=0\) gives \(|a,b,ab\rangle\), i.e. a reversible AND. This is how every classical Boolean function is embedded into a quantum circuit, which is exactly what oracle construction in Unit II requires.
The Fredkin gate (CSWAP) swaps two targets conditioned on a control; it appears in the swap test used for quantum k-means (L32).
Cost: a Toffoli decomposes into 6 CNOTs + several single-qubit gates (7 \(T\) gates). Toffoli count therefore dominates the cost of arithmetic circuits such as modular exponentiation in Shor's algorithm.
8.4 Entanglement¶
Definition (Product / separable state). A pure state \(|\psi\rangle_{AB}\) is separable if it can be written \(|\psi\rangle_{AB} = |\phi\rangle_A \otimes |\chi\rangle_B\). Otherwise it is entangled.
The determinant test for two qubits¶
For \(|\psi\rangle = a_{00}|00\rangle + a_{01}|01\rangle + a_{10}|10\rangle + a_{11}|11\rangle\), define the concurrence
Why. If \(|\psi\rangle = (\alpha|0\rangle+\beta|1\rangle)\otimes(\gamma|0\rangle+\delta|1\rangle)\) then \(a_{00}=\alpha\gamma\), \(a_{01}=\alpha\delta\), \(a_{10}=\beta\gamma\), \(a_{11}=\beta\delta\), and
Conversely if the determinant vanishes the coefficient matrix has rank 1 and factorises. \(\blacksquare\)
The Bell states¶
These four form an orthonormal basis of \(\mathbb{C}^4\) (the Bell basis), and each has concurrence 1.
Preparation circuit. For input \(|xy\rangle\):
q0: --[H]--*--
|
q1: ------[X]-- ( * = control, [X] = target )
| Input | Output |
|---|---|
| \(\lvert 00\rangle\) | \(\lvert \Phi^+\rangle\) |
| \(\lvert 01\rangle\) | \(\lvert \Psi^+\rangle\) |
| \(\lvert 10\rangle\) | \(\lvert \Phi^-\rangle\) |
| \(\lvert 11\rangle\) | \(\lvert \Psi^-\rangle\) |
The circuit is unitary, so running it backwards (\(H\otimes I\) after CNOT) performs a Bell measurement — indispensable for teleportation (L10).
Reduced density matrices¶
Definition (Partial trace). For a bipartite state \(\rho_{AB}\),
\(\rho_A\) describes everything an experimenter with access only to system \(A\) can observe.
Entanglement criterion. For a pure joint state:
Definition (Entanglement entropy). \(S(\rho_A) = -\mathrm{Tr}(\rho_A\log_2\rho_A)\). For two qubits, \(S = 0\) for a product state and \(S = 1\) for a Bell state.
The defining paradox in one line. For \(|\Phi^+\rangle\) the global state is pure — maximal knowledge — yet \(\rho_A = I/2\) is maximally mixed — zero knowledge of either part. All the information lives in the correlations, not in the parts.
Bell's theorem and the CHSH inequality¶
Define correlations \(E(a,b) = \langle A_a \otimes B_b\rangle\) for two measurement settings each. The CHSH quantity
satisfies, for any local hidden-variable theory,
Quantum mechanics with \(|\Phi^+\rangle\) and the settings \(a=Z\), \(a'=X\), \(b = \frac{Z+X}{\sqrt2}\), \(b' = \frac{Z-X}{\sqrt2}\) achieves
Experiments (Aspect 1982; loophole-free tests 2015; 2022 Nobel Prize to Aspect, Clauser and Zeilinger) confirm the quantum prediction. Nature is not describable by local hidden variables.
No-signalling. Entanglement does not allow faster-than-light communication. Alice's local statistics are governed by \(\rho_A\), which is unchanged by anything Bob does — his operations act as \(I \otimes U_B\), and \(\mathrm{Tr}_B\big((I\otimes U_B)\rho(I\otimes U_B^\dagger)\big) = \rho_A\) by cyclicity of the trace. Correlations only become visible when the two parties compare results over a classical channel.
8.5 Universality¶
Theorem. The set \(\{\text{CNOT}\} \cup \{\text{all single-qubit unitaries}\}\) is universal: any \(n\)-qubit unitary can be built exactly from these.
Discrete universal set. \(\{H, T, \mathrm{CNOT}\}\) is universal to arbitrary accuracy (Solovay–Kitaev). Alternative: \(\{H, S, \mathrm{CNOT}, T\}\) = Clifford + \(T\).
Gottesman–Knill theorem. Circuits containing only Clifford gates (\(H\), \(S\), CNOT) and computational-basis measurements can be simulated efficiently classically. Entanglement alone is therefore not sufficient for quantum advantage — \(|\Phi^+\rangle\) is a stabiliser state. The non-Clifford \(T\) gate is what pushes a circuit beyond classical reach.
8.6 Solved Problems¶
Problem 1 — Testing for entanglement¶
Classify each state as product or entangled. If product, give the factorisation.
(a) \(\frac{1}{2}\big(|00\rangle + |01\rangle + |10\rangle + |11\rangle\big)\) (b) \(\frac{1}{\sqrt2}\big(|00\rangle + |11\rangle\big)\) (c) \(\frac{1}{\sqrt3}\big(|00\rangle + |01\rangle + |10\rangle\big)\)
Solution.
(a) \(a_{00}=a_{01}=a_{10}=a_{11}=\frac12\).
Factorisation: \(\frac12(|0\rangle+|1\rangle)(|0\rangle+|1\rangle) = |+\rangle\otimes|+\rangle\).
(b) \(a_{00}=a_{11}=\frac{1}{\sqrt2}\), \(a_{01}=a_{10}=0\).
(c) \(a_{00}=a_{01}=a_{10}=\frac{1}{\sqrt3}\), \(a_{11}=0\).
Problem 2 — Reduced density matrix of a Bell state¶
For \(|\Phi^+\rangle = \frac{1}{\sqrt2}(|00\rangle+|11\rangle)\) compute \(\rho_A\), its purity and entanglement entropy.
Solution.
Trace out \(B\) (keep terms where \(B\)'s bra and ket labels match):
Purity: \(\mathrm{Tr}(\rho_A^2) = \mathrm{Tr}\begin{pmatrix}0.25&0\\0&0.25\end{pmatrix} = 0.5\) — maximally mixed.
Entropy: eigenvalues both \(\tfrac12\), so
Interpretation. One full ebit of entanglement. Alice, examining her qubit alone, sees perfectly random 0s and 1s and can learn nothing about the global state.
Problem 3 — Tracing a circuit that builds a Bell state¶
Trace \(|10\rangle\) through \(H\) on qubit 0 followed by CNOT (control 0, target 1). Verify the result against the Bell table.
Solution.
Step 1: \(H \otimes I\) on \(|10\rangle\). \(H|1\rangle = |-\rangle\), so
Step 2: CNOT. Flip the second bit wherever the first is 1:
- \(|00\rangle \to |00\rangle\) (control 0, no flip)
- \(|10\rangle \to |11\rangle\) (control 1, flip)
This matches the table entry for input \(|10\rangle\). Concurrence: \(2|\frac{1}{\sqrt2}\cdot(-\frac{1}{\sqrt2}) - 0| = 1\) — maximally entangled.
Problem 4 — CNOT does not entangle basis states¶
Show that CNOT applied to \(|1\rangle\otimes|+\rangle\) produces a product state, and explain the "phase kick-back" you observe.
Solution.
Apply CNOT (control = qubit 0, which is \(|1\rangle\), so always flip qubit 1):
The state is unchanged — still \(|1\rangle\otimes|+\rangle\), a product state. CNOT does nothing because \(|+\rangle\) is an eigenvector of \(X\) with eigenvalue \(+1\).
Now the kick-back version. Try \(|1\rangle\otimes|-\rangle\):
The state acquired a phase of \(-1\), and that phase is attached to the control qubit even though CNOT nominally acts on the target. Compare with \(|0\rangle\otimes|-\rangle\), which is unchanged. Hence
This is phase kick-back, the single mechanism behind Deutsch–Jozsa, Bernstein–Vazirani, Simon and Grover. It is developed fully in L11.
Problem 5 — Building a GHZ state and its correlations¶
Design a circuit producing the 3-qubit GHZ state \(|\mathrm{GHZ}\rangle = \frac{1}{\sqrt2}(|000\rangle + |111\rangle)\) from \(|000\rangle\). What happens to the other two qubits if qubit 1 is measured?
Solution.
Circuit: \(H\) on \(q_0\), then \(\mathrm{CNOT}_{0\to1}\), then \(\mathrm{CNOT}_{0\to2}\).
Measuring qubit 1 in the \(Z\) basis. Using \(P_0 = |0\rangle\langle0|\otimes I\otimes I\):
All three qubits collapse together. Measuring one determines the other two with certainty — maximal three-way correlation. The GHZ state is famously fragile: losing (tracing out) any single qubit leaves the remaining two in the separable mixture \(\frac12(|00\rangle\langle00| + |11\rangle\langle11|)\), with no entanglement at all. This contrasts with the W state \(\frac{1}{\sqrt3}(|001\rangle+|010\rangle+|100\rangle)\), whose entanglement survives the loss of one qubit.
8.7 Practice Problems¶
- Compute the matrix of \(\mathrm{CNOT}_{2\to1}\) (control = qubit 1, target = qubit 0).
- Is \(\frac{1}{\sqrt2}(|00\rangle + |01\rangle)\) entangled? Factorise if possible. [Ans: product, \(|0\rangle\otimes|+\rangle\)]
- Verify that the four Bell states are mutually orthogonal.
- Compute \(\rho_A\) for \(\frac{1}{\sqrt3}(|00\rangle + |01\rangle + |10\rangle)\) and its purity. [Ans: purity \(7/9\)]
- Show \(\mathrm{SWAP} = \mathrm{CNOT}_{12}\mathrm{CNOT}_{21}\mathrm{CNOT}_{12}\) by acting on all four basis states.
- Write the Toffoli matrix and verify it computes reversible AND when \(c=0\).
- Explain why the Gottesman–Knill theorem does not contradict the existence of quantum speed-ups.
- Prove no-signalling: show that Bob applying any \(U_B\) leaves \(\rho_A\) unchanged.
8.8 Summary¶
- CNOT is the canonical entangling gate: \(|c,t\rangle \to |c, t\oplus c\rangle\); it converts product states into entangled ones, which no single-qubit gate can do.
- CZ is control-symmetric; SWAP = three CNOTs; Toffoli is universal for classical reversible logic and is the workhorse of oracle construction.
- A two-qubit pure state is entangled iff \(a_{00}a_{11} - a_{01}a_{10} \ne 0\) (concurrence \(C \ne 0\)).
- The four Bell states form an orthonormal basis; the \(H\) + CNOT circuit prepares them, and its inverse performs a Bell measurement.
- Reduced density matrices diagnose entanglement: a pure global state is entangled iff \(\rho_A\) is mixed; \(\rho_A = I/2\) means maximal entanglement.
- CHSH: local hidden variables give \(|S|\le2\); quantum mechanics gives \(2\sqrt2\). Entanglement is real but cannot signal.
- \(\{H,T,\mathrm{CNOT}\}\) is universal; Clifford-only circuits are classically simulable (Gottesman–Knill).
Next lesson: L09 — Quantum parallelism, interference and the no-cloning theorem.
Practise now: unit1-qubit-lab.html → Entanglement Lab: build two-qubit circuits, watch
concurrence update live, and run a CHSH experiment to see \(S \to 2\sqrt2\).