{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:10:04Z","timestamp":1750695004295,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":18,"publisher":"ACM","funder":[{"name":"NSERC","award":["RGPIN-2023-03731"],"award-info":[{"award-number":["RGPIN-2023-03731"]}]},{"name":"Institute for Quantum Computing, University of Waterloo","award":[""],"award-info":[{"award-number":[""]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,15]]},"DOI":"10.1145\/3717823.3718253","type":"proceedings-article","created":{"date-parts":[[2025,6,15]],"date-time":"2025-06-15T22:21:27Z","timestamp":1750026087000},"page":"1242-1253","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Dimension Independent and Computationally Efficient Shadow Tomography"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0002-9289-3776","authenticated-orcid":false,"given":"Pulkit","family":"Sinha","sequence":"first","affiliation":[{"name":"University of Waterloo, Waterloo, Canada"},{"name":"University of Waterloo, Waterloo, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188802"},{"key":"e_1_3_2_1_2_1","volume-title":"Advances in Neural Information Processing Systems","author":"Aaronson Scott","year":"2018","unstructured":"Scott Aaronson, Xinyi Chen, Elad Hazan, Satyen Kale, and Ashwin Nayak. 2018. Online Learning of Quantum States. In Advances in Neural Information Processing Systems, S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (Eds.). 31, Curran Associates, Inc.. https:\/\/proceedings.neurips.cc\/paper_files\/paper\/2018\/file\/c1a3d34711ab5d85335331ca0e57f067-Paper.pdf"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316378"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1038\/s42254-023-00662-4"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2019.27"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.46298\/theoretics.24.7"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00063"},{"key":"e_1_3_2_1_8_1","unstructured":"Sitan Chen Weiyuan Gong and Qi Ye. 2024. Optimal tradeoffs for estimating Pauli observables. arxiv:2404.19105. arxiv:2404.19105"},{"key":"e_1_3_2_1_9_1","unstructured":"Sitan Chen Jerry Li and Allen Liu. 2024. Optimal high-precision shadow estimation. arxiv:2407.13874. arxiv:2407.13874"},{"key":"e_1_3_2_1_10_1","unstructured":"Thomas G Draper. 2000. Addition on a quantum computer. arXiv preprint quant-ph\/0008033."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.22331\/q-2024-06-17-1373"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41567-020-0932-7"},{"key":"e_1_3_2_1_14_1","unstructured":"Jerry Huang Laura Lewis Hsin-Yuan Huang and John Preskill. 2024. Predicting adaptively chosen observables in quantum systems. arxiv:2410.15501. arxiv:2410.15501"},{"key":"e_1_3_2_1_15_1","unstructured":"Robbie King David Gosset Robin Kothari and Ryan Babbush. 2024. Triply efficient shadow tomography. arxiv:2404.19211. arxiv:2404.19211"},{"volume-title":"High-Dimensional Probability: An Introduction with Applications in Data Science","author":"Vershynin Roman","key":"e_1_3_2_1_16_1","unstructured":"Roman Vershynin. 2018. High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge University Press."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1017\/9781316848142"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2024.97"}],"event":{"name":"STOC '25: 57th Annual ACM Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Prague Czechia","acronym":"STOC '25"},"container-title":["Proceedings of the 57th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3717823.3718253","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T15:46:34Z","timestamp":1750693594000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3717823.3718253"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,15]]},"references-count":18,"alternative-id":["10.1145\/3717823.3718253","10.1145\/3717823"],"URL":"https:\/\/doi.org\/10.1145\/3717823.3718253","relation":{},"subject":[],"published":{"date-parts":[[2025,6,15]]},"assertion":[{"value":"2025-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}