An analysis of iterative refinement for quantum linear system solvers

DOI10.48550/arXiv.2609.10250MaRDI QIDQ7288220arXivFDO

Authors Mohammadhossein Mohammadisiahroudi, Brandon Augustino, Giacomo Nannicini, Tamás Terlaky, Adrian Harkness

Publication date 9 September 2026

Published in arXiv

Tldr We propose an iterative refinement framework for improving the precision dependence of quantum linear system solvers combining a QLSA with tomography, retaining polylogarithmic dependence in the inverse error tolerance throughout the entire process by progressively refining solutions with fixed-precision quantum subroutines. This scheme is analyzed under three input models and evaluated through numerical experiments on quantum simulators and real hardware, demonstrating efficient improvement of precision and robustness to noise.

Full work available at URL https://doi.org/10.48550/arXiv.2609.10250

arXiv classification

math.NAquant-ph

Cites work

• A new analysis of iterative refinement and its application to accurate solution of ill-conditioned sparse linear systems
• Accelerating the solution of linear systems by iterative refinement in three precisions
• An inexact feasible interior point method for linear optimization with high adaptability to quantum computers
• An Inexact Feasible Quantum Interior Point Method for Linearly Constrained Quadratic Optimization
• Efficient use of quantum linear system algorithms in inexact infeasible IPMs for linear optimization
• Error bounds from extra-precise iterative refinement
• Fast state tomography with optimal error bounds
• Gaussian elimination is not optimal
• Hamiltonian simulation with nearly optimal dependence on all parameters
• Hamiltonian simulation with nearly optimal dependence on spectral norm
• Improvements to Quantum Interior Point Method for Linear Optimization
• Iterative Methods for Sparse Linear Systems
• Iterative refinement for linear programming
• Matrix multiplication via arithmetic progressions
• Methods of conjugate gradients for solving linear systems
• Powers of tensors and fast matrix multiplication
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Quantum Computing Inspired Iterative Refinement for Semidefinite Optimization
• Quantum Interior Point Methods for Semidefinite Optimization
• Quantum linear system solver based on time-optimal adiabatic quantum computing and quantum approximate optimization algorithm
• Quantum recommendation systems
• Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
• Quantum tomography using state-preparation unitaries
• Rounding Errors in Algebraic Processes
• Solving sparse linear systems faster than matrix multiplication
• The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation
• Variable time amplitude amplification and quantum algorithms for linear algebra problems

This page was built for publication: An analysis of iterative refinement for quantum linear system solvers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7288220)