Inverting well-conditioned matrices in Quantum Logspace

Add to your list(s) Download to your calendar using vCal

• Ta-Shma, A (Tel Aviv University)
• Wednesday 27 November 2013, 15:00-16:00
• Seminar Room 1, Newton Institute.

If you have a question about this talk, please contact Mustapha Amrani.

This talk has been canceled/deleted

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

This talk is part of the Isaac Newton Institute Seminar Series series.

This talk is included in these lists:

This talk is not included in any other list

Note that ex-directory lists are not shown.