{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,23]],"date-time":"2026-07-23T00:25:36Z","timestamp":1784766336324,"version":"3.55.0"},"publisher-location":"New York, NY, USA","reference-count":70,"publisher":"ACM","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,15]]},"DOI":"10.1145\/3717823.3718191","type":"proceedings-article","created":{"date-parts":[[2025,6,15]],"date-time":"2025-06-15T23:34:42Z","timestamp":1750030482000},"page":"429-438","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Stabilizer Bootstrapping: A Recipe for Efficient Agnostic Tomography and Magic Estimation"],"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\/0000-0002-6599-8110","authenticated-orcid":false,"given":"Weiyuan","family":"Gong","sequence":"additional","affiliation":[{"name":"Harvard University, Cambridge, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-5606-8824","authenticated-orcid":false,"given":"Qi","family":"Ye","sequence":"additional","affiliation":[{"name":"Tsinghua University, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-6290-7691","authenticated-orcid":false,"given":"Zhihan","family":"Zhang","sequence":"additional","affiliation":[{"name":"Tsinghua University, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"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":"Quantum Pseudoentanglement. In 15th Innovations in Theoretical Computer Science Conference (ITCS","author":"Aaronson Scott","year":"2024","unstructured":"Scott Aaronson, Adam Bouland, Bill Fefferman, Soumik Ghosh, Umesh Vazirani, Chenyi Zhang, and Zixin Zhou. 2024. Quantum Pseudoentanglement. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). arxiv:2211.00747."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.70.052328"},{"key":"e_1_3_2_1_4_1","volume-title":"Identifying stabilizer states","author":"Aaronson Scott","unstructured":"Scott Aaronson and Daniel Gottesman. 2008. Identifying stabilizer states. Perimeter Institute Recorded Seminar Archive, https:\/\/pirsa.org\/08080052."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316378"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Anurag Anshu and Srinivasan Arunachalam. 2023. A survey on the complexity of learning quantum states. Nature Reviews Physics 1\u201311. arxiv:2305.20069.","DOI":"10.1038\/s42254-023-00662-4"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41567-021-01232-0"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-017-2973-z"},{"key":"e_1_3_2_1_9_1","unstructured":"Srinivasan Arunachalam Sergey Bravyi and Arkopal Dutt. 2024. A note on polynomial-time tolerant testing stabilizer states. arXiv:2410.22220 arxiv:2410.22220."},{"key":"e_1_3_2_1_10_1","unstructured":"Srinivasan Arunachalam and Arkopal Dutt. 2024. Tolerant testing stabilizer states. arXiv:2408.06289 arxiv:2408.06289."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451109"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316344"},{"key":"e_1_3_2_1_13_1","volume-title":"Allen Liu, Ryan O\u2019Donnell, and Ewin Tang.","author":"Bakshi Ainesh","year":"2024","unstructured":"Ainesh Bakshi, John Bostanci, William Kretschmer, Zeph Landau, jerry Li, Allen Liu, Ryan O\u2019Donnell, and Ewin Tang. 2024. Learning the closest product state. arXiv:2411.04283, arxiv:2411.04283."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649619"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/15\/12\/125020"},{"key":"e_1_3_2_1_16_1","volume-title":"Dax Enshan Koh, and Tobias Haug","author":"Bansal Nikhil","year":"2024","unstructured":"Nikhil Bansal, Wai-Keong Mok, Kishor Bharti, Dax Enshan Koh, and Tobias Haug. 2024. Pseudorandom density matrices. arXiv:2407.11607, arxiv:2407.11607."},{"key":"e_1_3_2_1_17_1","unstructured":"Zongbo Bao Philippe van Dordrecht and Jonas Helsen. 2024. Tolerant testing of stabilizer states with a polynomial gap via a generalized uncertainty relation. arXiv preprint arXiv:2410.21811."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1088\/2058-9565\/ab8963"},{"key":"e_1_3_2_1_19_1","volume-title":"Logical quantum processor based on reconfigurable atom arrays. Nature, 626, 7997","author":"Bluvstein Dolev","year":"2024","unstructured":"Dolev Bluvstein, Simon J Evered, Alexandra A Geim, Sophie H Li, Hengyun Zhou, Tom Manovitz, Sepehr Ebadi, Madelyn Cain, Marcin Kalinowski, and Dominik Hangleiter. 2024. Logical quantum processor based on reconfigurable atom arrays. Nature, 626, 7997 (2024), 58\u201365. arxiv:2312.03982."},{"key":"e_1_3_2_1_20_1","volume-title":"46th International Colloquium on Automata, Languages, and Programming (ICALP","author":"Brand\u00e3o Fernando GSL","year":"2019","unstructured":"Fernando GSL Brand\u00e3o, Amir Kalev, Tongyang Li, Cedric Yen-Yu Lin, Krysta M Svore, and Xiaodi Wu. 2019. Quantum SDP Solvers: Large Speed-Ups, Optimality, and Applications to Quantum Learning. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). arxiv:1710.02581."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.22331\/q-2019-09-02-181"},{"key":"e_1_3_2_1_22_1","volume-title":"Improved classical simulation of quantum circuits dominated by Clifford gates. Physical review letters, 116, 25","author":"Bravyi Sergey","year":"2016","unstructured":"Sergey Bravyi and David Gosset. 2016. Improved classical simulation of quantum circuits dominated by Clifford gates. Physical review letters, 116, 25 (2016), 250501. arxiv:1601.07601."},{"key":"e_1_3_2_1_23_1","article-title":"Trading classical and quantum computational resources","author":"Bravyi Sergey","year":"2016","unstructured":"Sergey Bravyi, Graeme Smith, and John A Smolin. 2016. Trading classical and quantum computational resources. Physical Review X, 6, 2 (2016), 021043. arxiv:1506.01396.","journal-title":"Physical Review"},{"key":"e_1_3_2_1_24_1","volume-title":"Optimal universal quantum cloning and state estimation. Physical review letters, 81, 12","author":"Bruss Dagmar","year":"1998","unstructured":"Dagmar Bruss, Artur Ekert, and Chiara Macchiavello. 1998. Optimal universal quantum cloning and state estimation. Physical review letters, 81, 12 (1998), 2598. arxiv:quant-ph\/9712019."},{"key":"e_1_3_2_1_25_1","volume-title":"Efficient classical simulation of Clifford circuits with nonstabilizer input states. Physical review letters, 123, 17","author":"Bu Kaifeng","year":"2019","unstructured":"Kaifeng Bu and Dax Enshan Koh. 2019. Efficient classical simulation of Clifford circuits with nonstabilizer input states. Physical review letters, 123, 17 (2019), 170502. arxiv:1902.11257."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00063"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS61266.2024.00072"},{"key":"e_1_3_2_1_28_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_29_1","doi-asserted-by":"publisher","DOI":"10.22331\/q-2024-02-12-1250"},{"key":"e_1_3_2_1_30_1","volume-title":"Efficient quantum state tomography. Nature communications, 1, 1","author":"Cramer Marcus","year":"2010","unstructured":"Marcus Cramer, Martin B Plenio, Steven T Flammia, Rolando Somma, David Gross, Stephen D Bartlett, Olivier Landon-Cardinal, David Poulin, and Yi-Kai Liu. 2010. Efficient quantum state tomography. Nature communications, 1, 1 (2010), 149. arxiv:1101.4366."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536498"},{"key":"e_1_3_2_1_32_1","volume-title":"International Conference on Machine Learning. 11598\u201311613","author":"Gong Weiyuan","year":"2023","unstructured":"Weiyuan Gong and Scott Aaronson. 2023. Learning distributions over quantum measurement outcomes. In International Conference on Machine Learning. 11598\u201311613. arxiv:2209.03007."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.57.127"},{"key":"e_1_3_2_1_34_1","unstructured":"Sabee Grewal Vishnu Iyer William Kretschmer and Daniel Liang. 2023. Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates. arXiv:2305.13409 arxiv:2305.13409. arxiv:2305.13409"},{"key":"e_1_3_2_1_35_1","unstructured":"Sabee Grewal Vishnu Iyer William Kretschmer and Daniel Liang. 2024. Agnostic Tomography of Stabilizer Product States. arXiv:2404.03813 arxiv:2404.03813."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649738"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-021-04118-7"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.132.210602"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897585"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"crossref","unstructured":"Jeongwan Haah Robin Kothari and Ewin Tang. 2024. Learning quantum Hamiltonians from high-temperature Gibbs states and real-time evolutions. Nature Physics 1\u20135.","DOI":"10.1038\/s41567-023-02376-x"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.133.020601"},{"key":"e_1_3_2_1_42_1","unstructured":"Tobias Haug Leandro Aolita and MS Kim. 2024. Probing quantum complexity via universal saturation of stabilizer entropies. arXiv:2406.04190 arxiv:2406.04190."},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1103\/PRXQuantum.4.010301"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.132.240602"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevB.107.035148"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.22331\/q-2023-08-28-1092"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.118.090501"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41567-020-0932-7"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.126.190505"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649722"},{"key":"e_1_3_2_1_51_1","volume-title":"Proceedings, Part III 38","author":"Ji Zhengfeng","year":"2018","unstructured":"Zhengfeng Ji, Yi-Kai Liu, and Fang Song. 2018. Pseudorandom quantum states. In Advances in Cryptology\u2013CRYPTO 2018: 38th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19\u201323, 2018, Proceedings, Part III 38. 126\u2013152."},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/130385.130424"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2022.3151760"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1038\/nphys3345"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"crossref","unstructured":"Lorenzo Leone and Lennart Bittel. 2024. Stabilizer entropies are monotones for magic-state resource theory. arXiv:2404.11652 arxiv:2404.11652.","DOI":"10.1103\/PhysRevA.110.L040403"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.128.050402"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.22331\/q-2024-05-27-1361"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.109.022429"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1103\/PRXQuantum.3.020333"},{"key":"e_1_3_2_1_60_1","unstructured":"Saeed Mehraban and Mehrdad Tahmasbi. 2024. Improved bounds for testing low stabilizer complexity states. arxiv:2410.24202. arxiv:2410.24202"},{"key":"e_1_3_2_1_61_1","unstructured":"Ashley Montanaro. 2017. Learning stabilizer states by Bell sampling. arXiv:1707.04012 arxiv:1707.04012."},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897544"},{"key":"e_1_3_2_1_63_1","volume-title":"Measuring magic on a quantum processor. npj Quantum Information, 8, 1","author":"Oliviero Salvatore FE","year":"2022","unstructured":"Salvatore FE Oliviero, Lorenzo Leone, Alioscia Hamma, and Seth Lloyd. 2022. Measuring magic on a quantum processor. npj Quantum Information, 8, 1 (2022), 148. arxiv:2204.00015."},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-27660-6_9"},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.22331\/q-2021-12-20-606"},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.99.062337"},{"key":"e_1_3_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.133.010601"},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.109.L040401"},{"key":"e_1_3_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/16\/1\/013009"},{"key":"e_1_3_2_1_70_1","volume-title":"Quantum Event Learning and Gentle Random Measurements. In 15th Innovations in Theoretical Computer Science Conference (ITCS","author":"Watts Adam Bene","year":"2024","unstructured":"Adam Bene Watts and John Bostanci. 2024. Quantum Event Learning and Gentle Random Measurements. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). arxiv:2210.09155."}],"event":{"name":"STOC '25: 57th Annual ACM Symposium on Theory of Computing","location":"Prague Czechia","acronym":"STOC '25","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"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.3718191","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T15:42:56Z","timestamp":1750693376000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3717823.3718191"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,15]]},"references-count":70,"alternative-id":["10.1145\/3717823.3718191","10.1145\/3717823"],"URL":"https:\/\/doi.org\/10.1145\/3717823.3718191","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"}}]}}