Understanding quantum speedup through phase kickback — one qubit at a time
Consider a function f : {0, 1} → {0, 1} — it takes a single bit as input and outputs a single bit. There are exactly 4 possible such functions. Two are constant (same output for all inputs) and two are balanced (different outputs). Click any function below to inspect it.
Before diving into the full algorithm, let's understand the crucial mechanism that makes it work: phase kickback. This is the trick at the heart of most quantum algorithms.
We prepare a special "ancilla" qubit in the state |−⟩ = (|0⟩ − |1⟩)/√2. Start with |0⟩, apply X to flip it to |1⟩, then apply H:
The oracle Uf maps |x⟩|y⟩ → |x⟩|y ⊕ f(x)⟩. Let's see what happens when the ancilla is in |−⟩:
Pick a function and an input state to see the phase kickback in action:
Now the magic: if the input is in superposition (|0⟩ + |1⟩)/√2 instead of a single basis state, phase kickback creates different phases on each branch. Then a final Hadamard gate creates interference that reveals the answer.
Now let's see the complete Deutsch algorithm. Select an oracle and step through each stage to see the quantum state evolve.
Compare all four oracles side by side. Click any function to auto-run the algorithm and see the result, or try the "Surprise Me" challenge!
| Oracle | f(0) | f(1) | After Uf | After H (input) | Measure | Type |
|---|
A hidden function is loaded. Run the algorithm and predict whether it's constant or balanced!