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

Quantum singular-value decomposition of nonsparse low-rank matrices

Patrick Rebentrost, Adrian Steffens, Iman Marvian, Seth Lloyd

Published Jan 24, 2018• 135 citations
arXivHTMLPDF

Abstract

We present a method to exponentiate nonsparse indefinite low-rank matrices on a quantum computer. Given access to the elements of the matrix, our method allows one to determine the singular values and their associated singular vectors in time exponentially faster in the dimension of the matrix than known classical algorithms. The method extends to non-Hermitian and nonsquare matrices via matrix embedding. Moreover, our method preserves the phase relations between the singular spaces allowing for efficient algorithms that require operating on the entire singular-value decomposition of a matrix. As an example of such an algorithm, we discuss the Procrustes problem of finding a closest isometry to a given matrix.

DOI
10.1103/physreva.97.012327

Related papers

Continuous-variable quantum Gaussian process regression and quantum singular value decomposition of nonsparse low-rank matrices

Siddhartha Das, George Siopsis, Christian Weedbrook

With the significant advancement in quantum computation during the past couple of decades, the exploration of machine-learning subroutines using quantum strategies has become increasingly popular. Gaussian process regression is a widely used technique in supervised classical machine learning. Here we introduce an algorithm for Gaussian process regression using continuous-variable quantum systems that can be realized with technology based on photonic quantum computers under certain assumptions regarding distribution of data and availability of efficient quantum access. Our algorithm shows that by using a continuous-variable quantum computer a dramatic speedup in computing Gaussian process regression can be achieved, i.e., the possibility of exponentially reducing the time to compute. Furthermore, our results also include a continuous-variable quantum-assisted singular value decomposition method of nonsparse low rank matrices and forms an important subroutine in our Gaussian process regression algorithm.

arXiv:1707.00360•Physical Review A•Feb 12, 2018•26 citations

Quantum polar decomposition algorithm

Seth Lloyd, Samuel Bosch, Giacomo De Palma +5 more

The polar decomposition for a matrix $A$ is $A=UB$, where $B$ is a positive Hermitian matrix and $U$ is unitary (or, if $A$ is not square, an isometry). This paper shows that the ability to apply a Hamiltonian $\pmatrix{ 0 & A^\dagger \cr A & 0 \cr} $ translates into the ability to perform the transformations $e^{-iBt}$ and $U$ in a deterministic fashion. We show how to use the quantum polar decomposition algorithm to solve the quantum Procrustes problem, to perform pretty good measurements, to find the positive Hamiltonian closest to any Hamiltonian, and to perform a Hamiltonian version of the quantum singular value transformation.

arXiv:2006.00841•Jun 1, 2020•7 citations

Quantum-Inspired Algorithms for Solving Low-Rank Linear Equation Systems with Logarithmic Dependence on the Dimension

Nai-Hui Chia, András Gilyén, Han-Hsuan Lin +3 more

We present two efficient classical analogues of the quantum matrix inversion algorithm [16] for low-rank matrices. Inspired by recent work of Tang [27], assuming length-square sampling access to input data, we implement the pseudoinverse of a low-rank matrix allowing us to sample from the solution to the problem Ax = b using fast sampling techniques. We construct implicit descriptions of the pseudo-inverse by finding approximate singular value decomposition of A via subsampling, then inverting the singular values. In principle, our approaches can also be used to apply any desired “smooth” function to the singular values. Since many quantum algorithms can be expressed as a singular value transformation problem [15], our results indicate that more low-rank quantum algorithms can be effectively “dequantised” into classical length-square sampling algorithms.

•Jan 1, 2020•15 citations

Inverting well conditioned matrices in quantum logspace

Amnon Ta‐Shma

We show that quantum computers improve on the best known classical algorithms for matrix inversion (and singular value decomposition) as far as space is concerned. This adds to the (still short) list of important problems where quantum computers are of help. Specifically, we show that the inverse of a well conditioned matrix can be approximated in quantum logspace with intermediate measurements. This should be compared with the best known classical algorithm for the problem that requires Ω(log2 n) space. We also show how to approximate the spectrum of a normal matrix, or the singular values of an arbitrary matrix, with ε additive accuracy, and how to approximate the singular value decomposition (SVD) of a matrix whose singular values are well separated.

ACM Symposium on Theory of Computing (STOC)•May 28, 2013•36 citations

Quantum Higher Order Singular Value Decomposition

Lejia Gu, Xiaoqiang Wang, Guofeng Zhang

Higher order singular value decomposition (HOSVD) is an important tool for analyzing big data in multilinear algebra and machine learning. In this paper, we present a quantum algorithm for higher order singular value decomposition. Our method allows one to decompose a tensor into a core tensor containing tensor singular values and some unitary matrices by quantum computers. Compared to the classical HOSVD algorithm, our quantum algorithm provides an exponential speedup.

arXiv:1908.00719•Conference proceedings/Conference proceedings - IEEE International Conference on Systems, Man, and Cybernetics•Oct 1, 2019•9 citations

Quantum-Inspired Classical Algorithms for Singular Value Transformation

Dhawal Jethwani, François Le Gall, Sanjay Kumar Singh

A recent breakthrough by Tang (STOC 2019) showed how to "dequantize" the quantum algorithm for recommendation systems by Kerenidis and Prakash (ITCS 2017). The resulting algorithm, classical but "quantum-inspired", efficiently computes a low-rank approximation of the users' preference matrix. Subsequent works have shown how to construct efficient quantum-inspired algorithms for approximating the pseudo-inverse of a low-rank matrix as well, which can be used to (approximately) solve low-rank linear systems of equations. In the present paper, we pursue this line of research and develop quantum-inspired algorithms for a large class of matrix transformations that are defined via the singular value decomposition of the matrix. In particular, we obtain classical algorithms with complexity polynomially related (in most parameters) to the complexity of the best quantum algorithms for singular value transformation recently developed by Chakraborty, Gilyén and Jeffery (ICALP 2019) and Gilyén, Su, Low and Wiebe (STOC 2019).

arXiv:1910.05699•Leibniz international proceedings in informatics•Oct 13, 2019•14 citations
We present a method to exponentiate nonsparse indefinite low-rank matrices on a quantum computer. Given access to the elements of the matrix, our method allows one to determine the singular values and their associated singular vectors in time exponentially faster in the dimension of the matrix than known classical algorithms. The method extends to non-Hermitian and nonsquare matrices via matrix embedding. Moreover, our method preserves the phase relations between the singular spaces allowing for efficient algorithms that require operating on the entire singular-value decomposition of a matrix. As an example of such an algorithm, we discuss the Procrustes problem of finding a closest isometry to a given matrix.
With the significant advancement in quantum computation during the past couple of decades, the exploration of machine-learning subroutines using quantum strategies has become increasingly popular. Gaussian process regression is a widely used technique in supervised classical machine learning. Here we introduce an algorithm for Gaussian process regression using continuous-variable quantum systems that can be realized with technology based on photonic quantum computers under certain assumptions regarding distribution of data and availability of efficient quantum access. Our algorithm shows that by using a continuous-variable quantum computer a dramatic speedup in computing Gaussian process regression can be achieved, i.e., the possibility of exponentially reducing the time to compute. Furthermore, our results also include a continuous-variable quantum-assisted singular value decomposition method of nonsparse low rank matrices and forms an important subroutine in our Gaussian process regression algorithm.
The polar decomposition for a matrix AAA is A=UBA=UBA=UB, where BBB is a positive Hermitian matrix and UUU is unitary (or, if AAA is not square, an isometry). This paper shows that the ability to apply a Hamiltonian $\pmatrix{ 0 & A^\dagger \cr A & 0 \cr} $ translates into the ability to perform the transformations e−iBte^{-iBt}e−iBt and UUU in a deterministic fashion. We show how to use the quantum polar decomposition algorithm to solve the quantum Procrustes problem, to perform pretty good measurements, to find the positive Hamiltonian closest to any Hamiltonian, and to perform a Hamiltonian version of the quantum singular value transformation.
We present two efficient classical analogues of the quantum matrix inversion algorithm [16] for low-rank matrices. Inspired by recent work of Tang [27], assuming length-square sampling access to input data, we implement the pseudoinverse of a low-rank matrix allowing us to sample from the solution to the problem Ax = b using fast sampling techniques. We construct implicit descriptions of the pseudo-inverse by finding approximate singular value decomposition of A via subsampling, then inverting the singular values. In principle, our approaches can also be used to apply any desired “smooth” function to the singular values. Since many quantum algorithms can be expressed as a singular value transformation problem [15], our results indicate that more low-rank quantum algorithms can be effectively “dequantised” into classical length-square sampling algorithms.
We show that quantum computers improve on the best known classical algorithms for matrix inversion (and singular value decomposition) as far as space is concerned. This adds to the (still short) list of important problems where quantum computers are of help. Specifically, we show that the inverse of a well conditioned matrix can be approximated in quantum logspace with intermediate measurements. This should be compared with the best known classical algorithm for the problem that requires Ω(log2 n) space. We also show how to approximate the spectrum of a normal matrix, or the singular values of an arbitrary matrix, with ε additive accuracy, and how to approximate the singular value decomposition (SVD) of a matrix whose singular values are well separated.
A recent breakthrough by Tang (STOC 2019) showed how to "dequantize" the quantum algorithm for recommendation systems by Kerenidis and Prakash (ITCS 2017). The resulting algorithm, classical but "quantum-inspired", efficiently computes a low-rank approximation of the users' preference matrix. Subsequent works have shown how to construct efficient quantum-inspired algorithms for approximating the pseudo-inverse of a low-rank matrix as well, which can be used to (approximately) solve low-rank linear systems of equations. In the present paper, we pursue this line of research and develop quantum-inspired algorithms for a large class of matrix transformations that are defined via the singular value decomposition of the matrix. In particular, we obtain classical algorithms with complexity polynomially related (in most parameters) to the complexity of the best quantum algorithms for singular value transformation recently developed by Chakraborty, Gilyén and Jeffery (ICALP 2019) and Gilyén, Su, Low and Wiebe (STOC 2019).