A Residual-Based Quantum Linear System Algorithm with Dynamic Stopping and Applications to Elliptic PDEs

• URL: http://arxiv.org/abs/2605.06414v1
• Date: Thu, 07 May 2026 15:22:55 GMT
• Title: A Residual-Based Quantum Linear System Algorithm with Dynamic Stopping and Applications to Elliptic PDEs
• Abstract summary: Quantum linear-system algorithms (QLSAs) have rigorous worst-case complexity guarantees, but their runtimes are often chosen from spectral information assumed in advance.<n>What is largely lacking is an a posteriori progress flag: most QLSA, unlike the classical counterparts, do not provide a built-in mechanism to signal whether a particular instance has already converged.<n>We design an augmented dynamics with residual variables, in which measuring a residual register gives an on-the-fly convergence indicator.
• Score: 3.3636842548621275
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum linear-system algorithms (QLSAs) have rigorous worst-case complexity guarantees, but their runtimes are often chosen from spectral information assumed in advance. What is largely lacking is an a posteriori progress flag: most QLSA workflows, unlike the classical counterparts, do not provide a built-in mechanism to signal whether a particular instance has already converged. For discretizations of elliptic PDEs $-\nabla\cdot(a(x)\nabla u(x))=f(x),$ with divergence--gradient structure \[ -\nabla\cdot \big(a(x)\nabla) \approx A_h=G_h^\dagger G_h, \] we formulate a stable first-order ODE whose limiting solution block is the desired Galerkin solution. The PDE-dependent scale is then \(\norm{G_h}=\bigO(h^{-1})\), comparable to factorized QLSA constructions with square-root condition-number scaling. We design an augmented dynamics with residual variables, in which measuring a residual register gives an on-the-fly convergence indicator without reconstructing the solution vector. For smooth right-hand sides, dynamic stopping can reduce the evolution time and gate count relative to a fixed worst-case schedule, and may also reduce exposure to accumulated hardware errors. Numerical experiments for a two-dimensional finite element Poisson problem show that the residual-register probability follows the actual error decay and, for some right-hand sides, can stop the quantum circuit well before a conservative worst-case runtime estimate is reached.

Related papers

• Attractor Geometry Determines the Identifiability Limits of System Discovery [0.764671395172401]
  We show that a single number, $_min(M)$, sets the identifiability ceiling for both sparse regression (SINDy) and evolutionary regression (PySR)<n>We also introduce Soft F1, a coefficient-weighted structural metric that resolves performance differences invisible to binary-success and predictive scores.
  arXiv  Detail & Related papers  (2026-07-20T20:19:19Z)
• Circuit Depth Reduction of One-Ancilla Quantum Differential Equation Solver via Extrapolation [1.0742675209112622]
  A recent one-ancilla quantum differential equation solver provides a hardware-friendly and locality-preserving approach.<n>We reduce the maximum single-run circuit depth to $O(mathrmpolylog (1/)$ without adding quantum ancillae or sacrificing locality.<n> Numerical experiments on the Hatano-Nelson model (ODE) and the convection-diffusion equation (PDE) demonstrate the effectiveness of the approach.
  arXiv  Detail & Related papers  (2026-07-08T13:20:43Z)
• Is Spurious Correlation Removal Always Learnable? [56.28155520961125]
  Invariant learning can fail even when the structure is statistically identifiable.<n>We show a conditional computational barrier: under a black-box samplable supervised sparse recovery primitive, there exist emphamplable multi-dimensional environments.<n>Synthetic and real datasets illustrate the predicted gaps and transitions and motivate simple diversity diagnostics.
  arXiv  Detail & Related papers  (2026-06-11T05:49:43Z)
• Toward Efficient End-to-End Quantum Elliptic PDE Solvers: a Multilevel Correction Algorithm for Direct Observable Estimation [3.3636842548621275]
  A central test case for quantum linear system algorithms (QLSA) is elliptic PDEs after a finite element discretization.<n>We present a multilevel framework for this readout problem, motivated by the variance-reduction mechanism of multilevel Monte Carlo.<n>Our algorithm is based on Schur-complement factorization of the corrected Green's operator through a Ritz-complement map.
  arXiv  Detail & Related papers  (2026-05-31T14:47:58Z)
• Operator-Algebraic Methods for Asymptotic-Preserving Quantum Simulation of Open Systems [0.0]
  We develop a mathematically rigorous framework for simulating multiscale physical systems using quantum computational resources.<n>We prove that layered quantum protocols, which implement fast-scale relaxation via native analog evolution or analytic manifold projection, converge uniformly in the diamond norm.<n>This work provides a principled mathematical bridge between classical multiscale numerical analysis and quantum simulation algorithms.
  arXiv  Detail & Related papers  (2026-05-16T19:27:58Z)
• Stabilizing Fixed-Point Iteration for Markov Chain Poisson Equations [49.702772230127465]
  We study finite-state Markov chains with $n$ states and transition matrix $P$.<n>We show that all non-decaying modes are captured by a real peripheral invariant subspace $mathcalK(P)$, and that the induced operator on the quotient space $mathbbRn/mathcalK(P) is strictly contractive, yielding a unique quotient solution.
  arXiv  Detail & Related papers  (2026-01-31T02:57:01Z)
• Quadratic Continuous Quantum Optimization [0.9023122463034333]
  Quantum annealers can solve QUBO problems efficiently but struggle with continuous optimization tasks like regression.<n>We introduce Quadratic Continuous Quantum Optimization (QCQO), an anytime algorithm that approximates solutions to unconstrained programs via a sequence of QUBO instances.
  arXiv  Detail & Related papers  (2025-12-31T10:08:41Z)
• Block encoding the 3D heterogeneous Poisson equation with application to fracture flow [0.0]
  Quantum linear system (QLS) algorithms offer the potential to solve large-scale linear systems exponentially faster than classical methods.<n>We study the feasibility of applying QLS algorithms to solve discretized three-dimensional heterogeneous Poisson equations.
  arXiv  Detail & Related papers  (2025-08-10T00:17:09Z)
• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  In this work, we present a robust phase retrieval problem where the task is to recover an unknown signal. Our proposed oracle avoids the need for computationally spectral descent, using a simple gradient step and outliers.
  arXiv  Detail & Related papers  (2024-09-07T06:37:23Z)
• Provably Accelerating Ill-Conditioned Low-rank Estimation via Scaled Gradient Descent, Even with Overparameterization [48.65416821017865]
  This chapter introduces a new algorithmic approach, dubbed scaled gradient (ScaledGD) It converges linearly at a constant rate independent of the condition number of the low-rank object. It maintains the low periteration cost of gradient descent for a variety of tasks.
  arXiv  Detail & Related papers  (2023-10-09T21:16:57Z)
• Quantum Relaxation for Linear Systems in Finite Element Analysis [0.0]
  We present Quantum Relaxation for Linear System (qRLS) as an iterative approach for gate-based quantum computers. The well-conditioned system enables a practical iterative solution of finite element problems using the state-of-the-art Quantum Signal Processing (QSP) variant of QLSAs. This represents an exponential efficiency gain, offering a new approach for iterative finite element problem-solving on quantum hardware.
  arXiv  Detail & Related papers  (2023-08-02T18:31:33Z)
• Constrained Optimization via Exact Augmented Lagrangian and Randomized Iterative Sketching [55.28394191394675]
  We develop an adaptive inexact Newton method for equality-constrained nonlinear, nonIBS optimization problems. We demonstrate the superior performance of our method on benchmark nonlinear problems, constrained logistic regression with data from LVM, and a PDE-constrained problem.
  arXiv  Detail & Related papers  (2023-05-28T06:33:37Z)
• Implicit Bias of Gradient Descent for Logistic Regression at the Edge of Stability [69.01076284478151]
  In machine learning optimization, gradient descent (GD) often operates at the edge of stability (EoS) This paper studies the convergence and implicit bias of constant-stepsize GD for logistic regression on linearly separable data in the EoS regime.
  arXiv  Detail & Related papers  (2023-05-19T16:24:47Z)
• On optimization of coherent and incoherent controls for two-level quantum systems [77.34726150561087]
  This article considers some control problems for closed and open two-level quantum systems. The closed system's dynamics is governed by the Schr"odinger equation with coherent control. The open system's dynamics is governed by the Gorini-Kossakowski-Sudarshan-Lindblad master equation.
  arXiv  Detail & Related papers  (2022-05-05T09:08:03Z)
• Last iterate convergence of SGD for Least-Squares in the Interpolation regime [19.05750582096579]
  We study the noiseless model in the fundamental least-squares setup. We assume that an optimum predictor fits perfectly inputs and outputs $langle theta_*, phi(X) rangle = Y$, where $phi(X)$ stands for a possibly infinite dimensional non-linear feature map.
  arXiv  Detail & Related papers  (2021-02-05T14:02:20Z)
• Differentially Quantized Gradient Methods [53.3186247068836]
  We show that Differentially Quantized Gradient Descent (DQ-GD) attains a linear contraction factor of $maxsigma_mathrmGD, rhon 2-R$. No algorithm within a certain class can converge faster than $maxsigma_mathrmGD, 2-R$.
  arXiv  Detail & Related papers  (2020-02-06T20:40:53Z)

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.