Simple Algorithm
Quantum Computing · Excited State · 22 min

Oracles & Phase Kickback: Deutsch–Jozsa

The first quantum speedups, and the trick behind them.

In 1985 David Deutsch noticed that a quantum computer can learn whether f(0)=f(1)f(0) = f(1), something that classically requires evaluating ff twice. The trick behind the modern one-query version, phase kickback, writes f(x)f(x) into the sign of an amplitude, and it sits inside nearly every quantum algorithm since.

What you’ll learn

  • Construct the bit oracle UfU_f, prove it is unitary and self-inverse, and explain why scratch garbage must be uncomputed.
  • Derive phase kickback with a ∣−⟩\ket{-} ancilla, both directly and as the eigenvalue of a controlled-XX.
  • Prove H⊗n∣x⟩=2−n/2∑y(−1)x⋅y∣y⟩H^{\otimes n}\ket{x} = 2^{-n/2}\sum_y(-1)^{x\cdot y}\ket{y} and use it to analyze Deutsch–Jozsa exactly.
  • Compare deterministic, randomized and quantum query costs for Deutsch–Jozsa and Bernstein–Vazirani.

Functions as unitaries

A classical function f:{0,1}n→{0,1}mf:\{0,1\}^n\to\{0,1\}^m is usually not reversible: f(x)f(x) alone does not determine xx. Quantum gates are unitary, hence reversible, so the map ∣x⟩↦∣f(x)⟩\ket{x}\mapsto\ket{f(x)} is not available. The standard fix keeps the input and XORs the output into a second register:

Uf∣x⟩∣y⟩=∣x⟩∣y⊕f(x)⟩,x∈{0,1}n, y∈{0,1}m.U_f\ket{x}\ket{y} = \ket{x}\ket{y\oplus f(x)}, \qquad x\in\{0,1\}^n,\ y\in\{0,1\}^m.
The bit (standard) oracle; ⊕\oplus is bitwise XOR.
DerivationU_f is unitary and self-inverse
  1. Uf2∣x⟩∣y⟩=∣x⟩∣y⊕f(x)⊕f(x)⟩=∣x⟩∣y⟩U_f^2\ket{x}\ket{y} = \ket{x}\ket{y\oplus f(x)\oplus f(x)} = \ket{x}\ket{y}

    Applying UfU_f twice XORs f(x)f(x) in and out again, since f(x)⊕f(x)=0f(x)\oplus f(x)=0.

  2. Uf2=I⟹Uf−1=UfU_f^2 = \id \quad\Longrightarrow\quad U_f^{-1} = U_f

    So UfU_f maps the computational basis to itself bijectively: it is a permutation matrix.

  3. Uf†=UfT=Uf−1=UfU_f^\dagger = U_f^{T} = U_f^{-1} = U_f

    Permutation matrices are real and orthogonal, so UfU_f is unitary; being its own inverse, it is also Hermitian.

Check your understanding

Take m=1m=1. Why can the "overwrite" map ∣x⟩∣y⟩↦∣x⟩∣f(x)⟩\ket{x}\ket{y}\mapsto\ket{x}\ket{f(x)} not be implemented as a quantum gate?

  1. It is unitary, but too slow to implement
  2. It sends ∣x⟩∣0⟩\ket{x}\ket{0} and ∣x⟩∣1⟩\ket{x}\ket{1} to the same state, so it is not injective and hence not unitary
  3. Quantum gates cannot act on two registers at once
  4. It is fine whenever ff is balanced
Show the answer

B. It sends ∣x⟩∣0⟩\ket{x}\ket{0} and ∣x⟩∣1⟩\ket{x}\ket{1} to the same state, so it is not injective and hence not unitary

Unitaries are invertible, so orthogonal inputs must stay orthogonal. Overwriting forgets yy: both ∣x⟩∣0⟩\ket{x}\ket{0} and ∣x⟩∣1⟩\ket{x}\ket{1} land on ∣x⟩∣f(x)⟩\ket{x}\ket{f(x)}. With XOR, yy can always be recovered.

Phase kickback

Feed the oracle's target register (take m=1m=1) the state ∣−⟩=12(∣0⟩−∣1⟩)\ket{-}=\tfrac{1}{\sqrt2}(\ket0-\ket1). Something odd happens: the target does not change, but the input register picks up a sign.

DerivationPhase kickback
  1. Uf∣x⟩∣−⟩=12(∣x⟩∣f(x)⟩−∣x⟩∣1⊕f(x)⟩)U_f\ket{x}\ket{-} = \tfrac{1}{\sqrt2}\big(\ket{x}\ket{f(x)} - \ket{x}\ket{1\oplus f(x)}\big)

    Apply UfU_f to each term of ∣−⟩\ket{-}.

  2. f(x)=0:12∣x⟩(∣0⟩−∣1⟩)=∣x⟩∣−⟩f(x)=0:\quad \tfrac{1}{\sqrt2}\ket{x}(\ket0-\ket1) = \ket{x}\ket{-}

    If f(x)=0f(x)=0 nothing changes.

  3. f(x)=1:12∣x⟩(∣1⟩−∣0⟩)=−∣x⟩∣−⟩f(x)=1:\quad \tfrac{1}{\sqrt2}\ket{x}(\ket1-\ket0) = -\ket{x}\ket{-}

    If f(x)=1f(x)=1 the two terms swap, which is an overall minus sign.

  4. Uf(∑xαx∣x⟩)∣−⟩=(∑x(−1)f(x)αx∣x⟩)∣−⟩U_f\Big(\sum_x\alpha_x\ket{x}\Big)\ket{-} = \Big(\sum_x(-1)^{f(x)}\alpha_x\ket{x}\Big)\ket{-}

    Both cases read Uf∣x⟩∣−⟩=(−1)f(x)∣x⟩∣−⟩U_f\ket{x}\ket{-} = (-1)^{f(x)}\ket{x}\ket{-}; by linearity the signs attach to every branch of a superposition, while the target factors out untouched.

Since the target stays in ∣−⟩\ket{-}, unentangled, we can drop it: one query to UfU_f implements the phase oracle

Of∣x⟩=(−1)f(x)∣x⟩.O_f\ket{x} = (-1)^{f(x)}\ket{x}.

Why it works: Uf=∑x∣x⟩ ⁣⟨x∣⊗Xf(x)U_f = \sum_x \dyad{x}\otimes X^{f(x)} is a controlled-Xf(x)X^{f(x)}, and ∣−⟩\ket{-} is the eigenstate of XX with eigenvalue −1-1. A controlled-UU acting on an eigenstate of UU leaves the target alone and kicks the eigenvalue back onto the control. This phase-kickback mechanism also drives phase estimation (see Phase Kickback & Phase Estimation).

Think first What would happen if qubit 1 started in ∣0⟩\ket{0} instead of ∣−⟩\ket{-}?

The CNOT would copy xx into qubit 1, producing 12(∣00⟩+∣11⟩)\tfrac{1}{\sqrt2}(\ket{00}+\ket{11}). No phase reaches qubit 0; its reduced state is now maximally mixed, and the final H yields a fair coin. The ∣−⟩\ket{-} ancilla is what turns "write f(x)f(x) down" into "mark xx with a sign".

Deutsch's algorithm

Deutsch's problem: given f:{0,1}→{0,1}f:\{0,1\}\to\{0,1\}, compute f(0)⊕f(1)f(0)\oplus f(1), i.e. decide whether ff is constant or balanced. One classical evaluation reveals one value, which says nothing about the XOR, so you need two; a randomized algorithm with one query is right only half the time. The circuit you just built does it with one query.

DerivationDeutsch's algorithm
  1. ∣0⟩∣1⟩→ H⊗H ∣+⟩∣−⟩\ket{0}\ket{1} \xrightarrow{\,H\otimes H\,} \ket{+}\ket{-}

    Input in ∣+⟩\ket{+}, target in ∣−⟩\ket{-}.

  2. → Uf 12((−1)f(0)∣0⟩+(−1)f(1)∣1⟩)∣−⟩\xrightarrow{\,U_f\,} \tfrac{1}{\sqrt2}\big((-1)^{f(0)}\ket{0} + (-1)^{f(1)}\ket{1}\big)\ket{-}

    Phase kickback on each branch.

  3. =(−1)f(0) 12(∣0⟩+(−1)f(0)⊕f(1)∣1⟩)∣−⟩= (-1)^{f(0)}\,\tfrac{1}{\sqrt2}\big(\ket{0} + (-1)^{f(0)\oplus f(1)}\ket{1}\big)\ket{-}

    Factor out the global phase (−1)f(0)(-1)^{f(0)}. What remains is ∣+⟩\ket{+} if f(0)=f(1)f(0)=f(1) and ∣−⟩\ket{-} otherwise.

  4. → H⊗I (−1)f(0)∣f(0)⊕f(1)⟩∣−⟩\xrightarrow{\,H\otimes\id\,} (-1)^{f(0)}\ket{f(0)\oplus f(1)}\ket{-}

    HH maps ∣±⟩\ket{\pm} to ∣0⟩,∣1⟩\ket{0},\ket{1}. Measuring the first qubit returns f(0)⊕f(1)f(0)\oplus f(1) with certainty.

ffTypeCircuit for UfU_fOutcome
f(x)=0f(x)=0constantnothing00
f(x)=1f(x)=1constantXX on the target00
f(x)=xf(x)=xbalancedCNOT11
f(x)=1⊕xf(x)=1\oplus xbalancedCNOT, then XX on the target11
The four one-bit functions. For f(x)=1f(x)=1 the target becomes X∣−⟩=−∣−⟩X\ket{-}=-\ket{-}: a global phase, invisible.

Deutsch–Jozsa

Now f:{0,1}n→{0,1}f:\{0,1\}^n\to\{0,1\} is promised to be constant or balanced. First a workhorse identity. For one qubit, H∣x⟩=12(∣0⟩+(−1)x∣1⟩)=12∑y∈{0,1}(−1)xy∣y⟩H\ket{x} = \tfrac{1}{\sqrt2}\big(\ket0+(-1)^x\ket1\big) = \tfrac{1}{\sqrt2}\sum_{y\in\{0,1\}}(-1)^{xy}\ket{y}. Taking the tensor product of nn copies:

H⊗n∣x⟩=12n∑y∈{0,1}n(−1)x⋅y∣y⟩,x⋅y=x1y1⊕⋯⊕xnyn.H^{\otimes n}\ket{x} = \frac{1}{\sqrt{2^n}}\sum_{y\in\{0,1\}^n}(-1)^{x\cdot y}\ket{y},\qquad x\cdot y = x_1y_1\oplus\cdots\oplus x_ny_n.
The Hadamard transform: the Fourier transform over Z2n\mathbb{Z}_2^n.
DerivationDeutsch–Jozsa, exactly
  1. ∣0n⟩∣1⟩→ H⊗(n+1) 12n∑x∣x⟩∣−⟩\ket{0^n}\ket{1}\xrightarrow{\,H^{\otimes(n+1)}\,}\frac{1}{\sqrt{2^n}}\sum_x\ket{x}\ket{-}

    Uniform superposition over all inputs, target in ∣−⟩\ket{-}.

  2. → Uf 12n∑x(−1)f(x)∣x⟩∣−⟩\xrightarrow{\,U_f\,}\frac{1}{\sqrt{2^n}}\sum_x(-1)^{f(x)}\ket{x}\ket{-}

    One query, phase kickback.

  3. → H⊗n ∑y[12n∑x(−1)f(x)+x⋅y]∣y⟩∣−⟩\xrightarrow{\,H^{\otimes n}\,}\sum_y\Big[\frac{1}{2^n}\sum_x(-1)^{f(x)+x\cdot y}\Big]\ket{y}\ket{-}

    Apply the Hadamard identity to each ∣x⟩\ket{x} and collect terms.

  4. amp(0n)=12n∑x(−1)f(x)={±1f constant0f balanced\text{amp}(0^n) = \frac{1}{2^n}\sum_x(-1)^{f(x)} = \begin{cases}\pm 1 & f\text{ constant}\\ 0 & f\text{ balanced}\end{cases}

    The amplitude of y=0ny=0^n is the average sign. Constant: the outcome is 0n0^n with certainty. Balanced: 0n0^n never occurs. One query, zero error.

Check your understanding

Run Deutsch–Jozsa with n=3n=3 on the balanced function f(x)=x1⊕x3f(x) = x_1\oplus x_3 (bits x1x2x3x_1x_2x_3 from left to right). What do you measure?

  1. 000000
  2. A uniformly random nonzero string
  3. 101101, with certainty
  4. 010010, with certainty
Show the answer

C. 101101, with certainty

Here f(x)=s⋅xf(x) = s\cdot x with s=101s=101, so the amplitude of yy is 2−3∑x(−1)(s⊕y)⋅x2^{-3}\sum_x(-1)^{(s\oplus y)\cdot x}. A nonzero character sums to zero, so this is 11 for y=sy=s and 00 otherwise: you measure 101101 with certainty.

Honest accounting

Is Deutsch–Jozsa an exponential speedup? Against exact classical algorithms, yes: 11 query versus 2n−1+12^{n-1}+1. Against randomized ones, no. Query kk independent uniformly random inputs and answer "constant" if all agree. Constant functions are always classified correctly, and a balanced one fools you only if all kk answers agree, which happens with probability 2⋅2−k2\cdot2^{-k}, whatever nn is.

Predict before you look

What is the smallest kk for which this randomized test errs with probability at most 1%1\%, for every nn?

Show the answer

8 queries

2⋅2−k=21−k≤0.012\cdot 2^{-k} = 2^{1-k}\le 0.01 needs k≥1+log⁡2100≈7.64k\ge 1+\log_2 100\approx 7.64, so k=8k=8 (error 2−7≈0.8%2^{-7}\approx 0.8\%; k=7k=7 gives 1.6%1.6\%). A constant, independent of nn.

ProblemDeterministicRandomized (error ≤13\le\frac13)Quantum
Deutsch (n=1n=1)222211 (exact)
Deutsch–Jozsa2n−1+12^{n-1}+1O(1)O(1)11 (exact)
Bernstein–Vaziraninnnn11 (exact)
SimonΩ(2n/2)\Omega(2^{n/2})Θ(2n/2)\Theta(2^{n/2})O(n)O(n)
Search (OR of NN bits)NNΘ(N)\Theta(N)Θ(N)\Theta(\sqrt N)
Query complexities. Simon's problem and search are developed in the next lessons.

Key takeaways

  • Uf∣x⟩∣y⟩=∣x⟩∣y⊕f(x)⟩U_f\ket{x}\ket{y}=\ket{x}\ket{y\oplus f(x)} is a self-inverse permutation; scratch garbage must be uncomputed so it cannot spoil interference.
  • With the target in ∣−⟩\ket{-}, one query implements the phase oracle ∣x⟩↦(−1)f(x)∣x⟩\ket{x}\mapsto(-1)^{f(x)}\ket{x}: the eigenvalue of Xf(x)X^{f(x)} is kicked back onto the input.
  • H⊗n∣x⟩=2−n/2∑y(−1)x⋅y∣y⟩H^{\otimes n}\ket{x}=2^{-n/2}\sum_y(-1)^{x\cdot y}\ket{y} turns sign patterns into measurable strings; in Deutsch–Jozsa the amplitude of 0n0^n is the average of (−1)f(x)(-1)^{f(x)}.
  • Deutsch–Jozsa beats exact classical algorithms exponentially but randomized ones only by a constant; Bernstein–Vazirani's 11-versus-nn gap survives randomness.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

What is Uf∣x⟩∣−⟩U_f\ket{x}\ket{-}, where Uf∣x⟩∣y⟩=∣x⟩∣y⊕f(x)⟩U_f\ket{x}\ket{y} = \ket{x}\ket{y\oplus f(x)}?

  1. ∣x⟩∣f(x)⟩\ket{x}\ket{f(x)}
  2. ∣x⟩∣−⟩\ket{x}\ket{-}, unchanged
  3. (−1)f(x)∣x⟩∣−⟩(-1)^{f(x)}\ket{x}\ket{-}
  4. (−1)f(x)∣x⟩∣+⟩(-1)^{f(x)}\ket{x}\ket{+}
Show the answer

C. (−1)f(x)∣x⟩∣−⟩(-1)^{f(x)}\ket{x}\ket{-}

∣−⟩\ket{-} is an eigenvector of XX with eigenvalue −1-1, and UfU_f applies Xf(x)X^{f(x)} to it. The target is unchanged and the eigenvalue (−1)f(x)(-1)^{f(x)} is kicked back onto ∣x⟩\ket{x}.

Question 2

In Deutsch–Jozsa with a balanced ff, what is the probability of measuring 0n0^n?

  1. Exactly 00
  2. 2−n2^{-n}
  3. 12\tfrac12
  4. It depends on which balanced function
Show the answer

A. Exactly 00

The amplitude of 0n0^n is 2−n∑x(−1)f(x)2^{-n}\sum_x(-1)^{f(x)}, and a balanced ff has equally many +1+1 and −1-1 terms. Destructive interference is exact.

Question 3

Run the circuit HH on the input, UfU_f with f(x)=xf(x)=x (a CNOT), then HH on the input, but with the target starting in ∣0⟩\ket{0} instead of ∣−⟩\ket{-}. What does measuring the input give?

  1. 11 with certainty, as before
  2. 00 with certainty
  3. The value f(0)f(0)
  4. 00 or 11 with probability 12\tfrac12 each
Show the answer

D. 00 or 11 with probability 12\tfrac12 each

With target ∣0⟩\ket{0} the CNOT produces 12(∣00⟩+∣11⟩)\tfrac{1}{\sqrt2}(\ket{00}+\ket{11}): f(x)f(x) is written down, not kicked back. The input is entangled with the target, its reduced state is maximally mixed, and the final HH yields a fair coin.

Question 4

Why must an oracle built from a classical circuit uncompute its scratch qubits?

  1. To save qubits; leftover garbage is otherwise harmless
  2. Garbage that depends on xx entangles with the input register and destroys the interference between different xx
  3. Unitary circuits cannot produce garbage in the first place
  4. Uncomputing is what makes UfU_f Hermitian
Show the answer

B. Garbage that depends on xx entangles with the input register and destroys the interference between different xx

With garbage the state is ∑x(−1)f(x)∣x⟩∣g(x)⟩\sum_x(-1)^{f(x)}\ket{x}\ket{g(x)}. Branches with different g(x)g(x) are orthogonal and can no longer interfere, so the final Hadamards fail. Uncomputation returns the scratch to ∣0⋯0⟩\ket{0\cdots0}, a common factor.

Question 5

Bernstein–Vazirani: f(x)=s⋅x mod 2f(x) = s\cdot x \bmod 2, find ss. Which statement is correct?

  1. Quantum needs nn queries, classical 2n2^n
  2. Quantum and classical both need nn
  3. Quantum needs 11 query, randomized classical about n/2n/2
  4. Quantum needs 11 query; classical needs nn, even with randomness
Show the answer

D. Quantum needs 11 query; classical needs nn, even with randomness

The Deutsch–Jozsa circuit maps ∑x(−1)s⋅x∣x⟩\sum_x(-1)^{s\cdot x}\ket{x} to ∣s⟩\ket{s} exactly. Classically, each query returns a single bit, so qq queries can distinguish at most 2q2^q of the 2n2^n possible strings ss, which forces q≥nq\ge n for success probability 2/32/3.

Go deeper

Further reading

  • D. Deutsch, "Quantum theory, the Church–Turing principle and the universal quantum computer", Proc. R. Soc. Lond. A 400, 97–117 (1985).
  • D. Deutsch & R. Jozsa, "Rapid solution of problems by quantum computation", Proc. R. Soc. Lond. A 439, 553–558 (1992).
  • R. Cleve, A. Ekert, C. Macchiavello & M. Mosca, "Quantum algorithms revisited", Proc. R. Soc. Lond. A 454, 339–354 (1998).
  • M. A. Nielsen & I. L. Chuang, Quantum Computation and Quantum Information, §1.4 (Cambridge, 10th anniv. ed., 2010).