Quantum Parallelism & Deutsch-Jozsa
The first algorithm to prove a quantum computer can beat a classical one
By the end of this topic you'll be able to
Setting an n-qubit register to |0⟩ and applying a Hadamard operator to every qubit puts the register into an equal superposition of every representable n-bit number, from Binney and Skinner's Ch.6.2 result generalized to n qubits. Evaluating a function f on this superposed register, using the control-and-data-register trick from that same chapter, computes f on all 2ⁿ inputs in a single pass — what is generally called quantum parallelism.
The catch, which trips up almost everyone meeting this idea for the first time, is that measuring the register afterward returns only one of those 2ⁿ results, chosen at random; naive measurement throws away nearly everything that parallel evaluation just computed. A genuine quantum algorithm's cleverness lies entirely in arranging interference so that the one answer actually wanted is the one left standing after measurement, while the rest cancel.
Binney and Skinner's Box 6.2 works through exactly this pattern for the problem posed by Deutsch: given a function f(x) taking an n-bit argument and returning 0 or 1, promised to be either constant (the same output on every input) or balanced (0 on exactly half the inputs, 1 on the rest), determine which, using the black-box function as few times as possible.
Classically this can demand checking more than half of all 2ⁿ possible inputs in the worst case before the answer is certain — check that many 0-outputs, and either a 1 has turned up (balanced) or over half the inputs are now confirmed 0 (constant).
The quantum recipe needs only a single query. Prepare the control register in an equal superposition and the data register in (|0⟩−|1⟩)/√2, evaluate f once, and the phase-kickback trick converts the function's output into a sign, (−1)^{f(x)}, attached to each term of the superposition rather than a value stored in the data register.
Applying Hadamards to the control register a second time completes the calculation: if f is constant, every term picked up the identical overall phase, and the Hadamards return the register exactly to |0⟩. If f is balanced, Binney and Skinner show the phases differ across inputs in a way that guarantees the control register can never be measured as all zeros.
Measuring the control register therefore settles the question outright — zero if constant, anything else if balanced — using exactly one query to f, with zero probability of error, an exponential improvement over the best possible classical strategy.
Deutsch's original problem is admittedly a somewhat artificial one, not something anyone would need solved in practice. Its lasting value is pedagogical: 'superpose, query once, interfere, measure' is the cleanest possible demonstration of a pattern that reappears, in far more useful forms, in essentially every quantum algorithm covered from here on.
Try It Yourself
For n=2 (a 2-bit input), how many queries would a deterministic classical algorithm need in the worst case to decide constant vs. balanced, using the 2ⁿ⁻¹+1 formula? Compare to the single quantum query.
- 1Plug n=2 into the classical worst-case formula: 2ⁿ⁻¹+1 = 2¹+1 = 3 queries.
- 2There are 2²=4 possible inputs (00,01,10,11). A deterministic classical algorithm could get unlucky and see the same output on the first 2 queries (both 0s, say) without yet being able to rule out either possibility — a third query is what actually settles it, matching the formula.
- 3The quantum algorithm needs exactly 1 query, regardless of n — so at n=2 the gap is 3 vs 1, and it only widens as n grows: at n=10, classical needs 2⁹+1=513 queries, quantum still needs just 1.
Classical needs 3 queries in the worst case for n=2 (and 513 for n=10); the quantum algorithm needs exactly 1 query regardless of n — the gap grows exponentially with the input size.
Reference
| Classical worst case | Deterministic classical algorithm to decide constant vs. balanced | |
| Quantum queries | Deutsch-Jozsa algorithm, deterministic (zero error) | |
| Oracle | Phase-kickback implementation of the black-box function |
Quick Check
What does 'quantum parallelism' actually give you, before any interference is used?
How many queries does the quantum Deutsch-Jozsa algorithm need to the black-box function f?