🧩

Topic 6 of 12

Deutsch-Jozsa & Bernstein-Vazirani

The Deutsch-Jozsa algorithm was the first algorithm to demonstrate an exponential quantum speedup — albeit for a contrived problem. It determines in one query whether a hidden Boolean function is constant or balanced, whereas classical deterministic algorithms may need exponentially many. Bernstein-Vazirani finds a hidden bit string in one query versus n classical queries, giving a concrete polynomial speedup.

Key Concepts

Oracle Model

Algorithms access a function

f

only through an oracle (black box)

U_f|x\rangle|y\rangle = |x\rangle|y \oplus f(x)\rangle

that computes

f(x)

without revealing its implementation. Query complexity counts oracle calls, not arithmetic. Quantum algorithms can query

f

in superposition — evaluating all inputs simultaneously.

Constant vs Balanced Functions

A function

f:\{0,1\}^n \to \{0,1\}

is constant if

f(x) = c

for all

x

(either all 0 or all 1), or balanced if exactly half the inputs map to 0 and half to 1. Deutsch-Jozsa distinguishes these two cases with a guarantee that the function is one or the other.

Deutsch-Jozsa Algorithm

Prepare

n

input qubits in

|0\rangle^{\otimes n}

and one ancilla in

|{-}\rangle

. Apply

H^{\otimes n}

to create equal superposition, then query the oracle once, then apply

H^{\otimes n}

again. Measure the input register: outcome

|0\rangle^{\otimes n}

means constant; any other outcome means balanced. One query suffices.

Bernstein-Vazirani Problem

Given oracle for

f(x) = s \cdot x \bmod 2

(bitwise dot product with hidden string

s

), find

s

. Quantum: prepare superposition, query oracle once, apply

H^{\otimes n}

, measure — output is exactly

s

. Classical: need

n

queries (one per bit of

s

). Quantum advantage: factor of

n

Query Complexity Separation

Deutsch-Jozsa proves an exponential separation between quantum and classical deterministic query complexity:

Q(f) = 1

D(f) = 2^{n-1}+1

. While not a practical speedup (randomized classical algorithms solve it in 2 queries), it was the first proof that quantum computers can be exponentially faster in the query model.

Key Equations

Oracle Action

U_f|x\rangle|y\rangle = |x\rangle|y \oplus f(x)\rangle

The quantum oracle computes f(x) into an ancilla qubit without measuring x.

Phase Kickback

U_f|x\rangle|{-}\rangle = (-1)^{f(x)}|x\rangle|{-}\rangle

With ancilla in |−⟩, the oracle imprints f(x) as a phase on |x⟩ — the phase kickback trick.

Deutsch-Jozsa After Oracle

H^{\otimes n}\left(\sum_x (-1)^{f(x)}|x\rangle\right) = \begin{cases} |0^n\rangle & f \text{ constant}\\ \perp |0^n\rangle & f \text{ balanced}\end{cases}

Constructive/destructive interference reveals the function type in one measurement.

Bernstein-Vazirani Output

H^{\otimes n} \cdot U_f \cdot H^{\otimes n} |0^n\rangle = |s\rangle

One oracle query reveals the full n-bit hidden string s.

Worked Example

Deutsch's Algorithm (n=1)

Problem

For $n=1$ , Deutsch's algorithm determines if $f:\{0,1\}\to\{0,1\}$ is constant or balanced with one query. Trace through it for a balanced function with $f(0)=0, f(1)=1$ .

Solution

Start with $|01\rangle$ (input qubit 0, ancilla qubit 1). Apply $H\otimes H$ :

|{+}\rangle|{-}\rangle = \frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)\cdot\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)

Apply oracle $U_f$ . Phase kickback gives $(-1)^{f(x)}$ on each term:

\frac{1}{\sqrt{2}}[(-1)^{f(0)}|0\rangle + (-1)^{f(1)}|1\rangle]|{-}\rangle = \frac{1}{\sqrt{2}}[|0\rangle - |1\rangle]|{-}\rangle = |{-}\rangle|{-}\rangle

Apply $H$ to input: $H|{-}\rangle = |1\rangle$ .

Measuring $|1\rangle$ (not $|0\rangle$ ) indicates the function is balanced.

Answer Measurement outcome |1⟩ → balanced function. One oracle query sufficed.

Practice

Exercises

5 problems

1 of 5

Deutsch-Jozsa uses 1 quantum query. Classical deterministic worst case for $n=3$ input bits requires $2^{n-1}+1$ queries. How many?

Your answer

queries

2 of 5

Quantum Deutsch-Jozsa speedup ratio (classical/quantum queries) for any $n$ : quantum=1, classical= $2^{n-1}+1$ . For $n=10$ , how many classical queries are needed?

Your answer

queries

3 of 5

A balanced $f:\{0,1\}^3\to\{0,1\}$ has exactly half of $2^3=8$ inputs mapping to 1. How many inputs map to 1?

Unlock Exercise 3

Subscribe to PhysWeb Pro to access all exercises and track your progress.

Upgrade to Pro →

4 of 5

Bernstein-Vazirani recovers a $n=128$ bit string with 1 quantum query. Classical needs $n=128$ queries. Quantum savings?

Unlock Exercise 4

Subscribe to PhysWeb Pro to access all exercises and track your progress.

Upgrade to Pro →

5 of 5

For a constant function in Deutsch-Jozsa, the probability of measuring all-zeros $|0^n\rangle$ is:

Unlock Exercise 5

Subscribe to PhysWeb Pro to access all exercises and track your progress.

Upgrade to Pro →

Key Takeaways

The oracle $U_f|x\rangle|y\rangle = |x\rangle|y\oplus f(x)\rangle$ enables superposition queries — evaluating $f$ on all inputs at once.
Phase kickback: using ancilla $|{-}\rangle$ converts oracle action to phase $(-1)^{f(x)}$ on $|x\rangle$ .
Deutsch-Jozsa distinguishes constant from balanced $f$ in 1 query; classical deterministic needs $2^{n-1}+1$ .
Bernstein-Vazirani recovers the full $n$ -bit hidden string $s$ in 1 query; classical needs $n$ .
Both algorithms use the same circuit template: $H^{\otimes n} \to U_f \to H^{\otimes n} \to$ measure.