{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:56:52Z","timestamp":1781078212203,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":33,"publisher":"ACM","license":[{"start":{"date-parts":[[2024,6,10]],"date-time":"2024-06-10T00:00:00Z","timestamp":1717977600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"National Science Foundation","award":["Graduate Research Fellowship"],"award-info":[{"award-number":["Graduate Research Fellowship"]}]},{"name":"Hertz Foundation","award":["Hertz Fellowship"],"award-info":[{"award-number":["Hertz Fellowship"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2024,6,10]]},"DOI":"10.1145\/3618260.3649704","type":"proceedings-article","created":{"date-parts":[[2024,6,11]],"date-time":"2024-06-11T19:25:02Z","timestamp":1718133902000},"page":"1331-1342","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["An Optimal Tradeoff between Entanglement and Copy Complexity for State Tomography"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9450-3332","authenticated-orcid":false,"given":"Sitan","family":"Chen","sequence":"first","affiliation":[{"name":"Harvard University, Cambridge, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-5035-3728","authenticated-orcid":false,"given":"Jerry","family":"Li","sequence":"additional","affiliation":[{"name":"Microsoft Research, Redmond, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7987-5755","authenticated-orcid":false,"given":"Allen","family":"Liu","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,6,11]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Quantum algorithmic measurement. Nature communications, 13, 1","author":"Aharonov Dorit","year":"2022","unstructured":"Dorit Aharonov, Jordan Cotler, and Xiao-Liang Qi. 2022. Quantum algorithmic measurement. Nature communications, 13, 1 (2022), 1\u20139."},{"key":"e_1_3_2_1_2_1","volume-title":"Fernando GSL Brandao, and David A Buell","author":"Arute Frank","year":"2019","unstructured":"Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando GSL Brandao, and David A Buell. 2019. Quantum supremacy using a programmable superconducting processor. Nature, 574, 7779 (2019), 505\u2013510."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451109"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00070"},{"key":"e_1_3_2_1_5_1","unstructured":"Matthias C Caro. 2022. Learning quantum processes and Hamiltonians via the Pauli transfer matrix. arXiv preprint arXiv:2212.04471."},{"key":"e_1_3_2_1_6_1","unstructured":"Sitan Chen Jordan Cotler Hsin-Yuan Huang and Jerry Li. 2021. A hierarchy for replica quantum advantage. arXiv preprint arXiv:2111.05874."},{"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 and Weiyuan Gong. 2023. Futility and utility of a few ancillas for Pauli channel learning. arXiv preprint arXiv:2309.14326."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS57990.2023.00029"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00118"},{"key":"e_1_3_2_1_11_1","volume-title":"Proceedings of Thirty Fifth Conference on Learning Theory, Po-Ling Loh and Maxim Raginsky (Eds.) (Proceedings of Machine Learning Research","volume":"2596","author":"Chen Sitan","year":"2022","unstructured":"Sitan Chen, Jerry Li, and Ryan O\u2019Donnell. 2022. Toward Instance-Optimal State Certification With Incoherent Measurements. In Proceedings of Thirty Fifth Conference on Learning Theory, Po-Ling Loh and Maxim Raginsky (Eds.) (Proceedings of Machine Learning Research, Vol. 178). PMLR, 2541\u20132596. https:\/\/proceedings.mlr.press\/v178\/chen22b.html"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Senrui Chen Changhun Oh Sisi Zhou Hsin-Yuan Huang and Liang Jiang. 2023. Tight bounds on Pauli channel learning without entanglement. arxiv:2309.13461.","DOI":"10.1103\/PhysRevLett.132.180805"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.105.032435"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.78"},{"key":"e_1_3_2_1_15_1","volume-title":"Proceedings of Thirty Sixth Conference on Learning Theory, Gergely Neu and Lorenzo Rosasco (Eds.) (Proceedings of Machine Learning Research","volume":"1884","author":"Fawzi Omar","year":"2023","unstructured":"Omar Fawzi, Nicolas Flammarion, Aur\u00e9lien Garivier, and Aadil Oufkir. 2023. Quantum Channel Certification with Incoherent Measurements. In Proceedings of Thirty Sixth Conference on Learning Theory, Gergely Neu and Lorenzo Rosasco (Eds.) (Proceedings of Machine Learning Research, Vol. 195). PMLR, 1822\u20131884. https:\/\/proceedings.mlr.press\/v195\/fawzi23a.html"},{"key":"e_1_3_2_1_16_1","volume-title":"representations, and invariants. 255","author":"Goodman Roe","unstructured":"Roe Goodman and Nolan R Wallach. 2009. Symmetry, representations, and invariants. 255, Springer."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1088\/1751-8121\/ab8111"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897585"},{"key":"e_1_3_2_1_19_1","volume-title":"Quantum advantage in learning from experiments. Science, 376, 6598","author":"Huang Hsin-Yuan","year":"2022","unstructured":"Hsin-Yuan Huang, Michael Broughton, Jordan Cotler, Sitan Chen, Jerry Li, Masoud Mohseni, Hartmut Neven, Ryan Babbush, Richard Kueng, and John Preskill. 2022. Quantum advantage in learning from experiments. Science, 376, 6598 (2022), 1182\u20131186."},{"key":"e_1_3_2_1_20_1","volume-title":"Measuring entanglement entropy in a quantum many-body system. Nature, 528, 7580","author":"Islam Rajibul","year":"2015","unstructured":"Rajibul Islam, Ruichao Ma, Philipp M Preiss, M Eric Tai, Alexander Lukin, Matthew Rispoli, and Markus Greiner. 2015. Measuring entanglement entropy in a quantum many-body system. Nature, 528, 7580 (2015), 77\u201383."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129055X06002565"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1103\/physreva.64.052311"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.acha.2015.07.007"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.98.052334"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585129"},{"key":"e_1_3_2_1_26_1","unstructured":"Ashley Montanaro. 2017. Learning stabilizer states by Bell sampling. arxiv:1707.04012."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"crossref","unstructured":"Michael A Nielsen and Isaac Chuang. 2002. Quantum computation and quantum information.","DOI":"10.1119\/1.1463744"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746582"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897544"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055454"},{"key":"e_1_3_2_1_31_1","volume-title":"The surprising mathematics of longest increasing subsequences","author":"Romik Dan","unstructured":"Dan Romik. 2015. The surprising mathematics of longest increasing subsequences. Cambridge University Press."},{"key":"e_1_3_2_1_32_1","volume-title":"The symmetric group: representations, combinatorial algorithms, and symmetric functions. 203","author":"Sagan Bruce E","unstructured":"Bruce E Sagan. 2013. The symmetric group: representations, combinatorial algorithms, and symmetric functions. 203, Springer Science & Business Media."},{"key":"e_1_3_2_1_33_1","volume-title":"How to learn a quantum state. Ph. D. Dissertation","author":"Wright John","unstructured":"John Wright. 2016. How to learn a quantum state. Ph. D. Dissertation. Carnegie Mellon University."}],"event":{"name":"STOC '24: 56th Annual ACM Symposium on Theory of Computing","location":"Vancouver BC Canada","acronym":"STOC '24","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 56th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3618260.3649704","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3618260.3649704","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:03:52Z","timestamp":1750291432000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3618260.3649704"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,10]]},"references-count":33,"alternative-id":["10.1145\/3618260.3649704","10.1145\/3618260"],"URL":"https:\/\/doi.org\/10.1145\/3618260.3649704","relation":{},"subject":[],"published":{"date-parts":[[2024,6,10]]},"assertion":[{"value":"2024-06-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}