Source-linked AI summary
Quantum algorithms: an overview
Ashley Montanaro
TL;DR
Quantum algorithms target computational tasks where quantum mechanics may provide speedups over classical computation, across areas including cryptography, optimisation, simulation, and linear systems. This survey organizes algorithms by application and discusses their performance, recent progress, and near-term implementations. It highlights powerful theoretical results alongside limitations from current hardware and algorithmic scope.
Problem
The paper addresses how quantum algorithms can improve computational efficiency for important tasks such as cryptography, optimisation, simulation, and solving linear systems.
Method
The paper surveys quantum algorithms with clear applications and rigorous performance bounds, emphasizing broad application-level coverage over technical detail.
Results
The survey covers quantum algorithms with theoretical advantages including Shor’s factorisation algorithm, quantum simulation, quantum walks, and algorithms for global properties of linear-system solutions.
Takeaways & Limitations
Quantum algorithms have applications across cryptography, search and optimisation, quantum simulation, and selected properties of large linear systems.
Takeaways & Limitations
Current quantum implementations generally use only a few qubits, so they are usually proofs of principle rather than demonstrations of genuine speedups over classical state of the art.
Abstract
from arXiv · showhide
Quantum computers are designed to outperform standard computers by running quantum algorithms. Areas in which quantum algorithms can be applied include cryptography, search and optimisation, simulation of quantum systems, and solving large systems of linear equations. Here we briefly survey some known quantum algorithms, with an emphasis on a broad overview of their applications rather than their technical details. We include a discussion of recent developments and near-term applications of quantum algorithms.
1 Introduction
The paper surveys quantum algorithms as a broad, active field, emphasizing algorithms with clear applications and rigorous performance bounds. It frames quantum speedup through asymptotic complexity and computational complexity classes.
- Quantum algorithms run on quantum computers and can achieve speedups or other efficiency improvements over classical algorithms.
- The survey aims to provide a broad overview of quantum algorithmics while omitting technical details and remaining necessarily non-comprehensive.The authors note that the field already includes hundreds of papers and several existing surveys.
- Measuring quantum speedup: Quantum speedup is evaluated primarily through asymptotic scaling of runtime or space with problem size.Runtime is measured by the number of elementary operations used by an algorithm.
- Measuring quantum speedup: Quantum-circuit runtime counts elementary quantum gates applied to small numbers of qubits, with performance expressed using O(f(n)) notation.O(f(n)) denotes an asymptotic upper bound by f(n).
- Complexity classes: Complexity classes group problems by difficulty, and completeness identifies problems that are among the hardest in their class.A complete problem belongs to the class and every other problem in that class reduces to it.
2 The hidden subgroup problem and applications to cryptography
The survey presents cryptographic applications of quantum algorithms through the hidden subgroup problem. Shor’s algorithm efficiently factors integers, threatening RSA, while other hidden-subgroup cases connect quantum algorithms to additional cryptosystems and open problems.
- Shor’s algorithm factors integers in time O((log N)^3), substantially faster than the best known classical method described in the survey.The classical general number field sieve is given a heuristic runtime of exp(O((log N)1/3(log log N)2/3)).
- Shor’s factorisation result implies that RSA public-key cryptography is insecure against attacks by a large quantum computer.
- The classical factorisation of a 768-bit number required approximately 10^20 operations, whereas a fault-tolerant architecture estimate uses approximately 3 × 10^11 quantum gates for a 2000-bit number.The quantum estimate also assumes approximately a billion qubits and just over a day at a 10MHz clock rate, beyond current technology.
- Shor’s approach reduces integer factorisation to a special case of the hidden subgroup problem and solves that case efficiently on a quantum computer.
- A hidden subgroup problem asks one to identify an unknown subgroup from a function that is constant on its cosets and distinct across cosets.
- Efficient hidden-subgroup algorithms for other groups could break additional cryptosystems, but polynomial-time algorithms are not currently known for the dihedral and symmetric groups.
3 Search and optimisation
Quantum search algorithms provide quadratic speedups for unstructured and heuristic search, while applications extend to NP problems, optimisation, graph problems, and pattern matching. Adiabatic approaches offer practical implementations but lack general worst-case guarantees and have unresolved speedup questions in quantum annealing.
- Search: For NP problems with certificate length m, Grover search gives O(2^m/2 poly(m)) time instead of O(2^m poly(m)) classical exhaustive search.At comparable clock speeds, this can make instances approximately twice as large solvable in comparable time.
- Search: Grover’s algorithm reduces unstructured search from 2^n classical evaluations to O(2^n/2 poly(n)) quantum runtime.The algorithm treats the evaluation function as a black-box oracle and has arbitrarily small fixed failure probability.
- Amplitude amplification: Amplitude amplification reduces heuristic-search evaluations from average O(1/ϵ) classically to O(1/√ϵ) quantumly, with failure probability arbitrarily close to zero.It repeatedly amplifies successful outcomes without requiring detailed use of the heuristic’s internal structure.
- Amplitude amplification: Applying amplitude amplification to a randomized 3-SAT algorithm changes the runtime from O((4/3)^n poly(n)) to O((4/3)^n/2 poly(n)).This illustrates a quadratic speedup applied to an existing classical heuristic rather than to exhaustive search.
- Applications: Quantum algorithms improve several combinatorial tasks, including graph connectivity in O(N^3/2) time and pattern matching with superpolynomial average-case speedup when M is large.The graph result is up to logarithmic factors; the pattern-matching comparison is against classical O(N + M) worst-case complexity and an average-case bound stated in the text.
- Adiabatic optimisation: The adiabatic algorithm targets constraint satisfaction by maximizing satisfied constraints, but lacks general rigorous worst-case upper bounds and can take exponential time on constructed instances.D-Wave systems implement related quantum annealing hardware, yet thermal states make it unclear whether the adiabatic algorithm’s predicted speedup persists.
4 Quantum simulation
Quantum simulation uses quantum computers to calculate dynamical properties of physical systems, addressing tasks whose general classical description can be exponentially complex. Digital simulation efficiently approximates evolution for many physically realistic systems, while analogue simulation directly mimics a target system with another.
- Applications: Quantum simulation applications include quantum chemistry, superconductivity, metamaterials, and high-energy physics.
- Quantum simulation: Quantum simulation calculates dynamical properties by evolving an initial state under a Hamiltonian and measuring properties of the resulting state.The target state is |ψ_t⟩ = e^−iHt|ψ⟩.
- Quantum simulation: General quantum-state descriptions have exponential complexity, and no efficient general classical algorithm for quantum simulation is known.
- Digital simulation: For many physically realistic systems with local interactions, digital quantum simulation runs in polynomial time in system size and evolution time.The algorithm produces an approximation to the evolved state, from which quantities of interest can be measured.
- Analogue simulation: Analogue quantum simulation mimics a target Hamiltonian by constructing another physical system with an approximately corresponding Hamiltonian.
5 Quantum walks
Quantum walks provide a framework for quantum algorithms that can outperform classical random walks through faster hitting or mixing. Applications include graph navigation, Boolean-formula evaluation, and speedups for Markov-chain-based search problems.
- Quantum-walk advantages: Quantum walks outperform random walks through faster hitting or faster mixing, with exponentially smaller hitting times on some graphs and at most approximately quadratic mixing-time separation.
- Graph navigation: On a glued-trees graph with a random middle cycle, a quantum walk finds the exit in O(log N) time with probability at least 1/poly(log N), whereas classical algorithms require order N^1/6 time.
- Boolean formulas: A quantum walk evaluates any Boolean formula in slightly more than O(N^1/2) operations, compared with worst-case randomized classical time of order N^0.753... for a wide class.
- Boolean formulas: The Boolean-formula algorithm uses a quantum walk on the tree representing the formula, with AND-OR trees providing a special case linked to deciding two-player-game winners.
- Markov-chain speedups: Quantum-walk analogues of Markov-chain algorithms improve dependence on the spectral parameter δ quadratically, enabling speedups for distinctness testing and triangle finding.
6 Solving linear equations and related tasks
HHL solves linear systems by producing a quantum state proportional to the solution rather than explicitly outputting every component. Under sparsity and conditioning assumptions, this yields an exponential improvement for suitable global properties and algorithmically generated systems.
- Quantum linear-system solving: HHL receives a quantum state encoding b and access to A, then outputs a quantum state approximately proportional to the solution state |x⟩.The N-dimensional state can be stored using O(log N) qubits.
- Assumptions: Efficient runtime requires sparse A, oracle-style access to its nonzero entries, and a small condition number κ.Each row contains at most d nonzero elements, with d ≪ N.
- Performance: When d and κ are small, HHL provides an exponential improvement over standard classical algorithms.
- Output limitation: Explicitly recovering all components of x generally requires order N measurements, so HHL is most useful for global properties accessible from |x⟩.Examples include determining whether two linear-equation systems have the same solution.
- Applications: HHL is likely applicable when A and b are generated algorithmically, including finite-element electromagnetic-scattering problems using a preconditioner.
7 Few-qubit applications and experimental implementations
Near-term quantum-computing applications include proof-of-principle experiments, quantum simulation, Boson Sampling, and quantum algorithmic thinking, although current devices remain too small to establish genuine speedups.
- Experimental status: Current implementations use only a few qubits, and computations up to 20–30 qubits can be readily simulated classically.Existing demonstrations should therefore usually be viewed as proofs of principle rather than genuine speedups over classical state-of-the-art.
- Quantum simulation: Quantum simulations have been implemented across essentially every quantum-computing platform, including general digital simulation with a 6-qubit ion-trap system.Some simulations may already measure properties beyond current classical simulation techniques.
- Quantum chemistry: Classical molecular simulation is limited to 50–70 spin orbitals, while approximately 100 logical qubits could enable calculations beyond classical reach.The quantum-simulation challenge is reducing the initially prohibitive polynomial simulation time.
- Boson Sampling: Boson Sampling uses linear optics to sample photon distributions conjectured to be classically hard, with several small-scale demonstrations already completed.Later work connected the task to molecular vibrations and vibronic spectra.
- Quantum algorithmic thinking: Quantum algorithmic thinking applies quantum-algorithm ideas to small-scale physical problems, such as high-precision measurement schemes based on quantum phase estimation.This approach does not require a large-scale quantum computer.
8 Zero-qubit applications
Quantum-computation ideas can be useful without a large-scale quantum computer by informing complexity analysis of quantum systems and proving limits for classical problems.
- Zero-qubit applications: Quantum-computation theory can be applied to other scientific and mathematical fields without requiring an actual large-scale quantum computer.The paper summarizes these as “zero-qubit” applications of quantum-computing ideas.
- Hamiltonian complexity: Hamiltonian complexity studies the difficulty of computing quantities about quantum-mechanical systems, including local-Hamiltonian ground-state energies.The local-Hamiltonian problem is QMA-complete, making efficient quantum or classical algorithms unlikely under the paper’s stated analogy.
- Hamiltonian complexity: Hamiltonian-complexity results have formally justified empirical observations about the relative hardness of problems in condensed-matter physics.The broader program remains incomplete.
- Classical problems: Quantum information-theoretic principles yield strong classical communication lower bounds for inner product and limitations for classical data structures, codes, and formulae.These applications use quantum information as a mathematical tool for problems that are themselves classical.
9 Outlook
The outlook emphasizes both limits on discovering stronger quantum speedups and the importance of applying existing algorithms and primitives to new problem areas.
- Open questions: Known quantum algorithms have prompted the question of why more exponential speedups are not known.The paper frames this as an open issue after surveying many algorithms and problems.
- Limits: Query-complexity lower bounds constrain quantum algorithms, including Grover’s algorithm, whose query complexity cannot be improved by even one query at the same success probability.Exponential query-complexity speedups require a property of the problem’s structure.
- Algorithmic primitives: Known algorithms rely largely on a small set of quantum primitives, including the quantum Fourier transform and quantum walks.The paper notes that any quantum circuit can be approximated using only Toffoli and Hadamard gates.
- Future research: Future progress may depend on applying known quantum algorithms and primitives to new problem areas with substantial input from practitioners in other fields.The paper identifies cross-disciplinary communication as part of this research direction.