The Deutsch-Jozsa algorithm

The entanglement protocols of the past few sections solved communication problems. This section switches battlefields: computation. We will watch quantum mechanics beat the classical world at computing for the first time, cleanly — and the way it wins is not “calculating faster” but “asking fewer questions”.

The problem at the door: can one question identify both faces of a coin?

Someone hands you a black box (an oracle) containing a function $f:\{0,1\}^n\to\{0,1\}$ — feed it an $n$-bit string, it spits out one bit. They promise $f$ is one of exactly two kinds:

• Constant: every input gives the same output (all 0 or all 1);
• Balanced: exactly half the inputs give 0, the other half give 1.

The task: decide which. The only thing you can do is query — feed one input, see one output. Question: how few queries suffice?

The classical bill. With luck, 2 queries (two different outputs ⇒ balanced). But to declare “constant” beyond all doubt, the worst case requires

$$\frac{2^n}{2}+1=2^{n-1}+1\ \text{queries}\tag{9.7.1}$$

— if half the inputs have come back identical, only query number $2^{n-1}+1$ can settle it. For $n=100$ that is about $6.3\times10^{29}$ queries; the age of the universe would not cover it. The quantum algorithm queries once.

Why naive “quantum parallelism” is not enough

The quantum black box must be reversible (section 9.2); the standard construction adds an ancilla wire:

$$U_f\ket{x}\ket{y}=\ket{x}\ket{y\oplus f(x)}\tag{9.7.2}$$

($\oplus$ is addition mod 2; applying it twice undoes it, so it really is unitary.) The first move anyone thinks of: use a row of $H$‘s to build the superposition of all inputs, then query once:

$$U_f\left(\frac{1}{\sqrt{2^n}}\sum_x\ket{x}\right)\ket{0} =\frac{1}{\sqrt{2^n}}\sum_x\ket{x}\ket{f(x)}\tag{9.7.3}$$

One call, and all $2^n$ function values have been computed — that is quantum parallelism. But hold the celebration: measure this state and it collapses randomly onto a single $(x, f(x))$ pair, no different from one classical query. Section 9.1’s old lesson: information stored in a state ≠ information you can take out. Quantum parallelism is the necessary fuel; interference is the spark — the information of all the $f(x)$‘s must be funnelled into the probability distribution of the measurement outcome. The wrench that does the funnelling is called phase kickback.

Phase kickback: moving the function value into the phasebasic~5 minexpand

Prepare the ancilla in $\ket{-}=\frac{\ket{0}-\ket{1}}{\sqrt2}$ and feed it to $U_f$:

$$U_f\ket{x}\ket{-} =\ket{x}\otimes\frac{\ket{0\oplus f(x)}-\ket{1\oplus f(x)}}{\sqrt2}\tag{9.7.4}$$

Two cases:

• $f(x)=0$: the ancilla is $\frac{\ket{0}-\ket{1}}{\sqrt2}=\ket{-}$, untouched;
• $f(x)=1$: the ancilla is $\frac{\ket{1}-\ket{0}}{\sqrt2}=-\ket{-}$, an extra minus sign.

Both cases in one line:

$$U_f\ket{x}\ket{-}=(-1)^{f(x)}\ket{x}\ket{-}\tag{9.7.5}$$

The ancilla stays $\ket{-}$ throughout, and the function value has become a phase $(-1)^{f(x)}$ on the $\ket{x}$ branch. For a single $x$, a global phase means nothing; but in a superposition, each branch collects its own sign — they become relative phases, and relative phases are the control lever of interference (section 9.2’s lesson from $Z\ket{+}=\ket{-}$).

Hand-compute the smallest case first: the Deutsch algorithm (n = 1)

For $n=1$ there are four possible $f$‘s: constant ($f\equiv0$, $f\equiv1$), balanced ($f(x)=x$, $f(x)=1-x$). The decision problem boils down to one bit: $f(0)\oplus f(1)=?$ (0 ⇒ constant, 1 ⇒ balanced). The circuit:

|0⟩ ──[H]──┬──────[H]──[measure] → 0: constant / 1: balanced
           │Uf
|−⟩ ───────┴────────────────── (ancilla stays |−⟩ throughout)

Step by step (the ancilla stays $\ket{-}$; we write only the first qubit):

$$\ket{0} \ \xrightarrow{H}\ \frac{\ket{0}+\ket{1}}{\sqrt2} \ \xrightarrow{U_f}\ \frac{(-1)^{f(0)}\ket{0}+(-1)^{f(1)}\ket{1}}{\sqrt2}\tag{9.7.6}$$

Pull out the global phase $(-1)^{f(0)}$ (unobservable — discard):

$$=\frac{\ket{0}+(-1)^{f(0)\oplus f(1)}\ket{1}}{\sqrt2} =\begin{cases}\ket{+},&\text{constant}\\[2pt]\ket{-},&\text{balanced}\end{cases}$$

The final $H$ rotates $\ket{\pm}$ back to the computational basis:

$$\ket{+}\xrightarrow{H}\ket{0}\ (\text{constant}),\qquad \ket{-}\xrightarrow{H}\ket{1}\ (\text{balanced})\tag{9.7.7}$$

Measure the first qubit and read the answer deterministically. One query has extracted $f(0)\oplus f(1)$, which classically takes two — note that we did not obtain the individual values of $f(0)$ and $f(1)$, only one global property of theirs. Quantum speedup always plays this game: surrender pointwise information, gain global information.

The general case: n-qubit Deutsch–Jozsa

|0⟩ ──[H]──┬─────[H]──[measure]┐
|0⟩ ──[H]──┤Uf   [H]──[measure]├─ all 0: constant / otherwise: balanced
 ⋮    ⋮    │      ⋮     ⋮      │
|−⟩ ───────┴───────────────────┘ (ancilla not measured)

How interference concentrates the answer onto the all-zero stringadvanced~8 minexpand

Step 1: prepare and query. $n$ copies of $\ket{0}$ go through a row of $H$‘s, then phase kickback:

$$\frac{1}{\sqrt{2^n}}\sum_{x}\ket{x} \ \xrightarrow{U_f}\ \frac{1}{\sqrt{2^n}}\sum_{x}(-1)^{f(x)}\ket{x}\tag{9.7.8}$$

Step 2: another row of $H$‘s. We need the formula for $H^{\otimes n}$ acting on basis states. For one qubit, $H\ket{x}=\frac{1}{\sqrt2}\sum_{y}(-1)^{xy}\ket{y}$ (check by substituting $x=0,1$); for $n$ bits, multiply bit by bit:

$$H^{\otimes n}\ket{x}=\frac{1}{\sqrt{2^n}}\sum_{y}(-1)^{x\cdot y}\ket{y}, \qquad x\cdot y\equiv x_1y_1\oplus\cdots\oplus x_ny_n\tag{9.7.9}$$

Substituting gives the final state:

$$\ket{\Psi_{\text{final}}}=\sum_{y}\left[\frac{1}{2^n}\sum_{x}(-1)^{f(x)+x\cdot y}\right]\ket{y}\tag{9.7.10}$$

Step 3: look only at the amplitude of the all-zero string $y=0\cdots0$. There $x\cdot y=0$:

$$c_{0}=\frac{1}{2^n}\sum_{x}(-1)^{f(x)}\tag{9.7.11}$$

• Constant: all $2^n$ terms share one sign, $c_0=\pm1$. Probability $|c_0|^2=1$ — every branch interferes constructively and floods into the all-zero string; the measurement is certain to give $0\cdots0$.
• Balanced: half $+1$‘s, half $-1$‘s, cancelling in pairs, $c_0=0$ — the all-zero string is emptied by destructive interference; the measurement is certain to give a non-zero string.

The verdict: an all-zero readout ⇒ constant; any non-zero bit ⇒ balanced. One query, zero error rate.

∎Key formulas

• Quantum oracle

  $$U_f\ket{x}\ket{y}=\ket{x}\ket{y\oplus f(x)}$$

  The function query made reversible; applying twice undoes it

• Phase kickback

  $$U_f\ket{x}\ket{-}=(-1)^{f(x)}\ket{x}\ket{-}$$

  Set the ancilla to ∣−⟩ and the function value moves into the phase

• Hadamard transform

  $$H^{\otimes n}\ket{x}=\frac{1}{\sqrt{2^n}}\sum_y(-1)^{x\cdot y}\ket{y}$$

  x·y is the mod-2 sum of bitwise products

• Decision amplitude

  $$c_0=\frac{1}{2^n}\sum_x(-1)^{f(x)}=\pm1\ \text{or}\ 0$$

  Constant ⇒ all-zero string guaranteed; balanced ⇒ non-zero string guaranteed

?Self-check4 questions

1. 1.

   n = 3 (8 inputs). To decide constant/balanced beyond all doubt, how many queries does a classical algorithm need in the worst case?

   0% relative tolerance

   Submit
2. 2.

   What state must the ancilla be in for phase kickback?

   • ∣−⟩ = (∣0⟩ − ∣1⟩)/√2
   • ∣0⟩
   • ∣+⟩ = (∣0⟩ + ∣1⟩)/√2
   • Any state works

   Submit
3. 3.

   The algorithm ends and you measure the all-zero string 00…0. What does that tell you?

   • f is a constant function
   • f is a balanced function
   • f(00…0) = 0
   • This run failed and must be repeated

   Submit
4. 4.

   Which statements about "quantum parallelism" are correct? (Select all that apply.)

   Select all that apply

   • A single U_f call really does act on all 2ⁿ input branches at once
   • Measuring straight after the parallel step yields no more than one classical query
   • Interference gathers the phase information scattered across branches into a measurable global property
   • Quantum parallelism means every problem gets an exponential speedup

   Submit

What comes next

Deutsch–Jozsa is an exhibition match tailor-made for quantum mechanics: the problem is artificial, and classical randomised algorithms handle it easily too. A real-world problem looks like this: one of $N$ drawers hides a key, opening a drawer costs one look, and classically you open $N/2$ on average. Can quantum open fewer? Next section, Grover’s algorithm answers $\sqrt N$ — and we will see it with perfect clarity in a purely geometric picture: two mirrors squeezing out a rotation.