This post explores foundational quantum algorithms developed before 2020: Shor’s exponential factoring, Grover’s search speedup, core subroutines like phase estimation, and other key methods such as Simon’s algorithm, HHL for linear systems, and hybrid approaches like VQE. These algorithms illustrate how quantum mechanics can outperform classical computation for specific tasks.

Shor’s Algorithm

Peter Shor’s algorithm (1994) factors integers in polynomial time by reducing factoring to a period-finding problem and employing the quantum Fourier transform for exponential speedup over classical methods [1]. It showed that quantum computers, in principle, could break widely used RSA encryption once sufficiently large, fault-tolerant devices exist.

Grover’s Algorithm

Lov Grover’s algorithm (1996) searches an unstructured database of size $N$ in $O(\sqrt{N})$ time, providing a quadratic speedup compared to $O(N)$ classically [2]. Though not exponential, this advantage applies broadly across search and optimization problems.

Quantum Phase Estimation (QPE)

The phase estimation algorithm estimates the eigenphase of a unitary operator to $m$ bits of precision using $O(m)$ ancilla qubits and controlled unitaries [3]. Introduced by Kitaev in 1995, QPE underpins Shor’s algorithm and many quantum simulation routines [4].

Simon’s Algorithm

Daniel Simon’s algorithm (1994) solves Simon’s problem, finding a hidden XOR mask, exponentially faster than any classical probabilistic algorithm [5]. It was the first demonstration of exponential quantum speedup in the query model and motivated the hidden subgroup framework.

HHL: Solving Linear Systems

The Harrow–Hassidim–Lloyd (HHL) algorithm (2009) solves certain sparse linear systems $A\mathbf{x}=\mathbf{b}$ in time logarithmic in the system size under ideal conditions, offering exponential speedup over classical algorithms for specific tasks [6].

Variational Quantum Eigensolver (VQE)

The VQE algorithm (2014) is a hybrid quantum-classical method for estimating ground-state energies of Hamiltonians. It uses a parameterized quantum circuit to prepare trial states and a classical optimizer to minimize the measured energy [7]. VQE is suited to noisy intermediate-scale quantum (NISQ) devices due to its relatively shallow circuits [8].

Other Notable Algorithms

  • Deutsch–Jozsa: First quantum algorithm showing deterministic separation from classical query complexity [9].
  • Bernstein–Vazirani: Finds a hidden bitstring in one query using superposition [9].
  • Amplitude Amplification: Generalizes Grover’s technique to boost success probability across diverse quantum routines [2].

References

[1] Shor, P. W. (1994). Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings 35th Annual Symposium on Foundations of Computer Science (pp. 124-134). IEEE.

[2] Grover, L. K. (1996). A fast quantum mechanical algorithm for database search. In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing (pp. 212-219).

[3] Nielsen, M. A., & Chuang, I. L. (2000). Quantum Computation and Quantum Information. Cambridge University Press.

[4] Kitaev, A. Y. (1995). Quantum measurements and the Abelian stabilizer problem. arXiv:quant-ph/9511026.

[5] Simon, D. R. (1994). On the power of quantum computation. In Proceedings 35th Annual Symposium on Foundations of Computer Science (pp. 116-123). IEEE.

[6] Harrow, A. W., Hassidim, A., & Lloyd, S. (2009). Quantum algorithm for linear systems of equations. Physical Review Letters, 103(15), 150502.

[7] Peruzzo, A., et al. (2014). A variational eigenvalue solver on a photonic quantum processor. Nature Communications, 5(1), 4213.

[8] Temme, K., Bravyi, S., & Gambetta, J. M. (2017). Error mitigation for short-depth quantum circuits. Physical Review Letters, 119(18), 180509.

[9] Deutsch, D., & Jozsa, R. (1992). Rapid solution of problems by quantum computation. Proceedings of the Royal Society of London A, 439(1907), 553-558.

[10] Preskill, J. (2018). Quantum computing in the NISQ era and beyond. Quantum, 2, 79.