Chapter 10

Phase kickback and the Deutsch–Jozsa algorithm

A black box computes a one-bit function $f$ of one bit. To decide with certainty whether $f(0)=f(1)$, a classical computer must query the box twice. How can one query decide it, when neither value of $f$ is ever read out?

Before you start: Relative phase (Chapter 1); the Hadamard gate and reversible function evaluation, the oracle $U_f$ (Chapter 4). A change of basis before measurement, as in Bell decoding (Chapter 9). Notation guide.

Turn a bit flip into a phase

$$U_f|x\rangle|-\rangle=|x\rangle X^{f(x)}|-\rangle=(-1)^{f(x)}|x\rangle|-\rangle.$$

The target is unchanged and factors out, while the data branch acquires a sign. The function value has not been written anywhere a computational-basis measurement could read it; it has become a sign. On a single basis input this sign is global and unobservable. On a superposition of different inputs, different signs become relative phases and can affect interference. This is phase kickback.

Deutsch's one-bit problem

For $f:\{0,1\}\to\{0,1\}$, decide whether $f(0)=f(1)$ or $f(0)\ne f(1)$. Prepare the data qubit in $|+\rangle$ and the target in $|-\rangle$. After one oracle call, suppressing the unchanged target, the data state is

$$\frac{(-1)^{f(0)}|0\rangle+(-1)^{f(1)}|1\rangle}{\sqrt2}.$$

Applying $H$ gives

$$\frac{(-1)^{f(0)}+(-1)^{f(1)}}2|0\rangle+\frac{(-1)^{f(0)}-(-1)^{f(1)}}2|1\rangle.$$

Equal function values make the $|1\rangle$ amplitude zero and the other amplitude $\pm1$. Different values make the $|0\rangle$ amplitude zero. Measuring the data qubit therefore returns $f(0)\oplus f(1)$ with certainty. We learn a relation between the values, not the two values separately.

For $f(0)=1,f(1)=0$, the post-oracle state is $-| -\rangle$, and the final state is $-|1\rangle$. The common minus sign has no effect on the answer. This example is a useful check that a negative amplitude is not a negative probability.

What happens without the final Hadamard?

Measuring the phase-encoded data state directly in the computational basis returns $0$ or $1$ with probability $1/2$, for every function. It does not reveal $f(x)$ at the sampled input: the value is stored in a phase that this measurement ignores. This differs from the state $\sum_x|x\rangle|f(x)\rangle/\sqrt N$ (here and below $N=2^n$ counts the $n$-bit inputs), where measuring both registers does return one input-output pair.

The final gate matters because it adds the two amplitudes for one outcome and subtracts them for the other. The problem is designed so that those sums depend only on the property being sought. We can identify which output cancels by adding its contributions, which is the calculation that will generalise to more input bits.

Extend the calculation to $n$ input bits

Let $N=2^n$. Promise that $f:\{0,1\}^n\to\{0,1\}$ is either constant or balanced, meaning exactly $N/2$ inputs give one. Prepare $|0^n\rangle$, apply $H^{\otimes n}$, call the oracle with a $|-\rangle$ target, and apply $H^{\otimes n}$ again.

Here $H^{\otimes n}$ means one Hadamard on each of the $n$ qubits. It acts on a basis string $x$ as $H^{\otimes n}|x\rangle=N^{-1/2}\sum_z(-1)^{x\cdot z}|z\rangle$, where $x\cdot z$ is defined below.

The $n$-qubit Hadamard identity, derived from the one-qubit rule

The notation $H^{\otimes n}$ means one Hadamard on each of the $n$ qubits, with no interaction between them in this layer. Start with a single bit $b$. The two rules for $H$ combine into one expression:

$$H|b\rangle=\frac{|0\rangle+(-1)^b|1\rangle}{\sqrt2} =\frac1{\sqrt2}\sum_{z=0}^1(-1)^{bz}|z\rangle.$$

For two input bits, distributing the tensor product produces

$$H^{\otimes2}|x_1x_2\rangle =\frac12\sum_{z_1,z_2=0}^1(-1)^{x_1z_1}(-1)^{x_2z_2}|z_1z_2\rangle.$$

The factor $1/2$ comes from two factors of $1/\sqrt2$, and the signs multiply by adding their exponents. With $n$ qubits there are $2^n$ output strings, each with magnitude $2^{-n/2}$. Its sign is determined by the parity of $\sum_jx_jz_j$. This derives the many-qubit identity used below, rather than introducing a separate transform rule.

For bit strings, write $x\cdot z=\sum_jx_jz_j\pmod2$. The identity $H^{\otimes n}|x\rangle=N^{-1/2}\sum_z(-1)^{x\cdot z}|z\rangle$ gives the final amplitude

$$a_z=\frac1N\sum_x(-1)^{f(x)+x\cdot z}.$$

At $z=0^n$, this is the average of $(-1)^{f(x)}$. A constant function gives $a_0=\pm1$ and hence outcome $0^n$ certainly. A balanced function gives $a_0=0$ and hence a nonzero string certainly. If the promise is violated, the binary decision is not guaranteed: if a fraction $q$ of outputs are one, then $p(0^n)=(1-2q)^2$.

A complete two-bit example

Take $f(x_1x_2)=x_1\oplus x_2$. In basis order $00,01,10,11$, the oracle produces amplitudes $(1,-1,-1,1)/2$. This factors as $|-\rangle\otimes|-\rangle$. The last Hadamards give $|11\rangle$. Thus the balanced verdict is certain, and here even the particular nonzero output is fixed. Other balanced functions can have different output distributions.

Two input bits, three functions. Left: after the oracle, each amplitude is $\pm\tfrac12$, the sign being $(-1)^{f(x)}$; a computational-basis measurement here would give each string with probability $\tfrac14$, the same for all three functions. Right: the final Hadamards add the four signed amplitudes with a different sign pattern for each output string. For the constant function they all add at $00$. For the balanced functions shown, the amplitudes cancel at $00$ and combine at a single nonzero string: $11$ for $x_1\oplus x_2$, the chapter's example, and $10$ for $f=x_1$. Other balanced functions can spread over several nonzero strings; only the zero at $00$ is guaranteed.

Count the right resource

A deterministic classical algorithm needs $N/2+1$ queries in the worst case: after $N/2$ identical values, both promises remain possible. The quantum circuit uses one oracle call. But a randomised classical algorithm can sample $k$ inputs independently and declare balanced if it sees both values. On a balanced function the probability all values agree is $2(1/2)^k=2^{1-k}$; on a constant function it is always correct.

The exponential contrast is therefore with exact deterministic query complexity, not with bounded-error classical computation. Total execution cost also includes preparing registers, implementing the oracle, and applying gates. The oracle model isolates one resource; it does not settle practical runtime.

Where this leaves us

One query suffices because the query is made on a superposition of both inputs with the target in $|-\rangle$, so each value of $f$ becomes a sign on its branch rather than a readable bit. The final Hadamard adds the two signed amplitudes at one outcome and subtracts them at the other, so the outcome reports $f(0)\oplus f(1)$ with certainty, and neither value separately. With $n$ input bits the same circuit decides constant against balanced with one query. That contrast is with exact deterministic classical algorithms; a randomised classical algorithm with a small error probability needs only a few queries.

Here every phase was $\pm1$, and the final change of basis was a layer of Hadamards. Phases can take any value on the unit circle, and a periodic function can write a pattern of them. The next chapter uses the transform that reads such patterns, the quantum Fourier transform, to find a period, and follows the classical work the answer still needs.

Problems

1. Replace the target $|-\rangle$ by $|+\rangle$. What answer distribution results?

Worked answer

On the replacement target, $X|+\rangle=(|1\rangle+|0\rangle)/\sqrt2=|+\rangle$. Therefore either oracle action, $X^0$ or $X^1$, gives the same target vector with the same phase:

$$U_f\left(\frac1{\sqrt N}\sum_x|x\rangle|+\rangle\right)=\frac1{\sqrt N}\sum_x|x\rangle|+\rangle.$$

The input data state is still $H^{\otimes n}|0^n\rangle$. The final Hadamard layer gives $(H^2)^{\otimes n}|0^n\rangle=|0^n\rangle$. Its outcome is zero for every function, so it cannot distinguish the two promises.

The tempting wrong turn is to think the oracle did nothing here. It did act, flipping the target in every branch where $f(x)=1$, but $|+\rangle$ is unchanged by a flip, so no branch acquired a sign and there was nothing for the final Hadamards to convert.

2. Let $f(x)=s\cdot x\oplus c$ for fixed string $s$ and bit $c$. Evaluate $a_z$.

Worked answer

Substitute $f(x)=s\cdot x\oplus c$ into the amplitude formula and use parity arithmetic to combine the exponents:

$$a_z=\frac{(-1)^c}{N}\sum_x(-1)^{(s\oplus z)\cdot x}.$$

If $z=s$, the exponent is zero for every $x$, giving $a_s=(-1)^c$. Otherwise choose an index $j$ where $s_j\ne z_j$ and pair each string $x$ with $x\oplus e_j$, where $e_j$ has only bit $j$ equal to one. Their exponents differ by one, so their contributions sum to zero. Every string belongs to exactly one such pair, making $a_z=0$ for all $z\ne s$. The output is consequently $(-1)^c|s\rangle$, with an irrelevant common sign.

References and further reading

Nielsen & Chuang, §1.4.1–1.4.4 (reversible computation, quantum parallelism, Deutsch, and Deutsch–Jozsa).