# A Catalyst Framework for the Quantum Linear System Problem via the Proximal Point Algorithm

arXiv: https://arxiv.org/abs/2406.13879 · HTML: https://mlsanity.com/paper/2406.13879/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 49 references that are in the map.
- First posted on arXiv 19 Jun 2024.

## Builds on (most cited first, 9 of 9)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Traces of Class/Cross-Class Structure Pervade Deep Learning Spectra](https://mlsanity.com/paper/2008.11865/) (2020)
- [Quantum Recommendation Systems](https://mlsanity.com/paper/1603.08675/) (2016)
- [A Universal Catalyst for First-Order Optimization](https://mlsanity.com/paper/1506.02186/) (2015)
- [Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning](https://mlsanity.com/paper/1910.06151/) (2019)
- [Quantum Computing: Lecture Notes](https://mlsanity.com/paper/1907.09415/) (2019)
- [Understanding Nesterov's Acceleration via Proximal Point Method](https://mlsanity.com/paper/2005.08304/) (2020)
- [Convergence and Stability of the Stochastic Proximal Point Algorithm with Momentum](https://mlsanity.com/paper/2111.06171/) (2021)
- [Improving quantum linear system solvers via a gradient descent perspective](https://mlsanity.com/paper/2109.04248/) (2021)

## Abstract (arXiv)

Solving systems of linear equations is a fundamental problem, but it can be computationally intensive for classical algorithms in high dimensions. Existing quantum algorithms can achieve exponential speedups for the quantum linear system problem (QLSP) in terms of the problem dimension, but the advantage is bottlenecked by condition number of the coefficient matrix. In this work, we propose a new quantum algorithm for QLSP inspired by the classical proximal point algorithm (PPA). Our proposed method can be viewed as a meta-algorithm that allows inverting a modified matrix via an existing textttQLSPsolver, thereby directly approximating the solution vector instead of approximating the inverse of the coefficient matrix. By carefully choosing the step size η, the proposed algorithm can effectively precondition the linear system to mitigate the dependence on condition numbers that hindered the applicability of previous approaches. Importantly, this is the first iterative framework for QLSP where a tunable parameter η and initialization x0 allows controlling the trade-off between the runtime and approximation error.