Inverting well-conditioned matrices in Quantum Logspace
Seminar Room 1, Newton Institute
AbstractWe show that the inverse of a well conditioned matrix can be approximated in quantum logspace with intermediate measurements. To the best of our knowledge the best classical algorithm for the problem requires Omega(log^2n) 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 SVD decomposition of a matrix whose singular values are well separated.
The technique builds on ideas from several previous works, including simulating a Hamiltonian in small quantum space, treating a Hermitian matrix as a Hamiltonian and running the quantum phase estimation procedure on it (building on Harrow, Hassidim, and Lloyd) and making small space probabilistic (and quantum) computation consistent through the use of offline randomness and the shift and truncate method of Saks and Zhou.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.