The first quantum speedup — one query instead of two
Can you determine a global property of a function (constant or balanced?) by evaluating it only once, when classically you need two evaluations?
Deutsch’s algorithm (1985, refined by Deutsch and Jozsa in 1992) was the first proof that a quantum computer can solve a specific problem strictly faster than any classical computer. The problem it solves is simple: given a black-box function f(x) on one bit, decide whether f is constant (f(0)=f(1)) or balanced (f(0)f(1)). Classically, you must query f twice. Deutsch’s algorithm does it with one query. The speedup is modest, but the principle — encoding the answer in phase and extracting it through interference — is the blueprint for every quantum algorithm that followed.
The trick has three parts. First, prepare a helper qubit (called the ancilla) in |−⟩ so that the oracle kicks its answer into phase rather than flipping a visible bit. Second, put the input in superposition so both f(0) and f(1) are queried simultaneously — but the result is encoded in relative phase, not in two separate answers. Third, apply Hadamard to convert the phase difference into a definite measurement outcome: means constant, means balanced.
The oracle does not return f(x) as a bit you read. It encodes f(x) as a phase (±1) via kickback. Interference then converts the global property (constant vs balanced) into a single deterministic bit.
Apply X then H to qubit 1. This creates |−⟩ = (−, the eigenstate that enables phase kickback.
Apply H to qubit 0. Now the input queries both x=0 and x=1 simultaneously.
The oracle applies f(x) via phase kickback. Each branch picks up (−1)^{f(x)}. If f is balanced, the two branches get opposite signs. If f is constant, both branches get the same sign.
Hadamard converts the phase pattern into a definite computational basis state. Same phases → (constant). Opposite phases → (balanced).
Read qubit 0. The result is f(0)⊕f(1): 0 means constant, 1 means balanced. One query determined a global property.
Measuring on qubit 0 means f is constant (f(0)=f(1)). Measuring means f is balanced (f(0)f(1)). The result is deterministic, not probabilistic.
The oracle is a black-box gate that encodes the function. It maps |x,y⟩ to |x, y XOR f(x)⟩, where XOR means the output bit flips if f(x)=1 and stays the same if f(x)=0. With the ancilla (helper qubit) in |−⟩, this XOR action converts into a phase via kickback: |−⟩ becomes (−1)^{f(x)}|−⟩. When the input is in (superposition of both x=0 and x=1), both branches pick up their respective phases. If f is constant, both phases are the same, leaving . If f is balanced, the phases are opposite, giving |−⟩. A final Hadamard maps to (constant) or |−⟩ to (balanced). One query gives a deterministic answer.
Classically, you must evaluate f(0) and f(1) separately and compare. Two queries are always required, regardless of strategy.
Quantumly, superposition lets you evaluate both inputs at once, and interference converts the global property (same or different) into a single measurable bit. One query suffices.
It is tempting to think the algorithm computes f(0) and f(1) separately and then compares them. That is not what happens. The algorithm never learns the individual values of f(0) or f(1). It determines the global property (constant vs balanced) directly through interference, without extracting either value on its own.
Deutsch-Jozsa generalizes this to n-bit functions: one query vs 2^{n−1}+1 classical queries. The same phase-kickback-then-interference pattern scales up to Bernstein-Vazirani, Simon’s algorithm, and eventually Shor’s factoring algorithm.
In Deutsch’s algorithm, the oracle is implemented as a CNOT. What type of function does this CNOT oracle represent?