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

## Abstract

Abstract 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 even such a theoretical advantage is bottlenecked by the 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 QLSP_solver , thereby directly approximating the solution vector instead of approximating the inverse of the coefficient matrix. By carefully choosing the step size η 𝜂 \eta italic_η , the proposed algorithm can effectively precondition the linear system to mitigate the dependence on condition numbers that hindered the applicability of previous approaches.

## 1 Introduction

Background.
Solving systems of linear equations is a fundamental problem with many applications spanning science and engineering.
Mathematically, for a given (Hermitian) matrix $A\in\mathbb{C}^{N\times N}$ and vector $b\in\mathbb{C}^{N}$, the goal is to find the $N$-dimensional vector $x^{\star}$ that satisfies $Ax^{\star}=b$.
While classical algorithms, such as Gaussian elimination [, ], conjugate gradient method [], $LU$ factorization [, ], $QR$ factorization [, ], and iterative Krylov subspace methods [, ], can solve this problem, their complexity scales (at worst) cubically with $N$, the dimension of $A$, motivating the development of quantum algorithms that could potentially achieve speedups.

Indeed, for the quantum linear system problem (QLSP) in Definition 1,
Harrow, Hassidim, and Lloyd (a.k.a. the HHL algorithm) [] showed that the dependence on the problem dimension exponentially reduces to $\mathcal{O}\left(\text{poly}\log(N)\right)$, with query complexity of $\mathcal{O}(\kappa^{2}/\varepsilon)$,
under some (quantum) access model for $A$ and $b$ (c.f., Definitions 2 and 3).
Here, $\kappa$ is the condition number of $A$, defined as the ratio of the largest to the smallest singular value of $A$.
Subsequent works, such as the work by Ambainis [] and by Childs, Kothari, and Somma [] (a.k.a. the CKS algorithm)
improve the dependence on $\kappa$ and $\varepsilon$; see Table 1.
The best quantum algorithm for QLSP is based on the discrete adiabatic theorem [], achieving the query complexity of $\mathcal{O}(\kappa\cdot\log(1/\varepsilon))$, matching the lower bound [].(^1^11Note that this also matches the iteration complexity of the (classical) conjugate gradient method [].)

Challenges in existing methodologies.
A common limitation of the existing quantum algorithms is that the dependence on the condition number $\kappa$ must be small to achieve the quantum advantage.
To put more context, for any quantum algorithm in Table 1 to achieve an exponential advantage over classical algorithms, $\kappa$ needs to be in the order of $\text{poly}\log(N)$, where $N$ is the dimension of $A$.
For instance, for $N=10^{3},$ $\kappa$ needs to be around $4$ to exhibit the exponential advantage.
However, condition numbers are often large in real-world problems [].

Moreover, it was proven [, Proposition 6] that for QLSP, even when $A$ is positive-definite, the dependence on condition number cannot be improved from $\mathcal{O}(\kappa)$. This is in contrast to the classical algorithms, such as the conjugate gradient method, which achieves $\mathcal{O}(\sqrt{\kappa})$ reduction in complexity for the linear systems of equations with $A\succ 0$. Such observation reinforces the importance of alleviating the dependence on the condition number $\kappa$ for quantum algorithms, which is our aim.

Our contributions.
We present a novel meta-algorithm for solving the QLSP, based on the proximal point algorithm (PPA) [, ]; see Algorithm 1.
Notably, in contrast to some existing methods that approximate $A^{-1}$ [, , , , ],
our algorithm directly approximates $x^{\star}=A^{-1}b$ through an iterative process based on PPA.
Classically, PPA is known to improve the “conditioning” of the problem at hand, compared to the gradient descent [, , ]; it can also be accelerated [, ].

An approximate proximal point algorithm for classical convex optimization has been proposed under the name of “catalyst” [] in the machine learning community.
Our proposed method operates similarly and can be viewed as a generic acceleration scheme for QLSP where one can plug in different QLSP_solver –e.g., HHL, CKS– to achieve generic (constant-level) acceleration. In Figure 1, we illustrate the case where the best quantum algorithm for QLSP [], based on the discrete adiabatic theorem, is utilized as a subroutine for Algorithm 1. The improvement in the query complexitycompared to the original algorithm to achieve a fixed accuracy increases as $\kappa$ increases.

Figure: Figure 1: Query complexity scaling with respect to the condition number $\kappa$. Here, the best quantum algorithm [] is used as QLSP_solver for the subroutine in Algorithm 1. Simply by “wrapping” the QLSP_solver, one can achieve much better scaling with respect to the condition number $\kappa$.
Refer to caption: extracted/5679239/figures/kappa-scaling.png

Intuitively, by the definition of PPA detailed in Section 3, our proposed method allows to invert a modified matrix $I+\eta A$ and arrive at the same solution $A^{-1}b$, as shown below:

$$ $x_{t+1}=(I+\eta A)^{-1}(x_{t}+\eta b)\underset{\eta\rightarrow\infty}{=}A^{-1}b.$ $$

Yet, the key feature and the main distinction here is the introduction of a tunable (step size) parameter $\eta$ that allows pre-conditioning the linear system. By carefully choosing $\eta$, we can invert the modified matrix $I+\eta A$ that is better conditioned than $A$, thereby mitigating the dependence on $\kappa$ of the existing quantum algorithms; see also Remark 3 and Figure 1.

Our meta-algorithmic framework complements and provides advantages over prior works on QLSP. Most importantly, it alleviates the strict requirements on the condition number, enabling quantum speedups for a broader class of problems where $\kappa$ may be large. Moreover, the $\eta$ parameter can be tuned to balance the convergence rate and precision demands, providing greater flexibility in optimizing the overall algorithmic complexity.

In summary, our contributions and findings are as follows:

- •
We propose a meta-algorithmic framework for the quantum linear system problem (QLSP) based on the proximal point algorithm. Unlike existing quantum algorithms for QLSP, which rely on different unitary approximations of $A^{-1}$, our proposed method allows to invert a modified matrix with a smaller condition number (c.f., Remark 3 and Lemma 1).
- •
To our knowledge, this is the first framework for QLSP where a tunable parameter $\eta$ allows the user to control the trade-off between the runtime (query complexity) and the approximation error (solution quality). Importantly, there exist choices of $\eta>0$ that allow to decrease the runtime while maintaining the same error level (c.f., Theorem 3).
- •
Our proposed method allows to achieve significant constant-level improvements in the query complexity, even compared to the best quantum algorithm for QLSP [], simply by using it as a subroutine of Algorithm 1. This is possible as the improvement “grows faster” than the overhead (c.f., Figure 2 and Theorem 6).

## 2 Problem Setup and Related Work

Notation.
Matrices are represented with uppercase letters as in $A\in\mathbb{C}^{N\times N}$; vectors are represented with lowercase letters as in $b\in\mathbb{C}^{N}$, and are distinguished from scalars based on the context.
The condition number of a matrix $A$, denoted as $\kappa$, is the ratio of the largest to the smallest singular value of $A$.
We denote $\|\cdot\|$ as the Euclidean $\ell_{2}$-norm.
Qubit is the fundamental unit in quantum computing, analogous to the bit in classical computing.
The state of a qubit is represented using the bra-ket notation, where a single qubit state $|\psi\rangle\in\mathbb{C}^{2}$ can be expressed as a linear combination of the basis states $|0\rangle=[0\;1]^{\top}\in\mathbb{C}^{2}$ and $|1\rangle=[1\;0]^{\top}\in\mathbb{C}^{2}$, as in $|\psi\rangle=\alpha|0\rangle+\beta|1\rangle$; here, $\alpha,\beta\in\mathbb{C}$ are called amplitudes and encode the probability of the qubit collapsing to either, such that $|\alpha|^{2}+|\beta|^{2}=1$.
Thus, $|\psi\rangle$ represents a normalized column vector by definition.
$|\cdot\rangle$ is a column vector (called bra), and its conjugate transpose (called ket), denoted by $\langle\cdot|,$ is defined as $\langle\cdot|=|\cdot\rangle^{*}.$
Generalizing the above, an $n$-qubit state is a unit vector in $n$-qubit Hilbert space, defined as the Kronecker product of $n$ single qubit states, i.e., $\mathcal{H}=\otimes_{i=1}^{n}\mathbb{C}^{2}\cong\mathbb{C}^{2^{n}}$.
It is customary to write $2^{n}=N$.
Quantum states can be manipulated using quantum gates, represented by unitary matrices that act on the state vectors.
For example, a single-qubit gate $U\in\mathbb{C}^{2\times 2}$ acting on a qubit state $|\psi\rangle$ transforms it to $U|\psi\rangle$, altering the state’s probability amplitudes according to the specific operation represented by $U$.

### 2.1 The Quantum Linear System Problem

In the quantum setting, the goal of the quantum linear system problem (QLSP) is to prepare a quantum state proportional to the vector $x^{\star}$. That is, we want to output
$|x^{\star}\rangle:=\frac{\sum_{i}x^{\star}_{i}|i\rangle}{\|\sum_{i}x^{\star}_{
i}|i\rangle\|}$
where the vector $x^{\star}=[x^{\star}_{1},\dots,x^{\star}_{N}]^{\top}$ satisfies $Ax^{\star}=b$.
Formally, we define the QLSP problem as below.

###### Definition 1 (Quantum Linear System Problem [ 9 ] ) .

Let $A$ be an $N\times N$ Hermitian matrix satisfying $\|A\|=1$ with condition number $\kappa$ and at most $s$ nonzero entries in any row or column. Let $b$ be an $N$-dimensional vector, and let $x^{\star}:=A^{-1}b$. We define the quantum states $|b\rangle$ and $|x^{\star}\rangle$ as in:

$$ $\displaystyle|b\rangle:=\frac{\sum_{i=0}^{N-1}b_{i}|i\rangle}{\left\|\sum_{i=0 }^{N-1}b_{i}|i\rangle\right\|}\quad\text{and}\quad|x^{\star}\rangle:=\frac{ \sum_{i=0}^{N-1}x^{\star}_{i}|i\rangle}{\Big{\|}\sum_{i=0}^{N-1}x^{\star}_{i}| i\rangle\Big{\|}}.$ (1) $$

Given access to $A$ via $\mathcal{P}_{A}$ in Definition 3 or $\mathcal{U}_{A}$ in Definition 4, and access to the state $|b\rangle$ via $\mathcal{P}_{B}$ in Definition 2, the goal of QLSP is to output a state $|\tilde{x}\rangle$ such that $\||\tilde{x}\rangle-|x^{\star}\rangle\|\leqslant\varepsilon$.

As in previous works [, , , , , ], we assume that access to $A$ and $b$ is provided by black-box subroutines that we detail below. We start with the state preparation oracle for the vector $b\in\mathbb{C}^{N}$.

###### Definition 2 (State preparation oracle [ 20 ] ) .

Given a vector $b\in\mathbb{C}^{N}$, there exists a procedure $\mathcal{P}_{B}$ that prepares the state $|b\rangle:=\frac{\sum_{i}b_{i}|i\rangle}{\|\sum_{i}b_{i}|i\rangle\|}$ in time $\mathcal{O}(\text{poly}\log(N))$.

We assume two encoding models for $A$: the sparse-matrix-access in Definition 3 denoted by $\mathcal{P}_{A}$, and the matrix-block-encoding model [, ] in Definition 4, denoted by $\mathcal{U}_{A}$, respectively.

###### Definition 3 (Sparse matrix access [ 9 ] ) .

Given a $N\times N$ Hermitian matrix $A$ with operator norm $\|A\|\leqslant 1$ and at most $s$ nonzero entries in any row or column, $\mathcal{P}_{A}$ allows the following mapping:

$$ $\displaystyle|j,\ell\rangle$ $\displaystyle\mapsto|j,\nu(j,\ell)\rangle$ $\displaystyle\forall j\in[N]\text{ and }\ell\in[s],$ (2) $\displaystyle|j,k,z\rangle|0\rangle$ $\displaystyle\mapsto|j,k,z\oplus A_{jk}\rangle$ $\displaystyle\forall j,k\in[N],$ (3) $$

where $\nu:[N]\times[s]\rightarrow[N]$ in (2) computes the row index of the $\ell$th nonzero entry of the $j$th column, and the third register of (3) holds a bit string representing the entry of $A_{jk}$.

###### Definition 4 (Matrix block-encoding [ 15 ] ) .

A unitary operator $\mathcal{U}_{A}$ acting on $n+c$ qubits is called an $(\alpha,c,\varepsilon)$-matrix-block-encoding of a $n$-qubit operator $A$ if

$$ $\|A-\alpha((\langle 0^{c}|\otimes I)~{}\mathcal{U}_{A}~{}(|0^{c}\rangle\otimes I ))\|\leqslant\varepsilon.$ $$

The above can also be expressed as follows:

$$ $\mathcal{U}_{A}=\begin{bmatrix}\nicefrac{{\tilde{A}}}{{\alpha}}&*\\ *&*\end{bmatrix}\quad\text{with}\quad\|\tilde{A}-A\|\leqslant\varepsilon,$ $$

where $*$’s denote arbitrary matrix blocks with appropriate dimensions.

In [], it was shown that a $(s,1,0)$-matrix-block-encoding of $A$ is possible using a constant number of calls to $\mathcal{P}_{A}$ in Definition 3 (and $\mathcal{O}(\text{poly}(n))$ extra elementary gates).
In short, $\mathcal{P}_{A}$ in Definition 3 implies efficient implementation of $\mathcal{U}_{A}$ in Definition 4 (c.f., [, Lemma 48]).
We present both for completeness as different works rely on different access models; however, our proposed meta-algorithm can provide generic acceleration for any QLSP solver, regardless of the encoding method.

**Table 1: Query complexities and key results used in related works on QLSP. Our proposed framework in Algorithm 1 allows to improve the dependence on the condition number $\kappa$ for any QLSP_solver.**
| QLSP_solver | Query Complexity | Key Technique/Result |
| --- | --- | --- |
| HHL [] | $\mathcal{O}\left(\kappa^{2}/\varepsilon\right)$ | First quantum algorithm for QLSP |
| Ambainis [] | $\mathcal{O}\left(\kappa\log^{3}(\kappa)/\varepsilon^{3}\right)$ | Variable Time Amplitude Amplification |
| CKS [] | $\mathcal{O}\left(\kappa\cdot\text{poly}\log(\kappa/\varepsilon)\right)$ | (Truncated) Chebyshev bases via LCU |
| Subaşı et al. [] | $\mathcal{O}\left((\kappa\log\kappa)/\varepsilon)\right)$ | Adiabatic Randomization Method |
| An & Lin [] | $\mathcal{O}\left(\kappa\cdot\text{poly}\log(\kappa/\varepsilon)\right)$ | Time-Optimal Adiabatic Method |
| Lin & Tong [] | $\mathcal{O}\left(\kappa\cdot\log(\kappa/\varepsilon)\right)$ | Zeno Eigenstate Filtering |
| Costa, et al. [] | $\mathcal{O}\left(\kappa\cdot\log(1/\varepsilon)\right)$ | Discrete Adiabatic Theorem |
| Ours | $\kappa\rightarrow\frac{\kappa(1+\eta)}{\kappa+\eta}$ for all above | Proximal Point Algorithm |

###### Definition 1 (Quantum Linear System Problem [ 9 ] ) .

###### Definition 2 (State preparation oracle [ 20 ] ) .

###### Definition 3 (Sparse matrix access [ 9 ] ) .

###### Definition 4 (Matrix block-encoding [ 15 ] ) .

### 2.2 Related Work

Quantum algorithms.
We summarize the related quantum algorithms for QLSP and their query complexities in Table 1; all QLSP_solvers share the exponential improvement on the input dimension, $\mathcal{O}(\text{poly}\log(N))$.
The HHL algorithm [] utilizes quantum subroutines including $(i)$ Hamiltonian simulation [, , ] that applies the unitary operator $e^{iAt}$ to $|b\rangle$ for a superposition of different times $t$, $(ii)$ phase estimation [] that allows to decompose $|b\rangle$ into the eigenbasis of
$A$ and to find its corresponding eigenvalues, and $(iii)$ amplitude amplification [, , ] that allows to implement the final state with amplitudes the same with the elements of $x^{\star}$.
Subsequently, [] achieved a quadratic improvement on the condition number at the cost of worse error dependence; the main technical contribution was to improve the amplitude amplification, the previous bottleneck.
CKS [] significantly improved the suboptimality by the linear combination of unitaries. We review these subroutines in the appendix.

[] is the state-of-the-art QLS algorithm based on the adiabatic framework, which was spearheaded by [] and improved in [, ]. These are significantly different from the aforementioned HHL-based approaches. Importantly, Algorithm 1 is oblivious to such differences and provides generic acceleration.

Lower bounds.
Along with the proposal of the first quantum algorithm for QLSP, [] also proved the lower bound of $\Omega(\kappa)$ queries to the entries of the matrix is needed for general linear systems. In [, Proposition 6], this lower bound was surprisingly extended to the case of positive-definite systems. This is in contrast to the classical optimization literature, where methods such as the conjugate gradient method [] achieve $\sqrt{\kappa}$-acceleration for positive-definite systems.

## 3 The Proximal Point Algorithm for QLSP

We now introduce our proposed methodology, summarized in Algorithm 1. At a high level, our method can be viewed as a meta-algorithm, where one can plug in any existing QLSP_solver as a subroutine to achieve generic acceleration. We first review the proximal point algorithm (PPA), a classical optimization method on which Algorithm 1 is based.

### 3.1 The Proximal Point Algorithm

We take a step back from the QLSP in Definition 1 and introduce the proximal point algorithm (PPA), a fundamental optimization method in convex optimization [, , , ].
PPA is an iterative algorithm that proceeds by minimizing the original function plus an additional quadratic term, as in:

$$ $x_{t+1}=\arg\min_{x}\Big{\{}f(x)+\frac{1}{2\eta}\|x-x_{t}\|_{2}^{2}\Big{\}}.$ (4) $$

As a result, it changes the “conditioning” of the problem; if $f(\cdot)$ is convex, the optimization problem in (4) can be strongly convex [].
By the first-order optimality condition [, Eq. (4.22)], (4) can be written in the following form, also known as the implicit gradient descent (IGD):

$$ $\displaystyle x_{t+1}$ $\displaystyle=x_{t}-\eta\nabla f(x_{t+1}).$ (5) $$

(5) is an implicit method and generally cannot be implemented. However, the case we are interested in is the quadratic minimization problem:

$$ $\min_{x}f(x)=\frac{1}{2}x^{\top}Ax-b^{\top}x.$ (6) $$

Then, we have the closed-form update for (5) as follows:

$$ $\displaystyle x_{t+1}$ $\displaystyle=x_{t}-\eta(Ax_{t+1}-b)=x_{t}-\eta A(x_{t+1}-x^{\star}).$ $$

In particular, by rearranging and unfolding, we have

$$ $\displaystyle x_{t+1}$ $\displaystyle=(I+\eta A)^{-1}(x_{t}+\eta b)=\dots=(I+\eta A)^{-(t+1)}x_{0}+ \eta b\sum_{k=1}^{t+1}(I+\eta A)^{-k}.$ (7) $$

The above expression sheds some light on how applying PPA can differ from simple inversion: $A^{-1}b$.
In particular, PPA enables to invert a modified matrix $I+\eta A$ based on $\eta$; see also Remark 3 below.

Further, since $b=Ax^{\star}$, we can equivalently express the series of operations in (7) as follows:

$$ $\displaystyle x_{t+1}-x^{\star}$ $\displaystyle=(I+\eta A)^{-1}(x_{t}-x^{\star})=\cdots=(I+\eta A)^{-t}(x_{0}-x^ {\star}).$ (8) $$

The above expression helps compute the number of iterations required for PPA, given $\eta>0$, for finding $\varepsilon$-approximate solution, as we detail in Section 4.

### 3.2 Meta-Algorithm for QLSP via PPA

We present our proposed method, which is extremely simple as summarized in Algorithm 1.

Figure: Algorithm 1 Proximal Point Algorithm for the Quantum Linear System Problem

Line 2 is the cornerstone of the algorithm where one can employ any QLSP_solver –like HHL [], CKS [] or the recent work based on discrete adiabatic approach []– to the (normalized) matrix $(I+\eta A)/\|I+\eta A\|$, enabled by the PPA approach.
In other words, line 3 can be seen as the output of applying $\texttt{QLSP_solver}(\frac{I+\eta A}{\|I+\eta A\|},|x_{0}+\eta b\rangle)$. We make some remarks on the input.

###### Remark 1 (Access to $(I+\eta A)/\|I+\eta A\|$ ) .

Our algorithm necessitates an oracle $P_{\eta,A}$, which can provide either sparse access to $(I+\eta A)/\|I+\eta A\|$ (as in Definition 3) or its block encoding (as in Definition 4). For sparse access to $(I+\eta A)/\|I+\eta A\|$, direct access is feasible from sparse access to $A$, when all diagonal entries of $A$ are non-zero. Specifically, the access described in (3) is identical to that of $A$, while the access in (2) modifies $A_{jj}$ to $(1+\eta A_{jj})/\|I+\eta A\|$. If $A$ contains zero diagonal entries, sparse access to $(I+\eta A)/\|I+\eta A\|$ requires only two additional uses of (3).

For block encoding, $(I+\eta A)/\|I+\eta A\|$ can be achieved through a linear combination of block-encoded matrices, as demonstrated in [, Lemma 52]. This method allows straightforward adaptation of existing data structures that facilitate sparse-access or block-encoding of $A$ to also support $(I+\eta A)/\|I+\eta A\|$.

In addition, original data or data structures that provide sparse access or block-encoding of $A$ can be easily modified for access to $(I+\eta A)/\|I+\eta A\|$. For instance, suppose that we are given a matrix as a sum of multiple small matrices as in the local Hamiltonian problem or Hamiltonian simulation (see [] for an introduction). Then the sparse access and block encoding of both $A$ and $(I+\eta A)/\|I+\eta A\|$ can be efficiently derived from the sum of small matrices.

###### Remark 2 (Access to $|x_{0}+\eta b\rangle$ ) .

We prepare the initial state $|x_{0}+\eta b\rangle$, instead of $|b\rangle$, reflecting the PPA update in (7). For this step, we assume there exists an oracle $\mathcal{P}_{b,x_{0},\eta}$ such that $|x_{0}+\eta b\rangle$ can be efficiently prepared similarly to Definition 2; otherwise, we can simply initialize $x_{0}$ with zero vector.

Since we are inverting the (normalized) modified matrix $\frac{I+\eta A}{\|I+\eta A\|}$, the spectrum changes as follows.

###### Lemma 1 .

Let $A$ be an $N\times N$ Hermitian matrix satisfying $\|A\|=1$ with condition number $\kappa$. Then, the condition number of the modified matrix in Algorithm 1, $\frac{I+\eta A}{\|I+\eta A\|}$, is given by $\hat{\kappa}=\frac{\kappa(1+\eta)}{\kappa+\eta}$.

Notice that the modified condition number $\hat{\kappa}$ depends both on $\kappa$ and the step size parameter $\eta$ for PPA. As a result, $\eta$ plays a crucial role in the overall performance of Algorithm 1. The introduction of the tunable parameter $\eta$ in the context of QLSP is a main property that differentiates Algorithm 1 from other quantum algorithms. We summarize the trade-off of $\eta$ in the following remark.

###### Remark 3 .

The modified condition number, $\hat{\kappa}=\frac{\kappa(1+\eta)}{\kappa+\eta}$, in conjunction with the PPA convergence in (8) introduces a trade-off based on the tunable parameter $\eta.$

- •
Large $\eta$ regime: setting large $\eta$ allows PPA to converge fast, as can be seen in (15). On the other hand, the benefit of the modified condition number diminishes and recovers the original $\kappa$:
$\displaystyle\hat{\kappa}=\frac{\kappa(1+\eta)}{\kappa+\eta}\underset{\eta
\rightarrow\infty}{\longrightarrow}\kappa,$
- •
Small $\eta$ regime: setting small $\eta$ slows down the convergence rate of PPA and requires more number of iterations, as can be seen in (15). On the other hand, the modified condition number becomes increasingly better conditioned, as in:
$\displaystyle\hat{\kappa}=\frac{\kappa(1+\eta)}{\kappa+\eta}\underset{\eta
\rightarrow 0}{\longrightarrow}1.$

###### Remark 1 (Access to ( I + η ⁢ A ) / ‖ I + η ⁢ A ‖ 𝐼 𝜂 𝐴 norm 𝐼 𝜂 𝐴 (I+\eta A)/\|I+\eta A\| ( italic_I + italic_η italic_A ) / ∥ italic_I + italic_η italic_A ∥ ) .

###### Remark 2 (Access to | x 0 + η ⁢ b ⟩ ket subscript 𝑥 0 𝜂 𝑏 |x_{0}+\eta b\rangle | italic_x start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT + italic_η italic_b ⟩ ) .

###### Lemma 1 .

###### Remark 3 .

## 4 Theoretical Analysis

As shown in Algorithm 1 as well as the PPA iteration explained in (7), the main distinction of our proposed method from the existing QLSP algorithms is that we invert the modified matrix $(I+\eta A)/\|I+\eta A\|$ instead of the original matrix $A.$
Precisely, our goal is to bound the following:

$$ $\bigg{\|}\underbrace{\big{|}\psi_{I+\eta A,x_{0}+\eta b}\big{\rangle}-{\color[ rgb]{.5,.5,.5}\big{|}\big{(}\tfrac{I+\eta A}{\|I+\eta A\|}\big{)}^{-1}(x_{0}+ \eta b)\big{\rangle}}}_{\texttt{QLSP_solver}\text{ error }(\text{c.f., Proposition}~{}\ref{prop:qlsp_error})}+\underbrace{{\color[rgb]{.5,.5,.5}\big{ |}\big{(}\tfrac{I+\eta A}{\|I+\eta A\|}\big{)}^{-1}(x_{0}+\eta b)\big{\rangle} }-|A^{-1}b\rangle}_{\text{PPA error }(\text{c.f., Proposition}~{}\ref{prop:ppa -numiter})}\bigg{\|}\leqslant\varepsilon,$ (9) $$

where $\big{|}\psi_{I+\eta A,x_{0}+\eta b}\big{\rangle}$ is the output of Algorithm 1, and $|A^{-1}b\rangle=\frac{A^{-1}b}{\|A^{-1}b\|}$ is the target quantum state of QLSP based on Definition 1. In between, the term $\big{|}\big{(}\tfrac{I+\eta A}{\|I+\eta A\|}\big{)}^{-1}(x_{0}+\eta b)\big{\rangle}$ is added and subtracted, reflecting the modified inversion due to PPA. Specifically, the first pair of terms quantifies the error coming from the inexactness of any QLSP_solver used as a subroutine of Algorithm 1. The second pair of terms quantifies the error coming from PPA in estimating $A^{-1}b$, as can be seen in (8).
In the following subsections, we analyze each term carefully.
Due to space limitations, we defer all proofs to the appendix at the end of the paper.

Figure: Figure 2: How the “improvement” term, the “overhead” term, and their sum “total” allows improvement compared to the baselines from [] and [] (c.f., Theorem 6). Right panel: using CKS [] as baseline (c.f., Theorem 4); Left panel: using [] as baseline (c.f., Theorem 5). The key insight is that the rate of “improvement” is faster than the rate of “overhead,” which plateaus quickly thanks to the logarithm as can be seen in Theorem 6.
Refer to caption: extracted/5679239/figures/improve-costa.png

### 4.1 Inverting the Modified Matrix ( I + η ⁢ A ) / ‖ I + η ⁢ A ‖ 𝐼 𝜂 𝐴 norm 𝐼 𝜂 𝐴 (I+\eta A)/\|I+\eta A\| ( italic_I + italic_η italic_A ) / ∥ italic_I + italic_η italic_A ∥

In the first part, we apply any QLSP_solver
to invert the modified matrix $(I+\eta A)/\|I+\eta A\|$.
Importantly, we first need to encode it into a quantum computer, and this requires normalization so that the resulting encoded matrix is unitary, which is necessary for any quantum computer operation (c.f.,
Remarks 1 and 2).
As in this part we are simply invoking existing QLSP_solver, we just have to control the error $\varepsilon_{1}$ and its contribution to the final accuracy $\varepsilon$, as summarized below.

###### Proposition 1 ( QLSP_solver error) .

Assume access to the oracle $\mathcal{P}_{\eta,A}$ in Algorithm 1, similarly to the Definition 3 or 4 (c.f., Remark 1). Further, assume access to the oracle $\mathcal{P}_{b,x_{0},\eta}$ similarly to the Definition 2 (c.f., Remark 2), respectively.
Then, there exists quantum algorithms, such as the ones in Table 1,
satisfying

$$ $\bigg{\|}\Big{|}\psi_{I+\eta A,x_{0}+\eta b}\Big{\rangle}-\Big{|}\big{(}\tfrac {I+\eta A}{\|I+\eta A\|}\big{)}^{-1}(x_{0}+\eta b)\Big{\rangle}\bigg{\|} \leqslant\varepsilon_{1}.$ (10) $$

###### Example 1 (CKS polynomial [ 9 ] ) .

CKS performed the following polynomial approximation of $A^{-1}$:

$$ $A^{-1}\approx P(A)=\sum_{i}\alpha_{i}\mathcal{T}_{i}(A),$ (11) $$

where $\mathcal{T}_{i}$ denotes the Chevyshev polynomials (of the first kind).
Then, given that $\|P(A)-A^{-1}\|\leqslant\varepsilon_{1}<\frac{1}{2}$,
[, Proposition 9] proves the following:

$$ $\displaystyle\left\|\frac{P(A)|\phi\rangle}{\big{\|}P(A)|\phi\rangle\big{\|}}- \frac{A^{-1}|\phi\rangle}{\big{\|}A^{-1}|\phi\rangle\big{\|}}\right\|\leqslant 4 \varepsilon_{1}.$ (12) $$

Adapting Example 1 to Algorithm 1.
The approximation in (11) is only possible when the norm of the matrix to be inverted is upper-bounded by 1.
Hence, we can use the following approximation:

$$ $\displaystyle\|I+\eta A\|^{-1}\sum_{i}\alpha_{i}\mathcal{T}_{i}\left(\frac{I+ \eta A}{\|I+\eta A\|}\right)=\|I+\eta A\|^{-1}\cdot P\left(\frac{I+\eta A}{\|I +\eta A\|}\right),$ (13) $$

which allows similar step as (12) to hold, and further allows the dependence on $\kappa$ for the CKS algorithm to be alleviated as summarized in Lemma 1; see also the illustration in Figure 2 (right).

###### Proposition 1 ( QLSP_solver error) .

###### Example 1 (CKS polynomial [ 9 ] ) .

### 4.2 Approximating x ⋆ = A − 1 ⁢ b superscript 𝑥 ⋆ superscript 𝐴 1 𝑏 x^{\star}=A^{-1}b italic_x start_POSTSUPERSCRIPT ⋆ end_POSTSUPERSCRIPT = italic_A start_POSTSUPERSCRIPT - 1 end_POSTSUPERSCRIPT italic_b via PPA

For the PPA error (second pair of terms in (9)), the step size $\eta$ needs to be properly set up so that a single step of PPA, i.e., $x_{1}=(I+\eta A)^{-1}(x_{0}+\eta b)$ is close enough to $A^{-1}b=x^{\star}.$
To achieve that, observe from (8):

$$ $\displaystyle\|x_{t+1}-x^{\star}\|$ $\displaystyle\leqslant\|(I+\eta A)^{-t}\|\cdot\|x_{0}-x^{\star}\|\leqslant \frac{1}{(1+\eta\sigma_{\min})^{t}}\|x_{0}-x^{\star}\|,$ (14) $$

where $\sigma_{\min}$ is the smallest singular value of $A$.
We desire the RHS to be less than $\varepsilon_{2}$.
Denoting $\|x_{0}-x^{\star}\|:=d$ and using $\sigma_{\min}=1/\kappa$ (c.f., Definition 1),
we can compute the lower bound on the number of iterations $t$ as:

$$ $\displaystyle\frac{d}{(1+\eta/\kappa)^{t}}$ $\displaystyle\leqslant\varepsilon_{2}\implies\frac{\log(\frac{d}{\varepsilon_{ 2}})}{\log(1+\frac{\eta}{\kappa})}\leqslant t.$ (15) $$

Based on the above analysis, we can compute the number of iterations $t$ required to have $\varepsilon$-optimal solution of the quadratic problem in (6). Here, (15) is well defined in the sense that the lower bound on $t$ is positive, as long as $\eta>0$.
In other words, if the LHS of (15) is less than 1, that means PPA converges to $\varepsilon_{2}$-approximate solution in one step, with a proper step size.

Again, our goal is to achieve (9). Hence, we have to characterize how (14)
results in the proximity in corresponding normalized quantum states. We utilize Lemma 2 below.

###### Lemma 2 .

Let $x$ and $y$ be two vectors. Suppose $\|x-y\|\leqslant\epsilon$ for some small positive scalar $\epsilon$. Then, the distance between the normalized vectors satisfies the following:

$$ $\left\|\frac{x}{\|x\|}-\frac{y}{\|y\|}\right\|\leqslant\frac{\epsilon}{\sqrt{ \|x\|\cdot\|y\|}}.$ $$

Now, we characterize the error of the normalized quantum state of as an output of PPA.

###### Proposition 2 .

Running the PPA in (7) for a single iteration with $\eta=\kappa\left(\frac{d}{\varepsilon_{2}}-1\right)$, where $d:=\|x_{0}-A^{-1}b\|$,
results in the normalized quantum state satisfying:

$$ $\displaystyle\left\|\big{|}\big{(}\tfrac{I+\eta A}{\|I+\eta A\|}\big{)}^{-1}(x _{0}+\eta b)\big{\rangle}-\big{|}A^{-1}b\big{\rangle}\right\|\leqslant\frac{ \varepsilon_{2}}{\Psi},$ (16) $$

where $\Psi:=\sqrt{\|(I+\eta A)^{-1}(x_{0}+\eta b)\|\cdot\|A^{-1}b\|}$.

###### Lemma 2 .

###### Proposition 2 .

### 4.3 Overall Complexity and Improvement

Equipped with Propsitions 1 and 2, we arrive at the following theorem.

###### Theorem 3 (Main result) .

Consider solving the QLSP problem in Definition 1 with Algorithm 1, of which the approximation error $\varepsilon$ can be decomposed as (9), recalled below:

$$ $\bigg{\|}\underbrace{\big{|}\psi_{I+\eta A,x_{0}+\eta b}\big{\rangle}-{\color[ rgb]{.5,.5,.5}\big{|}\big{(}\tfrac{I+\eta A}{\|I+\eta A\|}\big{)}^{-1}(x_{0}+ \eta b)\big{\rangle}}}_{\texttt{QLSP_solver}\text{ error}~{}\leqslant~{} \varepsilon_{1}~{}(\text{c.f., Proposition}~{}\ref{prop:qlsp_error})}+ \underbrace{{\color[rgb]{.5,.5,.5}\big{|}\big{(}\tfrac{I+\eta A}{\|I+\eta A\|} \big{)}^{-1}(x_{0}+\eta b)\big{\rangle}}-|A^{-1}b\rangle}_{\text{PPA error}~{} \leqslant~{}\varepsilon_{2}/\Psi~{}(\text{c.f., Proposition}~{}\ref{prop:ppa- numiter})}\bigg{\|}\leqslant\varepsilon.$ $$

Suppose the existence of a QLSP_solver satisfying the assumptions of Proposition 1 such that (10) is satisfied with $\varepsilon_{1}=\varepsilon/c$, for $c>1$.
Further, suppose the assumptions of Proposition 2 hold, i.e., single-run PPA with $\eta=\kappa\left(\frac{d}{\varepsilon_{2}}-1\right)$ is implemented with accuracy $\varepsilon_{2}=\left(1-\frac{1}{c}\right)\varepsilon\cdot\Psi$. Then, the output of Algorithm 1 satisfies:

$$ $\displaystyle\bigg{\|}\big{|}\psi_{I+\eta A,x_{0}+\eta b}\big{\rangle}-\big{|} A^{-1}b\big{\rangle}\bigg{\|}\leqslant\varepsilon.$ $$

Moreover, the dependence on the condition number of QLSP_solver changes from $\kappa$ to $\frac{\kappa(1+\eta)}{\kappa+\eta}$.

We now further interpret the analysis from the previous subsection and compare it with other QLSP algorithms (e.g., CKS []). We first recall the CKS query complexity below.

###### Theorem 4 (CKS complexity, Theorem 5 in [ 9 ] ) .

The QLSP in Definition 1 can be solved to $\varepsilon$-accuracy by a quantum algorithm that makes
$\mathcal{O}\left(\kappa\cdot\emph{poly}\log\left(\frac{\kappa}{\varepsilon}
\right)\right)$ queries to the oracles $\mathcal{P}_{A}$ in Definition 3 and $\mathcal{P}_{B}$ in Definition 2.

It was an open question whether there exists a quantum algorithm that can match the lower bound: $\Omega\left(\kappa\cdot\log\left(\frac{1}{\varepsilon}\right)\right)$ []. A recent quantum algorithm based on the complicated discrete adiabatic theorem [] was shown to match this lower bound. We recall their result below.

###### Theorem 5 (Optimal complexity, Theorem 19 in [ 11 ] ) .

The QLSP in Definition 1 can be solved to $\varepsilon$-accuracy by a quantum algorithm that makes $\mathcal{O}\left(\kappa\cdot\log\left(\frac{1}{\varepsilon}\right)\right)$ queries to the oracles $\mathcal{U}_{A}$ in Definition 4 and $\mathcal{P}_{B}$ in Definition 2.

A natural direction to utilize Algorithm 1 is to use the best QLSP_solver [], which has the query complexity $\mathcal{O}\left(\kappa\cdot\log\left(\frac{1}{\varepsilon}\right)\right)$ from Theorem 5.
We summarize this in the next theorem.

###### Theorem 6 (Improving the optimal complexity) .

Consider running Algorithm 1 with [] as the candidate for QLSP_solver, which has the original complexity of $\mathcal{O}\left(\kappa\cdot\log\left(\frac{1}{\varepsilon}\right)\right)$ (c.f., Theorem 5).
The modified complexity of Algorithm 1 via Theorem 3 can be written and decomposed to:

$$ $\displaystyle\hat{\kappa}\cdot\log\left(\frac{c}{\varepsilon}\right)= \underbrace{\frac{\kappa(1+\eta)}{\kappa+\eta}\cdot\log\left(\frac{1}{ \varepsilon}\right)}_{\text{Improvement}}+\underbrace{\frac{\kappa(1+\eta)}{ \kappa+\eta}\cdot\log(c)}_{\text{Overhead}},$ (17) $$

where the “improvement” comes from $\hat{\kappa}\leqslant\kappa$, and the “overhead” is due to the weight of $\varepsilon_{1}=\varepsilon/c$ (and subsequently $\varepsilon_{2}=\left(1-\frac{1}{c}\right)\varepsilon\cdot\Psi$) in Theorem 3.
Further, with $\eta=\kappa\left(\frac{d}{\varepsilon_{2}}-1\right)$,
it follows

$$ $\displaystyle\hat{\kappa}=\frac{\kappa(1+\eta)}{\kappa+\eta}=\kappa-\frac{(c-1 )(\kappa-1)\Psi\varepsilon}{c\cdot d}\leqslant\kappa.$ (18) $$

We illustrate Theorem 6 in Figure 2 (left); thanks to the flexibility of Algorithm 1 and Theorem 3, similar analysis can done with CKS [] as the baseline, as illustrated in Figure 2 (right).

Intuitively, based on the decomposition in (17), we can see that the constant $c$ –which controls the weight of $\varepsilon_{1}$ and $\varepsilon_{2}$ in Theorem 3– enters a logarithmic term in the “overhead.” On the contrary, the (additive) improvement in $\kappa$ is proportional to the term $\frac{(c-1)}{c}$, as can be seen in (18).

###### Theorem 3 (Main result) .

###### Theorem 4 (CKS complexity, Theorem 5 in [ 9 ] ) .

###### Theorem 5 (Optimal complexity, Theorem 19 in [ 11 ] ) .

###### Theorem 6 (Improving the optimal complexity) .

## 5 Conclusion and Discussion

In this work, we proposed a novel quantum algorithm for solving the quantum linear systems problem (QLSP), based on the proximal poin algorithm (PPA). Specifically, we showed that implementing a single-step PPA is possible by utilizing existing QLSP solvers. We designed a meta-algorithm where any QLSP solver can be utilized as a subroutine to improve the dependence on the condition number. Even the current best quantum algorithm [] can be significantly accelerated via Algorithm 1, especially when the problem is ill-conditioned.

Limitations. A main limitation of this work is that only constant-level improvement is attained; yet, due to the existing lower bound [, ], asymptotic improvement is not possible.
Another limitation is that only a single-step PPA is implemented in Algorithm 1 at the moment. This necessitates $\eta$ to be fairly large, as can be seen in (7) or (15). Then, in conjunction with Remark 3 and (18), the benefit from the modified condition number $\hat{\kappa}=\frac{\kappa(1+\eta)}{\kappa+\eta}$ diminishes. To address this, two interesting future directions can be considered.

Implementing multi-step PPA.
A natural idea is to implement multi-step PPA. Based on (7), two-step PPA can be written as :

$$ $\displaystyle x_{t+1}$ $\displaystyle=(I+\eta A)^{-2}(x_{t-1}+\eta b)+(I+\eta A)^{-1}\eta b$ $\displaystyle=\big{(}(I+\eta A)^{-2}+(I+\eta A)^{-1}\big{)}\eta b,$ $$

where in the second step we set $x_{t-1}$ with zero vector (i.e., initialization). As can be seen, this requires implementing different powers (and their addition) of the modified matrix $I+\eta A$, which is possible via [, Lemmas 52 and 53], and may provide overall improvement over Algorithm 1.

Warm starting. The modified condition number $\hat{\kappa}$ of $(I+\eta A)/\|I+\eta A\|$ relies on the initial point of PPA, $x_{0}$. In particular, $\hat{\kappa}$ can be expressed as in (18) from Theorem 6, where $d:=\|x_{0}-x^{\star}\|$. Therefore, a better initialization $x_{0}$ can result in a bigger improvement in the overall complexity.

To achieve that, for instance, suppose that we have some knowledge about the solution $x^{\star}$, such that it is not far from a specific point or a set of vectors. Then we can use that set of vectors as our starting point. Alternatively, we can also run other QLSP solvers or quantum-inspired linear system solvers (e.g., [, ]) with constant accuracy, and use the solution as the initialization.

## Appendix

## Appendix A Missing Proofs

### A.1 Proof of Lemma 1

###### Proof.

By the assumption on QLSP in Definition 1, the singular values of $A$ is contained in the interval $\big{[}\frac{1}{\kappa},1\big{]}$. Thus, for the normalized modified matrix, i.e., $\frac{I+\eta A}{\|I+\eta A\|}$, the singular values are contained in the interval $\big{[}\frac{\kappa+\eta}{\kappa(1+\eta)},1\big{]}$, leading to the modified condition number $\hat{\kappa}=\frac{\kappa(1+\eta)}{\kappa+\eta}$.
∎

###### Proof.

### A.2 Proof of Lemma 2

###### Proof.

We need to bound:

$$ $\displaystyle\left\|\hat{x}-\hat{y}\right\|=\left\|\frac{x}{\|x\|}-\frac{y}{\| y\|}\right\|.$ $$

Consider the inner product form:

$$ $\displaystyle\left\|\frac{x}{\|x\|}-\frac{y}{\|y\|}\right\|^{2}=2-2\left \langle\frac{x}{\|x\|},\frac{y}{\|y\|}\right\rangle=2-2\frac{\langle x,y \rangle}{\|x\|\|y\|}.$ $$

The inner product can be bounded using $\|x-y\|\leqslant\epsilon$:

$$ $\displaystyle\langle x,y\rangle$ $\displaystyle=\frac{1}{2}\left(\|x\|^{2}+\|y\|^{2}-\|x-y\|^{2}\right)$ $\displaystyle\geqslant\frac{1}{2}\left(\|x\|^{2}+\|y\|^{2}-\epsilon^{2}\right).$ $$

Now, substituting this into the normalized inner product:

$$ $\displaystyle\frac{\langle x,y\rangle}{\|x\|\|y\|}\geqslant\frac{\frac{1}{2} \left(\|x\|^{2}+\|y\|^{2}-\epsilon^{2}\right)}{\|x\|\|y\|}=\frac{1}{2}\left( \frac{\|x\|}{\|y\|}+\frac{\|y\|}{\|x\|}-\frac{\epsilon^{2}}{\|x\|\|y\|}\right).$ $$

Using $\frac{\|x\|}{\|y\|}+\frac{\|y\|}{\|x\|}\geqslant 2$ from AM-GM inequality, we get:

$$ $\displaystyle\frac{\langle x,y\rangle}{\|x\|\|y\|}\geqslant 1-\frac{\epsilon^{ 2}}{2\|x\|\|y\|}.$ $$

Substituting the above back into the distance expression, we get:

$$ $\displaystyle\left\|\frac{x}{\|x\|}-\frac{y}{\|y\|}\right\|^{2}\leqslant 2-2 \left(1-\frac{\epsilon^{2}}{2\|x\|\|y\|}\right)=\frac{\epsilon^{2}}{\|x\|\|y\|},$ $$

which implies the desired result:

$$ $\displaystyle\left\|\frac{x}{\|x\|}-\frac{y}{\|y\|}\right\|\leqslant\frac{ \epsilon}{\sqrt{\|x\|\|y\|}}.$ $$

∎

###### Proof.

### A.3 Proof of Proposition 1

###### Proof.

Since the input matrix $\frac{I+\eta A}{\|I+\eta A\|}$ is normalized, and due to the reasoning in Remark 1, we can have sparse-acess or block-encoding of $\frac{I+\eta A}{\|I+\eta A\|}$. Then, the result of Proposition 1 simply follows from the result of each related work in Table 1.
∎

###### Proof.

### A.4 Proof of Proposition 2

###### Proof.

As explained in Section 4.2 of the main text, we can compute the number of iterations for PPA using (15), recalled below, which is based on (14).

$$ $\displaystyle\frac{d}{(1+\eta/\kappa)^{t}}$ $\displaystyle\leqslant\varepsilon_{2}\implies\frac{\log(\frac{d}{\varepsilon_{ 2}})}{\log(1+\frac{\eta}{\kappa})}\leqslant t.$ $$

In this work, since we are implementing a single-step PPA, we want $t=1$ from (15). To achieve that, we can have:

$$ $\displaystyle\log\left(\frac{d}{\varepsilon_{2}}\right)$ $\displaystyle=\log\left(1+\frac{\eta}{\kappa}\right)\Rightarrow$ $\displaystyle\eta$ $\displaystyle=\kappa\left(\frac{d}{\varepsilon_{2}}-1\right).$ $$

∎

###### Proof.

### A.5 Proof of Theorem 3

###### Proof.

Recall the decomposition:

$$ $\bigg{\|}\underbrace{\big{|}\psi_{I+\eta A,x_{0}+\eta b}\big{\rangle}-{\color[ rgb]{.5,.5,.5}\big{|}\big{(}\tfrac{I+\eta A}{\|I+\eta A\|}\big{)}^{-1}(x_{0}+ \eta b)\big{\rangle}}}_{\texttt{QLSP_solver}\text{ error}~{}\leqslant~{} \varepsilon_{1}}+\underbrace{{\color[rgb]{.5,.5,.5}\big{|}\big{(}\tfrac{I+\eta A }{\|I+\eta A\|}\big{)}^{-1}(x_{0}+\eta b)\big{\rangle}}-|A^{-1}b\rangle}_{ \text{PPA error}~{}\leqslant~{}\varepsilon_{2}}\bigg{\|}\leqslant\varepsilon.$ $$

The QLSP_solver error can be provided by Proposition 1, with the accuracy of $\varepsilon_{1}=\varepsilon/c$, for $c>1$. Similarly, $\eta$ is chosen based on Proposition 2, with $\varepsilon_{2}=\left(1-\frac{1}{c}\right)\varepsilon\cdot\Psi$. Then, by adding the result from each proposition, we have

$$ $\displaystyle\varepsilon_{1}+\frac{\varepsilon_{2}}{\Psi}=\frac{\varepsilon}{c }+\left(1-\frac{1}{c}\right)\varepsilon=\varepsilon.$ $$

Note that since QLSP_solver is only called once in Algorithm 1, the final accuracy $\varepsilon$ is the same for the output of Algorithm 1 and the subroutine QLSP_solver being called.
∎

###### Proof.

### A.6 Proof of Theorem 6

(17) simply follows from plugging in the modified condition number $\hat{\kappa}$, along with $\varepsilon_{1}=\varepsilon/c$. That is,

$$ $\displaystyle\mathcal{O}\left(\hat{\kappa}\cdot\log\left(\frac{1}{\varepsilon_ {1}}\right)\right)$ $\displaystyle=\mathcal{O}\left(\frac{\kappa(1+\eta)}{\kappa+\eta}\cdot\log \left(\frac{c}{\varepsilon}\right)\right)$ $\displaystyle=\mathcal{O}\left(\frac{\kappa(1+\eta)}{\kappa+\eta}\cdot\log \left(\frac{1}{\varepsilon}\right)+\frac{\kappa(1+\eta)}{\kappa+\eta}\cdot\log (c)\right).$ $$

Note that similar analysis can be done for CKS [], starting from $\mathcal{O}\left(\hat{\kappa}\cdot\log\left(\frac{\hat{\kappa}}{\varepsilon_{1
}}\right)\right)$.

For (18), it follows from the below steps:

$$ $\displaystyle\frac{\kappa(1+\eta)}{\kappa+\eta}$ $\displaystyle=\frac{1+\eta}{1+\eta/\kappa}$ $\displaystyle=\frac{1+\frac{\kappa dc}{(c-1)\varepsilon\Psi}-\kappa}{\frac{ \kappa dc}{(c-1)\varepsilon\Psi}}$ $\displaystyle=\kappa-\frac{\kappa-1}{\frac{dc}{(c-1)\varepsilon\Psi}}$ $\displaystyle=\kappa-\frac{(c-1)\varepsilon\Psi(\kappa-1)}{dc}.$ $$

## Peer Reviews

confidence: 4
contribution: 2
initial_rating: 5
presentation: 3
questions: 1. Can the authors provide more discussions on these additionally introduced parameters?
2. Can the authors give a more detailed discussion on how the tradeoff between the runtime and the approximation error is achieved from the bound in Theorem 6?
soundness: 4
strengths: This paper introduces a novel framework that enhances the dependence on the condition number $\kappa$ in quantum algorithms, while incorporating additional problem-dependent parameters. In the worst-case scenario, it achieves a significant constant-factor improvement over the existing state-of-the-art algorithm. The framework also includes a tunable parameter $\eta$, allowing users to adjust the balance between runtime and approximation error.
summary: This paper investigates the quantum linear system problem (QLSP), which aims to produce a quantum state encoding the solution vector $x$ for a given matrix $A$ and vector $b$, such that $Ax = b$, assuming quantum query access to $A$ and $b$. The current best-known algorithm for QLSP achieves a query complexity of $O(\kappa \log \epsilon^{-1})$, where $\kappa$ is the condition number of $A$ and $\epsilon$ is the target error. While this result offers an exponential speedup in terms of $N$, the dimension of the system, the algorithm’s query complexity scales linearly with $\kappa$. Prior work has established that this linear dependence on $\kappa$ is unavoidable in the worst case, reducing the quantum advantage for poorly conditioned matrices.

This paper partially addresses this limitation by introducing a meta-algorithm for QLSP based on the proximal point algorithm (PPA)—a classical iterative optimization technique. This framework can be applied to any existing quantum linear system algorithm (QLSA) to modulate the tradeoff between solution precision and condition number. When applied to the current state-of-the-art QLSA, this meta-algorithm yields a constant-level improvement across a range of precision requirements, thereby extending the practical applicability of quantum linear system solvers.
weaknesses: 1. The meta algorithm itself is relatively simple, and the techniques used to analyze the problem is not extremely complicated.
2. The algorithm introduces additional problem-specific parameters, such as, $\Psi$ and $d\coloneqq ||x_0-x^*||$. Moreover, the paper did not provide a very thorough discussion on these parameters.

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 3
questions: Besides the questions that are raised in the "Weaknesses" part, I have the following questions:
- Is there a practical way to choose the stepsize $\eta$ in the algorithm? What if the obtained solution is still far from the exact solution to the linear system?
- Is it possible to use the PPA solution as a "warm start" in a quantum linear system solver, which might be helpful to improve the overall performance?
- Can the authors further elaborate on how the comparison is made in Figure 1? Is it fair to include a $c$ parameter in Algorithm 1?
soundness: 3
strengths: - This paper exploits the proximal point algorithm to reformulate the original linear system problem as an approximate optimization problem, where the new problem is parametrized by the "step size" $\eta$. This new parameter provides a continuous interpolation from the original problem (for $\eta = +\infty$) to a pre-conditioned problem (for small $\eta$). This is an interesting point of view and also the first proposal to combine the proximal point algorithm with a quantum linear system solver (to my best knowledge).
- Numerical results show that this approach reduces the total query complexity over the STOA quantum linear system solver.
summary: This paper proposes a novel meta-algorithm for solving the quantum linear system problem (QLSP) based on the proximal point algorithm (PPA). The performance of quantum linear system solvers heavily depends on the condition number of the linear system. Due to a query lower bound result, the linear dependence on condition number can not be further improved (in the asymptotic scaling sense). This paper incorporates the proximal point algorithm as a pre-conditioner of a QLSP solver. The new proximal-point QLSS can leverage the trade-offs between the approximation error (in the output solution) and the condition number of the linear system. It is proven that a finite stepsize mitigates the condition number, at the cost of making the resulting solution inexact. Numerical results show this new approach can lead to a generic (constant) speedup in solving linear systems over existing STOA.
weaknesses: - My main concern is that the proximal point algorithm proposed in this paper can have a **single** iteration. This feature makes this algorithm less useful in practice. The main difficulty is that the state preparation oracle (see Definition 2) is hard (or maybe impossible) to construct for subsequent steps. 
- While it is discussed that a multi-step PPA can be realized by implementing different powers of the modified matrix, it is not clear why this would lead to asymptotic speedup because inverting $(I + \eta A)^n$ for $n \ge 2$ is likely to incur a super-linear overhead in the condition number. I would conjecture that the naive multi-step PPA will lead to a polynomial slowdown compared to the quantum STOA. 
- I do not understand how this PPA approach is compared to an "exact" quantum linear system solver, because this PPA approach can only perform a single iteration step so the solution is not exact. Can the authors elaborate on how a fair comparison is achieved? Is the error budget for both methods pre-fixed?

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 3
questions: See the weakness above.
soundness: 2
strengths: The proposed approach is easy to plug in any quantum linear systems solver. Improving the conditional number is one of the most important tasks in QLSA.
summary: This paper is a good attempt to make QLSA more practical although there is no theoretical improvement in the bigO complexity. However, the authors did not discuss how large the “constant” improvement could be if someone wants to “read out” the quantum solution. In fact, an issue would appear in that regime and limit the “constant” improvement.
weaknesses: As demonstrated in Figure 1, kappa^hat is less than kappa/2. According to lemma 1, parameter eta would be less than kappa-2 (or simply kappa). According to the eta choice in theorem 3, if we simply use eta less than kappa, then we have epsilon_2 larger than d. Recall that epsilon_2 is the accuracy for x_{t+1}-x^* as in equation 14, which is the accuracy people care about in the classical setting. This means, if someone wants to eventually read out the quantum solution, ignoring the error from the reading-out process, the accuracy of the classical solution will be very low because the accuracy is at most d and d is simply the initial accuracy. If we don’t want to read out the solutions, the applicability will be significantly limited. 

A side comment: the notations of a quantum state are not consistent, i.e., some of them use the braket notation while some do not.

---

confidence: 3
contribution: 3
initial_rating: 5
presentation: 2
questions: - In Theorem 3, the parameter $\eta$ is set to $\kappa (d/\varepsilon_2 - 1)$, but $\kappa$ may be unknown. Could the authors explain what to to if $\kappa$ is not known?

- In Theorem 6, it seems that difference between the modified condition number $\hat{\kappa}$ and $\kappa$ has a linear dependence on $\Psi$, which relies on the choice of $x_0$ and $\eta$. Could the authors explain more about how to choose $x_0$ and $\eta$?

- Page 9, Line 482: proximal poin algorithm —> proximal point algorithm.

- Page 14, Line 733: the codes in algorithm 2 for Hamilonian simulation could be improved for readability.
soundness: 3
strengths: The authors propose a new algorithm (PPA for QLSP) to alleviate the linear dependence on condition number of the QLSP solvers, yielding a constant acceleration of previous QLSP solvers.
summary: Quantum linear system problem (QLSP) is of great importance in quantum algorithms, which focuses on solving a system of linear equations, i.e., find a state $\ket{x} = x/\|x\|$ where $x$ is the solution to $Ax=b$. QLSP problem is fundamental as it is a key step in many quantum algorithms, such as quantum recommendation systems and solving differential equations. However, a major limitation of the QLSP solver is that the complexity has a linear dependence of the condition number $\kappa$ of the matrix $A$. Whether one can alleviate this issue is also of general interest.

In this paper, the authors propose a new algorithm based on proximal point algorithm (PPA) to reduce the query complexity in solving QLSP in a constant degree. To achieve this acceleration, the authors uses the technique of shifting the matrix $A$ of the problem to $I+\eta A$, leading to the change of condition number of the problem. In addition, the authors also draw some graphs to demonstrate the acceleration.
weaknesses: First, a main technical tool is the use of PPA algorithm for shifting, which might lack novelity. 
Second, the proofs of the main theorems seems straigthforward and incremental. 
Also, it looks like more numerical experiments could be conducted to demonstrate the actual performance of their proposed algorithm.
Furthermore, I am not sure whether the topic of this paper fits for the scope of ``learning represenations''.

Meta-review: This paper proposed a new framework for the quantum linear system problem via the proximal point problem. Specifically, this new framework can be seen as a meta-algorithm that adapts step size, and hence allows the user to control the trade-off between the runtime and the approximation error. Numerical experiments demonstrate the improvement of the proposed framework over previous algorithms.

During the review period, the reviewers acknowledged the contribution on having tunable parameters for the quantum linear system problem, and also benign numerical results. However, there are general concerns about the technical novelty over previous quantum computing results. Another main issue is that this paper focuses more on a technical problem in quantum computing - quantum linear system problem, but didn't introduce the impact to learning theory and potential applications. The scores are mostly on the reject side.

The final decision is hence rejection. For future versions, we encourage the authors to merge all points raised during the rebuttal to future versions of the paper. If the authors target for machine learning venues in the future, extension of the studied results to specific machine learning problems (that use solving linear systems) both in theory and experiments will be very appreciated.

Decision: Reject