Quantum algorithm for systems of linear equations with exponentially improved dependence on precision

Abstract

Harrow, Hassidim, and Lloyd showed that for a suitably specified $N\times N$ matrix $A$ and $N$-dimensional vector $\vec{b}$, there is a quantum algorithm that outputs a quantum state proportional to the solution of the linear system of equations $A\vec{x}=\vec{b}$. If $A$ is sparse and well-conditioned, their algorithm runs in time $\mathrm{poly}(\log N,1/\epsilon )$, where $\epsilon$ is the desired precision in the output state. We improve this to an algorithm whose running time is polynomial in $\log (1/\epsilon )$, exponentially improving the dependence on precision while keeping essentially the same dependence on other parameters. Our algorithm is based on a general technique for implementing any operator with a suitable Fourier or Chebyshev series representation. This allows us to bypass the quantum phase estimation algorithm, whose dependence on $\epsilon$ is prohibitive.

v1: 28 pages; v2: 31 pages, minor change to title, various minor changes and clarifications in response to referee comments

References in corpus (6)

• Quantum algorithm for solving linear systems of equations
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Synthesis of Quantum Logic Circuits
• Quantum algorithms and the finite element method
• Variable time amplitude amplification and a faster quantum algorithm for solving systems of linear equations
• Quantum Merlin Arthur with Exponentially Small Gap

Cited by in corpus (309)

• Variational Quantum Algorithms
• Noisy intermediate-scale quantum (NISQ) algorithms
• Hamiltonian Simulation by Qubitization
• Quantum computing for finance: overview and prospects
• Large-scale silicon quantum photonics implementing arbitrary two-qubit processing
• Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
• Quantum machine learning: a classical perspective
• A Review on Quantum Approximate Optimization Algorithm and its Variants
• Variational quantum algorithms for nonlinear problems
• Efficient quantum algorithm for dissipative nonlinear differential equations
• Variational quantum simulation of general processes
• A quantum linear system algorithm for dense matrices
• Variational Quantum Linear Solver
• Solving nonlinear differential equations with differentiable quantum circuits
• Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing
• Variational algorithms for linear algebra
• Challenges and Opportunities in Quantum Optimization
• Near-optimal ground state preparation
• Quantum State Preparation with Optimal Circuit Depth: Implementations and Applications
• Quantum gradient descent for linear systems and least squares
• Quantum Variational Autoencoder
• High-precision quantum algorithms for partial differential equations
• Quantum Algorithm for Simulating the Wave Equation
• Large gradients via correlation in random parameterized quantum circuits
• Efficient phase-factor evaluation in quantum signal processing
• Ground state preparation and energy estimation on early fault-tolerant quantum computers via quantum eigenvalue transformation of unitary matrices
• On the impact of quantum computing technology on future developments in high-performance scientific computing
• Machine learning method for state preparation and gate synthesis on photonic quantum computers
• Variational Quantum algorithm for Poisson equation
• Black-box quantum state preparation without arithmetic
• Optimizing quantum optimization algorithms via faster quantum gradient computation
• Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems
• Emergent quantum state designs from individual many-body wavefunctions
• Quantum assisted Gaussian process regression
• Quantum Power Method by a Superposition of Time-Evolved States
• Improved quantum algorithms for linear and nonlinear differential equations
• A comprehensive review of Quantum Machine Learning: from NISQ to Fault Tolerance
• Hamiltonian simulation in the low-energy subspace
• Biology and medicine in the landscape of quantum advantages
• Quantum algorithm for non-homogeneous linear partial differential equations
• Fast inversion, preconditioned quantum linear system solvers, and fast evaluation of matrix functions
• Universal discriminative quantum neural networks
• Quantum simulation of partial differential equations via Schrodingerisation: technical details
• Quantum-centric Supercomputing for Materials Science: A Perspective on Challenges and Future Directions
• Quantum SDP-Solvers: Better upper and lower bounds
• Product Decomposition of Periodic Functions in Quantum Signal Processing
• The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation
• Linear combination of Hamiltonian simulation for nonunitary dynamics with optimal state preparation cost
• Provably accurate simulation of gauge theories and bosonic systems
• Quantum Simulation of the Sachdev-Ye-Kitaev Model by Asymmetric Qubitization
• NISQ Computers: A Path to Quantum Supremacy
• Variational Quantum Singular Value Decomposition
• Quantum Spectral Clustering
• Single-particle digitization strategy for quantum computation of a ${\varphi }^4$ scalar field theory
• Variational quantum algorithm based on the minimum potential energy for solving the Poisson equation
• Quantum Algorithm for the Vlasov Equation
• Benchmarking Adversarially Robust Quantum Machine Learning at Scale
• Preparation of excited states for nuclear dynamics on a quantum computer
• Time-marching based quantum solvers for time-dependent linear differential equations
• Quantum Fast Poisson Solver: the algorithm and modular circuit design
• Quantum linear systems algorithms: a primer
• Quantum Algorithms for Estimating Physical Quantities using Block-Encodings
• Asymptotic Quantum Algorithm for the Toeplitz Systems
• Variational Quantum Solutions to the Advection-Diffusion Equation for Applications in Fluid Dynamics
• On applications of quantum computing to plasma simulations
• Quantum inverse iteration algorithm for programmable quantum simulators
• Efficient Fully-Coherent Quantum Signal Processing Algorithms for Real-Time Dynamics Simulation
• Exponential quantum speedup in simulating coupled classical oscillators
• Quantum-accelerated multilevel Monte Carlo methods for stochastic differential equations in mathematical finance
• Generalized quantum circuit differentiation rules
• Time complexity analysis of quantum algorithms via linear representations for nonlinear ordinary and partial differential equations
• Variational Quantum Computation of Molecular Linear Response Properties on a Superconducting Quantum Processor
• Quantum algorithm for the Navier Stokes equations by using the streamfunction vorticity formulation and the lattice Boltzmann method
• Graph isomorphism and Gaussian boson sampling
• Computing Ground State Properties with Early Fault-Tolerant Quantum Computers
• Enhancing the Quantum Linear Systems Algorithm using Richardson Extrapolation
• Quantum computation of molecular response properties
• Quantum simulation of partial differential equations via Schrodingerisation
• Hybrid quantum algorithms for flow problems
• Fast-forwarding quantum evolution
• Spectral density estimation with the Gaussian Integral Transform
• Machine learning \& artificial intelligence in the quantum domain
• A variational quantum eigensolver for dynamic correlation functions
• Quantum phase estimation for a class of generalized eigenvalue problems
• Configurable sublinear circuits for quantum state preparation
• Quantum algorithms and lower bounds for convex optimization
• Linear embedding of nonlinear dynamical systems and prospects for efficient quantum algorithms
• Efficient quantum amplitude encoding of polynomial functions
• Lattice Boltzmann-Carleman quantum algorithm and circuit for fluid flows at moderate Reynolds number
• Quantum algorithms for approximate function loading
• Quantum algorithm for persistent Betti numbers and topological data analysis
• Finding Angles for Quantum Signal Processing with Machine Precision
• Quantum Computing for Fusion Energy Science Applications
• Random circuit block-encoded matrix and a proposal of quantum LINPACK benchmark
• FABLE: Fast Approximate Quantum Circuits for Block-Encodings
• New Quantum Algorithms for Computing Quantum Entropies and Distances
• Approximate Quantum Circuit Synthesis using Block-Encodings
• Quantum Computing: Lecture Notes
• Implementing any Linear Combination of Unitaries on Intermediate-term Quantum Computers
• Two quantum algorithms for solving the one-dimensional advection-diffusion equation
• Box algorithm for the solution of differential equations on a quantum annealer
• Quantum Differentially Private Sparse Regression Learning
• FEqa: Finite Element Computations on Quantum Annealers
• Quantum Circulant Preconditioner for Linear System of Equations
• An Application of Quantum Annealing Computing to Seismic Inversion
• Exact gate decompositions for photonic quantum computing
• Lanczos recursion on a quantum computer for the Green's function and ground state
• Noisy intermediate-scale quantum simulation of the one-dimensional wave equation
• Quantum algorithms from fluctuation theorems: Thermal-state preparation
• Hamiltonian operator approximation for energy measurement and ground state preparation
• Quantum Algorithm for Solving the Advection Equation using Hamiltonian Simulation
• Towards Quantum Computational Mechanics
• Hybrid classical-quantum linear solver using Noisy Intermediate-Scale Quantum machines
• Sublinear quantum algorithms for training linear and kernel-based classifiers
• Continuous-variable quantum Gaussian process regression and quantum singular value decomposition of non-sparse low rank matrices
• Linear-depth quantum circuits for loading Fourier approximations of arbitrary functions
• An efficient quantum algorithm for preparation of uniform quantum superposition states
• Quantum algorithm for time-dependent differential equations using Dyson series
• Potential quantum advantage for simulation of fluid dynamics
• Computing partition functions in the one clean qubit model
• Quantum Circuits for partial differential equations via Schrödingerisation
• Stable factorization for phase factors of quantum signal processing
• Dyson Maps and Unitary Evolution for Maxwell Equations in Tensor Dielectric Media
• Quantum Computing and Preconditioners for Hydrological Linear Systems
• Selected topics of quantum computing for nuclear physics
• Scalable Benchmarks for Gate-Based Quantum Computers
• Fragmented imaginary-time evolution for early-stage quantum signal processors
• Hamiltonian simulation for hyperbolic partial differential equations by scalable quantum circuits
• Quantum Interior Point Methods for Semidefinite Optimization
• Hamiltonian simulation with nearly optimal dependence on spectral norm
• Continuous-variable assisted thermal quantum simulation
• Quantum Regularized Least Squares
• Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra
• Time complexity analysis of quantum difference methods for linear high dimensional and multiscale partial differential equations
• Quantum Algorithms to Matrix Multiplication
• Enabling Large-Scale and High-Precision Fluid Simulations on Near-Term Quantum Computers
• Incompressible Navier-Stokes solve on noisy quantum hardware via a hybrid quantum-classical scheme
• Perturbation theory with quantum signal processing
• Quantum Circuit Design Methodology for Multiple Linear Regression
• Circuit complexity of quantum access models for encoding classical data
• A hybrid quantum-classical framework for computational fluid dynamics
• Importance of the spectral gap in estimating ground-state energies
• On efficient quantum block encoding of pseudo-differential operators
• Quantum linear system solver based on time-optimal adiabatic quantum computing and quantum approximate optimization algorithm
• Quantum advantage for differential equation analysis
• Protocol for implementing quantum nonparametric learning with trapped ions
• Quantum computation of nuclear observables involving linear combination of unitary operators
• Simulating fluid flows with quantum computing
• End-to-end resource analysis for quantum interior point methods and portfolio optimization
• Block-encoding dense and full-rank kernels using hierarchical matrices: applications in quantum numerical linear algebra
• Randomized Row and Column Iterative Methods with a Quantum Computer
• Compact quantum algorithms for time-dependent differential equations
• Quantum algorithms for scientific computing
• Quantum computation of molecular structure using data from challenging-to-classically-simulate nuclear magnetic resonance experiments
• Quantum exploration algorithms for multi-armed bandits
• Quantum algorithm for partial differential equations of non-conservative systems with spatially varying parameters
• Complexity of quantum state verification in the quantum linear systems problem
• Quantum algorithms for computing observables of nonlinear partial differential equations
• On quantum algorithms for the Schrödinger equation in the semi-classical regime
• A Quantum Interior-Point Predictor-Corrector Algorithm for Linear Programming
• Large-scale quantum hybrid solution for linear systems of equations
• A Quantum Model for Multilayer Perceptron
• Quantum differential equation solvers: limitations and fast-forwarding
• Quantum-classical algorithms for skewed linear systems with optimized Hadamard test
• Effects of Cosine Tapering Window on Quantum Phase Estimation
• Quantum Computing Perspective for Electromagnetic Wave Propagation in Cold Magnetized Plasmas
• Quantum-Inspired Classical Algorithms for Singular Value Transformation
• Harrow-Hassidim-Lloyd algorithm without ancilla postselection
• Fast Black-Box Quantum State Preparation Based on Linear Combination of Unitaries
• A quantum active learning algorithm for sampling against adversarial attacks
• A quantum annealing-sequential quadratic programming assisted finite element simulation for non-linear and history-dependent mechanical problems
• Discriminating Quantum States with Quantum Machine Learning
• A quantum algorithm for the linear Vlasov equation with collisions
• Limitations for Quantum Algorithms to Solve Turbulent and Chaotic Systems
• Hamiltonian simulation for low-energy states with optimal time dependence
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms
• Explicit Quantum Circuit for Simulating the Advection-Diffusion-Reaction Dynamics
• Highly optimized quantum circuits synthesized via data-flow engines
• Experimental Quantum Learning of a Spectral Decomposition
• Implementing smooth functions of a Hermitian matrix on a quantum computer
• Efficient Quantum Circuits for Accurate State Preparation of Smooth, Differentiable Functions
• Quantum state preparation for multivariate functions
• Quantum Computing for Software Engineering: Prospects
• Calculating the many-body density of states on a digital quantum computer
• Parallel Quantum Algorithm for Hamiltonian Simulation
• On proving the robustness of algorithms for early fault-tolerant quantum computers
• Quantum Quantitative Trading: High-Frequency Statistical Arbitrage Algorithm
• Quantum Simulation of Bound State Scattering
• Quantum Algorithm for Solving a Quadratic Nonlinear System of Equations
• Quantum algorithm for linear non-unitary dynamics with near-optimal dependence on all parameters
• Simulation of linear non-Hermitian boundary-value problems with quantum singular value transformation
• A quantum algorithm for simulating non-sparse Hamiltonians
• Quantum simulation of discrete linear dynamical systems and simple iterative methods in linear algebra via Schrodingerisation
• An Improved Method for Quantum Matrix Multiplication
• Faster spectral density calculation using energy moments
• Tight Bound for Estimating Expectation Values from a System of Linear Equations
• Quantum Carleman linearisation efficiency in nonlinear fluid dynamics
• Black-Box Quantum State Preparation with Inverse Coefficients
• Design nearly optimal quantum algorithm for linear differential equations via Lindbladians
• Quantum Finite Volume Method for Computational Fluid Dynamics with Classical Input and Output
• Quantum algorithms for group convolution, cross-correlation, and equivariant transformations
• Quantum Algorithms for Boolean Equation Solving and Quantum Algebraic Attack on Cryptosystems
• Accelerating Quantum Algorithms with Precomputation
• Solving the Hele-Shaw flow using the Harrow-Hassidim-Lloyd algorithm on superconducting devices: A study of efficiency and challenges
• Hybrid quantum-classical unsupervised data clustering based on the self-organizing feature map
• Deep Quantum Circuit Simulations of Low-Energy Nuclear States
• Quantum Algorithms for Geologic Fracture Networks
• Limitations of the Macaulay matrix approach for using the HHL algorithm to solve multivariate polynomial systems
• Observability of fidelity decay at the Lyapunov rate in few-qubit quantum simulations
• End-to-end complexity for simulating the Schwinger model on quantum computers
• Solving Differential-Algebraic Equations in Power System Dynamic Analysis with Quantum Computing
• Simulations of Future Particle Accelerators: Issues and Mitigations
• Quantum Algorithm For Estimating Eigenvalue
• Solving Differential-Algebraic Equations in Power System Dynamic Analysis with Quantum Computing
• Halving the Cost of Quantum Algorithms with Randomization
• Quantum simulation of dissipation for Maxwell equations in dispersive media
• Universal Counterdiabatic Driving
• Quantum Power Flows: From Theory to Practice
• Quantum Newton's method for solving system of nonlinear algebraic equations
• Quantum algorithms for powering stable Hermitian matrices
• Probabilistic state synthesis based on optimal convex approximation
• A Quantum Algorithm Framework for Discrete Probability Distributions with Applications to Rényi Entropy Estimation
• An Early Investigation of the HHL Quantum Linear Solver for Scientific Applications
• The discrete adiabatic quantum linear system solver has lower constant factors than the randomized adiabatic solver
• Quantum Algorithm for Estimating Betti Numbers Using Cohomology Approach
• Randomized semi-quantum matrix processing
• A Quantum Algorithm for Dynamic Mode Decomposition Integrated with a Quantum Differential Equation Solver
• Pricing multi-asset derivatives by finite difference method on a quantum computer
• Quantum algorithms for spectral sums
• Dictionary-based Block Encoding of Sparse Matrices with Low Subnormalization and Circuit Depth
• Ground state-based quantum feature maps
• Ladder Operator Block-Encoding
• Decomposition of high-rank factorized unitary coupled-cluster operators using ancilla and multi-qubit controlled low-rank counterparts
• Quantum Annealing based Power Grid Partitioning for Parallel Simulation
• Quantum algorithms for calculating determinant and inverse of matrix and solving linear algebraic systems
• Hamiltonian Learning via Shadow Tomography of Pseudo-Choi States
• Constructing Local Bases for a Deep Variational Quantum Eigensolver for Molecular Systems
• Quantum algorithms for linear and non-linear fractional reaction-diffusion equations
• Quantum channel decomposition with pre- and post-selection
• Quantum Iterative Methods for Solving Differential Equations with Application to Computational Fluid Dynamics
• Tensor-Programmable Quantum Circuits for Solving Differential Equations
• Quantum algorithms for solving a drift-diffusion equation: A complexity analysis
• Quantum Algorithm for Optimization and Polynomial System Solving over Finite Field and Application to Cryptanalysis
• qlbm -- A Quantum Lattice Boltzmann Software Framework
• Efficient explicit circuit for quantum state preparation of piecewise continuous functions
• Sample Complexity of Black Box Work Extraction
• Quantum Algorithm for Radiative Transfer Equation
• Faster Coherent Quantum Algorithms for Phase, Energy, and Amplitude Estimation
• Correspondence between open bosonic systems and stochastic differential equations
• Double-bracket algorithm for quantum signal processing without post-selection
• Multidimensional Quantum Generative Modeling by Quantum Hartley Transform
• Quantum Register Machine: Efficient Implementation of Quantum Recursive Programs
• Quantum circuits for partial differential equations in Fourier space
• Quantum homotopy perturbation method for nonlinear dissipative ordinary differential equations
• Quantum Realization of the Finite Element Method
• Quantum Lower Bounds by Sample-to-Query Lifting
• A quantum-inspired algorithm for approximating statistical leverage scores
• Integrating Quantum Algorithms Into Classical Frameworks: A Predictor-corrector Approach Using HHL
• Quantum Calculation for Two-Stream Instability and Advection Test of Vlasov-Maxwell Equations: Numerical Evaluation of Hamiltonian Simulation
• Quantum many-body simulation of finite-temperature systems with sampling a series expansion of a quantum imaginary-time evolution
• On solving classes of positive-definite quantum linear systems with quadratically improved runtime in the condition number
• Entanglement Properties of Quantum Superpositions of Smooth, Differentiable Functions
• A Quantum-Inspired Algorithm for Wave Simulation Using Tensor Networks
• An Efficient Decomposition of the Carleman Linearized Burgers' Equation
• On Solving Linear Systems in Sublinear Time
• Tight Quantum Depth Lower Bound for Solving Systems of Linear Equations
• Expanding Hardware-Efficiently Manipulable Hilbert Space via Hamiltonian Embedding
• Topological Signal Processing on Quantum Computers for Higher-Order Network Analysis
• Quantum computation of nonlinear maps
• Quantum Machine Learning For Classical Data
• Block Lanczos method for excited states on a quantum computer
• Warm-Start Variational Quantum Policy Iteration
• Integrating Quantum Algorithms with Gravitational-Wave Metrology for Enhanced Signal Detection
• Refined Criteria for QRAM Error Suppression via Efficient Large-Scale QRAM Simulator
• Discontinuous Galerkin method with Voronoi partitioning for Quantum Simulation of Chemistry
• State preparation and evolution in quantum computing: a perspective from Hamiltonian moments
• End-to-End Quantum Algorithm for Topology Optimization in Structural Mechanics
• Quantum Amplitude Arithmetic
• Range dependent Hamiltonian Algorithm for numerical QUBO formulation
• Quantum algorithm for PageRank computation through multistep quantum resonant transitions
• Optimizing Quantum Chemistry Simulations with a Hybrid Quantization Scheme
• Quantum approximated cloning-assisted density matrix exponentiation
• Quantum linear system algorithm with optimal queries to initial state preparation
• Resource-efficient quantum algorithm for linear systems of equations
• Detailed Account of Complexity for Implementation of Some Gate-Based Quantum Algorithms
• Quantum community detection via deterministic elimination
• Improving quantum linear system solvers via a gradient descent perspective
• Quantum Signal Processing and Quantum Singular Value Transformation on $U(N)$
• Quantum Simulation via Stochastic Combination of Unitaries
• Quantum Algorithms for Unsupervised Machine Learning and Neural Networks
• Quantum Algorithm for Matrix Logarithm by Integral Formula
• Two Variations of Quantum Phase Estimation for Reducing Circuit Error Rates: Application to the Harrow--Hassidim--Lloyd Algorithm
• Vortex Detection from Quantum Data
• Block Encoding of Sparse Matrices via Coherent Permutation
• Quantum Simulation-Based Optimization for Cooling System Design
• Quantum Encoding of Structured Data with Matrix Product States
• Preconditioned Block Encodings for Quantum Linear Systems
• QAFE${}^2$: Quantum accelerated multiscale finite element analysis
• Quantum state preparation with multiplicative amplitude transduction
• Optical Quantum Computing
• POPQC: Parallel Optimization for Quantum Circuits (Extended Version)
• Numerical investigation of the quantum inverse algorithm on small molecules
• Quantum Algorithm For Solving Nonlinear Algebraic Equations
• An efficient explicit implementation of a near-optimal quantum algorithm for simulating linear dissipative differential equations
• Quantum multi-row iteration algorithm for linear systems with non-square coefficient matrices
• Quantum relaxed row and column iteration methods based on block-encoding
• Creation of Wave Packets for Quantum Chromodynamics on Quantum Computers
• Schmidt quantum compressor
• Randomized adiabatic quantum linear solver algorithm with optimal complexity scaling and detailed running costs