On solving classes of positive-definite quantum linear systems with quadratically improved runtime in the condition number

Abstract

Quantum algorithms for solving the Quantum Linear System (QLS) problem are among the most investigated quantum algorithms of recent times, with potential applications including the solution of computationally intractable differential equations and speed-ups in machine learning. A fundamental parameter governing the efficiency of QLS solvers is $\kappa$, the condition number of the coefficient matrix $A$, as it has been known since the inception of the QLS problem that for worst-case instances the runtime scales at least linearly in $\kappa$ [Harrow, Hassidim and Lloyd, PRL 103, 150502 (2009)]. However, for the case of positive-definite matrices classical algorithms can solve linear systems with a runtime scaling as $\sqrt{\kappa }$, a quadratic improvement compared to the the indefinite case. It is then natural to ask whether QLS solvers may hold an analogous improvement. In this work we answer the question in the negative, showing that solving a QLS entails a runtime linear in $\kappa$ also when $A$ is positive definite. We then identify broad classes of positive-definite QLS where this lower bound can be circumvented and present two new quantum algorithms featuring a quadratic speed-up in $\kappa$: the first is based on efficiently implementing a matrix-block-encoding of $A^{-1}$, the second constructs a decomposition of the form $A=L{L}^{†}$ to precondition the system. These methods are widely applicable and both allow to efficiently solve BQP-complete problems.

arXiv comment49 pages, 3 figures, section on Variable-Time Amplitude Amplification added

References in corpus (31)

• Quantum algorithm for solving linear systems of equations
• Quantum Amplitude Amplification and Estimation
• Quantum random access memory
• Hamiltonian Simulation by Qubitization
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Tight bounds on quantum searching
• Synthesis of Quantum Logic Circuits
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
• Preconditioned quantum linear system algorithm
• Creating superpositions that correspond to efficiently integrable probability distributions
• A quantum linear system algorithm for dense matrices
• Quantum algorithms and the finite element method
• Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing
• Efficient phase-factor evaluation in quantum signal processing
• Focus beyond quadratic speedups for error-corrected quantum advantage
• Hamiltonian Simulation Using Linear Combinations of Unitary Operations
• Black-box quantum state preparation without arithmetic
• Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems
• Fast inversion, preconditioned quantum linear system solvers, and fast evaluation of matrix functions
• The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation
• Experimental realization of quantum algorithms for linear system inspired by adiabatic quantum computing
• Enhancing the Quantum Linear Systems Algorithm using Richardson Extrapolation
• Quantum Circuits for Sparse Isometries
• Spectral Gap Amplification
• Finding Angles for Quantum Signal Processing with Machine Precision
• Quantum Circulant Preconditioner for Linear System of Equations
• Analysis and limitations of modified circuit-to-Hamiltonian constructions
• Complexity of quantum state verification in the quantum linear systems problem
• Quantum-classical algorithms for skewed linear systems with optimized Hadamard test

Cited by in corpus (1)

• Improving quantum linear system solvers via a gradient descent perspective