Deutsch–Jozsa: a certain answer in one query

The first quantum algorithm to decide with certainty, in a single query, whether a function is constant or balanced. Meet phase kickback and oracles.

The problem

We have a function f that takes bit strings and returns 0 or 1; we can’t look inside, we can only query it. We are promised that f is either constant (the same answer for every input) or balanced (0 for exactly half of the inputs, 1 for the other half). Which is it?

For n-bit inputs a classical computer must, in the worst case, query one more than half of the inputs. The Deutsch–Jozsa algorithm gives a certain answer with a single query.

Oracles and phase kickback

In quantum algorithms the function is given as an “oracle” circuit. The oracle XORs a helper qubit with f(x). Something interesting happens if the helper qubit is first put into (|0⟩ − |1⟩)/√2 with X and H: the XOR does not change the helper qubit; instead, the phase (−1)^f(x) is written onto the input. This is called phase kickback.

In the playground example q0 and q1 are the inputs and q2 the helper qubit. The two CNOTs encode f(x) = x0 XOR x1, which is balanced.

Why is one query enough?

The inputs are put into a superposition of all possible values with H, the oracle writes each its own phase, and H is applied to the inputs again. If the function is constant all phases are equal and interference returns the inputs to 00…0 with certainty. If it is balanced, the amplitude of 00…0 is cancelled exactly.

So if the inputs read 00 the function is constant; anything else and it is balanced: certainty, not probability. The problem looks artificial, but oracles and phase kickback are the foundation of Grover, Shor and phase estimation.

Try it yourself

Remove both CNOTs: the oracle now does nothing, so f is constant 0. The inputs (q1 q0) read 00; the result goes back to 100.

Open the circuit in your browser

The circuit playground is in Turkish. Button guide: “1000 kez ölç” = measure 1000 times, “Durum vektörünü göster” = show the state vector, “Bu devrenin Qiskit kodu” = this circuit’s Qiskit code, “Geri al” = undo, “Temizle” = clear. Click a gate in the circuit to remove it.

Key points

An oracle gives the function as a quantum circuit.
If the helper qubit is in (|0⟩ − |1⟩)/√2, the oracle writes the phase (−1)^f(x) onto the input: phase kickback.
For a constant function the inputs read 00…0 with certainty; for a balanced one never.
Classically an exponential number of queries is needed in the worst case; quantum needs one.

Test yourself

What do we learn if the Deutsch–Jozsa inputs read something other than 00?

The function is constant
The function is balanced
Nothing; we have to measure again

Show the answer

The function is balanced. For a constant function interference returns the inputs to 00…0 with certainty; any other result shows with certainty that the function is balanced.

← Phase and the Bloch sphere: the invisible dial · Bernstein–Vazirani: find the hidden string in one go →