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

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].

Physical Review Research•Feb 22, 2022•3 citations

Fast algorithm for quantum polar decomposition, pretty-good measurements, and the Procrustes problem

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. [LBP+20], 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 pre-requisite 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 [LBP+20, GLMQW20]. For these applications of the polar decomposition, we also obtain an exponential speedup in precision compared to [LBP+20], as the block-encodings remove the need for the costly density matrix exponentiation step. We contribute a rigorous analysis of the approach of [LBP+20].

arXiv:2106.07634•Jun 14, 2021•1 citation

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•135 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•1 citation

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

Quantum Eigenvalue Transformations for Arbitrary Matrices

Xabier Gutiérrez, Lorenzo Laneve, Mikel Sanz

Quantum Signal Processing (QSP) and Quantum Singular Value Transformation (QSVT) provide an efficient framework for implementing polynomials of block-encoded matrices, and thus offer a systematic approach to quantum algorithm design. However, despite a number of recent advances, important limitations remain. In particular, QSP can only transform unitary matrices, by applying a polynomial to their eigenvalues, while QSVT is a singular-value transformation and thus one can only obtain the polynomial of Hermitian matrices. As a consequence, these techniques do not directly apply to an arbitrary non-Hermitian matrix that is not diagonalizable. In this work, we propose a simple yet powerful method to extend these ideas to arbitrary square matrices by acting on their eigenvalues. To this end, we introduce the notion of an $n$-regular block encoding, namely, a block encoding whose $k$-th power reproduces the $k$-th power of the encoded matrix for every $0 < k < n$. We show that applying QSP to any unitary with this property is equivalent to applying a polynomial of degree at most $n$ to the block-encoded matrix, independently of its internal structure. Moreover, we provide a simple construction that transforms any block encoding into an $n$-regular one using only $O(\log n)$ ancillary qubits and operations. Finally, we show that this construction induces the desired transformation on the eigenvalues associated with the Jordan normal form of the matrix; for non-diagonalizable matrices this yields the full matrix function $P(A)$, whose action on each Jordan block involves the derivatives of $P$, and not merely the map $λ\mapsto P(λ)$.

quant-pharXiv:2604.19688•Apr 22, 2026•0 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.
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].
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. [LBP+20], 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 pre-requisite 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 [LBP+20, GLMQW20]. For these applications of the polar decomposition, we also obtain an exponential speedup in precision compared to [LBP+20], as the block-encodings remove the need for the costly density matrix exponentiation step. We contribute a rigorous analysis of the approach of [LBP+20].
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.
Quantum Signal Processing (QSP) and Quantum Singular Value Transformation (QSVT) provide an efficient framework for implementing polynomials of block-encoded matrices, and thus offer a systematic approach to quantum algorithm design. However, despite a number of recent advances, important limitations remain. In particular, QSP can only transform unitary matrices, by applying a polynomial to their eigenvalues, while QSVT is a singular-value transformation and thus one can only obtain the polynomial of Hermitian matrices. As a consequence, these techniques do not directly apply to an arbitrary non-Hermitian matrix that is not diagonalizable. In this work, we propose a simple yet powerful method to extend these ideas to arbitrary square matrices by acting on their eigenvalues. To this end, we introduce the notion of an nnn-regular block encoding, namely, a block encoding whose kkk-th power reproduces the kkk-th power of the encoded matrix for every 0<k<n0 < k < n0<k<n. We show that applying QSP to any unitary with this property is equivalent to applying a polynomial of degree at most nnn to the block-encoded matrix, independently of its internal structure. Moreover, we provide a simple construction that transforms any block encoding into an nnn-regular one using only O(log⁡n)O(\log n)O(logn) ancillary qubits and operations. Finally, we show that this construction induces the desired transformation on the eigenvalues associated with the Jordan normal form of the matrix; for non-diagonalizable matrices this yields the full matrix function P(A)P(A)P(A), whose action on each Jordan block involves the derivatives of PPP, and not merely the map λ↦P(λ)λ\mapsto P(λ)λ↦P(λ).