Source-linked AI summary
An analysis of iterative refinement for quantum linear system solvers
Adrian Harkness, Mohammadhossein Mohammadisiahroudi, Brandon Augustino, Giacomo Nannicini, Tamás Terlaky
TL;DR
The paper targets the polynomial target-precision dependence in obtaining classical solutions through QLSA and tomography. It uses fixed-precision iterative refinement and reports geometric residual reduction and convergence under hardware noise.
Problem
Combining QLSA with tomography to obtain a classical solution has polynomial target-precision dependence, which the paper seeks to reduce.
Source: §7 · p. 22Method
The framework repeatedly applies fixed-precision quantum oracles and classical residual updates to refine a classical linear-system solution.
Source: §7 · p. 22Results
Experiments show geometric residual reduction and convergence under hardware noise; convergence is rapid when QPE precision resolves A’s spectrum, while refinement distributes precision across manageable-depth iterations otherwise.
Source: §6.1 · p. 19, §7 · p. 22, §6.4 · p. 22Takeaways & Limitations
The scheme offers a path to high-precision solutions using O(log(1/ζ)) repetitions of constant-depth circuits, with logarithmic overhead in total quantum operations.
Source: §6.4 · p. 22The main remaining classical cost is the matrix-vector multiplication needed to compute each refinement-step residual.
Source: §7 · p. 22
Abstract
from arXiv · showhide
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.
1. Introduction.
The paper develops iterative refinement to obtain high-precision classical solutions using fixed-precision quantum subroutines. It analyzes the approach across three input models and evaluates it in simulation and on quantum hardware.
1. Introduction.
- HHL established quantum linear-system algorithms, whose polylogarithmic dimension dependence suggested potential exponential speedups for solving linear systems.Source: §1 · pp. 1–2
1.1. Literature Review.
- QLSA research improved condition-number scaling, developed block-encoding methods, and established optimal κ_A and ε scaling, while practical constant factors remained relevant [12].Source: §1.1 · pp. 2–3
- Classical iterative refinement began as a way to obtain extended-precision linear-system solutions using low-precision arithmetic and was later applied to inexact classical solvers.Source: §1.1 · p. 3
1.2. Contributions.
- Fixed-precision QLSA and tomography steps with classical residual correction reduce the final target-precision dependence from polynomial to polylogarithmic.The framework is analyzed for QRAM, sparse-access, and LCU input models.Source: §1.2 · pp. 3–4
- Experiments show geometric residual reduction in noiseless settings, convergence under hardware noise, and resource advantages over a single high-precision circuit.The proposed approach uses repeated relatively shallow, low-precision quantum circuits to obtain high-precision classical solutions.Source: §1.2 · pp. 4–5
2. Notation and assumptions.
The section fixes notation and the matrix assumptions used in the analysis, and makes the algorithms’ success-probability dependence implicit.
2. Notation and assumptions.
- Logarithms are base 2, and vector and matrix dimensions are assumed to be powers of 2, with zero-padding available when needed.Source: §2 · p. 5
- Matrices are assumed row- and column-sparse, with largest singular value 1 and smallest singular value 1/κ_A, up to rescaling.It is sufficient to know the singular values up to a constant prefactor.Source: §2 · p. 5
- Quantum algorithms succeed with probability at least 1 − δ, and the polylogarithmic cost dependence on δ is omitted from stated results.Source: §2 · p. 5
3. Preliminaries on quantum linear algebra.
This section establishes preliminaries for quantum linear-system solving, defining the problems and describing oracle constructions across input models, including block-encoding and LCU approaches and their approximation-error control. It also frames iterative refinement as a classical technique for obtaining accurate solutions.
3. Preliminaries on quantum linear algebra.
- The quantum LSP is defined for a minimum-norm solution encoded as a quantum state, with the requested state satisfying the prescribed approximation condition.When A is invertible, its solution state is the normalized amplitude encoding of A^-1 b.Source: §3 · pp. 6–7
- The paper analyzes overall running time in the circuit and QRAM models, considering sparse access, QRAM, and linear combinations of unitaries as input models.The assumed data structure affects state preparation, block-encoding subnormalization, the QLSA used, and tomography cost.Source: §3.1 · p. 7
3.1.1. Sparse access model.
- Sparse access supplies nonzero matrix entries through index and value oracles, while QRAM makes classical data accessible in coherent superposition with classical writes.The QRAM analysis assumes access cost polylogarithmic in its size and reports accesses, additional gates, and initialization operations.Source: §3.1.1 · p. 7, §3.1.2 · p. 7
3.1.3. Linear Combination of Unitaries.
- An LCU input represents a matrix as a weighted sum of unitaries; a Pauli-basis representation always exists, and its sparsity affects solving cost.The section also introduces block-encodings as the framework used by the best-asymptotic-query-complexity QLSA across the three input models.Source: §3.1.3 · p. 8, §3.2 · p. 8
3.2. Complexity of the QLSP in the three input models.
- Block-encodings can be constructed from QRAM, sparse-access, or LCU inputs, enabling QLSA solution of linear systems with complexity depending polylogarithmically on dimension.The section states that the QLSA uses a block-encoding of A together with a state-preparation unitary for b.Source: §3.1.3 · p. 8, §3.2 · p. 9
3.3. Quantum state tomography.
- Tomography of a prepared state has sample complexity linear in dimension and inverse error, while its gate complexity depends on QRAM availability.The described algorithm extracts the real amplitudes; extra phase gates allow extraction of imaginary parts without changing asymptotic complexity.Source: §3.3 · pp. 9–10
3.4. A quantum oracle for the LSP.
- The oracle returns a classical vector whose residual satisfies ||A x̄ − b|| ≤ ξ, using norm estimation, QLSA state preparation, tomography, and rescaling.Its construction estimates the solution norm, prepares the normalized solution state, obtains a classical description by tomography, and rescales that description.Source: §3.4 · pp. 10–11
- In the LCU input model, the linear-system oracle is constructed from LCU oracles, assuming a normalized right-hand side in the column space of A.The setup also requires the matrix’s nonzero singular values to lie in the stated condition-number range, though the corresponding expression is corrupted in the passage.Source: §3.4 · p. 11
- The oracle construction bounds coefficient error in the unitary preparation to control block-encoding perturbation, then applies the linear-system theorem at precision ξ/2.The resulting vector has norm O(ακ_A); the proof combines this bound with the perturbation error to obtain the target error.Source: §3.4 · p. 12
- Iterative refinement is introduced as a classical technique for obtaining accurate solutions to linear systems.The passage presents this as a high-level overview before the algorithm’s analysis.Source: §4 · p. 12
4. Iterative Refinement for the LSP using quantum subroutines.
The section uses classical iterative refinement around fixed-precision quantum linear-system solves to reach a target residual accuracy. Its convergence is geometric, while the quantum solve precision remains fixed.
4.1. The algorithm.
- Each iteration classically forms and normalizes the residual, tomographs a fixed-precision quantum correction, rescales it, and adds it to the current iterate.The system may be classically scaled before refinement; the method assumes invertible A, with the pseudoinverse used for singular systems.Source: §4.1 · pp. 12–13
4.2. Convergence.
- The residual contracts as ∥r^(k)∥ ≤ ξ^k, giving a logarithmic iteration bound in the target accuracy for fixed ξ.The algorithm stops when the residual is at most ϵ∥b∥.Source: §4.2 · pp. 13–14
4.3. Computational complexity.
- In the QRAM model, residual-state preparation has polylogarithmic query complexity in the dimension, and each refining solve’s quantum cost is independent of final ϵ.The residual and its norm are computed classically at each iteration.Source: §4.3 · p. 15
4.4. A difference between classical and quantum IR.
- Because the quantum right-hand side is ℓ2-normalized, the convergence argument does not carry over to measuring residual error in the ℓ∞ norm.The cited discussion notes that an ℓ∞-error bound at each iteration does not suffice for the refinement scheme.Source: §4.3 · p. 15, §4.4 · p. 16
5. Complexity analysis in the three input models.
The complexity analysis covers QRAM, sparse-access, and LCU inputs. It highlights polylogarithmic dependence on final precision, while noting that the method does not achieve quantum advantage over classical conjugate gradient.
5.1. Detailed complexity statements.
- The analysis gives complexity results for classical solution output under QRAM, sparse-access, and LCU input models.Table 2 compares the proposed method with classical and quantum algorithms and states that its final-precision dependence is polylogarithmic.Source: §5.1 · p. 16, Table 2 · p. 17
- For LCU inputs, the classical arithmetic-operation count is parameterized by C_U, an upper bound on the cost of multiplying by each decomposition unitary.Source: §5.1 · p. 17
5.2. Comparison to existing linear system solvers.
- The quantum IR scheme does not achieve quantum advantage: classical conjugate gradient has the fastest asymptotic running time, although IR improves precision dependence over prior quantum approaches.The paper states that IR has polylogarithmic dependence on inverse precision, compared with polynomial cost for previous quantum approaches that produce a classical solution description.Source: §5.2 · p. 17
6. Numerical Experiments.
The experiments use HHL with QPE and tomography on randomly generated linear systems in simulation and on quantum hardware. They evaluate convergence, circuit-depth sensitivity, and resource trade-offs.
6. Numerical Experiments.
- The experiments use randomly generated Hermitian systems and 500 successful post-selected shots per iteration; the 8-variable hardware test uses dynamical decoupling and Pauli twirling.The hardware test uses a system with condition number 5 and sparsity 4.Source: §6 · pp. 17–18, §6.1 · p. 18
6.1. Convergence in simulation and quantum hardware.
- In noise-free simulation, q=5 reaches the 10^-9 residual criterion in 9 iterations and q=4 in 10, while q=3 reaches 6.6 × 10^-9 within 12 iterations.Each additional QPE qubit reduces eigenvalue quantization error and improves the search direction at each iteration.Source: Figure 1 · p. 18, §6.1 · p. 18
- On hardware, all three configurations converge monotonically, but their residuals are statistically indistinguishable as decoherence outweighs the benefit of greater QPE resolution.Residuals fall from 8.6 × 10^-1 to 1.03 × 10^-1 (q=3), 1.04 × 10^-1 (q=4), and 7.3 × 10^-2 (q=5).Source: §6.1 · p. 19
6.2. Sensitivity analysis.
- At ε=10^-6, HHL + IR depth remains near 10^4, while extrapolated direct-HHL depth reaches 2.4 × 10^10–1.3 × 10^11, a six-to-seven-order gap.At the directly compilable ε=10^-2 threshold, measured direct-HHL depths are already 30–300 times deeper than IR at ε=10^-6.Source: Figure 2 · p. 20, §6.2 · p. 20
- With q=1 or q=3, convergence can fail to reach residual 10^-6 within 30 iterations, whereas q=7 suffices across the tested condition-number range.The fixed per-iteration precision must satisfy ξ<1 for geometric convergence.Source: §6.2 · p. 21
6.3. Resource trade-offs.
- For a 64-variable system, 100 shots per iteration require about 10 iterations to reach residual 10^-3, while 1,000 shots require 2 iterations but roughly double cumulative shots.Across the tested parameter combinations, the best residual along a fixed-resource contour uses multiple IR iterations rather than a single high-precision call.Source: §6.3 · p. 21, Figure 3 · p. 21
- With fixed QPE precision, high precision can be reached in O(log(1/ζ)) iterations of a constant-depth circuit instead of one circuit whose depth grows polynomially in 1/ζ.The per-iteration depth grows approximately exponentially with q, while IR keeps q modest and total depth grows linearly with iteration count.Source: §6.3 · pp. 21–22, §6.4 · p. 22
7. Conclusion.
The experiments demonstrate geometric residual reduction and show that repeated low-precision quantum solves can be more resource-efficient than a single high-precision solve. The main remaining classical cost is computing the residual at each refinement step.
7. Conclusion.
- Experiments demonstrate geometric residual reduction and show repeated low-precision quantum solves can be more resource-efficient than a single high-precision solve.The framework is analyzed under QRAM, sparse-access, and LCU input models.Source: §7 · p. 22
- Residual computation still requires a classical matrix-vector multiplication at every refinement step.The paper identifies efficient quantum residual computation as a direction for future research.Source: §7 · p. 22