A Catalyst Framework for the Quantum Linear System Problem via the Proximal Point Algorithm
This work addresses a fundamental computational bottleneck in quantum algorithms for linear systems, offering a novel iterative approach with practical implications for quantum computing applications.
The authors tackled the quantum linear system problem (QLSP) by proposing a new quantum algorithm based on the proximal point algorithm (PPA), which directly approximates the solution vector rather than the matrix inverse. Their method effectively mitigates the condition number dependence that bottlenecked previous approaches, introducing the first iterative framework with tunable parameters for controlling runtime-accuracy trade-offs.
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 \texttt{QLSP\_solver}, 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 $x_0$ allows controlling the trade-off between the runtime and approximation error.