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:2105.13511 · Physical Review A

Linear regression by quantum amplitude estimation and its extension to convex optimization

Kazuya Kaneko, Koichi Miyamoto, Naoyuki Takeda, Kazuyoshi Yoshino

Published Aug 25, 2021• 7 citations
arXivHTMLPDF

Abstract

Linear regression is a basic and widely used methodology in data analysis. It is known that some quantum algorithms efficiently perform least-squares linear regression of an exponentially large dataset. However, if we obtain values of the regression coefficients as classical data, the complexity of the existing quantum algorithms can be larger than the classical method. This is because it depends strongly on the tolerance error $\ensuremath{\epsilon}$: the best one among the existing proposals is $O({\ensuremath{\epsilon}}^{\ensuremath{-}2})$. In this paper, we propose a quantum algorithm for linear regression, which has a complexity of $O({\ensuremath{\epsilon}}^{\ensuremath{-}1})$ and keeps a logarithmic dependence on the number of data points ${N}_{D}$. In this method, we overcome bottleneck parts in the calculation, which take the form of the sum over data points and therefore have a complexity proportional to ${N}_{D}$, using quantum amplitude estimation, and other parts classically. Additionally, we generalize our method to some class of convex optimization problems.

DOI
10.1103/physreva.104.022430

Related papers

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

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•144 citations

Quantum Kaczmarz Algorithm for Solving Linear Algebraic Equations

Nhat A. Nghiem, Tuan K. Do, Trung V. Phan

We introduce a quantum linear system solving algorithm based on the Kaczmarz method, a widely used workhorse for large linear systems and least-squares problems that updates the solution by enforcing one equation at a time. Its simplicity and low memory cost make it a practical choice across data regression, tomographic reconstruction, and optimization. In contrast to many existing quantum linear solvers, our method does not rely on oracle access to query entries, relaxing a key practicality bottleneck. In particular, when the rank of the system of interest is sufficiently small and the rows of the matrix of interest admit an appropriate structure, we achieve circuit complexity $\mathcal{O}\left(\frac{1}{\varepsilon}\log m\right)$, where $m$ is the number of variables and $\varepsilon$ is the target precision, without dependence on the sparsity $s$, and could possibly be without explicit dependence on condition number $κ$. This shows a significant improvement over previous quantum linear solvers where the dependence on $κ,s$ is at least linear. At the same time, when the rows have an arbitrary structure and have at most $s$ nonzero entries, we obtain the circuit depth $\mathcal{O}\left(\frac{1}{\varepsilon}\log s\right)$ using extra $\mathcal{O}(s)$ ancilla qubits, so the depth grows only logarithmically with sparsity $s$. When the sparsity $s$ grows as $\mathcal{O}(\log m)$, then our method can achieve an exponential improvement with respect to circuit depth compared to existing quantum algorithms, while using (asymptotically) the same amount of qubits.

quant-pharXiv:2601.01342•Jan 6, 2026•0 citations

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

Zhao Song, Junze Yin, Ruizhe Zhang

Linear regression is one of the most fundamental linear algebra problems. Given a dense matrix $A \in \mathbb{R}^{n \times d}$ and a vector $b$, the goal is to find $x'$ such that $ \| Ax' - b \|_2^2 \leq (1+ε) \min_{x} \| A x - b \|_2^2 $. The best classical algorithm takes $O(nd) + \mathrm{poly}(d/ε)$ time [Clarkson and Woodruff STOC 2013, Nelson and Nguyen FOCS 2013]. On the other hand, quantum linear regression algorithms can achieve exponential quantum speedups, as shown in [Wang Phys. Rev. A 96, 012335, Kerenidis and Prakash ITCS 2017, Chakraborty, Gily{é}n and Jeffery ICALP 2019]. However, the running times of these algorithms depend on some quantum linear algebra-related parameters, such as $κ(A)$, the condition number of $A$. In this work, we develop a quantum algorithm that runs in $\widetilde{O}(ε^{-1}\sqrt{n}d^{1.5}) + \mathrm{poly}(d/ε)$ time. It provides a quadratic quantum speedup in $n$ over the classical lower bound without any dependence on data-dependent parameters. In addition, we also show our result can be generalized to multiple regression and ridge linear regression.

arXiv:2311.14823•Nov 24, 2023•0 citations

Quantum-Enhanced Symbolic Regression

Jincheng Zhang

Symbolic regression is a powerful technique for automatically discovering mathematical equations from data. However, its performance is often limited by the computational cost of exploring the exponentially large space of possible equations. This paper presents a novel approach that integrates symbolic regression with quantum amplitude estimation (QAE) to accelerate the equation discovery process. The core idea is to utilize QAE to efficiently estimate the probability amplitude of different equation candidates, thereby reducing the search time. We formulate the symbolic regression problem as a quantum optimization task and demonstrate, through theoretical analysis and a conceptual framework, the potential for significant speedups. The proposed method addresses the inherent challenges of symbolic regression by exploiting the parallel processing capabilities of quantum computers. The results suggest that quantum-enhanced symbolic regression holds promise for tackling complex datasets and discovering intricate mathematical relationships that would be intractable for classical symbolic regression algorithms. The key contribution lies in the application of QAE within the symbolic regression framework, offering a pathway toward faster and more accurate equation modeling.

•Sep 3, 2026•0 citations

Quantum Algorithm for Linear Regression for Large Feature-Set

Amey Kulkarni, Devvrat Joshi

Linear Regression is a widely used optimization problem with many practical applications. Adiabatic Quantum Computers are excellent at solving such optimization problems. Current quantum-based solutions allow for datasets having only a small number of features (maximum 32). We have come up with a novel approach that allows for a greater number of features for Linear Regression. We have found that our approach works for a large number of features, ranging from 64 to 128. We obtained a reasonably similar MSE (Mean Squared Error) to that of sklearn’s standard Linear Regression class, with a difference that lies between 0.01 and 0.03.

Joint International Conference on Data Science & Management of Data (CODS-COMAD)•Jan 7, 2022•0 citations
Linear regression is a basic and widely used methodology in data analysis. It is known that some quantum algorithms efficiently perform least-squares linear regression of an exponentially large dataset. However, if we obtain values of the regression coefficients as classical data, the complexity of the existing quantum algorithms can be larger than the classical method. This is because it depends strongly on the tolerance error \ensuremathϵ\ensuremath{\epsilon}\ensuremathϵ: the best one among the existing proposals is O(\ensuremathϵ\ensuremath−2)O({\ensuremath{\epsilon}}^{\ensuremath{-}2})O(\ensuremathϵ\ensuremath−2). In this paper, we propose a quantum algorithm for linear regression, which has a complexity of O(\ensuremathϵ\ensuremath−1)O({\ensuremath{\epsilon}}^{\ensuremath{-}1})O(\ensuremathϵ\ensuremath−1) and keeps a logarithmic dependence on the number of data points ND{N}_{D}ND​. In this method, we overcome bottleneck parts in the calculation, which take the form of the sum over data points and therefore have a complexity proportional to ND{N}_{D}ND​, using quantum amplitude estimation, and other parts classically. Additionally, we generalize our method to some class of convex optimization problems.
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.
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.
We introduce a quantum linear system solving algorithm based on the Kaczmarz method, a widely used workhorse for large linear systems and least-squares problems that updates the solution by enforcing one equation at a time. Its simplicity and low memory cost make it a practical choice across data regression, tomographic reconstruction, and optimization. In contrast to many existing quantum linear solvers, our method does not rely on oracle access to query entries, relaxing a key practicality bottleneck. In particular, when the rank of the system of interest is sufficiently small and the rows of the matrix of interest admit an appropriate structure, we achieve circuit complexity O(1εlog⁡m)\mathcal{O}\left(\frac{1}{\varepsilon}\log m\right)O(ε1​logm), where mmm is the number of variables and ε\varepsilonε is the target precision, without dependence on the sparsity sss, and could possibly be without explicit dependence on condition number κκκ. This shows a significant improvement over previous quantum linear solvers where the dependence on κ,sκ,sκ,s is at least linear. At the same time, when the rows have an arbitrary structure and have at most sss nonzero entries, we obtain the circuit depth O(1εlog⁡s)\mathcal{O}\left(\frac{1}{\varepsilon}\log s\right)O(ε1​logs) using extra O(s)\mathcal{O}(s)O(s) ancilla qubits, so the depth grows only logarithmically with sparsity sss. When the sparsity sss grows as O(log⁡m)\mathcal{O}(\log m)O(logm), then our method can achieve an exponential improvement with respect to circuit depth compared to existing quantum algorithms, while using (asymptotically) the same amount of qubits.
Linear regression is one of the most fundamental linear algebra problems. Given a dense matrix A∈Rn×dA \in \mathbb{R}^{n \times d}A∈Rn×d and a vector bbb, the goal is to find x′x'x′ such that $ \| Ax' - b \|_2^2 \leq (1+ε) \min_{x} \| A x - b \|_2^2 $. The best classical algorithm takes O(nd)+poly(d/ε)O(nd) + \mathrm{poly}(d/ε)O(nd)+poly(d/ε) time [Clarkson and Woodruff STOC 2013, Nelson and Nguyen FOCS 2013]. On the other hand, quantum linear regression algorithms can achieve exponential quantum speedups, as shown in [Wang Phys. Rev. A 96, 012335, Kerenidis and Prakash ITCS 2017, Chakraborty, Gily{é}n and Jeffery ICALP 2019]. However, the running times of these algorithms depend on some quantum linear algebra-related parameters, such as κ(A)κ(A)κ(A), the condition number of AAA. In this work, we develop a quantum algorithm that runs in O~(ε−1nd1.5)+poly(d/ε)\widetilde{O}(ε^{-1}\sqrt{n}d^{1.5}) + \mathrm{poly}(d/ε)O(ε−1n​d1.5)+poly(d/ε) time. It provides a quadratic quantum speedup in nnn over the classical lower bound without any dependence on data-dependent parameters. In addition, we also show our result can be generalized to multiple regression and ridge linear regression.
Symbolic regression is a powerful technique for automatically discovering mathematical equations from data. However, its performance is often limited by the computational cost of exploring the exponentially large space of possible equations. This paper presents a novel approach that integrates symbolic regression with quantum amplitude estimation (QAE) to accelerate the equation discovery process. The core idea is to utilize QAE to efficiently estimate the probability amplitude of different equation candidates, thereby reducing the search time. We formulate the symbolic regression problem as a quantum optimization task and demonstrate, through theoretical analysis and a conceptual framework, the potential for significant speedups. The proposed method addresses the inherent challenges of symbolic regression by exploiting the parallel processing capabilities of quantum computers. The results suggest that quantum-enhanced symbolic regression holds promise for tackling complex datasets and discovering intricate mathematical relationships that would be intractable for classical symbolic regression algorithms. The key contribution lies in the application of QAE within the symbolic regression framework, offering a pathway toward faster and more accurate equation modeling.
Linear Regression is a widely used optimization problem with many practical applications. Adiabatic Quantum Computers are excellent at solving such optimization problems. Current quantum-based solutions allow for datasets having only a small number of features (maximum 32). We have come up with a novel approach that allows for a greater number of features for Linear Regression. We have found that our approach works for a large number of features, ranging from 64 to 128. We obtained a reasonably similar MSE (Mean Squared Error) to that of sklearn’s standard Linear Regression class, with a difference that lies between 0.01 and 0.03.