Quantum Algorithms

The Algorithm Landscape

Where quantum beats classical

Not all problems benefit from quantum computing. This module maps the landscape of quantum speedups, introduces complexity classes like BQP, and explains when quantum algorithms truly excel.

Deutsch-Jozsa & Bernstein-Vazirani

The first quantum speedups

The Deutsch-Jozsa and Bernstein-Vazirani algorithms were among the first to demonstrate quantum speedup. Though their practical applications are limited, they beautifully illustrate the power of quantum parallelism and interference.

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.

Shor's Factoring Algorithm

Breaking RSA with quantum mechanics

Shor's algorithm factors integers in polynomial time, an exponential speedup over the best-known classical algorithms. It threatens RSA encryption and demonstrates the profound power of quantum computing.

Quantum Simulation

Feynman's original vision

Quantum simulation was Richard Feynman's original motivation for quantum computing. Simulating quantum systems is exponentially hard for classical computers but natural for quantum ones.

Quantum Machine Learning

When quantum meets neural networks

Quantum machine learning explores how quantum computers can accelerate or enhance machine learning tasks. This module covers variational quantum circuits, quantum kernels, and the current state of the field.

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.

Shor's algorithm factors integers in polynomial time, offering an exponential speedup over the best known classical algorithms. It poses a fundamental threat to RSA encryption and remains the most celebrated example of quantum computational advantage.

Quantum simulators leverage quantum mechanics itself to model molecular and material systems. Algorithms like Trotterization and Quantum Phase Estimation enable simulations that are intractable for even the most powerful classical supercomputers.

Variational Quantum Eigensolver (VQE) and Quantum Approximate Optimization Algorithm (QAOA) are hybrid quantum-classical algorithms designed for near-term quantum devices. They use short quantum circuits evaluated on quantum hardware, with classical optimizers tuning the parameters.

Quantum Machine Learning explores how quantum computers can accelerate learning tasks. Quantum neural networks, kernel methods, and generative models leverage high-dimensional Hilbert spaces to potentially recognize patterns intractable for classical systems.

Quantum error correction algorithms protect fragile quantum information from decoherence and gate errors. Surface codes, color codes, and neural network decoders form the algorithmic backbone of fault-tolerant quantum computing.

The Deutsch-Jozsa algorithm was one of the first quantum algorithms to demonstrate an exponential speedup over any deterministic classical algorithm. Given a black-box function promised to be either constant (same output for all inputs) or balanced (outputs 0 for half the inputs and 1 for the other half), it determines which with just a single query.

The Bernstein-Vazirani algorithm finds an unknown n-bit binary string hidden inside a black-box oracle using just one quantum query. Classically, n queries are necessary in the worst case, giving the algorithm a provable linear speedup that generalizes the ideas of Deutsch-Jozsa to a natural learning problem.

Simon's algorithm finds a hidden period s of a function f: {0,1}^n → {0,1}^n promised to be periodic under bitwise XOR. It runs in polynomial time on a quantum computer, while the best classical algorithms require exponentially many queries. Simon's algorithm was a direct precursor to Shor's factoring algorithm.

Quantum teleportation is a protocol for transferring an arbitrary quantum state from one location to another using a shared entangled pair and a classical communication channel. It demonstrates that entanglement plus classical bits can replace a direct quantum transmission, and it underpins many quantum networking and error-correction protocols.

Superdense coding is a quantum communication protocol that allows Alice to send two classical bits to Bob by transmitting only one qubit, provided they share a maximally entangled Bell pair beforehand. It is the conceptual inverse of quantum teleportation and demonstrates how entanglement can double the classical capacity of a quantum channel.

The Quantum Fourier Transform (QFT) is the quantum analogue of the classical discrete Fourier transform (DFT), and it serves as the backbone of many of the most important quantum algorithms, including Shor's factoring algorithm and quantum phase estimation. While the classical DFT requires O(N log N) operations using the Fast Fourier Transform, the QFT achieves an exponential speedup, requiring only O((log N)^2) quantum gates. The QFT maps quantum states from the computational basis to the Fourier basis by applying a carefully structured sequence of Hadamard gates and controlled phase rotations.

Quantum Phase Estimation (QPE) is a fundamental quantum algorithm that determines the eigenvalue phase of a unitary operator given access to one of its eigenvectors. It serves as a critical subroutine in quantum counting, the HHL algorithm for linear systems, and quantum chemistry simulations where molecular energy levels must be computed. By combining controlled unitary operations with the inverse Quantum Fourier Transform, QPE achieves an exponential advantage in precision over any classical sampling-based approach.

Quantum Counting combines the quadratic speedup of Grover's search algorithm with the precision of Quantum Phase Estimation to estimate the number of solutions to a search problem without explicitly finding them. Given an unstructured database of N items and a predicate function marking M solutions, this algorithm determines M in O(sqrt(N)) time, providing an exponential improvement over classical counting for large databases. It is an essential tool in quantum search theory, optimization, and constraint satisfaction problems.

Quantum walks are the quantum mechanical analogues of classical random walks, where a walker evolves according to unitary dynamics rather than stochastic transitions. They exhibit fundamentally different behavior from their classical counterparts, including ballistic propagation rather than diffusive spreading, and they can provide polynomial and even exponential speedups for certain search and sampling problems. Quantum walks underpin some of the most powerful quantum algorithms for element distinctness, spatial search, and simulation of quantum physical systems.

The Harrow-Hassidim-Lloyd (HHL) algorithm solves systems of linear equations Ax = b on a quantum computer with an exponential speedup over classical methods for certain classes of sparse, well-conditioned matrices. It combines Quantum Phase Estimation, controlled Hamiltonian simulation, and conditional rotation to encode the solution vector x into a quantum state. The algorithm is a cornerstone of quantum machine learning and scientific computing, though it produces a quantum state rather than the full classical vector, limiting its direct applicability.

Quantum Support Vector Machines leverage quantum feature maps to compute kernel functions that may be intractable for classical computers. By estimating kernel entries on a quantum device and feeding them into a classical SVM optimizer, the algorithm achieves a powerful hybrid approach to classification.

Quantum Generative Adversarial Networks combine a quantum generator, which prepares a data distribution as a quantum state, with a classical discriminator that distinguishes real from fake samples. This hybrid architecture can learn probability distributions with fewer parameters than fully classical GANs.

BB84, proposed by Bennett and Brassard in 1984, is the first quantum key distribution protocol. It exploits the no-cloning theorem and the fact that measuring a quantum state disturbs it, enabling two parties to detect eavesdropping while establishing a shared secret key.

Quantum Kernel Estimation computes the similarity between data points by encoding them into quantum states and estimating their overlap. For carefully designed feature maps, this overlap can encode correlations that are exponentially hard to compute classically, offering a pathway to quantum advantage in machine learning.

Quantum Principal Component Analysis leverages quantum algorithms to extract the principal components of a density matrix exponentially faster than classical PCA for low-rank approximations. By treating the covariance matrix as a quantum state, QPCA can reveal dominant eigenvectors and eigenvalues using quantum phase estimation.

The Quantum Adiabatic Algorithm exploits the adiabatic theorem of quantum mechanics to evolve a quantum system from the ground state of a simple, initial Hamiltonian to the ground state of a complex problem Hamiltonian. By varying the Hamiltonian sufficiently slowly, the system remains in its instantaneous ground state throughout the evolution, ultimately encoding the solution to an optimization problem in the final quantum state. This framework naturally connects to quantum annealing and represents one of the earliest proposed models for quantum-enhanced computation.

The Swap Test is a fundamental quantum primitive that measures the overlap, or fidelity, between two quantum states without requiring full state tomography. By interfering a control qubit with the swapped states of two registers, the test extracts the squared inner product |\langle \phi | \psi \rangle|^2 through simple projective measurements on the ancilla. This protocol underpins numerous quantum machine learning algorithms, state comparison tasks, and quantum fingerprinting schemes.

The Hadamard Test provides a method to estimate the expectation value \langle \psi | \hat{U} | \psi \rangle of a unitary operator \hat{U} with respect to a quantum state |\psi\rangle by introducing a single ancilla qubit and performing Hadamard-controlled operations. By measuring the ancilla in different bases, one can extract both the real and imaginary parts of complex expectation values. This test is foundational for quantum phase estimation, quantum chemistry simulations, and variational algorithms requiring expectation value estimation.

The Quantum Natural Gradient optimizer generalizes classical natural gradient descent to the quantum regime by accounting for the non-Euclidean geometry of parameterized quantum states through the Fubini-Study metric tensor. Unlike vanilla gradient descent, which treats parameter space as flat, QNG uses the Quantum Fisher Information matrix to rescale update directions according to the state's local curvature. This approach often yields faster convergence and more stable optimization landscapes in variational quantum algorithms.

The Quantum Approximate Optimization Algorithm is a variational hybrid quantum-classical protocol specifically designed to tackle combinatorial optimization problems such as Max-Cut by alternating between problem-specific cost Hamiltonians and uniform mixing operators. Its p-layer ansatz interpolates between the quantum approximate optimization regime and adiabatic quantum computing as the depth p increases, with bounded approximation ratios for certain graph families. QAOA has become a flagship NISQ algorithm for demonstrating quantum advantage in structured optimization landscapes.

Explore how variational algorithms power quantum neural networks.

Learn about surface codes and neural network decoders.

Discover the hardware platform that brings algorithms to life.