Architecture aware compilation of quantum circuits via lazy synthesis

Simon Martiel; Timothée Goubault de Brugière

doi:10.22331/q-2022-06-07-729

Architecture aware compilation of quantum circuits via lazy synthesis

Simon Martiel¹ and Timothée Goubault de Brugière^1,2,3

¹Atos Quantum Lab. Les Clayes-sous-bois, France
²Laboratoire de Recherche en Informatique (LRI), Orsay, France
³Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Nancy, France

Published:	2022-06-07, volume 6, page 729
Eprint:	arXiv:2012.09663v4
Doi:	https://doi.org/10.22331/q-2022-06-07-729
Citation:	Quantum 6, 729 (2022).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

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'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.

► BibTeX data

@article{Martiel2022architectureaware,
  doi = {10.22331/q-2022-06-07-729},
  url = {https://doi.org/10.22331/q-2022-06-07-729},
  title = {Architecture aware compilation of quantum circuits via lazy synthesis},
  author = {Martiel, Simon and Brugi{\`{e}}re, Timoth{\'{e}}e Goubault de},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {6},
  pages = {729},
  month = jun,
  year = {2022}
}

► References

[1] Matthew Amy, Parsiad Azimzadeh, and Michele Mosca. On the controlled-not complexity of controlled-not–phase circuits. Quantum Science and Technology, 4(1):015002, 2018. doi:10.1088/2058-9565/aad8ca.
https://doi.org/10.1088/2058-9565/aad8ca

[2] Scott Aaronson and Daniel Gottesman. Improved simulation of stabilizer circuits. Physical Review A, 70(5), Nov 2004. doi:10.1103/physreva.70.052328.
https://doi.org/10.1103/physreva.70.052328

[3] Matthew Amy and Vlad Gheorghiu. staq—a full-stack quantum processing toolkit. Quantum Science and Technology, 5(3):034016, jun 2020. doi:10.1088/2058-9565/ab9359.
https://doi.org/10.1088/2058-9565/ab9359

[4] 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.
https://doi.org/10.1109/TIT.2021.3081415
arXiv:2003.09412

[5] 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.
https://doi.org/10.4230/LIPIcs.TQC.2019.5

[6] 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.
https://doi.org/10.4230/LIPIcs.TQC.2019.3

[7] Niel de Beaudrap. A linearized stabilizer formalism for systems of finite dimension. 2011. doi:10.5555/2481591.2481597.
https://doi.org/10.5555/2481591.2481597

[8] Timothée Goubault de Brugière, Marc Baboulin, Benoı̂t 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–205. Springer, 2020. doi:10.1007/978-3-030-52482-1_11.
https://doi.org/10.1007/978-3-030-52482-1_11

[9] 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.
arXiv:2011.12191

[10] 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–166, 2011. doi:10.26421/QIC11.1-2-10.
https://doi.org/10.26421/QIC11.1-2-10

[11] 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–3106, Jul 2008. doi:10.1098/rspa.2008.0189.
https://doi.org/10.1098/rspa.2008.0189

[12] 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.
https://doi.org/10.48550/arXiv.quant-ph/0701194
arXiv:quant-ph/0701194

[13] Aleks Kissinger and Arianne Meijer van de Griend. Cnot circuit extraction for topologically-constrained quantum memories, 2019. doi:10.26421/QIC20.7-8-4.
https://doi.org/10.26421/QIC20.7-8-4

[14] Gushu Li, Yufei Ding, and Yuan Xie. Tackling the qubit mapping problem for nisq-era quantum devices, 2018. doi:10.1145/3297858.3304023.
https://doi.org/10.1145/3297858.3304023

[15] Daniel Litinski. Magic state distillation: Not as costly as you think. Quantum, 3:205, Dec 2019. doi:10.22331/q-2019-12-02-205.
https://doi.org/10.22331/q-2019-12-02-205

[16] 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.
https://doi.org/10.1088/2058-9565/ab79b1

[17] Ketan N Patel, Igor L Markov, and John P Hayes. Optimal synthesis of linear reversible circuits. Quantum Information & Computation, 8(3):282–294, 2008. doi:10.5555/2011763.2011767.
https://doi.org/10.5555/2011763.2011767

[18] John Preskill. Quantum computing in the nisq era and beyond. Quantum, 2:79, Aug 2018. doi:10.22331/q-2018-08-06-79.
https://doi.org/10.22331/q-2018-08-06-79

[19] 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–6, 2013. doi:10.1145/2463209.2488785.
https://doi.org/10.1145/2463209.2488785

[20] Hiromitsu Takahashi. An approximate solution for the steiner problem in graphs. Math. Japonica., 6:573–577, 1990.

[21] 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.
https://doi.org/10.22331/q-2020-09-12-322

[22] Arianne Meijer van de Griend and Ross Duncan. Architecture-aware synthesis of phase polynomials for nisq devices, 2020. doi:10.4204/EPTCS.
https://doi.org/10.4204/EPTCS

[23] 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.
https://doi.org/10.48550/arXiv.1903.12456
arXiv:1903.12456

[24] 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.
https://doi.org/10.1109/TCAD.2018.2846658

Cited by

[1] Joris Kattemölle and Seenivasan Hariharan, "Line-Graph Qubit Routing", ACM Transactions on Quantum Computing 6 3, 1 (2025).

[2] Vivien Vandaele, Simon Martiel, and Timothée Goubault de Brugière, "Phase polynomials synthesis algorithms for NISQ architectures and beyond", Quantum Science and Technology 7 4, 045027 (2022).

[3] Vivien Vandaele, "Lower T-count with faster algorithms", Quantum 9, 1860 (2025).

[4] Aaron Miller, Adam Glos, and Zoltán Zimborás, "Treespilation: architecture- and state-optimised fermion-to-qubit mappings", npj Quantum Information 12 1, 26 (2026).

[5] Timothée Goubault de Brugière, Simon Martiel, and Christophe Vuillot, "A graph-state based synthesis framework for Clifford isometries", Quantum 9, 1589 (2025).

[6] Ji Liu, Alvin Gonzales, Benchen Huang, Zain Hamid Saleem, and Paul Hovland, 2025 IEEE International Symposium on High Performance Computer Architecture (HPCA) 158 (2025) ISBN:979-8-3315-0647-6.

[7] Jin Ming Koh, Dax Enshan Koh, and Jayne Thompson, "Readout Error Mitigation for Mid-Circuit Measurements and Feedforward", PRX Quantum 7 1, 010317 (2026).

[8] Berend Klaver, Stefan M. A. Rombouts, Michael Fellner, Anette Messinger, Kilian Ender, Katharina Ludwig, and Wolfgang Lechner, "SWAP-less implementation of quantum algorithms", Physical Review A 113 1, 012443 (2026).

[9] Arun Govindankutty, "A study of qubit modalities in contemporary quantum computing", Discover Quantum Science 2 1, 28 (2026).

[10] Junyu Zhou, Yuhao Liu, Yunong Shi, Ali Javadi-Abhari, and Gushu Li, 2024 ACM/IEEE 51st Annual International Symposium on Computer Architecture (ISCA) 261 (2024) ISBN:979-8-3503-2658-1.

[11] Mohammad Haidar, Marko J. Rančić, Thomas Ayral, Yvon Maday, and Jean‐Philip Piquemal, "Open source variational quantum eigensolver extension of the quantum learning machine for quantum chemistry", WIREs Computational Molecular Science 13 5, e1664 (2023).

[12] Ewan Murphy and Aleks Kissinger, "Global Synthesis of CNOT Circuits with Holes", Electronic Proceedings in Theoretical Computer Science 384, 75 (2023).

[13] Yuri Alexeev, Maximilian Amsler, Marco Antonio Barroca, Sanzio Bassini, Torey Battelle, Daan Camps, David Casanova, Young Jay Choi, Frederic T. Chong, Charles Chung, Christopher Codella, Antonio D. Córcoles, James Cruise, Alberto Di Meglio, Ivan Duran, Thomas Eckl, Sophia Economou, Stephan Eidenbenz, Bruce Elmegreen, Clyde Fare, Ismael Faro, Cristina Sanz Fernández, Rodrigo Neumann Barros Ferreira, Keisuke Fuji, Bryce Fuller, Laura Gagliardi, Giulia Galli, Jennifer R. Glick, Isacco Gobbi, Pranav Gokhale, Salvador de la Puente Gonzalez, Johannes Greiner, Bill Gropp, Michele Grossi, Emanuel Gull, Burns Healy, Matthew R. Hermes, Benchen Huang, Travis S. Humble, Nobuyasu Ito, Artur F. Izmaylov, Ali Javadi-Abhari, Douglas Jennewein, Shantenu Jha, Liang Jiang, Barbara Jones, Wibe Albert de Jong, Petar Jurcevic, William Kirby, Stefan Kister, Masahiro Kitagawa, Joel Klassen, Katherine Klymko, Kwangwon Koh, Masaaki Kondo, Dog̃a Murat Kürkçüog̃lu, Krzysztof Kurowski, Teodoro Laino, Ryan Landfield, Matt Leininger, Vicente Leyton-Ortega, Ang Li, Meifeng Lin, Junyu Liu, Nicolas Lorente, Andre Luckow, Simon Martiel, Francisco Martin-Fernandez, Margaret Martonosi, Claire Marvinney, Arcesio Castaneda Medina, Dirk Merten, Antonio Mezzacapo, Kristel Michielsen, Abhishek Mitra, Tushar Mittal, Kyungsun Moon, Joel Moore, Sarah Mostame, Mario Motta, Young-Hye Na, Yunseong Nam, Prineha Narang, Yu-ya Ohnishi, Daniele Ottaviani, Matthew Otten, Scott Pakin, Vincent R. Pascuzzi, Edwin Pednault, Tomasz Piontek, Jed Pitera, Patrick Rall, Gokul Subramanian Ravi, Niall Robertson, Matteo A.C. Rossi, Piotr Rydlichowski, Hoon Ryu, Georgy Samsonidze, Mitsuhisa Sato, Nishant Saurabh, Vidushi Sharma, Kunal Sharma, Soyoung Shin, George Slessman, Mathias Steiner, Iskandar Sitdikov, In-Saeng Suh, Eric D. Switzer, Wei Tang, Joel Thompson, Synge Todo, Minh C. Tran, Dimitar Trenev, Christian Trott, Huan-Hsin Tseng, Norm M. Tubman, Esin Tureci, David García Valiñas, Sofia Vallecorsa, Christopher Wever, Konrad Wojciechowski, Xiaodi Wu, Shinjae Yoo, Nobuyuki Yoshioka, Victor Wen-zhe Yu, Seiji Yunoki, Sergiy Zhuk, and Dmitry Zubarev, "Quantum-centric supercomputing for materials science: A perspective on challenges and future directions", Future Generation Computer Systems 160, 666 (2024).

[14] Arianne Meijer-Van De Griend, 2024 IEEE International Conference on Software Analysis, Evolution and Reengineering - Companion (SANER-C) 146 (2024) ISBN:979-8-3503-5157-6.

[15] Simon Martiel, Thomas Ayral, and Cyril Allouche, "Benchmarking Quantum Coprocessors in an Application-Centric, Hardware-Agnostic, and Scalable Way", IEEE Transactions on Quantum Engineering 2, TQE.2021 (2021).

[16] P. Besserve and T. Ayral, "Unraveling correlated material properties with noisy quantum computers: Natural orbitalized variational quantum eigensolving of extended impurity models within a slave-boson approach", Physical Review B 105 11, 115108 (2022).

[17] Ewan Murphy and Aleks Kissinger, "Global Synthesis of CNOT Circuits with Holes", arXiv:2308.16496, (2023).

[18] Junyu Zhou, Yuhao Liu, Yunong Shi, Ali Javadi-Abhari, and Gushu Li, "Bosehedral: Compiler Optimization for Bosonic Quantum Computing", arXiv:2402.02279, (2024).

[19] Mohammad Haidar, Marko J. Rančić, Thomas Ayral, Yvon Maday, and Jean-Philip Piquemal, "Open Source Variational Quantum Eigensolver Extension of the Quantum Learning Machine (QLM) for Quantum Chemistry", arXiv:2206.08798, (2022).

[20] David Winderl, Qunsheng Huang, Arianne Meijer-van de Griend, and Richie Yeung, "Architecture-Aware Synthesis of Stabilizer Circuits from Clifford Tableaus", arXiv:2309.08972, (2023).

The above citations are from Crossref's cited-by service (last updated successfully 2026-08-07 06:10:32) and SAO/NASA ADS (last updated successfully 2026-08-06 15:38:01). The list may be incomplete as not all publishers provide suitable and complete citation data.

Could not fetch ADS cited-by data during last attempt 2026-08-07 06:10:32: Cannot retrieve data from ADS due to rate limitations.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.