Full Characterization of the Depth Overhead for Quantum Circuit Compilation with Arbitrary Qubit Connectivity Constraint

Pei Yuan; Shengyu Zhang

doi:10.22331/q-2025-05-28-1757

Full Characterization of the Depth Overhead for Quantum Circuit Compilation with Arbitrary Qubit Connectivity Constraint

Pei Yuan and Shengyu Zhang

Tencent Quantum Laboratory, Tencent, Shenzhen, Guangdong 518057, China

Published:	2025-05-28, volume 9, page 1757
Editor:	Daniel Grier
Eprint:	arXiv:2402.02403v2
Doi:	https://doi.org/10.22331/q-2025-05-28-1757
Citation:	Quantum 9, 1757 (2025).

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

Abstract

In some physical implementations of quantum computers, 2-qubit operations can be applied only on certain pairs of qubits. Compilation of a quantum circuit into one compliant to such qubit connectivity constraint results in an increase of circuit depth. Various compilation algorithms were studied, yet what this depth overhead is remains elusive. In this paper, we fully characterize the depth overhead by the routing number of the underlying constraint graph, a graph-theoretic measure which has been studied for 3 decades. We also give reduction algorithms between different graphs, which allow compilation for one graph to be transferred to one for another. These results, when combined with existing routing algorithms, give asymptotically optimal compilation for all commonly seen connectivity graphs in quantum computing.

► BibTeX data

@article{Yuan2025full,
  doi = {10.22331/q-2025-05-28-1757},
  url = {https://doi.org/10.22331/q-2025-05-28-1757},
  title = {Full {C}haracterization of the {D}epth {O}verhead for {Q}uantum {C}ircuit {C}ompilation with {A}rbitrary {Q}ubit {C}onnectivity {C}onstraint},
  author = {Yuan, Pei and Zhang, Shengyu},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {9},
  pages = {1757},
  month = may,
  year = {2025}
}

► References

[1] Peter W Shor. ``Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer''. SIAM review 41, 303–332 (1999).
https://doi.org/10.1137/S0036144598347011

[2] Lov K Grover. ``A fast quantum mechanical algorithm for database search''. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing. Pages 212–219. (1996).
https://doi.org/10.1145/237814.237866

[3] Stephen Jordan. ``Quantum algorithm zoo''. https://quantumalgorithmzoo. org/.

[4] Marco Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C Benjamin, Suguru Endo, Keisuke Fujii, et al. ``Variational quantum algorithms''. Nature Reviews Physics 3, 625–644 (2021).
https://doi.org/10.1038/s42254-021-00348-9

[5] IBM Quantum. ``IBM Quantum''. https://quantumexperience.ng.bluemix.net /qx/devices.
https://quantumexperience.ng.bluemix.net

[6] Yangsen Ye, Zi-Yong Ge, Yulin Wu, Shiyu Wang, Ming Gong, Yu-Ran Zhang, et al. ``Propagation and localization of collective excitations on a 24-qubit superconducting processor''. Physical Review Letters 123, 050502 (2019).
https://doi.org/10.1103/PhysRevLett.123.050502

[7] Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C Bardin, Rami Barends, et al. ``Quantum supremacy using a programmable superconducting processor''. Nature 574, 505–510 (2019).
https://doi.org/10.1038/s41586-019-1666-5

[8] Ming Gong, Shiyu Wang, Chen Zha, Ming-Cheng Chen, He-Liang Huang, Yulin Wu, et al. ``Quantum walks on a programmable two-dimensional 62-qubit superconducting processor''. Science 372, 948–952 (2021).
https://doi.org/10.1126/science.abg7812

[9] M Ciorga, AS Sachrajda, Pawel Hawrylak, C Gould, Piotr Zawadzki, S Jullian, Y Feng, and Zbigniew Wasilewski. ``Addition spectrum of a lateral dot from coulomb and spin-blockade spectroscopy''. Physical Review B 61, R16315 (2000).
https://doi.org/10.1103/PhysRevB.61.R16315

[10] JM Elzerman, R Hanson, JS Greidanus, LH Willems Van Beveren, S De Franceschi, LMK Vandersypen, S Tarucha, and LP Kouwenhoven. ``Few-electron quantum dot circuit with integrated charge read out''. Physical Review B 67, 161308 (2003).
https://doi.org/10.1103/PhysRevB.67.161308

[11] JR Petta, AC Johnson, CM Marcus, MP Hanson, and AC Gossard. ``Manipulation of a single charge in a double quantum dot''. Physical Review Letters 93, 186802 (2004).
https://doi.org/10.1103/PhysRevLett.93.186802

[12] D Schröer, AD Greentree, L Gaudreau, K Eberl, LCL Hollenberg, JP Kotthaus, and S Ludwig. ``Electrostatically defined serial triple quantum dot charged with few electrons''. Physical Review B 76, 075306 (2007).
https://doi.org/10.1103/PhysRevB.76.075306

[13] DM Zajac, TM Hazard, Xiao Mi, E Nielsen, and Jason R Petta. ``Scalable gate architecture for a one-dimensional array of semiconductor spin qubits''. Physical Review Applied 6, 054013 (2016).
https://doi.org/10.1103/PhysRevApplied.6.054013

[14] Andrew M Childs, Eddie Schoute, and Cem M Unsal. ``Circuit transformations for quantum architectures''. In 14th Conference on the Theory of Quantum Computation, Communication and Cryptography. Pages 3:1–3:24. (2019).
https://doi.org/10.4230/LIPIcs.TQC.2019.3

[15] Immanuel Bloch. ``Quantum coherence and entanglement with ultracold atoms in optical lattices''. Nature 453, 1016–1022 (2008).
https://doi.org/10.1038/nature07126

[16] Iulia Buluta, Sahel Ashhab, and Franco Nori. ``Natural and artificial atoms for quantum computation''. Reports on Progress in Physics 74, 104401 (2011).
https://doi.org/10.1088/0034-4885/74/10/104401

[17] Hannes Bernien, Sylvain Schwartz, Alexander Keesling, Harry Levine, Ahmed Omran, Hannes Pichler, et al. ``Probing many-body dynamics on a 51-atom quantum simulator''. Nature 551, 579–584 (2017).
https://doi.org/10.1038/nature24622

[18] Kyle Booth, Minh Do, J Beck, Eleanor Rieffel, Davide Venturelli, and Jeremy Frank. ``Comparing and integrating constraint programming and temporal planning for quantum circuit compilation''. In Proceedings of the International Conference on Automated Planning and Scheduling. Pages 366–374. (2018).
https://doi.org/10.1609/icaps.v28i1.13920

[19] Dmitri Maslov, Sean M. Falconer, and Michele Mosca. ``Quantum circuit placement''. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 27, 752–763 (2008).
https://doi.org/10.1109/TCAD.2008.917562

[20] Alireza Shafaei, Mehdi Saeedi, and Massoud Pedram. ``Optimization of quantum circuits for interaction distance in linear nearest neighbor architectures''. In Proceedings of the 50th annual design automation conference. Pages 1–6. (2013).
https://doi.org/10.1145/2463209.2488785

[21] Alireza Shafaei, Mehdi Saeedi, and Massoud Pedram. ``Qubit placement to minimize communication overhead in 2d quantum architectures''. In 2014 19th Asia and South Pacific Design Automation Conference. Pages 495–500. (2014).
https://doi.org/10.1109/ASPDAC.2014.6742940

[22] Abhoy Kole, Kamalika Datta, and Indranil Sengupta. ``A heuristic for linear nearest neighbor realization of quantum circuits by swap gate insertion using $n$-gate lookahead''. IEEE journal on emerging and selected topics in circuits and systems 6, 62–72 (2016).
https://doi.org/10.1109/JETCAS.2016.2528720

[23] Chia-Chun Lin, Susmita Sur-Kolay, and Niraj K. Jha. ``Paqcs: Physical design-aware fault-tolerant quantum circuit synthesis''. IEEE Transactions on Very Large Scale Integration (VLSI) Systems 23, 1221–1234 (2015).
https://doi.org/10.1109/TVLSI.2014.2337302

[24] Ritu Ranjan Shrivastwa, Kamalika Datta, and Indranil Sengupta. ``Fast qubit placement in 2d architecture using nearest neighbor realization''. In 2015 IEEE International Symposium on Nanoelectronic and Information Systems. Pages 95–100. (2015).
https://doi.org/10.1109/iNIS.2015.59

[25] Gushu Li, Yufei Ding, and Yuan Xie. ``Tackling the qubit mapping problem for nisq-era quantum devices''. In Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems. Pages 1001–1014. (2019).
https://doi.org/10.1145/3297858.3304023

[26] Julian Kelly, Rami Barends, Austin G Fowler, Anthony Megrant, Evan Jeffrey, Theodore C White, et al. ``State preservation by repetitive error detection in a superconducting quantum circuit''. Nature 519, 66–69 (2015).
https://doi.org/10.1038/nature14270

[27] Rigetti. ``Rigetti''. http://docs.rigetti.com/en/latest/qpu.html.
http://docs.rigetti.com/en/latest/qpu.html.

[28] John Preskill. ``Quantum computing in the NISQ era and beyond''. Quantum 2, 79 (2018).
https://doi.org/10.22331/q-2018-08-06-79

[29] Matthew P Harrigan, Kevin J Sung, Matthew Neeley, et al. ``Quantum approximate optimization of non-planar graph problems on a planar superconducting processor''. Nature Physics 17, 332–336 (2021).
https://doi.org/10.1038/s41567-020-01105-y

[30] Noga Alon, F. R. K. Chung, and R. L. Graham. ``Routing permutations on graphs via matchings''. SIAM Journal on Discrete Mathematics 7, 513–530 (1994).
https://doi.org/10.1137/S0895480192236628

[31] Louxin Zhang. ``Optimal bounds for matching routing on trees''. SIAM Journal on Discrete Mathematics 12, 64–77 (1999).
https://doi.org/10.1137/S0895480197323159

[32] Indranil Banerjee and Dana Richards. ``New results on routing via matchings on graphs''. In Fundamentals of Computation Theory. Pages 69–81. (2017).
https://doi.org/10.1007/978-3-662-55751-8_7

[33] Wei-Tian Li, Linyuan Lu, and Yiting Yang. ``Routing numbers of cycles, complete bipartite graphs, and hypercubes''. SIAM Journal on Discrete Mathematics 24, 1482–1494 (2010).
https://doi.org/10.1137/090776317

[34] Rajko Nenadov. ``Routing permutations on spectral expanders via matchings''. Combinatorica Pages 1–6 (2023).
https://doi.org/10.1007/s00493-023-00033-8

[35] Indranil Banerjee, Dana Richards, and Igor Shinkar. ``Sorting networks on restricted topologies''. In SOFSEM 2019: Theory and Practice of Computer Science. Pages 54–66. (2019).
https://doi.org/10.1007/978-3-030-10801-4_6

[36] MA Nielsen. ``A geometric approach to quantum circuit lower bounds''. Quantum Information & Computation 6, 213–262 (2006).
https://doi.org/10.5555/2011686.2011688

[37] M.A. Nielsen, M.R. Dowling, M. Gu, and A.C. Doherty. ``Quantum computation as geometry''. Science 311, 1133 (2006).
https://doi.org/10.1126/science.1121541

[38] Pei Yuan, Jonathan Allcock, and Shengyu Zhang. ``Does qubit connectivity impact quantum circuit complexity?''. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 43, 520–533 (2024).
https://doi.org/10.1109/TCAD.2023.3311734

[39] Xiaoming Sun, Guojing Tian, Shuai Yang, Pei Yuan, and Shengyu Zhang. ``Asymptotically optimal circuit depth for quantum state preparation and general unitary synthesis''. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 42, 3301–3314 (2023).
https://doi.org/10.1109/TCAD.2023.3244885

[40] Martin Plesch and Caslav Brukner. ``Quantum-state preparation with universal gate decompositions''. Physical Review A 83, 032302 (2011).
https://doi.org/10.1103/PhysRevA.83.032302

[41] Charles C Pinter. ``A book of abstract algebra: second edition''. Courier Corporation. (2019).

[42] Alan Roberts, Antonis Symvonis, and Louxin Zhang. ``Routing on trees via matchings''. In Algorithms and Data Structures. Pages 251–262. (1995).
https://doi.org/10.1007/3-540-60220-8_67

[43] Sanjeev Arora and Boaz Barak. ``Computational complexity: a modern approach''. Cambridge University Press. (2009).
https://doi.org/10.1017/CBO9780511804090

Cited by

[1] Hansika Weerasena and Prabhat Mishra, Design Automation for Quantum Computing 31 (2026) ISBN:978-3-032-09302-8.

[2] Alex Krasnok, "Metamaterials in superconducting and cryogenic quantum technologies", Applied Physics Reviews 13 2, 021311 (2026).

[3] Milad Eslaminia and Sébastien Le Beux, "Reducing Maximum Subcircuits Depth in Quantum Circuit Cutting", IEEE Transactions on Quantum Engineering 7, 3103209 (2026).

[4] Norman Bunk and Felix Govaers, 2025 IEEE Sensor Data Fusion: Trends, Solutions, Applications (SDF) 1 (2025) ISBN:979-8-3315-7651-6.

[5] Nathan Constantinides, Ali Fahimniya, Dhruv Devulapalli, Dolev Bluvstein, Michael J. Gullans, J. V. Porto, Andrew M. Childs, and Alexey V. Gorshkov, "Optimal Routing Protocols for Reconfigurable Atom Arrays", arXiv:2411.05061, (2024).

[6] Florian Dreier, Christoph Fleckenstein, Gregor Aigner, Michael Fellner, Philipp Aumann, Reinhard Stahn, Martin Lanthaler, and Wolfgang Lechner, "Connectivity-aware Synthesis of Quantum Algorithms", arXiv:2501.14020, (2025).

[7] Pei Yuan and Shengyu Zhang, "Depth-Efficient Quantum Circuit Synthesis for Deterministic Dicke State Preparation", arXiv:2505.15413, (2025).

[8] Nikolaos Cheimarios and Spyridoula Cheimariou, "Logical Consistency as a Dynamical Invariant: A Quantum Model of Self-Reference and Paradox", arXiv:2512.21914, (2025).

[9] Marten Folkertsma, Lorenzo Grevink, Jonas Helsen, and Alicja Dutkiewicz, "Arts & crafts: Strong random unitaries and geometric locality", arXiv:2605.03023, (2026).

The above citations are from Crossref's cited-by service (last updated successfully 2026-08-09 04:53:09) and SAO/NASA ADS (last updated successfully 2026-08-08 16:03:46). 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-09 04:53:09: 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.