Constant Factor Analysis of Optimal Quantum Linear Solvers in Practice

• URL: http://arxiv.org/abs/2604.22185v2
• Date: Mon, 27 Apr 2026 10:50:07 GMT
• Title: Constant Factor Analysis of Optimal Quantum Linear Solvers in Practice
• Abstract summary: An optimal solver using a discrete adiabatic approach has large analytically proven constant factors for the upper bound on the complexity.<n>A Shortcut'' method has been found to provide an optimal solver which also has small proven constant factors.<n>We find that, in the case where the solution norm is unknown, the adiabatic solver provides slightly better performance.
• Score: 42.05066415498962
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Optimal quantum linear equation solvers provide complexity $O(κ\log(1/ε))$, where $κ$ is the condition number and $ε$ is the allowable error. The optimal solver using a discrete adiabatic approach [PRX Quantum 3, 040303 (2022)] has large analytically proven constant factors for the upper bound on the complexity. The constant factors were later found to be about 1,200 times smaller in numerical testing [Quantum 9, 1887 (2025)]. This meant it is about an order of magnitude more efficient than using a randomised approach from [PRX Quantum 6, 040373 (2025)], which has far smaller analytically proven constant factors. Recently, a ``Shortcut'' method has been found to provide an optimal solver which also has small proven constant factors. In the present work, we conduct a comprehensive numerical analysis comparing this method with the adiabatic solver for two families of random linear systems. We find that, in the case where the solution norm is unknown, the adiabatic solver provides slightly better performance. If the solution norm is known, then the shortcut method provides significantly better performance for non-Hermitian matrices.

Related papers

• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  A fundamental and long-standing challenge is their efficient approximation.<n>We develop a linear-space algorithm that requires $P(|hatboldsymbol-boldsymbol|_2geq)leq $ for all commonly used semi-values.<n>Our algorithm allows explicit minimization of the mean square error for each specific utility function.
  arXiv  Detail & Related papers  (2026-04-09T16:38:14Z)
• Constant-Factor Improvements in Quantum Algorithms for Linear Differential Equations [0.4199844472131922]
  We prove constant factor bounds for a promising new quantum differential equation solver, the linear combination of Hamiltonian simulation algorithm.<n>Our new formulae improve over previous state of the art by at least two orders of magnitude, where the speedup can be far greater if state preparation has a significant cost.
  arXiv  Detail & Related papers  (2025-06-25T18:50:44Z)
• Accelerated Stochastic Min-Max Optimization Based on Bias-corrected Momentum [30.01198677588252]
  First-order algorithms require at least $mathcalO(varepsilonepsilon-4)$ complexity to find an $varepsilon-stationary point.<n>We introduce novel momentum algorithms utilizing efficient variable complexity.<n>The effectiveness of the method is validated through robust logistic regression using real-world datasets.
  arXiv  Detail & Related papers  (2024-06-18T20:14:52Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• The discrete adiabatic quantum linear system solver has lower constant factors than the randomized adiabatic solver [3.2655159697679292]
  The solution of linear systems of equations is the basis of many other quantum algorithms.<n>Recent results provided an algorithm with optimal scaling in both the condition number $kappa$ and the allowable error $epsilon$.<n>Here we show via numerical testing on random matrices that the constant factor is in practice about 1,200 times smaller than the upper bound found numerically in the previous results.
  arXiv  Detail & Related papers  (2023-12-12T19:36:41Z)
• Randomized adiabatic quantum linear solver algorithm with optimal complexity scaling and detailed running costs [0.0]
  We develop a quantum linear solver algorithm based on adiabatic quantum computing.<n>The algorithm is improved to the optimal scaling $O(kappa/log$)$ - an exponential improvement in $epsilon$.<n>We introduce a cheaper randomized walk operator method replacing Hamiltonian simulation.
  arXiv  Detail & Related papers  (2023-05-19T00:07:32Z)
• Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimization [88.0031283949404]
  Many real-world problems have complicated non functional constraints and use a large number of data points. Our proposed method outperforms an existing method with the previously best-known result.
  arXiv  Detail & Related papers  (2022-12-19T14:48:54Z)
• Explicit Second-Order Min-Max Optimization: Practical Algorithms and Complexity Analysis [71.05708939639537]
  We propose and analyze several inexact regularized Newton-type methods for finding a global saddle point of emphconcave unconstrained problems.<n>Our method improves the existing line-search-based min-max optimization by shaving off an $O(loglog(1/eps)$ factor in the required number of Schur decompositions.
  arXiv  Detail & Related papers  (2022-10-23T21:24:37Z)
• Optimal scaling quantum linear systems solver via discrete adiabatic theorem [0.9846257338039974]
  We develop a quantum algorithm for solving linear systems that is discreteally optimal. Compared to existing suboptimal methods, our algorithm is simpler and easier to implement.
  arXiv  Detail & Related papers  (2021-11-16T00:21:37Z)
• Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
  We show that families of algorithms fail to produce nearly optimal solutions with high probability. For the case of Boolean circuits, our results improve the state-of-the-art bounds known in circuit complexity theory.
  arXiv  Detail & Related papers  (2020-04-25T05:45:59Z)

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.