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 (
randnandsprandn). - 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