{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,21]],"date-time":"2026-10-21T16:17:07Z","timestamp":1792599427434,"version":"4.5.0"},"reference-count":75,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA2","license":[{"start":{"date-parts":[[2022,10,31]],"date-time":"2022-10-31T00:00:00Z","timestamp":1667174400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2022,10,31]]},"abstract":"<jats:p>Emerging quantum algorithms for problems such as element distinctness, subset sum, and closest pair demonstrate computational advantages by relying on abstract data structures. Practically realizing such an algorithm as a program for a quantum computer requires an efficient implementation of the data structure whose operations correspond to unitary operators that manipulate quantum superpositions of data.<\/jats:p>\n                  <jats:p>To correctly operate in superposition, an implementation must satisfy three properties --- reversibility, history independence, and bounded-time execution. Standard implementations, such as the representation of an abstract set as a hash table, fail these properties, calling for tools to develop specialized implementations.<\/jats:p>\n                  <jats:p>In this work, we present Core Tower, the first language for quantum programming with random-access memory. Core Tower enables the developer to implement data structures as pointer-based, linked data. It features a reversible semantics enabling every valid program to be translated to a unitary quantum circuit.<\/jats:p>\n                  <jats:p>We present Boson, the first memory allocator that supports reversible, history-independent, and constant-time dynamic memory allocation in quantum superposition. \nWe also present Tower, a language for quantum programming with recursively defined data structures. Tower features a type system that bounds all recursion using classical parameters as is necessary for a program to execute on a quantum computer.<\/jats:p>\n                  <jats:p>Using Tower, we implement Ground, the first quantum library of data structures, including lists, stacks, queues, strings, and sets. We provide the first executable implementation of sets that satisfies all three mandated properties of reversibility, history independence, and bounded-time execution.<\/jats:p>","DOI":"10.1145\/3563297","type":"journal-article","created":{"date-parts":[[2022,10,31]],"date-time":"2022-10-31T16:23:35Z","timestamp":1667233415000},"page":"259-288","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":26,"title":["Tower: data structures in Quantum superposition"],"prefix":"10.1145","volume":"6","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4918-4467","authenticated-orcid":false,"given":"Charles","family":"Yuan","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6928-0456","authenticated-orcid":false,"given":"Michael","family":"Carbin","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,10,31]]},"reference":[{"key":"#cr-split#-e_1_2_2_1_1.1","unstructured":"Scott Aaronson. 2002. Quantum Lower Bound for Recursive Fourier Sampling. https:\/\/doi.org\/10.48550\/ARXIV.QUANT-PH\/0209060 arxiv:0209060. 10.48550\/ARXIV.QUANT-PH"},{"key":"#cr-split#-e_1_2_2_1_1.2","unstructured":"Scott Aaronson. 2002. Quantum Lower Bound for Recursive Fourier Sampling. https:\/\/doi.org\/10.48550\/ARXIV.QUANT-PH\/0209060 arxiv:0209060."},{"key":"e_1_2_2_2_1","unstructured":"Scott Aaronson Nai-Hui Chia Han-Hsuan Lin Chunhao Wang and Ruizhe Zhang. 2019. On the Quantum Complexity of Closest Pair and Related Problems. arxiv:1911.01973. \t\t\t\t  Scott Aaronson Nai-Hui Chia Han-Hsuan Lin Chunhao Wang and Ruizhe Zhang. 2019. On the Quantum Complexity of Closest Pair and Related Problems. arxiv:1911.01973."},{"key":"e_1_2_2_3_1","volume-title":"Qiskit: An Open-source Framework for Quantum Computing.","author":"Abraham H\u00e9ctor","year":"2019","unstructured":"H\u00e9ctor Abraham . 2019 . Qiskit: An Open-source Framework for Quantum Computing. H\u00e9ctor Abraham. 2019. Qiskit: An Open-source Framework for Quantum Computing."},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.79.2586"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2005.1"},{"key":"e_1_2_2_6_1","unstructured":"Andris Ambainis. 2003. Quantum walk algorithm for element distinctness. arxiv:0311001. \t\t\t\t  Andris Ambainis. 2003. Quantum walk algorithm for element distinctness. arxiv:0311001."},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/17\/12\/123010"},{"key":"e_1_2_2_8_1","doi-asserted-by":"crossref","unstructured":"Holger Bock Axelsen and Robert Gl\u00fcck. 2013. Reversible Representation and Manipulation of Constructor Terms in the Heap. In Reversible Computation Gerhard W. Dueck and D. Michael Miller (Eds.). \t\t\t\t  Holger Bock Axelsen and Robert Gl\u00fcck. 2013. Reversible Representation and Manipulation of Constructor Terms in the Heap. In Reversible Computation Gerhard W. Dueck and D. Michael Miller (Eds.).","DOI":"10.1007\/978-3-642-38986-3_9"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIFS.2015.2491309"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796302452"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysicsPhysiqueFizika.1.195"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1147\/rd.176.0525"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218053"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.05.025"},{"key":"e_1_2_2_15_1","doi-asserted-by":"crossref","unstructured":"Daniel J. Bernstein Stacey Jeffery Tanja Lange and Alexander Meurer. 2013. Quantum Algorithms for the Subset-Sum Problem. In Post-Quantum Cryptography. \t\t\t\t  Daniel J. Bernstein Stacey Jeffery Tanja Lange and Alexander Meurer. 2013. Quantum Algorithms for the Subset-Sum Problem. In Post-Quantum Cryptography.","DOI":"10.1007\/978-3-642-38616-9_2"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41534-018-0071-5"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3385412.3386007"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1328438.1328487"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.22331\/q-2021-09-28-550"},{"key":"e_1_2_2_20_1","volume-title":"Dagger Traced Symmetric Monoidal Categories and Reversible Programming. In Workshop on Reversible Computation.","author":"Bowman William","year":"2011","unstructured":"William Bowman , Roshan James , and Amr Sabry . 2011 . Dagger Traced Symmetric Monoidal Categories and Reversible Programming. In Workshop on Reversible Computation. William Bowman, Roshan James, and Amr Sabry. 2011. Dagger Traced Symmetric Monoidal Categories and Reversible Programming. In Workshop on Reversible Computation."},{"key":"e_1_2_2_21_1","unstructured":"Harry Buhrman Bruno Loff Subhasree Patro and Florian Speelman. 2021. Limits of quantum speed-ups for computational geometry and other problems: Fine-grained complexity via quantum walks. arxiv:2106.02005. \t\t\t\t  Harry Buhrman Bruno Loff Subhasree Patro and Florian Speelman. 2021. Limits of quantum speed-ups for computational geometry and other problems: Fine-grained complexity via quantum walks. arxiv:2106.02005."},{"key":"#cr-split#-e_1_2_2_22_1.1","unstructured":"Harry Buhrman Bruno Loff Subhasree Patro and Florian Speelman. 2022. Memory Compression with Quantum Random-Access Gates. https:\/\/doi.org\/10.48550\/ARXIV.2203.05599 arxiv:2203.05599. 10.48550\/ARXIV.2203.05599"},{"key":"#cr-split#-e_1_2_2_22_1.2","unstructured":"Harry Buhrman Bruno Loff Subhasree Patro and Florian Speelman. 2022. Memory Compression with Quantum Random-Access Gates. https:\/\/doi.org\/10.48550\/ARXIV.2203.05599 arxiv:2203.05599."},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICALP.2019.33"},{"key":"#cr-split#-e_1_2_2_24_1.1","unstructured":"Lijie Chen and Ramis Movassagh. 2021. Quantum Merkle Trees. https:\/\/doi.org\/10.48550\/ARXIV.2112.14317 arxiv:2112.14317. 10.48550\/ARXIV.2112.14317"},{"key":"#cr-split#-e_1_2_2_24_1.2","unstructured":"Lijie Chen and Ramis Movassagh. 2021. Quantum Merkle Trees. https:\/\/doi.org\/10.48550\/ARXIV.2112.14317 arxiv:2112.14317."},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1049\/el:20020949"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11128-019-2407-2"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1801723115"},{"key":"e_1_2_2_28_1","unstructured":"D. Coppersmith. 1994. An approximate Fourier transform useful in quantum factoring. \t\t\t\t  D. Coppersmith. 1994. An approximate Fourier transform useful in quantum factoring."},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISCA45697.2020.00054"},{"key":"e_1_2_2_30_1","unstructured":"Thomas G. Draper. 2000. Addition on a Quantum Computer. arxiv:quant-ph\/0008033. \t\t\t\t  Thomas G. Draper. 2000. Addition on a Quantum Computer. arxiv:quant-ph\/0008033."},{"key":"#cr-split#-e_1_2_2_31_1.1","unstructured":"Edward Farhi Jeffrey Goldstone and Sam Gutmann. 2014. A Quantum Approximate Optimization Algorithm. https:\/\/doi.org\/10.48550\/ARXIV.1411.4028 arxiv:1411.4028. 10.48550\/ARXIV.1411.4028"},{"key":"#cr-split#-e_1_2_2_31_1.2","unstructured":"Edward Farhi Jeffrey Goldstone and Sam Gutmann. 2014. A Quantum Approximate Optimization Algorithm. https:\/\/doi.org\/10.48550\/ARXIV.1411.4028 arxiv:1411.4028."},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01857727"},{"key":"#cr-split#-e_1_2_2_33_1.1","unstructured":"Craig Gidney. 2022. Quantum Dictionaries without QRAM. https:\/\/doi.org\/10.48550\/ARXIV.2204.13835 arxiv:2204.13835. 10.48550\/ARXIV.2204.13835"},{"key":"#cr-split#-e_1_2_2_33_1.2","unstructured":"Craig Gidney. 2022. Quantum Dictionaries without QRAM. https:\/\/doi.org\/10.48550\/ARXIV.2204.13835 arxiv:2204.13835."},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1103\/physrevlett.100.160501"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/233551.233553"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491956.2462177"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237866"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1103\/physrevlett.103.150502"},{"key":"e_1_2_2_39_1","volume-title":"Rocke","author":"Hartline Jason D.","year":"2002","unstructured":"Jason D. Hartline , Edwin S. Hong , Alexander E. Mohr , William R. Pentney , and Emily C . Rocke . 2002 . Characterizing History Independent Data Structures. In Algorithms and Computation, Prosenjit Bose and Pat Morin (Eds .). Jason D. Hartline, Edwin S. Hong, Alexander E. Mohr, William R. Pentney, and Emily C. Rocke. 2002. Characterizing History Independent Data Structures. In Algorithms and Computation, Prosenjit Bose and Pat Morin (Eds.)."},{"key":"#cr-split#-e_1_2_2_40_1.1","unstructured":"Tue Haulund. 2017. Design and Implementation of a Reversible Object-Oriented Programming Language. https:\/\/doi.org\/10.48550\/ARXIV.1707.07845 arxiv:1707.07845. 10.48550\/ARXIV.1707.07845"},{"key":"#cr-split#-e_1_2_2_40_1.2","unstructured":"Tue Haulund. 2017. Design and Implementation of a Reversible Object-Oriented Programming Language. https:\/\/doi.org\/10.48550\/ARXIV.1707.07845 arxiv:1707.07845."},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.3923\/itj.2009.208.213"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.106"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1146\/annurev-physchem-032210-103512"},{"key":"#cr-split#-e_1_2_2_44_1.1","unstructured":"Iordanis Kerenidis and Anupam Prakash. 2016. Quantum Recommendation Systems. https:\/\/doi.org\/10.48550\/ARXIV.1603.08675 arxiv:1603.08675. 10.48550\/ARXIV.1603.08675"},{"key":"#cr-split#-e_1_2_2_44_1.2","unstructured":"Iordanis Kerenidis and Anupam Prakash. 2016. Quantum Recommendation Systems. https:\/\/doi.org\/10.48550\/ARXIV.1603.08675 arxiv:1603.08675."},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.2172\/366453"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3428218"},{"key":"e_1_2_2_47_1","volume-title":"Introductory quantum mechanics","author":"Liboff Richard L.","unstructured":"Richard L. Liboff . 1980. Introductory quantum mechanics . Addison-Wesley . Richard L. Liboff. 1980. Introductory quantum mechanics. Addison-Wesley."},{"key":"e_1_2_2_48_1","unstructured":"Christopher Lutz. 1986. Janus: a time-reversible language. Letter to R. Landauer. \t\t\t\t  Christopher Lutz. 1986. Janus: a time-reversible language. Letter to R. Landauer."},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/tqe.2020.2965803"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/321479.321481"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380844"},{"key":"e_1_2_2_52_1","volume-title":"Chuang","author":"Nielsen Michael A.","year":"2010","unstructured":"Michael A. Nielsen and Isaac L . Chuang . 2010 . Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press . Michael A. Nielsen and Isaac L. Chuang. 2010. Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press."},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1103\/physreva.102.032608"},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/3453483.3454040"},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/3009837.3009894"},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-45231-5_29"},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129506005238"},{"key":"e_1_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/TQE.2021.3054623"},{"key":"e_1_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795293172"},{"key":"e_1_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183895.3183901"},{"key":"e_1_2_2_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897336.2897345"},{"key":"e_1_2_2_62_1","unstructured":"Carlin Vieri. 1995. Pendulum\u2013a reversible computer architecture. \t\t\t\t  Carlin Vieri. 1995. Pendulum\u2013a reversible computer architecture."},{"key":"e_1_2_2_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/2660267.2660314"},{"key":"e_1_2_2_64_1","volume-title":"Svore","author":"Wecker Dave","year":"2014","unstructured":"Dave Wecker , Krysta M. Svore , and Krysta M . Svore . 2014 . LIQUi|>: A Software Design Architecture and Domain-Specific Language for Quantum Computing . February. Dave Wecker, Krysta M. Svore, and Krysta M. Svore. 2014. LIQUi|>: A Software Design Architecture and Domain-Specific Language for Quantum Computing. February."},{"key":"e_1_2_2_65_1","volume-title":"Protocols for Secure Computations. In Symposium on Foundations of Computer Science. https:\/\/doi.org\/10","author":"Yao Andrew C.","year":"1982","unstructured":"Andrew C. Yao . 1982 . Protocols for Secure Computations. In Symposium on Foundations of Computer Science. https:\/\/doi.org\/10 .5555\/1382436.1382751 10.5555\/1382436.1382751 Andrew C. Yao. 1982. Protocols for Secure Computations. In Symposium on Foundations of Computer Science. https:\/\/doi.org\/10.5555\/1382436.1382751"},{"key":"e_1_2_2_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/1244381.1244404"},{"key":"e_1_2_2_67_1","doi-asserted-by":"publisher","DOI":"10.5281\/zenodo.6819031"},{"key":"e_1_2_2_68_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2013.40"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3563297","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3563297","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T12:38:10Z","timestamp":1750163890000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3563297"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,31]]},"references-count":75,"journal-issue":{"issue":"OOPSLA2","published-print":{"date-parts":[[2022,10,31]]}},"alternative-id":["10.1145\/3563297"],"URL":"https:\/\/doi.org\/10.1145\/3563297","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,10,31]]},"assertion":[{"value":"2022-10-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}