Quantum Computing · Chapter 07
In Chapter 6, we saw that applying a reversible circuit \(U_f\) to a superposition of inputs evaluates \(f(x)\) on every input at once, yet measuring the register reveals only one random pair \((x, f(x))\). Moreover, because the target qubit retains \(f(x)\), branches with different outputs cannot interfere.
We first introduce a model in which a function is accessed through queries and pose a problem that asks for a relation between function values. We then show how to record function values in the phases of amplitudes rather than in the target register, leading to our first quantum algorithm.
Can we learn a relation between two function values without learning the individual values themselves?
Suppose a function \(f\) takes one bit, \(0\) or \(1\), and outputs one bit, \(0\) or \(1\). Instead of asking for the values \(f(0)\) and \(f(1)\) separately, suppose we only want to know whether \(f(0)\) and \(f(1)\) are equal or different.
Classically, finding out whether \(f(0) = f(1)\) requires evaluating \(f\) twice—once on \(0\) and once on \(1\)—because knowing \(f(0)\) alone leaves both possibilities open. Can a quantum computation answer this question using only a single evaluation of \(U_f\)?
Use a reversible query to encode a property in relative phase and read it through interference.
Use reversible target updates, the Hadamard transformation, and joint-state notation.
The reversible target update of a function becomes a phase mark, and two-path interference becomes the readout.
Deutsch’s task here uses a one-bit Boolean function and an ideal reversible oracle. A single query does not reveal every function value.
7.1
To compare the power of quantum and classical computation without getting lost in hardware details, we count a resource that both models use in a well-defined way: calls to a black-box function \(f\). In this section, we classify the four one-bit Boolean functions into constant and balanced families, establish why any classical procedure needs two queries to tell them apart, and formulate the reversible unitary oracle \(U_f\) that allows a quantum computer to query the same black box.
constantbalancedpromise
Consider the four possible Boolean functions on a single bit, \(f:\{0,1\}\to\{0,1\}\), which we met in Chapter 2. Instead of asking for the full truth table of \(f\), let us ask a single yes-or-no question: is \(f(0)\) equal to \(f(1)\)? If \(f(0) = f(1)\)—which holds for the constant-\(0\) function (\(f(x)=0\)) and the constant-\(1\) function (\(f(x)=1\))—we say that \(f\) is constant. If \(f(0)\ne f(1)\)—which holds for the identity function (\(f(x)=x\)) and the negation function (\(f(x)=1\oplus x\))—equal numbers of inputs map to \(0\) and \(1\), and we say that \(f\) is balanced.
Notice how little information this question asks for: we only want the single parity bit \(f(0)\oplus f(1)\) (\(0\) for constant, \(1\) for balanced), not the individual values \(f(0)\) and \(f(1)\). Each of the two classes—constant and balanced—contains two functions that differ by an overall bit flip of their outputs. Can a computation extract the relation \(f(0)\oplus f(1)\) without having to evaluate \(f(0)\) and \(f(1)\) separately?
For a one-bit input, every function \(f:\{0,1\}\to\{0,1\}\) is automatically either constant or balanced. When this problem is generalized to \(n\)-bit functions \(f:\{0,1\}^n\to\{0,1\}\), most functions are neither constant nor balanced; restricting the input to belong to one of those two families is then a stated promise about the problem.
As we saw in Chapter 2, any of the four one-bit functions can be evaluated reversibly on two wires by keeping the input bit \(x\) on the top wire and XORing \(f(x)\) into a target bit \(y\) on the bottom wire, \((x,y)\mapsto (x, y\oplus f(x))\). Initializing \(y=0\) writes \(f(x)\) directly onto the target wire while preserving \(x\) so that the transformation is one-to-one.
List the four functions \(f:\{0,1\}\to\{0,1\}\) as pairs \((f(0),f(1))\), and classify each as constant or balanced.
\((0,0)\) and \((1,1)\) are constant; \((0,1)\) and \((1,0)\) are balanced.
Among the functions \(f:\{0,1\}^2\to\{0,1\}\), how many are constant, how many are balanced (output \(1\) on exactly half the inputs), and how many are neither?
There are \(2^4=16\) functions. Two are constant. A balanced function outputs \(1\) on exactly two of the four inputs, chosen in \(\binom42=6\) ways. The remaining \(16-2-6=8\) are neither, which is why the promise is needed.
For \(f\) on \(n\)-bit inputs, promised to be constant or balanced, show that a deterministic classical algorithm can decide which with \(2^{n-1}+1\) queries, and that \(2^{n-1}\) queries do not always suffice.
If two queried values differ, \(f\) is balanced. If \(2^{n-1}+1\) queried values all agree, \(f\) cannot be balanced, since a balanced function takes each value on only \(2^{n-1}\) inputs; so \(f\) is constant. With only \(2^{n-1}\) queries all returning \(0\), \(f\) could be the constant \(0\) or the balanced function that is \(1\) on all the unqueried inputs, so the algorithm cannot be sure.
query
Suppose our only access to \(f\) is through a black-box query: we submit a single input bit \(x\in\{0,1\}\) to the box, and the box returns the single output bit \(f(x)\). How many queries must a classical algorithm make to determine with certainty whether \(f\) is constant or balanced?
After just one classical query—say we query \(x=0\) and learn that \(f(0)=0\)—we still have zero information about \(f(1)\). If \(f(1)=0\), the function is constant; if \(f(1)=1\), the function is balanced. Even if we guess at random after one query, we will be wrong half the time on the worst-case choice of \(f\). Thus any classical algorithm that succeeds with certainty (or even with probability better than \(1/2\) in the worst case) must make two queries, evaluating both \(f(0)\) and \(f(1)\) and comparing them.
Keep in mind that this two-query requirement applies specifically to black-box query access, where we are not allowed to open the box and inspect a circuit diagram or algebraic formula for \(f\). Comparing algorithms by counting black-box calls isolates how efficiently each model extracts information from the function.
A classical algorithm queries \(f(1)\) and receives \(1\). Which of the four functions remain possible?
\((0,1)\), which is balanced, and \((1,1)\), which is constant. One reply is consistent with both answers.
For \(f\) on two-bit inputs, promised constant or balanced, an algorithm queries \(f(00)\) and \(f(01)\). If they differ it answers “balanced”; otherwise it makes one more query. Complete the algorithm, and give its number of queries in the worst case.
If \(f(00)=f(01)\), query \(f(10)\). If it differs, answer “balanced”; if it agrees, three of the four values agree, which rules out a balanced function, so answer “constant.” The worst case uses three queries, matching \(2^{n-1}+1\) for \(n=2\).
Show that no one-query classical algorithm for \(f:\{0,1\}\to\{0,1\}\), even one that chooses its query at random, is correct with probability greater than \(1/2\) on every function.
Average the success probability over the four functions, each weighted \(1/4\). Whatever input \(x\) is queried and whatever value \(v\) is returned, exactly two functions are consistent with the reply, one constant and one balanced, and they are equally weighted. So any answer is right for exactly one of them, and the average success is \(1/2\). Some function must therefore have success probability at most \(1/2\).
oracleblack-box
To give a quantum algorithm access to the same black-box function \(f\), the query operation must be a valid unitary transformation—even when \(f\) itself is a many-to-one constant function! As we saw in Section 2.3.3 and Section 6.5.1, our standard reversible embedding solves this cleanly: we supply an input wire \(\ket{x}\) and a target wire \(\ket{y}\), and define the quantum query gate \(U_f\) on the computational basis by
\[U_f\ket{x}\ket{y} = \ket{x}\ket{y\oplus f(x)},\qquad x,y\in\{0,1\}.\]
On the four two-qubit basis configurations \(\{\ket{00},\ket{01},\ket{10},\ket{11}\}\), \(U_f\) acts as a one-to-one permutation: for each \(x\in\{0,1\}\), if \(f(x)=0\) it leaves \(\ket{x0}\) and \(\ket{x1}\) unchanged, and if \(f(x)=1\) it swaps \(\ket{x0}\) and \(\ket{x1}\). Its \(4\times 4\) matrix is a permutation matrix with a single \(1\) in each row and column and \(0\)s elsewhere. Because permuting coordinates preserves inner products and swapping twice restores every basis state, \(U_f\) is unitary and self-inverse (\(U_f^2 = I\)) for every Boolean function \(f\).
In the black-box (or oracle) model of quantum computation, we call \(U_f\) the quantum oracle for \(f\), and we count each application of \(U_f\) in a circuit as one quantum query, regardless of whether its input wires are in a computational basis state or a superposition. Notice that if we feed a classical basis state \(\ket{x}\ket{0}\) into \(U_f\) and immediately measure the target wire, we learn \(f(x)\) in one query just like a classical query box; the oracle model treats internal gate construction inside \(U_f\) as a single black-box step so that classical and quantum query counts can be compared directly.
Write the action of \(U_f\) on the four basis states for \(f=(1,0)\), that is, \(f(0)=1\) and \(f(1)=0\).
\(\ket{00}\to\ket{01}\), \(\ket{01}\to\ket{00}\), \(\ket{10}\to\ket{10}\), and \(\ket{11}\to\ket{11}\): the target flips when the input is \(0\).
Write the matrix of \(U_f\) for \(f=(0,1)\) in the order \(00,01,10,11\), and check that it is unitary.
\(U_f\) fixes \(\ket{00}\) and \(\ket{01}\) and exchanges \(\ket{10}\) and \(\ket{11}\): the matrix of CNOT. It is a permutation matrix, whose columns are distinct basis vectors and hence orthonormal, so \(U_f^\dagger U_f=I\).
Show that the map \(\ket{x,y}\mapsto\ket{x,f(x)}\), which overwrites the target, is not unitary for any \(f\), and that \(\ket x\mapsto\ket{f(x)}\) is not unitary when \(f\) is constant.
Overwriting sends \(\ket{x,0}\) and \(\ket{x,1}\) to the same state \(\ket{x,f(x)}\), so it is not one-to-one, and a unitary is invertible. For constant \(f\), \(\ket0\) and \(\ket1\) both go to \(\ket{f(0)}\), again merging two orthogonal states. Keeping the input and adding into the target avoids both problems.
7.2
Because the quantum oracle \(U_f\) is a linear unitary operator, we can apply a single query to a superposition of both inputs \(x=0\) and \(x=1\). In this section, we trace what happens when we prepare the target qubit in \(\ket{0}\) and query \(U_f\) on an equal superposition of inputs—seeing why neither an immediate measurement nor a naive Hadamard interference step can distinguish a constant function from a balanced one when the target qubit records \(f(x)\).
Let us start our two-qubit register with the input wire in the uniform superposition \(\ket{+} = (\ket{0}+\ket{1})/\sqrt{2}\) (prepared by applying \(H\) to \(\ket{0}\)) and the target wire in \(\ket{0}\). When we apply the oracle \(U_f\) once, linearity carries both input branches through \(U_f\) simultaneously:
\[U_f\left(\frac{\ket{0}+\ket{1}}{\sqrt{2}}\otimes\ket{0}\right) = \frac{\ket{0}\ket{f(0)} + \ket{1}\ket{f(1)}}{\sqrt{2}}.\]
After just one query, both function values \(f(0)\) and \(f(1)\) sit inside the two-qubit state vector, each paired with its corresponding input bit. Does holding both values in this superposition mean we have already solved the problem? Not yet: we still have to extract the answer \(f(0)\oplus f(1)\) via a measurement.
Apply \(U_f\) for \(f=(1,1)\) to \(\tfrac{\ket0+\ket1}{\sqrt2}\otimes\ket0\).
Both inputs flip the target: \((\ket{01}+\ket{11})/\sqrt2=\ket+\ket1\), a product state.
For each of the four functions, write \(U_f\bigl(\tfrac{\ket0+\ket1}{\sqrt2}\otimes\ket0\bigr)\), and say which results are entangled.
\((0,0)\): \(\ket+\ket0\). \((1,1)\): \(\ket+\ket1\). \((0,1)\): \((\ket{00}+\ket{11})/\sqrt2\). \((1,0)\): \((\ket{01}+\ket{10})/\sqrt2\). The constant functions give product states; the balanced ones give entangled states.
With \(n\) input qubits in the uniform superposition and a clean target, \(U_f\) produces \(2^{-n/2}\sum_x\ket x\ket{f(x)}\). Measuring both registers gives a uniformly random \(x\) with \(f(x)\). About how many runs are needed, on average, before every value \(f(x)\) has been seen?
Each run reveals one input chosen uniformly from \(N=2^n\). After \(k\) distinct inputs have been seen, a new one appears with probability \((N-k)/N\), taking \(N/(N-k)\) runs on average. Summing, \(N\bigl(1+\tfrac12+\dots+\tfrac1N\bigr)\approx N\ln N\) runs are needed, more than the \(N\) queries of a classical algorithm that simply asks each input once.
What happens if we measure the two-qubit state \(\bigl(\ket{0}\ket{f(0)} + \ket{1}\ket{f(1)}\bigr)/\sqrt{2}\) in the computational basis right after the oracle call? Just as we saw for general quantum parallelism in Section 6.5.2, the measurement collapses the state to either \((0, f(0))\) with probability \(1/2\) or \((1, f(1))\) with probability \(1/2\). We learn a single randomly chosen input–output pair, while the other branch vanishes completely.
Flipping a classical coin to pick \(x\in\{0,1\}\) and querying \(f(x)\) classically would produce the exact same result! Simply putting both values into superposition and measuring in the computational basis gives zero advantage over a single classical query.
Remember, however, that we do not need to learn both \(f(0)\) and \(f(1)\); we only need to distinguish the constant case (\(f(0)=f(1)\)) from the balanced case (\(f(0)\ne f(1)\)). Can we apply a Hadamard gate \(H\) to the input wire before measuring so that the two branches \(x=0\) and \(x=1\) interfere?
Measure both registers of \((\ket{00}+\ket{11})/\sqrt2\). What are the possible results and their probabilities? How many function values does one run reveal?
\(00\) and \(11\), each with probability \(1/2\). One run reveals one pair \((x,f(x))\), a single function value.
To decide constant or balanced, we repeatedly prepare \((\ket{0,f(0)}+\ket{1,f(1)})/\sqrt2\) and measure both registers until both inputs have been seen. How many runs does this take on average?
The first run shows one input. Each later run shows the other input with probability \(1/2\), taking \(2\) runs on average. The total is \(1+2=3\) runs on average, worse than the two classical queries.
Show that measuring only the input register of \((\ket{0,f(0)}+\ket{1,f(1)})/\sqrt2\) gives \(0\) and \(1\) with probability \(1/2\) each for all four functions.
The probability of input \(x\) is the total squared amplitude of the configurations beginning with \(x\). There is exactly one, \(\ket{x,f(x)}\), with amplitude \(1/\sqrt2\), whatever \(f\) is. The input register alone reveals nothing about \(f\).
Let us test what happens if we apply \(H\otimes I\) to the state \(\bigl(\ket{0}\ket{f(0)} + \ket{1}\ket{f(1)}\bigr)/\sqrt{2}\) and then measure the input wire. When \(f\) is constant (\(f(0)=f(1)=c\)), both branches share the same target state \(\ket{c}\), so the state factors as \(\ket{+}\otimes\ket{c}\), and applying \(H\) to the input wire returns \(\ket{0}\otimes\ket{c}\)—giving input outcome \(0\) with certainty. What if \(f\) is balanced, say \(f(0)=0\) and \(f(1)=1\)? Then the state after the oracle is the entangled Bell state \((\ket{00}+\ket{11})/\sqrt{2}\)! Applying \(H\otimes I\) yields
\[(H\otimes I)\frac{\ket{00}+\ket{11}}{\sqrt{2}} = \frac{\ket{00}+\ket{10}+\ket{01}-\ket{11}}{2}.\]
Because the branch from \(x=0\) carries target state \(\ket{0}\) while the branch from \(x=1\) carries orthogonal target state \(\ket{1}\), the two paths arriving at input \(0\) land on distinct two-qubit configurations (\(\ket{00}\) and \(\ket{01}\)) and cannot cancel! Measuring the input wire yields \(0\) with probability \((1/2)^2 + (1/2)^2 = 1/2\) and \(1\) with probability \(1/2\).
Once again, we have run straight into the path-information barrier from Section 3.4.4 and Section 6.5.3: when \(f(0)\ne f(1)\), the target qubit initialized in \(\ket{0}\) records which branch was taken, entangling the target with the input and destroying interference on the input wire.
This diagnosis points directly to the cure. To make the \(x=0\) and \(x=1\) branches interfere on the input wire, we must prepare the target qubit in a state that ends up in the exact same target vector whether \(U_f\) leaves it alone (\(f(x)=0\)) or flips it with \(X\) (\(f(x)=1\))—while still picking up a numerical factor that distinguishes a flip from no flip!
For \(f=(0,1)\), apply \(H\) to the input of \((\ket{00}+\ket{11})/\sqrt2\), and find the probability of each input outcome.
\(H\) on the first qubit gives \(\tfrac12(\ket{00}+\ket{10}+\ket{01}-\ket{11})\). The input is \(0\) with probability \(\tfrac14+\tfrac14=\tfrac12\), and \(1\) with probability \(\tfrac12\). The target record prevents any cancellation.
For the constant function \(f=(0,0)\), repeat the calculation: start from \(\tfrac{\ket0+\ket1}{\sqrt2}\otimes\ket0\), apply \(U_f\), then \(H\) to the input.
\(U_f\) leaves \(\ket+\ket0\) unchanged, and \(H\) turns it into \(\ket0\ket0\). The input is \(0\) with certainty: here the target holds no record, because it is the same in both branches.
Combining the two previous problems, design a one-query procedure with a clean target that never wrongly answers “balanced.” With what probability does it detect a balanced function?
Run \(U_f\) on \(\ket+\ket0\), apply \(H\) to the input, and measure it. Constant functions always give \(0\); balanced ones give \(0\) or \(1\) with probability \(1/2\) each. Answer “balanced” on outcome \(1\), and “not sure” on \(0\). The answer “balanced” is never wrong, but it is given for a balanced function only half the time. Deutsch’s algorithm, whose target leaves no record, succeeds every time.
7.3
How can a target qubit respond to a bit flip \(X\) without changing its state vector into an orthogonal direction? The answer lies in the eigenvectors of \(X\). By preparing the target qubit in \(\ket{-} = (\ket{0}-\ket{1})/\sqrt{2}\), a bit flip multiplies the target by \(-1\) without altering its state vector, transferring the function value \(f(x)\) into a sign factor on the input wire—an effect called phase kickback. We also show how to achieve the exact same phase kickback when \(f\) is computed by a multi-gate reversible circuit that uses temporary workspace.
For each input \(x\), the oracle \(U_f\) acts on the target qubit either as the identity \(I\) (when \(f(x)=0\)) or as the bit-flip gate \(X\) (when \(f(x)=1\)). Which single-qubit states are changed by \(X\) only by an overall scalar factor? Let us test the two diagonal superposition states \(\ket{+} = (\ket{0}+\ket{1})/\sqrt{2}\) and \(\ket{-} = (\ket{0}-\ket{1})/\sqrt{2}\). Because \(X\) swaps \(\ket{0}\) and \(\ket{1}\),
\[X\ket{+} = \frac{\ket{1}+\ket{0}}{\sqrt{2}} = +\ket{+},\qquad X\ket{-} = \frac{\ket{1}-\ket{0}}{\sqrt{2}} = -\ket{-}.\]
In linear algebra, a nonzero vector that a linear operator transforms into a scalar multiple of itself is called an eigenvector (or eigenstate) of that operator, and the scalar multiplier is its corresponding eigenvalue. Thus \(\ket{+}\) and \(\ket{-}\) are eigenvectors of the bit-flip operator \(X\) with eigenvalues \(+1\) and \(-1\), respectively.
Which of these two eigenstates should we choose for our target qubit? If we prepare the target in \(\ket{+}\), both \(I\) (when \(f(x)=0\)) and \(X\) (when \(f(x)=1\)) multiply \(\ket{+}\) by \(+1\), so the oracle does nothing at all to the state—all dependence on \(f(x)\) is lost! If instead we prepare the target in \(\ket{-}\), then \(I\) multiplies \(\ket{-}\) by \(+1\) when \(f(x)=0\), while \(X\) multiplies \(\ket{-}\) by \(-1\) when \(f(x)=1\). In both cases the target qubit remains in the exact same state vector \(\ket{-}\), while the sign factor \(\pm 1\) records whether \(f(x)\) was \(0\) or \(1\)!
Compute \(X(\ket0+i\ket1)/\sqrt2\). Is \((\ket0+i\ket1)/\sqrt2\) an eigenvector of \(X\)?
\(X(\ket0+i\ket1)/\sqrt2=(i\ket0+\ket1)/\sqrt2=i(\ket0-i\ket1)/\sqrt2\). This is not a multiple of \((\ket0+i\ket1)/\sqrt2\), so it is not an eigenvector.
Find every state that \(X\) leaves unchanged apart from a factor, by solving \(X(a,b)^T=\lambda(a,b)^T\).
\(X(a,b)^T=(b,a)^T\), so \(b=\lambda a\) and \(a=\lambda b\), giving \(\lambda^2=1\). For \(\lambda=1\), \(a=b\): the state \(\ket+\). For \(\lambda=-1\), \(b=-a\): the state \(\ket-\). Up to global phase, these are the only two.
The target is prepared in \(\cos\theta\ket0+\sin\theta\ket1\), with real \(\theta\), and the oracle flips it. Show that its overlap with the original target is \(\sin2\theta\), and that the target keeps no record of the flip only when it is \(\ket+\) or \(\ket-\).
\(X(\cos\theta,\sin\theta)^T=(\sin\theta,\cos\theta)^T\), whose overlap with the original is \(2\cos\theta\sin\theta=\sin2\theta\). The target keeps no record when the flipped state equals the original up to a factor, which requires an overlap of magnitude \(1\): \(\sin2\theta=\pm1\), so \(\theta=\pm\pi/4\) up to multiples of \(\pi\). These are \(\ket+\) and \(\ket-\), up to sign. For any other target, the flip leaves a partial record that reduces the interference.
Let us evaluate \(U_f\) when the input wire is in a basis state \(\ket{x}\) and the target wire is prepared in \(\ket{-} = (\ket{0}-\ket{1})/\sqrt{2}\) (which we obtain by applying \(H\) to \(\ket{1}\)). When \(f(x)=0\), the target is untouched and stays \(\ket{-} = (+1)\ket{-}\); when \(f(x)=1\), the target is flipped by \(X\), which turns \(\ket{-}\) into \(-\ket{-} = (-1)\ket{-}\). Both cases combine into the single formula
\[U_f\ket{x}\ket{-} = (-1)^{f(x)}\ket{x}\ket{-}.\]
Now feed the uniform input superposition \(\ket{+} = (\ket{0}+\ket{1})/\sqrt{2}\) into \(U_f\) alongside the target \(\ket{-}\). By linearity,
\[U_f(\ket{+}\otimes\ket{-}) = \left(\frac{(-1)^{f(0)}\ket{0} + (-1)^{f(1)}\ket{1}}{\sqrt{2}}\right)\otimes\ket{-}.\]
Look closely at what just happened. The target qubit ends up in \(\ket{-}\) on both branches, so it factors completely out of the two-qubit state! Because the target stays in \(\ket{-}\) regardless of \(x\), it retains no path record and creates zero entanglement with the input register. Meanwhile, the scalar eigenvalue \((-1)^{f(x)}\)—since scalar factors move freely across a tensor product, \(\ket{x}\otimes\bigl((-1)^{f(x)}\ket{-}\bigr) = \bigl((-1)^{f(x)}\ket{x}\bigr)\otimes\ket{-}\)—has been "kicked back" onto the amplitude of the input configuration \(\ket{x}\). This remarkable mechanism is called phase kickback, and it turns the bit-flipping oracle \(U_f\) into an effective phase oracle \(O_f\ket{x} = (-1)^{f(x)}\ket{x}\) on the input register.
Now compare the state of the input wire for our two classes of functions. When \(f\) is constant (\(f(0)=f(1)\)), both terms carry the same sign \((-1)^{f(0)}\), so the input wire is in \(\pm(\ket{0}+\ket{1})/\sqrt{2} = \pm\ket{+}\), where the overall \(\pm\) is an unobservable global phase. When \(f\) is balanced (\(f(0)\ne f(1)\)), the two terms carry opposite signs, so the input wire is in \(\pm(\ket{0}-\ket{1})/\sqrt{2} = \pm\ket{-}\)! A single query has mapped constant and balanced functions into two orthogonal states of the input qubit: \(\pm\ket{+}\) versus \(\pm\ket{-}\).
For \(f=(1,0)\), compute \(U_f\ket+\ket-\).
The signs are \((-1)^{f(0)}=-1\) and \((-1)^{f(1)}=+1\), so the result is \(\tfrac{-\ket0+\ket1}{\sqrt2}\otimes\ket-=-\ket-\ket-\).
Prepare the input in \(\ket+\), but mistakenly prepare the target in \(\ket+\) too. Find the output of \(U_f\) for each of the four functions. Does leaving the target unentangled suffice to obtain useful phase kickback?
Since \(X\ket+=\ket+\), either value of \(f(x)\) leaves the target unchanged with eigenvalue \(+1\). For all four functions the output is \(\ket+\ket+\). The target is unentangled, but no information about \(f\) reaches the input. The \(\ket-\) preparation matters because a flip has eigenvalue \(-1\), giving different phases to different function values.
With \(n\) input qubits and the target in \(\ket-\), show that \(U_f\bigl(2^{-n/2}\sum_x\ket x\bigr)\ket-=\bigl(2^{-n/2}\sum_x(-1)^{f(x)}\ket x\bigr)\ket-\), and that the target ends in \(\ket-\) for every \(f\).
For each basis input, \(U_f\ket x\ket-=(-1)^{f(x)}\ket x\ket-\), because a flip multiplies \(\ket-\) by \(-1\) and no flip leaves it alone. By linearity, the superposition becomes \(\sum_x(-1)^{f(x)}\ket x\ket-\), up to the factor \(2^{-n/2}\). The target factors out as \(\ket-\), so it carries no record of \(x\).
compute, phase, uncompute
What if \(f(x)\) is not handed to us as an elementary black-box gate \(U_f\), but is instead computed by a multi-gate reversible circuit \(A\) that uses extra scratchpad (ancilla) qubits along the way? Recall from Section 2.4.3 that a forward pass of a reversible circuit \(A\) maps \(\ket{x}\ket{0}\ket{0}\) to \(\ket{x}\ket{f(x)}\ket{g(x)}\), where \(\ket{g(x)}\) holds the intermediate garbage bits left in the workspace. If we did not clean up \(\ket{g(x)}\), those workspace bits would vary with \(x\), acting as a path record that spoils interference just as surely as a target record!
We can produce a clean phase \((-1)^{f(x)}\) and erase all workspace records using the three-stage pattern compute, phase, uncompute: first run \(A\) forward to compute \(\ket{x}\ket{f(x)}\ket{g(x)}\); next apply a single-qubit phase-flip gate \(Z\) to the answer wire \(\ket{f(x)}\), which multiplies the branch by \((-1)^{f(x)}\); and finally run the inverse circuit \(A^\dagger\) (which applies the reversed sequence of gates) to uncompute both the answer wire and the workspace back to \(\ket{0}\ket{0}\):
\[A^\dagger Z_{\mathrm{answer}} A\,\ket{x}\ket{0}\ket{0} = A^\dagger\bigl((-1)^{f(x)}\ket{x}\ket{f(x)}\ket{g(x)}\bigr) = (-1)^{f(x)}\ket{x}\ket{0}\ket{0}.\]
Because the phase factor \((-1)^{f(x)}\) is just a scalar multiplier on the branch \(\ket{x}\), it stays intact while \(A^\dagger\) restores the answer and ancilla registers to \(\ket{0}\ket{0}\) for every \(x\). When counting gate complexity rather than black-box queries, we must remember that this construction runs both \(A\) and \(A^\dagger\), doubling the gate count of evaluating \(f\) once.
For \(f(x)=x\), computed into a clean answer bit by CNOT, compute \(\mathrm{CNOT}\,(I\otimes Z)\,\mathrm{CNOT}\) on \(\ket{0,0}\) and \(\ket{1,0}\).
\(\ket{00}\) passes unchanged, with \(Z\) acting on \(0\): the result is \(\ket{00}\). For \(\ket{10}\): CNOT gives \(\ket{11}\), \(Z\) gives \(-\ket{11}\), and CNOT gives \(-\ket{10}\). The phases are \((-1)^x\), and the answer bit is back to \(0\).
Compute \(\mathrm{CNOT}\,(I\otimes Z)\,\mathrm{CNOT}\) on all four basis states, and identify the operation. Why does compute, phase, uncompute need the workspace to start at \(0\)?
On \(\ket{x,y}\): CNOT gives \(\ket{x,y\oplus x}\), \(Z\) multiplies by \((-1)^{x\oplus y}\), and CNOT restores \(\ket{x,y}\). The operation is \(\ket{x,y}\mapsto(-1)^{x\oplus y}\ket{x,y}\), that is, \(Z\otimes Z\). Only when \(y=0\) is the phase \((-1)^{f(x)}\); a workspace starting elsewhere adds an unwanted phase.
Omit the uncomputation: compute \(f(x)=x\) into the answer bit with CNOT and apply \(Z\) to the answer bit, but do not run CNOT again. Starting from \(\ket+\ket0\), apply \(H\) to the input at the end. Show that the outcome is random, whereas with uncomputation it is certain.
CNOT gives \((\ket{00}+\ket{11})/\sqrt2\), and \(Z\) gives \((\ket{00}-\ket{11})/\sqrt2\). \(H\) on the input gives \(\tfrac12(\ket{00}+\ket{10}-\ket{01}+\ket{11})\), so the input is \(0\) or \(1\) with probability \(1/2\) each. With uncomputation, the state before \(H\) is \((\ket0-\ket1)\ket0/\sqrt2=\ket-\ket0\), and \(H\) gives \(\ket1\ket0\): outcome \(1\) with certainty. The answer bit left behind is a record that blocks the interference.
7.4
With phase kickback in hand, a single query to \(U_f\) encodes whether \(f\) is constant or balanced into the relative sign between \(\ket{0}\) and \(\ket{1}\) on the input qubit—producing \(\pm\ket{+}\) when \(f\) is constant and \(\pm\ket{-}\) when \(f\) is balanced. In this section, we complete Deutsch's algorithm with a final Hadamard gate that turns those orthogonal superpositions into the computational basis states \(\ket{0}\) and \(\ket{1}\), compare its single query against the two queries required classically, and review why each stage of the circuit is essential.
Immediately after the oracle call \(U_f(\ket{+}\otimes\ket{-})\), the target wire is in \(\ket{-}\) and the input wire is in the state
\[\frac{s_0\ket{0} + s_1\ket{1}}{\sqrt{2}},\qquad\text{where } s_x = (-1)^{f(x)} \in \{+1,-1\}.\]
If we measured the input wire in the computational basis right now, we would still get \(0\) or \(1\) with probability \(|s_x/\sqrt{2}|^2 = 1/2\) each, because a computational-basis measurement is blind to the relative sign between \(\ket{0}\) and \(\ket{1}\). To convert that relative sign into a deterministic readout, we apply a Hadamard gate \(H\) to the input wire, which maps \(\ket{+}\mapsto\ket{0}\) and \(\ket{-}\mapsto\ket{1}\):
\[H\left(\frac{s_0\ket{0}+s_1\ket{1}}{\sqrt{2}}\right) = \frac{s_0+s_1}{2}\ket{0} + \frac{s_0-s_1}{2}\ket{1} = (-1)^{f(0)}\ket{f(0)\oplus f(1)}.\]
Look at the two cases:
Notice that the overall sign \((-1)^{f(0)} = \pm 1\) is a global phase that disappears upon measurement: the measured bit is \(f(0)\oplus f(1)\) with certainty, revealing whether \(f(0)\) and \(f(1)\) agree without ever revealing whether \(f(0)\) itself is \(0\) or \(1\)!
Compute \(H\bigl((-\ket0+\ket1)/\sqrt2\bigr)\).
\(-\tfrac{H\ket0}{\sqrt2}+\tfrac{H\ket1}{\sqrt2}=\tfrac12\bigl(-(\ket0+\ket1)+(\ket0-\ket1)\bigr)=-\ket1\).
For each of the four functions, compute the final input amplitudes \((s_0+s_1)/2\) and \((s_0-s_1)/2\).
\((0,0)\): \(s=(1,1)\), amplitudes \((1,0)\). \((1,1)\): \(s=(-1,-1)\), amplitudes \((-1,0)\). \((0,1)\): \(s=(1,-1)\), amplitudes \((0,1)\). \((1,0)\): \(s=(-1,1)\), amplitudes \((0,-1)\). The constant functions give \(0\) and the balanced ones give \(1\), each up to sign.
Show that if the final \(H\) is omitted, or replaced by \(X\), the measurement gives \(0\) and \(1\) with probability \(1/2\) each, for every function.
Before the final step the input is \((s_0\ket0+s_1\ket1)/\sqrt2\) with \(s_x=\pm1\), so each outcome has probability \(1/2\). \(X\) only swaps the two amplitudes, leaving both probabilities at \(1/2\). Only an operation that combines the two amplitudes, such as \(H\), turns the relative sign into a definite outcome.
Deutsch’s algorithmquery separation
Putting all the steps together gives Deutsch’s algorithm:
In the ideal black-box model, Deutsch's algorithm succeeds with probability \(1\) using just \(1\) query to \(U_f\), whereas every deterministic (or bounded-error) classical algorithm requires \(2\) queries to \(f\). This \(1\)-versus-\(2\) gap is our first provable query separation between quantum and classical computation.
Let us be clear about the terms of this comparison. Both models are asked the exact same question about \(f\), but the quantum model is granted coherent access to the reversible oracle \(U_f\) so that it can query superpositions of inputs. While saving a single query on a tiny two-qubit problem is not a practical industrial speedup, Deutsch's algorithm exhibits in miniature the complete blueprint of quantum algorithm design: prepare a uniform superposition, use phase kickback to encode a global property into relative phases without leaving workspace records, and apply an interference transform to focus probability onto the answer.
Interactive figure. This circuit compares Deutsch’s parity test on constant and balanced Boolean functions. Select each oracle type, step through the phase kickback and final Hadamard gate, and test whether complementing every output flips the measured bit.
A constant function yields \(0\) and a balanced function yields \(1\). Complementing every function value multiplies the state after the phase oracle by a global sign \(-1\), leaving the final measurement outcome unchanged.
Count the queries and the other operations in Deutsch’s algorithm, starting from \(\ket{00}\).
One query to \(U_f\). Besides it: one \(X\) to prepare \(\ket1\), two \(H\) gates to prepare \(\ket+\ket-\), one final \(H\), and one measurement.
Run Deutsch’s algorithm for \(f=(1,0)\), giving the state after each step.
\(\ket0\ket1\to\ket+\ket-\to-\ket-\ket-\to-\ket1\ket-\). The input gives \(1\): balanced.
With \(n\) input qubits, after the query and \(H\) applied to each input qubit, show that the amplitude of the input configuration \(0^n\) is \(2^{-n}\sum_x(-1)^{f(x)}\). Deduce that one query distinguishes constant from balanced functions with certainty.
\(H\) on each qubit sends every \(\ket x\) to a superposition in which \(\ket{0^n}\) has amplitude \(2^{-n/2}\). Applied to \(2^{-n/2}\sum_x(-1)^{f(x)}\ket x\), it gives \(\ket{0^n}\) the amplitude \(2^{-n}\sum_x(-1)^{f(x)}\). For constant \(f\), this is \(\pm1\), so the outcome is \(0^n\) with certainty; for balanced \(f\), the signs cancel exactly and the outcome is never \(0^n\). One query suffices, against \(2^{n-1}+1\) classically.
Looking back across the circuit of Deutsch's algorithm, we see four interlocking stages—prepare coherent alternatives, kick back a function-dependent phase, recombine paths via interference, and measure—and we can see immediately why altering any stage breaks the algorithm:
Only when all four parts work together does a single oracle call resolve the problem. In Chapter 9, we will use the exact same phase-kickback mechanism to mark target solutions with a \(-1\) phase in quantum search—after first examining in Chapter 8 how oracles, reflections, and general quantum circuits are constructed from elementary gates.
Name the four stages of Deutsch’s algorithm and the operations used in each.
Prepare: \(X\) and two \(H\) gates make \(\ket+\ket-\). Encode: one query to \(U_f\) puts \(f\) into relative phase. Recombine: \(H\) on the input. Measure: the input in the computational basis.
Replace the target \(\ket-\) by \(\ket+\), and run the algorithm for \(f=(0,1)\). What does the measurement give?
\(X\ket+=\ket+\), so \(U_f\) leaves \(\ket+\ket+\) unchanged, and the final \(H\) gives \(\ket0\). The algorithm reports “constant” for a balanced function: with the wrong target, the function leaves no mark at all.
Leave out the first \(H\) on the input, so that the input stays \(\ket0\). Show that the algorithm then gives each outcome with probability \(1/2\) for every function.
\(U_f\ket0\ket-=(-1)^{f(0)}\ket0\ket-\), which depends only on \(f(0)\), and only through a global sign. The final \(H\) gives \(\pm\ket+\), so each outcome has probability \(1/2\). Without a superposition of inputs, the query sees only one input, and no relative phase forms.
Attempt each question before opening a hint. Explain your reasoning, then compare it with the solution.
For \(f=(0,1)\), what does \(U_f\) do to \(\ket1\ket-\)?
\(f(1)=1\), so the target flips.
\(X\ket-=-\ket-\).
The target flips, which multiplies \(\ket-\) by \(-1\): \(U_f\ket1\ket-=-\ket1\ket-\). The function value appears as a sign, and the target is unchanged.
A programmer prepares the target of Deutsch’s algorithm as \(\ket1\) but forgets the Hadamard on it, so the query acts on \(\ket+\ket1\). For the balanced function \(f=(0,1)\), find the state after the query and the probability that the final input measurement gives the correct answer \(1\).
\(U_f\ket x\ket1=\ket x\ket{1\oplus f(x)}\).
Do the two input branches end with the same target label?
The query gives \(\frac{1}{\sqrt2}(\ket0\ket1+\ket1\ket0)\): the target now records the input branch, exactly as with a blank target. After \(H\) on the input, the state is \(\frac12(\ket0\ket1+\ket1\ket1+\ket0\ket0-\ket1\ket0)\), and the input reads \(1\) with probability \(\frac14+\frac14=\frac12\). The target \(\ket1\) is a basis state, not an eigenstate of the flip, so the function value is written into the target instead of being kicked back as a sign. Only \(\ket-\) works.
For \(n=3\) input bits under the constant-or-balanced promise, how many queries does an exact deterministic classical algorithm need in the worst case? A randomized algorithm queries \(k\) inputs chosen uniformly at random (with replacement) and answers “constant” if all values agree. With what probability can it be wrong on a balanced function, and how large must \(k\) be for an error below \(1\%\)?
The worst case for a deterministic algorithm sees half the inputs agree.
On a balanced function, all \(k\) values agree with probability \(2\cdot2^{-k}\).
Deterministically, \(2^{n-1}+1=5\) queries are needed: after \(4\) equal answers the function could still be balanced. The randomized algorithm is never wrong on a constant function. On a balanced one, each query returns \(0\) or \(1\) with probability \(\frac12\), and all \(k\) agree with probability \(2^{1-k}\). That is below \(0.01\) for \(k\ge8\). Deutsch–Jozsa uses one query and never errs, but against algorithms allowed a small error the classical cost stays constant as \(n\) grows. The size of a quantum advantage depends on which classical success criterion is used for comparison.
Run the \(n\)-qubit version of Deutsch’s algorithm for \(n=2\) and the balanced function \(f(x_1x_2)=x_1\). Show that the outcome \(00\) never occurs.
After the query the input amplitudes are \((-1)^{x_1}/2\).
Factor the input state before applying \(H\otimes H\).
After the query, the input is \(\tfrac12(\ket{00}+\ket{01}-\ket{10}-\ket{11})=\ket-\ket+\). Applying \(H\otimes H\) gives \(\ket1\ket0\), so the outcome is \(10\), never \(00\). The function is identified as balanced with one query.
With the target in \(\ket-\), the query acts on the input as the phase oracle \(O_f=\mathrm{diag}\big((-1)^{f(0)},(-1)^{f(1)}\big)\). Write \(O_f\) for each of the four functions, and compute \(HO_fH\) in each case. Use the result to describe Deutsch’s algorithm as a single one-qubit operation.
The four phase oracles are \(I\), \(-I\), \(Z\), and \(-Z\).
\(HZH=X\) and \(HIH=I\).
For \(f=(0,0)\), \(O_f=I\); for \((1,1)\), \(-I\); for \((0,1)\), \(Z\); for \((1,0)\), \(-Z\). Conjugating by \(H\): \(HIH=I\), \(H(-I)H=-I\), \(HZH=X\), and \(H(-Z)H=-X\). So on the input qubit, Deutsch’s algorithm applies \(\pm I\) for a constant function and \(\pm X\) for a balanced one, to the input \(\ket0\). The result is \(\pm\ket0\) or \(\pm\ket1\), and the measurement reads the class with certainty. The signs are global phases, which is why the algorithm cannot reveal which constant or which balanced function was used.
Let \(f(x_1,x_2)=x_1\land x_2\) be computed by a Toffoli gate into an answer bit starting at \(0\). Apply compute, phase, uncompute: Toffoli, then \(Z\) on the answer bit, then Toffoli again. Show that the net operation on \(\ket{x_1x_2}\ket0\) is the controlled-\(Z\) gate on the two inputs, and that the answer bit returns to \(0\).
Track a basis input \(\ket{x_1x_2}\ket0\) through the three steps.
Controlled-\(Z\) multiplies \(\ket{11}\) by \(-1\) and leaves the other basis states alone.
On \(\ket{x_1x_2}\ket0\), the first Toffoli gate gives \(\ket{x_1x_2}\ket{x_1x_2}\). Then \(Z\) multiplies by \((-1)^{x_1x_2}\). The second Toffoli gate adds \(x_1x_2\) to the answer bit again, returning it to \(0\). The result is \((-1)^{x_1x_2}\ket{x_1x_2}\ket0\): a sign \(-1\) only on \(\ket{11}\), which is controlled-\(Z\), with the answer bit cleanly factored out. By linearity this holds for every superposition of inputs. The phase oracle of AND costs two Toffoli gates and one \(Z\), with one temporary bit, and the clean workspace is what allows the inputs’ signs to interfere later.
A circuit for \(f(x_1,x_2)=x_1\oplus x_2\) first copies \(x_1\) into a workspace bit \(w\), then forms the answer \(w\oplus x_2\). A programmer applies \(Z\) to the answer and uncomputes the answer step only, leaving \(w=x_1\). Starting from the uniform input superposition, apply \(H\) to both inputs and find the outcome distribution. Compare with the clean version.
Before the final Hadamards the state is \(\frac12\sum_x(-1)^{x_1\oplus x_2}\ket{x_1x_2}\ket{x_1}\).
Group the terms by the value of \(w\).
Group by \(w\). For \(w=0\) the input part is \(\frac12(\ket{00}-\ket{01})=\frac{1}{\sqrt2}\ket0\ket-\); for \(w=1\) it is \(\frac12(-\ket{10}+\ket{11})=-\frac{1}{\sqrt2}\ket1\ket-\). After \(H\otimes H\) these become \(\frac{1}{\sqrt2}\ket+\ket1\ket0\) and \(-\frac{1}{\sqrt2}\ket-\ket1\ket1\). The second input reads \(1\) with certainty, but the first input is \(\ket+\) on one record and \(\ket-\) on the other, so it reads \(0\) or \(1\) with probability \(\frac12\). The outcomes are \(01\) and \(11\), each with probability \(\frac12\). The clean version gives \(11\) with certainty. The garbage records \(x_1\), so it destroys exactly the interference that would reveal the \(x_1\) part of the answer, while the \(x_2\) part survives.
A student claims: “Deutsch’s algorithm evaluates \(f(0)\) and \(f(1)\) in one query, so with a better readout it could report both values.” Write the full two-qubit output state in terms of \(f(0)\) and \(d=f(0)\oplus f(1)\), and explain why no measurement of it can reveal \(f(0)\).
Factor out \((-1)^{f(0)}\) from the final input amplitudes.
Which part of the state depends on \(f(0)\) alone?
After the final Hadamard, the input is \(\frac{s_0+s_1}{2}\ket0+\frac{s_0-s_1}{2}\ket1\) with \(s_x=(-1)^{f(x)}\). Factoring out \(s_0\), this is \((-1)^{f(0)}\ket d\), so the output is \((-1)^{f(0)}\ket d\ket-\). The value \(f(0)\) appears only in a global phase, which no measurement detects, and the target \(\ket-\) is the same for every function. So the output carries exactly one bit, \(d\). The query did act on both inputs, but the interference that made \(d\) certain also discarded every other distinction. One query of this kind reveals at most one bit about \(f\), not both values.
Show that Deutsch’s algorithm gives the same outcome for \(f\) and for its complement \(1-f\), and that the outcome depends only on \(f(0)\oplus f(1)\).
Complementing \(f\) multiplies both signs by \(-1\).
The final amplitudes are \((s_0\pm s_1)/2\).
For \(1-f\), each sign \((-1)^{f(x)}\) is multiplied by \(-1\), a global phase that changes no probability. The outcome is \(1\) exactly when \(s_0\neq s_1\), that is, when \(f(0)\oplus f(1)=1\). The algorithm extracts this one bit and nothing more about \(f\).
A two-bit function is promised to have the form \(f(x)=s_1x_1\oplus s_2x_2\) for an unknown string \(s=s_1s_2\). Run the two-qubit version of the algorithm (Hadamards on both inputs, target \(\ket-\), one query, Hadamards on both inputs) for \(s=10\) and \(s=11\), and show that the measurement returns \(s\). How many classical queries are needed to learn \(s\)?
After the query the input amplitudes are \(\frac12(-1)^{s\cdot x}\).
\((-1)^{s_1x_1}(-1)^{s_2x_2}\) is a product of one-qubit sign patterns.
After the query the input state is \(\frac12\sum_x(-1)^{s_1x_1}(-1)^{s_2x_2}\ket{x_1x_2}=\frac{\ket0+(-1)^{s_1}\ket1}{\sqrt2}\otimes\frac{\ket0+(-1)^{s_2}\ket1}{\sqrt2}\). Each factor is \(\ket+\) if \(s_i=0\) and \(\ket-\) if \(s_i=1\), and \(H\) maps them to \(\ket0\) and \(\ket1\). So the output is \(\ket{s_1s_2}\) with certainty: \(10\) gives \(\ket{10}\) and \(11\) gives \(\ket{11}\). Classically each query returns one bit, \(s\cdot x\), and there are four possible strings, so two queries are necessary (and \(x=10,01\) suffice). With \(n\) bits the gap is one query against \(n\). This is the Bernstein–Vazirani problem, developed in Quantum Algorithms.
Where this leads. Chapter 8 constructs the oracle and other operations from elementary gates.