  We introduce the problem of *shadow tomography*: given an unknown
$D$-dimensional quantum mixed state $\rho$, as well as known two-outcome
measurements $E_{1},\ldots,E_{M}$, estimate the probability that $E_{i}$
accepts $\rho$, to within additive error $\varepsilon$, for each of the $M$
measurements. How many copies of $\rho$ are needed to achieve this, with high
probability? Surprisingly, we give a procedure that solves the problem by
measuring only $\widetilde{O}\left( \varepsilon^{-4}\cdot\log^{4} M\cdot\log
D\right)$ copies. This means, for example, that we can learn the behavior of an
arbitrary $n$-qubit state, on all accepting/rejecting circuits of some fixed
polynomial size, by measuring only $n^{O\left( 1\right)}$ copies of the state.
This resolves an open problem of the author, which arose from his work on
private-key quantum money schemes, but which also has applications to quantum
copy-protected software, quantum advice, and quantum one-way communication.
Recently, building on this work, Brand\~ao et al. have given a different
approach to shadow tomography using semidefinite programming, which achieves a
savings in computation time.
