Quantum Algorithms for Solving Generalized Linear Systems via Momentum Accelerated Gradient and Schrödingerization

• URL: http://arxiv.org/abs/2509.16576v1
• Date: Sat, 20 Sep 2025 08:40:53 GMT
• Title: Quantum Algorithms for Solving Generalized Linear Systems via Momentum Accelerated Gradient and Schrödingerization
• Authors: Qitong Hu, Xiaoyang He, Shi Jin, Xiao-Dong Zhang,
• Abstract summary: We propose a quantum algorithm that combines the momentum accelerated gradient method with Schr"odingerization.<n>The algorithm achieves speedup over its classical counterpark in solving linear systems.<n>It can overcome the practical limitations of existing non-Schr"odingerization-based quantum linear system algorithms.
• Score: 34.04094622012203
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we propose a quantum algorithm that combines the momentum accelerated gradient method with Schr\"odingerization [S. Jin, N. Liu and Y. Yu, Phys. Rev. Lett, 133 (2024), 230602][S. Jin, N. Liu and Y. Yu, Phys. Rev. A, 108 (2023), 032603], achieving polynomial speedup over its classical counterpark in solving linear systems. The algorithm achieves a query complexity of the same order as the Schr\"odingerization based damped dynamical system method, namely, linear dependence on the condition number of the matrix, and can overcome the practical limitations of existing non-Schr\"odingerization-based quantum linear system algorithms. These limitations stem from their reliance on techniques such as VTAA and RM, which introduce substantial quantum hardware resource overhead. Furthermore, it demonstrates both theoretically and experimentally that the auxiliary variables introduced by our method do not dominate the error reduction at any point, thereby preventing a significant increase in the actual evolution time compared to the theoretical prediction. In contrast, the damped method fails to meet this criterion. This gives new perspectives for quantum algorithms for linear systems, establishing a novel analytical framework for algorithms with broader applicability, faster convergence rates, and superior solution quality.

Related papers

• An em algorithm for quantum Boltzmann machines [40.40469032705598]
  We develop a quantum version of the em algorithm for training quantum Boltzmann machines.<n>We implement the algorithm on a semi-quantum restricted Boltzmann machine, where quantum effects are confined to the hidden layer.
  arXiv  Detail & Related papers  (2025-07-29T07:59:22Z)
• A time-marching quantum algorithm for simulation of the nonlinear Lorenz dynamics [0.0]
  We develop a quantum algorithm that implements the time evolution of a second order time-discretized version of the Lorenz model.<n> Notably, we showcase that it accurately captures the structural characteristics of the Lorenz system.
  arXiv  Detail & Related papers  (2025-06-26T15:08:00Z)
• New Quantum Algorithm For Solving Linear System of Equations [0.0]
  We introduce a new quantum algorithm for solving linear systems based on the gradient descent method.<n>Inspired by the vector/density state formalism, we represent a point, or vector, as a density state-like entity.<n>The operator corresponding to the intermediate solution is updated iteratively, with a provable guarantee of convergence.
  arXiv  Detail & Related papers  (2025-02-19T11:08:56Z)
• A Catalyst Framework for the Quantum Linear System Problem via the Proximal Point Algorithm [9.804179673817574]
  We propose a new quantum algorithm for the quantum linear system problem (QLSP) inspired by the classical proximal point algorithm (PPA) Our proposed method can be viewed as a meta-algorithm that allows inverting a modified matrix via an existing texttimattQLSP_solver. By carefully choosing the step size $eta$, the proposed algorithm can effectively precondition the linear system to mitigate the dependence on condition numbers that hindered the applicability of previous approaches.
  arXiv  Detail & Related papers  (2024-06-19T23:15:35Z)
• Bias-field digitized counterdiabatic quantum optimization [39.58317527488534]
  We call this protocol bias-field digitizeddiabatic quantum optimization (BF-DCQO) Our purely quantum approach eliminates the dependency on classical variational quantum algorithms. It achieves scaling improvements in ground state success probabilities, increasing by up to two orders of magnitude.
  arXiv  Detail & Related papers  (2024-05-22T18:11:42Z)
• An Efficient Quantum Algorithm for Linear System Problem in Tensor Format [4.264200809234798]
  We propose a quantum algorithm based on the recent advances on adiabatic-inspired QLSA. We rigorously show that the total complexity of our implementation is polylogarithmic in the dimension.
  arXiv  Detail & Related papers  (2024-03-28T20:37:32Z)
• Improving the convergence of an iterative algorithm for solving arbitrary linear equation systems using classical or quantum binary optimization [39.58317527488534]
  We propose a novel method for solving linear systems. We transform the linear system into a binary optimization problem, drawing inspiration from the geometry of the original problem. We demonstrate that by leveraging partial knowledge of the problem's intrinsic geometry, we can decompose the original problem into smaller, independent sub-problems.
  arXiv  Detail & Related papers  (2023-09-18T16:51:03Z)
• Quantum differential equation solvers: limitations and fast-forwarding [16.446810053424024]
  We show that quantum algorithms suffer from computational overheads due to two types of non-quantumness''<n>We then show that homogeneous ODEs in the absence of both types of non-quantumness'' are equivalent to quantum dynamics.<n>We show how to fast-forward quantum algorithms for solving special classes of ODEs which leads to improved efficiency.
  arXiv  Detail & Related papers  (2022-11-09T22:50:14Z)
• Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays [39.76254807200083]
  We experimentally investigate quantum algorithms for solving the Maximum Independent Set problem. We find the problem hardness is controlled by the solution degeneracy and number of local minima. On the hardest graphs, we observe a superlinear quantum speedup in finding exact solutions.
  arXiv  Detail & Related papers  (2022-02-18T19:00:01Z)
• Quadratic Unconstrained Binary Optimisation via Quantum-Inspired Annealing [58.720142291102135]
  We present a classical algorithm to find approximate solutions to instances of quadratic unconstrained binary optimisation. We benchmark our approach for large scale problem instances with tuneable hardness and planted solutions.
  arXiv  Detail & Related papers  (2021-08-18T09:26:17Z)
• Quantum algorithms for quantum dynamics: A performance study on the spin-boson model [68.8204255655161]
  Quantum algorithms for quantum dynamics simulations are traditionally based on implementing a Trotter-approximation of the time-evolution operator. variational quantum algorithms have become an indispensable alternative, enabling small-scale simulations on present-day hardware. We show that, despite providing a clear reduction of quantum gate cost, the variational method in its current implementation is unlikely to lead to a quantum advantage.
  arXiv  Detail & Related papers  (2021-08-09T18:00:05Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.