Shadow tomography of quantum states

We introduce the problem of *shadow tomography*: given an unknown D -dimensional quantum mixed state ρ, as well as known two-outcome measurements E 1 ,…, E M , estimate the probability that E i accepts ρ, to within additive error ε, for each of the M measurements. How many copies of ρ are needed to achieve this, with high probability? Surprisingly, we give a procedure that solves the problem by measuring only O ( ε −5 ·log 4 M ·log D ) 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 ( 1) 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ão et al. have given a different approach to shadow tomography using semidefinite programming, which achieves a savings in computation time.

Authors

• Scott Aaronson

Keywords

• information theory
• mixed state
• one-way communication
• postselection
• quantum advice
• quantum money