Everybody hates tomography. And with good reason! Experimentalists hate it because it is inefficient and difficult. Theorists hate it because it isn't very "quantum." But because of our current lack of meso-scale quantum computers capable of convincingly performing non-classical calculations, tomography seems like a necessary evil. In this talk, I will attempt to banish quantum state tomography to the Hell of Lost Paradigms where it belongs. I hope to achieve this by introducing several methods for learning quantum states more efficiently, in some cases exponentially so. The first method runs in polynomial time and outputs a polynomial-sized classical approximation of the state (in matrix product state form), together with a rigorous bound on the fidelity. The second result takes advantage of the fact that most interesting states are close to pure states to get a quadratic speedup using ideas from compressed sensing. I'll also show simulations of this second method that demonstrate how well it works in practical situations. Both of these results are heralded, and require no a priori assumptions about the state.
This is joint work with S. Bartlett, D. Gross, R. Somma (first result), and D. Gross, Y.-K. Liu, S. Becker, J. Eisert, (second result; arXiv:0909:3304).