Search & Amplitude Amplification

Grover's Algorithm

Quadratic Speedup for Unstructured Search

Grover's algorithm provides a quadratic speedup for searching unstructured databases. While classical search requires O(N) queries in the worst case, Grover's algorithm finds the target in O(√N) queries — a provably optimal quantum advantage for this problem.

The Problem

Imagine finding one specific item in an unsorted list of N entries. Classically, you might need to check every single item. On average, you'll check about N/2 items, and in the worst case, all N items.

Grover's algorithm solves this by exploiting quantum superposition and interference. Instead of checking items one by one, it amplifies the amplitude of the correct answer while canceling out the wrong ones.

•Classical Complexity: O(N) queries required in the worst case for unstructured search.
•Quantum Complexity: O(√N) queries using Grover's amplitude amplification technique.
•Optimality: It has been proven that no quantum algorithm can solve unstructured search faster than O(√N), making Grover's algorithm optimal.

How It Works

The algorithm alternates between two operations: the Oracle and the Diffusion operator. The Oracle marks the solution by flipping its phase (a negative sign), while the Diffusion operator reflects all amplitudes about the average amplitude, amplifying the marked state's probability.

After approximately π/4 · √N iterations, measuring the quantum register yields the correct answer with high probability. For a database of one million items, Grover's algorithm needs only about 1,000 steps instead of 500,000.

U_f |x\rangle = (-1)^{f(x)} |x\rangle

Oracle Operator

D = 2|s\rangle\langle s| - I

Diffusion Operator

|\psi_k\rangle = (DU_f)^k |\psi_0\rangle

Amplitude Amplification

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

Optimal Iterations

•Initialization: Create an equal superposition of all possible states using Hadamard gates.
•Oracle: Apply a function that recognizes the target state and inverts its amplitude.
•Diffusion: Reflect all amplitudes around the average, amplifying the marked state.
•Iteration: Repeat Oracle + Diffusion √N times, then measure.

Applications

Beyond database search, Grover's algorithm serves as a subroutine for speeding up NP problems, constraint satisfaction, and cryptographic attacks. It can provide a quadratic speedup for any problem where you can verify a solution classically.

•SAT Solvers: Speeding up boolean satisfiability problems by quadratically reducing search space.
•Database Search: Finding entries in unstructured or partially structured databases.
•Cryptanalysis: Key search attacks against symmetric ciphers (e.g., brute-forcing AES keys).
•Optimization: As a building block for quantum optimization heuristics.

Code in Action

Runnable implementations you can copy and experiment with.

Grover's Search with Qiskit

A minimal implementation of Grover's algorithm searching for the state |11⟩ in a 2-qubit system.

grover_search.py

from qiskit import QuantumCircuit
from qiskit_aer import AerSimulator

# Create a 2-qubit Grover circuit
circuit = QuantumCircuit(2, 2)

# Initialize superposition
circuit.h([0, 1])

# Oracle for |11>
circuit.cz(0, 1)

# Diffusion operator
circuit.h([0, 1])
circuit.x([0, 1])
circuit.cz(0, 1)
circuit.x([0, 1])
circuit.h([0, 1])

# Measure
circuit.measure([0, 1], [0, 1])

# Run on simulator
simulator = AerSimulator()
job = simulator.run(circuit, shots=1024)
result = job.result()
counts = result.get_counts()

print("Measurement results:", counts)
# Expected: {'11': ~100%}

3-Qubit Grover for |101⟩

Extending the search to 3 qubits, looking for the state |101⟩. This demonstrates how the oracle generalizes.

grover_3qubit.py

from qiskit import QuantumCircuit
from qiskit_aer import AerSimulator
import numpy as np

n = 3
circuit = QuantumCircuit(n, n)

# Initialize superposition
circuit.h(range(n))

# Oracle for |101>: flip phase when q0=1, q1=0, q2=1
circuit.x(1)          # flip q1 to check for 0
circuit.h(2)
circuit.mcx([0, 1], 2)  # multi-controlled X on q2
circuit.h(2)
circuit.x(1)          # undo q1 flip

# Diffusion operator
circuit.h(range(n))
circuit.x(range(n))
circuit.h(n - 1)
circuit.mcx(list(range(n - 1)), n - 1)
circuit.h(n - 1)
circuit.x(range(n))
circuit.h(range(n))

# Measure
circuit.measure(range(n), range(n))

simulator = AerSimulator()
job = simulator.run(circuit, shots=2048)
counts = job.result().get_counts()
print(counts)

Grover's Search with PennyLane

A PennyLane implementation of Grover's algorithm searching for the state |11⟩ in a 2-qubit system.

grover_pennylane.py

import pennylane as qml
import numpy as np

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

def oracle():
    qml.CZ(wires=[0, 1])

def diffusion():
    for w in range(n_qubits):
        qml.Hadamard(wires=w)
        qml.PauliX(wires=w)
    qml.CZ(wires=[0, 1])
    for w in range(n_qubits):
        qml.PauliX(wires=w)
        qml.Hadamard(wires=w)

@qml.qnode(dev)
def grover_circuit():
    for w in range(n_qubits):
        qml.Hadamard(wires=w)
    oracle()
    diffusion()
    return qml.probs(wires=range(n_qubits))

probs = grover_circuit()
print("Probabilities:", probs)
# Expected: peak at state |11>

Explore next

Shor's Algorithm

Explore next

Variational Algorithms

from qiskit import QuantumCircuit from qiskit_aer import AerSimulator # Create a 2-qubit Grover circuit circuit = QuantumCircuit(2, 2) # Initialize superposition circuit.h([0, 1]) # Oracle for |11> circuit.cz(0, 1) # Diffusion operator circuit.h([0, 1]) circuit.x([0, 1]) circuit.cz(0, 1) circuit.x([0, 1]) circuit.h([0, 1]) # Measure circuit.measure([0, 1], [0, 1]) # Run on simulator simulator = AerSimulator() job = simulator.run(circuit, shots=1024) result = job.result() counts = result.get_counts() print("Measurement results:", counts) # Expected: {'11': ~100%}

from qiskit import QuantumCircuit from qiskit_aer import AerSimulator import numpy as np n = 3 circuit = QuantumCircuit(n, n) # Initialize superposition circuit.h(range(n)) # Oracle for |101>: flip phase when q0=1, q1=0, q2=1 circuit.x(1) # flip q1 to check for 0 circuit.h(2) circuit.mcx([0, 1], 2) # multi-controlled X on q2 circuit.h(2) circuit.x(1) # undo q1 flip # Diffusion operator circuit.h(range(n)) circuit.x(range(n)) circuit.h(n - 1) circuit.mcx(list(range(n - 1)), n - 1) circuit.h(n - 1) circuit.x(range(n)) circuit.h(range(n)) # Measure circuit.measure(range(n), range(n)) simulator = AerSimulator() job = simulator.run(circuit, shots=2048) counts = job.result().get_counts() print(counts)

import pennylane as qml import numpy as np n_qubits = 2 dev = qml.device('default.qubit', wires=n_qubits) def oracle(): qml.CZ(wires=[0, 1]) def diffusion(): for w in range(n_qubits): qml.Hadamard(wires=w) qml.PauliX(wires=w) qml.CZ(wires=[0, 1]) for w in range(n_qubits): qml.PauliX(wires=w) qml.Hadamard(wires=w) @qml.qnode(dev) def grover_circuit(): for w in range(n_qubits): qml.Hadamard(wires=w) oracle() diffusion() return qml.probs(wires=range(n_qubits)) probs = grover_circuit() print("Probabilities:", probs) # Expected: peak at state |11>