{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T00:49:07Z","timestamp":1773190147282,"version":"3.50.1"},"reference-count":102,"publisher":"Association for Computing Machinery (ACM)","issue":"PLDI","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2025,6,10]]},"abstract":"<jats:p>Quantum recursive programming has been recently introduced for describing sophisticated and complicated quantum algorithms in a compact and elegant way. However, implementation of quantum recursion involves intricate interplay between quantum control flow and recursive procedure calls. In this paper, we aim at resolving this fundamental challenge and develop a series of techniques to efficiently implement quantum recursive programs. Our main contributions include:<\/jats:p>\n          <jats:p>1. We propose a notion of quantum register machine, the first quantum architecture (including an instruction set) that provides instruction-level support for quantum control flow and recursive procedure calls at the same time.<\/jats:p>\n          <jats:p>2. Based on quantum register machine, we describe the first comprehensive implementation process of quantum recursive programs, including the compilation, the partial evaluation of quantum control flow, and the execution on the quantum register machine.<\/jats:p>\n          <jats:p>3. As a bonus, our efficient implementation of quantum recursive programs also offers automatic parallelisation of quantum algorithms. For implementing certain quantum algorithmic subroutine, like the widely used quantum multiplexor, we can even obtain exponential parallel speed-up (over the straightforward implementation) from this automatic parallelisation. This demonstrates that quantum recursive programming can be win-win for both modularity of programs and efficiency of their implementation.<\/jats:p>","DOI":"10.1145\/3729283","type":"journal-article","created":{"date-parts":[[2025,6,13]],"date-time":"2025-06-13T16:02:27Z","timestamp":1749830547000},"page":"822-847","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Quantum Register Machine: Efficient Implementation of Quantum Recursive Programs"],"prefix":"10.1145","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7436-0426","authenticated-orcid":false,"given":"Zhicheng","family":"Zhang","sequence":"first","affiliation":[{"name":"University of Technology Sydney, Sydney, Australia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4847-702X","authenticated-orcid":false,"given":"Mingsheng","family":"Ying","sequence":"additional","affiliation":[{"name":"University of Technology Sydney, Sydney, Australia"}]}],"member":"320","published-online":{"date-parts":[[2025,6,13]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2020.16"},{"key":"e_1_2_2_2_1","unstructured":"V. Aho Alfred S. Lam Monica Ravi Sethi and D. Ullman Jeffrey. 2007. Compilers: principles techniques & tools. Pearson Education."},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2005.1"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447311"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-63390-9_1"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41598-021-85474-1"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-19861-8_9"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74510-5_9"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/18\/3\/033032"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevX.8.041015"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevX.8.011044"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/367236.367262"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/366193.366201"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1984.715894"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1147\/rd.176.0525"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1272729.1272739"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38616-9_2"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167097"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.114.090502"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.54"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3385412.3386007"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.12.046"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-18073-6_4"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.4204\/EPTCS.195.3"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1087072"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.26421\/QIC12.11-12-1"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2000.892140"},{"key":"e_1_2_2_28_1","volume-title":"Gambetta","author":"Cross Andrew W.","year":"2017","unstructured":"Andrew W. Cross, Lev S. Bishop, John A. Smolin, and Jay M. Gambetta. 2017. Open quantum assembly language. arxiv:1707.03429."},{"key":"e_1_2_2_29_1","unstructured":"Raphael Dias da Silva Einar Pius and Elham Kashefi. 2013. Global quantum circuit optimization. arxiv:1301.0351."},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1219092.1219096"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3632901"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.1985.0070"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/bf01386232"},{"key":"e_1_2_2_34_1","unstructured":"Edsger W. Dijkstra. 1970. Notes on structured programming. http:\/\/www.cs.utexas.edu\/users\/EWD\/ewd02xx\/EWD249.PDF circulated privately"},{"key":"e_1_2_2_35_1","unstructured":"Edsger W. Dijkstra. 1979. Programming considered as a human activity. In Classics in software engineering. 1\u20139. https:\/\/www.cs.utexas.edu\/~EWD\/ewd01xx\/EWD117.PDF"},{"key":"e_1_2_2_36_1","volume-title":"Reversibility for efficient computing. Ph. D. Dissertation","author":"Frank Michael Patrick","unstructured":"Michael Patrick Frank. 1999. Reversibility for efficient computing. Ph. D. Dissertation. Massachusetts Institute of Technology."},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA.2019.00040"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.78.052310"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.100.160501"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.26421\/QIC2.1-3"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1103\/PRXQuantum.2.020311"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.123.250501"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3434318"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/366622.366644"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00976239"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2005.v001a005"},{"key":"e_1_2_2_47_1","volume-title":"Rattew","author":"Jaques Samuel","year":"2023","unstructured":"Samuel Jaques and Arthur G. Rattew. 2023. QRAM: A survey and critique. arxiv:2305.10310."},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.13"},{"key":"e_1_2_2_49_1","volume-title":"Partial evaluation and automatic program generation","author":"Jones Neil D.","unstructured":"Neil D. Jones, Carsten K. Gomard, and Peter Sestoft. 1993. Partial evaluation and automatic program generation. Prentice Hall."},{"key":"e_1_2_2_50_1","unstructured":"Richard Jozsa. 2005. An introduction to measurement based quantum computation. arxiv:quant-ph\/0508124."},{"key":"e_1_2_2_51_1","volume-title":"Efficient algorithms in quantum query complexity. Ph. D. Dissertation","author":"Kothari Robin","unstructured":"Robin Kothari. 2014. Efficient algorithms in quantum query complexity. Ph. D. Dissertation. University of Waterloo."},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1147\/rd.53.0183"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/3563309"},{"key":"e_1_2_2_54_1","unstructured":"Noah Linden and Sandu Popescu. 1998. The halting problem for quantum computers. arxiv:quant-ph\/9806054."},{"key":"e_1_2_2_55_1","unstructured":"Chenxu Liu Meng Wang Samuel A. Stein Yufei Ding and Ang Li. 2023. Quantum memory: a missing piece in quantum computing units. arxiv:2309.14432."},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.22331\/q-2024-06-17-1375"},{"key":"e_1_2_2_57_1","unstructured":"Guang Hao Low and Nathan Wiebe. 2019. Hamiltonian simulation in the interaction picture. arxiv:1805.00675."},{"key":"e_1_2_2_58_1","volume-title":"Janus: a time-reversible language. Letter to Rolf Landauer, 2","author":"Lutz Christopher","year":"1986","unstructured":"Christopher Lutz and Howard Derby. 1986. Janus: a time-reversible language. Letter to Rolf Landauer, 2 (1986)."},{"key":"e_1_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11080-005-0923-2"},{"key":"e_1_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799355053"},{"key":"e_1_2_2_61_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.78.1823"},{"key":"e_1_2_2_62_1","first-page":"589","article-title":"On the algorithmic complexity of discrete functions","volume":"7","author":"Ofman Yu","year":"1963","unstructured":"Yu Ofman. 1963. On the algorithmic complexity of discrete functions. In Sov. Math. Dokl.. 7, 589.","journal-title":"Sov. Math. Dokl.."},{"key":"e_1_2_2_63_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.80.631"},{"key":"e_1_2_2_64_1","doi-asserted-by":"publisher","DOI":"10.1007\/0-306-47097-7_32"},{"key":"e_1_2_2_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/3453483.3454040"},{"key":"e_1_2_2_66_1","doi-asserted-by":"publisher","DOI":"10.22331\/q-2024-02-19-1258"},{"key":"e_1_2_2_67_1","volume-title":"Automatic parallelisation of quantum circuits using the measurement based quantum computing model. Master\u2019s thesis","author":"Pius Einar","unstructured":"Einar Pius. 2010. Automatic parallelisation of quantum circuits using the measurement based quantum computing model. Master\u2019s thesis. University of Edinburgh."},{"key":"e_1_2_2_68_1","doi-asserted-by":"publisher","DOI":"10.4204\/eptcs.287.17"},{"key":"e_1_2_2_69_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.86.5188"},{"key":"e_1_2_2_70_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215017"},{"key":"e_1_2_2_71_1","unstructured":"Gregory Rosenthal. 2023. Query and depth upper bounds for quantum unitaries via Grover search. arxiv:2111.07992."},{"key":"e_1_2_2_72_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-89366-2_19"},{"key":"e_1_2_2_73_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129504004256"},{"key":"e_1_2_2_74_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2005.855930"},{"key":"e_1_2_2_75_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0375-9601(02)00015-4"},{"key":"e_1_2_2_76_1","volume-title":"Zeng","author":"Smith Robert S.","year":"2017","unstructured":"Robert S. Smith, Michael J. Curtis, and William J. Zeng. 2017. A practical quantum instruction set architecture. arxiv:1608.03355."},{"key":"e_1_2_2_77_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2023.3244885"},{"key":"e_1_2_2_78_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2013.25"},{"key":"e_1_2_2_79_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519939.3523431"},{"key":"e_1_2_2_80_1","doi-asserted-by":"publisher","DOI":"10.26421\/QIC4.2-5"},{"key":"e_1_2_2_81_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-29517-1_3"},{"key":"e_1_2_2_82_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxu145"},{"key":"e_1_2_2_83_1","doi-asserted-by":"publisher","DOI":"10.1145\/3689785"},{"key":"e_1_2_2_84_1","volume-title":"Reversible computer engineering and architecture. Ph. D. Dissertation","author":"Vieri Carlin James","unstructured":"Carlin James Vieri. 1999. Reversible computer engineering and architecture. Ph. D. Dissertation. Massachusetts Institute of Technology."},{"key":"e_1_2_2_85_1","doi-asserted-by":"publisher","DOI":"10.1145\/3571225"},{"key":"e_1_2_2_86_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2022.08.002"},{"key":"e_1_2_2_87_1","doi-asserted-by":"publisher","DOI":"10.1145\/3676641.3716256"},{"key":"e_1_2_2_88_1","unstructured":"Zhaowei Xu Mingsheng Ying and Beno\u00eet Valiron. 2021. Reasoning about recursive quantum programs. arxiv:2107.11679."},{"key":"e_1_2_2_89_1","doi-asserted-by":"publisher","unstructured":"Mingsheng Ying. 2016. Foundations of quantum programming. Morgan Kaufmann. https:\/\/doi.org\/10.1016\/C2014-0-02660-3 10.1016\/C2014-0-02660-3","DOI":"10.1016\/C2014-0-02660-3"},{"key":"e_1_2_2_90_1","unstructured":"Mingsheng Ying Nengkun Yu and Yuan Feng. 2012. Defining quantum control flow. arxiv:1209.4379."},{"key":"e_1_2_2_91_1","unstructured":"Mingsheng Ying and Zhicheng Zhang. 2024. Verification of recursively defined quantum circuits. arxiv:2404.05934."},{"key":"e_1_2_2_92_1","doi-asserted-by":"publisher","DOI":"10.1145\/1366230.1366239"},{"key":"e_1_2_2_93_1","doi-asserted-by":"publisher","DOI":"10.1145\/1244381.1244404"},{"key":"e_1_2_2_94_1","doi-asserted-by":"publisher","DOI":"10.1145\/3563297"},{"key":"e_1_2_2_95_1","doi-asserted-by":"publisher","DOI":"10.1145\/3656397"},{"key":"e_1_2_2_96_1","doi-asserted-by":"publisher","DOI":"10.1145\/3649811"},{"key":"e_1_2_2_97_1","doi-asserted-by":"publisher","DOI":"10.22331\/q-2023-03-20-956"},{"key":"e_1_2_2_98_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.129.230504"},{"key":"e_1_2_2_99_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41534-024-00835-8"},{"key":"e_1_2_2_100_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevResearch.3.043200"},{"key":"e_1_2_2_101_1","doi-asserted-by":"publisher","DOI":"10.22331\/q-2024-01-15-1228"},{"key":"e_1_2_2_102_1","unstructured":"Zhicheng Zhang and Mingsheng Ying. 2024. Quantum register machine: efficient implementation of quantum recursive programs. arxiv:2408.10054."}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3729283","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,16]],"date-time":"2025-07-16T06:06:21Z","timestamp":1752645981000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3729283"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,10]]},"references-count":102,"journal-issue":{"issue":"PLDI","published-print":{"date-parts":[[2025,6,10]]}},"alternative-id":["10.1145\/3729283"],"URL":"https:\/\/doi.org\/10.1145\/3729283","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,10]]},"assertion":[{"value":"2024-11-12","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-03-06","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-06-13","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}