Multi-Qubit Computation

When a computational problem takes an \(n\)-bit input string, our quantum computer uses an \(n\)-qubit register. How do we write the basis states of \(n\) qubits? For two qubits, we saw in Section 4.2.3 that the composite-state postulate assigns an amplitude to each two-bit configuration, and that two independently prepared qubits combine via the tensor product:

\[\begin{pmatrix}a\\b\end{pmatrix}\otimes\begin{pmatrix}c\\d\end{pmatrix} = \begin{pmatrix}ac\\ad\\bc\\bd\end{pmatrix}.\]

Adding a third qubit—or \(n\) qubits in general—simply repeats the tensor product. For each \(n\)-bit string \(x = x_1x_2\cdots x_n \in \{0,1\}^n\), the corresponding computational basis vector of the register is the tensor product of the individual qubit basis states:

\[\ket{x} = \ket{x_1}\otimes\ket{x_2}\otimes\cdots\otimes\ket{x_n} = \ket{x_1x_2\cdots x_n}.\]

These \(2^n\) mutually orthogonal unit vectors form the product basis (or computational basis) of the \(n\)-qubit register. By convention, the leftmost bit \(x_1\) labels the first (topmost) qubit, so \(\ket{01}\) means qubit \(1\) is in \(\ket{0}\) and qubit \(2\) is in \(\ket{1}\), and we order the basis configurations in standard binary order (\(00, 01, 10, 11\) for two qubits).

In addition to the qubits that hold the problem input, a quantum register often includes extra working qubits called ancillas, initialized in \(\ket{0}\), just like the scratchpad bits of our reversible circuits in Chapter 2. Preparing ancillas and resetting them via uncomputation are part of the algorithm's total cost.

In a multi-qubit circuit diagram, each qubit has its own horizontal wire, ordered from qubit \(1\) at the top to qubit \(n\) at the bottom. A gate box placed on a single wire acts on that qubit alone, whereas a gate spanning multiple wires couples those qubits together. When a wire is drawn with a diagonal slash through it (sometimes labeled with an integer \(n\)), it represents an entire bundle of \(n\) qubit wires drawn compactly as a single line.

When can an \(n\)-qubit register be described by assigning each qubit its own individual state vector? Precisely when the joint state vector factors into a tensor product of single-qubit states, \(\ket{\psi_1}\otimes\ket{\psi_2}\otimes\cdots\otimes\ket{\psi_n}\). As we saw for two qubits in Section 4.2.3, such a state is called a product state. In a product state, every joint amplitude is the product of the corresponding single-qubit amplitudes, which guarantees that measurements on different qubits are statistically independent.

How can we tell from a list of joint amplitudes whether a state is a product state? Do not be fooled by how many basis terms appear in the superposition! A state with two or four nonzero computational-basis terms can still be a simple product state. For example, \((\ket{00}+\ket{10})/\sqrt{2}\) is a superposition of two bit strings, yet factoring out \(\ket{0}\) on the second qubit reveals

\[\frac{\ket{00}+\ket{10}}{\sqrt{2}} = \left(\frac{\ket{0}+\ket{1}}{\sqrt{2}}\right)\otimes\ket{0},\]

meaning the first qubit is in \(\ket{+}\) and the second is definitely in \(\ket{0}\). Even a state in which all four two-qubit basis configurations have nonzero amplitudes can be a product state:

\[\frac{\sqrt{3}\ket{00}+\sqrt{3}\ket{01}+\ket{10}+\ket{11}}{2\sqrt{2}} = \left(\frac{\sqrt{3}\ket{0}+\ket{1}}{2}\right)\otimes\left(\frac{\ket{0}+\ket{1}}{\sqrt{2}}\right).\]

Here, measuring the first qubit yields \(0\) with probability \(3/4\) regardless of what happens to the second qubit, and measuring the second yields \(0\) or \(1\) with probability \(1/2\) regardless of the first. Whether a two-qubit state \(c_{00}\ket{00} + c_{01}\ket{01} + c_{10}\ket{10} + c_{11}\ket{11}\) factors into \((a\ket{0}+b\ket{1})\otimes(c\ket{0}+d\ket{1})\) depends not on how many amplitudes are nonzero, but on whether the amplitudes satisfy the factorization test \(c_{00}c_{11} = c_{01}c_{10}\). When they do, the qubits are independent; when they do not, the state is entangled.

How many complex numbers are required to specify the state of an \(n\)-qubit register? By the composite-state postulate, any normalized superposition of the \(2^n\) product-basis states is a valid physical state:

\[\ket{\Psi} = \sum_{x\in\{0,1\}^n} c_x\ket{x},\qquad \sum_{x\in\{0,1\}^n} |c_x|^2 = 1.\]

Thus a general \(n\)-qubit state vector carries \(2^n\) complex amplitudes—one for every \(n\)-bit string \(x\). By contrast, an \(n\)-qubit product state \(\ket{\psi_1}\otimes\cdots\otimes\ket{\psi_n}\) is completely specified by giving two amplitudes for each qubit, or just \(2n\) complex numbers in total. Each additional qubit doubles the dimension \(2^n\) of the full state space while adding only \(2\) coordinates to a product-state description.

Does measuring an \(n\)-qubit register read out those \(2^n\) complex amplitudes? Never. A computational-basis measurement of all \(n\) qubits returns a single \(n\)-bit string \(x\) with probability \(|c_x|^2\)—just \(n\) classical bits of output from a state vector of \(2^n\) complex numbers.

Simulating a general \(n\)-qubit circuit by tracking all \(2^n\) amplitudes on a classical computer quickly becomes prohibitive: \(30\) qubits require more than a billion complex numbers, and \(300\) qubits require more amplitudes than there are atoms in the observable universe. Yet the sheer size of the state space does not automatically make a quantum computer fast: because readout yields only \(n\) bits, an algorithm achieves a speedup only when it uses interference to concentrate probability onto the specific \(n\)-bit string that answers the problem.

When we apply a single-qubit gate \(U\) to the first wire of a two-qubit register and do nothing (\(I\)) to the second wire, how does the combined operation transform the four-dimensional state space? It updates the first bit label according to the arrows of \(U\) while leaving the second bit label untouched: for each value \(b\in\{0,1\}\) of the second qubit, the transition amplitude from \(\ket{ib}\) to \(\ket{jb}\) is simply \(\bra{j}U\ket{i}\). We write this tensor-product operator as \(U\otimes I\). Acting on a product state, each operator acts independently on its own slot:

\[(U\otimes I)(\ket{\psi}\otimes\ket{\phi}) = (U\ket{\psi})\otimes\ket{\phi}.\]

More generally, applying \(U\) to the first qubit and \(V\) to the second is written \(U\otimes V\), which maps \(\ket{\psi}\otimes\ket{\phi}\) to \((U\ket{\psi})\otimes(V\ket{\phi})\); when the same gate \(H\) is applied to each of \(n\) qubits, we write \(H^{\otimes n}\). Gates that act on individual wires separately are called local gates. Because local gates on distinct wires operate on independent subsystems, hardware can execute them in parallel during a single time step.

Can local gates ever entangle two initially independent qubits? The equation \((U\otimes V)(\ket{\psi}\otimes\ket{\phi}) = (U\ket{\psi})\otimes(V\ket{\phi})\) immediately says no: any tensor product of local gates sends every product state to another product state. To create correlations or entanglement between wires, a circuit needs a multi-qubit gate whose action on one qubit depends on the state of another.

The fundamental two-qubit coupling gate is the controlled-NOT, or CNOT, which we met for classical reversible bits in Chapter 2. With the first qubit as the control and the second as the target, CNOT acts on the computational basis states by flipping the target bit if and only if the control bit is \(1\):

\[\operatorname{CNOT}\ket{a}\ket{b} = \ket{a}\ket{b\oplus a},\qquad a,b\in\{0,1\},\]

where \(\oplus\) is addition modulo \(2\) (XOR). In a circuit diagram, CNOT is drawn as a filled dot on the control wire connected by a vertical line to a \(\oplus\) symbol on the target wire. Remember that the control dot is not a measurement: CNOT is a coherent linear operator that applies this basis rule simultaneously to every branch of a superposition.

Written as a \(4\times 4\) matrix in the basis order \(00, 01, 10, 11\), CNOT leaves the first two coordinates (\(\ket{00}\) and \(\ket{01}\)) unchanged and swaps the last two coordinates (\(\ket{10}\) and \(\ket{11}\)):

\[\begin{pmatrix}c_{00}\\c_{01}\\c_{10}\\c_{11}\end{pmatrix} \longmapsto \begin{pmatrix}c_{00}\\c_{01}\\c_{11}\\c_{10}\end{pmatrix}.\]

Because permuting coordinates preserves vector lengths and swapping twice restores the original column, CNOT is unitary and equals its own inverse (\(\operatorname{CNOT}^2 = I\)). More generally, for any single-qubit unitary \(U\), a controlled gate (controlled-\(U\)) applies the identity \(I\) to the target wire on branches where the control is \(\ket{0}\) and applies \(U\) to the target wire on branches where the control is \(\ket{1}\).

Let us trace a two-qubit circuit that combines local gates and a CNOT. Starting from \(\ket{00}\), apply \(H\) to the top wire and \(X\) to the bottom wire in parallel:

\[(H\otimes X)\ket{00} = (H\ket{0})\otimes(X\ket{0}) = \left(\frac{\ket{0}+\ket{1}}{\sqrt{2}}\right)\otimes\ket{1} = \frac{\ket{01}+\ket{11}}{\sqrt{2}}.\]

If we measured both qubits right now, we would obtain \(01\) or \(11\) with probability \(1/2\) each—the second bit would always be \(1\). Instead, apply CNOT before measuring: the branch \(\ket{01}\) (control \(0\)) stays \(\ket{01}\), while \(\ket{11}\) (control \(1\)) flips its target to become \(\ket{10}\), producing \((\ket{01}+\ket{10})/\sqrt{2}\). Now measuring both qubits yields \(01\) or \(10\) with probability \(1/2\) each, so the two bits are guaranteed to be opposite!

Algebraically, the full unitary evolution before measurement is \(U = \operatorname{CNOT}(H\otimes X)\), read right to left. This circuit uses two qubits (its width) and three elementary gates (\(H\), \(X\), and CNOT). Because \(H\) and \(X\) act on separate wires during the first time step and CNOT acts in the second time step, the circuit has two sequential gate layers—a quantity called the circuit depth.

Suppose we start two qubits in the product state \(\ket{00}\), apply a Hadamard gate \(H\) to the first qubit, and then apply CNOT with the first qubit as control and the second as target. Let us follow the state vector step by step:

First, \(H\otimes I\) puts the control qubit into \(\ket{+}\) while leaving the target in \(\ket{0}\), giving the product state \((\ket{00}+\ket{10})/\sqrt{2}\). Second, CNOT acts linearly on the two branches: it leaves \(\ket{00}\) unchanged (since the control bit is \(0\)) and flips the target of \(\ket{10}\) to produce \(\ket{11}\) (since the control bit is \(1\)):

\[\ket{00} \xrightarrow{\ H\otimes I\ } \frac{\ket{00}+\ket{10}}{\sqrt{2}} \xrightarrow{\ \operatorname{CNOT}\ } \frac{\ket{00}+\ket{11}}{\sqrt{2}}.\]

This famous two-qubit state is called a Bell state (or EPR pair), denoted \(\ket{\Phi^+}\).

Notice again that the vertical control line of CNOT does not measure the first qubit to decide whether to flip the second. Because CNOT acts coherently on both branches of the superposition without recording which branch was taken outside the pair, the output is the single coherent superposition \(\ket{\Phi^+} = (\ket{00}+\ket{11})/\sqrt{2}\), rather than a random choice between \(\ket{00}\) and \(\ket{11}\).

Why is \(\ket{\Phi^+} = (\ket{00}+\ket{11})/\sqrt{2}\) an entangled state rather than a product state? As we checked in Section 4.2.3, any two-qubit product state \((a\ket{0}+b\ket{1})\otimes(c\ket{0}+d\ket{1})\) has amplitudes \(c_{00}=ac\), \(c_{01}=ad\), \(c_{10}=bc\), and \(c_{11}=bd\), which must satisfy \(c_{00}c_{11} = c_{01}c_{10}\). For \(\ket{\Phi^+}\), we have \(c_{00}c_{11} = (1/\sqrt{2})(1/\sqrt{2}) = 1/2\), whereas \(c_{01}c_{10} = 0\cdot 0 = 0\). No choice of single-qubit amplitudes \(a, b, c, d\) can make \(ac\) and \(bd\) nonzero while keeping \(ad\) and \(bc\) zero!

Look at where entanglement entered the circuit: after the local gate \(H\otimes I\), the state \((\ket{0}+\ket{1})/\sqrt{2}\otimes\ket{0}\) was still a product state. It was the two-qubit CNOT gate that turned the local superposition of the control qubit into a non-factorizable joint superposition of the pair.

In an entangled state like \(\ket{\Phi^+}\), the two-qubit register as a whole has a completely definite unit state vector, allowing us to calculate the probability of any joint or single-qubit measurement. What fails is any attempt to assign a standalone single-qubit state vector to qubit \(1\) and another to qubit \(2\).

Does observing perfectly correlated bits (\(00\) half the time and \(11\) half the time) in the computational basis prove that two qubits are in the state \(\ket{\Phi^+}\)? Not by itself! Suppose someone flips a fair classical coin and prepares the product state \(\ket{00}\) on heads or the product state \(\ket{11}\) on tails. In such a classical mixture, each run contains a definite basis state (\(\ket{00}\) or \(\ket{11}\)), and we average classical probabilities across runs rather than adding amplitudes within a single state. Yet measuring that classical mixture in the computational basis yields \(00\) with probability \(1/2\) and \(11\) with probability \(1/2\)—the exact same histogram as \(\ket{\Phi^+}\). To expose the coherent superposition linking \(\ket{00}\) and \(\ket{11}\) in \(\ket{\Phi^+}\), we must measure in a second basis.

Even when a two-qubit state \(\ket{\Psi} = \sum_{a,b\in\{0,1\}} c_{ab}\ket{ab}\) is entangled, all outcome probabilities follow directly from the Born rule. Measuring both qubits in the computational basis yields the outcome pair \((a,b)\) with joint probability \(p(a,b) = |c_{ab}|^2\). The probability that the first qubit yields outcome \(a\) regardless of what happens to the second is the marginal probability, obtained by summing over the second qubit's outcomes: \(p(a) = \sum_{b\in\{0,1\}} p(a,b) = |c_{a0}|^2 + |c_{a1}|^2\). And once the first qubit is observed to give outcome \(a\) (with \(p(a) > 0\)), the conditional probability that the second qubit yields \(b\) is \(p(b\mid a) = p(a,b)/p(a)\).

For the Bell state \(\ket{\Phi^+} = (\ket{00}+\ket{11})/\sqrt{2}\), the joint probabilities are \(p(0,0) = 1/2\) and \(p(1,1) = 1/2\) (with \(p(0,1)=p(1,0)=0\)). Each qubit's marginal distribution is completely uniform—\(p(a=0) = 1/2\) and \(p(a=1) = 1/2\)—yet the conditional probabilities are completely locked together: \(p(b=0\mid a=0) = 1\) and \(p(b=1\mid a=1) = 1\).

What happens to the two-qubit state vector if we measure only the first qubit and obtain outcome \(a\)? Just as for a single qubit, we project onto the subspace consistent with the observed outcome—retaining all terms whose first bit is \(a\) and discarding the rest—and renormalize by dividing by \(\sqrt{p(a)}\). For example, if a register is in the state \((\ket{00}+\ket{01}+\ket{11})/\sqrt{3}\) and a measurement of the first qubit yields \(0\) (which occurs with marginal probability \(p(a=0) = 1/3 + 1/3 = 2/3\)), the post-measurement state collapses to \((\ket{00}+\ket{01})/\sqrt{2} = \ket{0}\otimes\ket{+}\).

Now let us see how measuring both qubits in the diagonal \(X\) basis \(\{\ket{+},\ket{-}\}\) cleanly distinguishes the entangled state \(\ket{\Phi^+}\) from a \(50/50\) classical mixture of \(\ket{00}\) and \(\ket{11}\). As we saw in Section 4.2.2, measuring a qubit in the \(X\) basis is equivalent to applying a Hadamard gate \(H\) (which maps \(\ket{+}\mapsto\ket{0}\) and \(\ket{-}\mapsto\ket{1}\)) followed by a computational-basis measurement. Let us apply \(H\otimes H\) to the two terms of \(\ket{\Phi^+}\):

\[(H\otimes H)\ket{00} = \frac{\ket{00}+\ket{01}+\ket{10}+\ket{11}}{2},\qquad (H\otimes H)\ket{11} = \frac{\ket{00}-\ket{01}-\ket{10}+\ket{11}}{2}.\]

When we add these two expressions with weight \(1/\sqrt{2}\) for \(\ket{\Phi^+} = (\ket{00}+\ket{11})/\sqrt{2}\), the cross terms \(\ket{01}\) and \(\ket{10}\) destructively cancel while \(\ket{00}\) and \(\ket{11}\) constructively reinforce, leaving \((H\otimes H)\ket{\Phi^+} = (\ket{00}+\ket{11})/\sqrt{2} = \ket{\Phi^+}\). Consequently, when both qubits of \(\ket{\Phi^+}\) are measured in the \(X\) basis, their outcomes (whether \(++\) or \(--\)) still agree \(100\%\) of the time! By contrast, in the classical mixture of \(\ket{00}\) and \(\ket{11}\), each run starts in either \(\ket{00}\) alone or \(\ket{11}\) alone; applying \(H\otimes H\) to either basis state spreads probability \(1/4\) across all four outcomes \(00, 01, 10, 11\), so the two \(X\)-basis measurements agree only half the time, by pure chance. Coherence between \(\ket{00}\) and \(\ket{11}\) is invisible in the \(Z\) basis alone, but unmistakable as soon as we also test in the \(X\) basis.

In classical computing, copying a bit is trivial: fan-out splits a wire, or a CNOT gate with a target initialized to \(0\) copies any basis bit \(x\in\{0,1\}\) via \(\operatorname{CNOT}\ket{x}\ket{0} = \ket{x}\ket{x}\). Specifically, \(\ket{0}\ket{0}\mapsto\ket{0}\ket{0}\) and \(\ket{1}\ket{0}\mapsto\ket{1}\ket{1}\).

What happens if we feed a superposition \(\ket{\psi} = \alpha\ket{0} + \beta\ket{1}\) into the control of that same CNOT gate? By linearity,

\[\operatorname{CNOT}(\alpha\ket{0}+\beta\ket{1})\ket{0} = \alpha\ket{00} + \beta\ket{11}.\]

Compare this output with what a genuine two-copy state \(\ket{\psi}\otimes\ket{\psi}\) would look like:

\[\ket{\psi}\otimes\ket{\psi} = (\alpha\ket{0}+\beta\ket{1})\otimes(\alpha\ket{0}+\beta\ket{1}) = \alpha^2\ket{00} + \alpha\beta\ket{01} + \alpha\beta\ket{10} + \beta^2\ket{11}.\]

Whenever both \(\alpha\) and \(\beta\) are nonzero, the two expressions are completely different: \(\ket{\psi}\otimes\ket{\psi}\) is a product state containing cross terms \(\alpha\beta\ket{01}\) and \(\alpha\beta\ket{10}\), whereas \(\operatorname{CNOT}\ket{\psi}\ket{0} = \alpha\ket{00}+\beta\ket{11}\) is an entangled state that has no \(\ket{01}\) or \(\ket{10}\) terms at all! Instead of cloning the superposition \(\ket{\psi}\), CNOT copies only the computational basis labels \(0\) and \(1\), entangling the two wires in the process.

Even if CNOT fails to copy superpositions, could some more sophisticated unitary operator \(U\) clone every unknown quantum state? Suppose a hypothetical cloning unitary \(U\) satisfied \(U(\ket{\psi}\otimes\ket{0}) = \ket{\psi}\otimes\ket{\psi}\) for all states \(\ket{\psi}\). Let us test this equation on two arbitrary states \(\ket{\psi}\) and \(\ket{\phi}\) using the fact that every unitary operator preserves inner products. First, how do we compute the inner product between two product states \(\ket{u}\otimes\ket{v}\) and \(\ket{x}\otimes\ket{y}\)? Expanding in the product basis shows that the inner product of tensor products is simply the product of their individual inner products:

\[\bigl(\bra{u}\otimes\bra{v}\bigr)\bigl(\ket{x}\otimes\ket{y}\bigr) = \sum_{i,j} u_i^* v_j^* x_i y_j = \left(\sum_i u_i^* x_i\right)\left(\sum_j v_j^* y_j\right) = \braket{u}{x}\braket{v}{y}.\]

Now equate the inner product of the two states before \(U\) acts—namely \(\ket{\phi}\otimes\ket{0}\) and \(\ket{\psi}\otimes\ket{0}\)—with the inner product of their putative cloned outputs \(\ket{\phi}\otimes\ket{\phi}\) and \(\ket{\psi}\otimes\ket{\psi}\):

\[\braket{\phi}{\psi}\braket{0}{0} = \braket{\phi}{\psi}\braket{\phi}{\psi} \quad\Longrightarrow\quad \braket{\phi}{\psi} = \bigl(\braket{\phi}{\psi}\bigr)^2.\]

A complex number \(z = \braket{\phi}{\psi}\) satisfies \(z = z^2\) if and only if \(z = 0\) or \(z = 1\)! That means a single unitary \(U\) can copy both \(\ket{\psi}\) and \(\ket{\phi}\) only if the two states are either identical (\(\braket{\phi}{\psi}=1\)) or orthogonal (\(\braket{\phi}{\psi}=0\)). It can never copy two distinct non-orthogonal states—such as \(\ket{0}\) and \(\ket{+}\), whose inner product is \(\braket{0}{+} = 1/\sqrt{2} \notin \{0,1\}\). This fundamental impossibility is the no-cloning theorem: no unitary operation (even aided by extra workspace qubits) can duplicate an arbitrary unknown quantum state.

Be careful to note what the no-cloning theorem does and does not forbid. It does not forbid copying states chosen from a known mutually orthogonal set (such as \(\{\ket{0},\ket{1}\}\), which CNOT copies perfectly), nor does it prevent us from preparing multiple copies of a state when we know the classical circuit recipe that creates it from \(\ket{0}\). What is physically impossible is a universal copying machine that takes a single copy of an unknown state \(\ket{\psi}\) and outputs \(\ket{\psi}\otimes\ket{\psi}\).

Suppose Alice and Bob sit in distant laboratories, separated by light-years, sharing the entangled Bell pair \(\ket{\Phi^+} = (\ket{00}+\ket{11})/\sqrt{2}\). Alice holds the first qubit; Bob holds the second. If Alice measures her qubit and observes \(0\), the measurement postulate dictates that the two-qubit state collapses instantaneously to \(\ket{00}\). At that very moment, Bob’s qubit is guaranteed to be \(\ket{0}\). Nothing in the mathematical rule mentions spatial distance or propagation time. Could Alice exploit this instantaneous collapse to send Bob a message faster than light? To settle the question, we must look at what Bob can actually observe in his own laboratory.

Before Alice touches her qubit, what is Bob’s probability of observing \(0\)? Because Bob has access only to his own qubit, his outcome is governed by a marginal probability—the sum of the joint probabilities for all outcomes where the second bit is \(0\):

\[p_B(0) = p(0,0) + p(1,0) = \tfrac{1}{2} + 0 = \tfrac{1}{2}.\]

Now suppose Alice performs a measurement in the computational basis, but does not send Bob a message. Two things can happen. With probability \(1/2\), Alice gets \(0\), collapsing the system to \(\ket{00}\), so Bob is certain to see \(0\). With probability \(1/2\), Alice gets \(1\), collapsing the system to \(\ket{11}\), so Bob is certain to see \(1\). Because Bob has received no communication from Alice, he does not know which branch occurred. His observed probability of seeing \(0\) is therefore the statistical average of the two conditional probabilities, weighted by how likely each case was:

\[p_B^{\text{after}}(0) = \tfrac{1}{2}\cdot 1 + \tfrac{1}{2}\cdot 0 = \tfrac{1}{2}.\]

The probability has not moved by a hair. Alice’s measurement certainly collapsed the global state, but because she cannot choose which outcome occurs, her action looks to Bob like a fair coin toss that leaves his local statistics completely undisturbed.

Could this invariance be a mere coincidence of the Bell pair’s perfect \(50/50\) symmetry? Furthermore, Alice has far more freedom than simply measuring: what if she applies an arbitrary local unitary gate \(U_A\) to her qubit, or what if Bob tests his qubit in another basis? To test this rigorously, let us examine an asymmetric, lopsided state:

\[\ket{\Psi} = \frac{\ket{00}+\ket{01}+\ket{11}}{\sqrt{3}}.\]

Each of the three terms carries probability \(1/3\). Initially, Bob sees \(0\) only through \(\ket{00}\) (since there is no \(\ket{10}\) term), so his marginals are \(p_B(0) = 1/3\) and \(p_B(1) = 2/3\). Alice, by contrast, observes \(0\) through \(\ket{00}\) and \(\ket{01}\), giving \(p_A(0) = 2/3\).

Now let Alice apply a local Hadamard gate, \(H\otimes I\). The operation acts solely on Alice's bit while leaving Bob's wire untouched:

\[(H\otimes I)\ket{\Psi} = \frac{\ket{00} + 2\ket{01} + \ket{10}}{\sqrt{6}}.\]

Alice’s local statistics shift dramatically: her probability of observing \(0\) jumps from \(2/3\) to \(p_A(0) = 1/6 + 4/6 = 5/6\). But what happens to Bob? Bob sees \(0\) through \(\ket{00}\) and \(\ket{10}\), and \(1\) through \(\ket{01}\):

\[p_B(0) = \tfrac{1}{6} + \tfrac{1}{6} = \tfrac{1}{3},\qquad p_B(1) = \tfrac{4}{6} = \tfrac{2}{3}.\]

Even though the global state was transformed and Alice's local distribution changed by \(16.7\%\), Bob's marginal probabilities remain strictly \(1/3\) and \(2/3\)—identical to his starting numbers!

Why does this invariance hold for every state and every possible gate? The key is to group the terms of an arbitrary two-qubit state \(\ket{\Psi} = \sum_{a,b} c_{ab}\ket{ab}\) according to Bob’s bit:

\[\ket{\Psi} = \bigl(c_{00}\ket{0} + c_{10}\ket{1}\bigr)\otimes\ket{0} \;+\; \bigl(c_{01}\ket{0} + c_{11}\ket{1}\bigr)\otimes\ket{1} = \ket{v_0}\otimes\ket{0} + \ket{v_1}\otimes\ket{1}.\]

Here \(\ket{v_b} = c_{0b}\ket{0} + c_{1b}\ket{1}\) is the unnormalized state on Alice's qubit that accompanies Bob's bit \(b\). Bob's probability of observing \(b\) is simply the squared Euclidean length of \(\ket{v_b}\): \(p_B(b) = |c_{0b}|^2 + |c_{1b}|^2 = \|\ket{v_b}\|^2\). Any local unitary operation \(U_A\otimes I\) transforms each term to \((U_A\ket{v_b})\otimes\ket{b}\). Because unitary transformations preserve lengths and inner products (they are isometries), \(\|U_A\ket{v_b}\|^2 = \|\ket{v_b}\|^2\). Alice's gate reshuffles amplitudes among her own basis labels, but it can never transfer amplitude across Bob's orthogonal sectors \(\ket{0}\) and \(\ket{1}\).

What if Bob chooses to measure in a different basis, such as the \(X\) basis? Measuring in another basis corresponds to applying a local unitary \(V_B\) before measuring in the computational basis. Because operations on distinct wires act on independent tensor factors, they commute: \((U_A\otimes I)(I\otimes V_B) = (I\otimes V_B)(U_A\otimes I)\). We can mathematically evaluate the circuit as if Bob applied \(V_B\) first, which merely produces a new two-qubit state to which our length-preservation argument immediately applies. Alice’s local gate is undetectable in every basis Bob can choose.

Finally, what if Alice measures her qubit? If Alice measures in the computational basis, she obtains outcome \(a\) with probability \(p_A(a) = |c_{a0}|^2 + |c_{a1}|^2\), collapsing the state and leaving Bob with the conditional probability \(p(b\mid a) = |c_{ab}|^2 / p_A(a)\). Without Alice's message, Bob’s observed distribution is the unconditioned average over Alice’s possible results:

\[p_B^{\text{after}}(b) = \sum_a p_A(a)\,p(b\mid a) = \sum_a p_A(a)\,\frac{|c_{ab}|^2}{p_A(a)} = \sum_a |c_{ab}|^2 = p_B(b).\]

The normalization denominator \(p_A(a)\) of each collapsed branch is exactly cancelled by the probability with which that branch occurs! Bob’s local statistics remain untouched.

This fundamental principle is the no-signalling theorem: no local unitary operation or measurement performed on one half of an entangled state can alter the outcome statistics on the other half. Entanglement creates correlations between separated measurements, but it never constitutes a communication channel. Alice and Bob can witness their correlation only when they meet or transmit their classical measurement records over an ordinary communication channel that respects the cosmic speed limit of light.

Suppose Alice holds a qubit in an unknown state \(\ket{\psi} = \alpha\ket{0} + \beta\ket{1}\) and wants to deliver that exact state to Bob. She has no quantum channel left to send the physical qubit to Bob, she cannot clone \(\ket{\psi}\), and if she simply measured \(\ket{\psi}\) she would obtain only a single random bit while collapsing the state and losing the amplitudes \(\alpha\) and \(\beta\). However, suppose Alice and Bob previously shared a two-qubit Bell state \(\ket{\Phi^+} = (\ket{00}+\ket{11})/\sqrt{2}\), with Alice holding the first half and Bob holding the second.

The three-qubit system—ordered as (1) Alice's input qubit, (2) Alice's half of the Bell pair, and (3) Bob's half of the Bell pair—starts in the product of \(\ket{\psi}\) and \(\ket{\Phi^+}\):

\[\ket{\psi}\otimes\ket{\Phi^+} = (\alpha\ket{0}+\beta\ket{1})\otimes\frac{\ket{00}+\ket{11}}{\sqrt{2}} = \frac{\alpha\ket{000}+\alpha\ket{011}+\beta\ket{100}+\beta\ket{111}}{\sqrt{2}}.\]

Notice that Bob's third wire already carries combinations of \(\ket{0}\) and \(\ket{1}\), while Alice holds the first two wires in her laboratory. To couple her unknown input qubit to the shared entangled pair, Alice first applies a CNOT gate with her input qubit (wire 1) as control and her Bell qubit (wire 2) as target. This flips the middle bit whenever the first bit is \(1\), transforming the three-qubit state into

\[\frac{\alpha\ket{000}+\alpha\ket{011}+\beta\ket{110}+\beta\ket{101}}{\sqrt{2}}.\]

Next, Alice applies a Hadamard gate \(H\) to her first wire so that the two branches \(\alpha\) and \(\beta\) interfere across her local basis states.

Let us see what state emerges when Alice applies \(H\) to the first qubit of \((\alpha\ket{000}+\alpha\ket{011}+\beta\ket{110}+\beta\ket{101})/\sqrt{2}\). Substituting \(H\ket{0} = (\ket{0}+\ket{1})/\sqrt{2}\) and \(H\ket{1} = (\ket{0}-\ket{1})/\sqrt{2}\) on the first wire expands the four terms into eight:

\[\frac{1}{2}\bigl(\alpha\ket{000}+\alpha\ket{100}+\alpha\ket{011}+\alpha\ket{111}+\beta\ket{010}-\beta\ket{110}+\beta\ket{001}-\beta\ket{101}\bigr).\]

Now regroup these eight terms according to the four possible computational-basis configurations \(\ket{mn}\) of Alice's two qubits (wires 1 and 2):

• When Alice's wires are \(\ket{00}\), Bob's wire carries \(\alpha\ket{0}+\beta\ket{1} = \ket{\psi}\).
• When Alice's wires are \(\ket{01}\), Bob's wire carries \(\alpha\ket{1}+\beta\ket{0} = X\ket{\psi}\).
• When Alice's wires are \(\ket{10}\), Bob's wire carries \(\alpha\ket{0}-\beta\ket{1} = Z\ket{\psi}\).
• When Alice's wires are \(\ket{11}\), Bob's wire carries \(\alpha\ket{1}-\beta\ket{0} = XZ\ket{\psi}\).

Thus the entire three-qubit state before Alice's measurement can be written as

\[\frac{1}{2}\Bigl(\ket{00}\otimes\ket{\psi} + \ket{01}\otimes(X\ket{\psi}) + \ket{10}\otimes(Z\ket{\psi}) + \ket{11}\otimes(XZ\ket{\psi})\Bigr).\]

This algebraic identity is the heart of teleportation. Notice that each of the four branches has squared norm \((1/2)^2(|\alpha|^2+|\beta|^2) = 1/4\), completely independent of the unknown amplitudes \(\alpha\) and \(\beta\)! When Alice measures her two qubits in the computational basis, she obtains one of the four two-bit outcomes \(mn\in\{00, 01, 10, 11\}\) with probability \(1/4\) each, and Bob's qubit immediately collapses to the corresponding conditional state \(X^n Z^m\ket{\psi}\).

Once Alice transmits her two classical bits \((m,n)\) to Bob, Bob applies \(X^n\) (an \(X\) gate if \(n=1\)) followed by \(Z^m\) (a \(Z\) gate if \(m=1\)). Because \(Z^m X^n (X^n Z^m\ket{\psi}) = Z^m I Z^m\ket{\psi} = \ket{\psi}\), Bob recovers the exact state \(\ket{\psi} = \alpha\ket{0} + \beta\ket{1}\) on every single run—without either Alice or Bob ever learning \(\alpha\) or \(\beta\).

Why doesn't teleportation violate the no-signalling principle or the no-cloning theorem? Consider first what Bob has before Alice's two classical bits \((m,n)\) arrive. Without knowing \((m,n)\), Bob holds an equally likely mixture of the four states \(\ket{\psi}\), \(X\ket{\psi}\), \(Z\ket{\psi}\), and \(XZ\ket{\psi}\). If he measures his qubit in the computational basis without waiting for Alice's message, his probability of observing \(0\) is the average across the four equally likely branches:

\[p_B(0) = \frac{1}{4}\bigl(|\alpha|^2 + |\beta|^2 + |\alpha|^2 + |\beta|^2\bigr) = \frac{1}{2}.\]

Even if Bob measures in an arbitrary orthonormal basis containing \(\ket{v} = c\ket{0} + d\ket{1}\), the four branches contribute \(|c^*\alpha + d^*\beta|^2\), \(|c^*\beta + d^*\alpha|^2\), \(|c^*\alpha - d^*\beta|^2\), and \(|c^*\beta - d^*\alpha|^2\); averaging them cancels all the opposite-sign cross terms and leaves \(\tfrac{1}{2}(|c|^2+|d|^2)(|\alpha|^2+|\beta|^2) = 1/2\), completely independent of \(\alpha\) and \(\beta\)! Until the two classical bits arrive at or below the speed of light, Bob's qubit behaves like a completely random coin toss that reveals zero information about \(\ket{\psi}\).

Second, why doesn't teleportation violate the no-cloning theorem? Because Alice's measurement projects her two qubits onto a definite computational basis state \(\ket{mn}\), erasing the superposition \(\alpha\ket{0}+\beta\ket{1}\) on her side and consuming the shared Bell pair \(\ket{\Phi^+}\). At the end of the protocol, only one copy of \(\ket{\psi}\) exists—now located in Bob's laboratory rather than Alice's.

Teleportation is crystal clear as long as we keep three descriptions distinct: the pure three-qubit state vector before measurement, Bob's conditional state \(X^n Z^m\ket{\psi}\) once Alice's outcome \(mn\) is known, and Bob's completely uniform marginal statistics when \(mn\) is unknown.

In Chapter 2, we learned how to evaluate any Boolean function \(f:\{0,1\}^n\to\{0,1\}\) reversibly without losing information: preserve the \(n\)-bit input \(x\) in an input register, XOR the answer \(f(x)\) into a target bit \(y\), and uncompute any temporary workspace. Promoted to a quantum register of \(n\) input qubits and \(1\) target qubit, this reversible map defines the unitary operator \(U_f\):

\[U_f\ket{x}\ket{y} = \ket{x}\ket{y\oplus f(x)}.\]

Because \(U_f\) simply permutes the computational basis states—swapping \(\ket{x}\ket{0}\) and \(\ket{x}\ket{1}\) when \(f(x)=1\) and leaving them fixed when \(f(x)=0\)—it is unitary and can be built directly from Toffoli and CNOT gates at a gate cost comparable to a single classical circuit evaluation of \(f\).

What happens when we feed a superposition of inputs into \(U_f\)? Start with two input qubits initialized to \(\ket{00}\) and apply a Hadamard gate to each wire:

\[(H\otimes H)\ket{00} = \left(\frac{\ket{0}+\ket{1}}{\sqrt{2}}\right)\otimes\left(\frac{\ket{0}+\ket{1}}{\sqrt{2}}\right) = \frac{1}{2}\bigl(\ket{00}+\ket{01}+\ket{10}+\ket{11}\bigr).\]

Just two single-qubit gates spread equal amplitude \(1/2\) across all four two-bit strings! More generally, applying \(H^{\otimes n}\) to \(n\) qubits in \(\ket{0\cdots 0}\) uses only \(n\) gates in a single layer to create an equal superposition of all \(2^n\) bit strings, each with amplitude \(2^{-n/2}\).

Now attach a target qubit in \(\ket{0}\) and apply \(U_f\) once. By linearity, \(U_f\) acts on all \(2^n\) basis branches simultaneously:

\[U_f\left(\frac{1}{\sqrt{2^n}}\sum_{x\in\{0,1\}^n}\ket{x}\right)\ket{0} = \frac{1}{\sqrt{2^n}}\sum_{x\in\{0,1\}^n}\ket{x}\ket{f(x)}.\]

For a concrete two-bit example, take \(f(x_1,x_2) = x_1\land x_2\) (logical AND, which equals \(1\) only on \(x=11\)). One application of \(U_f\) produces

\[\frac{1}{2}\bigl(\ket{00}\ket{0} + \ket{01}\ket{0} + \ket{10}\ket{0} + \ket{11}\ket{1}\bigr).\]

In a single invocation of \(U_f\), the register now holds a superposition in which every input string \(x\) is paired with its corresponding output \(f(x)\). This capability is called quantum parallelism. It is tempting to think that we have evaluated all \(2^n\) entries of the truth table of \(f\) for the price of one call—but having \(2^n\) values present in the amplitudes of a state vector is very different from being able to read them out.

Suppose we try to read out the parallel evaluation of AND by measuring all three qubits in the computational basis right after \(U_f\). Each of the four terms \(\ket{x}\ket{f(x)}\) has amplitude \(1/2\), so by the measurement postulate we observe a single pair \((x, f(x))\)—either \((00,0)\), \((01,0)\), \((10,0)\), or \((11,1)\)—chosen uniformly at random with probability \(1/4\) each. Worse still, the measurement collapses the state vector onto that single observed pair \((x,f(x))\), erasing the other three branches completely!

If our goal is to learn the entire truth table of \(f\), we would have to re-prepare the state and run \(U_f\) again and again—and because each run samples a random input \(x\) (with replacement), collecting all four distinct inputs takes more runs on average than simply evaluating \(f\) classically on \(00, 01, 10, 11\) in order! For \(n\) input bits, the truth table has \(2^n\) entries, whereas a single measurement of \(n+1\) qubits can return at most \(n+1\) classical bits.

Could we bypass this bottleneck by cloning the superposition \(\tfrac{1}{2}\sum_x \ket{x}\ket{f(x)}\) many times before measuring? No: different functions \(f\) produce non-orthogonal parallel states (for instance, the parallel state for AND has inner product \(3/4\) with the parallel state for the constant-\(0\) function), so the no-cloning theorem forbids any unitary device from copying them.

What if we measure only the target qubit of the AND state? Outcome \(0\) occurs with probability \(3/4\), collapsing the input register to \((\ket{00}+\ket{01}+\ket{10})/\sqrt{3}\), while outcome \(1\) occurs with probability \(1/4\), collapsing the input register to \(\ket{11}\). Measuring the target reveals one output value \(y\) and projects the input register onto a uniform superposition of all inputs satisfying \(f(x)=y\).

Notice a crucial structural feature of the state \(\tfrac{1}{2}\sum_x \ket{x}\ket{f(x)}\): whenever \(f\) is not constant, the input register and the target qubit are entangled! Because some input branches carry \(\ket{0}\) on the target while others carry \(\ket{1}\), the target qubit acts as a path record indicating whether \(f(x)=0\) or \(f(x)=1\).

If a single run cannot read out the full truth table of \(f\), what kind of question can quantum parallelism help us answer? Many computational problems ask not for every value \(f(x)\) individually, but for a single bit or short summary that depends on how the values \(f(x)\) relate to one another across the entire domain—for example, whether \(f\) is constant, whether two halves of the table match, or whether any \(x\) satisfies \(f(x)=1\). Such a collective feature is called a global property of \(f\).

To extract a global property, we need paths from different inputs \(x\) to interfere before we measure. Suppose we try the simplest interference test after applying \(U_f\): apply \(H\otimes H\) to the two input qubits and measure them in the computational basis. Because each two-bit state \(\ket{x}\) has transition amplitude \(\bra{00}(H\otimes H)\ket{x} = +1/2\) into the all-zero input state \(\ket{00}\), the outcome \(00\) gathers contributions from all four input branches.

When \(f(x)=c\) is a constant function, all four branches share the exact same target state \(\ket{c}\), so the parallel state factors as \(\bigl(\tfrac{1}{2}\sum_x \ket{x}\bigr)\otimes\ket{c}\). Applying \(H\otimes H\) to the input register brings all four branches together at the common configuration \(\ket{00}\ket{c}\) with amplitude \(4\times(1/4) = 1\), returning the input readout \(00\) with probability \(1\).

What happens when \(f\) is AND? Now the four contributions to input readout \(00\) do not all land on the same three-qubit configuration! The three inputs \(00, 01, 10\) (where \(f(x)=0\)) arrive at \(\ket{00}\ket{0}\) with combined amplitude \(3\times(1/4) = 3/4\), whereas the input \(11\) (where \(f(11)=1\)) arrives at the distinct configuration \(\ket{00}\ket{1}\) with amplitude \(1/4\). Because \(\ket{00}\ket{0}\) and \(\ket{00}\ket{1}\) have orthogonal target states, their amplitudes cannot add coherently; instead, their probabilities add:

\[p(\text{input}=00) = \left(\frac{3}{4}\right)^2 + \left(\frac{1}{4}\right)^2 = \frac{9}{16} + \frac{1}{16} = \frac{5}{8}.\]

Why did the branches with \(f(x)=0\) and \(f(x)=1\) fail to interfere with each other? Because writing \(f(x)\) into a target qubit initialized in \(\ket{0}\) left a record of \(f(x)\) in the target register—the exact path-information effect we discovered in Section 3.4.4! For different function values \(f(x)\) to interfere coherently on the input register, we must evaluate \(f\) in a way that leaves the target qubit in the same state regardless of \(f(x)\) while transferring the value \(f(x)\) into a relative phase. Discovering how to do that is the subject of Chapter 7.