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

Quantum polar decomposition algorithm

Seth Lloyd, Samuel Bosch, Giacomo De Palma, Bobak T. Kiani, Zi-Wen Liu, Milad Marvian, Patrick Rebentrost, David R. M. Arvidsson-Shukur

Published Jun 1, 2020• 23 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2006.00841

Related papers

Quantum singular-value decomposition of nonsparse low-rank matrices

Patrick Rebentrost, Adrian Steffens, Iman Marvian +1 more

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.

arXiv:1607.05404•Physical Review A•Jan 24, 2018•141 citations

Generalized Quantum Singular Value Transformation

Christoph Sünderhauf

The quantum singular value transformation has revolutionised quantum algorithms. By applying a polynomial to an arbitrary matrix, it provides a unifying picture of quantum algorithms. However, polynomials are restricted to definite parity and real coefficients, and finding the circuit (the phase factors) has proven difficult in practice. Recent work has removed these restrictions and enabled faster computation of phase factors, yet only for unitary matrices. Here we propose two generalisations. The generalised quantum singular value transformation allows complex polynomials for arbitrary matrices. For Hermitian matrices, we propose the generalised quantum eigenvalue transformation that even allows polynomials of indefinite parity. While we find that the polynomial might have to be downscaled compared to the quantum singular value transformation, the higher expressivity of polynomials and faster computation of phase factors can sometimes result in advantages. The results are achieved with various block encoding (or projected unitary encoding) techniques, including qubitisation, Hermitianisation, and multiplication. We show how to multiply block-encoded matrices with only one extra qubit, and introduce measure-early multiplication to further avoid the extra qubit and decrease average circuit length.

arXiv:2312.00723•Dec 1, 2023•39 citations

Efficient quantum algorithms for solving quantum linear system problems

Hefeng Wang, Hua Xiang

We transform the problem of solving linear system of equations $A\mathbf{x}=\mathbf{b}$ to a problem of finding the right singular vector with singular value zero of an augmented matrix $C$, and present two quantum algorithms for solving this problem. The first algorithm solves the problem directly by applying the quantum eigenstate filtering algorithm with query complexity of $O\left( sκ\log \left( 1/ε\right) \right) $ for a $s$-sparse matrix $C$, where $κ$ is the condition number of the matrix $A$, and $ε$ is the desired precision. The second algorithm uses the quantum resonant transition approach, the query complexity scales as $O\left[sκ+ \log\left( 1/ε\right)/\log \log \left( 1/ε\right) \right] $. Both algorithms meet the optimal query complexity in $κ$, and are simpler than previous algorithms.

arXiv:2208.06763•Aug 14, 2022•1 citation

Fast algorithm for quantum polar decomposition and applications

Yihui Quek, Patrick Rebentrost

The polar decomposition of a matrix is a key element in the quantum linear algebra toolbox. We show that the problem of quantum polar decomposition, recently studied in Lloyd et al. [arXiv:2006.00841], has a simple and concise implementation via the quantum singular value transform (QSVT). We focus on the applications to pretty-good measurements, a close-to-optimal measurement to distinguish quantum states, and the quantum Procrustes problem, the task of learning an optimal unitary mapping between given ``input'' and ``output'' quantum states. By transforming the state-preparation unitaries into a block-encoding, a prerequisite for QSVT, we develop algorithms for these problems whose gate complexity exhibits a polynomial advantage in the size and condition number of the input compared to alternative approaches for the same problem settings [Lloyd et al., arXiv:2006.00841; Gily\'en et al., arXiv:2006.16924]. For these applications of the polar decomposition, we also obtain an exponential speedup in precision compared to Lloyd et al. [arXiv:2006.00841], as the block-encodings remove the need for the costly density matrix exponentiation step. We contribute a rigorous analysis of the approach of Lloyd et al. [arXiv:2006.00841].

arXiv:2106.07634•Physical Review Research•Feb 22, 2022•8 citations

Quantum determinant estimation

J. Agerskov, K. Splittorff

A quantum algorithm for computing the determinant of a unitary matrix $U\in U(N)$ is given. The algorithm requires no preparation of eigenstates of $U$ and estimates the phase of the determinant to $t$ binary digits accuracy with $\mathcal{O}(N\log^2 N+t^2)$ operations and $tN$ controlled applications of $U^{2^m}$ with $m=0,\ldots,t-1$. For an orthogonal matrix $O\in O(N)$ the algorithm can determine with certainty the sign of the determinant using $\mathcal{O}(N\log^2 N)$ operations and $N$ controlled applications of $O$. An extension of the algorithm to contractions is discussed.

arXiv:2504.07497•Physical Review A•Jun 13, 2025•0 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
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 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.
The quantum singular value transformation has revolutionised quantum algorithms. By applying a polynomial to an arbitrary matrix, it provides a unifying picture of quantum algorithms. However, polynomials are restricted to definite parity and real coefficients, and finding the circuit (the phase factors) has proven difficult in practice. Recent work has removed these restrictions and enabled faster computation of phase factors, yet only for unitary matrices. Here we propose two generalisations. The generalised quantum singular value transformation allows complex polynomials for arbitrary matrices. For Hermitian matrices, we propose the generalised quantum eigenvalue transformation that even allows polynomials of indefinite parity. While we find that the polynomial might have to be downscaled compared to the quantum singular value transformation, the higher expressivity of polynomials and faster computation of phase factors can sometimes result in advantages. The results are achieved with various block encoding (or projected unitary encoding) techniques, including qubitisation, Hermitianisation, and multiplication. We show how to multiply block-encoded matrices with only one extra qubit, and introduce measure-early multiplication to further avoid the extra qubit and decrease average circuit length.
We transform the problem of solving linear system of equations Ax=bA\mathbf{x}=\mathbf{b}Ax=b to a problem of finding the right singular vector with singular value zero of an augmented matrix CCC, and present two quantum algorithms for solving this problem. The first algorithm solves the problem directly by applying the quantum eigenstate filtering algorithm with query complexity of $O\left( sκ\log \left( 1/ε\right) \right) $ for a sss-sparse matrix CCC, where κκκ is the condition number of the matrix AAA, and εεε is the desired precision. The second algorithm uses the quantum resonant transition approach, the query complexity scales as $O\left[sκ+ \log\left( 1/ε\right)/\log \log \left( 1/ε\right) \right] $. Both algorithms meet the optimal query complexity in κκκ, and are simpler than previous algorithms.
The polar decomposition of a matrix is a key element in the quantum linear algebra toolbox. We show that the problem of quantum polar decomposition, recently studied in Lloyd et al. [arXiv:2006.00841], has a simple and concise implementation via the quantum singular value transform (QSVT). We focus on the applications to pretty-good measurements, a close-to-optimal measurement to distinguish quantum states, and the quantum Procrustes problem, the task of learning an optimal unitary mapping between given ``input'' and ``output'' quantum states. By transforming the state-preparation unitaries into a block-encoding, a prerequisite for QSVT, we develop algorithms for these problems whose gate complexity exhibits a polynomial advantage in the size and condition number of the input compared to alternative approaches for the same problem settings [Lloyd et al., arXiv:2006.00841; Gily\'en et al., arXiv:2006.16924]. For these applications of the polar decomposition, we also obtain an exponential speedup in precision compared to Lloyd et al. [arXiv:2006.00841], as the block-encodings remove the need for the costly density matrix exponentiation step. We contribute a rigorous analysis of the approach of Lloyd et al. [arXiv:2006.00841].
A quantum algorithm for computing the determinant of a unitary matrix U∈U(N)U\in U(N)U∈U(N) is given. The algorithm requires no preparation of eigenstates of UUU and estimates the phase of the determinant to ttt binary digits accuracy with O(Nlog⁡2N+t2)\mathcal{O}(N\log^2 N+t^2)O(Nlog2N+t2) operations and tNtNtN controlled applications of U2mU^{2^m}U2m with m=0,…,t−1m=0,\ldots,t-1m=0,…,t−1. For an orthogonal matrix O∈O(N)O\in O(N)O∈O(N) the algorithm can determine with certainty the sign of the determinant using O(Nlog⁡2N)\mathcal{O}(N\log^2 N)O(Nlog2N) operations and NNN controlled applications of OOO. An extension of the algorithm to contractions is discussed.
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.