{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,21]],"date-time":"2026-10-21T01:08:21Z","timestamp":1792544901789,"version":"4.5.0"},"reference-count":33,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","funder":[{"DOI":"10.13039\/100000005","name":"U.S. Department of Defense","doi-asserted-by":"publisher","award":["Vannevar Bush Fellowship"],"award-info":[{"award-number":["Vannevar Bush Fellowship"]}],"id":[{"id":"10.13039\/100000005","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000893","name":"Simons Foundation","doi-asserted-by":"publisher","award":["Simons Investigator Award"],"award-info":[{"award-number":["Simons Investigator Award"]}],"id":[{"id":"10.13039\/100000893","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000893","name":"Simons Foundation","doi-asserted-by":"publisher","award":["It from Qubit collaboration"],"award-info":[{"award-number":["It from Qubit collaboration"]}],"id":[{"id":"10.13039\/100000893","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2020,1]]},"abstract":"<jats:p>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(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, Branda\u0342o et al. have given a different approach to shadow tomography using semidefinite programming, which achieves a savings in computation time.<\/jats:p>","DOI":"10.1137\/18m120275x","type":"journal-article","created":{"date-parts":[[2020,6,30]],"date-time":"2020-06-30T14:29:34Z","timestamp":1593527374000},"page":"STOC18-368-STOC18-394","source":"Crossref","is-referenced-by-count":115,"title":["Shadow Tomography of Quantum States"],"prefix":"10.1137","volume":"49","author":[{"given":"Scott","family":"Aaronson","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2020,6,30]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2005.v001a001"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.2005.1546"},{"key":"atypb3","doi-asserted-by":"crossref","unstructured":"S. Aaronson,\n                      QMA\/qpoly $\\subseteq$ PSPACE\/poly: De-Merlinizing quantum protocols\n                      , in Proceedings of the 21st Annual IEEE Conference on Computational Complexity, 2006, pp. 261-273.","DOI":"10.1109\/CCC.2006.36"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.2007.0113"},{"key":"atypb5","first-page":"229","author":"Aaronson S.","year":"2009","journal-title":"Proc. Conference on Computational Complexity"},{"key":"atypb6","unstructured":"S. Aaronson,\n                      The complexity of quantum states and transformations: From quantum money to black holes\n                      , Lecture Notes for the 28th McGill Invitational Workshop on Computational Complexity, Holetown, Barbados, 2016, with guest lectures by A. Bouland and L. Schaeffer,http:\/\/www.scottaaronson.com\/barbados-2016.pdf."},{"key":"atypb7","first-page":"8962","author":"Aaronson S.","year":"2018","journal-title":"Curran Associates"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2013.v009a009"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1137\/110856939"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2007.v003a007"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1145\/581771.581773"},{"key":"atypb12","doi-asserted-by":"crossref","unstructured":"C. H. Bennett, G. Brassard, S. Breidbart, and S. Wiesner,\n                      Quantum cryptography, or unforgeable subway tokens\n                      , in Proceedings of CRYPTO, Plenum Press, 1982, pp. 267-275.","DOI":"10.1007\/978-1-4757-0602-4_26"},{"key":"atypb13","unstructured":"F. Branda\u0342o, A. Kalev, T. Li, C. Lin, K. Svore, and X. Wu,\n                      Exponential Quantum Speed-Ups for Semidefinite Programming with Applications to Quantum Learning\n                      , preprint,https:\/\/arxiv.org\/abs\/1710.02581v1, 2017."},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2004.01.024"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.105.190503"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1137\/070706550"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.105.150401"},{"key":"atypb18","first-page":"5628","volume":"63","author":"Haah J.","year":"2017","journal-title":"IEEE Trans. Inform. Theory"},{"key":"atypb19","doi-asserted-by":"crossref","unstructured":"A. Harrow, C. Lin, and A. Montanaro,\n                      Sequential measurements, disturbance and property testing\n                      , in Proc. 2017 ACM-SIAM Symp. on Discrete Algorithms (SODA), 2017, pp. 1598-1611,https:\/\/doi.org\/10.1137\/1.9781611974782.105.","DOI":"10.1137\/1.9781611974782.105"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-006-1535-6"},{"key":"atypb21","first-page":"177","volume":"9","author":"Holevo A. S.","year":"1973","journal-title":"Probl. Inform. Transmission"},{"key":"atypb22","first-page":"1066","author":"Kamath S.","year":"2015","journal-title":"ACM"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-005-0194-x"},{"key":"atypb24","first-page":"45","author":"Molina A.","year":"2012","journal-title":"Springer"},{"key":"atypb25","unstructured":"A. Montanaro,\n                      Learning Stabilizer States by Bell Sampling\n                      , preprint,https:\/\/arxiv.org\/abs\/1707.04012, 2017."},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2004.02.005"},{"key":"atypb27","first-page":"899","author":"O'Donnell R.","year":"2016","journal-title":"Proc. ACM STOC"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.119.180511"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1145\/1968.1972"},{"key":"atypb30","unstructured":"J. van Apeldoorn and A. Gily\u00e9n,\n                      Improvements in Quantum SDP-Solving with Applications\n                      , preprint,https:\/\/arxiv.org\/abs\/1804.05058, 2019."},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1145\/1008908.1008920"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.2013.0259"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1109\/18.796385"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/18M120275X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:02:32Z","timestamp":1787338952000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/18M120275X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1]]},"references-count":33,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["10.1137\/18M120275X"],"URL":"https:\/\/doi.org\/10.1137\/18m120275x","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,1]]}}}