Quantum Algorithms Explained

What Makes an Algorithm Quantum

A quantum algorithm uses operations that have no classical analogue: putting registers into superposition, creating entanglement between qubits, and using interference to amplify correct answers while suppressing incorrect ones. The speedup comes not from raw clock speed (quantum gates are actually much slower than classical transistor operations) but from the algorithm's ability to process exponentially many states with a polynomial number of operations, then extract useful global properties from the result.

Not every problem benefits from a quantum approach. The class BQP (Bounded-Error Quantum Polynomial time) contains all problems that a quantum computer can solve efficiently with high probability. BQP contains the class P (problems efficiently solvable classically) but is believed to be strictly larger, meaning there are problems quantum computers solve efficiently that classical computers cannot. Whether BQP contains the class NP (problems whose solutions can be verified efficiently) is unknown, and most researchers believe it does not. This means quantum computers probably cannot solve all the hardest optimization problems efficiently, only specific ones with exploitable mathematical structure.

The quantum algorithm zoo, maintained by the National Institute of Standards and Technology, catalogs over 400 quantum algorithms with proven speedups for specific problems. These span areas including number theory, graph theory, optimization, simulation, machine learning, and linear algebra. However, the practical significance varies enormously: some provide exponential speedups for problems of genuine importance (factoring, simulation), while others provide modest polynomial speedups for artificial problems with little real-world relevance. The challenge of quantum algorithm research is expanding the set of important problems with meaningful quantum advantages.

Shor's Algorithm: Exponential Speedup for Factoring

Peter Shor published his factoring algorithm in 1994, and it remains the most important quantum algorithm because of its implications for cryptography. The algorithm factors an N-bit integer in O(N^2 * log(N) * log(log(N))) operations, compared to the best known classical algorithm (the general number field sieve) which requires roughly O(exp(N^(1/3))) operations. For a 2048-bit RSA key, the classical algorithm would take thousands of years on the fastest supercomputer, while Shor's algorithm would take hours on a sufficiently powerful quantum computer.

Shor's algorithm works by reducing factoring to the problem of finding the period of a function. Given a number N to factor, the algorithm picks a random number a less than N and computes the function f(x) = a^x mod N. This function is periodic, with a period r that depends on a and N. Once r is found, the factors of N can be extracted using the mathematical relationship gcd(a^(r/2) +/- 1, N), which yields a non-trivial factor with probability at least 50%. If the first attempt fails, repeating with a different random a succeeds quickly.

The quantum speedup comes from finding the period r. Classically, finding the period requires evaluating f(x) for many values of x, which takes exponential time. Shor's quantum circuit creates a superposition of all possible x values, computes f(x) in superposition (so the quantum register contains a superposition of all (x, f(x)) pairs), and then applies the quantum Fourier transform to the x register. The Fourier transform converts the periodic structure of the state into peaks at positions proportional to 1/r, and measuring the result reveals r with high probability. The entire process requires only polynomial time because the quantum Fourier transform circuit has depth O(N^2) for N qubits.

Running Shor's algorithm on cryptographically relevant key sizes requires a fault-tolerant quantum computer with thousands of logical qubits. Current estimates suggest that factoring a 2048-bit RSA key requires roughly 4,000 logical qubits and millions of T gates. With surface code error correction at realistic physical error rates, this translates to roughly 20 million physical qubits. No current or near-term quantum processor approaches this scale, which is why RSA encryption remains secure for now, but the prospect has motivated the global transition to post-quantum cryptographic standards.

Grover's Algorithm: Quadratic Speedup for Search

Lov Grover published his search algorithm in 1996, providing a quadratic speedup for searching unstructured databases and, more broadly, for any problem that can be formulated as "find an input x such that f(x) = 1." Classically, finding a marked item among N items requires checking O(N) items on average. Grover's algorithm finds it in O(sqrt(N)) queries to the oracle function that identifies the marked item. For N = one million, this is a speedup from 500,000 average checks to about 1,000.

The algorithm works through amplitude amplification, a process that gradually increases the probability amplitude of the target state while decreasing the amplitudes of non-target states. Starting from a uniform superposition of all N states (each with amplitude 1/sqrt(N)), each iteration of the Grover operator performs two steps: the oracle flips the sign of the target state's amplitude (multiplying it by negative one), and the diffusion operator reflects all amplitudes about their mean. The net effect of each iteration is to rotate the state vector toward the target state by a fixed angle of roughly 2/sqrt(N) radians. After pi/4 * sqrt(N) iterations, the state has rotated to align with the target, and measurement produces the correct answer with probability close to 1.

Grover's speedup is provably optimal: no quantum algorithm can search an unstructured database faster than O(sqrt(N)). This is a quadratic speedup rather than the exponential speedup of Shor's algorithm, but it applies to a much broader class of problems. Any computational task that involves checking whether a candidate solution satisfies some criterion can be cast as a search problem and accelerated by Grover's algorithm. This includes satisfiability problems, constraint satisfaction, and certain optimization tasks. However, the quadratic speedup means that a problem requiring 2^128 classical operations still requires 2^64 quantum operations, which may or may not be practical depending on the context.

Quantum Phase Estimation and Simulation

Quantum phase estimation (QPE) is a subroutine used in many quantum algorithms, including Shor's algorithm and quantum chemistry algorithms. Given a unitary operator U and one of its eigenstates |psi>, QPE estimates the eigenvalue e^(2*pi*i*phi) by determining the phase phi to a desired number of bits of precision. The circuit uses a register of ancilla qubits, each controlling a successively higher power of U, followed by an inverse quantum Fourier transform that extracts the phase into a measurable bit string.

QPE is the foundation of quantum simulation algorithms for chemistry and materials science. The electronic structure of a molecule is determined by the eigenvalues of its Hamiltonian operator, with the lowest eigenvalue corresponding to the ground state energy. By encoding the molecular Hamiltonian as a quantum operator and applying QPE, a quantum computer can determine molecular energy levels with precision that scales polynomially with system size, compared to the exponential scaling of exact classical methods. This capability would transform drug design, catalyst development, and materials engineering by enabling accurate prediction of molecular properties that are currently impossible to compute.

Hamiltonian simulation, computing the time evolution of a quantum system under a given Hamiltonian, is another natural quantum computing application. The Suzuki-Trotter decomposition breaks the time evolution into small steps, each implemented by a short quantum circuit. Product formula methods, linear combination of unitaries, and qubitization provide increasingly efficient approaches to implementing these simulations. For condensed matter physics, quantum simulation can model phenomena like high-temperature superconductivity and quantum magnetism that remain poorly understood because they involve strongly correlated quantum systems that defeat classical computational methods.

Variational Quantum Algorithms

Variational algorithms are designed for the current NISQ era, when quantum processors have too many errors for deep circuits but enough qubits to explore quantum states that classical computers cannot represent. The core idea is to use a short, parameterized quantum circuit as an ansatz (trial solution), measure a cost function on the quantum processor, and use a classical optimizer to adjust the circuit parameters. This hybrid quantum-classical loop iterates until the cost function converges.

The Variational Quantum Eigensolver (VQE) finds the ground state energy of a molecular Hamiltonian by minimizing the expectation value of the Hamiltonian operator over parameterized quantum states. The quantum processor prepares a trial state and measures the energy, and the classical optimizer adjusts the circuit parameters to lower the energy toward the ground state. VQE has been demonstrated on small molecules (H2, LiH, BeH2) on real quantum hardware, though achieving chemical accuracy for molecules larger than what classical computers can already handle remains an open challenge.

The Quantum Approximate Optimization Algorithm (QAOA) addresses combinatorial optimization by encoding the objective function as a quantum operator and alternating between applying this operator and a mixing operator for a fixed number of rounds. The parameters (angles for each operator application) are optimized classically. QAOA with one round is equivalent to a simple classical heuristic, but with increasing rounds it can in principle converge to the optimal solution. Whether QAOA provides a practical advantage over classical optimization algorithms for real-world problem instances is actively debated, with theoretical and numerical evidence supporting both optimistic and pessimistic viewpoints.

The main challenge facing variational algorithms is the barren plateau problem: for many choices of circuit ansatz, the cost function landscape becomes exponentially flat as the number of qubits increases, meaning the gradients vanish and the classical optimizer cannot find a direction to improve. Strategies to mitigate barren plateaus include using physically motivated ansatze that incorporate problem structure, layer-wise training where parameters are optimized one layer at a time, and choosing cost functions with favorable gradient properties. Research into whether variational algorithms can achieve practical quantum advantage for any real-world problem is one of the most active areas in quantum computing.

Emerging Quantum Algorithms

Quantum linear algebra algorithms, beginning with the HHL algorithm (Harrow, Hassidim, Lloyd, 2009), solve systems of linear equations exponentially faster than classical methods under certain conditions. Given a system Ax = b where A is a sparse N x N matrix, the HHL algorithm produces the solution vector x encoded as a quantum state in O(log(N)) time, compared to O(N) for classical Gaussian elimination. The catch is that reading out the full solution vector requires O(N) measurements, erasing the speedup for problems where the full solution is needed. The algorithm is useful when only global properties of the solution (like the inner product of x with another vector) are needed.

Quantum random walks generalize classical random walks to quantum systems, where the walker exists in a superposition of positions and the walk dynamics create interference between paths. Quantum walks provide speedups for graph problems including element distinctness, triangle finding, and group commutativity testing. The quantum walk framework has also led to new quantum algorithms for spatial search and matrix property testing.

Quantum machine learning algorithms remain an active research frontier. Quantum kernel methods use quantum circuits to compute kernel functions in feature spaces that are exponentially large, potentially capturing complex patterns that classical kernels miss. Quantum Boltzmann machines and quantum generative adversarial networks explore whether quantum circuits can generate or learn probability distributions more efficiently than classical neural networks. The theoretical case for quantum advantage in machine learning is still being established, and demonstrating practical advantage on a meaningful machine learning benchmark has not yet been achieved.