Grover's Algorithm

Also known as: Quantum unstructured search

First described: Lov Grover, 1996

Status: Proven Maturity: Demonstrated Speedup: Quadratic

The problem

Find x with f(x)=1 in an unstructured database of size N.

Given a black-box function f : {0,1}^n → {0,1} promised to have exactly one (or a small number of) marked inputs, find a marked input. The classical lower bound is Ω(N) queries; Grover achieves O(√N) and is provably optimal in the query model.

Best classical

O(N) queries

Quantum complexity

O(√N) queries, O(√N · cost(f)) gates

Our verdict

Quadratic, not exponential. Real-world search problems almost never look like the unstructured oracle model — they have structure that classical solvers exploit, and the oracle's gate cost is large. Treat Grover as a primitive (use it inside amplitude amplification), not a database speedup.

When to use it

Database-style search with a verifiable predicate and no exploitable structure.
As a building block inside amplitude amplification (BHT collision, minimum-finding, etc.).
When you control the oracle cost and it's roughly the same as a classical evaluation.

When not to use it

Real-world search problems — most have structure that classical algorithms exploit (SAT solvers, A*, etc.).
When the oracle is enormous: oracle cost gets multiplied by √N, killing wall-clock speedup.
Anything you'd actually solve with a hash table or an index.

Classical baseline

Linear scan O(N). For specific instances (3-SAT, k-SAT, CSPs) the best classical solvers beat Grover by enormous constants — Schöning's algorithm runs in O((4/3)^n) for 3-SAT, faster than O(√(2^n)) = O(2^{n/2}) for typical instance hardness.

Hardware cost

n logical qubits plus oracle ancillas. To beat brute force on n=40 bits you need ~10^6 oracle calls, each with depth ≥ poly(n). Currently impractical on NISQ.

Code

PennyLane

import pennylane as qml
import numpy as np

n_wires = 4
target = "1011"  # marked element

dev = qml.device("default.qubit", wires=n_wires)

def oracle():
    qml.FlipSign(int(target, 2), wires=range(n_wires))

@qml.qnode(dev)
def grover(n_iters):
    for w in range(n_wires):
        qml.Hadamard(wires=w)
    for _ in range(n_iters):
        oracle()
        qml.GroverOperator(wires=range(n_wires))
    return qml.probs(wires=range(n_wires))

# Optimal iters ≈ floor(π/4 · √N)
print(grover(int(np.pi/4 * np.sqrt(2**n_wires))))

Key papers

A fast quantum mechanical algorithm for database search ↗
Grover · 1996 · STOC '96
Tight bounds on quantum searching ↗
Boyer, Brassard, Høyer, Tapp · 1998 · Fortsch. Phys.

Deep-dive tutorials

→ Grover and Amplitude Amplification

Last verified: 2026-05-24