skip to content

Inverting well-conditioned matrices in Quantum Logspace

Wednesday 27th November 2013 - 13:30 to 14:30
INI Seminar Room 1
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.

The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.
Presentation Material: 
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons