{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,30]],"date-time":"2026-01-30T10:51:41Z","timestamp":1769770301960,"version":"3.49.0"},"reference-count":24,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2022,6,7]],"date-time":"2022-06-07T00:00:00Z","timestamp":1654560000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"ANR","award":["ANR-17-CE25-0009-02"],"award-info":[{"award-number":["ANR-17-CE25-0009-02"]}]},{"name":"French Ministry of industry","award":["P163746-484124"],"award-info":[{"award-number":["P163746-484124"]}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"<jats:p>Qubit routing is a key problem for quantum circuit compilation. It consists in rewriting a quantum circuit by adding the least possible number of instructions to make the circuit compliant with some architecture&amp;apos;s connectivity constraints. Usually, this problem is tackled via either SWAP insertion techniques or re-synthesis of portions of the circuit using architecture aware synthesis algorithms. In this work, we propose a meta-heuristic that couples the iterative approach of SWAP insertion techniques with greedy architecture-aware synthesis routines. We propose two new compilation algorithms based on this meta-heuristic and compare their performances to state-of-the-art quantum circuit compilation techniques for several standard classes of quantum circuits and show significant reduction in the entangling gate overhead due to compilation.<\/jats:p>","DOI":"10.22331\/q-2022-06-07-729","type":"journal-article","created":{"date-parts":[[2022,6,7]],"date-time":"2022-06-07T15:04:47Z","timestamp":1654614287000},"page":"729","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":12,"title":["Architecture aware compilation of quantum circuits via lazy synthesis"],"prefix":"10.22331","volume":"6","author":[{"given":"Simon","family":"Martiel","sequence":"first","affiliation":[{"name":"Atos Quantum Lab. Les Clayes-sous-bois, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Timoth\u00e9e Goubault de","family":"Brugi\u00e8re","sequence":"additional","affiliation":[{"name":"Atos Quantum Lab. Les Clayes-sous-bois, France"},{"name":"Laboratoire de Recherche en Informatique (LRI), Orsay, France"},{"name":"Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Nancy, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"9598","published-online":{"date-parts":[[2022,6,7]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Matthew Amy, Parsiad Azimzadeh, and Michele Mosca. On the controlled-not complexity of controlled-not\u2013phase circuits. Quantum Science and Technology, 4(1):015002, 2018. doi:10.1088\/2058-9565\/aad8ca.","DOI":"10.1088\/2058-9565\/aad8ca"},{"key":"1","doi-asserted-by":"publisher","unstructured":"Scott Aaronson and Daniel Gottesman. Improved simulation of stabilizer circuits. Physical Review A, 70(5), Nov 2004. doi:10.1103\/physreva.70.052328.","DOI":"10.1103\/physreva.70.052328"},{"key":"2","doi-asserted-by":"publisher","unstructured":"Matthew Amy and Vlad Gheorghiu. staq\u2014a full-stack quantum processing toolkit. Quantum Science and Technology, 5(3):034016, jun 2020. doi:10.1088\/2058-9565\/ab9359.","DOI":"10.1088\/2058-9565\/ab9359"},{"key":"3","doi-asserted-by":"publisher","unstructured":"Sergey Bravyi and Dmitri Maslov. Hadamard-free circuits expose the structure of the clifford group. arXiv preprint arXiv:2003.09412, 2020. doi:10.1109\/TIT.2021.3081415.","DOI":"10.1109\/TIT.2021.3081415"},{"key":"4","doi-asserted-by":"publisher","unstructured":"Alexander Cowtan, Silas Dilkes, Ross Duncan, Alexandre Krajenbrink, Will Simmons, and Seyon Sivarajah. On the qubit routing problem. In 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019. doi:10.4230\/LIPIcs.TQC.2019.5.","DOI":"10.4230\/LIPIcs.TQC.2019.5"},{"key":"5","doi-asserted-by":"publisher","unstructured":"Andrew M. Childs, E. Schoute, and Cem M. Unsal. Circuit transformations for quantum architectures. ArXiv, abs\/1902.09102, 2019. doi:10.4230\/LIPIcs.TQC.2019.3.","DOI":"10.4230\/LIPIcs.TQC.2019.3"},{"key":"6","doi-asserted-by":"publisher","unstructured":"Niel de Beaudrap. A linearized stabilizer formalism for systems of finite dimension. 2011. doi:10.5555\/2481591.2481597.","DOI":"10.5555\/2481591.2481597"},{"key":"7","doi-asserted-by":"publisher","unstructured":"Timoth\u00e9e Goubault de Brugi\u00e8re, Marc Baboulin, Beno\u0131\u0302t Valiron, Simon Martiel, and Cyril Allouche. Quantum cnot circuits synthesis for nisq architectures using the syndrome decoding problem. In International Conference on Reversible Computation, pages 189\u2013205. Springer, 2020. doi:10.1007\/978-3-030-52482-1_11.","DOI":"10.1007\/978-3-030-52482-1_11"},{"key":"8","unstructured":"Vlad Gheorghiu, Sarah Meng Li, Michele Mosca, and Priyanka Mukhopadhyay. Reducing the cnot count for clifford+t circuits on nisq architectures, 2020. arXiv:2011.12191."},{"key":"9","doi-asserted-by":"publisher","unstructured":"Yuichi Hirata, Masaki Nakanishi, Shigeru Yamashita, and Yasuhiko Nakashima. An efficient conversion of quantum circuits to a linear nearest neighbor architecture. Quantum Information & Computation, 11(1&2):142\u2013166, 2011. doi:10.26421\/QIC11.1-2-10.","DOI":"10.26421\/QIC11.1-2-10"},{"key":"10","doi-asserted-by":"publisher","unstructured":"Richard Jozsa and Akimasa Miyake. Matchgates and classical simulation of quantum circuits. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 464(2100):3089\u20133106, Jul 2008. doi:10.1098\/rspa.2008.0189.","DOI":"10.1098\/rspa.2008.0189"},{"key":"11","doi-asserted-by":"publisher","unstructured":"Samuel A Kutin, David Petrie Moulton, and Lawren M Smithline. Computation at a distance. arXiv preprint quant-ph\/0701194, 2007. doi:10.48550\/arXiv.quant-ph\/0701194.","DOI":"10.48550\/arXiv.quant-ph\/0701194"},{"key":"12","doi-asserted-by":"publisher","unstructured":"Aleks Kissinger and Arianne Meijer van de Griend. Cnot circuit extraction for topologically-constrained quantum memories, 2019. doi:10.26421\/QIC20.7-8-4.","DOI":"10.26421\/QIC20.7-8-4"},{"key":"13","doi-asserted-by":"publisher","unstructured":"Gushu Li, Yufei Ding, and Yuan Xie. Tackling the qubit mapping problem for nisq-era quantum devices, 2018. doi:10.1145\/3297858.3304023.","DOI":"10.1145\/3297858.3304023"},{"key":"14","doi-asserted-by":"publisher","unstructured":"Daniel Litinski. Magic state distillation: Not as costly as you think. Quantum, 3:205, Dec 2019. doi:10.22331\/q-2019-12-02-205.","DOI":"10.22331\/q-2019-12-02-205"},{"key":"15","doi-asserted-by":"publisher","unstructured":"Beatrice Nash, Vlad Gheorghiu, and Michele Mosca. Quantum circuit optimizations for nisq architectures. Quantum Science and Technology, 5(2):025010, Mar 2020. doi:10.1088\/2058-9565\/ab79b1.","DOI":"10.1088\/2058-9565\/ab79b1"},{"key":"16","doi-asserted-by":"publisher","unstructured":"Ketan N Patel, Igor L Markov, and John P Hayes. Optimal synthesis of linear reversible circuits. Quantum Information & Computation, 8(3):282\u2013294, 2008. doi:10.5555\/2011763.2011767.","DOI":"10.5555\/2011763.2011767"},{"key":"17","doi-asserted-by":"publisher","unstructured":"John Preskill. Quantum computing in the nisq era and beyond. Quantum, 2:79, Aug 2018. doi:10.22331\/q-2018-08-06-79.","DOI":"10.22331\/q-2018-08-06-79"},{"key":"18","doi-asserted-by":"publisher","unstructured":"A. Shafaei, M. Saeedi, and M. Pedram. Optimization of quantum circuits for interaction distance in linear nearest neighbor architectures. In 2013 50th ACM\/EDAC\/IEEE Design Automation Conference (DAC), pages 1\u20136, 2013. doi:10.1145\/2463209.2488785.","DOI":"10.1145\/2463209.2488785"},{"key":"19","unstructured":"Hiromitsu Takahashi. An approximate solution for the steiner problem in graphs. Math. Japonica., 6:573\u2013577, 1990."},{"key":"20","doi-asserted-by":"publisher","unstructured":"Ewout van den Berg and Kristan Temme. Circuit optimization of hamiltonian simulation by simultaneous diagonalization of pauli clusters. Quantum, 4:322, Sep 2020. doi:10.22331\/q-2020-09-12-322.","DOI":"10.22331\/q-2020-09-12-322"},{"key":"21","doi-asserted-by":"publisher","unstructured":"Arianne Meijer van de Griend and Ross Duncan. Architecture-aware synthesis of phase polynomials for nisq devices, 2020. doi:10.4204\/EPTCS.","DOI":"10.4204\/EPTCS"},{"key":"22","doi-asserted-by":"publisher","unstructured":"Fang Zhang and Jianxin Chen. Optimizing t gates in clifford+t circuit as $\\pi\/4$ rotations around paulis, 2019. arXiv:1903.12456, doi:10.48550\/arXiv.1903.12456.","DOI":"10.48550\/arXiv.1903.12456"},{"key":"23","doi-asserted-by":"publisher","unstructured":"Alwin Zulehner, Alexandru Paler, and Robert Wille. An efficient methodology for mapping quantum circuits to the ibm qx architectures, 2017. doi:10.1109\/TCAD.2018.2846658.","DOI":"10.1109\/TCAD.2018.2846658"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2022-06-07-729\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2022,6,7]],"date-time":"2022-06-07T15:04:58Z","timestamp":1654614298000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2022-06-07-729\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,7]]},"references-count":24,"URL":"https:\/\/doi.org\/10.22331\/q-2022-06-07-729","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,6,7]]},"article-number":"729"}}