Lesson 13: The Deutsch–Jozsa Algorithm¶
13.1 Learning Outcomes¶
By the end of this hour a student will be able to:
- State the Deutsch–Jozsa promise problem and the classical deterministic and randomised query bounds.
- Derive the algorithm in full using the \(n\)-qubit Hadamard identity.
- Prove that \(\Pr[\text{all zeros}] = 1\) for constant \(f\) and \(0\) for balanced \(f\).
- Explain the exponential separation and its important caveat (bounded-error randomised classical algorithms).
- Construct oracles for specific \(n\)-bit functions.
13.2 The Problem¶
Promise problem. Given an oracle for \(f:\{0,1\}^n \to \{0,1\}\) with the promise that \(f\) is either
- constant — \(f(x)\) is the same for all \(2^n\) inputs, or
- balanced — \(f(x) = 0\) for exactly \(2^{n-1}\) inputs and \(1\) for the other \(2^{n-1}\),
decide which.
The word "promise" matters. Functions that are neither constant nor balanced (e.g. \(f\) equal to 1 on exactly one input) are excluded; the algorithm's behaviour on them is undefined. Promise problems are how most quantum speed-ups are stated.
Classical query complexity¶
Deterministic (worst case). Query distinct inputs one at a time.
- If two queries ever return different values ⟹ definitely balanced. Stop.
- If the first \(2^{n-1}\) queries all return the same value, the function could still be balanced (all the 1s hiding in the untouched half). One more query settles it.
For \(n = 50\) that is \(563{,}949{,}953{,}421{,}313\) queries — over \(5\times10^{14}\).
Randomised (bounded error). Query \(k\) random distinct inputs. If \(f\) is balanced, the chance that all \(k\) agree is about \(2^{-(k-1)}\). Taking \(k = 21\) gives error \(< 10^{-6}\).
This caveat must be stated honestly. Deutsch–Jozsa gives an exponential separation against deterministic exact classical computation, but only a constant-factor separation against randomised classical computation. The first problem with an exponential separation even against randomised classical algorithms is Simon's problem (L15).
Quantum query complexity¶
13.3 The Algorithm¶
Circuit¶
q0 ... q(n-1) : --[H]^n-------.------[H]^n----[M]^n--
|
[ U_f ]
|
q_ancilla : --[X]--[H]----'--------------------
Derivation¶
Step 0.
Step 1 — Hadamards everywhere.
Step 2 — one oracle query (phase kick-back).
Step 3 — final Hadamards. Use the identity from L07:
Therefore
Step 4 — measure the input register. The amplitude of the all-zeros string \(y = 0^n\) is
The two cases¶
Case A: \(f\) constant. All \(2^n\) terms equal \((-1)^{c}\) where \(c = f(x)\) is the constant value:
Since the total probability is 1, every other amplitude is exactly zero. Perfect constructive interference on \(|0^n\rangle\), perfect destructive interference everywhere else.
Case B: \(f\) balanced. Exactly half the terms are \(+1\) and half are \(-1\):
Complete destructive interference on the all-zeros outcome.
The decision rule¶
Deterministic, one query, no error. \(\blacksquare\)
13.4 Constructing Oracles¶
| \(f\) | Type | Circuit for \(U_f\) |
|---|---|---|
| \(f(x) = 0\) | constant | no gates |
| \(f(x)=1\) | constant | \(X\) on the ancilla |
| \(f(x) = x_k\) | balanced | CNOT from \(q_k\) to the ancilla |
| \(f(x)=x_1\oplus x_2\oplus\cdots\oplus x_n\) (parity) | balanced (\(n\ge1\)) | CNOT from every input qubit to the ancilla |
| \(f(x) = a\cdot x\) for \(a\ne 0\) | balanced | CNOT from each \(q_j\) with \(a_j = 1\) |
| \(f(x)= x_1 \wedge x_2\) | neither | Toffoli — violates the promise |
Useful fact. For \(f(x) = a\cdot x\) (a linear function), Deutsch–Jozsa outputs the string \(a\) itself — not merely "balanced". Proving this is the Bernstein–Vazirani algorithm (L14).
13.5 Solved Problems¶
Problem 1 — Complete trace for n = 2, f(x) = x₁ ⊕ x₂¶
Run Deutsch–Jozsa on the 2-bit parity function and identify the measured string.
Solution. Truth table: \(f(00)=0\), \(f(01)=1\), \(f(10)=1\), \(f(11)=0\) — two 0s and two 1s, so balanced ✓.
After Step 2:
Factorise:
After Step 3: \(H|-\rangle = |1\rangle\), so
Measurement gives \(11\) with probability 1. Not \(00\) ⟹ balanced ✓.
Note the bonus: the output \(11\) is exactly the string \(a = 11\) defining \(f(x) = a\cdot x\).
Problem 2 — Complete trace for n = 3, f(x) = x₂¶
Run the algorithm for \(f(x_1x_2x_3) = x_2\) (oracle = CNOT from \(q_2\) to the ancilla).
Solution. \(f\) is balanced: it equals 0 on the four strings with \(x_2=0\) and 1 on the four with \(x_2 = 1\) ✓.
After Step 2:
The phase depends only on \(x_2\), so it attaches entirely to the middle qubit.
After Step 3: \(H|+\rangle = |0\rangle\), \(H|-\rangle=|1\rangle\):
Measurement gives \(010\) — again exactly the mask \(a\) with a 1 in position 2. Non-zero ⟹ balanced ✓.
Problem 3 — Query counts and the honest comparison¶
For \(n = 40\): (a) worst-case deterministic classical queries; (b) randomised classical queries for error \(< 10^{-9}\); (c) quantum queries. If a classical query takes 1 ns, how long is (a)?
Solution.
(a) \(2^{39} + 1 = 549{,}755{,}813{,}889 \approx 5.5\times10^{11}\) queries.
Time: \(5.5\times10^{11}\times10^{-9}\ \mathrm{s} = 550\ \mathrm{s} \approx \mathbf{9.2\ minutes}\).
(b) With \(k\) random distinct queries, a balanced \(f\) produces all-equal answers with probability about \(2^{-(k-1)}\). Require
(c) 1 query.
Discussion. The honest comparison is 1 vs 31, not 1 vs \(5.5\times10^{11}\). Deutsch–Jozsa's exponential separation is against exact deterministic classical computation. It is nevertheless a landmark result: it was the first proof that quantum computers can be exponentially faster at something, and it introduced the superpose–kickback–interfere template that Simon and Shor turned into genuine, randomised-classical-beating speed-ups.
Problem 4 — Amplitude of a general outcome¶
For balanced \(f\) with \(n=2\) and truth table \(f(00)=0, f(01)=0, f(10)=1, f(11)=1\), compute the amplitude of every basis state after Step 3.
Solution. Note \(f(x) = x_1\), so we expect the output \(10\).
Phases \((-1)^{f(x)}\): \((+1, +1, -1, -1)\) for \(x = 00,01,10,11\).
For \(y = 00\): \(x\cdot y = 0\) always.
For \(y = 01\): \(x\cdot y = x_2\), giving signs \((+,-,+,-)\).
For \(y = 10\): \(x\cdot y = x_1\), giving signs \((+,+,-,-)\).
For \(y = 11\): \(x\cdot y = x_1\oplus x_2\), signs \((+,-,-,+)\).
Summary: \(A_{10} = 1\), all others 0. \(\sum|A_y|^2 = 1\) ✓. Measurement returns \(10\) deterministically ⟹ balanced ✓.
Problem 5 — A function violating the promise¶
Apply the algorithm to \(f:\{0,1\}^2\to\{0,1\}\) with \(f(11) = 1\) and \(f = 0\) elsewhere (neither constant nor balanced). Compute the measurement distribution and interpret.
Solution. Phases: \((+1, +1, +1, -1)\) for \(x = 00,01,10,11\).
(signs for \(y=01\): \((+,-,+,-)\), applied to phases \((+,+,+,-)\) gives \(+1,-1,+1,+1\).)
Distribution: each outcome with probability \(\left(\frac12\right)^2 = \frac14\).
Interpretation. With probability \(\frac14\) we measure \(00\) and wrongly conclude "constant". The algorithm gives no guarantee outside its promise — which is the definition of a promise problem.
This is a genuinely useful observation. The amplitude \(A_{0^n} = \frac{1}{2^n}\sum_x(-1)^{f(x)}\) is in general a bias measure: it equals \(1 - 2\cdot(\text{fraction of inputs where } f = 1)\). Here \(1 - 2\cdot\frac14 = \frac12\) ✓. So the algorithm actually estimates the bias of \(f\); the constant/balanced decision is the special case where the bias is \(\pm1\) or \(0\). This observation generalises into the amplitude estimation primitive used in Unit III.
13.6 Practice Problems¶
- Trace the algorithm for \(n=2\), \(f(x) = 1\) (constant). [Ans: measures \(00\)]
- Give the oracle circuit for \(f(x_1x_2x_3) = x_1\oplus x_3\), and predict the measured string. [Ans: 3 CNOTs from \(q_1,q_3\); measures \(101\)]
- For \(n=10\), how many worst-case deterministic classical queries? [Ans: 513]
- Show that if \(f\) is balanced then \(\sum_x(-1)^{f(x)} = 0\) regardless of which half is 1.
- Prove that Deutsch–Jozsa with \(n=1\) reduces exactly to the Deutsch algorithm.
- A function has \(f(x)=1\) on \(\frac38\) of inputs. What is \(\Pr[0^n]\)? [Ans: \((1-2\cdot\frac38)^2 = \frac{1}{16}\)]
- Explain why Deutsch–Jozsa's separation is often called "unfair" and which algorithm repairs the unfairness.
13.7 Summary¶
- Promise problem: \(f\) is constant or balanced; decide which.
- Classical: \(2^{n-1}+1\) deterministic worst-case queries, but only \(O(1)\) randomised queries — state this caveat.
- Quantum: 1 query, deterministic.
- Derivation: \(H^{\otimes n}\) → phase kick-back → \(H^{\otimes n}\); the amplitude of \(0^n\) is \(\frac{1}{2^n}\sum_x(-1)^{f(x)}\), which is \(\pm1\) for constant and \(0\) for balanced.
- Decision rule: all zeros ⟹ constant; anything else ⟹ balanced.
- Outside the promise the algorithm still computes the bias of \(f\) — a fact that generalises to amplitude estimation.
Next lesson: L14 — The Bernstein–Vazirani algorithm.
Practise now: unit2-algorithms-lab.html → Deutsch–Jozsa tab: choose \(n\) up to 5, pick or
randomise the oracle, and watch the amplitude bars collapse onto \(0^n\) or spread away from it.