The Deutsch-Jozsa Algorithm

algorithmsLab

14 min read

The Deutsch-Jozsa Algorithm

One oracle query to tell constant from balanced, the first algorithm with a proven quantum speedup.

Suggested before this lesson

You now have every ingredient: uniform superposition and exact interference cancellation (from Superposition and Interference at Scale), phase kickback (from Phase Kickback), and the oracle convention (from Oracles and Black-Box Functions, sharpened last lesson into the formal constant/balanced distinction). Deutsch-Jozsa combines all four into the first algorithm in this course with a proven quantum speedup over any classical approach.

The Promise

You're handed an oracle for $f:\{0,1\}^n \to \{0,1\}$ with a guarantee: $f$ is either constant (same output for every input) or balanced (0 for exactly half the inputs, 1 for the other half). Nothing in between. Which one is it?

Classically, in the worst case you have to check more than half of all $2^n$ inputs before you can be sure: if the first $2^{n-1}$ all come back 0, you still can't rule out "balanced, and I just haven't seen a 1 yet" until one more check. Deutsch-Jozsa answers with certainty using a single query to the oracle.

The Oracle Under Test

Exactly the black box from the oracles lesson: the algorithm never gets to look inside this, only query it once.

Black Box

The Circuit

Start with $n$ input qubits at $|0\rangle$ and one ancilla. Set the ancilla to $|-\rangle$ ( $X$ then $H$ ), the phase-kickback setup from the Phase Kickback lesson.
$H$ on every input qubit: uniform superposition over all $2^n$ inputs, queried "all at once."
One query to the oracle. Every input's $f(x)$ gets kicked back as a phase on that input's amplitude, thanks to the ancilla sitting in $|-\rangle$ .
$H$ again on the input qubits: turns the pattern of phases into an interference pattern in the probabilities.
Measure the input register only (ignore the ancilla).

If every input qubit reads $0$ : $f$ is constant. If any input qubit reads $1$ : $f$ is balanced. That's the whole algorithm.

Constant Case: $f(x) = 0$

An oracle for the always-0 function does nothing at all (no gates). So step 3 is empty, and steps 2 and 4 become two $H$ s in a row on each input qubit with nothing in between: exactly the $H$ -then- $H$ interference from Superposition and Interference at Scale. Every input qubit returns to $|0\rangle$ with certainty.

Constant Oracle:

f (x_{0}, x_{1}) = 0

Watch the input qubits (0 and 1) in the Exact State table: whichever outcome the ancilla (qubit 2) lands on, the input bits are always 0. Check the Measurement Probabilities panel: every nonzero outcome has 00 as its input bits.

Circuit

Step through the circuit: after gate 6 of 6

7 / 7

Measurement Probabilities

$∣000 ⟩$

50.0%

$∣001 ⟩$

0.0%

$∣010 ⟩$

0.0%

$∣011 ⟩$

0.0%

$∣100 ⟩$

50.0%

$∣101 ⟩$

0.0%

$∣110 ⟩$

0.0%

$∣111 ⟩$

0.0%

Exact State

Basis state	Re	Probability
$∣000 ⟩$	0.707	50.0%
$∣001 ⟩$	0	0.0%
$∣010 ⟩$	0	0.0%
$∣011 ⟩$	0	0.0%
$∣100 ⟩$	-0.707	50.0%
$∣101 ⟩$	0	0.0%
$∣110 ⟩$	0	0.0%
$∣111 ⟩$	0	0.0%

Balanced Case: $f(x_0, x_1) = x_0$

A balanced function that depends only on $x_0$ : the oracle is a single $CX$ from qubit 0 into the ancilla (the oracle lesson's linear-oracle recipe, using just one of the two inputs).

Balanced Oracle:

f (x_{0}, x_{1}) = x_{0}

Qubit 0 (whose phase got kicked back by the oracle) no longer cancels back to

|0\rangle

; it's flipped to

|1\rangle

instead. Qubit 1, which the oracle never touched, still cancels back to

|0\rangle

exactly as in the constant case.

Circuit

Step through the circuit: after gate 7 of 7

8 / 8

Measurement Probabilities

$∣000 ⟩$

0.0%

$∣001 ⟩$

50.0%

$∣010 ⟩$

0.0%

$∣011 ⟩$

0.0%

$∣100 ⟩$

0.0%

$∣101 ⟩$

50.0%

$∣110 ⟩$

0.0%

$∣111 ⟩$

0.0%

Exact State

Basis state	Re	Probability
$∣000 ⟩$	0	0.0%
$∣001 ⟩$	0.707	50.0%
$∣010 ⟩$	0	0.0%
$∣011 ⟩$	0	0.0%
$∣100 ⟩$	0	0.0%
$∣101 ⟩$	-0.707	50.0%
$∣110 ⟩$	0	0.0%
$∣111 ⟩$	0	0.0%

Every nonzero outcome now has input bits $10$ , never $00$ : one query, and you know for certain this $f$ is balanced.

Exercise

Build the full Deutsch-Jozsa circuit for the balanced oracle

f(x_0, x_1) = x_0

on a 3-qubit circuit (qubits 0, 1 are the input register, qubit 2 is the ancilla): prepare the ancilla in

|-\rangle

, put the input register in superposition, apply the oracle (a single

CX

from qubit 0 into the ancilla), then apply

H

to the input register again.

Live preview of the circuit detected in your code

Need a hint?

Check your understanding

After running Deutsch-Jozsa once, you measure the input register and get all zeros. What can you conclude?

f

is definitely balanced.

f

is definitely constant: a single query has fully resolved the promise.

f

could be either; you need to run it again to be sure.

Nothing: the ancilla's outcome also has to be checked.