Chapter 6: Multiple Qubits and Entanglement

6.1 Two Qubits: The Tensor Product

A single qubit lives in a two-dimensional complex vector space spanned by $|0\rangle$ and $|1\rangle$. Its general state is described by two complex amplitudes. When we bring a second qubit into the picture, we need to describe the state of both qubits simultaneously. The mathematical tool for combining quantum systems is the tensor product, written $\otimes$.

From one qubit to two

If the first qubit is in state $|\psi\rangle = \alpha|0\rangle + \beta|1\rangle$ and the second qubit is in state $|\phi\rangle = \gamma|0\rangle + \delta|1\rangle$, then the joint state of the two-qubit system is:

We write $|00\rangle$ as shorthand for $|0\rangle \otimes |0\rangle$. The first digit refers to the first qubit (q[0]), the second digit to the second qubit (q[1]).

The four computational basis states

Two qubits have four computational basis states, each corresponding to a classical two-bit string:

A general two-qubit state is a superposition of all four basis states:

with the normalization condition $|\alpha_{00}|^2 + |\alpha_{01}|^2 + |\alpha_{10}|^2 + |\alpha_{11}|^2 = 1$.

A concrete example

Suppose qubit 0 is in state $|+\rangle = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$ and qubit 1 is in state $|0\rangle$. Their tensor product is:

Measuring this system gives $|00\rangle$ half the time and $|10\rangle$ half the time. The results of the two qubits are independent - qubit 0 is randomly 0 or 1, and qubit 1 is always 0 regardless. This is a product state: each qubit has its own well-defined individual state. Try it:

Notice that outcomes $|00\rangle$ and $|10\rangle$ each appear about 50% of the time, while $|01\rangle$ and $|11\rangle$ never appear. The two qubits are uncorrelated. Soon we will see states where this independence breaks down completely.

Exponential growth: the power and the curse

But there is a catch: we cannot access all $2^n$ amplitudes directly. Measurement collapses the state to a single basis state. The art of quantum algorithm design lies in structuring computations so that useful information concentrates in the amplitudes we can observe.

6.2 The CNOT Gate: Creating Correlations

All the gates we met in Chapter 5 - X, H, Z, S, T, and the rotation gates - act on a single qubit. To do anything interesting with multiple qubits, we need gates that create interactions between them. The most important two-qubit gate is the controlled-NOT, or CNOT (also written CX).

How CNOT works

The CNOT gate takes two qubits: a control and a target. If the control qubit is $|1\rangle$, the target qubit is flipped (an X gate is applied). If the control is $|0\rangle$, the target is left alone.

In matrix form, the CNOT gate acting on the basis $\{|00\rangle, |01\rangle, |10\rangle, |11\rangle\}$ is:

Notice that CNOT is its own inverse: applying it twice returns to the original state. On basis states, it computes a reversible XOR: the target becomes (target XOR control).

CNOT on computational basis states

Start with $|10\rangle$ (qubit 0 is 1, qubit 1 is 0). The CNOT with control q[0] and target q[1] flips q[1], producing $|11\rangle$:

CNOT on superpositions: where the magic happens

Now consider what happens when the control qubit is in a superposition. Start with $|+\rangle|0\rangle = \frac{1}{\sqrt{2}}(|00\rangle + |10\rangle)$ and apply CNOT:

The $|00\rangle$ term is unchanged (control is 0), but the $|10\rangle$ term becomes $|11\rangle$ (control is 1, so target flips). The result is something remarkable: a state that cannot be written as a product of two individual qubit states. This is entanglement, and we will explore it deeply in the next section.

Try different input states and see how CNOT transforms them. Experiment with putting qubit 1 in a superposition, or both qubits:

6.3 Entanglement: Spooky But Real

Entanglement is the phenomenon that sets quantum mechanics apart from all of classical physics. Einstein famously called it "spooky action at a distance," and it troubled him deeply. Today, entanglement is not just accepted - it is a resource that powers quantum teleportation, quantum cryptography, and quantum computation itself.

The Bell state $|\Phi^+\rangle$: the simplest entangled state

The state we just created with H followed by CNOT has a name. It is the Bell state $|\Phi^+\rangle$:

Why is this state special? Let us try to write it as a product of individual qubit states. We would need $(\alpha|0\rangle + \beta|1\rangle) \otimes (\gamma|0\rangle + \delta|1\rangle) = \alpha\gamma|00\rangle + \alpha\delta|01\rangle + \beta\gamma|10\rangle + \beta\delta|11\rangle$. Matching coefficients:

From $\alpha\delta = 0$, either $\alpha = 0$ or $\delta = 0$. But if $\alpha = 0$, then $\alpha\gamma = 0 \neq \frac{1}{\sqrt{2}}$. If $\delta = 0$, then $\beta\delta = 0 \neq \frac{1}{\sqrt{2}}$. There is no solution. The state is genuinely entangled - it has no description in terms of individual qubits.

The Bell circuit

The recipe for creating $|\Phi^+\rangle$ is elegantly simple: apply a Hadamard gate to qubit 0, then a CNOT with qubit 0 as control and qubit 1 as target. Step by step:

1. Start: $|00\rangle$
2. After H on q[0]: $\frac{1}{\sqrt{2}}(|0\rangle + |1\rangle) \otimes |0\rangle = \frac{1}{\sqrt{2}}(|00\rangle + |10\rangle)$
3. After CNOT: $\frac{1}{\sqrt{2}}(|00\rangle + |11\rangle) = |\Phi^+\rangle$

Why entanglement is remarkable

When you measure this state, you get $|00\rangle$ half the time and $|11\rangle$ half the time. Never $|01\rangle$ or $|10\rangle$. The two qubits are perfectly correlated: if one is 0, the other is guaranteed to be 0; if one is 1, the other is guaranteed to be 1.

All four Bell states

There are four maximally entangled two-qubit states, called the Bell states (or EPR pairs, after Einstein, Podolsky, and Rosen). They form a complete orthonormal basis for the two-qubit Hilbert space:

Each Bell state is created from a computational basis state by applying H to the first qubit and then CNOT. The four states correspond to the four possible starting states:

The $|\Phi\rangle$ states have correlated qubits (both 0 or both 1). The $|\Psi\rangle$ states have anti-correlated qubits (one 0 and one 1). The $+/-$ superscript indicates the relative phase between the two terms.

What entanglement IS NOT

Entanglement is surrounded by misconceptions. Let us address the most common ones:

• It is not faster-than-light communication. When Alice measures her entangled qubit, she gets a random result. She cannot control what result she gets, so she cannot send a message to Bob. Bob's local measurement statistics look completely random until he compares notes with Alice through a classical channel.
• It is not a physical connection. There is no wire, no field, no signal traveling between entangled particles. Entanglement is a property of the joint quantum state, not a force or interaction.
• It is not like a pair of matching socks. A common analogy: "Put one red sock and one blue sock in two boxes. When you open one and see red, you know the other is blue." But this analogy is wrong. In the sock scenario, the colors were determined at packing time. Bell's theorem proves that quantum outcomes are not predetermined - they are genuinely created at the moment of measurement.

The EPR paradox and Bell's theorem

In 1935, Einstein, Podolsky, and Rosen published a paper arguing that quantum mechanics must be incomplete. Their original argument used continuous position and momentum variables, but David Bohm reformulated it in 1951 using the cleaner language of spin-1/2 particles, which is the version universally taught today. In Bohm's formulation: prepare two particles in the singlet state $|\Psi^-\rangle$ and send them far apart. If Alice measures her qubit and gets $|0\rangle$, she instantly knows Bob's qubit is $|1\rangle$. EPR argued this means Bob's qubit "already had" a definite value - there must be "hidden variables" that quantum mechanics fails to describe.

In 1964, John Bell showed this reasoning leads to a testable prediction. He derived an inequality that any local hidden-variable theory must satisfy. Quantum mechanics predicts violations of this inequality, and experiments - from Alain Aspect's pioneering work in 1982 to the loophole-free tests of 2015 - have consistently confirmed the quantum prediction. Nature really is "spooky." Entangled particles do not carry predetermined values; their correlations are genuinely quantum.

Predict, Observe, Explain: entanglement in action

All four Bell states: interactive exploration

Explore all four Bell states. Each circuit below prepares a different Bell state by changing which qubits start in $|1\rangle$:

6.4 Beyond Two Qubits: Multi-Qubit Systems

Entanglement is not limited to pairs. Three or more qubits can be entangled in ways that have no two-qubit analog. The two most important multi-qubit entangled states are the GHZ state and the W state.

Three qubits: eight dimensions

Three qubits live in a $2^3 = 8$-dimensional state space, spanned by the basis states $|000\rangle, |001\rangle, |010\rangle, |011\rangle, |100\rangle, |101\rangle, |110\rangle, |111\rangle$. A general three-qubit state requires 8 complex amplitudes. The pattern continues: $n$ qubits need $2^n$ amplitudes, and the state space grows exponentially.

The GHZ state

The Greenberger-Horne-Zeilinger (GHZ) state for three qubits is:

This is the natural generalization of $|\Phi^+\rangle$ to three qubits: all qubits are 0 or all qubits are 1, with equal probability. The circuit follows the same pattern as the Bell state, extended with additional CNOT gates:

You should see only $|000\rangle$ and $|111\rangle$, each at roughly 50%. The GHZ state has a striking fragility property: if you trace out (ignore) any single qubit, the remaining two qubits are in a completely mixed state with no entanglement at all. Lose one qubit and the quantum correlations vanish entirely.

The W state

The W state for three qubits is:

Unlike the GHZ state, the W state is robust against qubit loss. If you trace out one qubit, the remaining two are still partially entangled. This makes the W state useful in quantum communication protocols where qubit loss is a realistic concern.

Scaling up

The pattern for GHZ states extends naturally to any number of qubits. An $n$-qubit GHZ state $\frac{1}{\sqrt{2}}(|00\ldots0\rangle + |11\ldots1\rangle)$ uses one Hadamard and $n-1$ CNOT gates. In practice, creating and maintaining large entangled states is one of the central challenges of quantum computing, because entanglement is extremely sensitive to noise and decoherence (Chapter 14).

6.5 Multi-Qubit Gates: Toffoli, SWAP, and Controlled Unitaries

The CNOT is the most common two-qubit gate, but several other multi-qubit gates appear frequently in quantum circuits.

The SWAP gate

The SWAP gate exchanges the states of two qubits: $|01\rangle \leftrightarrow |10\rangle$. Its matrix representation is:

The SWAP gate is crucial because real quantum hardware often has limited connectivity - not every qubit can directly interact with every other. SWAP gates route quantum information to where it needs to be.

We start with $|10\rangle$ (qubit 0 is 1, qubit 1 is 0). After the SWAP, the state becomes $|01\rangle$. A useful fact: SWAP can be decomposed into exactly three CNOT gates:

where $\text{CNOT}_{01}$ has qubit 0 as control and qubit 1 as target, and $\text{CNOT}_{10}$ has qubit 1 as control and qubit 0 as target. Try the decomposition yourself:

Both circuits produce $|01\rangle$ with 100% probability, confirming that the three-CNOT decomposition is equivalent to SWAP.

The controlled-Z (CZ) gate

The controlled-Z gate applies a Z gate to the target qubit when the control is $|1\rangle$. Its effect on basis states is simple: $|11\rangle \to -|11\rangle$, and all other basis states are unchanged:

A notable property: the CZ gate is symmetric in its two qubits. It does not matter which one you call the control and which you call the target. The CZ is related to the CNOT by conjugation with Hadamard gates: $\text{CNOT} = (I \otimes H) \cdot \text{CZ} \cdot (I \otimes H)$.

The Toffoli gate (CCX)

The Toffoli gate, also called CCX (controlled-controlled-NOT), is a three-qubit gate. It flips the target qubit only when both control qubits are $|1\rangle$:

When the target starts in $|0\rangle$, the Toffoli computes the AND of the two controls. It is universal for classical reversible computing, as we saw in Chapter 3.

Both controls are $|1\rangle$, so the target flips from $|0\rangle$ to $|1\rangle$: the result is $|111\rangle$. Try changing one of the X gates to verify that only when both controls are 1 does the target flip.

The Fredkin gate (CSWAP)

The Fredkin gate, or controlled-SWAP (CSWAP), swaps two target qubits only when the control qubit is $|1\rangle$. Like the Toffoli, it is universal for classical reversible computation.

General controlled-U

Any single-qubit gate $U$ can be made into a controlled gate. The controlled-$U$ applies $U$ to the target qubit only when the control is $|1\rangle$. We have already seen examples: CNOT is controlled-X, CZ is controlled-Z. The QASM simulator also supports controlled-Y (cy), controlled-H (ch), and controlled rotations like crz(theta) and cp(phi). This pattern generalizes: for any gate, there is a controlled version.

6.6 Universality: A Small Set of Gates Can Do Anything

One of the most important results in quantum computing is the universality theorem: a small, finite set of gates can approximate any unitary operation on any number of qubits to arbitrary precision.

Universal gate sets

A gate set is universal if any unitary operation can be approximated to arbitrary accuracy using a finite sequence of gates from the set. The most commonly cited universal gate set is:

Just three gates. With Hadamard gates, T gates, and CNOT gates, you can perform any quantum computation to any desired precision.

Why these three? The Hadamard creates superpositions and moves between the $X$ and $Z$ bases. The T gate provides a rotation by $\pi/4$ that, combined with H, can approximate any single-qubit rotation. The CNOT provides the two-qubit interaction needed to create entanglement. Together, they cover all the ingredients of quantum computation.

Other universal gate sets

Many gate sets are universal. Some important ones include:

• $\{H, T, \text{CNOT}\}$ - the standard set
• $\{H, \text{Toffoli}\}$ - using a three-qubit gate instead
• $\{R_y(\theta), R_z(\theta), \text{CNOT}\}$ for irrational $\theta/\pi$ - continuous rotations
• $\{\sqrt{X}, \text{CNOT}, R_z(\theta)\}$ - used by some hardware platforms

The choice of gate set depends on the physical hardware. Superconducting qubits, trapped ions, and photonic systems each have different native gate sets, but universality guarantees they can all perform the same computations.

The Solovay-Kitaev theorem

A natural question: how efficiently can we approximate a desired gate using a finite gate set? The Solovay-Kitaev theorem provides a remarkably strong answer.

Suppose you want to approximate a single-qubit gate $U$ to precision $\epsilon$ (meaning the operator-norm distance between your approximation and $U$ is at most $\epsilon$). If your gate set generates a dense subgroup of $\text{SU}(2)$, the Solovay-Kitaev theorem guarantees that you can achieve this using only $O(\log^c(1/\epsilon))$ gates, where $c$ is a small constant (originally about 3.97, subsequently improved to values close to 1).

The key insight is that this scaling is polylogarithmic: doubling the precision requires only a small additive increase in the number of gates, not a multiplicative one. This means the choice of universal gate set does not significantly affect computational complexity - switching gate sets changes circuit depth by at most a polylogarithmic factor.

6.7 The No-Cloning Theorem

In classical computing, copying information is trivial. You can duplicate a file, copy a bit, or broadcast a message to millions of recipients. In quantum mechanics, this is fundamentally impossible. The no-cloning theorem states that there is no quantum operation that can take an arbitrary unknown quantum state and produce a perfect copy of it.

The theorem

More precisely: there is no unitary operation $U$ that, for every quantum state $|\psi\rangle$, performs:

Proof sketch

The proof is elegant and short, relying only on the linearity of quantum mechanics and the properties of inner products. Suppose such a cloning operation $U$ exists. Then for any two states $|\psi\rangle$ and $|\phi\rangle$:

Take the inner product of both sides. Since $U$ is unitary, it preserves inner products. The left side gives:

The right side gives:

Setting these equal: $\langle\psi|\phi\rangle = \langle\psi|\phi\rangle^2$.

This equation has only two solutions: $\langle\psi|\phi\rangle = 0$ (the states are orthogonal) or $\langle\psi|\phi\rangle = 1$ (the states are identical). A cloning machine can only copy states that are either identical or orthogonal to each other - it cannot work for arbitrary unknown states. This is a fundamental consequence of the linearity of quantum mechanics.

Classical bits CAN be copied

In classical computing, copying is so routine we barely think about it. A classical fan-out gate takes one bit and produces two copies: $0 \to 00$, $1 \to 11$. This works because classical bits are always in definite states. But a qubit in the state $\alpha|0\rangle + \beta|1\rangle$ cannot be duplicated by any physical process. This is perhaps the sharpest distinction between classical and quantum information.

Why no-cloning matters

• Quantum cryptography. No-cloning is the reason quantum key distribution (Chapter 8) works. An eavesdropper cannot copy the quantum states being transmitted without disturbing them, which reveals their presence. This is security guaranteed by physics, not by computational assumptions.
• Quantum error correction. Classical error correction works by making redundant copies of data. Since we cannot copy quantum states, quantum error correction (Part VI) requires entirely different strategies - encoding information into entangled states across multiple qubits without ever copying the original.
• Quantum teleportation. No-cloning explains why quantum teleportation (Chapter 7) necessarily destroys the original state. If it did not, we would have a cloning machine: teleport the state and keep the original.
• No faster-than-light signaling. If cloning were possible, combined with entanglement it would enable superluminal communication. No-cloning is part of the consistency of physics.

Exercises

Chapter Summary

This chapter introduced the concepts that make quantum computing fundamentally more powerful than classical computing:

• Tensor products combine qubit state spaces, creating an exponentially large space: $n$ qubits need $2^n$ amplitudes.
• CNOT is the fundamental two-qubit gate that creates correlations, flipping the target when the control is $|1\rangle$.
• Entanglement occurs when a multi-qubit state cannot be factored into individual qubit states. Entangled qubits show correlations with no classical explanation.
• The four Bell states are maximally entangled two-qubit states that serve as the basic resource for quantum protocols.
• Multi-qubit entanglement (GHZ and W states) exhibits richer structure than two-qubit entanglement, with fundamentally different classes.
• The Toffoli, SWAP, CZ, and Fredkin gates extend our vocabulary beyond CNOT. The SWAP decomposes into three CNOTs.
• The gate set $\{H, T, \text{CNOT}\}$ is universal - it can approximate any quantum computation. The Solovay-Kitaev theorem ensures this approximation is efficient.
• The no-cloning theorem forbids copying unknown quantum states - a fundamental constraint that enables quantum cryptography.

With single-qubit gates (Chapter 5) and multi-qubit gates and entanglement (this chapter), we now have the complete toolkit for quantum computation. In Chapter 7, we will put these tools to work in one of the most remarkable quantum protocols: teleportation.