Interactive Quantum Search Explorer
Press Next Step to begin stepping through Grover's algorithm. Each iteration has two stages: the Oracle flips the target's phase, then the Diffusion amplifies its amplitude. Watch the bars and geometric view to see amplification in action.
Click any point to jump to that step. The curve reveals the sine-squared oscillation and why overshoot occurs.
Each Grover iteration rotates the state vector by 2θ toward the target |w⟩ in a 2D subspace. The goal: reach 90° (target probability ≈ 100%).
Probability = |amplitude|². Target state probability grows with each iteration.
Run many measurements to verify Born's rule in action: outcomes distribute according to |amplitude|². Compare measured frequencies against theoretical predictions.
See the quadratic speedup live: classical random search checks items one by one until a target is found, while Grover's algorithm needs only √N oracle queries. Run multiple races to build up statistics.
By the end of this module, you should be able to:
This module assumes familiarity with: single-qubit gates (especially Hadamard and phase gates), superposition, measurement probabilities (Born's rule), and basic Dirac notation. If needed, review the earlier modules on Single Qubit Gates and Measurements first.
Grover's algorithm (1996) solves the unstructured search problem: given a function f(x) that returns 1 for M "marked" inputs out of N possibilities, find a marked input. Classically, this requires checking items one by one — O(N) queries on average. Grover's quantum algorithm does it in just O(√N) queries, a provably optimal quadratic speedup.
| Property | Classical Search | Grover's Algorithm |
|---|---|---|
| Query complexity | O(N) | O(√N) |
| For N = 1,000,000 | ~500,000 queries (avg) | ~785 queries |
| For N = 2256 (AES-256) | ~2255 queries | ~2128 queries |
| Deterministic? | Yes (exhaustive) | Probabilistic (> 99% success) |
| Optimality | Best possible classically | Best possible quantum (BBBV 1997) |
Start with \(n\) qubits in state \(|0\dots0\rangle\) and apply Hadamard gates to create an equal superposition of all \(N = 2^n\) computational basis states:
Every state has amplitude \(1/\sqrt{N}\), so equal probability \(1/N\) of being measured. The search target is hidden in this uniform fog — no state is preferred yet.
The oracle \(O_f\) recognizes target states and flips their phase (amplitude sign), while leaving all other states unchanged:
This is invisible to measurement (probabilities depend on \(|\text{amplitude}|^2\)), but it creates a subtle asymmetry that the Diffusion operator will exploit.
The diffusion operator \(D\) reflects every amplitude about the mean amplitude \(\langle\alpha\rangle\):
After the oracle, the target amplitude is negative (below the mean). Here's why the mean trick works:
After \(k_{\text{opt}}\) iterations, target probability approaches 1. Going beyond causes over-rotation — the state vector swings past the target, and probability starts decreasing. This is unique to quantum algorithms; classically, more searching never hurts.
Measure all qubits in the computational basis. At the optimal iteration count, the probability of collapsing to a target state is at least 1 − M/N (typically > 99%). If the measurement fails, simply reset and try again.
Let's trace through Grover's algorithm on n = 2 qubits (N = 4 states), searching for target |11⟩. Optimal iterations: k = 1.
The oracle negates the amplitude of the target state |11⟩:
Probabilities are unchanged (|±0.5|2 = 0.25 for all), but the mean has shifted down.
Reflect each amplitude about the mean (0.25): αx → 2(0.25) − αx
After just one iteration, |11⟩ has amplitude 1.0 — measurement gives the target with 100% probability. This perfect result is special to N = 4 (where θ = 30° and 3θ = 90° exactly).
Set 2 qubits, mark |11⟩ as the target, and step through one full iteration. Verify that the target reaches amplitude 1.0 exactly.
Open in Simulator — 2 qubitsThen try 3 qubits with target |101⟩. After 2 iterations, check: is the success probability exactly 100%? Why not?
Open in Simulator — 3 qubitsHint: compute θ = arcsin(√(1/8)) ≈ 20.7°, so (2·2+1)θ = 5θ ≈ 103.5° ≠ 90°.
A common confusion: “If the oracle already knows the answer, why search?” The key is the query complexity model. The oracle is a function evaluator — it can answer “is x the target?” but cannot simply output the target. Think of it as a lock that clicks when you insert the right key: it can verify but not produce the answer.
Many real problems have this structure: checking a solution is easy, but finding one is hard. Verifying that a database record matches a query is O(1), but finding it in an unsorted database requires O(N) checks. The oracle encapsulates the efficient verification step, and Grover’s algorithm reduces the number of calls from O(N) to O(√N). In cryptography, the “oracle” is the encryption function — you can check if a key is correct, but finding the right key requires exhaustive search.
How does the oracle flip a phase without measuring? Through phase kickback. The trick is an ancilla qubit prepared in the state \(|-\rangle = (|0\rangle - |1\rangle)/\sqrt{2}\):
When \(f(x)=0\), the ancilla stays \(|-\rangle\) unchanged. When \(f(x)=1\), XOR flips the ancilla to \((|1\rangle - |0\rangle)/\sqrt{2} = -|-\rangle\), kicking a global \(-1\) phase onto the input register. The ancilla returns to \(|-\rangle\) in both cases — it's the input \(|x\rangle\) that acquires the conditional phase.
Grover’s algorithm is a special case of amplitude amplification (Brassard et al., 2002). The general technique works with any quantum algorithm A that produces a “good” state with probability p: amplitude amplification boosts success probability to near 1 using O(1/√p) repetitions. Grover’s search is the case where A = Hadamard and p = M/N. This generalization is used as a subroutine in many more advanced quantum algorithms.
The key insight is that Grover's algorithm operates entirely within a 2D subspace spanned by:
The initial state \(|\psi\rangle\) lies in this plane, making a small angle \(\theta\) with \(|s'\rangle\):
Each iteration rotates by \(2\theta\), where \(\theta \approx \arcsin(1/\sqrt{N}) \approx 1/\sqrt{N}\) for small angles. We need a total rotation of \(\sim\pi/2\):
This is provably optimal. Bennett, Bernstein, Brassard, and Vazirani (1997) showed that any quantum algorithm for unstructured search requires \(\Omega(\sqrt{N})\) oracle queries. No quantum algorithm — no matter how clever — can do better.
Classical search grows linearly with N; Grover's grows as √N. The gap widens exponentially as the number of qubits increases.
On real quantum hardware, Grover's algorithm faces decoherence and gate errors. Each iteration adds circuit depth, and errors accumulate. For large N, the required circuit depth exceeds current hardware coherence times. Use the Noise slider in the Simulator to see how decoherence degrades the algorithm's performance.
Grover's has been demonstrated on small instances (3–5 qubits) on superconducting and trapped-ion hardware. Scaling to practically useful sizes (hundreds of logical qubits with error correction) remains a major engineering challenge. The algorithm itself is well-understood; the bottleneck is hardware maturity and fault-tolerant gate overhead.
A quantum circuit reads left to right, like a musical score. Each horizontal line is a qubit (initialized to |0⟩). Gates are operations applied to qubits as time flows rightward.
Hover over any gate in the diagram below for a detailed tooltip.
Step through the full circuit for 3 qubits with 2 optimal iterations. Click gates or use the controls below.
The oracle is problem-specific: its circuit depends on which states are marked. For a single target |x*⟩, it applies a phase of −1 to exactly that state using multi-controlled Z gates.
To flip the phase of |101⟩ specifically, we use controlled gates that activate only when qubits match the target pattern:
For multiple targets, oracle circuits are combined. In practice, oracles are often constructed from classical Boolean circuits compiled into reversible quantum gates.
The diffusion operator performs "inversion about the mean" and has a fixed structure independent of the search target:
This decomposes into 5 stages. The key idea is a “sandwich” pattern: wrap a simple operation inside basis changes. Think of it like translating a book — translate to English, read it, translate back:
Outer bread = basis change | Inner filling = the actual phase flip | Symmetric = undo the basis change
Follow the numbered flow below:
Understanding the cost of Grover's algorithm is essential for assessing its practical feasibility.
| Resource | Per Iteration | Total (k iterations) |
|---|---|---|
| Oracle calls | 1 | 2 |
| Hadamard gates | 2n | 12 + 2n |
| X (NOT) gates | 2n | 12 |
| Multi-controlled Z | 1 (in diffusion) | 2 |
| Total circuit depth | O(n) | O(n√N) |
| Ancilla qubits | 1 (for phase kickback) + O(n) for MCZ decomposition | |
Values update based on the current qubit count in the Simulator. The multi-controlled Z gate itself requires O(n) basic gates (Toffoli decomposition), making total depth O(n2 · √N) for a full implementation.
Try changing the qubit count in the Simulator tab and return here. Watch how the resource table updates — notice that oracle calls grow as √N while Hadamard gates grow as n·√N. Which resource becomes the bottleneck for large n?
12 questions covering core concepts, geometric intuition, complexity analysis, and practical implications. Questions progress from fundamentals to deeper reasoning.