Quantum linear systems algorithms: a primer
arXiv:1802.08227
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.
arXiv comment55 pages, 5 figures, comments welcome
References in corpus (24)
- Quantum Mechanics helps in searching for a needle in a haystack
- Measurement-based quantum computation with cluster states
- Quantum principal component analysis
- Quantum Algorithms Revisited
- Quantum algorithms: an overview
- Exponential algorithmic speedup by quantum walk
- Synthesis of Quantum Logic Circuits
- Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
- Quantum machine learning: a classical perspective
- On the relationship between continuous- and discrete-time quantum walk
- Hamiltonian simulation with nearly optimal dependence on all parameters
- Creating superpositions that correspond to efficiently integrable probability distributions
- A quantum linear system algorithm for dense matrices
- Impossibility of deleting an unknown quantum state
- Quantum Circuits for Isometries
- Quantum gradient descent for linear systems and least squares
- Concentration of the adjacency matrix and of the Laplacian in random graphs with independent edges
- Approximation by Quantum Circuits
- Universal Quantum Hamiltonians
- Quantum Perceptron Models
- Hamiltonian Simulation with Optimal Sample Complexity
- Variable time amplitude amplification and a faster quantum algorithm for solving systems of linear equations
- Hamiltonian Simulation by Uniform Spectral Amplification
- Identity check is QMA-complete
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