Fast and Practical Quantum-Inspired Classical Algorithms for Solving Linear Systems

Qian Zuo, Tongyang Li

TL;DR

This paper introduces new classical algorithms for solving linear systems that are inspired by quantum computing. These algorithms significantly improve upon previous "quantum-inspired" methods by using a momentum technique, achieving faster convergence and matching the theoretical performance of quantum algorithms for sparse systems.

What Problem Does This Paper Address?

Solving linear systems of equations ($Ax = b$) is a fundamental problem in many scientific and engineering fields. While quantum computers offer potential speedups for this task, building and running quantum computers is challenging. "Quantum-inspired" classical algorithms aim to bridge this gap by developing classical algorithms that mimic the efficiency of quantum algorithms, often by using similar data structures and computational models. However, existing quantum-inspired algorithms for linear systems have had impractically high polynomial dependencies on problem parameters like the condition number, limiting their real-world applicability. This paper addresses this by developing faster and more practical quantum-inspired classical algorithms for solving linear systems.

Methods

The core innovation of this work is the application of the heavy ball momentum method to quantum-inspired algorithms for solving linear systems. This technique, borrowed from classical optimization, helps accelerate convergence by incorporating information from previous steps. The authors propose two specific algorithms:

  • Quantum-inspired Kaczmarz method with momentum: This method adapts the randomized Kaczmarz algorithm by adding a momentum term. For dense matrices, it achieves a time complexity of $\widetilde{O}(\kappa_F^4/\kappa\epsilon^2)$, a significant improvement over prior work. For $s$-sparse matrices, it achieves $\widetilde{O}(s\kappa\log(1/\epsilon))$, matching quantum lower bounds.
  • Quantum-inspired coordinate descent method with momentum: This algorithm is designed for symmetric positive-definite (SPD) matrices. For $s$-sparse SPD matrices, it achieves an impressive $\widetilde{O}(s\sqrt{\kappa}\log(1/\epsilon))$ complexity.

The analysis of these methods involves novel spectral norm concentration bounds and careful decomposition of momentum transition matrices.

Datasets

The authors evaluated their algorithms on:

  • Synthetic datasets: Both dense and sparse matrices were generated using MATLAB functions (randn and sprandn).
  • Real-world datasets: Matrices were sourced from the University of Florida Sparse Matrix Collection, covering various problem settings like linear programming, combinatorial problems, and power networks.

Key Insights and Ideas

  • Momentum is key for quantum-inspired speedups: Applying the heavy ball momentum method, a classical optimization technique, is crucial for achieving significant improvements in quantum-inspired algorithms for linear systems.
  • Bridging the gap to quantum: The proposed algorithms for sparse linear systems now match the theoretical performance of quantum algorithms, making them a more viable alternative.
  • Practicality is within reach: By reducing the polynomial dependence on condition numbers, these algorithms move closer to practical applicability, a major bottleneck for previous quantum-inspired methods.
  • Novel analysis techniques: The development of new spectral norm concentration bounds for random matrices is a valuable theoretical contribution.

Key Results

  • General (dense) matrices: The new algorithm achieves a time complexity of $\widetilde{O}(\kappa_F^4/\kappa\epsilon^2)$, improving upon the previous state-of-the-art.
  • $s$-sparse matrices: The algorithm achieves $\widetilde{O}(s\kappa\log(1/\epsilon))$ complexity, matching quantum lower bounds.
  • $s$-sparse and SPD matrices: The algorithm achieves $\widetilde{O}(s\sqrt{\kappa}\log(1/\epsilon))$ complexity, a significant speedup.
  • Numerical experiments: The proposed momentum-based methods (mRK, mRAK, mRCD) consistently outperformed their non-momentum counterparts (RK, RCD) in terms of iteration counts and CPU time across various synthetic and real-world datasets.

Limitations and Future Work

  • Open Questions: The authors pose several open questions:
  • Can momentum methods be applied to improve other quantum-inspired classical algorithms beyond linear systems?
  • Can other momentum methods (e.g., Nesterov) be explored?
  • Can theoretical results be further improved for averaged Kaczmarz methods, which showed superior performance in experiments despite not improving theoretical bounds?
  • Practicality: While the algorithms are faster, the paper notes that the performance of quantum-inspired algorithms can still degrade with increasing rank and condition numbers, suggesting that further practical optimizations might be needed.

Summary updated

Abstract

We propose fast and practical quantum-inspired classical algorithms for solving linear systems. Specifically, given sampling and query access to a matrix $A\in\mathbb{R}^{m\times n}$ and a vector $b\in\mathbb{R}^m$, we propose classical algorithms that produce a data structure for the solution $x\in\mathbb{R}^{n}$ of the linear system $Ax=b$ with the ability to sample and query its entries. The resulting $x$ satisfies $\|x-A^{+}b\|\leq\epsilon\|A^{+}b\|$, where $\|\cdot\|$ is the spectral norm and $A^+$ is the Moore-Penrose inverse of $A$. Our algorithm has time complexity $\widetilde{O}(\kappa_F^4/\kappa\epsilon^2)$ in the general case, where $\kappa_{F} =\|A\|_F\|A^+\|$ and $\kappa=\|A\|\|A^+\|$ are condition numbers. Compared to the prior state-of-the-art result [Shao and Montanaro, arXiv:2103.10309v2], our algorithm achieves a polynomial speedup in condition numbers. When $A$ is $s$-sparse, our algorithm has complexity $\widetilde{O}(s \kappa\log(1/\epsilon))$, matching the quantum lower bound for solving linear systems in $\kappa$ and $1/\epsilon$ up to poly-logarithmic factors [Harrow and Kothari]. When $A$ is $s$-sparse and symmetric positive-definite, our algorithm has complexity $\widetilde{O}(s\sqrt{\kappa}\log(1/\epsilon))$. Technically, our main contribution is the application of the heavy ball momentum method to quantum-inspired classical algorithms for solving linear systems, where we propose two new methods with speedups: quantum-inspired Kaczmarz method with momentum and quantum-inspired coordinate descent method with momentum. Their analysis exploits careful decomposition of the momentum transition matrix and the application of novel spectral norm concentration bounds for independent random matrices. Finally, we also conduct numerical experiments for our algorithms on both synthetic and real-world datasets, and the experimental results support our theoretical claims.
BibTeX
@misc{zuo2023fast,
  author = {Qian Zuo and Tongyang Li},
  title = {{Fast and Practical Quantum-Inspired Classical Algorithms for Solving Linear Systems}},
  year = {2023},
  eprint = {2307.06627},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2307.06627},
}
Figure