Quantum linear systems algorithms: a primer

Abstract

The Harrow-Hassidim-Lloyd (HHL) quantum algorithm for sampling from the solution of a linear system provides an exponential speed-up over its classical counterpart. The problem of solving a system of linear equations has a wide scope of applications, and thus HHL constitutes an important algorithmic primitive. In these notes, we present the HHL algorithm and its improved versions in detail, including explanations of the constituent sub- routines. More specifically, we discuss various quantum subroutines such as quantum phase estimation and amplitude amplification, as well as the important question of loading data into a quantum computer, via quantum RAM. The improvements to the original algorithm exploit variable-time amplitude amplification as well as a method for implementing linear combinations of unitary operations (LCUs) based on a decomposition of the operators using Fourier and Chebyshev series. Finally, we discuss a linear solver based on the quantum singular value estimation (QSVE) subroutine.

55 pages, 5 figures, comments welcome

References in corpus (5)

• Exponential algorithmic speedup by quantum walk
• Synthesis of Quantum Logic Circuits
• Creating superpositions that correspond to efficiently integrable probability distributions
• Variable time amplitude amplification and a faster quantum algorithm for solving systems of linear equations
• Hamiltonian Simulation by Uniform Spectral Amplification

Cited by in corpus (22)

• Robust data encodings for quantum classifiers
• A Comparison of Various Classical Optimizers for a Variational Quantum Linear Solver
• Universal discriminative quantum neural networks
• An improved quantum-inspired algorithm for linear regression
• Step-by-Step HHL Algorithm Walkthrough to Enhance the Understanding of Critical Quantum Computing Concepts
• An Application of Quantum Annealing Computing to Seismic Inversion
• Quantum Circuit Design Methodology for Multiple Linear Regression
• Quantum algorithms for scientific computing
• Experimental Quantum Computing to Solve Network DC Power Flow Problem
• Quantum-classical algorithms for skewed linear systems with optimized Hadamard test
• Quantum diffusion map for nonlinear dimensionality reduction
• Quantum Computing Solution of DC Power Flow
• Asymptotically Optimal Circuit Depth for Quantum State Preparation and General Unitary Synthesis
• Solving the Hele-Shaw flow using the Harrow-Hassidim-Lloyd algorithm on superconducting devices: A study of efficiency and challenges
• Quantum locally linear embedding for nonlinear dimensionality reduction
• On Solving Linear Systems in Sublinear Time
• Quantum Pattern Detection: Accurate State- and Circuit-based Analyses
• Quantum Machine Learning For Classical Data
• Combinatorial Potential of Random Equations with Mixture Models: Modeling and Simulation
• Towards a Pattern Language for Quantum Algorithms
• Fundamental Machine Learning Routines as Quantum Algorithms on a Superconducting Quantum Computer
• Solving the Nonlinear Vlasov Equation on a Quantum Computer