{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:04:49Z","timestamp":1781028289398,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":47,"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"}],"funder":[{"name":"National Key Research and Development Program of China","award":["2023YFA1009403"],"award-info":[{"award-number":["2023YFA1009403"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["12347104"],"award-info":[{"award-number":["12347104"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Royal Society University Research Fellowship","award":["URF\\R1\\211106"],"award-info":[{"award-number":["URF\\R1\\211106"]}]},{"name":"EPSRC","award":["EP\/Z534158\/1"],"award-info":[{"award-number":["EP\/Z534158\/1"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,6,9]]},"DOI":"10.1145\/3798129.3800783","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"675-686","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["A Meta-complexity Characterization of Minimal Quantum Cryptography"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0458-8767","authenticated-orcid":false,"given":"Bruno","family":"Cavalar","sequence":"first","affiliation":[{"name":"University of Oxford, Oxford, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-1043-0977","authenticated-orcid":false,"given":"Boyang","family":"Chen","sequence":"additional","affiliation":[{"name":"Tsinghua University, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6773-2711","authenticated-orcid":false,"given":"Andrea","family":"Coladangelo","sequence":"additional","affiliation":[{"name":"University of Washington, Seattle, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4065-0158","authenticated-orcid":false,"given":"Matthew","family":"Gray","sequence":"additional","affiliation":[{"name":"University of Oxford, Oxford, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-7005-9220","authenticated-orcid":false,"given":"Zihan","family":"Hu","sequence":"additional","affiliation":[{"name":"EPFL, Lausanne, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7659-3178","authenticated-orcid":false,"given":"Zhengfeng","family":"Ji","sequence":"additional","affiliation":[{"name":"Tsinghua University, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8058-7491","authenticated-orcid":false,"given":"Xingjian","family":"Li","sequence":"additional","affiliation":[{"name":"Tsinghua University, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,9]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"TR10-128","author":"Aaronson Scott","year":"2010","unstructured":"Scott Aaronson. The equivalence of sampling and searching. Electron. Colloquium Comput. Complex., TR10-128, 2010. URL: https:\/\/eccc.weizmann.ac.il\/report\/2010\/128, https:\/\/arxiv.org\/abs\/TR10-128 arXiv:TR10-128."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-78017-2_4"},{"key":"e_1_3_2_1_3_1","unstructured":"Scott Aaronson DeVon Ingram and William Kretschmer. The Acrobatics of BQP. Technical Report 164 2021."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-91098-2_1"},{"key":"e_1_3_2_1_5_1","volume-title":"On the computational hardness needed for quantum cryptography","author":"Brakerski Zvika","year":"2022","unstructured":"Zvika Brakerski, Ran Canetti, and Luowen Qian. On the computational hardness needed for quantum cryptography, 2022."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2013.2291780"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/focs61266.2024.00077"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-91098-2_2"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649603"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2000.856755"},{"key":"e_1_3_2_1_11_1","volume-title":"A meta-complexity characterization of minimal quantum cryptography. arXiv preprint arXiv:2510.07859","author":"Cavalar Bruno","year":"2025","unstructured":"Bruno Cavalar, Boyang Chen, Andrea Coladangelo, Matthew Gray, Zihan Hu, Zhengfeng Ji, and Xingjian Li. A meta-complexity characterization of minimal quantum cryptography. arXiv preprint arXiv:2510.07859, 2025."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-91098-2_5"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.22331\/Q-2025-03-27-1679"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-91098-2_4"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ITCS.2020.70"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-014-1990-4"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1976.1055638"},{"key":"e_1_3_2_1_18_1","unstructured":"Fr\u00e9d\u00e9ric Dupuis. The Decoupling Approach to Quantum Information Theory. PhD thesis Universit\u00e9 de Montr\u00e9al April 2010. https:\/\/arxiv.org\/abs\/1004.1641 arXiv:1004.1641."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/ccc.2001.933894"},{"key":"e_1_3_2_1_20_1","volume-title":"Countcrypt: Quantum cryptography between QCMA and PP. IACR Cryptol. ePrint Arch., page 1707","author":"Goldin Eli","year":"2024","unstructured":"Eli Goldin, Tomoyuki Morimae, Saachi Mutreja, and Takashi Yamakawa. Countcrypt: Quantum cryptography between QCMA and PP. IACR Cryptol. ePrint Arch., page 1707, 2024. URL: https:\/\/eprint.iacr.org\/2024\/1707."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(90)90010-U"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585138"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793244708"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-78017-2_5"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-032-01878-6_18"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS57990.2023.00033"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00047"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73009"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/SCT.1995.514853"},{"key":"e_1_3_2_1_30_1","volume-title":"TR21-082","author":"Ilango Rahul","year":"2021","unstructured":"Rahul Ilango, Hanlin Ren, and Rahul Santhanam. Hardness on any samplable distribution suffices: New characterizations of one-way functions by meta-complexity. Electron. Colloquium Comput. Complex., TR21-082, 2021. URL: https:\/\/eccc.weizmann.ac.il\/report\/2021\/082, https:\/\/arxiv.org\/abs\/TR21-082 arXiv:TR21-082."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-96878-0_5"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2212.00879"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","unstructured":"William Kretschmer. Quantum pseudorandomness and classical complexity. In Min-Hsiu Hsieh editor 16th Conference on the Theory of Quantum Computation Communication and Cryptography TQC 2021 July 5-8 2021 Virtual Conference volume 197 of LIPIcs pages 2:1\u20132:20. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik 2021. URL: https:\/\/doi.org\/10.4230\/LIPICS.TQC.2021.2 doi:10.4230\/LIPICS.TQC.2021.2. 10.4230\/LIPIcs.TQC.2021.2","DOI":"10.4230\/LIPICS.TQC.2021.2"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649654"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3717823.3718145"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579323"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649650"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00118"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-38545-2_21"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-032-01855-7_20"},{"key":"e_1_3_2_1_41_1","article-title":"Algorithmic complexity of quantum states","volume":"04","author":"Mora Caterina E.","year":"2004","unstructured":"Caterina E. Mora and Hans J. Briegel. Algorithmic complexity of quantum states. International Journal of Quantum Information 4.04, 2004.","journal-title":"International Journal of Quantum Information 4"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1142\/s0219749906002043"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060603"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/359340.359342"},{"key":"e_1_3_2_1_45_1","volume-title":"TR19-155","author":"Santhanam Rahul","year":"2019","unstructured":"Rahul Santhanam. Pseudorandomness and the minimum circuit size problem. Electron. Colloquium Comput. Complex., TR19-155, 2019. URL: https:\/\/eccc.weizmann.ac.il\/report\/2019\/155, https:\/\/arxiv.org\/abs\/TR19-155 arXiv:TR19-155."},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/MAHC.1984.10036"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2000.856757"}],"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.3800783","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:56:28Z","timestamp":1781027788000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800783"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":47,"alternative-id":["10.1145\/3798129.3800783","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800783","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"}}]}}