Quantum Algorithms

A quantum algorithm is a precise choreography of superposition, entanglement, and measurement designed to transform a hard classical task into one that yields to interference. Rather than storing bits, we prepare a wavefunction over many possibilities at once; rather than counting operations, we count how cleverly we steer amplitudes. This page surveys cornerstone ideas: period finding (Shor), amplitude amplification (Grover), and variational hybrid methods that pair classical optimizers with short quantum circuits on near-term devices.

The point is not magic speed but structure: when a problem presents symmetry (periodicity, oracles, conserved quantities), quantum mechanics lets us extract that structure more efficiently. We will keep the physics in view—unitary gates, phases, and interference—while translating those ingredients into algorithmic steps that you can simulate with Qiskit or Cirq before touching hardware.

Integer factorization is classically hard; Shor recasts it as period finding for the map \(x \mapsto a^x \bmod N\). Prepare a uniform superposition over exponents, compute \(a^x\) modulo \(N\) in a second register, and then apply the quantum Fourier transform (QFT) to the exponent register. Because modular exponentiation is periodic with unknown period \(r\), the QFT concentrates probability at frequencies near multiples of \(1/r\). Continued fractions recover \(r\) from the measured outcome, and number theory yields the factors of \(N\).

The physics view: the QFT is a phase interferometer. Modular exponentiation imprints a phase pattern indexed by the hidden period; the QFT turns that phase comb into sharp peaks. The cost is dominated by controlled multiplications and the depth of the QFT, both implementable polylogarithmically in \(N\) with fault-tolerant gates. On NISQ devices we simulate reduced instances to study precision, noise, and resource trade-offs.

Grover’s algorithm searches an unstructured database of \(N\) items for a marked element using only \(\mathcal{O}(\sqrt{N})\) oracle queries. Start in uniform superposition, apply a phase flip to marked states (the oracle), then reflect about the mean (the diffuser). The two reflections rotate the state vector within a two-dimensional subspace toward the marked subspace by an angle \(2\theta\) each iteration; after roughly \(\frac{\pi}{4}\sqrt{N/M}\) iterations (for \(M\) marked items) the success probability peaks.

The governing physics is simple geometry: interference causes constructive growth of the marked amplitudes and destructive cancellation elsewhere. Implementations vary—multi-controlled phase gates, ancilla-based oracles, or phase-kickback constructions—but the core is a clean, analyzable rotation. Variants include fixed-point Grover (avoids overshoot), quantum counting (estimates \(M\)), and amplitude estimation (quadratic speedup for Monte Carlo).

Variational quantum algorithms (VQAs) pair shallow, parameterized circuits with classical optimizers. In the Variational Quantum Eigensolver (VQE), a circuit \(U(\boldsymbol{\theta})\) prepares a trial state; measuring \(H\) gives an energy estimate; a classical routine updates \(\boldsymbol{\theta}\) to minimize \(\langle H \rangle\). Quantum Approximate Optimization Algorithm (QAOA) alternates problem and mixing unitaries tuned by angles \((\gamma,\beta)\). These methods trade asymptotic guarantees for practicality on noisy devices, making ansatz design, gradient estimation, and error mitigation central concerns.

From a physics angle, VQAs are controllable interferometers whose parameters sculpt entanglement and locality. From a computational angle, they are stochastic, high-variance optimizations sensitive to barren plateaus. Effective practice uses symmetries to restrict ansätze, natural-gradient updates, and measurement-frugal estimators (grouped Pauli terms, shadow tomography).