Revisiting Quantum Algorithms for Linear Regressions: Quadratic Speedups without Data-Dependent Parameters

We express our deepest gratitude to the reviewer for taking the time and effort to review our work. We thank you for pointing out the strengths of our work that we have attained a quadratic speed up in the parameters compared with the classical counterparts. Below, we want to address your concerns about our work.

Regarding our technical contribution, while we indeed build upon quantum leverage score sampling [AG23] and classical leverage score sampling [CW13], our contribution goes significantly beyond simply replacing classical sampling with quantum sampling. We would like to highlight that our work discovers an interesting application of the recently developed quantum spectral approximation procedure. More importantly, we find that using this procedure to solve the linear regression problem can achieve state-of-the-art complexity in the tall, dense regime, and can overcome the condition number issue in almost all previous quantum linear regression solvers. This removal of the matrix condition number $\kappa (A)$ is very crucial as it was a major limitation of previous quantum algorithms. This is a significant technical achievement that requires careful analysis of the interaction between quantum sampling and regression problems. Prior quantum algorithms could only guarantee speedups for well-conditioned matrices. Our algorithm provides the first unconditional quantum speedup for these regression problems.

Compared with [Sha23], we note that [Sha23] still has runtime dependencies on matrix-specific parameters. Their algorithm relies on the "cost of encoding a matrix into a quantum computer". Only if this cost is small, then their quantum algorithm achieves a quadratic speedup over classical algorithms. However, we achieve a quadratic speedup over classical algorithms without such dependencies. We provide comprehensive analysis for multiple regression and ridge regression variants, which are not addressed in [Sha23]. Our techniques yield better runtime bounds even for basic linear regression.

Regarding the inverse polynomial dependence on $\epsilon$, it is quite common in classical sketching algorithms. Intuitively, to construct an $\epsilon$-subspace embedding (or even just applying the JL lemma), the number of rows of the sketched matrix must be at least $1/\epsilon^2$. Therefore, if we want to keep a high-accuracy spectral approximation, the complexity will depend on $\mathrm{poly}(1/\epsilon)$. However, for the linear regression problem, there exists some classical algorithms that can achieve $\log(1/\epsilon)$. For example, [CW13] show that leverage score sketching can be combined with some iterative methods. More specifically, they use an $O(1)$-accuracy sketching matrix to construct a preconditioner. Then, they prove that $O(\log(1/\epsilon))$ iterations of the Conjugate Gradient method suffice to produce an $\epsilon$-error solution. The total time complexity is $\tilde{O}(\mathrm{nnz}(A)+d^3)$. We note that our quantum algorithm cannot be directly generalized to this setting. It can efficiently produce the preconditioner. However, the Conjugate Gradient method is hard to be quantumly sped up. We note that all the previous quantum linear regression algorithms have a $\mathrm{poly}(1/\epsilon)$ factor if a classical solution is required. Specifically, they are based on the quantum linear system solver, which outputs a quantum state that encodes the normalized solution. To obtain the classical solution, we need to perform a full state tomography and also need to estimate the normalization factor. These two steps must incur a $\mathrm{poly}(1/\epsilon)$ factor. We think achieving $\log(1/\epsilon)$ for the quantum linear regression algorithm is a very interesting open question.

We sincerely thank you again for your insightful comments, and we have responded to all the points you have made. We hope that our response may address all of your concerns about our paper. Also, we have uploaded the updated version of our paper to OpenReview. We have marked our changes in red color.

We express our deepest gratitude to the reviewer for taking the time and effort to review our work. We thank you for pointing out that our work studies an important question. It is very encouraging to see that our work has very clear improvement over the previous ones and our writing is generally good.

Regarding the novelty, we would like to highlight that our work discovers an interesting application of the recently developed quantum spectral approximation procedure. More importantly, we find that using this procedure to solve the linear regression problem can achieve state-of-the-art complexity in the tall, dense regime, and can overcome the condition number issue in almost all previous quantum linear regression solvers. Moreover, our quantum algorithm’s time complexity matches the quantum lower bound in terms of $n$. Since linear regression is one of the most fundamental problems in optimization and machine learning, our work sets a new benchmark for it. We provide a tool to solve this problem with currently the best efficiency and fully classical outputs, which will be very helpful to use as a black box to solve other problems in the future.

Question: Theorems 1.4 and 1.5 define that $r$ is the row-sparsity of the matrix but the running time of the algorithms in them has no dependence on $r$. Consider removing $r$ from them.

Answer: Thank you for pointing this out. The row sparsity $r$ does play a role in the running time. For example, the total running time of Theorem 1.5 should be $\widetilde{O}(r \sqrt{nd} / \epsilon + d^{\omega} / \epsilon + N d^{\omega -1} / \epsilon )$ (combining Lemma 3.9 and Lemma 4.3). Since the row sparsity $r$ must be smaller than or equal to the number of columns $d$, in the running time, we replace $r$ by $d$ to make it more clear. Therefore, instead of removing $r$, we added the condition $r \leq d$ to the theorem statement to make it more clear.

Question: "Classical linear algebra" section in the related work mentions a lot of references. It would be sufficient to give a smaller number of applications for classical linear algebra, as its significance is well understood.

Answer: We completely agree with this and have moved the related work of the iterate-and-sketch to the appendix. In the main text, we only keep the sketch-and-solve which is directly related to our work.

We sincerely thank you again for your insightful comments, and we have responded to all the points you have made. We hope that our response may address all of your concerns about our paper. Also, we have uploaded the updated version of our paper to OpenReview. We have marked our changes in red color.

We express our deepest gratitude to the reviewer for taking the time and effort to review our work. We thank you for pointing out that our work is well-organized and addresses a significant open problem in quantum linear systems research. Below, we want to address your concerns.

While individual lemmas come from prior work, their combination to achieve quantum speedups without matrix-dependent parameters required significant technical innovation. The key challenge was developing a quantum-compatible sampling framework that preserves both subspace embedding and approximate matrix product properties while being efficiently implementable on quantum hardware. This required careful analysis to ensure the quantum estimation of leverage scores (Lemma A.1) could interface correctly with the classical sampling guarantees (Lemmas 4.1 and 4.2).

Our framework provides the first quantum speedups for regression problems that work for any input matrix, not just well-conditioned ones. This required careful technical work to remove condition number dependencies while maintaining quantum advantages. On the one hand, it discovers an interesting application of the recently developed quantum spectral approximation algorithm. On the other hand, it sets a new benchmark for quantum optimization and machine learning algorithms since linear regression is a fundamental problem, and our algorithm overcomes the condition number issue in almost all previous quantum linear regression algorithms. Moreover, it provides a useful technical tool that can be easily applied as a black box for other applications.

Regarding the minor comments, we have fixed the grammatical issue in Lemma A.1. Also, we have uploaded the updated version of our paper to OpenReview. We have marked our changes in red color.

Regarding Lemma 4.2 (Lemma C.31 in Song et al. (2019c)), this is a correctness guarantee rather than an algorithmic result, so it doesn't have an associated time complexity.

We sincerely thank you again for your insightful comments, and we have responded to all the points you have made. We hope that our response may address all of your concerns about our paper.