Lesson 12: The Deutsch Algorithm¶
12.1 Learning Outcomes¶
By the end of this hour a student will be able to:
- State Deutsch's problem precisely and give the classical query lower bound.
- Derive the Deutsch algorithm line by line and prove it is deterministic.
- Build the oracle circuit for each of the four possible functions \(f:\{0,1\}\to\{0,1\}\).
- Explain exactly where the speed-up comes from — and why it is a global property being computed.
- Analyse the effect of noise on the algorithm's success probability.
12.2 Deutsch's Problem¶
Setup. A black box computes an unknown \(f:\{0,1\}\to\{0,1\}\). There are exactly four such functions:
| Name | \(f(0)\) | \(f(1)\) | Type | \(f(0)\oplus f(1)\) |
|---|---|---|---|---|
| \(f_0\) (constant-0) | 0 | 0 | constant | 0 |
| \(f_1\) (constant-1) | 1 | 1 | constant | 0 |
| \(f_2\) (identity) | 0 | 1 | balanced | 1 |
| \(f_3\) (negation) | 1 | 0 | balanced | 1 |
The problem. Decide whether \(f\) is constant (\(f(0) = f(1)\)) or balanced (\(f(0)\ne f(1)\)), using as few queries as possible.
Equivalently: compute the single bit
Classical lower bound. You must learn both \(f(0)\) and \(f(1)\). Knowing \(f(0)=0\) alone is consistent with both \(f_0\) (constant) and \(f_2\) (balanced). Therefore 2 queries are necessary and sufficient classically.
Quantum result (Deutsch, 1985). One query suffices, with certainty.
Read the problem statement carefully. We are not asked for \(f(0)\) or for \(f(1)\). We are asked for a global relational property of the function. Quantum algorithms are good at global properties precisely because a superposition can touch all inputs at once and interference can extract a joint feature — while measurement forbids extracting all the individual values.
12.3 The Algorithm¶
Circuit¶
q0 (input) : --[H]--------.---[H]---[M]--
|
[ U_f ]
|
q1 (ancilla) : --[X]--[H]---'---------------
Step-by-step derivation¶
Step 0 — initialise.
Step 1 — prepare the ancilla in \(|1\rangle\) and apply Hadamards to both.
Step 2 — one oracle query. By phase kick-back (L11):
Factor out the global phase \((-1)^{f(0)}\), which is unobservable:
This is the crucial line. The relative phase now encodes exactly the bit we want. Note that \((-1)^{f(1)}/(-1)^{f(0)} = (-1)^{f(1)-f(0)} = (-1)^{f(0)\oplus f(1)}\) because the exponent matters only mod 2.
Writing \(b = f(0)\oplus f(1)\):
Step 3 — interfere. Apply \(H\) to the input register. Since \(H|+\rangle = |0\rangle\) and \(H|-\rangle = |1\rangle\):
Step 4 — measure the input register.
The answer is deterministic — probability 1, not \(\frac23\) or "with high probability". One query, no error.
Compact algebraic proof¶
Using \(H|x\rangle = \frac{1}{\sqrt2}\sum_y(-1)^{xy}|y\rangle\), the amplitude of \(|0\rangle\) after Step 3 is
Likewise the amplitude of \(|1\rangle\) is \(\frac12[(-1)^{f(0)} - (-1)^{f(1)}]\), which is \(0\) for constant and \(\pm1\) for balanced. Constructive interference on \(|0\rangle\) for constant functions; destructive interference for balanced ones. That single sentence is the algorithm.
12.4 Building the Four Oracles¶
\(U_f|x\rangle|y\rangle = |x\rangle|y\oplus f(x)\rangle\):
| Function | Circuit for \(U_f\) | Reason |
|---|---|---|
| \(f_0(x)=0\) | identity (no gates) | \(y\oplus0 = y\) |
| \(f_1(x)=1\) | \(X\) on the ancilla | \(y\oplus1 = \bar y\) |
| \(f_2(x)=x\) | CNOT (control \(q_0\), target \(q_1\)) | \(y\oplus x\) |
| \(f_3(x)=\bar x\) | CNOT then \(X\) on the ancilla | \(y\oplus x\oplus 1\) |
Pedagogical honesty. To build the oracle you must know \(f\) — so in a classroom the demonstration is somewhat circular. The point is the query count: given the box, the quantum algorithm opens it once. In real applications (\(f\) = a hash function, a SAT instance, a database predicate) the oracle is a large but efficiently constructible circuit whose global properties are unknown.
12.5 Where Exactly Is the Speed-Up?¶
Three ingredients, none sufficient alone:
- Superposition puts both inputs into the query simultaneously.
- Phase kick-back converts \(f\)'s values into relative phases without entangling any record of \(x\).
- Interference (the final \(H\)) converts the phase difference — a global property — into a deterministic measurement outcome.
What the algorithm does NOT do. It does not learn \(f(0)\) or \(f(1)\). After the run you know \(f(0)\oplus f(1)\) and nothing more; the individual values are provably inaccessible from one query. The trade is: one global bit instead of two local bits. That trade is available quantumly and not classically, and it is the seed of every result in Unit II.
12.6 Solved Problems¶
Problem 1 — Full trace for f₂(x) = x¶
Run the Deutsch algorithm with \(f_2(x) = x\) (oracle = CNOT) and verify the output.
Solution.
Apply CNOT (flip \(q_1\) when \(q_0 = 1\)): the last two terms swap targets.
Apply \(H\) to \(q_0\): \(H|-\rangle = |1\rangle\).
Measurement of \(q_0\) gives 1 ⟹ balanced ✓ (\(f_2\) is indeed balanced).
Cross-check with the phase formula: \(b = f(0)\oplus f(1) = 0\oplus1 = 1\) ✓.
Problem 2 — Full trace for f₁(x) = 1¶
Run the algorithm with the constant-1 oracle (\(X\) on the ancilla).
Solution.
Apply \(H\) to \(q_0\): \(H|+\rangle = |0\rangle\), giving \(-|0\rangle|-\rangle\).
Measurement gives 0 ⟹ constant ✓.
Note. The \(-1\) is a global phase (it multiplies both branches equally) and is invisible. This is exactly why constant-0 and constant-1 give the same answer — the algorithm reports constant without distinguishing which constant. That information is genuinely unavailable from one query.
Problem 3 — Direct verification via amplitudes¶
Use the amplitude formula \(\langle 0|\psi_3\rangle = \frac12[(-1)^{f(0)}+(-1)^{f(1)}]\) to fill in the outcome for all four functions.
Solution.
| \(f\) | \((-1)^{f(0)}\) | \((-1)^{f(1)}\) | \(\langle 0\rvert\psi_3\rangle\) | \(\langle 1\rvert\psi_3\rangle\) | \(\Pr[0]\) | Verdict |
|---|---|---|---|---|---|---|
| \(f_0\) | \(+1\) | \(+1\) | \(+1\) | \(0\) | 1 | constant |
| \(f_1\) | \(-1\) | \(-1\) | \(-1\) | \(0\) | 1 | constant |
| \(f_2\) | \(+1\) | \(-1\) | \(0\) | \(+1\) | 0 | balanced |
| \(f_3\) | \(-1\) | \(+1\) | \(0\) | \(-1\) | 0 | balanced |
All four cases are deterministic, and \(|\langle0|\psi_3\rangle|^2 + |\langle1|\psi_3\rangle|^2 = 1\) in every row ✓. The sign of the surviving amplitude carries no information (global phase), which correctly reflects that we cannot distinguish \(f_0\) from \(f_1\).
Problem 4 — The algorithm under noise¶
Suppose the input qubit suffers a phase-flip error \(Z\) with probability \(p\) immediately after the oracle. Find the probability of a correct answer.
Solution. After the oracle the input register is \(|+\rangle\) (constant) or \(|-\rangle\) (balanced).
The error \(Z\) maps \(|+\rangle \leftrightarrow |-\rangle\). So with probability \(p\) the state is flipped to the other case.
- With probability \(1-p\): no error, final measurement gives the correct bit.
- With probability \(p\): state flipped, final \(H\) produces the wrong answer with certainty.
Practical consequence. Unlike the noiseless ideal, on real hardware the algorithm must be run
many times and the majority outcome taken. For \(p = 0.05\), running \(N\) times and taking the majority
gives error \(\approx \binom{N}{\lceil N/2\rceil}p^{N/2}\), which for \(N=5\) is under \(0.2\%\). This is
why every textbook demonstration on IBM hardware reports a histogram like {'0': 950, '1': 74}
rather than a clean single bar.
Note the asymmetry: a bit-flip (\(X\)) error on the input register after the oracle would map \(|+\rangle \to |+\rangle\) and \(|-\rangle\to-|-\rangle\) — no effect at all. The algorithm is immune to \(X\) errors at that point but maximally sensitive to \(Z\) errors, because its answer is stored in a phase.
Problem 5 — A three-query classical strategy is not needed; a one-query classical strategy fails¶
Prove rigorously that no classical algorithm can solve Deutsch's problem with one query, even with randomisation and allowing error probability \(< 1/2\).
Solution. A one-query deterministic classical algorithm queries some \(x\in\{0,1\}\) and outputs a verdict based on \(f(x)\).
Suppose it queries \(x = 0\) and sees \(f(0) = 0\). The two functions consistent with this observation are:
- \(f_0\): \(f(0)=0, f(1)=0\) — constant
- \(f_2\): \(f(0)=0, f(1)=1\) — balanced
The algorithm's view is identical in both cases, so whatever it outputs is wrong for one of them. The same argument applies to \(f(0)=1\) (functions \(f_1\) and \(f_3\)) and symmetrically to querying \(x=1\).
Randomised case. Let the algorithm query a random \(x\) and output a possibly random verdict. Consider the input distribution: pick uniformly from \(\{f_0,f_1,f_2,f_3\}\). Whatever \(x\) is queried and whatever value is returned, the posterior is exactly 50/50 between constant and balanced (each observed value \(f(x)=v\) is consistent with one constant and one balanced function, each with prior \(\frac14\)). Hence
for any one-query randomised classical algorithm — no better than guessing. \(\blacksquare\)
Contrast. The quantum algorithm achieves \(\Pr[\text{correct}] = 1\) with one query. This is a proved, unconditional separation — it does not rest on any unproven complexity assumption.
12.7 Practice Problems¶
- Trace the algorithm for \(f_3(x) = \bar x\) and confirm the output is 1.
- What happens if the ancilla is initialised in \(|0\rangle\) instead of \(|1\rangle\)? Show the measurement becomes uniformly random.
- Design the oracle circuit for \(f(x) = 1\oplus x\) using exactly two gates.
- If the ancilla suffers a \(Z\) error after the oracle, does the answer change? Justify. [Ans: no — \(Z|-\rangle = |+\rangle\), but the ancilla is never measured and by then it is unentangled]
- Show that the Deutsch algorithm can be viewed as the \(n=1\) case of Deutsch–Jozsa.
- With \(p = 0.1\) per run, how many runs give a majority-vote error below \(1\%\)? [Ans: 5 runs → ≈0.86%]
12.8 Summary¶
- Deutsch's problem: decide whether \(f:\{0,1\}\to\{0,1\}\) is constant or balanced — equivalently compute \(f(0)\oplus f(1)\).
- Classical: 2 queries necessary; one query gives no better than a coin flip, even with randomisation.
- Quantum: 1 query, deterministically correct.
- Mechanism: \(H\) creates superposition → phase kick-back writes \((-1)^{f(x)}\) → final \(H\) makes the two branches interfere → constructive on \(|0\rangle\) iff \(f\) is constant.
- The algorithm computes a global relational property, not the individual function values — that is the shape of every quantum advantage in this unit.
- The answer lives in a phase, making the circuit immune to \(X\) errors and maximally sensitive to \(Z\) errors on the input qubit.
Next lesson: L13 — The Deutsch–Jozsa algorithm (\(n\)-bit generalisation, exponential separation).
Practise now: unit2-algorithms-lab.html → Deutsch tab: choose one of the four functions,
step through the circuit, and watch the amplitude bars interfere.