Grover's Search Algorithm

Category: Quantum Computing
Difficulty: Advanced
Time Complexity: O(√N)
Space Complexity: O(N) where N = 2^n

Overview

Grover’s algorithm (1996) is a quantum search algorithm that finds a marked item in an unsorted database of N items using only O(√N) queries, achieving a quadratic speedup over classical linear search. The algorithm works by repeatedly applying two operators: (1) an Oracle that marks the target state by flipping its phase, and (2) a Diffusion operator (also called the Grover operator or ‘inversion about the mean’) that amplifies the probability amplitude of the marked state through constructive interference. Starting from a uniform superposition of all N = 2^n basis states, the algorithm applies R = ⌊π/4 × √(N/M)⌋ iterations (where M is the number of marked items) to rotate the state vector toward the target subspace. For the special case of 2 qubits and 1 target, a single iteration achieves P(target) = 1.0 exactly. Grover’s algorithm is provably optimal — no quantum algorithm can search an unstructured database faster than O(√N).

Try It

• Web: Open in Eigenvue →
• Python:

  import eigenvue
  eigenvue.show("grovers-search")

Default Inputs

{
  "numQubits": 2,
  "targets": [
    3
  ]
}

Input Examples

2 qubits, target |11⟩

{
  "numQubits": 2,
  "targets": [
    3
  ]
}

3 qubits, target |101⟩

{
  "numQubits": 3,
  "targets": [
    5
  ]
}

2 qubits, 2 targets

{
  "numQubits": 2,
  "targets": [
    1,
    3
  ]
}

Code

Pseudocode

// Grover's Search Algorithm
1  INITIALIZE n qubits to |0...0⟩
2  N ← 2^n, M ← number of targets
3
4  APPLY H to all qubits          // uniform superposition
5  // Each state has amplitude 1/√N
6
7  R ← floor(π/4 × √(N/M))       // optimal iterations
8  FOR iter ← 1 TO R:
9    ORACLE: flip sign of target states
10     ∀ target t: α_t ← −α_t
11   DIFFUSION: reflect about mean
12     mean ← (1/N) × Σ α_k
13     ∀ k: α_k ← 2 × mean − α_k
14
15 MEASURE → target with high probability

Python

import math

def grovers_search(num_qubits: int, targets: list[int]) -> list[float]:
    """Grover's search algorithm simulation."""
    N = 1 << num_qubits
    M = len(targets)
    target_set = set(targets)

    # Initialize uniform superposition
    state = [1.0 / math.sqrt(N)] * N

    # Optimal number of iterations
    R = math.floor(math.pi / 4 * math.sqrt(N / M))

    for _ in range(R):
        # Oracle: negate target amplitudes
        for t in target_set:
            state[t] = -state[t]

        # Diffusion: reflect about the mean
        mean = sum(state) / N
        state = [2 * mean - amp for amp in state]

    # Measurement probabilities
    probs = [amp ** 2 for amp in state]
    return probs

JavaScript

function groversSearch(numQubits, targets) {
  const N = 1 << numQubits;
  const M = targets.length;
  const targetSet = new Set(targets);

  // Initialize uniform superposition
  const amp = 1 / Math.sqrt(N);
  const state = Array(N).fill(amp);

  // Optimal number of iterations
  const R = Math.floor(Math.PI / 4 * Math.sqrt(N / M));

  for (let iter = 0; iter < R; iter++) {
    // Oracle: negate target amplitudes
    for (const t of targetSet) {
      state[t] = -state[t];
    }

    // Diffusion: reflect about the mean
    const mean = state.reduce((s, a) => s + a, 0) / N;
    for (let k = 0; k < N; k++) {
      state[k] = 2 * mean - state[k];
    }
  }

  // Measurement probabilities
  return state.map(a => a * a);
}

Key Concepts

Oracle

A quantum black-box operator that recognizes the target state(s) by flipping their phase: U_f|x⟩ = (−1)^{f(x)}|x⟩. The oracle encodes the search problem — it ‘knows’ which items are targets. Crucially, the oracle changes the phase but NOT the measurement probabilities.

Amplitude Amplification

The core mechanism of Grover’s algorithm. Each iteration consists of an oracle (phase flip) followed by diffusion (inversion about the mean). Together, they rotate the state vector in a 2D subspace toward the target states, increasing the target amplitude by approximately 2/√N per iteration.

Grover Diffusion Operator

Also called ‘inversion about the mean,’ the diffusion operator reflects every amplitude about their average value: α’_k = 2⟨α⟩ − α_k. This transforms the negative amplitude (from the oracle) into constructive interference, boosting the target’s probability while suppressing non-targets.

Quadratic Speedup

Grover’s algorithm finds a target in O(√N) queries, compared to O(N) for classical search. This is a quadratic speedup and is provably optimal for unstructured search — no quantum algorithm can do better. For N = 1,000,000 items, Grover’s needs only ~785 iterations instead of up to 1,000,000 classical checks.

Common Pitfalls

• Overshooting (Too Many Iterations): If you apply too many Grover iterations, the state vector ‘overshoots’ the target and the success probability DECREASES. The algorithm is periodic with period ~π√(N/M)/2, so applying more iterations is not always better. You must stop at exactly R = ⌊π/4 × √(N/M)⌋ iterations.
• Multiple Solutions Change Iteration Count: When there are M > 1 target states, the optimal number of iterations drops to R = ⌊π/4 × √(N/M)⌋. With more targets, fewer iterations are needed. If M is unknown, quantum counting can estimate it first.
• Precise Iteration Count Matters: The success probability oscillates sinusoidally with the number of iterations. Even one extra iteration can significantly reduce the probability of finding the target. For 2 qubits with 1 target, exactly 1 iteration gives P = 1.0; 2 iterations would give P = 0.

Quiz

Q1: How many oracle calls does Grover’s algorithm need to search N items?

• A) O(N)
• B) O(N log N)
• C) O(√N)
• D) O(log N)

Show answer

Answer: C) O(√N)

Grover’s algorithm achieves a quadratic speedup: it needs O(√N) oracle calls compared to O(N) for classical linear search. This is provably optimal for unstructured search.

Q2: After the oracle flips the target’s phase, what happens to its measurement probability?

• A) It doubles
• B) It drops to zero
• C) It stays the same — only the phase changes
• D) It becomes 1.0

Show answer

Answer: C) It stays the same — only the phase changes

The oracle only flips the sign (phase) of the target amplitude: α → −α. Since probability is |α|², the sign change has no effect on probability. The magic happens in the NEXT step — the diffusion operator converts this phase difference into a probability difference.

Q3: What happens if you apply too many Grover iterations?

• A) The algorithm converges faster
• B) The target probability stays at maximum
• C) The target probability decreases (overshooting)
• D) The quantum state collapses

Show answer

Answer: C) The target probability decreases (overshooting)

Grover’s algorithm is periodic — the success probability oscillates sinusoidally. After the optimal number of iterations R ≈ π/4 × √(N/M), additional iterations rotate the state AWAY from the target, reducing the probability. Knowing when to stop is critical.

Further Reading

• Grover’s Algorithm — Wikipedia (reference)
• Qiskit Textbook: Grover’s Algorithm (tutorial)
• Original Paper: A Fast Quantum Mechanical Algorithm for Database Search (Grover, 1996) (paper)

Related Algorithms

• Superposition & Measurement
• Quantum Teleportation

Prerequisites

• Quantum Gates & Circuits
• Superposition & Measurement