Deutsch-Jozsa: constant or balanced in one query

The problem

A function f takes n bits and returns one bit. You are promised it is either constant (the same answer for every input) or balanced (0 for exactly half of the inputs). You may only learn about f by calling it, through an oracle. A deterministic classical algorithm can need 2ⁿ⁻¹ + 1 calls before it is certain.

The quantum circuit

• Put the n input qubits in an equal superposition of all inputs with Hadamards.
• Prepare an output qubit y in |−⟩ = (|0⟩ − |1⟩)/√2 with x y then h y.
• Call the oracle once: it maps |x⟩|y⟩ to |x⟩|y ⊕ f(x)⟩. Because y is |−⟩, this multiplies each input by (−1)^f(x), a phase kickback.
• Apply Hadamards to the inputs again and measure them.

The probability of reading all zeros is |2⁻ⁿ Σ_x (−1)^f(x)|²: 1 when f is constant, 0 when it is balanced. One call decides.

The lab

The oracle is f(x) = x0 xor x1 xor x2, built from three CNOTs onto y. It is balanced, so the inputs never read 000; for this f they read 111 on every shot, as in our run. Delete the three cx lines and f becomes the constant 0, and the inputs read 000.

In perspective

The separation is against deterministic algorithms. A randomised classical algorithm that tries a few random inputs is right with high probability, so Deutsch-Jozsa is a clean demonstration of interference, not a practical speed-up.