Appendices

How much memory does a computation need? Start with the least: a finite automaton, which reads its input once while keeping one of finitely many control states. Two states suffice to track parity, whether the number of ones read so far is even or odd: reading a one swaps the states, and reading a zero leaves them unchanged.

Can a finite automaton check that a string consists of some number of \(a\)’s followed by the same number of \(b\)’s, the language \(\{a^nb^n:n\geq0\}\)? No. A fixed automaton has finitely many states, so two different long prefixes \(a^i\) and \(a^j\) must reach the same state. Appending \(b^i\) then forces the same decision on \(a^ib^i\), which is in the language, and on \(a^jb^i\), which is not. This state-collision argument proves the limitation.

What extra memory is enough? A stack, which can hold arbitrarily many pending symbols: push once for each \(a\), then pop once for each \(b\). Reject an \(a\) after the first \(b\), or a \(b\) with nothing left to pop. Accept when the input and stack run out together. A pushdown automaton formalizes this memory. A linear-bounded automaton has a writable tape no longer than a constant multiple of the input, and a Turing machine removes even that bound.

Do these models form a sequence of ever better machines? Not in that sense. More memory changes which configurations are available, not what a single step means. The models describe different classes of languages; they are not successive generations of hardware.

Instead of recognizing strings, can we describe a set of strings by how its members are produced? A grammar does this. It specifies a start symbol, terminal symbols, nonterminal symbols, and replacement rules. The rules \(S\to aSb\) and \(S\to\epsilon\), where \(\epsilon\) is the empty string, generate exactly the strings of matching \(a\)’s and \(b\)’s: applying the first rule twice and then the second gives \(aabb\).

How do grammars relate to machines? Generation asks what can be produced; recognition asks whether a given string belongs to the generated set. Regular grammars correspond to finite automata, context-free grammars to pushdown automata, context-sensitive grammars to linear-bounded automata, and unrestricted grammars to the languages a Turing machine recognizes, with the usual conventions about the empty string.

Can computation be described without any machine at all? Lambda calculus uses only functions, application, and substitution. The reduction \((\lambda x.t)u\to t[x:=u]\) replaces the free occurrences of \(x\) in \(t\) by \(u\), renaming bound variables where necessary to avoid capture; for example, \((\lambda x.x)u\to u\).

How can functions alone represent numbers? A Church numeral \(n\) is the function that applies a given function \(n\) times to a given starting value, so three is \(\lambda f.\lambda x.f(f(f(x)))\). Functions alone can encode data and iteration. The functions computable in lambda calculus are exactly the Turing-computable ones. That equivalence between formal models supports the broader Church–Turing thesis; it does not prove it.

This appendix collects, for reference, the linear algebra used in the book. Where an identity is not derived in the main text, it is derived here.

How are complex vectors compared? Through the inner product \(\braket uv=u^\dagger v\), where \(u^\dagger=(u^*)^T\) is the conjugate transpose. The norm is \(\sqrt{u^\dagger u}\). An orthonormal basis matrix \(B\) satisfies \(B^\dagger B=I\), and \(B^\dagger\) converts old coordinates to new ones.

In which order do matrices act? From right to left on column vectors, and the adjoint reverses the order of a product: \((AB)^\dagger=B^\dagger A^\dagger\). Three properties of a matrix are easily confused. A unitary preserves overlaps; a Hermitian matrix equals its adjoint; an orthogonal projector satisfies \(P^2=P=P^\dagger\).

How do tensor products behave? \((A\otimes B)(u\otimes v)=Au\otimes Bv\) and \(\braket{u\otimes v}{x\otimes y}=\braket ux\braket vy\). In the binary ordering used in this book, the leftmost qubit is the most significant label.

How large can a matrix make a vector? The operator norm \(\|A\|=\max_{\|v\|=1}\|Av\|\) answers this. It gives uniform error bounds, because \(\|(U-V)v\|\leq\|U-V\|\) for every unit vector \(v\).

What if we know only that a system was prepared in one of several states, \(\ket{\psi_r}\) with probability \(q_r\)? In general, no single state vector describes that preparation. The density matrix

\[\rho=\sum_rq_r\ket{\psi_r}\bra{\psi_r}\]

does. Its trace—the sum of its diagonal entries—is one. It is positive semidefinite, meaning \(\bra v\rho\ket v\geq0\) for every vector \(\ket v\); this ensures nonnegative measurement probabilities. A pure state has \(\rho=\ket\psi\bra\psi\). Different ensembles can give the same density matrix, and then they give the same predictions for every measurement. The measurement rule becomes \(p(j)=\operatorname{tr}(P_j\rho)\), and unitary evolution sends \(\rho\) to \(U\rho U^\dagger\).

What is the state of one part of an entangled pair? Its reduced state \(\rho_A=\operatorname{tr}_B\rho_{AB}\), computed by summing over the unobserved basis label: \((\rho_A)_{a,a^\prime}=\sum_b(\rho_{AB})_{ab,a^\prime b}\). The same \(b\) appears in the row and column because we ignore which outcome occurred in \(B\). For either half of a Bell state, it is \(I/2\).

Can an operation on \(B\) change \(\rho_A\)? Not when its outcome is ignored. A trace-preserving operation on \(B\), with operators \(M_r\) satisfying \(\sum_rM_r^\dagger M_r=I\), leaves \(\rho_A\) unchanged; inserting the sum into the partial trace shows this. Conditioning on the outcome \(r\) changes the description only for someone who knows \(r\).

Are projective measurements the only ones? No. A general measurement has positive operators \(E_j\), called effects, that sum to the identity, with probabilities \(p(j)=\operatorname{tr}(E_j\rho)\). The effects fix the probabilities but not the state after the measurement; measurement operators supply that further information.

Can we sometimes identify either of two nonorthogonal states with certainty, provided we allow an inconclusive result? A measurement with three outcomes makes this possible. Suppose the state is either \(\ket0\) or \(\ket+\). With \(c=1/(1+1/\sqrt2)\), take

\[E_0=c\ket-\bra-,\qquad E_+=c\ket1\bra1,\qquad E_?=I-E_0-E_+.\]

The outcome \(0\) is impossible for \(\ket+\), the outcome \(+\) is impossible for \(\ket0\), and the outcome \(?\) is inconclusive. \(E_?\) is positive because the largest eigenvalue of \(\ket-\bra-+\ket1\bra1\) is \(1+1/\sqrt2\). Whenever this measurement gives an answer, the answer is certain; the price is that it sometimes declines to answer.

Why must a search algorithm make many queries? In the Boolean query model, the hidden input is a string \(z\in\{0,1\}^N\), and a query transforms \(\ket{i,b}\) into \(\ket{i,b\oplus z_i}\). How does each query change the amplitudes? Every new amplitude is a combination of previous amplitudes multiplied by \(z_i\) or by \(1-z_i\).

The amplitudes therefore start as constants and gain degree at most one per query. Operations that do not depend on the input only form linear combinations, which do not raise the degree. By induction, after \(T\) queries every amplitude is a polynomial of degree at most \(T\) in the input bits.

What about the probability of accepting? It is a sum of squared magnitudes of amplitudes, so its degree is at most \(2T\). On Boolean inputs, any power \(z_i^k\) with \(k\geq1\) equals \(z_i\), so the polynomial can be taken to be multilinear.

The approximate degree of a Boolean function is the least degree of a real polynomial that approximates it, within a fixed error below one half, on every Boolean input. An algorithm with bounded error yields such a polynomial of degree at most \(2T\), so its number of queries is at least half the approximate degree.

Proving that OR has approximate degree of order \(\sqrt N\) needs an argument from approximation theory, beyond this short derivation. Together with the polynomial representation, that theorem gives the lower bound for detecting a marked item. Neither follows from the observation that known algorithms are slow.