Heralded Polynomial-Time Quantum State Tomography

Steve Flammia, Perimeter Institute

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", and hence boring. But in part because of our current lack of meso-scale quantum computers capable of convincingly performing non-classical calculations, and the need to certify quantum state preparation, 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 heuristics for learning quantum states more efficiently, in some cases exponentially so. One such heuristic runs in polynomial time and outputs a polynomial-sized classical approximation of the state (in matrix product state form.) Another takes advantage of the fact that most interesting states are close to pure states to get an (essentially) quadratic speedup using ideas from compressed sensing. Both algorithms come with rigorous error bounds.

close this window