Deutsch–Jozsa: The First Quantum Speedup

The circuit is 3 input qubits plus one ancilla. You choose the oracle — a black box that computes some f you are not allowed to look inside — and then step the circuit: prepare the ancilla, spread the input register over all 8 inputs, call f once, and interfere.

Watch two things. At step 4, the bar heights do not change at all: the oracle rearranges signs, and a measurement taken there is uniform noise. At step 5, all of that amplitude either piles onto |000⟩ or vanishes from it — there is no in-between.

The trick is the ancilla. Put it in |−⟩ = (|0⟩ − |1⟩)/√2 and the oracle’s XOR onto it stops being a write and becomes a sign: U_f|x⟩|−⟩ = (−1)^f(x)|x⟩|−⟩. The ancilla comes out exactly as it went in — you can check this on the page, the state stays a product at every step — and the input register is left carrying f’s entire truth table as a pattern of plus and minus signs.

That pattern is not readable. Every outcome is still equally likely, so measuring it gives you one random x and one bit of f, which is exactly what a classical query gives. What the second Hadamard layer does is ask a question about the pattern as a whole: amplitude |000⟩ after it is the average of the signs. A constant f averages to ±1, a balanced f averages to exactly 0. Nothing else can happen.

You called f once and learned a property of all 8 of its values. The oracle you picked is balanced, and the final state puts 0.0% of its probability on |000⟩ — so a single shot, with no repetition and no error bars, decides it. Switch between a constant and a balanced oracle and watch that number jump between 100% and 0% with nothing in between.

Try the balanced oracle that is not a parity. Deutsch–Jozsa still answers correctly — it only ever asks “is the average of the signs zero?” — but the Bernstein–Vazirani readout on the same function is spread across several outcomes, because there is no hidden string to find. The promise that f is linear is doing real work, and at 2 qubits you cannot even see the difference: every balanced function on two bits happens to be a parity.

To be certain whether f is constant or balanced, a classical algorithm may have to see half the inputs plus one: 2ⁿ⁻¹ + 1 queries. Until that last call, every answer so far is still consistent with both. The quantum circuit above asks once, at every n.

The honest footnote: if you allow a small chance of being wrong, a classical algorithm settles Deutsch–Jozsa in a handful of random queries — two differing answers prove balanced, and a run of identical ones makes constant overwhelmingly likely. The exponential gap here is against certainty, and that is exactly why Bernstein–Vazirani mattered more: its n-versus-1 gap survives randomness, because n bits of answer genuinely require n classical questions.

Nobody needs to know whether a black box is constant or balanced. Deutsch–Jozsa was built to be the smallest problem where a quantum computer is provably, unarguably faster than any classical one — small enough that you can follow it amplitude by amplitude, as you just did, instead of taking the speedup on faith.

The technique generalised immediately. Bernstein–Vazirani is the same circuit reading a linear function; Simon’s algorithm is the same idea with a hidden period instead of a hidden string, and gives an exponential separation that no randomised classical algorithm can close; Shor’s algorithm is Simon’s idea over the integers, with the quantum Fourier transform doing the final read. Every one of them is: spread out, make the answer interfere with itself, measure once.

The other family starts from Grover’s search, which uses the same phase-kickback oracle you just stepped through but amplifies one answer instead of cancelling a pattern — and buys a quadratic speedup rather than an exponential one, on a problem people actually have.

Query counts hide the price of the box. The oracle here is a real circuit: for a general truth table it is one 3-controlled X per input with f(x) = 1, and a 3-controlled X decomposes into a number of two-qubit gates that grows with 3. On a machine, the “one query” is one call to a subroutine that may be enormous.

The comparison is still fair, because the classical algorithm has to run that same subroutine 2ⁿ⁻¹ + 1 times. But “one query” is not “one gate”, and a page that let you believe otherwise would be selling something. The register here stops at 4 qubits for the same reason every simulator does: the statevector doubles with each one.