Fast algorithm for quantum polar decomposition, pretty-good measurements, and the Procrustes problem
arXiv:2106.07634
Abstract
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 comment16 pages (main); 11.5 pages (appendix)
References in corpus (13)
- Quantum algorithm for solving linear systems of equations
- Quantum principal component analysis
- Quantum Algorithms Revisited
- Quantum random access memory
- Hamiltonian simulation with nearly optimal dependence on all parameters
- Creating superpositions that correspond to efficiently integrable probability distributions
- A DCT Approximation for Image Compression
- Quantum singular value decomposition of non-sparse low-rank matrices
- Information-theoretic approach to quantum error correction and reversible measurement
- Hamiltonian Simulation with Optimal Sample Complexity
- Quantum algorithm for Petz recovery channels and pretty good measurements
- Robust and efficient multi-way spectral clustering
- Quantum polar decomposition algorithm