{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T03:36:31Z","timestamp":1773113791782,"version":"3.50.1"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2025,2,13]],"date-time":"2025-02-13T00:00:00Z","timestamp":1739404800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"French state through the ANR as a part of Plan France 2030","award":["NISQ2LSQ (ANR-22-PETQ-0006), EPiQ (ANR-22-PETQ-0007), SoftQPro (ANR-17-CE25-0009)"],"award-info":[{"award-number":["NISQ2LSQ (ANR-22-PETQ-0006), EPiQ (ANR-22-PETQ-0007), SoftQPro (ANR-17-CE25-0009)"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Quantum Comput."],"published-print":{"date-parts":[[2025,6,30]]},"abstract":"<jats:p>\n            We focus on the depth optimization of CNOT circuits on hardware with limited connectivity. We adapt the algorithm from Kutin et\u00a0al. that implements any\n            <jats:italic>n<\/jats:italic>\n            -qubit CNOT circuit in depth at most\n            <jats:italic>5n<\/jats:italic>\n            on a Linear Nearest Neighbor architecture. Our proposal is a block version of Kutin et\u00a0al.\u2019s algorithm that is scalable with the number of interactions available in the hardware: the more interactions we have, the less the depth. We derive better theoretical upper bounds and provide a simple implementation of the algorithm. Overall, we achieve better depth complexity for CNOT circuits on some realistic quantum hardware like a grid or a ladder. For instance, the execution of an\n            <jats:italic>n<\/jats:italic>\n            -qubit CNOT circuit on a grid can be done in depth\n            <jats:italic>4n+8<\/jats:italic>\n            .\n          <\/jats:p>","DOI":"10.1145\/3700884","type":"journal-article","created":{"date-parts":[[2024,11,5]],"date-time":"2024-11-05T10:51:57Z","timestamp":1730803917000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Shallower CNOT Circuits on Realistic Quantum Hardware"],"prefix":"10.1145","volume":"6","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8543-6871","authenticated-orcid":false,"given":"Timoth\u00e9e Goubault","family":"de Brugi\u00e8re","sequence":"first","affiliation":[{"name":"Quandela, Massy, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5624-2955","authenticated-orcid":false,"given":"Simon","family":"Martiel","sequence":"additional","affiliation":[{"name":"Atos, Bezons, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,2,13]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.70.052328"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1088\/2058-9565\/aad8ca"},{"key":"e_1_3_3_4_2","volume-title":"The Theory of Partitions","author":"Andrews George E.","year":"1998","unstructured":"George E. Andrews. 1998. The Theory of Partitions. Encyclopedia of Mathematics and Its Applications, Series Number 2. Cambridge University Press."},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.71.022316"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2021.3081415"},{"key":"e_1_3_3_7_2","doi-asserted-by":"crossref","first-page":"102726","DOI":"10.1016\/j.scico.2021.102726","article-title":"Decoding techniques applied to the compilation of CNOT circuits for NISQ architectures","author":"Brugi\u00e8re Timoth\u00e9e Goubault de","year":"2022","unstructured":"Timoth\u00e9e Goubault de Brugi\u00e8re, Marc Baboulin, Beno\u00eet Valiron, Simon Martiel, and Cyril Allouche. 2022. Decoding techniques applied to the compilation of CNOT circuits for NISQ architectures. Science of Computer Programming 214 (2022), 102726.","journal-title":"Science of Computer Programming"},{"issue":"3","key":"e_1_3_3_8_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3474226","article-title":"Gaussian elimination versus greedy methods for the synthesis of linear reversible circuits","volume":"2","author":"Brugi\u00e8re Timoth\u00e9e Goubault De","year":"2021","unstructured":"Timoth\u00e9e Goubault De Brugi\u00e8re, Marc Baboulin, Beno\u00eet Valiron, Simon Martiel, and Cyril Allouche. 2021. Gaussian elimination versus greedy methods for the synthesis of linear reversible circuits. ACM Transactions on Quantum Computing 2, 3 (2021), 1\u201326.","journal-title":"ACM Transactions on Quantum Computing"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1109\/TQE.2021.3091648"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.22331\/q-2020-06-04-279"},{"key":"e_1_3_3_11_2","volume-title":"Stabilizer Codes and Quantum Error Correction","author":"Gottesman Daniel","year":"1997","unstructured":"Daniel Gottesman. 1997. Stabilizer Codes and Quantum Error Correction. Ph. D. Dissertation. Caltech."},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.22331\/q-2020-09-21-327"},{"key":"e_1_3_3_13_2","first-page":"213","volume-title":"Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Jiang Jiaqing","year":"2020","unstructured":"Jiaqing Jiang, Xiaoming Sun, Shang-Hua Teng, Bujiao Wu, Kewen Wu, and Jialin Zhang. 2020. Optimal space-depth trade-off of CNOT circuits in quantum logic synthesis. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms. 213\u2013229."},{"issue":"7","key":"e_1_3_3_14_2","doi-asserted-by":"crossref","first-page":"581","DOI":"10.26421\/QIC20.7-8-4","article-title":"CNOT circuit extraction for topologically-constrained quantum memories","volume":"20","author":"Kissinger Aleks","year":"2020","unstructured":"Aleks Kissinger and Arianne Meijer-van de Griend. 2020. CNOT circuit extraction for topologically-constrained quantum memories. Quantum Information & Computation 20, 7-8 (2020), 581\u2013596. http:\/\/www.rintonpress.com\/xxqic20\/qic-20-78\/0581-0596.pdf","journal-title":"Quantum Information & Computation"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","unstructured":"Aleks Kissinger and John van de Wetering. 2020. PyZX: Large scale automated diagrammatic reasoning. Electronic Proceedings in Theoretical Computer Science 318 (2020) 229\u2013241. DOI:10.4204\/EPTCS.318.14","DOI":"10.4204\/EPTCS.318.14"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1038\/nature03350"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.77.012307"},{"key":"e_1_3_3_18_2","article-title":"Computation at a distance","volume":"2007","author":"Kutin Samuel A.","year":"2007","unstructured":"Samuel A. Kutin, David Petrie Moulton, and Lawren Smithline. 2007. Computation at a distance. Chicago Journal of Theoretical Computer Science 2007 (2007), Article 1. http:\/\/cjtcs.cs.uchicago.edu\/articles\/2007\/1\/contents.html","journal-title":"Chicago Journal of Theoretical Computer Science"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.106.180504"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.76.052310"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2018.2825602"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/TQE.2022.3180900"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1088\/2058-9565\/ab79b1"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.26421\/QIC8.3-4-4"},{"key":"e_1_3_3_25_2","article-title":"Efficient CNOT synthesis for NISQ devices","author":"Tang Yao","year":"2020","unstructured":"Yao Tang. 2020. Efficient CNOT synthesis for NISQ devices. arXiv preprint arXiv:2011.06760 (2020).","journal-title":"arXiv preprint arXiv:2011.06760"},{"issue":"1","key":"e_1_3_3_26_2","doi-asserted-by":"crossref","first-page":"013065","DOI":"10.1103\/PhysRevResearch.5.013065","article-title":"Optimization of CNOT circuits on limited-connectivity architecture","volume":"5","author":"Wu Bujiao","year":"2023","unstructured":"Bujiao Wu, Xiaoyu He, Shuai Yang, Lifu Shou, Guojing Tian, Jialin Zhang, and Xiaoming Sun. 2023. Optimization of CNOT circuits on limited-connectivity architecture. Physical Review Research 5, 1 (2023), 013065.","journal-title":"Physical Review Research"}],"container-title":["ACM Transactions on Quantum Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3700884","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3700884","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:10:23Z","timestamp":1750295423000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3700884"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,13]]},"references-count":25,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,6,30]]}},"alternative-id":["10.1145\/3700884"],"URL":"https:\/\/doi.org\/10.1145\/3700884","relation":{},"ISSN":["2643-6809","2643-6817"],"issn-type":[{"value":"2643-6809","type":"print"},{"value":"2643-6817","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,2,13]]},"assertion":[{"value":"2023-08-14","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-08-11","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-02-13","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}