An analysis of iterative refinement for quantum linear system solvers
Abstract
We present and analyze an iterative refinement (IR) framework for improving the precision dependence of algorithms that combine a quantum linear system algorithm (QLSA) with quantum state tomography. Existing QLSAs achieve polylogarithmic dependence on the inverse error tolerance to prepare a quantum state encoding the solution, but extracting a classical description of such a state via tomography typically introduces a polynomial dependence on the target precision. To retain polylogarithmic dependence in the inverse error tolerance throughout the entire process, we develop an IR scheme that solves a sequence of related linear systems to progressively refine the solution while requiring only fixed-precision quantum subroutines, finally obtaining a classical description of a high-precision solution. We analyze the proposed framework under three input models: quantum-read/classical-write RAM (QRAM), linear combinations of unitaries (LCU), and sparse-access oracles. We evaluate the proposed scheme through numerical experiments on both quantum simulators and real quantum hardware. The results demonstrate that iterative refinement efficiently improves the precision of the solution and exhibits robustness to hardware noise.
Related
- Low-cost non-iterative Sylvester solvers for dynamical low-rank approximation of reaction-diffusion equations
- Iterative Atom Refinement: A Monotonicity Principle for Dictionary Learning
- Progressive Reliability-Guided Refinement with Cross-Modal Consistency and Iterative Correction for Weakly Supervised PET/CT Tumor Segmentation
- Impact of Feature Scaling on the Convergence Speed of Linear SVM Solvers : An Empirical Benchmark
- Comparative Performance Analysis of Optimization Solvers for Linear Support Vector Machines: Impact of Preconditioning and Dimensionality An Empirical Study Using the Benchopt Framework
BibTeX
@misc{harkness2026analysis,
title = {{An analysis of iterative refinement for quantum linear system solvers}},
author = {Adrian Harkness and Mohammadhossein Mohammadisiahroudi and Brandon Augustino and Giacomo Nannicini and Tamás Terlaky},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.10250},
eprint = {2609.10250},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.10250},
}
RIS
TY - UNPB
TI - An analysis of iterative refinement for quantum linear system solvers
AU - Adrian Harkness
AU - Mohammadhossein Mohammadisiahroudi
AU - Brandon Augustino
AU - Giacomo Nannicini
AU - Tamás Terlaky
PY - 2026
DA - 2026/09/09
PB - arXiv
DO - 10.48550/arxiv.2609.10250
UR - https://arxiv.org/abs/2609.10250
AB - We present and analyze an iterative refinement (IR) framework for improving the precision dependence of algorithms that combine a quantum linear system algorithm (QLSA) with quantum state tomography. Existing QLSAs achieve polylogarithmic dependence on the inverse error tolerance to prepare a quantum state encoding the solution, but extracting a classical description of such a state via tomography typically introduces a polynomial dependence on the target precision. To retain polylogarithmic dependence in the inverse error tolerance throughout the entire process, we develop an IR scheme that solves a sequence of related linear systems to progressively refine the solution while requiring only fixed-precision quantum subroutines, finally obtaining a classical description of a high-precision solution. We analyze the proposed framework under three input models: quantum-read/classical-write RAM (QRAM), linear combinations of unitaries (LCU), and sparse-access oracles. We evaluate the proposed scheme through numerical experiments on both quantum simulators and real quantum hardware. The results demonstrate that iterative refinement efficiently improves the precision of the solution and exhibits robustness to hardware noise.
ER -