Quantum algorithms: A survey of applications and end-to-end complexities

Abstract

The anticipated applications of quantum computers span across science and industry, ranging from quantum chemistry and many-body physics to optimization, finance, and machine learning. Proposed quantum solutions in these areas typically combine multiple quantum algorithmic primitives into an overall quantum algorithm, which must then incorporate the methods of quantum error correction and fault tolerance to be implemented correctly on quantum hardware. As such, it can be difficult to assess how much a particular application benefits from quantum computing, as the various approaches are often sensitive to intricate technical details about the underlying primitives and their complexities. Here we present a survey of several potential application areas of quantum algorithms and their underlying algorithmic primitives, carefully considering technical caveats and subtleties. We outline the challenges and opportunities in each area in an "end-to-end" fashion by clearly defining the problem being solved alongside the input-output model, instantiating all "oracles," and spelling out all hidden costs. We also compare quantum solutions against state-of-the-art classical methods and complexity-theoretic limitations to evaluate possible quantum speedups. The survey is written in a modular, wiki-like fashion to facilitate navigation of the content. Each primitive and application area is discussed in a standalone section, with its own bibliography of references and embedded hyperlinks that direct to other relevant sections. This structure mirrors that of complex quantum algorithms that involve several layers of abstraction, and it enables rapid evaluation of how end-to-end complexities are impacted when subroutines are altered.

Survey document with wiki-like modular structure. 416 pages, including bibliography and sub-bibliographies. v2: includes updates through mid-2024 and revisions after conducting self-administered nonanonymized peer-review process. Published as open-access book by Cambridge University Press in April 2025

Cited by in corpus (32)

• Neural quantum kernels: training quantum kernels with quantum neural networks
• Benchmarking quantum gates and circuits
• In the shadow of the Hadamard test: Using the garbage state for good and further modifications
• Quantum computing for genomics: conceptual challenges and practical perspectives
• Letting the tiger out of its cage: bosonic coding without concatenation
• QSlack: A slack-variable approach for variational quantum semi-definite programming
• Quantum Circuit Design using a Progressive Widening Enhanced Monte Carlo Tree Search
• The Role of Quantum Computing in Advancing Scientific High-Performance Computing: A perspective from the ADAC Institute
• Lindblad engineering for quantum Gibbs state preparation under the eigenstate thermalization hypothesis
• Infinite quantum signal processing for arbitrary Szegő functions
• Efficient explicit circuit for quantum state preparation of piecewise continuous functions
• QKAN: quantum Kolmogorov-Arnold networks with applications in machine learning and multivariate state preparation
• Cross-platform hardware benchmark of style-based quantum GANs for data augmentation on superconducting and trapped-ion processors
• Quantum algorithms for solving a drift-diffusion equation: A complexity analysis
• Resource-Efficient Cross-Platform Verification with Modular Superconducting Devices
• Characterizing physical and logical errors in a transversal CNOT via cycle error reconstruction
• An Efficient Decomposition of the Carleman Linearized Burgers' Equation
• Extracting the spin excitation spectrum of a fermionic system using a quantum processor
• Superconducting qubits in the millions: the potential and limitations of modularity
• Fault-tolerant interfaces for modular quantum computing on diverse qubit platforms
• Phase Estimation with Compressed Controlled Time Evolution
• Demonstration of High-Fidelity Entangled Logical Qubits using Transmons
• Unified Architecture for Quantum Lookup Tables
• Ability of entanglement and purity to help to detect systematic experimental errors
• Quantum phase estimation with optimal confidence interval using three control qubits
• Vortex Detection from Quantum Data
• Accelerated spin-adapted ground state preparation with non-variational quantum algorithms
• Scalable Simulation of Fermionic Encoding Performance on Noisy Quantum Computers
• Network Requirements for Distributed Quantum Computation
• Quantum Simulation-Based Optimization for Cooling System Design
• Resource-efficient Quantum Algorithms for Selected Hamiltonian Subspace Diagonalization
• Co-Designing Spectral Transformation Oracles with Hybrid Oscillator-Qubit Quantum Processors: From Algorithms to Compilation