Scott Aaronson: Shadow Tomography – July 28, 2021

Shadow Tomography

Abstract:
Given an unknown quantum state rho, and a known list of two-outcome
measurements E_1,...,E_M, “shadow tomography” is the task of estimating the probability that each E_i accepts rho, by carefully measuring only a few copies of rho. In 2018, I gave the first nontrivial protocol for this task. In 2019, Guy Rothblum and I exploited a new connection between gentle measurement of quantum states and the field of differential privacy, to give a protocol that requires fewer copies of rho in some cases, and has the additional advantage of being online (that is, the measurements are processed one at a time). Huge challenges remain in making shadow tomography practical with near-term devices; extremely recently Huang, Kueng, and Preskill took some promising steps in that direction. I’ll survey
these developments and the challenges that remain.
Papers:
https://www.scottaaronson.com/papers/...
https://www.scottaaronson.com/papers/...
https://arxiv.org/abs/2002.08953

Bio:
Scott Aaronson is David J. Bruton Centennial Professor of Computer Science at the University of Texas at Austin. He received his bachelor’s from Cornell University and his PhD from UC Berkeley. Aaronson’s research in theoretical computer science has focused mainly on the capabilities and limits of quantum computers. His first book, Quantum Computing Since Democritus, was published in 2013 by Cambridge University Press. He received the National Science Foundation’s Alan T. Waterman Award, the United States PECASE Award, the Tomassoni-Chisesi Prize in Physics, and the ACM Prize in Computing.