Deutsch–Jozsa query circuit

A small worked example, computed in your browser. It is not a result from this record's papers.

Deutsch-Jozsa on a balanced function

3 input qubits, testing f(x) = x0 XOR x1 XOR x2, which is balanced.

1. Step 1 of 6 · X

   Sets the ancilla to |1⟩, so the next step can put it into |−⟩.

   The whole state moves from 0000 to 1000 — one certain outcome before, one certain outcome after, no superposition either side.

2. Step 2 of 6 · Hadamard layer(4)

   Hadamards everything: the ancilla becomes |−⟩, and the three input qubits spread into an equal superposition of all 8 inputs.

   Probability spreads from 1 outcome to 16. All 16 are equally likely.

   Show the gates inside this block
3. Step 3 of 6 · DJ balanced oracle(3)

   Applies f by CX-ing each input qubit onto the ancilla; against |−⟩, this kicks a phase (−1)^f(x) onto each input branch.

   The outcome probabilities do not move at all. What this step changes is phase — 2 distinct relative phases across the state now — which no measurement can see until a later step turns it back into probability.

   Show the gates inside this block
4. Step 4 of 6 · Hadamard layer(3)

   A second Hadamard layer on the inputs only turns those phases into a deterministic readout.

   Probability gathers from 16 outcomes onto 2. 0111 goes from 6.3% to 50.0%.

   Show the gates inside this block
5. Step 5 of 6 · H

   Undoes the ancilla's Hadamard.

   Probability gathers from 2 outcomes onto 1. 1111 goes from 50.0% to 100.0%.

6. Step 6 of 6 · X

   Returns the ancilla to |0⟩, purely for a tidy final state. It plays no further role in the algorithm.

   The whole state moves from 1111 to 0111 — one certain outcome before, one certain outcome after, no superposition either side.

Readout The three input qubits read 111 (any nonzero result proves f is balanced, not constant); the ancilla reads 0.