{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:04:17Z","timestamp":1781028257021,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":68,"publisher":"ACM","license":[{"start":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T00:00:00Z","timestamp":1780963200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,6,9]]},"DOI":"10.1145\/3798129.3800900","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"1949-1959","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Learning Stabilizer Structure of Quantum States"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6014-6624","authenticated-orcid":false,"given":"Srinivasan","family":"Arunachalam","sequence":"first","affiliation":[{"name":"IBM Research, San Jose, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6942-2963","authenticated-orcid":false,"given":"Arkopal","family":"Dutt","sequence":"additional","affiliation":[{"name":"IBM Research, Cambridge, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,9]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/18M120275X"},{"key":"e_1_3_2_1_2_1","unstructured":"Scott Aaronson and Gottesman Daniel. 2009. Identifying stabilizer states. https:\/\/pirsa.org\/08080052"},{"key":"e_1_3_2_1_3_1","unstructured":"Jonathan Allcock Joao F Doriguello G\u00e1bor Ivanyos and Miklos Santha. 2024. Beyond Bell sampling: stabilizer state learning and quantum pseudorandomness lower bounds on qudits."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","unstructured":"Noga Alon Tali Kaufman Michael Krivelevich Simon Litsyn and Dana Ron. 2003. Testing Low-Degree Polynomials over GF(2(. In Approximation Randomization and Combinatorial Optimization: Algorithms and Techniques 6th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems APPROX 2003 and 7th International Workshop on Randomization and Approximation Techniques in Computer Science RANDOM 2003 Princeton NJ USA August 24-26 2003 Proceedings Sanjeev Arora Klaus Jansen Jos\u00e9 D. P. Rolim and Amit Sahai (Eds.) (Lecture Notes in Computer Science). Springer USA. 188\u2013199. https:\/\/doi.org\/10.1007\/978-3-540-45198-3_17 10.1007\/978-3-540-45198-3_17","DOI":"10.1007\/978-3-540-45198-3_17"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384234"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1038\/s42254-023-00662-4"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.TQC.2023.3"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2026.11"},{"key":"e_1_3_2_1_9_1","unstructured":"Srinivasan Arunachalam and Arkopal Dutt. 2025. Learning stabilizer structure of quantum states. [Full version]"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3717823.3718277"},{"key":"e_1_3_2_1_11_1","volume-title":"Operator quantum error-correcting subsystems for self-correcting quantum memories. Physical Review A\u2014Atomic, Molecular, and Optical Physics, 73, 1","author":"Bacon Dave","year":"2006","unstructured":"Dave Bacon. 2006. Operator quantum error-correcting subsystems for self-correcting quantum memories. Physical Review A\u2014Atomic, Molecular, and Optical Physics, 73, 1 (2006), 012340."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01212974"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3717823.3718201"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43948-7_79"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.54"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1103\/pzx6-nkfb"},{"key":"e_1_3_2_1_17_1","volume-title":"Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing (STOC \u201990)","author":"Blum M.","unstructured":"M. Blum, M. Luby, and R. Rubinfeld. 1990. Self-testing\/correcting with applications to numerical problems. In Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing (STOC \u201990). Association for Computing Machinery, USA. 73\u201383. isbn:0897913612"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.22331\/q-2019-09-02-181"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.111.200501"},{"key":"e_1_3_2_1_20_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.","journal-title":"Physical Review"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611978971.224"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.2515667122"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-025-05421-3"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3538391"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS61266.2024.00072"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3717823.3718191"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.26421\/QIC12.11-12-1"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451007"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.106.230501"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"crossref","unstructured":"Gregory A Freiman. 2006. What is the structure of K if K+K is small? 109\u2013134 pages.","DOI":"10.1007\/BFb0072977"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73010"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s000390050065"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-001-0332-9"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2025.201.2.5"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/pdp019"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1112\/S0025579311001264"},{"key":"e_1_3_2_1_37_1","volume-title":"Linear forms and quadratic uniformity for functions on Z_N. Journal d\u2019analyse math\u00e9matique, 115","author":"Timothy Gowers W","year":"2011","unstructured":"W Timothy Gowers and Julia Wolf. 2011. Linear forms and quadratic uniformity for functions on Z_N. Journal d\u2019analyse math\u00e9matique, 115 (2011), 121\u2013186."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"crossref","unstructured":"Ben Green. 2006. Montreal lecture notes on quadratic Fourier analysis.","DOI":"10.1090\/crmp\/043\/06"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0013091505000325"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"crossref","unstructured":"Ben Green and Terence Tao. 2008. The primes contain arbitrarily long arithmetic progressions. 481\u2013547 pages.","DOI":"10.4007\/annals.2008.167.481"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ITCS.2023.64"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649738"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.22331\/q-2025-11-06-1907"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-021-04118-7"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.133.020601"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000064"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.43"},{"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","unstructured":"Vishnu Iyer and Daniel Liang. 2024. Tolerant Testing of Stabilizer States with Mixed State Inputs."},{"key":"e_1_3_2_1_50_1","unstructured":"Amolak Ratan Kalra and Pulkit Sinha. 2025. Stabilizer Ranks Barnes Wall Lattices and Magic Monotones."},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1103\/PRXQuantum.6.010336"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2022.3151760"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.22331\/q-2024-05-27-1361"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.109.022429"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.4086\/TOC.GS.2015.006"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/3717823.3718228"},{"key":"e_1_3_2_1_57_1","unstructured":"Ashley Montanaro. 2017. Learning stabilizer states by Bell sampling."},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055500"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-28.1.104"},{"key":"e_1_3_2_1_60_1","first-page":"323","article-title":"An analog of Freiman\u2019s theorem in groups","volume":"258","author":"Ruzsa Imre","year":"1999","unstructured":"Imre Ruzsa. 1999. An analog of Freiman\u2019s theorem in groups. Ast\u00e9risque, 258, 199 (1999), 323\u2013326.","journal-title":"Ast\u00e9risque"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250864"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250832"},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1215\/S0012-7094-04-12915-X"},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"crossref","unstructured":"Terence Tao. 2007. The dichotomy between structure and randomness arithmetic progressions and the primes. 581\u2013608 pages.","DOI":"10.4171\/022-1\/22"},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.5555\/1333875.1334177"},{"key":"e_1_3_2_1_66_1","volume-title":"One","author":"Tran Viet T","unstructured":"Viet T Tran and Richard Kueng. 2025. One, Two, Three: One empirical evaluation of a two-copy shadow tomography scheme with triple efficiency."},{"key":"e_1_3_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1137\/12086827X"},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch47"}],"event":{"name":"STOC '26: 58th Annual ACM Symposium on Theory of Computing","location":"Salt Lake City UT USA","acronym":"STOC '26","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 58th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800900","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:54:13Z","timestamp":1781027653000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800900"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":68,"alternative-id":["10.1145\/3798129.3800900","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800900","relation":{},"subject":[],"published":{"date-parts":[[2026,6,9]]},"assertion":[{"value":"2026-06-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}