{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:57:44Z","timestamp":1781031464228,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":27,"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.3800896","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"1901-1912","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["On the Need for (Quantum) Memory with Short Outputs"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0006-7381-6280","authenticated-orcid":false,"given":"Zihan","family":"Hao","sequence":"first","affiliation":[{"name":"University of California at San Diego, La Jolla, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-4191-8809","authenticated-orcid":false,"given":"Zikuan","family":"Huang","sequence":"additional","affiliation":[{"name":"Tsinghua University, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3994-7061","authenticated-orcid":false,"given":"Qipeng","family":"Liu","sequence":"additional","affiliation":[{"name":"University of California at San Diego, La Jolla, 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","unstructured":"Scott Aaronson. 2021. Open Problems Related to Quantum Query Complexity. doi:10.1145\/3488559 10.1145\/3488559","DOI":"10.1145\/3488559"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649700"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-22318-1_3"},{"key":"e_1_3_2_1_4_1","volume-title":"International Symposium on Algorithms and Computation. Springer, 209-220","author":"Borodin Allan","year":"1993","unstructured":"Allan Borodin. 1993. Time space tradeofs (getting closer to the barrier?). In International Symposium on Algorithms and Computation. Springer, 209-220."},{"key":"e_1_3_2_1_5_1","unstructured":"John Bostanci Jonas Haferkamp Chinmay Nirkhe and Mark Zhandry. 2025. Separating QMA from QCMA with a classical oracle. arXiv preprint arXiv:2511.09551 ( 2025 )."},{"key":"e_1_3_2_1_6_1","unstructured":"John Bostanci Andrew Huang and Vinod Vaikuntanathan. 2026. Separating Quantum and Classical Advice with Good Codes. arXiv preprint arXiv:2602.09385 ( 2026 )."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/261342.261346"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649704"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00068"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/SWAT.1966.30"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-45721-1_15"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1101821.1101822"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.92.052331"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237866"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-90459-3_7"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589986"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","unstructured":"J. L. W. V. Jensen. 1906. Sur les fonctions convexes et les in\u00e9galit\u00e9s entre les valeurs moyennes. Acta Mathematica 30 none ( 1906 ) 175-193. doi: 10.1007\/BF02418571 10.1007\/BF02418571","DOI":"10.1007\/BF02418571"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1098\/rspa"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/05063235X"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3717823.3718296"},{"key":"e_1_3_2_1_21_1","unstructured":"Qipeng Liu. 2022. Non-uniformity and Quantum Advice in the Quantum Random Oracle Model. arXiv: 2210.06693 [quant-ph] https:\/\/arxiv.org\/abs\/2210.06693"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585129"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-17659-4_7"},{"key":"e_1_3_2_1_24_1","unstructured":"Aran Nayebi Scott Aaronson Aleksandrs Belovs and Luca Trevisan. 2014. Quantum lower bound for inverting a permutation with advice. CoRR abs\/1408.3193 ( 2014 ). arXiv: 1408.3193 http:\/\/arxiv.org\/abs\/1408.3193"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977066.25"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","unstructured":"John M Pollard. 1978. Monte Carlo methods for index computation. Mathematics of computation 32 143 ( 1978 ) 918-924. doi: 10.2307\/2006496 10.2307\/2006496","DOI":"10.2307\/2006496"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-26951-7_9"}],"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.3800896","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:02:07Z","timestamp":1781028127000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800896"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":27,"alternative-id":["10.1145\/3798129.3800896","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800896","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"}}]}}