Quantum Model of Computation

How do state vectors, unitary matrices, and projective measurements come together to form a computation? Every computational task begins with a classical specification of an input and asks for a classical output that satisfies some criterion. The postulates of quantum mechanics divide a quantum run into three distinct stages:

First, we prepare a well-defined initial state vector \(\ket{\psi_{\mathrm{in}}}\) that encodes the input (or starts in a standard reference configuration such as \(\ket{0}\)). Second, we evolve the closed system through a sequence of unitary steps whose combined effect is a unitary transformation \(U\), producing the output state \(\ket{\psi_{\mathrm{out}}} = U\ket{\psi_{\mathrm{in}}}\). Third, we perform a measurement on \(\ket{\psi_{\mathrm{out}}}\) to obtain a single classical outcome \(y\):

\[\ket{\psi_{\mathrm{out}}} = U\ket{\psi_{\mathrm{in}}} \quad\xrightarrow{\ \text{measure}\ }\quad y.\]

Crucially, the user of a quantum computer never receives the output state vector \(\ket{\psi_{\mathrm{out}}}\) itself as a list of complex amplitudes. By the measurement postulate, a single run yields only one classical label \(y\), sampled with probability \(|\braket{y}{\psi_{\mathrm{out}}}|^2\). The output state vector determines the probability distribution over possible outcomes, and a single run draws one sample from that distribution. Consequently, a quantum algorithm succeeds only if its unitary evolution \(U\) concentrates high probability on outcomes \(y\) that answer the task.

Writing the entire evolution as a single matrix \(U\) is a convenient mathematical summary, but it hides how the transformation is actually carried out. A physical machine cannot apply an arbitrary unitary matrix in one step; it must build \(U\) from a sequence of elementary operations, and counting how many elementary operations are required is an essential part of analyzing any algorithm.

Although a general quantum protocol may perform measurements mid-computation and use the classical outcomes to choose subsequent unitary operations, almost every core quantum algorithm can be understood in the cleanest arrangement: unitary evolution from start to finish, followed by a single measurement at the very end.

When the total evolution \(U\) is assembled from a sequence of elementary unitary steps, how do those steps combine? Just as in Boolean circuits, we call an elementary unitary operation that the hardware applies directly a gate, and we call an ordered sequence of gates a quantum program (or circuit).

From Section 4.1.4, we know how successive steps compose: amplitudes multiply along paths and sum across intermediate configurations, which corresponds algebraically to matrix multiplication. If a program applies the gates \(U_1, U_2, \dots, U_T\) in that chronological order to \(\ket{\psi_{\mathrm{in}}}\), the combined unitary transformation is the matrix product

\[U = U_T\cdots U_2 U_1,\]

written from right to left because each gate acts on the column vector to its right: \(\ket{\psi_{\mathrm{out}}} = U_T(\cdots(U_2(U_1\ket{\psi_{\mathrm{in}}}))\cdots)\). Because each individual gate \(U_t\) is unitary and preserves vector lengths, their product \(U\) is also unitary, guaranteeing that the final outcome probabilities always sum to \(1\). Notice that collapsing the product into a single symbol \(U\) is purely notational—the hardware still has to execute all \(T\) gates in sequence.

Why execute a multi-gate sequence if the net effect is just another unitary matrix? Because intermediate gates can alter relative phases that are completely invisible to an immediate computational-basis measurement, yet decisive for how later gates recombine paths. Compare two simple programs starting from \(\ket{0}\): applying \(H\) then \(H\), versus applying \(H\), then \(Z\), then \(H\). After the first \(H\), the state is \((\ket{0}+\ket{1})/\sqrt{2}\), where \(0\) and \(1\) each have probability \(1/2\). Applying \(Z\) flips the sign of \(\ket{1}\) to give \((\ket{0}-\ket{1})/\sqrt{2}\), leaving the intermediate computational-basis probabilities unchanged at \(1/2\) and \(1/2\). Yet multiplying the matrices reveals completely opposite final evolutions:

\[HH = I,\qquad HZH = \frac{1}{2}\begin{pmatrix}1 & 1\\ 1 & -1\end{pmatrix}\begin{pmatrix}1 & 0\\ 0 & -1\end{pmatrix}\begin{pmatrix}1 & 1\\ 1 & -1\end{pmatrix} = \begin{pmatrix}0 & 1\\ 1 & 0\end{pmatrix} = X.\]

Starting from \(\ket{0}\), the sequence \(HH\) returns \(\ket{0}\) with certainty, whereas \(HZH\) returns \(\ket{1}\) with certainty! The relative minus sign introduced by \(Z\) cannot be detected by measuring in the computational basis right after \(Z\), but the final Hadamard gate converts that relative phase into constructive interference on \(\ket{1}\) and destructive cancellation on \(\ket{0}\). An intermediate quantum state is never merely a classical probability distribution over configurations; its relative phases govern the interference of all subsequent steps.

When the final gate finishes and we measure in the computational basis, outcome \(y\) appears with Born-rule probability

\[p(y) = |\braket{y}{\psi_{\mathrm{out}}}|^2 = |\bra{y}U\ket{\psi_{\mathrm{in}}}|^2.\]

What if the algorithm is probabilistic—say, it produces the correct answer with probability \(3/4\) and an incorrect answer with probability \(1/4\)? A single run will fail one time in four. However, by repeating the entire computation from scratch several times and taking the majority vote among the observed outcomes, we can drive the probability of an overall error arbitrarily close to zero. Because measurement collapses the state, each repetition requires preparing a fresh copy of \(\ket{\psi_{\mathrm{in}}}\) and running the full gate sequence \(U\) again. Any probabilistic quantum algorithm must state its per-run success probability so we know how many repetitions are needed.

For a cost comparison to be meaningful, we must also be honest about how the input is supplied. An algorithm must construct \(\ket{\psi_{\mathrm{in}}}\) and choose its gates using only the given problem specification; it cannot smuggle the solution into the state preparation for free.

How, then, do we measure the total cost of a quantum computation? We count the physical and operational resources the machine consumes: the number of qubits (workspace width), the total number of elementary gates, the number of sequential gate layers (depth), the number of independent runs required to achieve the target confidence, and any classical pre- or post-processing. For example, both the three-gate sequence \(HZH\) and the single gate \(X\) implement the exact same unitary matrix \(X\), but the first costs three gates while the second costs one.

Finally, keep in mind that a single-qubit example cannot by itself demonstrate a quantum speedup over classical computing. Computational advantage is a statement about how resource costs scale as the problem size grows—a question that requires multi-qubit registers and careful complexity analysis in the chapters ahead.

Just as we drew diagrams for classical logic circuits in Chapter 2, we can represent a quantum program visually as a quantum circuit so that the sequence of gates and measurements is clear at a glance. For a single qubit, the computation begins in an initial state \(\ket{\psi_{\mathrm{in}}} = a\ket{0} + b\ket{1}\) with \(|a|^2 + |b|^2 = 1\). To encode a classical input bit \(x\in\{0,1\}\), we initialize the qubit in \(\ket{0}\) and apply \(X\) if \(x=1\), producing the basis state \(\ket{x}\).

In a circuit diagram, time flows from left to right—Notice that this is opposite to the right-to-left order of matrices in an algebraic product \(U_T\cdots U_2 U_1\ket{\psi_{\mathrm{in}}}\). A horizontal single line, called a wire, represents the qubit evolving through time, with its initial state written at the left end. Each unitary gate—such as \(H\), \(X\), or \(Z\)—is drawn as a labeled box on the wire, while a bare segment of wire represents the identity step \(I\) (the qubit waiting unchanged). Remember that a wire depicts the history of a qubit over time, not a physical wire carrying an electric current through space.

A box marked with a meter symbol (or the letter \(\mathrm{M}\)) represents a measurement in the computational basis \(\{\ket{0},\ket{1}\}\). To the right of the measurement box, a double line carries the resulting classical bit \(y\). Keeping single wires and double lines visually distinct reminds us of a crucial physical boundary: before \(\mathrm{M}\), the single wire carries a coherent quantum state vector with complex amplitudes; after \(\mathrm{M}\), the double line carries a definite classical bit (\(0\) or \(1\)).

In the simple circuit below, the qubit starts in \(\ket{0}\), passes through a Hadamard box \(H\) to become \((\ket{0}+\ket{1})/\sqrt{2}\), and is then measured, yielding \(y=0\) or \(y=1\) with probability \(1/2\) each. A single box in a diagram can also stand for a larger subroutine built from many elementary gates; the visual width of a box on the page says nothing about its internal gate cost.

Let us trace a complete single-qubit computation that uses quantum interference to compute a deterministic function: logical negation (\(\mathrm{NOT}(x) = 1-x\)). While the single gate \(X\) flips a bit directly, implementing \(\mathrm{NOT}\) via the three-gate sequence \(H\), then \(Z\), then \(H\) lets us watch interference do the work step by step. Suppose the input bit is \(0\), so we start in \(\ket{0}\):

\[\ket{0} \xrightarrow{\ H\ } \frac{\ket{0}+\ket{1}}{\sqrt{2}} \xrightarrow{\ Z\ } \frac{\ket{0}-\ket{1}}{\sqrt{2}} \xrightarrow{\ H\ } \ket{1}.\]

Look at the three stages. The first Hadamard splits \(\ket{0}\) into an equal superposition of \(\ket{0}\) and \(\ket{1}\). Next, the phase-flip gate \(Z\) leaves the amplitude of \(\ket{0}\) at \(+1/\sqrt{2}\) and negates the amplitude of \(\ket{1}\) to \(-1/\sqrt{2}\). Finally, the second Hadamard sends two paths of magnitude \(1/2\) to each output configuration: at \(\ket{0}\), the two path contributions are \(+1/2\) and \(-1/2\), which cancel to \(0\); at \(\ket{1}\), both path contributions are \(+1/2\) (since the negative sign on \(\ket{1}\) multiplies the negative arrow weight \(\bra{1}H\ket{1} = -1/\sqrt{2}\)), reinforcing to \(+1\). Measuring at the end returns \(y=1\) with probability \(1\).

What if the input bit is \(1\)? Starting from \(\ket{1}\) and running the exact same circuit gives

\[\ket{1} \xrightarrow{\ H\ } \frac{\ket{0}-\ket{1}}{\sqrt{2}} \xrightarrow{\ Z\ } \frac{\ket{0}+\ket{1}}{\sqrt{2}} \xrightarrow{\ H\ } \ket{0}.\]

Here \(Z\) turns the relative minus sign back into a plus sign, so the second Hadamard reinforces on \(\ket{0}\) and cancels on \(\ket{1}\), returning \(y=0\) with certainty. Thus the circuit computes \(\mathrm{NOT}(x)\) for both classical inputs, and by linearity it transforms any superposition \(a\ket{0}+b\ket{1}\) into \(b\ket{0}+a\ket{1}\), matching the matrix identity \(HZH = X\).

Notice why both the middle phase gate and the absence of intermediate measurement are indispensable. If we omit \(Z\), the two Hadamards cancel (\(HH=I\)) and the input bit emerges unchanged. If we insert a computational-basis measurement right after the first \(H\) (or right after \(Z\)), the superposition collapses to either \(\ket{0}\) or \(\ket{1}\), and the final \(H\) then produces a random \(50/50\) coin toss instead of the negated bit.

In our \(HZH\) circuit, the gate \(Z\) flipped the relative sign of \(\ket{1}\) by \(-1 = e^{i\pi}\), switching the final measurement outcome from certainty of \(0\) to certainty of \(1\). What happens if we rotate the relative phase by an arbitrary angle \(\phi\) between \(0\) and \(\pi\)? Replace \(Z\) with the general phase gate \(R_\phi = \operatorname{diag}(1, e^{i\phi})\), which leaves \(\ket{0}\) unchanged and multiplies \(\ket{1}\) by the unit-magnitude phase factor \(e^{i\phi}\):

\[R_\phi\ket{0} = \ket{0},\qquad R_\phi\ket{1} = e^{i\phi}\ket{1}.\]

Because \(|e^{i\phi}| = 1\), the columns of \(R_\phi\) are orthonormal for every real angle \(\phi\), so \(R_\phi\) is unitary. Notice that \(\phi = 0\) gives \(R_0 = I\), while \(\phi = \pi\) gives \(R_\pi = Z\). Tracing the circuit \(H R_\phi H\) from input \(\ket{0}\) yields

\[\ket{0} \xrightarrow{\ H\ } \frac{\ket{0}+\ket{1}}{\sqrt{2}} \xrightarrow{\ R_\phi\ } \frac{\ket{0}+e^{i\phi}\ket{1}}{\sqrt{2}} \xrightarrow{\ H\ } \frac{1+e^{i\phi}}{2}\ket{0} + \frac{1-e^{i\phi}}{2}\ket{1}.\]

Taking the squared magnitudes of the two final amplitudes (using \(|1\pm e^{i\phi}|^2 = (1\pm\cos\phi)^2 + \sin^2\phi = 2(1\pm\cos\phi)\), just as in Section 3.4.3) gives the readout probabilities:

\[p(0) = \left|\frac{1+e^{i\phi}}{2}\right|^2 = \frac{1+\cos\phi}{2},\qquad p(1) = \left|\frac{1-e^{i\phi}}{2}\right|^2 = \frac{1-\cos\phi}{2}.\]

As \(\phi\) varies continuously from \(0\) to \(\pi\), the probability of reading out \(0\) glides smoothly from \(p(0)=1\) (at \(\phi=0\), pure constructive interference on \(0\)), through \(p(0)=1/2\) (at \(\phi=\pi/2\), where \(1\) and \(i\) meet at a right angle in the complex plane), down to \(p(0)=0\) (at \(\phi=\pi\), complete cancellation on \(0\) and certainty of \(1\)). Immediately before the second Hadamard gate, the state \((\ket{0}+e^{i\phi}\ket{1})/\sqrt{2}\) has identical computational-basis probabilities \((1/2, 1/2)\) for every value of \(\phi\); the final Hadamard gate is what translates the hidden relative phase \(\phi\) into observable readout probabilities.

We have met \(X\), which swaps \(\ket{0}\) and \(\ket{1}\), and \(Z\), which flips the relative sign of \(\ket{1}\). What happens if we perform both actions in sequence—applying \(Z\) first and \(X\) second? Acting on the computational basis states,

\[XZ\ket{0} = X\ket{0} = \ket{1},\qquad XZ\ket{1} = X(-\ket{1}) = -\ket{0}.\]

The product \(XZ\) swaps the two configurations and attaches opposite signs to them. Notice, however, one algebraic difference: whereas \(X\) and \(Z\) each equal their own adjoint and square to the identity (\(X^2 = I\) and \(Z^2 = I\)), applying \(XZ\) twice gives \((XZ)^2\ket{0} = XZ\ket{1} = -\ket{0}\), so \((XZ)^2 = -I\). Multiplying \(XZ\) by the imaginary unit \(i\) restores self-inversion, since \((iXZ)^2 = i^2(XZ)^2 = (-1)(-I) = I\). We therefore define the operator \(Y\) as

\[Y = iXZ,\qquad Y\ket{0} = i\ket{1},\qquad Y\ket{1} = -i\ket{0}.\]

Together, \(X\), \(Y\), and \(Z\) are called the Pauli operators (or Pauli matrices). Alongside the identity matrix \(I\), their \(2\times 2\) matrices in the computational basis \(\{\ket{0},\ket{1}\}\) are

\[I = \begin{pmatrix}1 & 0\\ 0 & 1\end{pmatrix},\quad X = \begin{pmatrix}0 & 1\\ 1 & 0\end{pmatrix},\quad Y = \begin{pmatrix}0 & -i\\ i & 0\end{pmatrix},\quad Z = \begin{pmatrix}1 & 0\\ 0 & -1\end{pmatrix}.\]

On a general single-qubit state \(\ket{\psi} = a\ket{0} + b\ket{1}\), the three Pauli gates act as a bit flip, a combined bit-and-phase flip, and a phase flip:

\[X(a\ket{0}+b\ket{1}) = b\ket{0}+a\ket{1},\quad Y(a\ket{0}+b\ket{1}) = -ib\ket{0}+ia\ket{1},\quad Z(a\ket{0}+b\ket{1}) = a\ket{0}-b\ket{1}.\]

Each of \(I, X, Y, Z\) is both unitary and equal to its own adjoint (\(P^\dagger = P\), a property called Hermitian), so each is its own inverse: \(X^2 = Y^2 = Z^2 = I\). Does the order matter when we multiply two distinct Pauli matrices? Very much so: we found \(XZ\ket{0} = \ket{1}\), whereas reversing the order gives \(ZX\ket{0} = Z\ket{1} = -\ket{1}\). In fact, any two distinct Pauli operators anticommute—swapping their order introduces a minus sign (\(ZX = -XZ\), \(YX = -XY\), \(ZY = -YZ\))—and multiplying any two distinct Paulis produces the third Pauli times \(\pm i\) (for instance, \(XY = iZ\) and \(YZ = iX\)). When a single-qubit state is multiplied by a product of Pauli gates, that extra factor of \(-1\) or \(\pm i\) is an overall global phase and does not alter any measurement probabilities.

Look at where the nonzero entries of \(I, X, Y, Z\) sit: \(I\) and \(Z\) occupy the main diagonal (with matching and opposite signs), while \(X\) and \(Y\) occupy the off-diagonal positions (with matching real entries and opposite imaginary entries). Can every \(2\times 2\) complex matrix be written as a linear combination of \(I, X, Y,\) and \(Z\)? Take an arbitrary \(2\times 2\) matrix

\[A = \begin{pmatrix}a & b\\ c & d\end{pmatrix}.\]

Because \(\tfrac{1}{2}(I+Z) = \begin{pmatrix}1 & 0\\ 0 & 0\end{pmatrix}\) and \(\tfrac{1}{2}(I-Z) = \begin{pmatrix}0 & 0\\ 0 & 1\end{pmatrix}\), combinations of \(I\) and \(Z\) can produce any diagonal entries \(a\) and \(d\). Similarly, because \(\tfrac{1}{2}(X+iY) = \begin{pmatrix}0 & 1\\ 0 & 0\end{pmatrix}\) and \(\tfrac{1}{2}(X-iY) = \begin{pmatrix}0 & 0\\ 1 & 0\end{pmatrix}\), combinations of \(X\) and \(Y\) can produce any off-diagonal entries \(b\) and \(c\). Combining all four pieces expresses \(A\) uniquely as

\[A = \frac{a+d}{2}I + \frac{b+c}{2}X + \frac{c-b}{2i}Y + \frac{a-d}{2}Z.\]

We can verify each entry directly: the top-left entry is \(\tfrac{a+d}{2} + \tfrac{a-d}{2} = a\), the bottom-right is \(\tfrac{a+d}{2} - \tfrac{a-d}{2} = d\), the top-right is \(\tfrac{b+c}{2} - i\tfrac{c-b}{2i} = b\), and the bottom-left is \(\tfrac{b+c}{2} + i\tfrac{c-b}{2i} = c\). Thus the four matrices \(\{I, X, Y, Z\}\) form a complete basis for single-qubit operators—every linear operator on a single qubit (whether unitary or not) is a weighted sum of these four matrices. For example, our Hadamard gate and phase gate expand as

\[H = \frac{X+Z}{\sqrt{2}},\qquad R_\phi = \frac{1+e^{i\phi}}{2}I + \frac{1-e^{i\phi}}{2}Z.\]

Pause to distinguish two very different ways of combining matrices. Writing \(H = (X+Z)/\sqrt{2}\) expresses \(H\) as a sum of Pauli matrices, whereas a quantum circuit combines gates in sequence by multiplying their matrices. A circuit containing only the gates \(X, Y, Z\) can only form products like \(ZX = iY\), which map \(\ket{0}\) to \(\pm\ket{0}\), \(\pm i\ket{0}\), \(\pm\ket{1}\), or \(\pm i\ket{1}\)—a sequence of Pauli gates starting from \(\ket{0}\) can never create a superposition like \(H\ket{0} = (\ket{0}+\ket{1})/\sqrt{2}\)! Nor is every linear combination of Pauli matrices a valid quantum gate: for instance, \(I+Z = \operatorname{diag}(2,0)\) doubles \(\ket{0}\) and annihilates \(\ket{1}\), which is not unitary.

When does a linear combination of \(I\) and a Pauli matrix give a valid unitary gate? For any real angle \(\theta\), define the continuous rotation operator

\[R_x(\theta) = \cos\frac{\theta}{2}\,I - i\sin\frac{\theta}{2}\,X = \begin{pmatrix}\cos(\theta/2) & -i\sin(\theta/2)\\ -i\sin(\theta/2) & \cos(\theta/2)\end{pmatrix}.\]

Taking its adjoint replaces \(-i\) with \(+i\) (since \(I^\dagger = I\) and \(X^\dagger = X\)), and multiplying \(R_x(\theta)^\dagger R_x(\theta)\) cancels the cross terms \(\pm i\cos(\theta/2)\sin(\theta/2)X\) while using \(X^2 = I\) to leave \(\bigl(\cos^2(\theta/2) + \sin^2(\theta/2)\bigr)I = I\). Thus \(R_x(\theta)\) is unitary for every \(\theta\): acting on \(\ket{0}\), it produces \(\cos(\theta/2)\ket{0} - i\sin(\theta/2)\ket{1}\), rotating the state continuously between \(\ket{0}\) (at \(\theta=0\)) and \(-i\ket{1}\) (at \(\theta=\pi\), where \(R_x(\pi) = -iX\)). Having a continuous family of gates \(R_x(\theta)\) is a much stronger hardware capability than having only the single fixed gate \(X\).

In short, the four Pauli matrices \(\{I, X, Y, Z\}\) provide a universal coordinate system for describing any single-qubit operator on paper; constructing arbitrary unitary evolutions out of a fixed set of hardware gates is a separate engineering and algorithmic question that we will tackle in Chapter 8.

Further reading: IBM Quantum’s guide to the Pauli basis.