A quantum linear system algorithm for dense matrices

Abstract

Solving linear systems of equations is a frequently encountered problem in machine learning and optimisation. Given a matrix $A$ and a vector $\mathbf{b}$ the task is to find the vector $\mathbf{x}$ such that $A\mathbf{x}=\mathbf{b}$. We describe a quantum algorithm that achieves a sparsity-independent runtime scaling of $\mathcal{O}({\kappa }^2\Vert A{\Vert }_F\text{polylog}(n)/\epsilon )$, where $n\times n$ is the dimensionality of $A$ with Frobenius norm $\Vert A{\Vert }_F$, $\kappa$ denotes the condition number of $A$, and $\epsilon$ is the desired precision parameter. When applied to a dense matrix with spectral norm bounded by a constant, the runtime of the proposed algorithm is bounded by $\mathcal{O}({\kappa }^2\sqrt{n}\text{polylog}(n)/\epsilon )$, which is a quadratic improvement over known quantum linear system algorithms. Our algorithm is built upon a singular value estimation subroutine, which makes use of a memory architecture that allows for efficient preparation of quantum states that correspond to the rows and row Frobenius norms of $A$.

References in corpus (5)

• Quantum algorithm for solving linear systems of equations
• Quantum random access memory
• Quantum Data Fitting
• Architectures for a quantum random access memory
• Quantum Bootstrapping via Compressed Quantum Hamiltonian Learning

Cited by in corpus (88)

• Quantum machine learning: a classical perspective
• Variational quantum simulation of general processes
• Variational Quantum Linear Solver
• Solving nonlinear differential equations with differentiable quantum circuits
• Variational algorithms for linear algebra
• Quantum Hopfield neural network
• Quantum gradient descent for linear systems and least squares
• Quantum State Preparation with Optimal Circuit Depth: Implementations and Applications
• Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning
• Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems
• A comprehensive review of Quantum Machine Learning: from NISQ to Fault Tolerance
• Quantum algorithm for non-homogeneous linear partial differential equations
• Biology and medicine in the landscape of quantum advantages
• Fast inversion, preconditioned quantum linear system solvers, and fast evaluation of matrix functions
• Universal discriminative quantum neural networks
• Quantum data compression by principal component analysis
• Variational Quantum Singular Value Decomposition
• Bayesian Deep Learning on a Quantum Computer
• Quantum linear systems algorithms: a primer
• An improved quantum-inspired algorithm for linear regression
• Enhancing the Quantum Linear Systems Algorithm using Richardson Extrapolation
• Quantum Computing: An Overview Across the System Stack
• Configurable sublinear circuits for quantum state preparation
• Optimal (controlled) quantum state preparation and improved unitary synthesis by quantum circuits with any number of ancillary qubits
• Random circuit block-encoded matrix and a proposal of quantum LINPACK benchmark
• Implementing any Linear Combination of Unitaries on Intermediate-term Quantum Computers
• Box algorithm for the solution of differential equations on a quantum annealer
• Quantum Circulant Preconditioner for Linear System of Equations
• Cost function embedding and dataset encoding for machine learning with parameterized quantum circuits
• Exact gate decompositions for photonic quantum computing
• An Application of Quantum Annealing Computing to Seismic Inversion
• Analyzing the impact of time-correlated noise on zero-noise extrapolation
• Optimizing a Polynomial Function on a Quantum Simulator
• Hybrid classical-quantum linear solver using Noisy Intermediate-Scale Quantum machines
• Quantum algorithm for Neighborhood Preserving Embedding
• Quantum Algorithms to Matrix Multiplication
• Incompressible Navier-Stokes solve on noisy quantum hardware via a hybrid quantum-classical scheme
• Quantum Circuit Design Methodology for Multiple Linear Regression
• Entanglement-based quantum deep learning
• Quantum algorithms for training Gaussian Processes
• Quantum linear system solver based on time-optimal adiabatic quantum computing and quantum approximate optimization algorithm
• Block-encoding dense and full-rank kernels using hierarchical matrices: applications in quantum numerical linear algebra
• Quantum algorithm for total least squares data fitting
• Quantum algorithms for scientific computing
• Spacetime-Efficient Low-Depth Quantum State Preparation with Applications
• Randomized Row and Column Iterative Methods with a Quantum Computer
• Quantum Gradient Algorithm for General Polynomials
• Quantum mean centering for block-encoding-based quantum algorithm
• Quantum-classical algorithms for skewed linear systems with optimized Hadamard test
• Circuit-based digital adiabatic quantum simulation and pseudoquantum simulation as new approaches to lattice gauge theory
• A Quantum Interior-Point Predictor-Corrector Algorithm for Linear Programming
• Quantum-Inspired Classical Algorithms for Singular Value Transformation
• Harrow-Hassidim-Lloyd algorithm without ancilla postselection
• Deterministic and Entanglement-Efficient Preparation of Amplitude-Encoded Quantum Registers
• Limitations for Quantum Algorithms to Solve Turbulent and Chaotic Systems
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms
• Asymptotically Optimal Circuit Depth for Quantum State Preparation and General Unitary Synthesis
• Quantum algorithms for matrix operations and linear systems of equations
• Entanglement assisted training algorithm for supervised quantum classifiers
• Quantum Carleman linearisation efficiency in nonlinear fluid dynamics
• A quantum algorithm for simulating non-sparse Hamiltonians
• Quantum Algorithms for Geologic Fracture Networks
• A Universal Quantum Circuit Design for Periodical Functions
• Quantum Algorithm For Estimating Eigenvalue
• Quantum Approximate Optimization Algorithm for Maximum Likelihood Detection in Massive MIMO
• Coherence dynamics in quantum algorithm for linear systems of equations
• From linear combination of quantum states to Grover's searching algorithm
• Numerical circuit synthesis and compilation for multi-state preparation
• Quantum algorithm for logistic regression
• Randomized semi-quantum matrix processing
• Quantum algorithms for calculating determinant and inverse of matrix and solving linear algebraic systems
• Random Projection using Random Quantum Circuits
• A quantum-inspired algorithm for approximating statistical leverage scores
• Integrating Quantum Algorithms Into Classical Frameworks: A Predictor-corrector Approach Using HHL
• Bayesian machine learning for Boltzmann machine in quantum-enhanced feature spaces
• On solving classes of positive-definite quantum linear systems with quadratically improved runtime in the condition number
• Range dependent Hamiltonian Algorithm for numerical QUBO formulation
• Quantum Regularized Least Squares Solver with Parameter Estimate
• Resource-efficient quantum algorithm for linear systems of equations
• The quantum version of the shifted power method and its application in quadratic binary optimization
• Quantum Machine Learning For Classical Data
• Two Variations of Quantum Phase Estimation for Reducing Circuit Error Rates: Application to the Harrow--Hassidim--Lloyd Algorithm
• Hermitian Matrix Definiteness from Quantum Phase Estimation
• Schmidt quantum compressor
• Quantum multi-row iteration algorithm for linear systems with non-square coefficient matrices
• Quantum relaxed row and column iteration methods based on block-encoding
• Solving the Nonlinear Vlasov Equation on a Quantum Computer
• Quantum Computation