Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2109.04248

Improving quantum linear system solvers via a gradient descent perspective

Sander Gribling, Iordanis Kerenidis, Dániel Szilágyi

Published Sep 9, 2021• 1 citation
arXivHTMLPDF

Abstract

Solving systems of linear equations is one of the most important primitives in quantum computing that has the potential to provide a practical quantum advantage in many different areas, including in optimization, simulation, and machine learning. In this work, we revisit quantum linear system solvers from the perspective of convex optimization, and in particular gradient descent-type algorithms. This leads to a considerable constant-factor improvement in the runtime (or, conversely, a several orders of magnitude smaller error with the same runtime/circuit depth). More precisely, we first show how the asymptotically optimal quantum linear system solver of Childs, Kothari, and Somma is related to the gradient descent algorithm on the convex function $\|A\vec x - \vec b\|_2^2$: their linear system solver is based on a truncation in the Chebyshev basis of the degree-$(t-1)$ polynomial (in $A$) that maps the initial solution $\vec{x}_1 := \vec{b}$ to the $t$-th iterate $\vec{x}_t$ in the basic gradient descent algorithm. Then, instead of starting from the basic gradient descent algorithm, we use the optimal Chebyshev iteration method (which can be viewed as an accelerated gradient descent algorithm) and show that this leads to considerable improvements in the quantum solver.

DOI
10.48550/arxiv.2109.04248

Related papers

An Optimal Linear-combination-of-unitaries-based Quantum Linear System Solver

Sander Gribling, Iordanis Kerenidis, Dániel Szilágyi

Solving systems of linear equations is one of the most important primitives in many different areas, including in optimization, simulation, and machine learning. Quantum algorithms for solving linear systems have the potential to provide a quantum advantage for these problems. In this work, we recall the Chebyshev iterative method and the corresponding optimal polynomial approximation of the inverse. We show that the Chebyshev iteration polynomial can be efficiently evaluated both using quantum singular value transformation (QSVT) as well as linear combination of unitaries (LCU). We achieve this by bounding the 1-norm of the coefficients of the polynomial expressed in the Chebyshev basis. This leads to a considerable constant-factor improvement in the runtime of quantum linear system solvers that are based on LCU or QSVT (or, conversely, a several orders of magnitude smaller error with the same runtime/circuit depth).

ACM Transactions on Quantum Computing•Feb 24, 2024•3 citations

Quantum gradient descent for linear systems and least squares

Iordanis Kerenidis, Anupam Prakash

Quantum machine learning and optimization are exciting new areas that have been brought forward by the breakthrough quantum algorithm of Harrow, Hassidim, and Lloyd for solving systems of linear equations. The utility of classical linear system solvers extends beyond linear algebra as they can be leveraged to solve optimization problems using iterative methods like gradient descent. In this work, we provide a quantum method for performing gradient descent when the gradient is an affine function. Performing $\ensuremath{\tau}$ steps of the gradient descent requires time $O(\ensuremath{\tau}{C}_{S})$ for weighted least-squares problems, where ${C}_{S}$ is the cost of performing one step of the gradient descent quantumly, which at times can be considerably smaller than the classical cost. We illustrate our method by providing two applications: first, for solving positive semidefinite linear systems, and, second, for performing stochastic gradient descent for the weighted least-squares problem with reduced quantum memory requirements. We also provide a quantum linear system solver in the QRAM data structure model that provides significant savings in cost for large families of matrices.

arXiv:1704.04992•Physical Review A•Feb 14, 2020•172 citations

New Quantum Algorithm For Solving Linear System of Equations

Nhat A. Nghiem

Linear equations play a pivotal role in many areas of science and engineering, making efficient solutions to linear systems highly desirable. The development of quantum algorithms for solving linear systems has been a significant breakthrough, with such algorithms rapidly becoming some of the most influential in quantum computing. Subsequent advances have focused on improving the efficiency of quantum linear solvers and extending their core techniques to address various challenges, such as least-squares data fitting. In this article, we introduce a new quantum algorithm for solving linear systems based on the gradient descent method. Inspired by the vector/density state formalism, we represent a point, or vector, as a density state-like entity, enabling us to leverage recent advancements in quantum algorithmic frameworks, such as block encoding, to directly manipulate operators and carry out the gradient descent method in a quantum setting. The operator corresponding to the intermediate solution is updated iteratively, with a provable guarantee of convergence. The quantum state representing the final solution to the linear system can then be extracted by further measurement. We provide a detailed complexity analysis and compare our approach with existing methods, demonstrating significant improvement in certain aspects.

arXiv:2502.13630•Feb 19, 2025•0 citations

Quantum gradient descent and Newton’s method for constrained polynomial optimization

Patrick Rebentrost, Maria Schuld, Leonard Wossnig +2 more

Abstract Optimization problems in disciplines such as machine learning are commonly solved with iterative methods. Gradient descent algorithms find local minima by moving along the direction of steepest descent while Newton’s method takes into account curvature information and thereby often improves convergence. Here, we develop quantum versions of these iterative optimization algorithms and apply them to polynomial optimization with a unit norm constraint. In each step, multiple copies of the current candidate are used to improve the candidate using quantum phase estimation, an adapted quantum state exponentiation scheme, as well as quantum matrix multiplications and inversions. The required operations perform polylogarithmically in the dimension of the solution vector and exponentially in the number of iterations. Therefore, the quantum algorithm can be useful for high-dimensional problems where a small number of iterations is sufficient.

arXiv:1612.01789•New Journal of Physics•Jun 20, 2019•15 citations

Quantum gradient descent and Newton’s method for constrained polynomial optimization

Rebentrost, Frank Patrick, Seth Lloyd

Optimization problems in disciplines such as machine learning are commonly solved with iterative methods. Gradient descent algorithms find local minima by moving along the direction of steepest descent while Newton's method takes into account curvature information and thereby often improves convergence. Here, we develop quantum versions of these iterative optimization algorithms and apply them to polynomial optimization with a unit norm constraint. In each step, multiple copies of the current candidate are used to improve the candidate using quantum phase estimation, an adapted quantum state exponentiation scheme, as well as quantum matrix multiplications and inversions. The required operations perform polylogarithmically in the dimension of the solution vector and exponentially in the number of iterations. Therefore, the quantum algorithm can be useful for high-dimensional problems where a small number of iterations is sufficient.

•Jul 1, 2019•127 citations

Quantum linear system solvers: A survey of algorithms and applications

Mauro E. S. Morales, Lirandë Pira, Philipp Schleich +7 more

Solving linear systems of equations plays a fundamental role in numerous computational problems from different fields of science. The widespread use of numerical methods to solve these systems motivates investigating the feasibility of solving linear systems problems using quantum computers. In this work, we provide a survey of the main advances in quantum linear systems algorithms, together with some applications. We summarize and analyze the main ideas behind some of the algorithms for the quantum linear systems problem in the literature. The analysis begins by examining the Harrow-Hassidim-Lloyd (HHL) solver. We note its limitations and reliance on computationally expensive quantum methods, then highlight subsequent research efforts which aimed to address these limitations and optimize runtime efficiency and precision via various paradigms. We focus in particular on the post-HHL enhancements which have paved the way towards optimal lower bounds with respect to error tolerance and condition number. By doing so, we propose a taxonomy that categorizes these studies. Furthermore, by contextualizing these developments within the broader landscape of quantum computing, we explore the foundational work that have inspired and informed their development, as well as subsequent refinements. Finally, we discuss the potential applications of these algorithms in differential equations, quantum machine learning, and many-body physics.

arXiv:2411.02522•Reviews of Modern Physics•Jan 8, 2026•4 citations
Solving systems of linear equations is one of the most important primitives in quantum computing that has the potential to provide a practical quantum advantage in many different areas, including in optimization, simulation, and machine learning. In this work, we revisit quantum linear system solvers from the perspective of convex optimization, and in particular gradient descent-type algorithms. This leads to a considerable constant-factor improvement in the runtime (or, conversely, a several orders of magnitude smaller error with the same runtime/circuit depth). More precisely, we first show how the asymptotically optimal quantum linear system solver of Childs, Kothari, and Somma is related to the gradient descent algorithm on the convex function ∥Ax⃗−b⃗∥22\|A\vec x - \vec b\|_2^2∥Ax−b∥22​: their linear system solver is based on a truncation in the Chebyshev basis of the degree-(t−1)(t-1)(t−1) polynomial (in AAA) that maps the initial solution x⃗1:=b⃗\vec{x}_1 := \vec{b}x1​:=b to the ttt-th iterate x⃗t\vec{x}_txt​ in the basic gradient descent algorithm. Then, instead of starting from the basic gradient descent algorithm, we use the optimal Chebyshev iteration method (which can be viewed as an accelerated gradient descent algorithm) and show that this leads to considerable improvements in the quantum solver.
Solving systems of linear equations is one of the most important primitives in many different areas, including in optimization, simulation, and machine learning. Quantum algorithms for solving linear systems have the potential to provide a quantum advantage for these problems. In this work, we recall the Chebyshev iterative method and the corresponding optimal polynomial approximation of the inverse. We show that the Chebyshev iteration polynomial can be efficiently evaluated both using quantum singular value transformation (QSVT) as well as linear combination of unitaries (LCU). We achieve this by bounding the 1-norm of the coefficients of the polynomial expressed in the Chebyshev basis. This leads to a considerable constant-factor improvement in the runtime of quantum linear system solvers that are based on LCU or QSVT (or, conversely, a several orders of magnitude smaller error with the same runtime/circuit depth).
Quantum machine learning and optimization are exciting new areas that have been brought forward by the breakthrough quantum algorithm of Harrow, Hassidim, and Lloyd for solving systems of linear equations. The utility of classical linear system solvers extends beyond linear algebra as they can be leveraged to solve optimization problems using iterative methods like gradient descent. In this work, we provide a quantum method for performing gradient descent when the gradient is an affine function. Performing $\ensuremath{\tau}$ steps of the gradient descent requires time $O(\ensuremath{\tau}{C}_{S})$ for weighted least-squares problems, where CS{C}_{S}CS​ is the cost of performing one step of the gradient descent quantumly, which at times can be considerably smaller than the classical cost. We illustrate our method by providing two applications: first, for solving positive semidefinite linear systems, and, second, for performing stochastic gradient descent for the weighted least-squares problem with reduced quantum memory requirements. We also provide a quantum linear system solver in the QRAM data structure model that provides significant savings in cost for large families of matrices.
Linear equations play a pivotal role in many areas of science and engineering, making efficient solutions to linear systems highly desirable. The development of quantum algorithms for solving linear systems has been a significant breakthrough, with such algorithms rapidly becoming some of the most influential in quantum computing. Subsequent advances have focused on improving the efficiency of quantum linear solvers and extending their core techniques to address various challenges, such as least-squares data fitting. In this article, we introduce a new quantum algorithm for solving linear systems based on the gradient descent method. Inspired by the vector/density state formalism, we represent a point, or vector, as a density state-like entity, enabling us to leverage recent advancements in quantum algorithmic frameworks, such as block encoding, to directly manipulate operators and carry out the gradient descent method in a quantum setting. The operator corresponding to the intermediate solution is updated iteratively, with a provable guarantee of convergence. The quantum state representing the final solution to the linear system can then be extracted by further measurement. We provide a detailed complexity analysis and compare our approach with existing methods, demonstrating significant improvement in certain aspects.
Abstract Optimization problems in disciplines such as machine learning are commonly solved with iterative methods. Gradient descent algorithms find local minima by moving along the direction of steepest descent while Newton’s method takes into account curvature information and thereby often improves convergence. Here, we develop quantum versions of these iterative optimization algorithms and apply them to polynomial optimization with a unit norm constraint. In each step, multiple copies of the current candidate are used to improve the candidate using quantum phase estimation, an adapted quantum state exponentiation scheme, as well as quantum matrix multiplications and inversions. The required operations perform polylogarithmically in the dimension of the solution vector and exponentially in the number of iterations. Therefore, the quantum algorithm can be useful for high-dimensional problems where a small number of iterations is sufficient.
Optimization problems in disciplines such as machine learning are commonly solved with iterative methods. Gradient descent algorithms find local minima by moving along the direction of steepest descent while Newton's method takes into account curvature information and thereby often improves convergence. Here, we develop quantum versions of these iterative optimization algorithms and apply them to polynomial optimization with a unit norm constraint. In each step, multiple copies of the current candidate are used to improve the candidate using quantum phase estimation, an adapted quantum state exponentiation scheme, as well as quantum matrix multiplications and inversions. The required operations perform polylogarithmically in the dimension of the solution vector and exponentially in the number of iterations. Therefore, the quantum algorithm can be useful for high-dimensional problems where a small number of iterations is sufficient.
Solving linear systems of equations plays a fundamental role in numerous computational problems from different fields of science. The widespread use of numerical methods to solve these systems motivates investigating the feasibility of solving linear systems problems using quantum computers. In this work, we provide a survey of the main advances in quantum linear systems algorithms, together with some applications. We summarize and analyze the main ideas behind some of the algorithms for the quantum linear systems problem in the literature. The analysis begins by examining the Harrow-Hassidim-Lloyd (HHL) solver. We note its limitations and reliance on computationally expensive quantum methods, then highlight subsequent research efforts which aimed to address these limitations and optimize runtime efficiency and precision via various paradigms. We focus in particular on the post-HHL enhancements which have paved the way towards optimal lower bounds with respect to error tolerance and condition number. By doing so, we propose a taxonomy that categorizes these studies. Furthermore, by contextualizing these developments within the broader landscape of quantum computing, we explore the foundational work that have inspired and informed their development, as well as subsequent refinements. Finally, we discuss the potential applications of these algorithms in differential equations, quantum machine learning, and many-body physics.