A mixed-precision quantum-classical algorithm for solving linear systems

1. Problem Statement

The paper addresses the fundamental computational problem of solving a system of linear equations ($Ax = b$) where $A$ is a non-singular matrix and $b$ is a vector. While classical algorithms (e.g., Gaussian elimination) are highly mature, quantum algorithms offer the potential for exponential speedups under specific conditions.

However, current quantum approaches, specifically the Quantum Singular Value Transformation (QSVT), face significant limitations:

• Resource Intensity: Achieving high accuracy (e.g., error $< 10^{-5}$) requires high-degree polynomial approximations, leading to deep quantum circuits and excessive resource demands.
• Conditioning Sensitivity: The complexity scales poorly with the condition number ($\kappa$) of the matrix.
• Hardware Constraints: The depth required for high-precision QSVT exceeds the capabilities of current Noisy Intermediate-Scale Quantum (NISQ) devices, necessitating a Large Scale Quantum (LSQ) context.

The core challenge is to reduce the quantum cost while maintaining acceptable solution accuracy.

2. Methodology

The authors propose a hybrid quantum-classical algorithm that combines the QSVT method with mixed-precision iterative refinement. This approach leverages the speed of low-precision quantum computation and the accuracy of high-precision classical computation.

Core Algorithm (Algorithm 2)

The process follows these steps:

1. Initial Low-Precision Solution ($x_0$):
   • Compute an initial approximate solution using QSVT on a Quantum Processing Unit (QPU).
   • This step uses low precision ($\epsilon_l$), allowing for a lower-degree polynomial approximation and fewer quantum gate operations.
   • The QPU handles the block-encoding of $A^\dagger$ and the application of the transformation.
2. Iterative Refinement Loop:
   • Residual Calculation (CPU): Compute the residual $r_i = b - Ax_i$ using high precision (classical CPU).
   • Correction Calculation (QPU): Solve the correction system $Ae_i = r_i$ using the QSVT method again, but still at the low precision $\epsilon_l$.
   • Update (CPU): Update the solution $x_{i+1} = x_i + e_i$ using high precision.
3. Termination: The loop continues until the scaled residual $\omega = \|b - A\tilde{x}\| / \|b\|$ meets the target accuracy $\epsilon$.

Key Technical Adaptations

• Normalization: Since quantum algorithms require normalized states, the vector $b$ is normalized before input. The norm $\|x\|$ is recovered on the CPU by solving a minimization problem after the QSVT measurement.
• Hybrid Data Flow: The matrix $A$ (via block-encoding circuits) is transferred once. In subsequent iterations, only the residual vector $r_i$ (encoded as a state preparation circuit) is transferred to the QPU, minimizing communication overhead.
• Polynomial Approximation: The inverse function is approximated using Chebyshev polynomials. The degree of the polynomial is adapted to the low precision $\epsilon_l$ rather than the final target $\epsilon$, significantly reducing circuit depth.

3. Key Contributions

A. Theoretical Analysis

• Convergence Proof: The authors prove (Theorem III.1) that the algorithm converges if $\epsilon_l \kappa < 1$. The scaled residual contracts by a factor of $\epsilon_l \kappa$ at each iteration.
• Iteration Bound: The number of iterations required to reach target accuracy $\epsilon$ is bounded by $\lceil \log(\epsilon) / \log(\epsilon_l \kappa) \rceil$.
• Complexity Reduction:
  • Quantum Cost: The total complexity is reduced because the number of samples required scales as $O(1/\epsilon_l^2)$ (lower precision) rather than $O(1/\epsilon^2)$. Furthermore, the degree of the polynomial (and thus block-encoding calls) depends on $\log(\kappa/\epsilon_l)$ rather than $\log(\kappa/\epsilon)$.
  • Classical Cost: Classical operations (residual calculation, update) are performed in high precision but are computationally cheap compared to the quantum solver.

B. Complexity Comparison

The paper provides a detailed breakdown (Table I) showing that for high target accuracies ($\epsilon \ll \epsilon_l$), the mixed-precision approach is significantly more efficient than running QSVT directly at high precision. The savings come from:

1. Fewer quantum circuit executions (samples).
2. Lower polynomial degrees (fewer block-encoding calls).

C. Implementation

The authors implemented the algorithm using the myQLM quantum software stack (Python-based simulator). They utilized:

• Tree-based state preparation.
• Block-encoding techniques for tridiagonal matrices (Poisson equation) and random matrices.
• Numerical computation of QSVT phases.

4. Experimental Results

The authors conducted numerical experiments on random matrices and a discretized 1D Poisson equation ($N=16$, $n=4$ qubits).

• Convergence: The experiments confirmed the theoretical convergence rate. The scaled residual decreased linearly on a log-scale, matching the bound $\lceil \log(\epsilon) / \log(\epsilon_l \kappa) \rceil$.
• Condition Numbers: Tests were performed with condition numbers $\kappa = 10, 100, 200, 300$. The algorithm successfully converged even for $\kappa=300$ within the simulation time limits.
• Complexity Advantage: Figure 5 demonstrates that for a fixed condition number ($\kappa=2$), the number of block-encoding calls required by the mixed-precision method is drastically lower than a direct high-precision QSVT approach, especially as the target accuracy $\epsilon$ becomes very small.

5. Significance and Future Work

• Bridging the Gap: This work demonstrates a practical pathway for using quantum computers in High-Performance Computing (HPC) environments. It acknowledges that current quantum hardware cannot solve linear systems to high precision directly but can be a powerful component in a hybrid loop.
• Resource Efficiency: By offloading the "heavy lifting" of precision to classical CPUs and using the QPU only for the "coarse" solving steps, the algorithm makes quantum linear solvers feasible for larger problem sizes and higher condition numbers than previously thought possible with pure quantum approaches.
• Limitations: The current results are based on simulations. The authors note that real-world application requires fault-tolerant quantum hardware (LSQ context) and further testing on actual quantum devices to validate performance against noise and error rates.
• Broader Impact: The methodology validates the application of classical mixed-precision techniques (widely used in GPU-accelerated HPC) to the emerging field of quantum-classical hybrid computing.

In conclusion, the paper proposes a viable strategy to overcome the resource bottleneck of QSVT-based linear solvers, offering a roadmap for future hybrid algorithms that leverage the strengths of both classical and quantum architectures.