Skip to content

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:

  1. Write the matrices of CNOT, CZ, SWAP, Toffoli and controlled-\(U\) and state their actions.
  2. Test a two-qubit state for separability versus entanglement.
  3. Construct the four Bell states and know their circuit.
  4. Compute a reduced density matrix by partial trace and use it to quantify entanglement.
  5. State the CHSH inequality and its quantum violation, and explain why entanglement does not permit signalling.
  6. 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

\[ |\psi\rangle = a_{00}|00\rangle + a_{01}|01\rangle + a_{10}|10\rangle + a_{11}|11\rangle, \qquad \sum |a_{ij}|^2 = 1 . \]

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\):

\[ \mathrm{CNOT}|c,t\rangle = |c,\ t\oplus c\rangle \]
\[ \mathrm{CNOT} = \begin{pmatrix} 1&0&0&0\\ 0&1&0&0\\ 0&0&0&1\\ 0&0&1&0 \end{pmatrix} \]

(rows/columns ordered \(00,01,10,11\)). It is Hermitian and unitary, so \(\mathrm{CNOT}^2 = I\).

The crucial property: CNOT creates entanglement.

\[ \mathrm{CNOT}\big(|+\rangle\otimes|0\rangle\big) = \mathrm{CNOT}\tfrac{1}{\sqrt2}\big(|00\rangle + |10\rangle\big) = \tfrac{1}{\sqrt2}\big(|00\rangle + |11\rangle\big) = |\Phi^+\rangle . \]

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 = \mathrm{diag}(1,1,1,-1), \qquad CU = \begin{pmatrix} I & 0 \\ 0 & U\end{pmatrix} \ \text{(block form)} \]

\(CZ\) is symmetric in control and target — swapping the roles gives the same gate. Useful identity:

\[ \mathrm{CNOT}_{1\to2} = (I\otimes H)\, CZ\, (I\otimes H) \]

which is how superconducting hardware that natively implements \(CZ\) realises a CNOT.

SWAP

\[ \mathrm{SWAP}|a,b\rangle = |b,a\rangle, \qquad \mathrm{SWAP} = \begin{pmatrix}1&0&0&0\\0&0&1&0\\0&1&0&0\\0&0&0&1\end{pmatrix} \]
\[ \mathrm{SWAP} = \mathrm{CNOT}_{1\to2}\cdot \mathrm{CNOT}_{2\to1}\cdot \mathrm{CNOT}_{1\to2} \]

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

\[ \mathrm{CCNOT}|a,b,c\rangle = |a,\,b,\,c\oplus(a\wedge b)\rangle \]

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

\[ C = 2\,\big| a_{00}a_{11} - a_{01}a_{10} \big| . \]
\[ \boxed{\ C = 0 \iff \text{separable};\qquad C = 1 \iff \text{maximally entangled}\ } \]

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

\[ a_{00}a_{11} - a_{01}a_{10} = \alpha\gamma\beta\delta - \alpha\delta\beta\gamma = 0 . \]

Conversely if the determinant vanishes the coefficient matrix has rank 1 and factorises. \(\blacksquare\)

The Bell states

\[ |\Phi^{+}\rangle = \tfrac{1}{\sqrt2}\big(|00\rangle + |11\rangle\big), \qquad |\Phi^{-}\rangle = \tfrac{1}{\sqrt2}\big(|00\rangle - |11\rangle\big) \]
\[ |\Psi^{+}\rangle = \tfrac{1}{\sqrt2}\big(|01\rangle + |10\rangle\big), \qquad |\Psi^{-}\rangle = \tfrac{1}{\sqrt2}\big(|01\rangle - |10\rangle\big) \]

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 )
\[ \mathrm{CNOT}\,(H\otimes I)\,|xy\rangle = |\beta_{xy}\rangle \]
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 = \mathrm{Tr}_B(\rho_{AB}) = \sum_j \big(I\otimes\langle j|_B\big)\,\rho_{AB}\,\big(I\otimes|j\rangle_B\big) . \]

\(\rho_A\) describes everything an experimenter with access only to system \(A\) can observe.

Entanglement criterion. For a pure joint state:

\[ |\psi\rangle_{AB} \text{ is separable} \iff \rho_A \text{ is pure } (\mathrm{Tr}\rho_A^2 = 1) . \]
\[ |\psi\rangle_{AB} \text{ is maximally entangled} \iff \rho_A = I/2 . \]

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

\[ S = E(a,b) - E(a,b') + E(a',b) + E(a',b') \]

satisfies, for any local hidden-variable theory,

\[ |S| \le 2 \qquad \text{(CHSH inequality)} . \]

Quantum mechanics with \(|\Phi^+\rangle\) and the settings \(a=Z\), \(a'=X\), \(b = \frac{Z+X}{\sqrt2}\), \(b' = \frac{Z-X}{\sqrt2}\) achieves

\[ |S| = 2\sqrt2 \approx 2.828 \qquad \text{(Tsirelson's bound)} . \]

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\).

\[ C = 2\left|\tfrac12\cdot\tfrac12 - \tfrac12\cdot\tfrac12\right| = 0 \Rightarrow \text{product}. \]

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 = 2\left|\tfrac12 - 0\right| = 1 \Rightarrow \textbf{maximally entangled}. \]

(c) \(a_{00}=a_{01}=a_{10}=\frac{1}{\sqrt3}\), \(a_{11}=0\).

\[ C = 2\left|0 - \tfrac13\right| = \tfrac23 \Rightarrow \textbf{partially entangled}. \]

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.

\[ \rho_{AB} = |\Phi^+\rangle\langle\Phi^+| = \tfrac12\big(|00\rangle+|11\rangle\big)\big(\langle00|+\langle11|\big) \]
\[ = \tfrac12\big(|00\rangle\langle00| + |00\rangle\langle11| + |11\rangle\langle00| + |11\rangle\langle11|\big) \]

Trace out \(B\) (keep terms where \(B\)'s bra and ket labels match):

\[ \rho_A = \tfrac12\big(|0\rangle\langle0|\underbrace{\langle0|0\rangle}_{1} + |0\rangle\langle1|\underbrace{\langle 1|0\rangle}_{0} + |1\rangle\langle0|\underbrace{\langle0|1\rangle}_{0} + |1\rangle\langle1|\underbrace{\langle1|1\rangle}_{1}\big) \]
\[ \rho_A = \tfrac12\big(|0\rangle\langle0| + |1\rangle\langle1|\big) = \frac{I}{2} = \begin{pmatrix}0.5 & 0\\ 0 & 0.5\end{pmatrix} \]

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

\[ S = -\left(\tfrac12\log_2\tfrac12 + \tfrac12\log_2\tfrac12\right) = 1 \text{ ebit}. \]

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

\[ (H\otimes I)|10\rangle = |-\rangle\otimes|0\rangle = \tfrac{1}{\sqrt2}\big(|00\rangle - |10\rangle\big) . \]

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)
\[ \mathrm{CNOT}\cdot\tfrac{1}{\sqrt2}\big(|00\rangle - |10\rangle\big) = \tfrac{1}{\sqrt2}\big(|00\rangle - |11\rangle\big) = |\Phi^-\rangle \ \checkmark \]

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.

\[ |1\rangle\otimes|+\rangle = \tfrac{1}{\sqrt2}\big(|10\rangle + |11\rangle\big) \]

Apply CNOT (control = qubit 0, which is \(|1\rangle\), so always flip qubit 1):

\[ \to \tfrac{1}{\sqrt2}\big(|11\rangle + |10\rangle\big) = \tfrac{1}{\sqrt2}\big(|10\rangle + |11\rangle\big) \]

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\):

\[ |1\rangle\otimes|-\rangle = \tfrac{1}{\sqrt2}\big(|10\rangle - |11\rangle\big) \xrightarrow{\text{CNOT}} \tfrac{1}{\sqrt2}\big(|11\rangle - |10\rangle\big) = -\tfrac{1}{\sqrt2}\big(|10\rangle - |11\rangle\big) \]
\[ = -\,|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

\[ \mathrm{CNOT}\big(|x\rangle\otimes|-\rangle\big) = (-1)^{x}\,|x\rangle\otimes|-\rangle . \]

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}\).

\[ |000\rangle \xrightarrow{H_0} \tfrac{1}{\sqrt2}\big(|000\rangle + |100\rangle\big) \]
\[ \xrightarrow{\mathrm{CNOT}_{0\to1}} \tfrac{1}{\sqrt2}\big(|000\rangle + |110\rangle\big) \]
\[ \xrightarrow{\mathrm{CNOT}_{0\to2}} \tfrac{1}{\sqrt2}\big(|000\rangle + |111\rangle\big) \ \checkmark \]

Measuring qubit 1 in the \(Z\) basis. Using \(P_0 = |0\rangle\langle0|\otimes I\otimes I\):

\[ P_0|\mathrm{GHZ}\rangle = \tfrac{1}{\sqrt2}|000\rangle, \qquad \Pr[0] = \tfrac12, \qquad |\psi'\rangle = |000\rangle \]
\[ P_1|\mathrm{GHZ}\rangle = \tfrac{1}{\sqrt2}|111\rangle, \qquad \Pr[1] = \tfrac12, \qquad |\psi'\rangle = |111\rangle \]

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

  1. Compute the matrix of \(\mathrm{CNOT}_{2\to1}\) (control = qubit 1, target = qubit 0).
  2. Is \(\frac{1}{\sqrt2}(|00\rangle + |01\rangle)\) entangled? Factorise if possible. [Ans: product, \(|0\rangle\otimes|+\rangle\)]
  3. Verify that the four Bell states are mutually orthogonal.
  4. Compute \(\rho_A\) for \(\frac{1}{\sqrt3}(|00\rangle + |01\rangle + |10\rangle)\) and its purity. [Ans: purity \(7/9\)]
  5. Show \(\mathrm{SWAP} = \mathrm{CNOT}_{12}\mathrm{CNOT}_{21}\mathrm{CNOT}_{12}\) by acting on all four basis states.
  6. Write the Toffoli matrix and verify it computes reversible AND when \(c=0\).
  7. Explain why the Gottesman–Knill theorem does not contradict the existence of quantum speed-ups.
  8. 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\).