110
Part Three · B · Algorithms

Oracle model and query complexity: Deutsch–Jozsa, Bernstein–Vazirani

You are handed a sealed box computing a function ff on nn-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 2n−1+12^{n-1} + 1 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 Uf∣x⟩∣y⟩=∣x⟩∣y⊕f(x)⟩U_f|x\rangle|y\rangle = |x\rangle|y\oplus f(x)\rangle (Chapter 94). Put the output qubit in ∣−⟩=(∣0⟩−∣1⟩)/2|-\rangle = (|0\rangle - |1\rangle)/\sqrt2: flipping it multiplies it by −1, so

Uf∣x⟩∣−⟩=(−1)f(x)∣x⟩∣−⟩U_f|x\rangle|-\rangle = (-1)^{f(x)}|x\rangle|-\rangle

The function value has been kicked back into a phase on the input. Apply this to a superposition of all inputs and every xx gets its own sign, in a single query. That is the engine of every algorithm in this part. Established

Deutsch–Jozsa

Hadamards on all nn qubits make the uniform superposition; one oracle call adds the signs; Hadamards again; measure. The amplitude of ∣0⋯0⟩|0\cdots0\rangle is the average of (−1)f(x)(-1)^{f(x)}: ±1 if ff 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 2n−1+12^{n-1} + 1 queries in the worst case; a randomized one that checks kk random inputs is wrong with probability at most 21−k2^{1-k}. 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 f(x)=s⋅x mod 2f(x) = s\cdot x \bmod 2 for a hidden string ss. Classically, each query reveals at most one bit of ss, so you need nn queries, even with randomness. The same circuit, one query, outputs ss exactly, because the Hadamard transform of (−1)s⋅x(-1)^{s\cdot x} is a single spike at ss. 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.

What does phase kickback do?tap
Turns a function value f(x) into a sign (−1)^f(x) on the input register.
Does Deutsch–Jozsa beat randomized classical algorithms exponentially?tap
No; a few random queries succeed with tiny error.
How many classical queries does Bernstein–Vazirani need?tap
n, one per bit of s; the quantum algorithm needs one.

And one to work out. For n=10n = 10 input bits, how many queries does a deterministic classical algorithm need in the worst case for Deutsch–Jozsa?

queries =

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).

Next · Chapter 111
Simon's algorithm and the hidden subgroup problem

The first exponential quantum separation. It is what inspired Shor.

Turn the page