07 · An algorithm
Deutsch
Classically you need two queries to learn if a one-bit function is constant or balanced. Interference does it in one. This is the smallest quantum advantage that is actually an advantage.
In English
Someone has a tiny function on one bit: either always the same answer (constant) or half and half (balanced). Classically you must ask twice. Deutsch asks once, using interference, and the cancellation itself tells you which kind it is.
- Try this
- Run all four oracles. Constant ones agree; balanced ones agree with each other and disagree with constant. One shot each.
- Keep this
- Deutsch is the smallest quantum speedup that is actually a speedup.
Lab · one query
f maps one bit to one bit. Constant: f(0)=f(1). Balanced: they differ. The oracle writes f(x) into qubit 1 as a CNOT-like kick. You never read f(0) or f(1) separately — you read their parity off an interference experiment.
f(0)=0 · f(1)=0 · secretly constant
Step 1 / 5 · |00⟩
|00⟩1100%|10⟩00%|01⟩00%|11⟩00%
Deutsch’s problem is deliberately tiny: learn one bit about f, constant or balanced, with one call to a black box. Classically the box must be queried at both inputs. Quantumly, you query a superposition and read the parity off an interference.
Grover and Shor are the same idea at larger n — amplitude steering — plus a lot of number theory. Continue in Volume III · Grover and period-finding.