QUANTUM 06
The first proof that one quantum query can beat many classical ones
Sinclair College - Dr. Mike Libassi
TODAY
01 · THE PROBLEM
A sealed oracle computes f(x) for an n-bit input and returns one bit. You're promised the function is one of two kinds.
Returns the same output for every input: always 0, or always 1.
Returns 0 for exactly half the inputs and 1 for the other half.
Decide which kind, with 100% certainty, in as few queries as possible.
02 · CLASSICAL VS. QUANTUM
| Input bits (n) | Possible inputs | Classical worst case | Quantum |
|---|---|---|---|
| 1 | 2 | 2 | 1 |
| 3 | 8 | 5 | 1 |
| 10 | 1,024 | 513 | 1 |
| 50 | ≈ 1.1 quadrillion | ≈ 563 trillion | 1 |
Classically you must check more than half the inputs (2ⁿ⁻¹ + 1) to rule out "balanced" for certain.
03 · THE QUANTUM WAY
n qubits at |0⟩, helper qubit at |−⟩
Superposition over all 2ⁿ inputs
Each input gets sign (−1)f(x): phase kickback
Signs interfere
All zeros = constant; else balanced
03 · WHY IT WORKS
This is interference at scale: wrong answers cancel, the right answer reinforces.
04 · WHY IT MATTERS
Nobody needs this answer, and a classical computer allowing tiny error needs only a few random queries.
Superposition, phase kickback, and interference: the pattern behind every major quantum algorithm.
Deutsch-Jozsa (1992) → Simon (1994) → Shor (1994), which breaks RSA.
WRAP-UP
The oracle is constant or balanced; the task is to tell which
Classically, certainty can take 2ⁿ⁻¹ + 1 queries
Quantumly, it takes exactly one query plus interference
The same pattern leads directly to Shor's algorithm
DISCUSSION
Deutsch-Jozsa has no practical use. Why is it still taught in nearly every quantum computing course?
Think about what it proved, and which later algorithms reuse its structure.