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:1907.06949

Quantum Data Fitting Algorithm for Non-sparse Matrices

Guangxi Li, Youle Wang, Yu Luo, Yuan Feng

Published Jul 16, 2019• 2 citations
arXivHTMLPDF

Abstract

We propose a quantum data fitting algorithm for non-sparse matrices, which is based on the Quantum Singular Value Estimation (QSVE) subroutine and a novel efficient method for recovering the signs of eigenvalues. Our algorithm generalizes the quantum data fitting algorithm of Wiebe, Braun, and Lloyd for sparse and well-conditioned matrices by adding a regularization term to avoid the over-fitting problem, which is a very important problem in machine learning. As a result, the algorithm achieves a sparsity-independent runtime of $O(κ^2\sqrt{N}\mathrm{polylog}(N)/(ε\logκ))$ for an $N\times N$ dimensional Hermitian matrix $\bm{F}$, where $κ$ denotes the condition number of $\bm{F}$ and $ε$ is the precision parameter. This amounts to a polynomial speedup on the dimension of matrices when compared with the classical data fitting algorithms, and a strictly less than quadratic dependence on $κ$.

DOI
10.48550/arxiv.1907.06949

Related papers

Quantum Linear System Algorithm for Dense Matrices

Leonard Wossnig, Zhikuan Zhao, Anupam Prakash

Solving linear systems of equations is a frequently encountered problem in machine learning and optimization. Given a matrix $A$ and a vector $\mathbf{b}$ the task is to find the vector $\mathbf{x}$ such that $A\mathbf{x}=\mathbf{b}$. We describe a quantum algorithm that achieves a sparsity-independent runtime scaling of $\mathcal{O}\mathbf{(}{\ensuremath{\kappa}}^{2}\sqrt{n}\text{polylog}(n)/\ensuremath{\epsilon}\mathbf{)}$ for an $n\ifmmode\times\else\texttimes\fi{}n$ dimensional $A$ with bounded spectral norm, where $\ensuremath{\kappa}$ denotes the condition number of $A$, and $\ensuremath{\epsilon}$ is the desired precision parameter. This amounts to a polynomial improvement over known quantum linear system algorithms when applied to dense matrices, and poses a new state of the art for solving dense linear systems on a quantum computer. Furthermore, an exponential improvement is achievable if the rank of $A$ is polylogarithmic in the matrix dimension. Our algorithm is built upon a singular value estimation subroutine, which makes use of a memory architecture that allows for efficient preparation of quantum states that correspond to the rows of $A$ and the vector of Euclidean norms of the rows of $A$.

arXiv:1704.06174•Physical Review Letters•Jan 31, 2018•222 citations

Quantum Regularized Least Squares

Shantanav Chakraborty, Aditya Morolia, Anurudh Peduri

Linear regression is a widely used technique to fit linear models and finds widespread applications across different areas such as machine learning and statistics. In most real-world scenarios, however, linear regression problems are often ill-posed or the underlying model suffers from o v e r f i t t i n g , leading to erroneous or trivial solutions. This is often dealt with by adding extra constraints, known as regularization. In this paper, we use the frameworks of block-encoding and quantum singular value transformation (QSVT) to design the first quantum algorithms for quantum least squares with general ℓ 2 -regularization. These include regularized versions of quantum ordinary least squares, quantum weighted least squares, and quantum generalized least squares. Our quantum algorithms substantially improve upon prior results on quantum ridge regression (polynomial improvement in the condition number and an exponential improvement in accuracy), which is a particular case of our result.To this end, we assume approximate block-encodings of the underlying matrices as input and use robust QSVT algorithms for various linear algebra operations. In particular, we develop a variable-time quantum algorithm for matrix inversion using QSVT, where we use quantum eigenvalue discrimination as a subroutine instead of gapped phase estimation. This ensures that substantially fewer ancilla qubits are required for this procedure than prior results. Owing to the generality of the block-encoding framework, our algorithms are applicable to a variety of input models and can also be seen as improved and generalized versions of prior results on standard (non-regularized) quantum least squares algorithms.

arXiv:2206.13143•Quantum•Apr 27, 2023•22 citations

Computing eigenvalues of diagonalizable matrices in a quantum computer

Changpeng Shao

Solving linear systems and computing eigenvalues are two fundamental problems in linear algebra. For solving linear systems, many efficient quantum algorithms have been discovered. For computing eigenvalues, currently, we have efficient quantum algorithms for Hermitian and unitary matrices. However, the general case is far from fully understood. Combining quantum phase estimation, quantum algorithm to solve linear differential equations and quantum singular value estimation, we propose two quantum algorithms to compute the eigenvalues of diagonalizable matrices that only have real eigenvalues and normal matrices. The output of the quantum algorithms is a superposition of the eigenvalues and the corresponding eigenvectors. The complexities are dominated by solving a linear system of ODEs and performing quantum singular value estimation, which usually can be solved efficiently in a quantum computer. In the special case when the matrix $M$ is $s$-sparse, the complexity is $\widetilde{O}(sρ^2 κ^2/ε^2)$ for diagonalizable matrices that only have real eigenvalues, and $\widetilde{O}(sρ\|M\|_{\max} /ε^2)$ for normal matrices. Here $ρ$ is an upper bound of the eigenvalues, $κ$ is the conditioning of the eigenvalue problem, and $ε$ is the precision to approximate the eigenvalues. We also extend the quantum algorithm to diagonalizable matrices with complex eigenvalues under an extra assumption.

arXiv:1912.08015•Dec 17, 2019•5 citations

Quantum Algorithm for Spectral Regression for Regularized Subspace Learning

Fan‐Xu Meng, Xutao Yu, Rui-Qing Xiang +1 more

In this paper, we propose an efficient quantum algorithm for spectral regression which is a dimensionality reduction framework based on the regression and spectral graph analysis. The quantum algorithm involves two core subroutines: the quantum principal eigenvectors analysis and the quantum ridge regression algorithm. The quantum principal eigenvectors analysis can be performed by an efficient sparse Hamiltonian simulation. For the ridge regression, we propose a quantum algorithm that is derived from the quantum singular value decomposition method. Our quantum ridge regression algorithm is more suitable for data matrices that are non-sparse and skewed. Our analysis demonstrates that the quantum subroutines can be implemented with an approximatively polynomial speedup on a quantum computer over their classical counterparts.

IEEE Access•Dec 13, 2018•7 citations

Computing eigenvalues of matrices in a quantum computer

Changpeng Shao

Eigenproblem arises in a large number of disciplines of sciences and engineering. Combining quantum algorithms to solve linear differential equations, quantum singular value estimation and quantum phase estimation, we propose quantum algorithms to compute the eigenvalues of diagonalizable matrices of two types: matrices that only have real eigenvalues and normal matrices. The quantum algorithms return a quantum state such that the first register stores eigenvalues and the second register stores the corresponding eigenvectors. For normal matrices, the complexity to obtain this quantum state is dominated by the complexity to perform quantum singular value estimation. For the other case, the complexity is determined by the solving of a linear system of differential equations. Under certain conditions (e.g. sparse), the complexities are polylog on the size $n$ of the given matrix. If we perform measurements, then we can obtain all the eigenvalues classically. If $M$ is $s$ sparse, then the complexity is $\widetilde{O}(sn\|M\|_{\max}\kappa^2/\epsilon^2)$, where $\kappa$ is the condition number of the matrix of eigenvectors.

•Dec 17, 2019•4 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
We propose a quantum data fitting algorithm for non-sparse matrices, which is based on the Quantum Singular Value Estimation (QSVE) subroutine and a novel efficient method for recovering the signs of eigenvalues. Our algorithm generalizes the quantum data fitting algorithm of Wiebe, Braun, and Lloyd for sparse and well-conditioned matrices by adding a regularization term to avoid the over-fitting problem, which is a very important problem in machine learning. As a result, the algorithm achieves a sparsity-independent runtime of O(κ2Npolylog(N)/(εlog⁡κ))O(κ^2\sqrt{N}\mathrm{polylog}(N)/(ε\logκ))O(κ2N​polylog(N)/(εlogκ)) for an N×NN\times NN×N dimensional Hermitian matrix F\bm{F}F, where κκκ denotes the condition number of F\bm{F}F and εεε is the precision parameter. This amounts to a polynomial speedup on the dimension of matrices when compared with the classical data fitting algorithms, and a strictly less than quadratic dependence on κκκ.
Solving linear systems of equations is a frequently encountered problem in machine learning and optimization. Given a matrix AAA and a vector b\mathbf{b}b the task is to find the vector x\mathbf{x}x such that Ax=bA\mathbf{x}=\mathbf{b}Ax=b. We describe a quantum algorithm that achieves a sparsity-independent runtime scaling of $\mathcal{O}\mathbf{(}{\ensuremath{\kappa}}^{2}\sqrt{n}\text{polylog}(n)/\ensuremath{\epsilon}\mathbf{)}$ for an $n\ifmmode\times\else\texttimes\fi{}n$ dimensional AAA with bounded spectral norm, where $\ensuremath{\kappa}$ denotes the condition number of AAA, and $\ensuremath{\epsilon}$ is the desired precision parameter. This amounts to a polynomial improvement over known quantum linear system algorithms when applied to dense matrices, and poses a new state of the art for solving dense linear systems on a quantum computer. Furthermore, an exponential improvement is achievable if the rank of AAA is polylogarithmic in the matrix dimension. Our algorithm is built upon a singular value estimation subroutine, which makes use of a memory architecture that allows for efficient preparation of quantum states that correspond to the rows of AAA and the vector of Euclidean norms of the rows of AAA.
Linear regression is a widely used technique to fit linear models and finds widespread applications across different areas such as machine learning and statistics. In most real-world scenarios, however, linear regression problems are often ill-posed or the underlying model suffers from o v e r f i t t i n g , leading to erroneous or trivial solutions. This is often dealt with by adding extra constraints, known as regularization. In this paper, we use the frameworks of block-encoding and quantum singular value transformation (QSVT) to design the first quantum algorithms for quantum least squares with general ℓ 2 -regularization. These include regularized versions of quantum ordinary least squares, quantum weighted least squares, and quantum generalized least squares. Our quantum algorithms substantially improve upon prior results on quantum ridge regression (polynomial improvement in the condition number and an exponential improvement in accuracy), which is a particular case of our result.To this end, we assume approximate block-encodings of the underlying matrices as input and use robust QSVT algorithms for various linear algebra operations. In particular, we develop a variable-time quantum algorithm for matrix inversion using QSVT, where we use quantum eigenvalue discrimination as a subroutine instead of gapped phase estimation. This ensures that substantially fewer ancilla qubits are required for this procedure than prior results. Owing to the generality of the block-encoding framework, our algorithms are applicable to a variety of input models and can also be seen as improved and generalized versions of prior results on standard (non-regularized) quantum least squares algorithms.
Solving linear systems and computing eigenvalues are two fundamental problems in linear algebra. For solving linear systems, many efficient quantum algorithms have been discovered. For computing eigenvalues, currently, we have efficient quantum algorithms for Hermitian and unitary matrices. However, the general case is far from fully understood. Combining quantum phase estimation, quantum algorithm to solve linear differential equations and quantum singular value estimation, we propose two quantum algorithms to compute the eigenvalues of diagonalizable matrices that only have real eigenvalues and normal matrices. The output of the quantum algorithms is a superposition of the eigenvalues and the corresponding eigenvectors. The complexities are dominated by solving a linear system of ODEs and performing quantum singular value estimation, which usually can be solved efficiently in a quantum computer. In the special case when the matrix MMM is sss-sparse, the complexity is O~(sρ2κ2/ε2)\widetilde{O}(sρ^2 κ^2/ε^2)O(sρ2κ2/ε2) for diagonalizable matrices that only have real eigenvalues, and O~(sρ∥M∥max⁡/ε2)\widetilde{O}(sρ\|M\|_{\max} /ε^2)O(sρ∥M∥max​/ε2) for normal matrices. Here ρρρ is an upper bound of the eigenvalues, κκκ is the conditioning of the eigenvalue problem, and εεε is the precision to approximate the eigenvalues. We also extend the quantum algorithm to diagonalizable matrices with complex eigenvalues under an extra assumption.
In this paper, we propose an efficient quantum algorithm for spectral regression which is a dimensionality reduction framework based on the regression and spectral graph analysis. The quantum algorithm involves two core subroutines: the quantum principal eigenvectors analysis and the quantum ridge regression algorithm. The quantum principal eigenvectors analysis can be performed by an efficient sparse Hamiltonian simulation. For the ridge regression, we propose a quantum algorithm that is derived from the quantum singular value decomposition method. Our quantum ridge regression algorithm is more suitable for data matrices that are non-sparse and skewed. Our analysis demonstrates that the quantum subroutines can be implemented with an approximatively polynomial speedup on a quantum computer over their classical counterparts.
Eigenproblem arises in a large number of disciplines of sciences and engineering. Combining quantum algorithms to solve linear differential equations, quantum singular value estimation and quantum phase estimation, we propose quantum algorithms to compute the eigenvalues of diagonalizable matrices of two types: matrices that only have real eigenvalues and normal matrices. The quantum algorithms return a quantum state such that the first register stores eigenvalues and the second register stores the corresponding eigenvectors. For normal matrices, the complexity to obtain this quantum state is dominated by the complexity to perform quantum singular value estimation. For the other case, the complexity is determined by the solving of a linear system of differential equations. Under certain conditions (e.g. sparse), the complexities are polylog on the size nnn of the given matrix. If we perform measurements, then we can obtain all the eigenvalues classically. If MMM is sss sparse, then the complexity is O~(sn∥M∥max⁡κ2/ϵ2)\widetilde{O}(sn\|M\|_{\max}\kappa^2/\epsilon^2)O(sn∥M∥max​κ2/ϵ2), where κ\kappaκ is the condition number of the matrix of eigenvectors.
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.