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:1704.04992 · Physical Review A

Quantum gradient descent for linear systems and least squares

Iordanis Kerenidis, Anupam Prakash

Published Feb 14, 2020• 172 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physreva.101.022316

Related papers

Improving quantum linear system solvers via a gradient descent perspective

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

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.

arXiv:2109.04248•Sep 9, 2021•1 citation

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

Faster Quantum-inspired Algorithms for Solving Linear Systems

Changpeng Shao, Ashley Montanaro

We establish an improved classical algorithm for solving linear systems in a model analogous to the QRAM that is used by quantum linear solvers. Precisely, for the linear system \( A{\bf x}= {\bf b} \) , we show that there is a classical algorithm that outputs a data structure for \( {\bf x} \) allowing sampling and querying to the entries, where \( {\bf x} \) is such that \( \Vert {\bf x}- A^{+}{\bf b}\Vert \le \epsilon \Vert A^{+}{\bf b}\Vert \) . This output can be viewed as a classical analogue to the output of quantum linear solvers. The complexity of our algorithm is \( \widetilde{O}(\kappa _F^6 \kappa ^2/\epsilon ^2) \) , where \( \kappa _F = \Vert A\Vert _F\Vert A^{+}\Vert \) and \( \kappa = \Vert A\Vert \Vert A^{+}\Vert \) . This improves the previous best algorithm [Gilyén, Song and Tang, arXiv:2009.07268] of complexity \( \widetilde{O}(\kappa _F^6 \kappa ^6/\epsilon ^4) \) . Our algorithm is based on the randomized Kaczmarz method, which is a particular case of stochastic gradient descent. We also find that when A is row sparse, this method already returns an approximate solution \( {\bf x} \) in time \( \widetilde{O}(\kappa _F^2) \) , while the best quantum algorithm known returns \( | {\bf x} \rangle \) in time \( \widetilde{O}(\kappa _F) \) when A is stored in the QRAM data structure. As a result, assuming access to QRAM and if A is row sparse, the speedup based on current quantum algorithms is quadratic.

arXiv:2103.10309•ACM Transactions on Quantum Computing•Mar 25, 2022•19 citations

Quantum Machine Learning: Adaptive Gradient Descent

Jincheng Zhang

Quantum Machine Learning (QML) represents a paradigm shift in machine learning, leveraging quantum mechanics to address computational challenges and unlock new capabilities. This paper explores the application of adaptive gradient descent, a core technique in classical machine learning, to quantum machine learning algorithms. We propose a novel quantum gradient descent framework that dynamically adjusts the learning rate and optimization direction based on the input data's inherent features. This adaptive approach aims to significantly enhance training efficiency and model generalization performance. The core mechanism involves the introduction of a 'quantum gradient descent' process, utilizing quantum entanglement and superposition to accelerate gradient computation compared to classical methods. We analyze the potential benefits and challenges of this new algorithm, demonstrating its effectiveness through a simplified conceptual model.

•Sep 1, 2026•0 citations

Quantum-Inspired Optimization of Large-Scale Machine Learning Models

Jincheng Zhang

The training of large-scale machine learning models presents significant computational challenges, primarily due to the inherent complexity of optimization algorithms like stochastic gradient descent (SGD) and its variants. These algorithms often struggle with convergence speed, getting trapped in local minima, and the ability to effectively explore the vast solution space. This paper investigates the potential of quantum-inspired optimization techniques to address these limitations. Specifically, we explore the application of quantum annealing and variational quantum eigensolver (VQE) approaches to accelerate the training and optimization process of large-scale machine learning models. Our core claim is that by mapping the optimization problem to a quantum system, we can leverage quantum computation to overcome the computational bottlenecks associated with classical optimization methods. We propose a framework where the objective function of the machine learning model is translated into a Hamiltonian for a quantum annealer or the cost function for a VQE, enabling a quantum-inspired solution. The results, while theoretical in this initial exploration, demonstrate a potential pathway for significantly reducing training times and improving the overall performance of large-scale machine learning models. Further research is needed to develop efficient hybrid quantum-classical algorithms and explore the practical limitations of this approach.

•Sep 6, 2026•0 citations

Pure quantum gradient descent algorithm and full quantum variational eigensolver

Ronghang Chen, Zhou Guang, Cong Guo +2 more

Optimization problems are prevalent in various fields, and the gradient-based gradient descent algorithm is a widely adopted optimization method. However, in classical computing, computing the numerical gradient for a function with d variables necessitates at least d + 1 function evaluations, resulting in a computational complexity of O ( d ). As the number of variables increases, the classical gradient estimation methods require substantial resources, ultimately surpassing the capabilities of classical computers. Fortunately, leveraging the principles of superposition and entanglement in quantum mechanics, quantum computers can achieve genuine parallel computing, leading to exponential acceleration over classical algorithms in some cases. In this paper, we propose a novel quantum-based gradient calculation method that requires only a single oracle calculation to obtain the numerical gradient result for a multivariate function. The complexity of this algorithm is just O (1). Building upon this approach, we successfully implemented the quantum gradient descent algorithm and applied it to the variational quantum eigensolver (VQE), creating a pure quantum variational optimization algorithm. Compared with classical gradient-based optimization algorithm, this quantum optimization algorithm has remarkable complexity advantages, providing an efficient solution to optimization problems. The proposed quantum-based method shows promise in enhancing the performance of optimization algorithms, highlighting the potential of quantum computing in this field.

arXiv:2305.04198•Frontiers of Physics•Dec 1, 2023•10 citations
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τ\ensuremath{\tau}\ensuremathτ steps of the gradient descent requires time O(\ensuremathτCS)O(\ensuremath{\tau}{C}_{S})O(\ensuremathτCS​) 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.
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.
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.
We establish an improved classical algorithm for solving linear systems in a model analogous to the QRAM that is used by quantum linear solvers. Precisely, for the linear system Ax=b A{\bf x}= {\bf b} Ax=b , we show that there is a classical algorithm that outputs a data structure for x {\bf x} x allowing sampling and querying to the entries, where x {\bf x} x is such that ∥x−A+b∥≤ϵ∥A+b∥ \Vert {\bf x}- A^{+}{\bf b}\Vert \le \epsilon \Vert A^{+}{\bf b}\Vert ∥x−A+b∥≤ϵ∥A+b∥ . This output can be viewed as a classical analogue to the output of quantum linear solvers. The complexity of our algorithm is O~(κF6κ2/ϵ2) \widetilde{O}(\kappa _F^6 \kappa ^2/\epsilon ^2) O(κF6​κ2/ϵ2) , where κF=∥A∥F∥A+∥ \kappa _F = \Vert A\Vert _F\Vert A^{+}\Vert κF​=∥A∥F​∥A+∥ and κ=∥A∥∥A+∥ \kappa = \Vert A\Vert \Vert A^{+}\Vert κ=∥A∥∥A+∥ . This improves the previous best algorithm [Gilyén, Song and Tang, arXiv:2009.07268] of complexity O~(κF6κ6/ϵ4) \widetilde{O}(\kappa _F^6 \kappa ^6/\epsilon ^4) O(κF6​κ6/ϵ4) . Our algorithm is based on the randomized Kaczmarz method, which is a particular case of stochastic gradient descent. We also find that when A is row sparse, this method already returns an approximate solution x {\bf x} x in time O~(κF2) \widetilde{O}(\kappa _F^2) O(κF2​) , while the best quantum algorithm known returns ∣x⟩ | {\bf x} \rangle ∣x⟩ in time O~(κF) \widetilde{O}(\kappa _F) O(κF​) when A is stored in the QRAM data structure. As a result, assuming access to QRAM and if A is row sparse, the speedup based on current quantum algorithms is quadratic.
Quantum Machine Learning (QML) represents a paradigm shift in machine learning, leveraging quantum mechanics to address computational challenges and unlock new capabilities. This paper explores the application of adaptive gradient descent, a core technique in classical machine learning, to quantum machine learning algorithms. We propose a novel quantum gradient descent framework that dynamically adjusts the learning rate and optimization direction based on the input data's inherent features. This adaptive approach aims to significantly enhance training efficiency and model generalization performance. The core mechanism involves the introduction of a 'quantum gradient descent' process, utilizing quantum entanglement and superposition to accelerate gradient computation compared to classical methods. We analyze the potential benefits and challenges of this new algorithm, demonstrating its effectiveness through a simplified conceptual model.
The training of large-scale machine learning models presents significant computational challenges, primarily due to the inherent complexity of optimization algorithms like stochastic gradient descent (SGD) and its variants. These algorithms often struggle with convergence speed, getting trapped in local minima, and the ability to effectively explore the vast solution space. This paper investigates the potential of quantum-inspired optimization techniques to address these limitations. Specifically, we explore the application of quantum annealing and variational quantum eigensolver (VQE) approaches to accelerate the training and optimization process of large-scale machine learning models. Our core claim is that by mapping the optimization problem to a quantum system, we can leverage quantum computation to overcome the computational bottlenecks associated with classical optimization methods. We propose a framework where the objective function of the machine learning model is translated into a Hamiltonian for a quantum annealer or the cost function for a VQE, enabling a quantum-inspired solution. The results, while theoretical in this initial exploration, demonstrate a potential pathway for significantly reducing training times and improving the overall performance of large-scale machine learning models. Further research is needed to develop efficient hybrid quantum-classical algorithms and explore the practical limitations of this approach.
Optimization problems are prevalent in various fields, and the gradient-based gradient descent algorithm is a widely adopted optimization method. However, in classical computing, computing the numerical gradient for a function with d variables necessitates at least d + 1 function evaluations, resulting in a computational complexity of O ( d ). As the number of variables increases, the classical gradient estimation methods require substantial resources, ultimately surpassing the capabilities of classical computers. Fortunately, leveraging the principles of superposition and entanglement in quantum mechanics, quantum computers can achieve genuine parallel computing, leading to exponential acceleration over classical algorithms in some cases. In this paper, we propose a novel quantum-based gradient calculation method that requires only a single oracle calculation to obtain the numerical gradient result for a multivariate function. The complexity of this algorithm is just O (1). Building upon this approach, we successfully implemented the quantum gradient descent algorithm and applied it to the variational quantum eigensolver (VQE), creating a pure quantum variational optimization algorithm. Compared with classical gradient-based optimization algorithm, this quantum optimization algorithm has remarkable complexity advantages, providing an efficient solution to optimization problems. The proposed quantum-based method shows promise in enhancing the performance of optimization algorithms, highlighting the potential of quantum computing in this field.