Deutsch-Jozsa: One Quantum Query Beats Every Classical Guess

A promise problem built for quantum interference

David Deutsch and Richard Jozsa's 1992 algorithm solves a deliberately narrow puzzle: you are handed a black-box function f mapping n bits to a single bit, with a promise that f is either constant (the same output for every possible input) or balanced (output 0 for exactly half of the 2ⁿ inputs and 1 for the other half). Your job is to say which, using the oracle as few times as possible.

Classically, if you insist on an answer that is certain rather than merely probable, there is no shortcut: an adversarial f can make you query up to 2ⁿ⁻¹ + 1 inputs before you can rule out both possibilities, because a run of identical outputs is consistent with "constant" right up until you have seen more than half the domain. The quantum algorithm answers with certainty using exactly one query to the oracle, regardless of n.

Phase kickback: encoding f(x) without touching the ancilla

The trick that makes one query enough is phase kickback. The oracle is implemented reversibly as U_f: |x⟩|y⟩ → |x⟩|y ⊕ f(x)⟩. Prepare the ancilla qubit not in |0⟩ but in the superposition |-⟩ = (|0⟩ - |1⟩)/√2. Applying U_f to |x⟩|-⟩ leaves the ancilla in |-⟩ exactly as it was, but multiplies the whole term by (-1)^f(x):

U_f |x⟩ (|0⟩-|1⟩)/√2  =  (-1)^f(x) |x⟩ (|0⟩-|1⟩)/√2

if the n input qubits hold a SUPERPOSITION over every x,
the single oracle call writes (-1)^f(x) as a phase onto
every branch of that superposition simultaneously.

Because the input register is put into an equal superposition of all 2ⁿ values before the oracle is called - by applying a Hadamard gate to each of the n qubits, which turns |0⟩^⊗n into (1/√2ⁿ) Σₓ |x⟩ - that one phase-kickback call effectively evaluates f at every input at once. The information does not come out as a readable bit string; it comes out encoded as a pattern of phases across an exponentially large superposition.

The algorithm, one query

1. prepare n input qubits in |0⟩^⊗n, one ancilla in |1⟩
2. apply H to all n+1 qubits          → input: equal superposition
                                          ancilla: |-⟩
3. apply the oracle U_f once          → phase kickback: (-1)^f(x) per branch
4. apply H to the n input qubits again  (Walsh-Hadamard transform)
5. measure the n input qubits
     all zeros  → f is CONSTANT
     any 1 bit  → f is BALANCED

Step 4 is the second half of the trick. A single Hadamard turns |0⟩ into a superposition; a layer of n Hadamards applied to a state that already carries a pattern of phases performs a Walsh-Hadamard transform - it interferes those 2ⁿ phased amplitudes back together, and where the interference lands depends entirely on the phase pattern the oracle wrote.

Why the amplitudes collapse to all-zero or never

The amplitude of measuring the all-zero string works out to a clean sum over every input:

amplitude(|00...0⟩) = (1/2ⁿ) Σₓ (-1)^f(x)

f constant  → every term has the same sign → sum = ±2ⁿ → probability 1
f balanced  → exactly half the terms are +1, half -1 → sum = 0 → probability 0

If f is constant, every one of the 2ⁿ terms in that sum has the same sign, so they add up constructively and the all-zero outcome is certain. If f is balanced, exactly half the terms are +1 and half are -1, they cancel exactly, and the all-zero outcome has probability precisely zero - measurement is guaranteed to return something other than all zeros. There is no ambiguous middle case, which is exactly why a single measurement gives a definite, error-free answer rather than a statistical hint.

What the speedup actually means

It is important to be precise about what Deutsch-Jozsa proves. Its exponential advantage is over the deterministic, exact classical algorithm, which must query in the worst case. A classical algorithm that is allowed to be randomized and only right with high probability can solve the same promise problem with a handful of queries - pick a small number of random inputs, and if you ever see two different outputs you know immediately f is balanced, while a run of identical outputs makes "constant" overwhelmingly likely after only a few checks. So Deutsch-Jozsa is not evidence that quantum computers beat the best classical strategy for this specific task; its real significance is historical and pedagogical. It was the first algorithm to demonstrate, rigorously, that a quantum computer's query complexity for an exact answer can be exponentially smaller than a classical computer's, and the phase-kickback and Walsh-Hadamard machinery it introduced became the toolkit that later, genuinely unbeatable speedups - Simon's algorithm, Shor's algorithm, Grover's algorithm - were all built from.

Frequently asked questions

Try it live

Everything above runs in your browser - open Deutsch-Jozsa Algorithm and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.