Oracle model and query complexity: Deutsch–Jozsa, Bernstein–Vazirani
You are handed a sealed box computing a function on -bit strings, promised to be either constant (same output for every input) or balanced (0 for exactly half the inputs). To be certain which, a classical computer may need to ask questions. A quantum computer needs one. That is the Deutsch–Jozsa algorithm, the first clear quantum speedup. It is also a cautionary tale: a classical computer that is allowed to guess, and be wrong one time in a million, needs only about twenty questions. Separations in this oracle model are real, but you must ask exactly what they are separating.
On the plate: an oracle box and a quantum circuit that queries it once.
Oracles and phase kickback
A classical function is made reversible as (Chapter 94). Put the output qubit in : flipping it multiplies it by −1, so
The function value has been kicked back into a phase on the input. Apply this to a superposition of all inputs and every gets its own sign, in a single query. That is the engine of every algorithm in this part. Established
Deutsch–Jozsa
Hadamards on all qubits make the uniform superposition; one oracle call adds the signs; Hadamards again; measure. The amplitude of is the average of : ±1 if is constant, exactly 0 if balanced. Choose an oracle: , , , . The plate runs the circuit with three input qubits.
The honest comparison: a deterministic classical algorithm needs queries in the worst case; a randomized one that checks random inputs is wrong with probability at most . So the exponential gap is only against exact classical algorithms. David Deutsch posed the one-bit version in 1985; Deutsch and Richard Jozsa generalized it in 1992. Established
Bernstein–Vazirani
Now for a hidden string . Classically, each query reveals at most one bit of , so you need queries, even with randomness. The same circuit, one query, outputs exactly, because the Hadamard transform of is a single spike at . Hide 5 (as three bits) and run it. Ethan Bernstein and Umesh Vazirani introduced it in 1993; their recursive version gave the first super-polynomial oracle separation against randomized classical computers.
What oracle separations mean
Query complexity counts calls to a black box and ignores everything else. It allows clean, provable separations, which are otherwise rare in complexity theory. But real problems don’t come in black boxes: someone must build the oracle as a circuit, and if the function is simple enough to write down, a classical computer may exploit its structure directly. Oracle separations show what quantum mechanics can do; whether a real problem benefits is a separate question, asked again in every chapter that follows.
What you now have
Reversible oracles and phase kickback, the Deutsch–Jozsa algorithm and its honest comparison with randomized classical methods, the Bernstein–Vazirani algorithm, and what query separations do and do not prove.
· · ·
Three questions to carry with you.
And one to work out. For input bits, how many queries does a deterministic classical algorithm need in the worst case for Deutsch–Jozsa?
Sources: D. Deutsch, Proc. R. Soc. A 400, 97 (1985). D. Deutsch and R. Jozsa, Proc. R. Soc. A 439, 553 (1992). R. Cleve, A. Ekert, C. Macchiavello and M. Mosca, Proc. R. Soc. A 454, 339 (1998). E. Bernstein and U. Vazirani, SIAM J. Comput. 26, 1411 (1997). R. de Wolf, Quantum Computing: Lecture Notes. Checked by code: Bernstein–Vazirani recovers every s for n = 4 in one query; Deutsch–Jozsa outputs 000 with probability 1 for constant and 0 for balanced oracles (Book.QSim).