Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Lecture notes in computer science

Fast Quantum Algorithms for Least Squares Regression and Statistic Leverage Scores

Yang Liu, Shengyu Zhang

Published Jan 1, 2015• 2 citations
Publisher
DOI
10.1007/978-3-319-19647-3_20

Related papers

Fast quantum algorithms for least squares regression and statistic leverage scores

Yang Liu, Shengyu Zhang

Theoretical Computer Science•Jun 11, 2016•48 citations

Quantum speedup of leverage score sampling and its application

Changpeng Shao

Leverage score sampling is crucial to the design of randomized algorithms for large-scale matrix problems, while the computation of leverage scores is a bottleneck of many applications. In this paper, we propose a quantum algorithm to accelerate this useful method. The speedup is at least quadratic and could be exponential for well-conditioned matrices. We also prove some quantum lower bounds, which suggest that our quantum algorithm is close to optimal. As an application, we propose a new quantum algorithm for rigid regression problems with vector solution outputs. It achieves polynomial speedups over the best classical algorithm known. In this process, we give an improved randomized algorithm for rigid regression.

arXiv:2301.06107•Jan 15, 2023•5 citations

Quantum algorithm for total least squares data fitting

Hefeng Wang, Hua Xiang

arXiv:1906.01194•Physics Letters A•Apr 24, 2019•16 citations

Quantum regularized least squares solver with parameter estimate

Changpeng Shao, Hua Xiang

Quantum Information Processing•Feb 14, 2020•8 citations

Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra

Nadiia Chepurko, Kenneth L. Clarkson, Lior Horesh C +2 more

We create classical (non-quantum) dynamic data structures supporting queries for recommender systems and least-squares regression that are comparable to their quantum analogues. De-quantizing such algorithms has received a flurry of attention in recent years; we obtain sharper bounds for these problems. More significantly, we achieve these improvements by arguing that the previous quantum-inspired algorithms for these problems are doing leverage or ridge-leverage score sampling in disguise; these are powerful and standard techniques in randomized numerical linear algebra. With this recognition, we are able to employ the large body of work in numerical linear algebra to obtain algorithms for these problems that are simpler or faster (or both) than existing approaches. Our experiments demonstrate that the proposed data structures also work well on real-world datasets.

arXiv:2011.04125•Nov 9, 2020•19 citations

Quantum Algorithms for Solving Linear Regression Equation

Kai Li, Hong‐Yi Dai, Jing Feng +4 more

Abstract Linear regression is one of the most important and common analytical methods in mathematical statistics. The letter studies a general model of linear regression problem based on least squares method, and investigates the impact of quantum algorithms on the time complexity of solving linear regression problem when quantum algorithms can be implemented on quantum computers. With the help of the general model of linear regression problem in terms of least squares method, we propose a novel simplified quantum scheme for solving linear regression equation based on the sparsity-independent quantum singular value estimation algorithm. For a linear regression equation with dimension n, our scheme can reduce the time complexity from O(Nn 2) to O ( N log N ) when both the condition number κ of related matrices and the reciprocal of precision ∈ are small in size O(play logN), where m is the dimension of the input u and N is the number of samples.

Journal of Physics Conference Series•Jan 1, 2021•6 citations
Leverage score sampling is crucial to the design of randomized algorithms for large-scale matrix problems, while the computation of leverage scores is a bottleneck of many applications. In this paper, we propose a quantum algorithm to accelerate this useful method. The speedup is at least quadratic and could be exponential for well-conditioned matrices. We also prove some quantum lower bounds, which suggest that our quantum algorithm is close to optimal. As an application, we propose a new quantum algorithm for rigid regression problems with vector solution outputs. It achieves polynomial speedups over the best classical algorithm known. In this process, we give an improved randomized algorithm for rigid regression.
We create classical (non-quantum) dynamic data structures supporting queries for recommender systems and least-squares regression that are comparable to their quantum analogues. De-quantizing such algorithms has received a flurry of attention in recent years; we obtain sharper bounds for these problems. More significantly, we achieve these improvements by arguing that the previous quantum-inspired algorithms for these problems are doing leverage or ridge-leverage score sampling in disguise; these are powerful and standard techniques in randomized numerical linear algebra. With this recognition, we are able to employ the large body of work in numerical linear algebra to obtain algorithms for these problems that are simpler or faster (or both) than existing approaches. Our experiments demonstrate that the proposed data structures also work well on real-world datasets.
Abstract Linear regression is one of the most important and common analytical methods in mathematical statistics. The letter studies a general model of linear regression problem based on least squares method, and investigates the impact of quantum algorithms on the time complexity of solving linear regression problem when quantum algorithms can be implemented on quantum computers. With the help of the general model of linear regression problem in terms of least squares method, we propose a novel simplified quantum scheme for solving linear regression equation based on the sparsity-independent quantum singular value estimation algorithm. For a linear regression equation with dimension n, our scheme can reduce the time complexity from O(Nn 2) to O ( N log N ) when both the condition number κ of related matrices and the reciprocal of precision ∈ are small in size O(play logN), where m is the dimension of the input u and N is the number of samples.