Deutsch Algorithm
Steps
Circuit
Initial State
Start with |00⟩.
What's happening?
Both qubits begin in the computational basis state |0⟩.
Key Insight
We need to prepare the ancilla qubit specially.
Bloch Spheres
Note: Individual Bloch spheres cannot fully represent entangled states.
Probabilities
Statevector |ψ⟩
| State | Amplitude | |ψ| | Phase | Prob |
|---|---|---|---|---|
| |00⟩ | 1 | 1.000 | 0 | 100% |
| |01⟩ | 0 | 0.000 | — | 0% |
| |10⟩ | 0 | 0.000 | — | 0% |
| |11⟩ | 0 | 0.000 | — | 0% |
Algorithm Overview
Determine if a function is constant or balanced with just one evaluation.
Classical Approach
Classically, determining if f is constant or balanced requires 2 queries: evaluate f(0) and f(1), then compare. Deutsch's algorithm needs only 1 query.
Quantum Advantage
This is the simplest example of quantum speedup. While the speedup is only 2x for one bit, the generalized Deutsch-Jozsa algorithm for n bits shows exponential speedup: 1 quantum query vs 2^(n-1)+1 classical queries in the worst case.
Complexity
Circuit depth: 4, Gate count: 5 (4 single-qubit, 1 two-qubit), Oracle queries: 1
Applications
- •Foundation for Deutsch-Jozsa algorithm
- •Introduction to quantum parallelism
- •Demonstration of phase kickback
- •Teaching quantum interference
Try it yourself
Want to experiment with this circuit? Open it in the Playground to modify and explore.
Open in PlaygroundExercises and quizzes coming soon!