Quantum Computing · Chapter 05

Quantum Model of Computation

How do the physical postulates of quantum mechanics become a programmable computation?

Mithilesh Kumar

→ or Space to advance · N for notes · F for fullscreen

5.1

Quantum Model of Computation

The postulates become a procedure: prepare an input, evolve it, measure, and count what the run costs.

Input, evolution, and output

A task gives an input and specifies which outputs count as correct. A quantum procedure makes three choices:

an initial state \(\ket{\psi_{\mathrm{in}}}\) that encodes the input;
unitary steps, which together form one unitary \(U\);
a measurement, which returns a classical result \(y\).

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

The output state itself cannot be read. A run returns one label, with probability equal to the squared magnitude of its amplitude. The output state fixes how likely each answer is, so a computation works only if it makes the correct answer likely.

Naming the whole evolution \(U\) says nothing about how a machine carries it out. Building \(U\) from available operations, and counting their cost, is part of the algorithm.

Procedures may also measure partway and choose later steps from the result; we start with a single final measurement.

Composition and interference

A gate is an operation a machine applies directly; a program is an ordered list of gates \(U_1,\ldots,U_T\). By the sum and product rules,

\[U=U_T\cdots U_2U_1 ,\]

with the later gate on the left. Each gate preserves length, so \(U\) does. Writing the product as one symbol does not remove the cost of \(T\) gates.

Why a sequence? Compare two programs from \(\ket0\): \(H,H\) and \(H,Z,H\). After the first \(H\) both outcomes have probability \(\tfrac12\), and \(Z\), which only flips the sign of the \(\ket1\) amplitude, leaves them at \(\tfrac12\).

\[HH=I,\]

\[HZH=\tfrac12\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 .\]

The first program returns \(\ket0\), the second \(\ket1\). A sign invisible to any measurement in the middle decided the answer.

Lesson

An intermediate state is not an answer: its relative phases decide how later steps combine its paths.

Readout and computational cost

A final computational-basis measurement returns \(y\) with probability

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

If the correct answer has probability \(\tfrac34\), one run is wrong a quarter of the time. Repeating and taking the majority helps, but each repetition needs a fresh input and the full work again. A probabilistic algorithm must state its success probability on the inputs it promises to handle.

The input may not carry the answer for free: a procedure must say what information about the task it is given.

Count qubits, gates, layers of gates (depth), repetitions, and the classical work to prepare inputs and interpret outputs.
\(H,Z,H\) and the single gate \(X\) compute the same NOT, with three gates and one.
A speedup is a claim about tasks of growing size under the same input-access rules; a one-qubit example cannot show one.

5.2

Single-Qubit Computation

A notation for programs, a complete computation decided by a relative sign, and the continuous dependence of the answer on phase.

Circuit notation

One qubit starts in \(\ket{\psi_{\mathrm{in}}}=a\ket0+b\ket1\), \(|a|^2+|b|^2=1\). For an input bit \(x\), prepare \(\ket x\): initialize \(\ket0\) and apply \(X\) if \(x=1\).

A circuit is read from left to right.
A horizontal wire follows the qubit through time; its initial state is written at the left.
A box labelled H, X or Z applies that gate; bare wire leaves the state unchanged.
A box labelled M measures in the computational basis; the double line after it carries one classical bit.

In the example, H sends \(\ket0\) to \((\ket0+\ket1)/\sqrt2\) and M returns either bit with probability \(\tfrac12\).

A box may also stand for a composite operation built from many gates; its size on the page says nothing about its cost.

A complete one-qubit computation

Task: reverse an input bit. \(X\) does it in one step; follow \(H,Z,H\) instead:

\[\ket0\xrightarrow{H}\tfrac{\ket0+\ket1}{\sqrt2}\xrightarrow{Z}\tfrac{\ket0-\ket1}{\sqrt2}\xrightarrow{H}\ket1 ,\]

\[\ket1\xrightarrow{H}\tfrac{\ket0-\ket1}{\sqrt2}\xrightarrow{Z}\tfrac{\ket0+\ket1}{\sqrt2}\xrightarrow{H}\ket0 .\]

In the last step from input 0, the two paths to 0 contribute \(\tfrac12\) and \(-\tfrac12\) and cancel; the paths to 1 add to 1. By linearity, \(a\ket0+b\ket1\mapsto b\ket0+a\ket1\): this is \(HZH=X\).

What is essential? Without \(Z\), the two \(H\) gates cancel and the input returns. With a measurement after the first \(H\), the state becomes \(\ket0\) or \(\ket1\) and both answers become equally likely.

Phase and output probabilities

Replace \(Z\) by the phase gate \(R_\phi\):

\[R_\phi\ket0=\ket0,\qquad R_\phi\ket1=e^{i\phi}\ket1 .\]

It preserves length; \(R_0=I\) and \(R_\pi=Z\). For input 0:

\[\begin{aligned}\ket0&\xrightarrow{H}\tfrac{\ket0+\ket1}{\sqrt2}\xrightarrow{R_\phi}\tfrac{\ket0+e^{i\phi}\ket1}{\sqrt2}\\&\xrightarrow{H}\tfrac{1+e^{i\phi}}2\ket0+\tfrac{1-e^{i\phi}}2\ket1 .\end{aligned}\]

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

\(\phi\)	\(p(0)\)	\(p(1)\)
\(0\)	1	0
\(\pi/2\)	\(1/2\)	\(1/2\)
\(\pi\)	0	1

Just before the final \(H\), both outcomes have probability \(\tfrac12\) for every \(\phi\). The last gate turns a relative phase that no measurement could see into the probabilities of the answer.

Check \(p(0)\): \(|1+e^{i\phi}|^2=(1+\cos\phi)^2+\sin^2\phi=2+2\cos\phi\).

5.3

Pauli Operators

A fixed family of four matrices that describes every single-qubit operator, and the difference between describing an operation and building it.

The Pauli operators

\(X\) exchanges the configurations; \(Z\) flips their relative sign. Doing both: \(XZ\ket0=\ket1\), \(XZ\ket1=-\ket0\). But \((XZ)^2=-I\), whereas \(X\) and \(Z\) undo themselves. Multiplying by \(i\) repairs this, so define

\[Y=iXZ,\qquad Y\ket0=i\ket1,\qquad Y\ket1=-i\ket0 .\]

On a general state:

\[X(a,b)=(b,a),\quad Y(a,b)=(-ib,ia),\quad Z(a,b)=(a,-b).\]

Each preserves length and \(X^2=Y^2=Z^2=I\). Order matters: \(ZX=-XZ\). A product of Paulis is again \(I,X,Y\) or \(Z\) times a phase.

\[I=\begin{pmatrix}1&0\\0&1\end{pmatrix},\quad X=\begin{pmatrix}0&1\\1&0\end{pmatrix},\]

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

Each column lists the amplitudes produced from one input configuration.

Here \((a,b)\) abbreviates \(a\ket0+b\ket1\).

The Pauli basis for operators

Can every \(2\times2\) matrix be written with \(I,X,Y,Z\)? \(I\) and \(Z\) supply the diagonal (equal and opposite signs); \(X\) and \(Y\) supply the off-diagonal (equal and opposite imaginary factors). Matching entries:

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

Check the off-diagonal entries: upper right \(\tfrac{b+c}2-\tfrac{c-b}2=b\), lower left \(\tfrac{b+c}2+\tfrac{c-b}2=c\). The coefficients are unique, so \(I,X,Y,Z\) form a basis for single-qubit operators (any linear maps, not only gates). For example

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

Describing an operator is not building it

The expansion adds matrices; a circuit multiplies them. X followed by Z performs \(ZX\), not \((X+Z)/\sqrt2\), and choosing X or Z at random does not produce the sum either.

From \(\ket0\), any sequence of Pauli gates leaves a single basis state up to phase, so it never reaches \(H\ket0=(\ket0+\ket1)/\sqrt2\).
Not every combination is a gate: \(I+Z\) sends \(\ket0\mapsto2\ket0\) and \(\ket1\mapsto0\), which is not unitary.

A continuous family from one Pauli:

\[R_x(\theta)=\cos\tfrac\theta2\,I-i\sin\tfrac\theta2\,X .\]

It is unitary: in \(R_x(\theta)^\dagger R_x(\theta)\) the cross terms cancel and \(X^2=I\) leaves \(\bigl(\cos^2\tfrac\theta2+\sin^2\tfrac\theta2\bigr)I=I\). It sends \(\ket0\) to \(\cos\tfrac\theta2\ket0-i\sin\tfrac\theta2\ket1\). A gate with an adjustable angle is a different capability from the fixed gate \(X\).

Summary

A quantum computation prepares \(\ket{\psi_{\mathrm{in}}}\), applies \(U=U_T\cdots U_1\), and measures; a run returns one outcome with probability \(|\bra yU\ket{\psi_{\mathrm{in}}}|^2\).
Cost counts qubits, gates, depth, repetitions and classical processing; speedups are claims about growing input sizes.
In \(H,R_\phi,H\) a relative phase invisible in the middle sets the output: \(p(0)=(1+\cos\phi)/2\).
\(I,X,Y,Z\) form a basis for single-qubit operators, but a circuit multiplies gates; describing an operator is not building it.