  Traditional quantum state tomography requires a number of measurements that
grows exponentially with the number of qubits n. But using ideas from
computational learning theory, we show that "for most practical purposes" one
can learn a state using a number of measurements that grows only linearly with
n. Besides possible implications for experimental physics, our learning theorem
has two applications to quantum computing: first, a new simulation of quantum
one-way communication protocols, and second, the use of trusted classical
advice to verify untrusted quantum advice.
