Entanglement, gates, and the circuit model

A two-qubit state lives in $\mathbb{C}^2 \otimes \mathbb{C}^2 = \mathbb{C}^4$, with basis $|00\rangle, |01\rangle, |10\rangle, |11\rangle$. A general state is

$|\psi\rangle = \alpha_{00}|00\rangle + \alpha_{01}|01\rangle + \alpha_{10}|10\rangle + \alpha_{11}|11\rangle, \quad \sum_{x}|\alpha_x|^2 = 1.$

A product state is one that factors:

$|\psi\rangle = (\alpha|0\rangle + \beta|1\rangle) \otimes (\gamma|0\rangle + \delta|1\rangle).$

Product states describe two qubits whose individual descriptions are independent of each other. An entangled state is any two-qubit state that cannot be written as a product. For example

$|\Phi^+\rangle = \frac{1}{\sqrt{2}}(|00\rangle + |11\rangle)$

is entangled: no choice of $\alpha, \beta, \gamma, \delta$ makes the product factorization work (the cross terms $\alpha\delta|01\rangle$ and $\beta\gamma|10\rangle$ would also have to appear, which they don't). Entanglement is the absence of factorization, not a separate physical phenomenon added on top of superposition.

Take $|\Phi^+\rangle = \frac{1}{\sqrt{2}}(|00\rangle + |11\rangle)$ and measure the first qubit in the standard basis.

• With probability $\frac{1}{2}$, the outcome is 0, and the post-measurement state is $|00\rangle$. The second qubit is now in state $|0\rangle$ with certainty.
• With probability $\frac{1}{2}$, the outcome is 1, and the post-measurement state is $|11\rangle$. The second qubit is now in state $|1\rangle$ with certainty.

The outcomes on the two qubits are perfectly correlated — they always match. This holds regardless of how far apart the two qubits are physically separated.

A classical correlation can match this statistic (two bits set to the same value via a shared random source). The quantum-distinct feature shows up in measurements in other bases. Bell's theorem (1964) and the subsequent CHSH experiments quantify the gap: entangled states violate inequalities that any classical hidden-variable model must satisfy. The structural point is that entanglement is a richer correlation than any classical mixture, and the gap is measurable.

The controlled-NOT (CNOT) gate is a two-qubit unitary: it flips the second (target) qubit if and only if the first (control) qubit is $|1\rangle$. As a $4 \times 4$ matrix in the $|00\rangle, |01\rangle, |10\rangle, |11\rangle$ basis:

$\text{CNOT} = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}.$

Its action on basis states: $|00\rangle \mapsto |00\rangle$, $|01\rangle \mapsto |01\rangle$, $|10\rangle \mapsto |11\rangle$, $|11\rangle \mapsto |10\rangle$.

CNOT is reversible (it is its own inverse) and unitary. Together with single-qubit gates, CNOT is universal: any unitary on $n$ qubits can be approximated to arbitrary precision by a finite circuit of CNOTs and single-qubit gates. The proof is constructive — every $n$-qubit unitary decomposes into a sequence of two-level rotations, each of which can be implemented with single-qubit gates and CNOTs.

Two gates — Hadamard then CNOT — turn two independent $|0\rangle$ qubits into a maximally entangled state.

Trace the circuit step by step.

Start: $|00\rangle$.

Apply Hadamard to qubit 1:

$(H \otimes I)|00\rangle = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle) \otimes |0\rangle = \frac{1}{\sqrt{2}}(|00\rangle + |10\rangle).$

Apply CNOT (control = qubit 1, target = qubit 2):

$\text{CNOT} \cdot \frac{1}{\sqrt{2}}(|00\rangle + |10\rangle) = \frac{1}{\sqrt{2}}(|00\rangle + |11\rangle) = |\Phi^+\rangle.$

The Hadamard puts qubit 1 in equal superposition; the CNOT entangles qubits 1 and 2 by conditioning qubit 2's flip on qubit 1's value, while qubit 1's state is in superposition. The result is one of the four Bell states, the maximally entangled two-qubit states. The other three are produced by similar two-gate circuits with different initial conditions or extra single-qubit gates.

A quantum circuit is a sequence of gates applied to a fixed set of qubits, ending in measurements. The gate count of a circuit is the total number of gates; the depth is the number of layers of gates that cannot be parallelized.

Useful complexity bookkeeping for quantum circuits:

• A general $n$-qubit unitary needs $O(4^n)$ single- and two-qubit gates in the worst case — the exponential is inherent in the dimension of the unitary group.
• Many structured unitaries (those arising in algorithms) admit polynomial-size circuits, which is why they are interesting.
• Decompositions of useful unitaries (e.g., the quantum Fourier transform on $n$ qubits) take $O(n^2)$ gates.
• A constant-depth circuit on $n$ qubits is a parallelizable computation; depth bounds are important for noisy hardware where each layer accumulates errors.

The circuit model is the standard abstraction for analyzing quantum algorithms. Hardware implementations differ on which gate set is native; compilers translate the algorithm's preferred gates into the hardware's native set with bounded overhead.

A universal gate set is a finite collection of gates from which every unitary can be approximated to arbitrary precision. The Solovay–Kitaev theorem makes this precise: any universal gate set approximates an arbitrary unitary within error $\epsilon$ using $O(\log^c(1/\epsilon))$ gates, where $c$ is a small constant (around 4 in the original proof, improved since).

Standard universal sets include:

• {H, T, CNOT} — Hadamard, $T = \begin{pmatrix} 1 & 0 \\ 0 & e^{i\pi/4} \end{pmatrix}$, and CNOT.
• {H, S, T, CNOT} where $S = T^2$ — convenient for fault-tolerant implementations.
• Clifford + T — the Clifford gates (H, S, CNOT) are not universal on their own, but adding T makes them so.

The Clifford gates are special because they can be efficiently simulated classically (Gottesman–Knill theorem). Useful quantum speedup therefore requires non-Clifford gates, of which $T$ is the canonical minimal addition. Hardware implementations vary in how cheap and how noisy non-Clifford gates are; this distinction drives many error-correction trade-offs (the next lesson).

Entanglement is a resource — quantifiable, consumable, and necessary for most quantum advantages.

What it enables.

• Quantum teleportation: an unknown qubit's state can be transferred between two parties who share an entangled pair, using two classical bits of communication.
• Superdense coding: two classical bits can be transmitted by sending one qubit, when the parties share an entangled pair beforehand.
• Quantum algorithms: most known speedups (Shor, simulation, quantum walk algorithms) require entanglement at intermediate steps; without it, the computation can be efficiently simulated classically.

What it does not enable.

• Faster-than-light communication. Measurements on entangled qubits produce correlated outcomes, but the outcome on each side is locally random. No information is transmitted by the act of measurement.
• Copying. The no-cloning theorem from the previous lesson still applies; entanglement does not let you duplicate an unknown state.
• Unbounded computational speedup for all problems. Most problems (search-style problems beyond the structure that algorithms exploit) gain at most a quadratic Grover-style speedup, which is polynomial.

The specific algorithmic exploitations of entanglement are the subject of the algorithms lesson later in the cursus.