You are reading without signing in. Sign in or continue as guest to take quizzes and climb the ranks.
Deutsch–Jozsa: one query instead of many
The first algorithm with a provable gap: is a function constant or balanced?
- 01Explain the oracle model and phase kickback.
- 02Predict the output of Deutsch–Jozsa for a constant and a balanced oracle.
- 03Say honestly why the speed-up is a toy.
You are given a black box computing f: {0,1}ⁿ → {0,1} and promised that f is either constant (same output for every input) or balanced (0 on exactly half the inputs). Classically, you may need 2ⁿ⁻¹ + 1 queries to be sure. Deutsch–Jozsa needs one.
- H on every input qubit: uniform superposition over all x.
- Oracle: phases (−1)^{f(x)}.
- H again: the amplitude of |0…0⟩ becomes the average of (−1)^{f(x)}: ±1 if constant, exactly 0 if balanced.
- Measure: all zeros means constant, anything else means balanced.
Balanced oracle on 3 qubits
The oracle is f(x) = x0 ⊕ x2 (two CNOTs onto the target). Simulate: the three input bits are never 000. Replace the two CNOTs by nothing (constant f = 0) and the result is always 000.
OPENQASM 3.0;
include "stdgates.inc";
qubit[4] q;
bit[3] c;
x q[3];
h q[0];
h q[1];
h q[2];
h q[3];
barrier q;
cx q[0], q[3];
cx q[2], q[3];
barrier q;
h q[0];
h q[1];
h q[2];
c[0] = measure q[0];
c[1] = measure q[1];
c[2] = measure q[2];
Be honest about the gap: the classical cost is exponential only if you insist on certainty. A randomised classical algorithm with a few queries is almost always right. Deutsch–Jozsa matters because it is the clearest demonstration of interference doing work, and because its structure returns in Bernstein–Vazirani, Simon and Shor.
2 questions · one try each counts
Why is the target qubit prepared in |−⟩ rather than |0⟩?
Sign in to answer and climb the ranks; you will come back to this lesson.
For a balanced oracle the probability of measuring 0…0 is…
Sign in to answer and climb the ranks; you will come back to this lesson.