Source-linked AI summary
Quantum singular value decomposition of non-sparse low-rank matrices
Patrick Rebentrost, Adrian Steffens, Seth Lloyd
TL;DR
The paper uses an extended Hermitian matrix to encode the singular values and singular vectors of a matrix. Its eigenvectors preserve the correct phase relations between left and right singular vectors, while the appendix also characterizes the modified-swap construction and its error scaling.
Problem
A singular-value representation needs the correct phase relations between left and right singular vectors, not only their separate values and vectors.
Source: Appendix · p. 5Method
The paper defines an extended Hermitian matrix for a complex, not necessarily square matrix, whose eigenvalues encode its singular values.
Source: Appendix · p. 5Results
The extended matrix has eigenvalues ±σ_j for the singular values σ_j, with corresponding eigenvectors proportional to (u_j, ±v_j).
Source: Appendix · p. 5Takeaways & Limitations
The extended-matrix eigenvectors preserve the correct phase relations between paired left and right singular vectors.
Source: Appendix · p. 5
Abstract
from arXiv · showhide
In this work, we present a method to exponentiate non-sparse indefinite low-rank matrices on a quantum computer. Given an operation for accessing the elements of the matrix, our method allows singular values and associated singular vectors to be found quantum mechanically in a time exponentially faster in the dimension of the matrix than known classical algorithms. The method extends to non-Hermitian and non-square matrices via embedding matrices. In the context of the generic singular value decomposition of a matrix, we discuss the Procrustes problem of finding a closest isometry to a given matrix.
Appendix
The appendix relates matrix norms to the modified swap construction and its second-order error, then characterizes an extended Hermitian matrix that encodes singular values and phase-consistent singular vectors. It also describes how a low-rank partial isometry acts on its subspace.
Appendix
- The appendix defines ∥A∥max as the largest absolute matrix element and identifies the Frobenius norm as the Hilbert-Schmidt norm.It also identifies r as rank and σ_j as singular values.Source: Appendix · p. 4
- Setting the entries A_jk to 1 recovers the original swap matrix.The appendix gives the original swap operator as a sum over row and column indices.Source: Appendix · p. 5
- The modified swap matrix has eigenvalues drawn from the diagonal entries of A and ±A_jk for off-diagonal entries, so its largest absolute eigenvalue is ∥A∥max.Its square has eigenvalues |A_jk|^2 and maximal eigenvalue ∥A∥max^2.Source: Appendix · p. 5
- The second-order error of the method naturally scales with ∥A∥max^2.The appendix estimates the error from the second-order term in the time-step expansion.Source: Appendix · p. 5
- The extended matrix has nonzero eigenvalues ±σ_j and corresponding eigenvectors encode left and right singular vectors with the correct relative phases.For rank r, the extended matrix has rank 2r.Source: Appendix · p. 5
- For the low-rank partial isometry, W†W acts as identity on the low-rank subspace and projects out its orthogonal complement.The construction is considered for M > N with orthogonal columns in the full-rank Procrustes case.Source: Appendix · p. 5