Quantum Algorithmic Thinking

Imagine a sealed device with one input switch and one output lamp. Set the switch to \(x\in\{0,1\}\) and the lamp shows a bit \(f(x)\). The wiring inside is fixed but hidden. Your job is not to reconstruct the device. Your job is to report one property of it: do the two switch positions give the same lamp?

Write the required answer as

\[d=f(0)\oplus f(1),\]

where \(\oplus\) is addition modulo two. The answer \(d=0\) means the outputs agree, and \(d=1\) means they differ. There are exactly four possible devices, and we can list them all.

Look at what this table asks for. Two of the four functions share each answer. The algorithm must separate the rows into two groups, not identify the row. That is less than the full truth table. Can we learn less more cheaply?

A classical procedure that is allowed to look at the lamp can certainly compare both outputs. Can it do so with one look? Suppose it sets the switch to \(0\) and sees \(f(0)=0\). Rows one and two are both still possible, and they have different answers. The same happens whichever input is tried first and whichever value appears. One inspection cannot determine \(d\) with certainty, because the unseen value changes the answer.

Three pieces of the problem statement are now explicit, and every later chapter will ask for the same three. The input family is the set of instances the algorithm must handle: here, all four functions. A promise is a restriction on that family which the algorithm may assume without checking. Deutsch’s problem needs none, since every one-bit function either agrees or disagrees with itself across inputs. For an \(n\)-bit function the analogous promise “constant or balanced” is a genuine restriction, and an algorithm that relies on it may give meaningless output on functions that break it. The success criterion says what counts as a correct run. Here we demand the right \(d\) with certainty on every row. Later problems allow error probability, say at most \(1/3\) per instance. That allowance must be granted to classical and quantum methods alike before their costs are compared.

Deutsch’s task asks for one bit. What changes when a task asks for something else? Take one Boolean function \(f\) on \(N\) inputs, and call an input marked when \(f(x)=1\). We can ask four different questions about the same \(f\).

First, is there any marked input? The answer is yes or no. A task whose answer is one bit is a decision problem.

Second, which input is marked? Now the answer is a witness: some \(x\) with \(f(x)=1\), or a report that none exists. This is a search problem. A witness can usually be checked with one more evaluation of \(f\), so a search algorithm that sometimes fails can still recognize its successes.

Third, how many inputs are marked? Let \(p\) be the fraction of marked inputs. An exact count may be expensive, so we ask instead for a number \(\tilde p\) with \(|\tilde p-p|\le\epsilon\), allowing failure with probability at most \(\delta\). This is an estimation problem. Its statement needs two numbers, the tolerance \(\epsilon\) and the failure probability \(\delta\). No single evaluation of \(f\) can check its answer.

Fourth, can we have a typical marked input? A sampling problem asks for a random output whose distribution is close to a target \(q(x)\), for example the uniform distribution over marked inputs. No single output is right or wrong. Only the distribution over many runs can be judged.

Does an algorithm for one of these questions answer the others? Not cheaply. Estimating \(p\) to within \(0.01\) does not produce any marked input. Producing one marked input says almost nothing about how many there are. So the kind of question must be fixed before two algorithms can be compared.

Quantum algorithms add a fifth kind of output: a quantum state handed to a later computation. A procedure that prepares a state whose amplitudes are proportional to the entries of a vector \(v\) has not output \(v\). Reading even one entry to accuracy \(\epsilon\) generally needs on the order of \(1/\epsilon^2\) repetitions of the whole procedure, and listing all \(N\) entries is at least as costly as \(N\). Algorithms for linear systems, later in the course, produce exactly such states, so this distinction will matter there.

So the second item of every problem statement in this course is the output type: a bit, a string, an estimate with tolerance and confidence, a sample with a distance to the target distribution, or a state with a fidelity requirement. Without it, “faster” has no meaning.

For Deutsch’s problem we assume access to a reversible version of the device, the oracle

\[U_f\ket{x}\ket{y}=\ket{x}\ket{y\oplus f(x)},\qquad x,y\in\{0,1\}.\]

The first register selects the input and is left unchanged. The second, the target, is flipped exactly when \(f(x)=1\). On the four basis states, \(U_f\) is a permutation, so it is unitary; applying it twice restores everything, so \(U_f^{-1}=U_f\). One application of \(U_f\) is one query, whatever state it is applied to.

Why does “whatever state” matter? Because \(U_f\) is linear, it can act on a superposition of inputs, which the lamp cannot. Prepare the input in \(\ket+=(\ket0+\ket1)/\sqrt2\) and the target in \(\ket0\). One query gives

\[U_f\,\frac{\ket0+\ket1}{\sqrt2}\ket0=\frac{\ket0\ket{f(0)}+\ket1\ket{f(1)}}{\sqrt2}.\]

What to observe

The measurement returns \((0,f(0))\) or \((1,f(1))\), each with probability \(1/2\). Either way we learn one value of \(f\) and nothing about the other, so \(d\) is not determined: we are exactly where the classical single look left us. Writing both values into a superposition is not the same as being able to read them.

Access with this property, where a single use acts linearly on a superposition of questions, is called coherent access. It is an assumption about the problem, not a consequence of quantum mechanics. A physical lamp on a lab bench offers no such operation. When \(f\) is given as a classical program, we can build \(U_f\) from reversible gates, as we will do when we turn classical programs into oracles, and its cost is then a gate count, not an abstract query.

The oracle contract says what \(U_f\) does. Later algorithms will want more: to undo an operation, to control it, to reuse a state, or to start from a table of numbers. Does the contract supply these? We try each in turn and see where it fails.

Suppose we must undo a unitary \(U\). For \(U_f\) this is free, because \(U_f\) is its own inverse. For a general \(U\) handed to us as a sealed box, we can only apply \(U\) itself. If we know a gate sequence for \(U\), we can reverse its order and invert each gate. Without that sequence, applying \(U^\dagger\) is an extra capability, called inverse access.

Next suppose we want \(U\) to act only on the branch where a control qubit is \(1\). From a gate sequence we can control each gate. But a sealed box is known only by its effect on states, and that effect does not fix a global phase: \(U\) and \(e^{i\alpha}U\) act identically. Once controlled, the phase \(e^{i\alpha}\) multiplies only the branch where the control is \(1\). It has become a relative phase between branches, which interference can detect. So the controlled box must be specified separately, phase included. This capability is controlled access.

Now suppose an algorithm needs a state \(\ket\psi\) several times and we hold one copy. Could we copy it? No procedure copies an unknown state; this is the no-cloning theorem. So we must be given either a preparation circuit or many copies, and the number of copies is a resource.

Finally, suppose the input is a classical table of \(N\) numbers. The algorithm wants them as amplitudes, or as an oracle it can query in superposition. Neither exists until a circuit builds it. Such a data loading circuit must read the table, so its cost can be comparable to \(N\). If we assume loading is free, an apparent speedup may come from that assumption alone.

Each of these capabilities returns later. Amplitude amplification uses a preparation and its inverse. Phase estimation uses controlled powers of a unitary. Linear-system solvers assume that a matrix is stored inside a larger unitary. In each case the speedup is stated relative to that access, and the access must be implemented and paid for in a full accounting. A box labelled \(U_f\) in a circuit diagram can contain thousands of elementary gates and its own workspace.

We want \(f(0)\) and \(f(1)\) to contribute to the same amplitude with signs that depend on the values. Signs combine the way we need: \((-1)^{f(0)}+(-1)^{f(1)}\) is \(\pm2\) when the values agree and \(0\) when they differ. So aim to put the function values into signs.

The target state \(\ket-=(\ket0-\ket1)/\sqrt2\) does this. Flipping it only changes its sign, \(X\ket-=-\ket-\). So when the oracle flips the target, the state picks up a factor \(-1\), and when it does not, nothing changes:

\[U_f\ket{x}\ket-=(-1)^{f(x)}\ket{x}\ket-.\]

The target ends in the same state \(\ket-\) for both inputs, and the function value has moved into a sign on the input. This is phase kickback; the resulting map \(\ket x\mapsto(-1)^{f(x)}\ket x\) is called a phase oracle. Now query with the input in \(\ket+\):

\[U_f\ket+\ket-=\frac{(-1)^{f(0)}\ket0+(-1)^{f(1)}\ket1}{\sqrt2}\otimes\ket-.\]

The two signs are relative phases between the input branches, which a Hadamard can turn into probabilities. Using \(H\ket0=(\ket0+\ket1)/\sqrt2\) and \(H\ket1=(\ket0-\ket1)/\sqrt2\), the input becomes

\[\frac{(-1)^{f(0)}+(-1)^{f(1)}}{2}\ket0+\frac{(-1)^{f(0)}-(-1)^{f(1)}}{2}\ket1.\]

If the values agree, the amplitude of \(\ket1\) is zero and the amplitude of \(\ket0\) has magnitude one. If they differ, the reverse. Measuring the input therefore returns \(d\) with certainty.

Starting from \(\ket0\ket1\), two Hadamards prepare \(\ket+\ket-\). Register order is input first, then target. The target is never measured. Notice what the design required: we first wrote down the quantity we wanted, \((-1)^{f(0)}\pm(-1)^{f(1)}\), and then chose the encoding and the final gate to produce it as an amplitude. That direction of reasoning, from desired amplitude back to circuit, is the habit this course tries to build.

Why not keep the simpler target \(\ket0\)? Let us see exactly what goes wrong, because the same failure will reappear inside every larger algorithm.

What to observe

Measuring \(d=1\) on the input has probability \(1/2\). Because the target holds a record \(\ket{f(x)}\) of which input branch occurred, contributions ending with different target records belong to orthogonal subspaces and cannot cancel.

The query gives \((\ket{00}+\ket{11})/\sqrt2\). Applying \(H\) to the first qubit,

\[\frac{1}{2}\big(\ket{00}+\ket{10}+\ket{01}-\ket{11}\big).\]

There is a minus sign, as in the successful circuit, but it sits on \(\ket{11}\), while the plus sign it would need to cancel sits on \(\ket{10}\). Those are different basis states of the pair. Amplitudes add only when they belong to the same complete configuration, so nothing cancels. Each input outcome has probability \(1/4+1/4=1/2\).

The target has become a which-path record: its value tells which input branch produced each term. Whenever two branches carry orthogonal records, they cannot interfere, and it makes no difference whether anyone looks at the record. Ignoring it does not erase it. The \(\ket-\) target avoided creating a distinguishing record in the first place: it ends in the same state on both branches, so the branches differ only by a sign on the input, and the sign can be made to cancel.

In larger algorithms some temporary record is unavoidable. Computing \(f\) from a formula usually leaves intermediate values in scratch qubits, and those values depend on \(x\). We will remove them by running the computation backwards after its answer has been used. For now, the design rule is simple to state: everything that distinguishes branches meant to interfere must be gone before they meet.

Look at the input register just before the final Hadamard. Constant functions leave it in \(\pm\ket+\) and balanced functions in \(\pm\ket-\). Measured directly in the computational basis, both give a fair coin. The answer is fully present, but this measurement is blind to it.

What makes the answer readable at all is that \(\ket+\) and \(\ket-\) are orthogonal: \(\braket{+}{-}=\frac12(1\cdot1+1\cdot(-1))=0\). Orthogonal states can be distinguished with certainty by measuring in a basis that contains them. The Hadamard is the change of basis that does this, since \(H\ket+=\ket0\) and \(H\ket-=\ket1\). Applying \(H\) and then measuring in the computational basis is the same as using \(\{\ket+,\ket-\}\) as the measurement basis.

The complete output state is

\[(-1)^{f(0)}\ket{d}\ket-,\qquad d=f(0)\oplus f(1).\]

The factor \((-1)^{f(0)}\) is a global phase and changes no probability. So the circuit separates the two classes of function but cannot tell the two members of each class apart. That loss is not a defect: we asked only for \(d\). It is also a warning. What if the states \(\ket a\) and \(\ket b\) encoding two answers were not orthogonal? If they were identical, every measurement would give them the same statistics, and the best we could do is guess, right half the time. Between orthogonal and identical, a quoted result of Helstrom (1969) gives the smallest error probability for two equally likely pure states:

\[P_{\text{err}}=\tfrac12\Big(1-\sqrt{1-|\braket ab|^2}\Big).\]

It is \(0\) when the overlap is \(0\) and \(\tfrac12\) when the overlap is \(1\), matching the two extremes. So designing an algorithm includes making the answer states orthogonal, or nearly so.

Deutsch’s circuit is exact. Most algorithms are not: they output a correct answer with some probability less than one, or an estimate with some error. The readout procedure must then say how runs are combined and what the combination guarantees.

Boosting a decision. Suppose a decision algorithm is correct with probability at least \(3/4\) on every input. Run it three times independently and take a majority vote. The majority is right if at least two runs are right:

\[\Pr[\text{majority correct}]\ \ge\ \left(\tfrac34\right)^3+3\left(\tfrac34\right)^2\tfrac14=\tfrac{27}{64}+\tfrac{27}{64}=\tfrac{27}{32}\approx0.84.\]

What do more runs buy? With single-run success \(3/4\), fifteen runs give a correct majority with probability about \(0.983\), and thirty-one runs about \(0.9987\). In general, write the single-run success as \(\tfrac12+\gamma\). A quoted result, the Chernoff–Hoeffding bound, says that the majority of \(R\) independent runs is wrong with probability at most \(e^{-2\gamma^2R}\). The failure probability falls exponentially in \(R\) as long as \(\gamma>0\). At \(\gamma=0\) every run is a coin flip, and voting cannot help.

Searching with a checker. If a run finds a valid answer with probability \(p\) and validity can be checked, then \(R\) independent runs all fail with probability \((1-p)^R\le e^{-pR}\). About \(\ln(1/\delta)/p\) runs bring the failure below \(\delta\). The checker is essential; without it we would not know which run to believe.

Estimating a probability. Suppose a measured bit is \(1\) with unknown probability \(p\), and we average \(R\) independent results. The average has mean \(p\) and variance \(p(1-p)/R\le1/(4R)\); variance is the expected squared deviation from the mean. Whenever the average misses \(p\) by more than \(\epsilon\), its squared deviation exceeds \(\epsilon^2\). Since the mean squared deviation is at most \(1/(4R)\), the probability of such a miss is at most

\[\Pr\big[|\bar p-p|>\epsilon\big]\le\frac{1}{4R\epsilon^2}.\]

This is Chebyshev’s inequality. It shows that precision \(\epsilon\) costs on the order of \(1/\epsilon^2\) repetitions. Halving the error quadruples the work. Amplitude estimation, built later from amplitude amplification, reduces this to order \(1/\epsilon\), at the price of longer circuits and stronger access assumptions. Repetition counts belong in every resource statement.

One more requirement hides in the word “independent.” Repetitions must use fresh preparations. Re-measuring the same post-measurement state returns the same outcome and adds no information.

Substituting the four rows of the table into the output formula gives the final states \(\ket0\ket-\), \(\ket1\ket-\), \(-\ket1\ket-\), and \(-\ket0\ket-\). That checks every allowed input. It is also more than a check: the formula \(\frac12\big((-1)^{f(0)}\pm(-1)^{f(1)}\big)\) explains why the answer comes out, which is what lets us generalize.

And there is nothing to scale yet. Deutsch’s problem has one size. A query count of one versus two is a constant-factor statement about a fixed problem. It cannot be extrapolated to say anything about how costs grow. To claim that one method scales better than another we need a family of problems indexed by a size \(n\), a proof of correctness for every allowed input of every size, and expressions for how each resource grows with \(n\) and with the requested accuracy.

Here is the first such family; we develop it fully when we study phase encoding. Let \(f:\{0,1\}^n\to\{0,1\}\) be promised to be either constant or balanced (a balanced function takes the value \(1\) on exactly half its inputs). Run the same design on \(n\) input qubits: Hadamards on all of them, one phase query, Hadamards again. The amplitude of the all-zero outcome is

\[\frac{1}{2^n}\sum_{x\in\{0,1\}^n}(-1)^{f(x)},\]

which is \(\pm1\) for a constant function and \(0\) for a balanced one. One query decides the promise problem exactly for every \(n\). That is a statement about a family, and its proof is a single line valid for all \(n\). It is the Deutsch–Jozsa algorithm.

Generalizing correctly also means keeping the assumptions in view. For \(n=1\) the promise was automatic; for \(n\ge2\) it is not. A function with three ones among eight inputs gives zero-outcome amplitude \((5-3)/8=1/4\), so the circuit outputs “constant” with probability \(1/16\) and something else otherwise. On such inputs the output means nothing, and the problem statement must say so.

A speedup is a comparison against a classical baseline: the best known classical method for the same task, under the same access and success criterion. Both sides must play the same game. For Deutsch’s problem the game is query complexity: count only uses of the function, under exact success. Classically two queries are necessary; quantumly one suffices. Could a randomized classical algorithm do better with one query if it is allowed to err?

No better than guessing. Pick the four functions uniformly at random and fix the algorithm’s internal coin flips. Whichever input it queries, the other value is a fresh fair bit, independent of what it saw. So \(d\) is a fair bit given everything the algorithm knows, and any output rule is right with probability exactly \(1/2\) on average. Averaging over the algorithm’s coins preserves this, so on at least one of the four functions the success probability is at most \(1/2\). Random guessing already achieves \(1/2\) on every input. The quantum circuit gives certainty.

That is the query comparison. Complete resource accounting lists more. For the circuit as drawn, with ideal oracle access:

The table separates resources that are often blurred. A query count is not a runtime. A runtime comparison would include building the oracle on both sides, the gates, the measurement, and any classical processing, all under the same allowed error. For Deutsch’s problem in particular, if \(f\) is given as a small classical circuit, evaluating it twice classically is cheap and the quantum version saves essentially nothing. The value of the example lies elsewhere: it isolates the mechanism of phase kickback plus interference, which becomes powerful when the same mechanism acts on exponentially many inputs at once.

Which of our decisions did the real work, and which were bookkeeping? Written in order, the decisions form a design process, and we can apply it to any proposed quantum algorithm. Each row of the table is one decision, posed as a question.

The decisive step was the encoding. We needed the parity of two values, so we encoded those values as signs and made the signed amplitudes meet in one output amplitude. The \(\ket-\) target made the oracle change a relative phase without leaving a record, and the final Hadamard converted that phase relation into a classical bit. Everything else was bookkeeping, but bookkeeping that would have hidden a mistake if skipped.

The one-query form of the algorithm presented here, with the target in \(\ket-\), is due to Cleve, Ekert, Macchiavello, and Mosca, Quantum Algorithms Revisited (1998), refining Deutsch’s original 1985 procedure, which succeeded only half the time. The family generalization is Deutsch and Jozsa, Rapid solution of problems by quantum computation (1992).

For a new problem, the same questions apply in the same order. What must be learned, and what does the input representation allow? Which encoding makes amplitudes or phases depend on that property? Which branches must interfere, and what records would stop them? What measurement would reveal the answer, and how often must it be repeated? How do all costs grow with size and accuracy, and what is the best classical method for the same task?

The rest of the course supplies tools for answering these questions, organized by technique rather than by famous algorithm. Named algorithms appear as applications or combinations.

The techniques overlap and build on one another. Phase estimation is controlled powers plus phase kickback plus an inverse Fourier transform. Amplitude estimation is amplification plus phase estimation. Later, a matrix stored inside a larger unitary will be turned into a set of rotations, so that the reflections of a walk act on that matrix. When a chapter uses an earlier technique, it says so and reuses the earlier analysis instead of repeating it.

Our next obstacle is already visible. Realistic function evaluation needs scratch space, and scratch space that remembers the input is exactly the kind of which-path record that destroyed interference when we used the target \(\ket0\). So we next build function evaluations that leave precisely the intended output and restore their temporary storage.