{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,29]],"date-time":"2026-03-29T08:45:42Z","timestamp":1774773942000,"version":"3.50.1"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"PLDI","license":[{"start":{"date-parts":[[2024,6,20]],"date-time":"2024-06-20T00:00:00Z","timestamp":1718841600000},"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":[[2024,6,20]]},"abstract":"<jats:p>\n            Reducing the width of quantum circuits is crucial due to limited number of qubits in quantum devices. This paper revisit an optimization strategy known as\n            <jats:italic toggle=\"yes\">qubit recycling<\/jats:italic>\n            (alternatively\n            <jats:italic toggle=\"yes\">wire-recycling<\/jats:italic>\n            or\n            <jats:italic toggle=\"yes\">measurement- and-reset<\/jats:italic>\n            ), which leverages gate commutativity to reuse discarded qubits, thereby reducing circuit width. We introduce\n            <jats:italic toggle=\"yes\">qubit dependency graphs<\/jats:italic>\n            (QDGs) as a key abstraction for this optimization. With QDG, we isolate the computationally demanding components, and observe that qubit recycling is essentially a matrix triangularization problem. Based on QDG and this observation, we study qubit recycling with a focus on complexity, algorithmic, and verification aspects. Firstly, we establish qubit recycling\u2019s NP-hardness through reduction from Wilf\u2019s question, another matrix triangularization problem. Secondly, we propose a QDG-guided solver featuring multiple heuristic options for effective qubit recycling. Benchmark tests conducted on RevLib illustrate our solver\u2019s superior or comparable performance to existing alternatives. Notably, it achieves optimal solutions for the majority of circuits. Finally, we develop a certified qubit recycler that integrates verification and validation techniques, with its correctness proof mechanized in Coq.\n          <\/jats:p>","DOI":"10.1145\/3656428","type":"journal-article","created":{"date-parts":[[2024,6,20]],"date-time":"2024-06-20T16:27:20Z","timestamp":1718900840000},"page":"1264-1287","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Qubit Recycling Revisited"],"prefix":"10.1145","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5965-1209","authenticated-orcid":false,"given":"Hanru","family":"Jiang","sequence":"first","affiliation":[{"name":"Beijing Institute of Mathematical Sciences and Applications, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,6,20]]},"reference":[{"key":"e_1_3_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2004.1319636"},{"key":"e_1_3_1_3_1","doi-asserted-by":"publisher","DOI":"10.5281\/zenodo.2562111"},{"key":"e_1_3_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-63390-9_1"},{"key":"e_1_3_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-84800-998-1"},{"key":"e_1_3_1_6_1","unstructured":"Suresh Bolusani Mathieu Besan\u00e7on Ksenia Bestuzheva Antonia Chmiela Jo\u00e3o Dion\u00edsio Tim Donkiewicz Jasper van Doornmalen Leon Eifler Mohammed Ghannam Ambros Gleixner Christoph Graczyk Katrin Halbig Ivo Hedtke Alexander Hoen Christopher Hojny Rolf van der Hulst Dominik Kamp Thorsten Koch Kevin Kofler Jurgen Lentz Julian Manns Gioni Mexi Erik M\u00fchmer Marc E. Pfetsch Franziska Schl\u00f6sser Felipe Serrano Yuji Shinano Mark Turner Stefan Vigerske Dieter Weninger and Lixing Xu. 2024. The SCIP Optimization Suite 9.0. Technical Report. Optimization Online. https:\/\/optimization-online.org\/2024\/02\/the-scip-optimization-suite-9-0\/"},{"key":"e_1_3_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103441"},{"key":"e_1_3_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/321958.321971"},{"key":"e_1_3_1_9_1","doi-asserted-by":"publisher","DOI":"10.1017\/9781316219317"},{"key":"e_1_3_1_10_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevX.13.041057"},{"key":"e_1_3_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISCA45697.2020.00054"},{"key":"e_1_3_1_12_1","volume-title":"Tensor categories","author":"Etingof Pavel","year":"2016","unstructured":"Pavel Etingof, Shlomo Gelaki, Dmitri Nikshych, and Victor Ostrik. 2016. Tensor categories. American Mathematical Soc https:\/\/bookstore.ams.org\/surv-205"},{"key":"e_1_3_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48971-0_15"},{"key":"e_1_3_1_14_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.86.032324"},{"key":"e_1_3_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2003.1159750"},{"key":"e_1_3_1_16_1","volume-title":"Triangularization: a two-processor scheduling problem","author":"Haddad Ramsey W.","year":"1990","unstructured":"Ramsey W. Haddad. 1990. Triangularization: a two-processor scheduling problem. Ph. D. Dissertation. Stanford University, USA. https:\/\/searchworks.stanford.edu\/view\/507223"},{"key":"e_1_3_1_17_1","doi-asserted-by":"publisher","DOI":"10.1093\/oso\/9780198739623.001.0001"},{"key":"e_1_3_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3434318"},{"key":"e_1_3_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3582016.3582030"},{"key":"e_1_3_1_20_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.QUANT-PH\/0305050"},{"key":"e_1_3_1_21_1","doi-asserted-by":"publisher","DOI":"10.5281\/zenodo.10721283"},{"key":"e_1_3_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/368996.369025"},{"key":"e_1_3_1_23_1","doi-asserted-by":"publisher","DOI":"10.4204\/eptcs.318.14"},{"key":"e_1_3_1_24_1","doi-asserted-by":"crossref","unstructured":"Elena Di Lavore and Pawe\u0142 Soboci\u0144ski. 2023. Monoidal Width. arXiv:2212.13229 [cs.LO]","DOI":"10.46298\/lmcs-19(3:15)2023"},{"key":"e_1_3_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1538788.1538814"},{"key":"e_1_3_1_26_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1621345114"},{"key":"e_1_3_1_27_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41534-018-0072-4"},{"key":"e_1_3_1_28_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.94.042337"},{"key":"e_1_3_1_29_1","unstructured":"Alex Parent Martin Roetteler and Krysta M. Svore. 2015. Reversible circuit compilation with space constraints. arXiv:1510.00377 [quant-ph]"},{"key":"e_1_3_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3341689"},{"key":"e_1_3_1_31_1","doi-asserted-by":"publisher","DOI":"10.22331\/q-2018-08-06-79"},{"key":"e_1_3_1_32_1","doi-asserted-by":"publisher","DOI":"10.4204\/EPTCS.287.17"},{"key":"e_1_3_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11970-5_13"},{"key":"e_1_3_1_34_1","unstructured":"Movahhed Sadeghi Soheil Khadirsharbiyani and Mahmut Taylan Kandemir. 2022. Quantum Circuit Resizing. arXiv:2301.00720 [cs.ET]"},{"key":"e_1_3_1_35_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129504004256"},{"key":"e_1_3_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2006.12.018"},{"key":"e_1_3_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519939.3523431"},{"key":"e_1_3_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2005.01.033"},{"key":"e_1_3_1_39_1","doi-asserted-by":"crossref","unstructured":"John Wiegley. 2022. An axiom-free formalization of category theory in Coq. https:\/\/github.com\/jwiegley\/category-theory. Version 1.0.0.","DOI":"10.1017\/9781108936880.002"},{"key":"e_1_3_1_40_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511662034.049"},{"key":"e_1_3_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISMVL.2008.43"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3656428","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3656428","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,4]],"date-time":"2025-07-04T20:43:24Z","timestamp":1751661804000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3656428"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,20]]},"references-count":40,"journal-issue":{"issue":"PLDI","published-print":{"date-parts":[[2024,6,20]]}},"alternative-id":["10.1145\/3656428"],"URL":"https:\/\/doi.org\/10.1145\/3656428","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,6,20]]},"assertion":[{"value":"2024-06-20","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}