Grover's Search Algorithm

Searching unstructured databases in sqrt(N) time

Grover's algorithm provides a quadratic speedup for searching unstructured databases. It is one of the most versatile quantum algorithms, with applications far beyond simple search.

The Search Problem

Given an unsorted database of N items, find a specific item. Classically, you need O(N) queries in the worst case. Grover's algorithm finds it in O(√N) queries.

This quadratic speedup is provably optimal: no quantum algorithm can search an unstructured database faster than O(√N).

O(N)

Classical queries

O(\sqrt{N})

Quantum queries

R \approx \frac{\pi}{4} \sqrt{N}

Optimal iterations

How Grover Works

Grover's algorithm uses two reflections: one that flips the amplitude of the target state (the oracle), and one that reflects all amplitudes about the average amplitude (the diffusion operator).

Each Grover iteration amplifies the target state's amplitude while shrinking the others. After about (π/4)√N iterations, the target state has near-unit probability.

•Initialize: Prepare an equal superposition of all N states.
•Oracle: Flip the amplitude of the target state.
•Diffusion: Reflect all amplitudes about the average.
•Repeat: Iterate oracle + diffusion about (π/4)√N times.

Beyond Search

Grover's algorithm is far more general than database search. Amplitude amplification, the core technique, can speed up any algorithm that has a probabilistic success condition. It is used in quantum machine learning, optimization, and cryptography.

The algorithm can also be adapted to count solutions (quantum counting) and find the minimum of a function (quantum minimum finding).

•SAT solving: Quadratic speedup for checking satisfiability.
•Collision finding: Finding collisions in hash functions.
•Quantum ML: Speeding up training of quantum classifiers.

Try It Yourself

Run this code in your own environment to experiment with the concepts.

PennyLane: Grover's Algorithm

Search for a marked item in a 4-element database.

grover.py

import pennylane as qml
from pennylane import numpy as np

n = 2
dev = qml.device('default.qubit', wires=n)

def oracle():
    # Mark |11>
    qml.Hadamard(wires=1)
    qml.CNOT(wires=[0, 1])
    qml.Hadamard(wires=1)

def diffusion():
    for i in range(n):
        qml.Hadamard(wires=i)
        qml.PauliX(wires=i)
    qml.ControlledPhaseShift(np.pi, wires=[0, 1])
    for i in range(n):
        qml.PauliX(wires=i)
        qml.Hadamard(wires=i)

@qml.qnode(dev)
def grover():
    for i in range(n):
        qml.Hadamard(wires=i)
    oracle()
    diffusion()
    return qml.probs(wires=range(n))

print('Grover result:', grover())

Self-Check Quiz

1. What is the query complexity of Grover's algorithm?

2. Is Grover's speedup optimal?

3. What does the diffusion operator do?

Deutsch-Jozsa & Bernstein-Vazirani

Shor's Factoring Algorithm

import pennylane as qml from pennylane import numpy as np n = 2 dev = qml.device('default.qubit', wires=n) def oracle(): # Mark |11> qml.Hadamard(wires=1) qml.CNOT(wires=[0, 1]) qml.Hadamard(wires=1) def diffusion(): for i in range(n): qml.Hadamard(wires=i) qml.PauliX(wires=i) qml.ControlledPhaseShift(np.pi, wires=[0, 1]) for i in range(n): qml.PauliX(wires=i) qml.Hadamard(wires=i) @qml.qnode(dev) def grover(): for i in range(n): qml.Hadamard(wires=i) oracle() diffusion() return qml.probs(wires=range(n)) print('Grover result:', grover())