Chapter 04

Gates, circuits, and universality

Start with two qubits, both in state 0. Apply a gate to the first, then let it control a flip of the second. The result is an entangled pair. Reverse the order of those same gates and the qubits remain independent. What changed, and how can we follow it through the circuit?

Before you start: Matrix multiplication; two-qubit basis states and tensor products (Chapter 1). Reduced states (Chapter 3) appear in one remark and are not needed for the calculations. Notation guide.

One circuit, step by step

A circuit diagram draws each qubit as a horizontal wire and each gate as a box or symbol on it, with time running from left to right. Here there are two qubits, both starting in $|0\rangle$. Qubit 1 is the top wire, and it is the first symbol in every basis label: $|10\rangle$ means qubit 1 is 1 and qubit 2 is 0. The basis order is $|00\rangle,|01\rangle,|10\rangle,|11\rangle$.

The first gate is the Hadamard $H$ on qubit 1, which sends $|0\rangle$ to $(|0\rangle+|1\rangle)/\sqrt2$. The second is a controlled-NOT: qubit 1 is the control (the dot) and qubit 2 the target (the circled plus). It flips the target in exactly those basis terms where the control is 1. The figure follows the four amplitudes through the two steps, and the sections below derive each step.

Read a circuit as a matrix product

A closed system evolves by a unitary $U$, satisfying $U^\dagger U=I$. This preserves inner products and normalisation. If gate $A$ acts first and gate $B$ second, the output is $BA|\psi\rangle$: the rightmost matrix acts first. The inverse operation is $U^\dagger$. A measurement with a discarded outcome generally has no inverse, so it must be treated separately.

For the first step of our circuit we need the Hadamard gate:

$$H=\frac1{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix}.$$

Multiplying by $|0\rangle=(1,0)^T$ selects its first column: $H|0\rangle=(|0\rangle+|1\rangle)/\sqrt2=|+\rangle$. Multiplying by $|1\rangle$ selects the second: $H|1\rangle=|-\rangle$. The columns tell us what the gate does to the basis states; linearity then tells us what it does to every superposition.

On two qubits, $H\otimes I$ means apply $H$ to the first and leave the second alone. On $|00\rangle$ it therefore gives $|+\rangle|0\rangle=(|00\rangle+|10\rangle)/\sqrt2$. The second qubit is still definitely 0. This is the middle row of amplitudes in the figure, before the controlled gate acts. Applying $H$ twice restores the original state: $H^2=I$.

Where noncommutativity enters

Two operators commute when their products agree in either order: $AB=BA$. Their commutator is $[A,B]=AB-BA$, so commuting means $[A,B]=0$. This definition concerns the operators on all inputs; two different products can still happen to agree on one particular state.

The circuit above already shows this. Applied in the other order, the same two gates give $(H\otimes I)\operatorname{CNOT}|00\rangle=|+\rangle|0\rangle$, because the controlled-NOT acts first on $|00\rangle$, where its control is 0, and does nothing. The order decides whether the output is entangled. A one-qubit example is just as sharp. Apply $H$ then $Z$ to $|0\rangle$: $ZH|0\rangle=|-\rangle$. Reverse the order: $HZ|0\rangle=|+\rangle$. The two outputs can be perfectly distinguished in the $X$ basis. Gate order is physically consequential. A useful identity is

$$HZH=X,\qquad HXH=Z.$$

For example, $HZH|0\rangle=H|-\rangle=|1\rangle$, and $HZH|1\rangle=H|+\rangle=|0\rangle$. Agreement on a basis establishes agreement on every superposition by linearity. Conjugating by $H$ changes a phase flip into a bit flip; this will let us reuse the bit-flip code for phase errors (Chapter 14).

Controlled operations on a superposition

With the first qubit as control and the second as target, controlled-NOT is

$$\operatorname{CNOT}=|0\rangle\langle0|\otimes I+|1\rangle\langle1|\otimes X=\begin{pmatrix}1&0&0&0\\0&1&0&0\\0&0&0&1\\0&0&1&0\end{pmatrix}.$$

It maps $|a,b\rangle$ to $|a,b\oplus a\rangle$, where $\oplus$ is addition modulo two. The word “control” does not mean that the control is measured. Apply the rule to each basis term and keep the amplitudes:

$$|00\rangle\xrightarrow{H\otimes I}\frac{|00\rangle+|10\rangle}{\sqrt2}\xrightarrow{\operatorname{CNOT}}\frac{|00\rangle+|11\rangle}{\sqrt2}.$$

This is step ③ of the figure: the Bell pair from Chapter 3. The gate moved the amplitude on $|10\rangle$ to $|11\rangle$, while leaving the amplitude on $|00\rangle$ alone. Both terms remain in the state; the control was never read and no outcome was selected.

Why can this state no longer be written as two independent qubits? Suppose it were $(a|0\rangle+b|1\rangle)(c|0\rangle+d|1\rangle)$. Its $|00\rangle$ and $|11\rangle$ amplitudes would be $ac$ and $bd$. Both must be nonzero, so all four factors must be nonzero. But then the unwanted amplitudes $ad$ on $|01\rangle$ and $bc$ on $|10\rangle$ would also be nonzero. The proposed product cannot describe the Bell pair.

A gate on each qubit separately keeps a product in product form: $(U\otimes V)(|a\rangle|b\rangle)=(U|a\rangle)(V|b\rangle)$. Creating this entanglement from the initial product therefore requires a joint gate. It does not follow that every use of CNOT entangles: Problem 1 gives an input it leaves unchanged. Each qubit of the Bell pair alone has state $I/2$, as Chapter 3 found.

We can also undo the circuit. CNOT sends the Bell pair back to $|+\rangle|0\rangle$, and $H\otimes I$ then returns it to $|00\rangle$. Undo the last step first. Here both gates are their own inverses, but the order still has to reverse.

More generally $\operatorname{C}U=|0\rangle\langle0|\otimes I+|1\rangle\langle1|\otimes U$. A subtlety follows: the global phase of a standalone $U$ becomes a relative phase between control branches in $\operatorname{C}U$. Controlled-$e^{i\gamma}U$ cannot generally be substituted for controlled-$U$ without a compensating phase on the control.

Changing a phase without changing the populations

The Hadamard mixes the two input amplitudes. Other useful gates change their relative phase. Chapter 1 showed why that matters: a change invisible to the 0/1 detector can become visible when amplitudes are combined in a later measurement.

Two such gates are

$$S=\begin{pmatrix}1&0\\0&i\end{pmatrix},\qquad T=\begin{pmatrix}1&0\\0&e^{i\pi/4}\end{pmatrix}.$$

For example, $S$ takes $|+\rangle$ to $(|0\rangle+i|1\rangle)/\sqrt2$. The two amplitude magnitudes stay the same, so the computational-basis probabilities remain one half each. Their relative phase changes by a quarter turn, moving the Bloch vector from $+x$ to $+y$. Applying $T$ twice gives $S$, and applying $S$ twice gives $Z$. We will use these gates when discussing a fixed set of circuit building blocks below.

Reversible evaluation of a function

The controlled-NOT kept the control and changed a target. The same arrangement lets us evaluate a classical function while retaining enough information to undo the computation.

A classical function $f$ may send several inputs to the same output and therefore cannot directly define a unitary $|x\rangle\mapsto|f(x)\rangle$. Preserve the input and use a target register instead:

$$U_f|x,y\rangle=|x,y\oplus f(x)\rangle.$$

Applying this twice returns $|x,y\rangle$, since $f(x)\oplus f(x)=0$. Thus it permutes basis vectors and defines a unitary. If a physical implementation uses work qubits, they must be uncomputed when their residual correlations would affect later interference. Such a reversible function box $U_f$ is called an oracle when an algorithm counts only how many times it is used; calling a box an oracle does not establish that it is inexpensive to implement.

What “universal” does and does not guarantee

The circuit above used one $H$ and one CNOT. Any unitary operation on qubits can be built from a suitable collection of gates: all one-qubit unitaries together with CNOT can exactly implement any finite-dimensional qubit unitary. This is a decomposition theorem, stated here; it does not say the decomposition is short. A general unitary on $n$ qubits has $4^n$ real parameters, so most such operations require exponentially many elementary gates. Universality does not imply efficient implementation.

A fixed finite alphabet, such as $H,T,$ and CNOT, is instead approximately universal, with physically irrelevant overall phase disregarded. Finite words form a countable set and cannot exactly cover the continuum of target operations. Approximate universality means that for every target and every $\epsilon>0$, some word $V$ satisfies $\min_\gamma\|U-e^{i\gamma}V\|<\epsilon$, using operator norm. Here the norm measures the largest length of the output-vector error over normalised inputs; minimising over $\gamma$ ignores a common phase. A small bound therefore controls the error for every input, rather than just the state used in one test.

There are two distinct construction problems here. In the first, arbitrary one-qubit matrices are available as elementary operations, so each can carry continuously chosen parameters. In the second, the available matrices are fixed in advance and only their sequence can vary. A continuously variable rotation cannot simply be counted as one fixed-alphabet gate; it must itself be synthesised.

Why finitely many gates can still approximate a continuum

Countability alone does not rule out arbitrarily good approximation. Decimal fractions have finite descriptions and form a countable set, yet they approximate any real number as closely as desired. For gates, the analogous question is whether available words come arbitrarily close to every target matrix. Some alphabets fail: powers of $T$ alone give only eight distinct matrices because $T^8=I$. The claim that $H,T,$ and CNOT suffice requires a separate density theorem, not merely the observation that there are infinitely many words.

Errors also accumulate. If each of $L$ unitary gates is approximated with operator-norm error at most $\delta$, the whole circuit is off by at most $L\delta$. Choosing a synthesis tolerance therefore depends on circuit length, not just on one gate.

The error bound, by a telescoping sum

Expand the difference of the two circuit products by replacing one factor at a time:

$$U_L\cdots U_1-V_L\cdots V_1=\sum_{k=1}^{L}U_L\cdots U_{k+1}\,(U_k-V_k)\,V_{k-1}\cdots V_1,$$

a telescoping sum in which consecutive terms cancel except the first and last. Each term has norm at most $\delta$, because multiplying by unitaries does not change the operator norm. The triangle inequality gives a total error at most $L\delta$.

Where this leaves us

Each gate is a matrix, and the circuit's output is their product, rightmost first. The Hadamard put qubit 1 into two terms. The controlled-NOT then changed something no one-qubit gate can: it correlated the two qubits, turning the product $|+\rangle|0\rangle$ into the entangled $(|00\rangle+|11\rangle)/\sqrt2$. In the other order the same gates leave a product. A controlled operation can also turn a phase on the target into a relative phase between the control's branches, as Problem 2 shows. Universality says such pieces suffice for any operation, not that the construction is short.

A gate here is a matrix that someone applies. A physical qubit has no matrices, only a Hamiltonian and whatever fields are applied to it for a while. The next chapter derives a one-qubit gate from a pulse, including how long the pulse must last.

Problems

1. What does CNOT do to $|+\rangle|+\rangle$? Does this gate always entangle?

Worked answer

The input expands as $|++\rangle=(|00\rangle+|01\rangle+|10\rangle+|11\rangle)/2$. Apply the basis rule $|a,b\rangle\mapsto|a,b\oplus a\rangle$ to each term:

$$\operatorname{CNOT}|++\rangle=(|00\rangle+|01\rangle+|11\rangle+|10\rangle)/2=|++\rangle.$$

The exchanged terms have equal amplitudes, so the joint vector is unchanged and remains a product. CNOT can create entanglement, but its effect depends on the input state.

The tempting wrong turn is to expect entanglement whenever the control is in a superposition. Here it is, but the target $|+\rangle$ is unchanged by $X$, so flipping it in one branch and not the other leaves the two branches with the same target state.

2. Compare controlled-$I$ and controlled-$(-I)$ on $|+0\rangle$.

Worked answer

Expand $|+0\rangle=(|00\rangle+|10\rangle)/\sqrt2$. Controlled-$I$ applies identity in both control branches and changes neither term. Controlled-$(-I)$ leaves the zero-control branch alone and negates the one-control branch:

$$\operatorname{C}(-I)|+0\rangle=(|00\rangle-|10\rangle)/\sqrt2=|-\rangle|0\rangle.$$

For the first circuit an $X$ measurement on the control returns $+1$ certainly; for the second it returns $-1$ certainly. The target’s phase has become a relative phase between control branches, making the two controlled operations distinguishable.

References and further reading

Nielsen & Chuang, §1.3 (gates and circuits), §4.3 (controlled operations), and §4.5 (universality and synthesis costs). The universality theorems are cited, not proved here.