Shadow tomography of quantum states

By Scott Aaronson. Electron. Colloquium Comput. Complex., 2017

573 citations recorded by the source corpus.

We introduce the problem of *shadow tomography*: given an unknown D-dimensional quantum mixed state ρ, as well as known two-outcome measurements E1,…,EM, estimate the probability that Ei 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·log4 M·logD) 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 nO( 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.

View Paper: https://www.semanticscholar.org/paper/fdf430527f842faf28aa7765f6e711511286f31c

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Predicting many properties of a quantum system from very few measurements (2020, methodology): “The best existing result is due to Aaronson and Rothblum [3].”
The randomized measurement toolbox (2022, background): “8 Université Grenoble Alpes, CNRS, LPMMC, Grenoble, France. e-mail: peter.zoller@uibk.ac.at Fortunately, a far less complete description of the state is adequate for many purposes 18–20 , so that the number of experiments and the amount of classical processing needed can be greatly reduced.”
Quantum simulation of fundamental particles and forces (2023, background): “In general, access to the full final-state wavefunctions is not possible, but recently proposed techniques, such as classical shadows [111, 158–160], permits sampling of the density matrix and evaluation of observables with significant reductions in required resources.”