The Learnability of Quantum States

Traditional quantum state estimation requires a number of measurements
that grows exponentially with the number of qubits n. But using ideas
from computational learning theory, I'll show that "for most practical
purposes" one can learn a quantum state using a number of measurements
that grows only linearly with n.  Besides possible implications for
experimental physics, this learning theorem has two applications to
quantum computing: first, a new simulation of quantum protocols, and
second, the use of trusted classical advice to verify untrusted
quantum advice.  No quantum computing background is required.

Paper: http://www.arxiv.org/abs/quant-ph/0608142