ECCC-Report TR17-164https://eccc.weizmann.ac.il/report/2017/164Comments and Revisions published for TR17-164en-usFri, 03 Nov 2017 10:38:46 +0200
Paper TR17-164
| Shadow Tomography of Quantum States |
Scott Aaronson
https://eccc.weizmann.ac.il/report/2017/164We 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^{-5}\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Ã£o et al. have given a different approach to shadow tomography using semidefinite programming, which achieves a savings in computation time.Fri, 03 Nov 2017 10:38:46 +0200https://eccc.weizmann.ac.il/report/2017/164