Interference at Work

Deutsch-Jozsa and phase kickback

One query decides a global property

~13 minLesson 15 of 24Written by Claude Fable 5

Someone hands you a function $f$ on $n$ -bit inputs and promises it is one of two kinds: constant (same output for every input) or balanced (output 0 on exactly half the inputs, 1 on the other half). Which is it? Classically you may have to check more than half of all $2^{n}$ inputs before you can be sure. A quantum computer settles it with a single query. This is the first place the interference from the last lesson does real, provable work.

The intuition to overturn

"Constant versus balanced is a global fact about the whole table of f, so you have to look at a large fraction of that table." It sounds airtight - and classically, if you demand certainty, it is: with

2^{n - 1}

agreeing answers you still cannot rule out a balanced function whose disagreement is hiding in the very next input. The surprise is that one quantum query, arranged correctly, extracts the global fact without reading any single output.

Run the one-query test

Below is the algorithm on a 2-qubit input. Pick an oracle - two are constant, two are balanced, and crucially you are not told which as you step. Advance through the layers and watch the amplitude on $∣ 00 ⟩$ . Constant oracles drive it to certainty; balanced oracles drive it to exactly zero. The verdict never depends on luck.

Deutsch-Jozsa on 2 input qubits: superpose, let the oracle kick a phase back, interfere, and decide with one query.

1. Superpose
2. Oracle (kickback)
3. Interfere
4. Measure

Input register in |00>. The hidden target qubit is held in |->, ready to kick phase back.

|00>

|01>

|10>

|11>

Step to the oracle and watch which bars dip below the axis - that flip is the phase kickback.

The one bar to keep your eye on is $∣ 00 ⟩$ . After the final layer its amplitude is either $\pm 1$ (constant) or exactly $0$ (balanced), with nothing in between. That razor edge is interference doing the deciding.

Phase kickback: how the oracle marks the input

The whole method rests on one small preparation. Put the oracle's output qubit not in $∣ 0 ⟩$ but in $∣ - ⟩ = \frac{1}{2} (∣ 0 ⟩ - ∣ 1 ⟩)$ , and watch what one query does to $∣ x ⟩ ∣ - ⟩$ . Since $U_{f}$ maps $∣ x ⟩ ∣ y ⟩$ to $∣ x ⟩ ∣ y \oplus f (x)⟩$ :

U_{f} ∣ x ⟩ (\frac{∣ 0 ⟩ - ∣ 1 ⟩}{2}) = ∣ x ⟩ (\frac{∣ f ( x )⟩ - ∣ 1 \oplus f ( x )⟩}{2}) = (- 1)^{f (x)} ∣ x ⟩ ∣ - ⟩ .

Read the two ends. If $f (x) = 0$ the target is unchanged; if $f (x) = 1$ the two terms swap, which is the same as multiplying by $- 1$ . Either way the target comes out exactly as it went in, and the factor $(- 1)^{f (x)}$ has jumped onto the input register. That is : the oracle writes $f$ as a sign on the input, never as a bit you would have to read out and collapse.^[2]

Interference turns signs into a verdict

Now the three-step choreography. Start the input in $∣ 0 ⟩^{\otimes n}$ , apply a Hadamard to each wire, query once, and apply the Hadamards again:

∣ 0 ⟩^{\otimes n} H^{\otimes n} \frac{1}{N} x \sum ∣ x ⟩ U_{f} \frac{1}{N} x \sum (- 1)^{f (x)} ∣ x ⟩ H^{\otimes n} z \sum c_{z} ∣ z ⟩ .

We only need the amplitude of the all-zeros outcome $∣ 0 ⟩^{\otimes n}$ after the final layer. Because each Hadamard sends every basis state to an equal spread with $+$ signs, the amplitude landing back on all-zeros is the plain average of the kicked-back signs:

c_{0 \dots 0} = \frac{1}{N} x = 0 \sum N - 1 (- 1)^{f (x)} .

This single number is the entire algorithm. If $f$ is constant, every term has the same sign, the average is $\pm 1$ , and you measure all-zeros with certainty. If $f$ is balanced, the $+ 1$ s and $- 1$ s cancel in perfectly matched pairs, the average is $0$ , and you never measure all-zeros. So the rule is exact: measure all-zeros and $f$ is constant; measure anything else and it is balanced.

One query versus exponentially many

Classically, guaranteeing the answer can force

2^{n - 1} + 1

evaluations - just over half the table - because any smaller sample of equal outputs is still consistent with a balanced function. The quantum algorithm uses one query regardless of

n

. That gap, constant versus exponential, is the kind of separation the big-O lesson trains you to care about. It is a promise problem, not a practical task, but it is the clean proof that interference can beat every classical strategy.

from qiskit import QuantumCircuit

qc = QuantumCircuit(3, 2)   # 2 input qubits + 1 output qubit

qc.x(2); qc.h(2)            # put the output qubit in |->  (X then H)
qc.h(0); qc.h(1)            # Hadamard layer on the input register

apply_oracle(qc)           # one query: kicks (-1)^{f(x)} onto the input

qc.h(0); qc.h(1)           # second Hadamard layer interferes the branches
qc.measure([0, 1], [0, 1]) # all-zeros -> constant; anything else -> balanced

Deutsch-Jozsa on 2 input qubits, in Qiskit-style code

Lock it in

Preparing the output qubit in |-> turns the oracle into phase kickback: U_f leaves it alone and multiplies the input |x> by (-1)^{f(x)}.
Sandwiching one query between two Hadamard layers makes the all-zeros amplitude equal the average of the signs, (1/N) sum_x (-1)^{f(x)}.
Constant f gives average +-1 (measure all-zeros with certainty); balanced f gives average 0 (never all-zeros) - a deterministic verdict.
One quantum query settles a question that classically needs up to 2^(n-1)+1 evaluations: the first clean, provable quantum speedup.

Check yourself

What does phase kickback do when the oracle's output qubit is prepared in |->?

For a promise that f on n bits is constant or balanced, how many queries does each model need for certainty?

Recall: which global property does Deutsch-Jozsa decide in one query, and what is the trick that makes it work?

The problem, the mechanism, and the payoff in one breath. Try to state it, then check.

Match each part of Deutsch-Jozsa to its role.

drop here

same output on every input

drop here

output 0 on half the inputs, 1 on the other half

drop here

the oracle writes f(x) as a sign on the input

drop here

interferes the branches into the all-zeros answer

Primary source

IBM Quantum Learning: Fundamentals of Quantum Algorithms

The query-algorithms unit builds Deutsch, then Deutsch-Jozsa, exactly this way - phase kickback first, then the Hadamard sandwich - and lets you run the circuits on a simulator so the deterministic all-zeros outcome is something you watch happen rather than take on faith.^[1]

Next: Grover's search, where the same cancel-and-reinforce idea becomes a geometric rotation you can watch, and where doing too many steps makes the answer worse.

Sources