The first quantum speedups, and the trick behind them.
In 1985 David Deutsch noticed that a quantum computer can learn whether f(0)=f(1), something that classically requires evaluating f twice. The trick behind the modern one-query version, phase kickback, writes f(x) into the sign of an amplitude, and it sits inside nearly every quantum algorithm since.
What you’ll learn
Construct the bit oracle Uf, prove it is unitary and self-inverse, and explain why scratch garbage must be uncomputed.
Derive phase kickback with a ∣−⟩ ancilla, both directly and as the eigenvalue of a controlled-X.
Prove H⊗n∣x⟩=2−n/2∑y(−1)x⋅y∣y⟩ and use it to analyze Deutsch–Jozsa exactly.
Compare deterministic, randomized and quantum query costs for Deutsch–Jozsa and Bernstein–Vazirani.
Functions as unitaries
A classical function f:{0,1}n→{0,1}m is usually not reversible: f(x) alone does not determine x. Quantum gates are unitary, hence reversible, so the map ∣x⟩↦∣f(x)⟩ is not available. The standard fix keeps the input and XORs the output into a second register:
Uf∣x⟩∣y⟩=∣x⟩∣y⊕f(x)⟩,x∈{0,1}n,y∈{0,1}m.
The bit (standard) oracle; ⊕ is bitwise XOR.
DerivationU_f is unitary and self-inverse
Uf2∣x⟩∣y⟩=∣x⟩∣y⊕f(x)⊕f(x)⟩=∣x⟩∣y⟩
Applying Uf twice XORs f(x) in and out again, since f(x)⊕f(x)=0.
Uf2=I⟹Uf−1=Uf
So Uf maps the computational basis to itself bijectively: it is a permutation matrix.
Uf†=UfT=Uf−1=Uf
Permutation matrices are real and orthogonal, so Uf is unitary; being its own inverse, it is also Hermitian.
Check your understanding
Take m=1. Why can the "overwrite" map ∣x⟩∣y⟩↦∣x⟩∣f(x)⟩ not be implemented as a quantum gate?
It is unitary, but too slow to implement
It sends ∣x⟩∣0⟩ and ∣x⟩∣1⟩ to the same state, so it is not injective and hence not unitary
Quantum gates cannot act on two registers at once
It is fine whenever f is balanced
Show the answer
B. It sends ∣x⟩∣0⟩ and ∣x⟩∣1⟩ to the same state, so it is not injective and hence not unitary
Unitaries are invertible, so orthogonal inputs must stay orthogonal. Overwriting forgets y: both ∣x⟩∣0⟩ and ∣x⟩∣1⟩ land on ∣x⟩∣f(x)⟩. With XOR, y can always be recovered.
Phase kickback
Feed the oracle's target register (take m=1) the state ∣−⟩=21(∣0⟩−∣1⟩). Something odd happens: the target does not change, but the input register picks up a sign.
DerivationPhase kickback
Uf∣x⟩∣−⟩=21(∣x⟩∣f(x)⟩−∣x⟩∣1⊕f(x)⟩)
Apply Uf to each term of ∣−⟩.
f(x)=0:21∣x⟩(∣0⟩−∣1⟩)=∣x⟩∣−⟩
If f(x)=0 nothing changes.
f(x)=1:21∣x⟩(∣1⟩−∣0⟩)=−∣x⟩∣−⟩
If f(x)=1 the two terms swap, which is an overall minus sign.
Uf(x∑αx∣x⟩)∣−⟩=(x∑(−1)f(x)αx∣x⟩)∣−⟩
Both cases read Uf∣x⟩∣−⟩=(−1)f(x)∣x⟩∣−⟩; by linearity the signs attach to every branch of a superposition, while the target factors out untouched.
Since the target stays in ∣−⟩, unentangled, we can drop it: one query to Uf implements the phase oracle
Of∣x⟩=(−1)f(x)∣x⟩.
Why it works: Uf=∑x∣x⟩⟨x∣⊗Xf(x) is a controlled-Xf(x), and ∣−⟩ is the eigenstate of X with eigenvalue −1. A controlled-U acting on an eigenstate of U leaves the target alone and kicks the eigenvalue back onto the control. This phase-kickback mechanism also drives phase estimation (see Phase Kickback & Phase Estimation).
Think first What would happen if qubit 1 started in ∣0⟩ instead of ∣−⟩?
The CNOT would copy x into qubit 1, producing 21(∣00⟩+∣11⟩). No phase reaches qubit 0; its reduced state is now maximally mixed, and the final H yields a fair coin. The ∣−⟩ ancilla is what turns "write f(x) down" into "mark x with a sign".
Deutsch's algorithm
Deutsch's problem: given f:{0,1}→{0,1}, compute f(0)⊕f(1), i.e. decide whether f is constant or balanced. One classical evaluation reveals one value, which says nothing about the XOR, so you need two; a randomized algorithm with one query is right only half the time. The circuit you just built does it with one query.
DerivationDeutsch's algorithm
∣0⟩∣1⟩H⊗H∣+⟩∣−⟩
Input in ∣+⟩, target in ∣−⟩.
Uf21((−1)f(0)∣0⟩+(−1)f(1)∣1⟩)∣−⟩
Phase kickback on each branch.
=(−1)f(0)21(∣0⟩+(−1)f(0)⊕f(1)∣1⟩)∣−⟩
Factor out the global phase (−1)f(0). What remains is ∣+⟩ if f(0)=f(1) and ∣−⟩ otherwise.
H⊗I(−1)f(0)∣f(0)⊕f(1)⟩∣−⟩
H maps ∣±⟩ to ∣0⟩,∣1⟩. Measuring the first qubit returns f(0)⊕f(1) with certainty.
f
Type
Circuit for Uf
Outcome
f(x)=0
constant
nothing
0
f(x)=1
constant
X on the target
0
f(x)=x
balanced
CNOT
1
f(x)=1⊕x
balanced
CNOT, then X on the target
1
The four one-bit functions. For f(x)=1 the target becomes X∣−⟩=−∣−⟩: a global phase, invisible.
Deutsch–Jozsa
Now f:{0,1}n→{0,1} is promised to be constant or balanced. First a workhorse identity. For one qubit, H∣x⟩=21(∣0⟩+(−1)x∣1⟩)=21∑y∈{0,1}(−1)xy∣y⟩. Taking the tensor product of n copies:
The amplitude of y=0n is the average sign. Constant: the outcome is 0n with certainty. Balanced: 0nnever occurs. One query, zero error.
Check your understanding
Run Deutsch–Jozsa with n=3 on the balanced function f(x)=x1⊕x3 (bits x1x2x3 from left to right). What do you measure?
000
A uniformly random nonzero string
101, with certainty
010, with certainty
Show the answer
C.101, with certainty
Here f(x)=s⋅x with s=101, so the amplitude of y is 2−3∑x(−1)(s⊕y)⋅x. A nonzero character sums to zero, so this is 1 for y=s and 0 otherwise: you measure 101 with certainty.
Honest accounting
Is Deutsch–Jozsa an exponential speedup? Against exact classical algorithms, yes: 1 query versus 2n−1+1. Against randomized ones, no. Query k independent uniformly random inputs and answer "constant" if all agree. Constant functions are always classified correctly, and a balanced one fools you only if all k answers agree, which happens with probability 2⋅2−k, whatever n is.
Predict before you look
What is the smallest k for which this randomized test errs with probability at most 1%, for every n?
Show the answer
8 queries
2⋅2−k=21−k≤0.01 needs k≥1+log2100≈7.64, so k=8 (error 2−7≈0.8%; k=7 gives 1.6%). A constant, independent of n.
Problem
Deterministic
Randomized (error ≤31)
Quantum
Deutsch (n=1)
2
2
1 (exact)
Deutsch–Jozsa
2n−1+1
O(1)
1 (exact)
Bernstein–Vazirani
n
n
1 (exact)
Simon
Ω(2n/2)
Θ(2n/2)
O(n)
Search (OR of N bits)
N
Θ(N)
Θ(N)
Query complexities. Simon's problem and search are developed in the next lessons.
Key takeaways
Uf∣x⟩∣y⟩=∣x⟩∣y⊕f(x)⟩ is a self-inverse permutation; scratch garbage must be uncomputed so it cannot spoil interference.
With the target in ∣−⟩, one query implements the phase oracle ∣x⟩↦(−1)f(x)∣x⟩: the eigenvalue of Xf(x) is kicked back onto the input.
H⊗n∣x⟩=2−n/2∑y(−1)x⋅y∣y⟩ turns sign patterns into measurable strings; in Deutsch–Jozsa the amplitude of 0n is the average of (−1)f(x).
Deutsch–Jozsa beats exact classical algorithms exponentially but randomized ones only by a constant; Bernstein–Vazirani's 1-versus-n gap survives randomness.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
Question 1
What is Uf∣x⟩∣−⟩, where Uf∣x⟩∣y⟩=∣x⟩∣y⊕f(x)⟩?
∣x⟩∣f(x)⟩
∣x⟩∣−⟩, unchanged
(−1)f(x)∣x⟩∣−⟩
(−1)f(x)∣x⟩∣+⟩
Show the answer
C.(−1)f(x)∣x⟩∣−⟩
∣−⟩ is an eigenvector of X with eigenvalue −1, and Uf applies Xf(x) to it. The target is unchanged and the eigenvalue (−1)f(x) is kicked back onto ∣x⟩.
Question 2
In Deutsch–Jozsa with a balanced f, what is the probability of measuring 0n?
Exactly 0
2−n
21
It depends on which balanced function
Show the answer
A. Exactly 0
The amplitude of 0n is 2−n∑x(−1)f(x), and a balanced f has equally many +1 and −1 terms. Destructive interference is exact.
Question 3
Run the circuit H on the input, Uf with f(x)=x (a CNOT), then H on the input, but with the target starting in ∣0⟩ instead of ∣−⟩. What does measuring the input give?
1 with certainty, as before
0 with certainty
The value f(0)
0 or 1 with probability 21 each
Show the answer
D.0 or 1 with probability 21 each
With target ∣0⟩ the CNOT produces 21(∣00⟩+∣11⟩): f(x) is written down, not kicked back. The input is entangled with the target, its reduced state is maximally mixed, and the final H yields a fair coin.
Question 4
Why must an oracle built from a classical circuit uncompute its scratch qubits?
To save qubits; leftover garbage is otherwise harmless
Garbage that depends on x entangles with the input register and destroys the interference between different x
Unitary circuits cannot produce garbage in the first place
Uncomputing is what makes Uf Hermitian
Show the answer
B. Garbage that depends on x entangles with the input register and destroys the interference between different x
With garbage the state is ∑x(−1)f(x)∣x⟩∣g(x)⟩. Branches with different g(x) are orthogonal and can no longer interfere, so the final Hadamards fail. Uncomputation returns the scratch to ∣0⋯0⟩, a common factor.
Question 5
Bernstein–Vazirani: f(x)=s⋅xmod2, find s. Which statement is correct?
Quantum needs n queries, classical 2n
Quantum and classical both need n
Quantum needs 1 query, randomized classical about n/2
Quantum needs 1 query; classical needs n, even with randomness
Show the answer
D. Quantum needs 1 query; classical needs n, even with randomness
The Deutsch–Jozsa circuit maps ∑x(−1)s⋅x∣x⟩ to ∣s⟩ exactly. Classically, each query returns a single bit, so q queries can distinguish at most 2q of the 2n possible strings s, which forces q≥n for success probability 2/3.