{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,16]],"date-time":"2026-10-16T13:22:01Z","timestamp":1792156921143,"version":"4.4.0"},"publisher-location":"New York, NY, USA","reference-count":51,"publisher":"ACM","license":[{"start":{"date-parts":[[2018,6,20]],"date-time":"2018-06-20T00:00:00Z","timestamp":1529452800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2018,6,20]]},"DOI":"10.1145\/3188745.3188802","type":"proceedings-article","created":{"date-parts":[[2018,6,20]],"date-time":"2018-06-20T20:15:46Z","timestamp":1529525746000},"page":"325-338","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":169,"title":["Shadow tomography of quantum states"],"prefix":"10.1145","author":[{"given":"Scott","family":"Aaronson","sequence":"first","affiliation":[{"name":"University of Texas at Austin, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,6,20]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"crossref","unstructured":"S. Aaronson. 2005.  S. Aaronson. 2005.","DOI":"10.1126\/stke.2722005tr6"},{"key":"e_1_3_2_2_2_1","volume-title":"Theory of Computing 1","year":"2005"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"crossref","unstructured":"S. Aaronson. 2005.  S. Aaronson. 2005.","DOI":"10.1126\/stke.2722005tr6"},{"key":"e_1_3_2_2_4_1","volume-title":"Proc. Roy. Soc. London A461, 2063","year":"2005"},{"key":"e_1_3_2_2_5_1","unstructured":"S. Aaronson. 2006.  S. Aaronson. 2006."},{"key":"e_1_3_2_2_6_1","volume-title":"Proc. Conference on Computational Complexity. 261\u2013273"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.2007.0113"},{"key":"e_1_3_2_2_8_1","unstructured":"quant-ph\/0608142.  quant-ph\/0608142."},{"key":"e_1_3_2_2_9_1","unstructured":"S. Aaronson. 2009.  S. Aaronson. 2009."},{"key":"e_1_3_2_2_10_1","volume-title":"Proc. Conference on Computational Complexity. 229\u2013242"},{"key":"e_1_3_2_2_11_1","unstructured":"S. Aaronson. 2016.  S. Aaronson. 2016."},{"key":"e_1_3_2_2_12_1","volume-title":"Lecture Notes for the 28th McGill Invitational Workshop on Computational Complexity, Holetown, Barbados. With guest lectures by A. Bouland and L. Schaeffer. www.scottaaronson.com\/barbados-2016"},{"key":"e_1_3_2_2_13_1","unstructured":"S. Aaronson X. Chen E. Hazan and A. Nayak. 2018. Online learning of quantum states. (2018).  S. Aaronson X. Chen E. Hazan and A. Nayak. 2018. Online learning of quantum states. (2018)."},{"key":"e_1_3_2_2_14_1","unstructured":"arXiv:1802.09025.  arXiv:1802.09025."},{"key":"e_1_3_2_2_15_1","unstructured":"S. Aaronson and P. Christiano. 2013.  S. Aaronson and P. Christiano. 2013."},{"key":"e_1_3_2_2_16_1","volume-title":"Theory of Computing 9","year":"2013"},{"key":"e_1_3_2_2_17_1","unstructured":"arXiv:1203.4740.  arXiv:1203.4740."},{"key":"e_1_3_2_2_18_1","unstructured":"S. Aaronson and A. Drucker. 2014.  S. Aaronson and A. Drucker. 2014."},{"key":"e_1_3_2_2_19_1","volume-title":"1131\u20131183. Earlier version in STOC\u20192010","author":"Comput A","year":"2014"},{"key":"e_1_3_2_2_20_1","unstructured":"arXiv:1004.0377.  arXiv:1004.0377."},{"key":"e_1_3_2_2_21_1","unstructured":"S. Aaronson and G. Kuperberg. 2007.  S. Aaronson and G. Kuperberg. 2007."},{"key":"e_1_3_2_2_22_1","volume-title":"Theory of Computing 3, 7","year":"2007"},{"key":"e_1_3_2_2_23_1","unstructured":"arXiv:quant-ph\/0604056.  arXiv:quant-ph\/0604056."},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/581771.581773"},{"key":"e_1_3_2_2_25_1","volume-title":"Proceedings of CRYPTO. Plenum Press, 267\u2013275","author":"Bennett C. H."},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"crossref","unstructured":"F. Brand\u00e3o A. Kalev T. Li C. Lin K. Svore and X. Wu. 2017. Exponential quantum speed-ups for semidefinite programming with applications to quantum learning. (2017).  F. Brand\u00e3o A. Kalev T. Li C. Lin K. Svore and X. Wu. 2017. Exponential quantum speed-ups for semidefinite programming with applications to quantum learning. (2017).","DOI":"10.1109\/FOCS.2017.45"},{"key":"e_1_3_2_2_27_1","unstructured":"arXiv:1710.02581.  arXiv:1710.02581."},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2004.01.024"},{"key":"e_1_3_2_2_29_1","unstructured":"E. Farhi D. Gosset A. Hassidim A. Lutomirski D. Nagaj and P. Shor. 2010.  E. Farhi D. Gosset A. Hassidim A. Lutomirski D. Nagaj and P. Shor. 2010."},{"key":"e_1_3_2_2_30_1","unstructured":"Quantum state restoration and single-copy tomography. Phys. Rev. Lett. 105 190503 (2010).  Quantum state restoration and single-copy tomography. Phys. Rev. Lett. 105 190503 (2010)."},{"key":"e_1_3_2_2_31_1","unstructured":"arXiv:0912.3823.  arXiv:0912.3823."},{"key":"e_1_3_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.105.150401"},{"key":"e_1_3_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897585"},{"key":"e_1_3_2_2_34_1","volume-title":"Proc. ACM-SIAM Symp. on Discrete Algorithms (SODA). 1598\u20131611","author":"Harrow A."},{"key":"e_1_3_2_2_35_1","unstructured":"arXiv:1607.03236.  arXiv:1607.03236."},{"key":"e_1_3_2_2_36_1","first-page":"177","article-title":"Some estimates of the information transmitted by quantum communication channels","volume":"9","author":"Holevo A. S.","year":"1973","journal-title":"Problems of Information Transmission"},{"key":"e_1_3_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-005-0194-x"},{"key":"e_1_3_2_2_38_1","doi-asserted-by":"crossref","unstructured":"A. Molina T. Vidick and J. Watrous. 2012. Optimal counterfeiting attacks and generalizations for Wiesner\u2019s quantum money. In Theory of Quantum Computation Communication and Cryptography. 45\u201364. arXiv:1202.4010.  A. Molina T. Vidick and J. Watrous. 2012. Optimal counterfeiting attacks and generalizations for Wiesner\u2019s quantum money. In Theory of Quantum Computation Communication and Cryptography. 45\u201364. arXiv:1202.4010.","DOI":"10.1007\/978-3-642-35656-8_4"},{"key":"e_1_3_2_2_39_1","unstructured":"A. Montanaro. 2017.  A. Montanaro. 2017."},{"key":"e_1_3_2_2_40_1","unstructured":"Learning stabilizer states by Bell sampling. (2017).  Learning stabilizer states by Bell sampling. (2017)."},{"key":"e_1_3_2_2_41_1","unstructured":"arXiv:1707.04012.  arXiv:1707.04012."},{"key":"e_1_3_2_2_42_1","unstructured":"STOC\u201918 June 25\u201329 2018 Los Angeles CA USA Scott Aaronson  STOC\u201918 June 25\u201329 2018 Los Angeles CA USA Scott Aaronson"},{"key":"e_1_3_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2004.02.005"},{"key":"e_1_3_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897544"},{"key":"e_1_3_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.119.180511"},{"key":"e_1_3_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1968.1972"},{"key":"e_1_3_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1008908.1008920"},{"key":"e_1_3_2_2_48_1","unstructured":"M. Wilde. 2013.  M. Wilde. 2013."},{"key":"e_1_3_2_2_49_1","volume-title":"Proc. Roy. Soc. London A469","year":"2013"},{"key":"e_1_3_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.796385"},{"key":"e_1_3_2_2_51_1","unstructured":"Abstract 1 Introduction 1.1 Our Result 1.2 Techniques 1.3 Comparison with Related Work 2 Motivation 3 Preliminaries 4 Gentle Search Procedure 5 Main Result 6 Lower Bound 7 Open Problems References  Abstract 1 Introduction 1.1 Our Result 1.2 Techniques 1.3 Comparison with Related Work 2 Motivation 3 Preliminaries 4 Gentle Search Procedure 5 Main Result 6 Lower Bound 7 Open Problems References"}],"event":{"name":"STOC '18: Symposium on Theory of Computing","location":"Los Angeles CA USA","acronym":"STOC '18","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3188745.3188802","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3188745.3188802","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:07:09Z","timestamp":1750212429000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3188745.3188802"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,20]]},"references-count":51,"alternative-id":["10.1145\/3188745.3188802","10.1145\/3188745"],"URL":"https:\/\/doi.org\/10.1145\/3188745.3188802","relation":{},"subject":[],"published":{"date-parts":[[2018,6,20]]},"assertion":[{"value":"2018-06-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}