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

Quantum Algorithms for Linear Algebra and Machine Learning.

Anupam Prakash

Published Jan 1, 2014• 47 citations
OpenAlex

Abstract

Most quantum algorithms offering speedups over classical algorithms are based on the three techniques of phase estimation, amplitude estimation and Hamiltonian simulation. In spite of the linear algebraic nature of the postulates of quantum mechanics, until recent work by Lloyd and coauthors cite{LMR13, LMR13a, LMR13b} no quantum algorithms achieving speedups for linear algebra or machine learning had been proposed. A quantum machine learning algorithm must address three issues: encoding of classical data into a succinct quantum representation, processing the quantum representation and extraction of classically useful information from the processed quantum state. In this dissertation, we make progress on all three aspects of the quantum machine learning problem and obtain quantum algorithms for low rank approximation and regularized least squares. The oracle $QRAM$, the standard model studied in quantum query complexity, requires time $O(sqrt{n})$ to encode vectors $v in R^{n}$ into quantum states. We propose simple hardware augmentations to the oracle $QRAM$, that enable vectors $v in R^{n}$ to be encoded in time $O(log n)$, with pre-processing. The augmented $QRAM$ incurs minimal hardware overheads, the pre-processing can be parallelized and is a flexible model that allows storage of multiple vectors and matrices. It provides a framework for designing quantum algorithms for linear algebra and machine learning. Using the augmented $QRAM$ for vector state preparation, we present two different algorithms for singular value estimation where given singular vector $ket{v}$ for $A in R^{mtimes n}$, the singular value $sigma_{i}$ is estimated within additive error $epsilon norm{A}_{F}$. The first algorithm requires time $wt{1/epsilon^{3}}$ and uses the approach for simulating $e^{-i rho}$ in cite{LMR13}. However, the analysis cite{LMR13} does not establish the coherence of outputs, we provide a qualitatively different analysis that uses the quantum Zeno effect to establish coherence and reveals the probabilistic nature of the simulation technique. The second algorithm has a running time $wt{1/epsilon}$ and uses Jordan's lemma from linear algebra and the augmented $QRAM$ to implement reflections. We use quantum singular value estimation to obtain algorithms for low rank approximation by column selection, the algorithms are based on importance sampling from the leverage score distribution. We obtain quadratic speedups for a large class of linear algebra algorithms that rely on importance sampling from the leverage score distribution including approximate least squares and $CX$ and $CUR$ decompositions. Classical algorithms for these problems require time $O(mn log n + poly(1/epsilon))$, the quantum algorithms have running time $O(sqrt{m}poly(1/epsilon, k, Delta))$ where $k, Delta$ are the rank and spectral gap. The running time of the quantum $CX$ decomposition algorithm does not depend on $m$, it is polynomial in problem parameters. We also provide quantum algorithms for $ell_{2}$ regularized regression problems, the quantum ridge regression algorithm requires time $wt{1/mu^{2} delta}$ to output a quantum state that is $delta$ close to the solution, where $mu$ is the regularization parameter.

Related papers

Quantum algorithms for linear algebra and machine learning. - eScholarship

Anupam Prakash

Most quantum algorithms offering speedups over classical algorithms are based on the three techniques of phase estimation, amplitude estimation and Hamiltonian simulation. In spite of the linear algebraic nature of the postulates of quantum mechanics, until recent work by Lloyd and coauthors cite{LMR13, LMR13a, LMR13b} no quantum algorithms achieving speedups for linear algebra or machine learning had been proposed. A quantum machine learning algorithm must address three issues: encoding of classical data into a succinct quantum representation, processing the quantum representation and extraction of classically useful information from the processed quantum state. In this dissertation, we make progress on all three aspects of the quantum machine learning problem and obtain quantum algorithms for low rank approximation and regularized least squares. The oracle $QRAM$, the standard model studied in quantum query complexity, requires time $O(sqrt{n})$ to encode vectors $v in R^{n}$ into quantum states. We propose simple hardware augmentations to the oracle $QRAM$, that enable vectors $v in R^{n}$ to be encoded in time $O(log n)$, with pre-processing. The augmented $QRAM$ incurs minimal hardware overheads, the pre-processing can be parallelized and is a flexible model that allows storage of multiple vectors and matrices. It provides a framework for designing quantum algorithms for linear algebra and machine learning. Using the augmented $QRAM$ for vector state preparation, we present two different algorithms for singular value estimation where given singular vector $ket{v}$ for $A in R^{mtimes n}$, the singular value $sigma_{i}$ is estimated within additive error $epsilon norm{A}_{F}$. The first algorithm requires time $wt{1/epsilon^{3}}$ and uses the approach for simulating $e^{-i rho}$ in cite{LMR13}. However, the analysis cite{LMR13} does not establish the coherence of outputs, we provide a qualitatively different analysis that uses the quantum Zeno effect to establish coherence and reveals the probabilistic nature of the simulation technique. The second algorithm has a running time $wt{1/epsilon}$ and uses Jordan's lemma from linear algebra and the augmented $QRAM$ to implement reflections. We use quantum singular value estimation to obtain algorithms for low rank approximation by column selection, the algorithms are based on importance sampling from the leverage score distribution. We obtain quadratic speedups for a large class of linear algebra algorithms that rely on importance sampling from the leverage score distribution including approximate least squares and $CX$ and $CUR$ decompositions. Classical algorithms for these problems require time $O(mn log n + poly(1/epsilon))$, the quantum algorithms have running time $O(sqrt{m}poly(1/epsilon, k, Delta))$ where $k, Delta$ are the rank and spectral gap. The running time of the quantum $CX$ decomposition algorithm does not depend on $m$, it is polynomial in problem parameters. We also provide quantum algorithms for $ell_{2}$ regularized regression problems, the quantum ridge regression algorithm requires time $wt{1/mu^{2} delta}$ to output a quantum state that is $delta$ close to the solution, where $mu$ is the regularization parameter.

•Jan 1, 2014•0 citations

Quantum Algorithms for Matrix Problems and Machine Learning

Sathyawageeswar Subramanian

This dissertation presents a study of quantum algorithms for problems that can be posed as matrix function tasks. In Chapter 1 we demonstrate a simple unifying framework for implementing of smooth functions of matrices on a quantum computer. This framework captures a variety of problems that can be solved by evaluating properties of some function of a matrix, and we identify speedups over classical algorithms for some problem classes. The analysis combines ideas from the classical theory of function approximation with the quantum algorithmic primitive of implementing linear combinations of unitary operators. In Chapter 2 we continue this study by looking at the role of sparsity of input matrices in constructing efficient quantum algorithms. We show that classically pre-processing an input matrix by spectral sparsification can be profitable for quantum Hamiltonian simulation algorithms, without compromising the simulation error or complexity. Such preprocessing incurs a one time cost linear in the size of the matrix, but can be exploited to exponentially speed up subsequent subroutines such as inversion. In Chapter 3, we give an application of this theory of matrix functions to the problem of estimating the Renyi entropy of an unknown quantum state. We combine matrix function techniques with mixed state quantum computation in the one-clean qubit model, and are able to bound of the expected runtime of our algorithm in terms of the unknown target quantity. In addition to the theme of analysing the complexity of our algorithms, we also identify instances that are of practical relevance, leading us to some problems of machine learning. In Chapter 4 we investigate kernel based learning methods using random features. We work with the QRAM input model suitable for big data, and show how matrix functions and the quantum Fourier transform can be used to devise a quantum algorithm for sampling random features that are optimised for given input data and choice of kernel. We obtain a potential exponential speedup over the best known classical algorithm even without explicit assumptions of sparsity or low rank. Finally in Chapter 5 we consider the technique of beamsearch decoding used in natural language processing. We work in the query model, and show how quantum search with advice can be used to construct a quantum search decoder that can find the optimal parse (which may for instance be a best translation, or text-to-speech transcript) at least quadratically faster than the best known classical algorithms, and obtain super-quadratic speedups in the expected runtime.

•Jul 24, 2020•0 citations

Quantum machine learning with subspace states

Iordanis Kerenidis, Anupam Prakash

We introduce a new approach for quantum linear algebra based on quantum subspace states and present three new quantum machine learning algorithms. The first is a quantum determinant sampling algorithm that samples from the distribution $\Pr[S]= det(X_{S}X_{S}^{T})$ for $|S|=d$ using $O(nd)$ gates and with circuit depth $O(d\log n)$. The state of art classical algorithm for the task requires $O(d^{3})$ operations \cite{derezinski2019minimax}. The second is a quantum singular value estimation algorithm for compound matrices $\mathcal{A}^{k}$, the speedup for this algorithm is potentially exponential. It decomposes a $\binom{n}{k}$ dimensional vector of order-$k$ correlations into a linear combination of subspace states corresponding to $k$-tuples of singular vectors of $A$. The third algorithm reduces exponentially the depth of circuits used in quantum topological data analysis from $O(n)$ to $O(\log n)$. Our basic tool are quantum subspace states, defined as $|Col(X)\rangle = \sum_{S\subset [n], |S|=d} det(X_{S}) |S\rangle$ for matrices $X \in \mathbb{R}^{n \times d}$ such that $X^{T} X = I_{d}$, that encode $d$-dimensional subspaces of $\mathbb{R}^{n}$. We develop two efficient state preparation techniques, the first using Givens circuits uses the representation of a subspace as a sequence of Givens rotations, while the second uses efficient implementations of unitaries $Γ(x) = \sum_{i} x_{i} Z^{\otimes (i-1)} \otimes X \otimes I^{n-i}$ with $O(\log n)$ depth circuits that we term Clifford loaders.

arXiv:2202.00054•Jan 31, 2022•10 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

An improved quantum-inspired algorithm for linear regression

András Gilyén, Zhao Song, Ewin Tang

We give a classical algorithm for linear regression analogous to the quantum matrix inversion algorithm [Harrow, Hassidim, and Lloyd, Physical Review Letters'09] for low-rank matrices [Wossnig, Zhao, and Prakash, Physical Review Letters'18], when the input matrix A is stored in a data structure applicable for QRAM-based state preparation.Namely, suppose we are given an A∈Cm×n with minimum non-zero singular value σ which supports certain efficient ℓ2 -norm importance sampling queries, along with a b∈Cm . Then, for some x∈Cn satisfying ‖x–A+b‖≤ε‖A+b‖ , we can output a measurement of |x⟩ in the computational basis and output an entry of x with classical algorithms that run in O~(‖A‖F6‖A‖6σ12ε4) and O~(‖A‖F6‖A‖2σ8ε4) time, respectively. This improves on previous "quantum-inspired" algorithms in this line of research by at least a factor of ‖A‖16σ16ε2 [Chia, Gilyén, Li, Lin, Tang, and Wang, STOC'20]. As a consequence, we show that quantum computers can achieve at most a factor-of-12 speedup for linear regression in this QRAM data structure setting and related settings. Our work applies techniques from sketching algorithms and optimization to the quantum-inspired literature. Unlike earlier works, this is a promising avenue that could lead to feasible implementations of classical regression in a quantum-inspired settings, for comparison against future quantum computers.

arXiv:2009.07268•Quantum•Jun 30, 2022•48 citations

Quantum Machine Learning: Applications, Algorithms, and Hardware Challenges

Juan Lopez

Quantum Machine Learning (QML) integrates quantum algorithms into machine learning programs to enhance and expedite classical machine learning techniques. It leverages quantum data and hybrid quantum-classical models, utilizing the principles of superposition and entanglement to handle complex joint probability distributions that would require exponential classical computational resources. QML aims to harness the unique properties of quantum computers for practical machine learning tasks, with the goal of achieving quantum advantage over classical approaches. QML finds applications in diverse fields such as chemical and quantum matter simulation, quantum control, quantum communication networks, and quantum metrology. Quantum algorithms can analyze quantum states and improve computational speed and data storage. Two main frameworks, quantum kernel methods and variational quantum algorithms, are widely used due to their implement ability on quantum hardware and capacity to work on general datasets. Quantum computers can solve linear algebraic problems, calculate eigenvectors and eigenvalues, and perform support vector algorithms at exponentially faster rates than classical computers. Despite its potential, QML faces significant challenges related to quantum hardware capabilities, including limited qubit connectivity, noise, coherence times, and errors in state preparation and measurement. Hardware constraints, compatibility issues, high computational and memory requirements, and the difficulty of quantum programming also pose obstacles. Overcoming these hardware and software limitations is crucial for realizing the full potential of quantum machine learning

International Journal of AI BigData Computational and Management Studies•Jan 1, 2024•1 citation
Most quantum algorithms offering speedups over classical algorithms are based on the three techniques of phase estimation, amplitude estimation and Hamiltonian simulation. In spite of the linear algebraic nature of the postulates of quantum mechanics, until recent work by Lloyd and coauthors cite{LMR13, LMR13a, LMR13b} no quantum algorithms achieving speedups for linear algebra or machine learning had been proposed. A quantum machine learning algorithm must address three issues: encoding of classical data into a succinct quantum representation, processing the quantum representation and extraction of classically useful information from the processed quantum state. In this dissertation, we make progress on all three aspects of the quantum machine learning problem and obtain quantum algorithms for low rank approximation and regularized least squares. The oracle QRAMQRAMQRAM, the standard model studied in quantum query complexity, requires time O(sqrtn)O(sqrt{n})O(sqrtn) to encode vectors vinRnv in R^{n}vinRn into quantum states. We propose simple hardware augmentations to the oracle QRAMQRAMQRAM, that enable vectors vinRnv in R^{n}vinRn to be encoded in time O(logn)O(log n)O(logn), with pre-processing. The augmented QRAMQRAMQRAM incurs minimal hardware overheads, the pre-processing can be parallelized and is a flexible model that allows storage of multiple vectors and matrices. It provides a framework for designing quantum algorithms for linear algebra and machine learning. Using the augmented QRAMQRAMQRAM for vector state preparation, we present two different algorithms for singular value estimation where given singular vector ketvket{v}ketv for AinRmtimesnA in R^{mtimes n}AinRmtimesn, the singular value sigmaisigma_{i}sigmai​ is estimated within additive error epsilonnormAFepsilon norm{A}_{F}epsilonnormAF​. The first algorithm requires time wt1/epsilon3wt{1/epsilon^{3}}wt1/epsilon3 and uses the approach for simulating e−irhoe^{-i rho}e−irho in cite{LMR13}. However, the analysis cite{LMR13} does not establish the coherence of outputs, we provide a qualitatively different analysis that uses the quantum Zeno effect to establish coherence and reveals the probabilistic nature of the simulation technique. The second algorithm has a running time wt1/epsilonwt{1/epsilon}wt1/epsilon and uses Jordan's lemma from linear algebra and the augmented QRAMQRAMQRAM to implement reflections. We use quantum singular value estimation to obtain algorithms for low rank approximation by column selection, the algorithms are based on importance sampling from the leverage score distribution. We obtain quadratic speedups for a large class of linear algebra algorithms that rely on importance sampling from the leverage score distribution including approximate least squares and CXCXCX and CURCURCUR decompositions. Classical algorithms for these problems require time O(mnlogn+poly(1/epsilon))O(mn log n + poly(1/epsilon))O(mnlogn+poly(1/epsilon)), the quantum algorithms have running time O(sqrtmpoly(1/epsilon,k,Delta))O(sqrt{m}poly(1/epsilon, k, Delta))O(sqrtmpoly(1/epsilon,k,Delta)) where k,Deltak, Deltak,Delta are the rank and spectral gap. The running time of the quantum CXCXCX decomposition algorithm does not depend on mmm, it is polynomial in problem parameters. We also provide quantum algorithms for ell2ell_{2}ell2​ regularized regression problems, the quantum ridge regression algorithm requires time wt1/mu2deltawt{1/mu^{2} delta}wt1/mu2delta to output a quantum state that is deltadeltadelta close to the solution, where mumumu is the regularization parameter.
Most quantum algorithms offering speedups over classical algorithms are based on the three techniques of phase estimation, amplitude estimation and Hamiltonian simulation. In spite of the linear algebraic nature of the postulates of quantum mechanics, until recent work by Lloyd and coauthors cite{LMR13, LMR13a, LMR13b} no quantum algorithms achieving speedups for linear algebra or machine learning had been proposed. A quantum machine learning algorithm must address three issues: encoding of classical data into a succinct quantum representation, processing the quantum representation and extraction of classically useful information from the processed quantum state. In this dissertation, we make progress on all three aspects of the quantum machine learning problem and obtain quantum algorithms for low rank approximation and regularized least squares. The oracle QRAMQRAMQRAM, the standard model studied in quantum query complexity, requires time O(sqrtn)O(sqrt{n})O(sqrtn) to encode vectors vinRnv in R^{n}vinRn into quantum states. We propose simple hardware augmentations to the oracle QRAMQRAMQRAM, that enable vectors vinRnv in R^{n}vinRn to be encoded in time O(logn)O(log n)O(logn), with pre-processing. The augmented QRAMQRAMQRAM incurs minimal hardware overheads, the pre-processing can be parallelized and is a flexible model that allows storage of multiple vectors and matrices. It provides a framework for designing quantum algorithms for linear algebra and machine learning. Using the augmented QRAMQRAMQRAM for vector state preparation, we present two different algorithms for singular value estimation where given singular vector ketvket{v}ketv for AinRmtimesnA in R^{mtimes n}AinRmtimesn, the singular value sigmaisigma_{i}sigmai​ is estimated within additive error epsilonnormAFepsilon norm{A}_{F}epsilonnormAF​. The first algorithm requires time wt1/epsilon3wt{1/epsilon^{3}}wt1/epsilon3 and uses the approach for simulating e−irhoe^{-i rho}e−irho in cite{LMR13}. However, the analysis cite{LMR13} does not establish the coherence of outputs, we provide a qualitatively different analysis that uses the quantum Zeno effect to establish coherence and reveals the probabilistic nature of the simulation technique. The second algorithm has a running time wt1/epsilonwt{1/epsilon}wt1/epsilon and uses Jordan's lemma from linear algebra and the augmented QRAMQRAMQRAM to implement reflections. We use quantum singular value estimation to obtain algorithms for low rank approximation by column selection, the algorithms are based on importance sampling from the leverage score distribution. We obtain quadratic speedups for a large class of linear algebra algorithms that rely on importance sampling from the leverage score distribution including approximate least squares and CXCXCX and CURCURCUR decompositions. Classical algorithms for these problems require time O(mnlogn+poly(1/epsilon))O(mn log n + poly(1/epsilon))O(mnlogn+poly(1/epsilon)), the quantum algorithms have running time O(sqrtmpoly(1/epsilon,k,Delta))O(sqrt{m}poly(1/epsilon, k, Delta))O(sqrtmpoly(1/epsilon,k,Delta)) where k,Deltak, Deltak,Delta are the rank and spectral gap. The running time of the quantum CXCXCX decomposition algorithm does not depend on mmm, it is polynomial in problem parameters. We also provide quantum algorithms for ell2ell_{2}ell2​ regularized regression problems, the quantum ridge regression algorithm requires time wt1/mu2deltawt{1/mu^{2} delta}wt1/mu2delta to output a quantum state that is deltadeltadelta close to the solution, where mumumu is the regularization parameter.
This dissertation presents a study of quantum algorithms for problems that can be posed as matrix function tasks. In Chapter 1 we demonstrate a simple unifying framework for implementing of smooth functions of matrices on a quantum computer. This framework captures a variety of problems that can be solved by evaluating properties of some function of a matrix, and we identify speedups over classical algorithms for some problem classes. The analysis combines ideas from the classical theory of function approximation with the quantum algorithmic primitive of implementing linear combinations of unitary operators. In Chapter 2 we continue this study by looking at the role of sparsity of input matrices in constructing efficient quantum algorithms. We show that classically pre-processing an input matrix by spectral sparsification can be profitable for quantum Hamiltonian simulation algorithms, without compromising the simulation error or complexity. Such preprocessing incurs a one time cost linear in the size of the matrix, but can be exploited to exponentially speed up subsequent subroutines such as inversion. In Chapter 3, we give an application of this theory of matrix functions to the problem of estimating the Renyi entropy of an unknown quantum state. We combine matrix function techniques with mixed state quantum computation in the one-clean qubit model, and are able to bound of the expected runtime of our algorithm in terms of the unknown target quantity. In addition to the theme of analysing the complexity of our algorithms, we also identify instances that are of practical relevance, leading us to some problems of machine learning. In Chapter 4 we investigate kernel based learning methods using random features. We work with the QRAM input model suitable for big data, and show how matrix functions and the quantum Fourier transform can be used to devise a quantum algorithm for sampling random features that are optimised for given input data and choice of kernel. We obtain a potential exponential speedup over the best known classical algorithm even without explicit assumptions of sparsity or low rank. Finally in Chapter 5 we consider the technique of beamsearch decoding used in natural language processing. We work in the query model, and show how quantum search with advice can be used to construct a quantum search decoder that can find the optimal parse (which may for instance be a best translation, or text-to-speech transcript) at least quadratically faster than the best known classical algorithms, and obtain super-quadratic speedups in the expected runtime.
We introduce a new approach for quantum linear algebra based on quantum subspace states and present three new quantum machine learning algorithms. The first is a quantum determinant sampling algorithm that samples from the distribution Pr⁡[S]=det(XSXST)\Pr[S]= det(X_{S}X_{S}^{T})Pr[S]=det(XS​XST​) for ∣S∣=d|S|=d∣S∣=d using O(nd)O(nd)O(nd) gates and with circuit depth O(dlog⁡n)O(d\log n)O(dlogn). The state of art classical algorithm for the task requires O(d3)O(d^{3})O(d3) operations \cite{derezinski2019minimax}. The second is a quantum singular value estimation algorithm for compound matrices Ak\mathcal{A}^{k}Ak, the speedup for this algorithm is potentially exponential. It decomposes a (nk)\binom{n}{k}(kn​) dimensional vector of order-kkk correlations into a linear combination of subspace states corresponding to kkk-tuples of singular vectors of AAA. The third algorithm reduces exponentially the depth of circuits used in quantum topological data analysis from O(n)O(n)O(n) to O(log⁡n)O(\log n)O(logn). Our basic tool are quantum subspace states, defined as ∣Col(X)⟩=∑S⊂[n],∣S∣=ddet(XS)∣S⟩|Col(X)\rangle = \sum_{S\subset [n], |S|=d} det(X_{S}) |S\rangle∣Col(X)⟩=∑S⊂[n],∣S∣=d​det(XS​)∣S⟩ for matrices X∈Rn×dX \in \mathbb{R}^{n \times d}X∈Rn×d such that XTX=IdX^{T} X = I_{d}XTX=Id​, that encode ddd-dimensional subspaces of Rn\mathbb{R}^{n}Rn. We develop two efficient state preparation techniques, the first using Givens circuits uses the representation of a subspace as a sequence of Givens rotations, while the second uses efficient implementations of unitaries Γ(x)=∑ixiZ⊗(i−1)⊗X⊗In−iΓ(x) = \sum_{i} x_{i} Z^{\otimes (i-1)} \otimes X \otimes I^{n-i}Γ(x)=∑i​xi​Z⊗(i−1)⊗X⊗In−i with O(log⁡n)O(\log n)O(logn) depth circuits that we term Clifford loaders.
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.
We give a classical algorithm for linear regression analogous to the quantum matrix inversion algorithm [Harrow, Hassidim, and Lloyd, Physical Review Letters'09] for low-rank matrices [Wossnig, Zhao, and Prakash, Physical Review Letters'18], when the input matrix A is stored in a data structure applicable for QRAM-based state preparation.Namely, suppose we are given an A∈Cm×n with minimum non-zero singular value σ which supports certain efficient ℓ2 -norm importance sampling queries, along with a b∈Cm . Then, for some x∈Cn satisfying ‖x–A+b‖≤ε‖A+b‖ , we can output a measurement of |x⟩ in the computational basis and output an entry of x with classical algorithms that run in O~(‖A‖F6‖A‖6σ12ε4) and O~(‖A‖F6‖A‖2σ8ε4) time, respectively. This improves on previous "quantum-inspired" algorithms in this line of research by at least a factor of ‖A‖16σ16ε2 [Chia, Gilyén, Li, Lin, Tang, and Wang, STOC'20]. As a consequence, we show that quantum computers can achieve at most a factor-of-12 speedup for linear regression in this QRAM data structure setting and related settings. Our work applies techniques from sketching algorithms and optimization to the quantum-inspired literature. Unlike earlier works, this is a promising avenue that could lead to feasible implementations of classical regression in a quantum-inspired settings, for comparison against future quantum computers.
Quantum Machine Learning (QML) integrates quantum algorithms into machine learning programs to enhance and expedite classical machine learning techniques. It leverages quantum data and hybrid quantum-classical models, utilizing the principles of superposition and entanglement to handle complex joint probability distributions that would require exponential classical computational resources. QML aims to harness the unique properties of quantum computers for practical machine learning tasks, with the goal of achieving quantum advantage over classical approaches. QML finds applications in diverse fields such as chemical and quantum matter simulation, quantum control, quantum communication networks, and quantum metrology. Quantum algorithms can analyze quantum states and improve computational speed and data storage. Two main frameworks, quantum kernel methods and variational quantum algorithms, are widely used due to their implement ability on quantum hardware and capacity to work on general datasets. Quantum computers can solve linear algebraic problems, calculate eigenvectors and eigenvalues, and perform support vector algorithms at exponentially faster rates than classical computers. Despite its potential, QML faces significant challenges related to quantum hardware capabilities, including limited qubit connectivity, noise, coherence times, and errors in state preparation and measurement. Hardware constraints, compatibility issues, high computational and memory requirements, and the difficulty of quantum programming also pose obstacles. Overcoming these hardware and software limitations is crucial for realizing the full potential of quantum machine learning