Computation

Quantum
Algorithms

Exploring the landmark algorithms that demonstrate genuine quantum advantage — from Shor's integer factoring to Grover's search — and understanding the deeper principles of why and when quantum computers outperform classical ones.

Shor's Algorithm Grover's Algorithm Quantum Fourier Transform Amplitude Amplification Complexity Theory BQP

What Makes a Quantum Algorithm?

Quantum Advantage and Where It Comes From

A quantum algorithm achieves an advantage not by running on faster hardware, but by exploiting superposition, entanglement, and interference in ways classical algorithms cannot. The algorithm is designed so that amplitudes corresponding to wrong answers interfere destructively and cancel out, while amplitudes for correct answers interfere constructively and grow.

Not all problems benefit from quantum computation. The complexity class BQP (Bounded-error Quantum Polynomial time) describes problems a quantum computer can solve efficiently. It is widely believed that BQP does not contain all of NP — meaning quantum computers are not a general solution to hard combinatorial problems like the travelling salesman problem.

Grover's Search Algorithm

A schematic circuit representation illustrating the key stages of GSA. The process includes initialization, where the qubits are prepared in a superposition state; marking, where the target item (items) in the database are identified and marked by the oracle; amplification, where the amplitude(s) of the marked item(s) are increased; and measurement, where the final result is obtained. Here, |0⟩, H, and X represent the initialization of the qubit to the |0⟩ state, the Hadamard gate, and Pauli’s X gate, respectively. Source

Grover's Search Algorithm

Unstructured Database Search

Problem: Find a marked item among N unsorted entries.

Classical cost: O(N) — on average, half the database must be checked before finding the target.

Quantum cost: O(√N) — a quadratic speedup. This is provably optimal for unstructured search.

Algorithm steps:

1. Apply Hadamard gates to all qubits, creating an equal superposition of all N states.

2. Apply the oracle Uf, which flips the phase of the target state: |x⟩ → −|x⟩.

3. Apply the diffusion operator (inversion about the mean): amplifies the target's amplitude at the expense of all others.

4. Repeat steps 2–3 approximately π√N / 4 times, then measure to obtain the target with high probability.

Applications: Cryptographic key search, constraint satisfaction, database queries, and as a subroutine in other quantum algorithms.

Shor's Factoring Algorithm

Integer Factorisation

Problem: Given an integer N, find its prime factors.

Classical cost: Sub-exponential — the General Number Field Sieve runs in roughly O(exp((log N)^⅓)). For RSA-2048, this is computationally infeasible in any reasonable timeframe.

Quantum cost: O((log N)³) — polynomial. Exponentially faster than the best known classical algorithm.

How it works: Shor reduces the factoring problem to period finding — discovering the period r of the function f(x) = aˣ mod N. The Quantum Fourier Transform (QFT) efficiently extracts this period from a superposition of values. Once r is known, the factors of N follow from classical number theory (Euclid's algorithm).

Cryptographic significance: Shor's algorithm breaks RSA, Diffie-Hellman, and elliptic curve cryptography — the foundations of today's internet security. This is the primary driver of the post-quantum cryptography movement.

The Quantum Fourier Transform

Classical Fourier Transform decomposing a composite wave into its component frequencies. The classical version processes a single signal sequentially. The Quantum Fourier Transform performs the same decomposition but on quantum amplitudes in superposition — where interference between all possible inputs happens simultaneously, rather than one frequency at a time. This interference mechanism is the foundation of algorithms like Shor's, in the same way Grover's relies on amplitude amplification. Source

Quantum vs Classical Complexity

Problem Best Classical Quantum Speedup Type
Integer factorisation Sub-exponential O((log N)³) Exponential
Discrete logarithm Sub-exponential O((log N)³) Exponential
Unstructured search O(N) O(√N) Quadratic
Quantum system simulation Exponential Polynomial Exponential
Linear systems (HHL) O(N) O(log N) * Exponential *
Sorting O(N log N) No proven speedup None
NP-complete problems Exponential No proven polynomial speedup Unknown
Important caveat: BQP (Bounded-error Quantum Polynomial time) is believed to sit between P and NP but not contain all of NP. Quantum computers are not a universal solution to all hard problems — speedups only exist for specific problem structures that quantum algorithms can exploit.