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

arXiv:1906.01194 · Physics Letters A

Quantum algorithm for total least squares data fitting

Hefeng Wang, Hua Xiang

Published Apr 24, 2019• 16 citations
arXivHTMLPDF
DOI
10.1016/j.physleta.2019.04.037

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

Fast Quantum Algorithms for Least Squares Regression and Statistic Leverage Scores

Yang Liu, Shengyu Zhang

Lecture notes in computer science•Jan 1, 2015•2 citations

Quantum Fuzzy Least Squares Algorithm for Uncertain Environment

Shipeng Yu, Yan Zuo Chang, Shibin Zhang +1 more

Communications in computer and information science•Jan 1, 2022•0 citations

An improved quantum algorithm for data fitting

Jiancheng Lei, Tingting Song, Ling Liu +1 more

Physica A Statistical Mechanics and its Applications•Jan 30, 2023•5 citations

Quantum algorithm for linear regression

Guoming Wang

We present a quantum algorithm for fitting a linear regression model to a given data set using the least-squares approach. Differently from previous algorithms which yield a quantum state encoding the optimal parameters, our algorithm outputs these numbers in the classical form. So by running it once, one completely determines the fitted model and then can use it to make predictions on new data at little cost. Moreover, our algorithm works in the standard oracle model, and can handle data sets with nonsparse design matrices. It runs in time $\text{poly}({log}_{2}(N),d,\ensuremath{\kappa},1/\ensuremath{\epsilon})$, where $N$ is the size of the data set, $d$ is the number of adjustable parameters, $\ensuremath{\kappa}$ is the condition number of the design matrix, and $\ensuremath{\epsilon}$ is the desired precision in the output. We also show that the polynomial dependence on $d$ and $\ensuremath{\kappa}$ is necessary. Thus, our algorithm cannot be significantly improved. Furthermore, we also give a quantum algorithm that estimates the quality of the least-squares fit (without computing its parameters explicitly). This algorithm runs faster than the one for finding this fit, and can be used to check whether the given data set qualifies for linear regression in the first place.

arXiv:1402.0660•Physical Review A•Jul 31, 2017•159 citations

Quantum regularized least squares solver with parameter estimate

Changpeng Shao, Hua Xiang

Quantum Information Processing•Feb 14, 2020•8 citations
We present a quantum algorithm for fitting a linear regression model to a given data set using the least-squares approach. Differently from previous algorithms which yield a quantum state encoding the optimal parameters, our algorithm outputs these numbers in the classical form. So by running it once, one completely determines the fitted model and then can use it to make predictions on new data at little cost. Moreover, our algorithm works in the standard oracle model, and can handle data sets with nonsparse design matrices. It runs in time $\text{poly}({log}_{2}(N),d,\ensuremath{\kappa},1/\ensuremath{\epsilon})$, where NNN is the size of the data set, ddd is the number of adjustable parameters, $\ensuremath{\kappa}$ is the condition number of the design matrix, and $\ensuremath{\epsilon}$ is the desired precision in the output. We also show that the polynomial dependence on ddd and $\ensuremath{\kappa}$ is necessary. Thus, our algorithm cannot be significantly improved. Furthermore, we also give a quantum algorithm that estimates the quality of the least-squares fit (without computing its parameters explicitly). This algorithm runs faster than the one for finding this fit, and can be used to check whether the given data set qualifies for linear regression in the first place.