quantum-computing

A Multilevel Framework for Partitioning Quantum Circuits

Quantum Science and Technology (arXiv overlay)

41 min read

0 likes

⚡ Quantum Brief

A Multilevel Framework for Partitioning Quantum Circuits

Summarize this article with:

AbstractExecuting quantum algorithms over distributed quantum systems requires quantum circuits to be divided into sub-circuits which communicate via entanglement-based teleportation. Naively mapping circuits to qubits over multiple quantum processing units (QPUs) results in large communication overhead, increasing both execution time and noise. This can be minimised by optimising the assignment of qubits to QPUs and the methods used for covering non-local operations. Formulations that are general enough to capture the spectrum of teleportation possibilities lead to complex problem instances which can be difficult to solve effectively. This highlights a need to exploit the wide range of heuristic techniques used in the graph partitioning literature. This paper formalises and extends existing constructions for graphical quantum circuit partitioning and designs a new objective function that captures further possibilities for non-local operations via $\textit{nested state teleportation}$. We adapt the well-known Fiduccia-Mattheyses heuristic to the constraints and problem objective and explore multilevel techniques that coarsen hypergraphs and partition at multiple levels of granularity. We find that this reduces runtime and improves solution quality of standard partitioning. We place these techniques within a larger framework, through which we can extract full distributed quantum circuits including teleportation instructions. We compare the entanglement requirements and runtimes with state-of-the-art methods, finding that we achieve the lowest entanglement costs in most cases. Averaging over a wide range of circuits, we reduce the entanglement requirements by 35% compared with the next best-performing method. We also find that our techniques can scale to much larger circuit sizes than competing methods, provided the number of partitions is not too large.Featured image: Starting with a fine-grained temporal hypergraph representing a quantum circuit, the time dimension is coarsened away until an ordinary, 'static', hypergraph remains. The time dimension is then gradually re-introduced while iteratively optimising the partitioning, resulting in a low cost final solution.The methods developed in this work are implemented in an open-source software tool called DisQCO (Distributed Quantum Circuit Optimisation), available on GitHub. Popular summaryAs quantum computers grow larger, they are increasingly being built as networks of smaller machines connected by light. In these modular and distributed architectures, multiple matter-based quantum processing units (QPUs) are linked using photonic connections that distribute entanglement between devices. This enables universal quantum computing through teleportation, but at a cost: entanglement generation is typically slow and imperfect, and excessive communication can significantly degrade computational performance. To address this, researchers have developed various techniques for partitioning quantum circuits, which involves breaking a large circuit into smaller pieces that run on separate QPUs while minimising communication between them. Most existing approaches are built around a single, specific way of using teleportation, which makes them powerful in narrow settings but inflexible across the wide diversity of real quantum circuits. In this work, we introduce a circuit partitioning framework based on hypergraphs with an explicit temporal dimension that is agnostic to how entanglement is used for communication. The construction allows the assignment of qubits to QPUs and the kind of teleportation used all to be directly optimised through partitioning. While this generality enables the method to handle a broad range of circuits, scalability remains a key challenge for large problem instances. To address this, we exploit multilevel partitioning techniques. We introduce a temporal coarsening procedure that produces a hierarchy of progressively smaller graphs with decreasing time resolution. Intuitively, this lets the optimiser first reason about a circuit in broad strokes over time, and then refine its decisions at finer and finer temporal scales. By performing partitioning across this hierarchy, we gradually transform a conventional, static hypergraph problem into a fully temporal one, achieving solutions that are both faster to compute and more effective at reducing communication. Using this approach, our framework partitions circuits using, on average, 35% less entanglement than state-of-the-art methods. ► BibTeX data@article{Burt2026multilevelframework, doi = {10.22331/q-2026-01-22-1984}, url = {https://doi.org/10.22331/q-2026-01-22-1984}, title = {A {M}ultilevel {F}ramework for {P}artitioning {Q}uantum {C}ircuits}, author = {Burt, Felix and Chen, Kuan-Cheng and Leung, Kin K.}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {1984}, month = jan, year = {2026} }► References [1] Marcello Caleffi, Michele Amoretti, Davide Ferrari, Jessica Illiano, Antonio Manzalini, and Angela Sara Cacciapuoti. Distributed quantum computing: A survey. Computer Networks, 254: 110672, December 2024. ISSN 1389-1286. 10.1016/j.comnet.2024.110672. https://doi.org/10.1016/j.comnet.2024.110672 [2] Nemanja Isailovic, Yatish Patel, Mark Whitney, and John Kubiatowicz. Interconnection Networks for Scalable Quantum Computers. ACM SIGARCH Computer Architecture News, 34 (2): 366–377, May 2006. ISSN 0163-5964. 10.1145/1150019.1136505. https://doi.org/10.1145/1150019.1136505 [3] M. Akhtar, F. Bonus, F. R. Lebrun-Gallagher, N. I. Johnson, M. Siegele-Brown, S. Hong, S. J. Hile, S. A. Kulmiya, S. Weidt, and W. K. Hensinger. A high-fidelity quantum matter-link between ion-trap microchip modules. Nature Communications, 14 (1): 531, February 2023. ISSN 2041-1723. 10.1038/s41467-022-35285-3. https://doi.org/10.1038/s41467-022-35285-3 [4] V. Krutyanskiy, M. Galli, V. Krcmarsky, S. Baier, D. A. Fioretto, Y. Pu, A. Mazloom, P. Sekatski, M. Canteri, M. Teller, J. Schupp, J. Bate, M. Meraner, N. Sangouard, B. P. Lanyon, and T. E. Northup. Entanglement of Trapped-Ion Qubits Separated by 230 Meters.

Physical Review Letters, 130 (5): 050803, February 2023. 10.1103/PhysRevLett.130.050803. https://doi.org/10.1103/PhysRevLett.130.050803 [5] Jameson O'Reilly, George Toh, Isabella Goetting, Sagnik Saha, Mikhail Shalaev, Allison L. Carter, Andrew Risinger, Ashish Kalakuntla, Tingguang Li, Ashrit Verma, and Christopher Monroe. Fast Photon-Mediated Entanglement of Continuously Cooled Trapped Ions for Quantum Networking.

Physical Review Letters, 133 (9): 090802, August 2024. 10.1103/PhysRevLett.133.090802. https://doi.org/10.1103/PhysRevLett.133.090802 [6] Photonic Inc, Francis Afzal, Mohsen Akhlaghi, Stefanie J. Beale, Olinka Bedroya, Kristin Bell, Laurent Bergeron, Kent Bonsma-Fisher, Polina Bychkova, Zachary M. E. Chaisson, Camille Chartrand, Chloe Clear, Adam Darcie, Adam DeAbreu, Colby DeLisle, Lesley A. Duncan, Chad Dundas Smith, John Dunn, Amir Ebrahimi, Nathan Evetts, Daker Fernandes Pinheiro, Patricio Fuentes, Tristen Georgiou, Biswarup Guha, Rafael Haenel, Daniel Higginbottom, Daniel M. Jackson, Navid Jahed, Amin Khorshidahmad, Prasoon K. Shandilya, Alexander T. K. Kurkjian, Nikolai Lauk, Nicholas R. Lee-Hone, Eric Lin, Rostyslav Litynskyy, Duncan Lock, Lisa Ma, Iain MacGilp, Evan R. MacQuarrie, Aaron Mar, Alireza Marefat Khah, Alex Matiash, Evan Meyer-Scott, Cathryn P. Michaels, Juliana Motira, Narwan Kabir Noori, Egor Ospadov, Ekta Patel, Alexander Patscheider, Danny Paulson, Ariel Petruk, Adarsh L. Ravindranath, Bogdan Reznychenko, Myles Ruether, Jeremy Ruscica, Kunal Saxena, Zachary Schaller, Alex Seidlitz, John Senger, Youn Seok Lee, Orbel Sevoyan, Stephanie Simmons, Oney Soykal, Leea Stott, Quyen Tran, Spyros Tserkis, Ata Ulhaq, Wyatt Vine, Russ Weeks, Gary Wolfowicz, and Isao Yoneda.

Distributed Quantum Computing in Silicon. arXiv preprint, (arXiv:2406.01704), June 2024. 10.48550/arXiv.2406.01704. https://doi.org/10.48550/arXiv.2406.01704 arXiv:2406.01704 [7] Aziza Almanakly, Beatriz Yankelevich, Max Hays, Bharath Kannan, Réouven Assouly, Alex Greene, Michael Gingras, Bethany M. Niedzielski, Hannah Stickler, Mollie E. Schwartz, Kyle Serniak, Joel Î-j Wang, Terry P. Orlando, Simon Gustavsson, Jeffrey A. Grover, and William D. Oliver. Deterministic remote entanglement using a chiral quantum interconnect. Nature Physics, pages 1–6, March 2025. ISSN 1745-2481. 10.1038/s41567-025-02811-1. https://doi.org/10.1038/s41567-025-02811-1 [8] Sagnik Saha, Mikhail Shalaev, Jameson O'Reilly, Isabella Goetting, George Toh, Ashish Kalakuntla, Yichao Yu, and Christopher Monroe. High-fidelity remote entanglement of trapped atoms mediated by time-bin photons. Nature Communications, 16 (1): 2533, March 2025. ISSN 2041-1723. 10.1038/s41467-025-57557-4. https://doi.org/10.1038/s41467-025-57557-4 [9] Kevin S. Chou, Jacob Z. Blumoff, Christopher S. Wang, Philip C. Reinhold, Christopher J. Axline, Yvonne Y. Gao, L. Frunzio, M. H. Devoret, Liang Jiang, and R. J. Schoelkopf. Deterministic teleportation of a quantum gate between two logical qubits. Nature, 561 (7723): 368–373, September 2018. ISSN 1476-4687. 10.1038/s41586-018-0470-y. https://doi.org/10.1038/s41586-018-0470-y [10] Yong Wan, Daniel Kienzler, Stephen D. Erickson, Karl H. Mayer, Ting Rei Tan, Jenny J. Wu, Hilma M. Vasconcelos, Scott Glancy, Emanuel Knill, David J. Wineland, Andrew C. Wilson, and Dietrich Leibfried. Quantum gate teleportation between separated qubits in a trapped-ion processor. Science, 364 (6443): 875–878, May 2019. 10.1126/science.aaw9415. https://doi.org/10.1126/science.aaw9415 [11] D. Main, P. Drmota, D. P. Nadlinger, E. M. Ainley, A. Agrawal, B. C. Nichol, R. Srinivas, G. Araneda, and D. M. Lucas. Distributed quantum computing across an optical network link. Nature, 638 (8050): 383–388, February 2025. ISSN 1476-4687. 10.1038/s41586-024-08404-x. https://doi.org/10.1038/s41586-024-08404-x [12] James Ang, Gabriella Carini, Yanzhu Chen, Isaac Chuang, Michael Demarco, Sophia Economou, Alec Eickbusch, Andrei Faraon, Kai-Mei Fu, Steven Girvin, Michael Hatridge, Andrew Houck, Paul Hilaire, Kevin Krsulich, Ang Li, Chenxu Liu, Yuan Liu, Margaret Martonosi, David McKay, Jim Misewich, Mark Ritter, Robert Schoelkopf, Samuel Stein, Sara Sussman, Hong Tang, Wei Tang, Teague Tomesh, Norm Tubman, Chen Wang, Nathan Wiebe, Yongxin Yao, Dillon Yost, and Yiyu Zhou. ARQUIN: Architectures for Multinode Superconducting Quantum Computers. ACM Transactions on Quantum Computing, 5 (3): 19:1–19:59, September 2024. 10.1145/3674151. https://doi.org/10.1145/3674151 [13] David Barral, F. Javier Cardama, Guillermo Díaz-Camacho, Daniel Faílde, Iago F. Llovo, Mariamo Mussa-Juane, Jorge Vázquez-Pérez, Juan Villasuso, César Piñeiro, Natalia Costas, Juan C. Pichel, Tomás F. Pena, and Andrés Gómez. Review of Distributed Quantum Computing: From single QPU to High Performance Quantum Computing.

Computer Science Review, 57: 100747, August 2025. ISSN 1574-0137. 10.1016/j.cosrev.2025.100747. https://doi.org/10.1016/j.cosrev.2025.100747 [14] Mariam Zomorodi-Moghadam, Mahboobeh Houshmand, and Monireh Houshmand.

Optimizing Teleportation Cost in Distributed Quantum Circuits. International Journal of Theoretical Physics, 57 (3): 848–861, March 2018. ISSN 1572-9575. 10.1007/s10773-017-3618-x. https://doi.org/10.1007/s10773-017-3618-x [15] Pablo Andrés-Martínez and Chris Heunen. Automated distribution of quantum circuits via hypergraph partitioning. Physical Review A, 100 (3): 032308, September 2019. 10.1103/PhysRevA.100.032308. https://doi.org/10.1103/PhysRevA.100.032308 [16] Omid Daei, Keivan Navi, and Mariam Zomorodi-Moghadam.

Optimized Quantum Circuit Partitioning. International Journal of Theoretical Physics, 59 (12): 3804–3820, December 2020. ISSN 0020-7748, 1572-9575. 10.1007/s10773-020-04633-8. https://doi.org/10.1007/s10773-020-04633-8 [17] Jonathan M. Baker, Casey Duckering, Alexander Hoover, and Frederic T. Chong. Time-sliced quantum circuit partitioning for modular architectures. In Proceedings of the 17th ACM International Conference on Computing Frontiers, CF '20, pages 98–107, New York, NY, USA, May 2020. Association for Computing Machinery. ISBN 978-1-4503-7956-4. 10.1145/3387902.3392617. https://doi.org/10.1145/3387902.3392617 [18] Davood Dadkhah, Mariam Zomorodi, and Seyed Ebrahim Hosseini. A New Approach for Optimization of Distributed Quantum Circuits. International Journal of Theoretical Physics, 60 (9): 3271–3285, September 2021. ISSN 1572-9575. 10.1007/s10773-021-04904-y. https://doi.org/10.1007/s10773-021-04904-y [19] Davide Ferrari, Angela Sara Cacciapuoti, Michele Amoretti, and Marcello Caleffi. Compiler Design for Distributed Quantum Computing. IEEE Transactions on Quantum Engineering, 2: 1–20, 2021. ISSN 2689-1808. 10.1109/TQE.2021.3053921. https://doi.org/10.1109/TQE.2021.3053921 [20] Ranjani G Sundaram, Himanshu Gupta, and C. R. Ramakrishnan. Efficient Distribution of Quantum Circuits.

In Seth Gilbert, editor, 35th International Symposium on Distributed Computing (DISC 2021), volume 209 of Leibniz International Proceedings in Informatics (LIPIcs), pages 41:1–41:20, Dagstuhl, Germany, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. ISBN 978-3-95977-210-5. 10.4230/LIPIcs.DISC.2021.41. https://doi.org/10.4230/LIPIcs.DISC.2021.41 [21] Eesa Nikahd, Naser Mohammadzadeh, Mehdi Sedighi, and Morteza Saheb Zamani. Automated window-based partitioning of quantum circuits. Physica Scripta, 96 (3): 035102, January 2021. ISSN 1402-4896. 10.1088/1402-4896/abd57c. https://doi.org/10.1088/1402-4896/abd57c [22] Jun-Yi Wu, Kosuke Matsui, Tim Forrer, Akihito Soeda, Pablo Andrés-Martínez, Daniel Mills, Luciana Henaut, and Mio Murao. Entanglement-efficient bipartite-distributed quantum computing. Quantum, 7: 1196, December 2023a. 10.22331/q-2023-12-05-1196. https://doi.org/10.22331/q-2023-12-05-1196 [23] Anbang Wu, Hezi Zhang, Gushu Li, Alireza Shabani, Yuan Xie, and Yufei Ding. AutoComm: A Framework for Enabling Efficient Communication in Distributed Quantum Programs. In 2022 55th IEEE/ACM International Symposium on Microarchitecture (MICRO), pages 1027–1041, Chicago, IL, USA, October 2022. IEEE. ISBN 978-1-6654-6272-3. 10.1109/MICRO56248.2022.00074. https://doi.org/10.1109/MICRO56248.2022.00074 [24] Anbang Wu, Yufei Ding, and Ang Li. QuComm: Optimizing Collective Communication for Distributed Quantum Computing. In Proceedings of the 56th Annual IEEE/ACM International Symposium on Microarchitecture, MICRO '23, pages 479–493, New York, NY, USA, December 2023b. Association for Computing Machinery. ISBN 979-8-4007-0329-4. 10.1145/3613424.3614253. https://doi.org/10.1145/3613424.3614253 [25] Daniele Cuomo, Marcello Caleffi, Kevin Krsulich, Filippo Tramonto, Gabriele Agliardi, Enrico Prati, and Angela Sara Cacciapuoti. Optimized Compiler for Distributed Quantum Computing. ACM Transactions on Quantum Computing, 4 (2): 1–29, June 2023. ISSN 2643-6809, 2643-6817. 10.1145/3579367. https://doi.org/10.1145/3579367 [26] Davide Ferrari, Stefano Carretta, and Michele Amoretti. A Modular Quantum Compilation Framework for Distributed Quantum Computing. IEEE Transactions on Quantum Engineering, 4: 1–13, 2023. ISSN 2689-1808. 10.1109/TQE.2023.3303935. https://doi.org/10.1109/TQE.2023.3303935 [27] Pau Escofet, Anabel Ovide, Carmen G. Almudever, Eduard Alarcón, and Sergi Abadal.

Hungarian Qubit Assignment for Optimized Mapping of Quantum Circuits on Multi-Core Architectures. IEEE Computer Architecture Letters, 22 (2): 161–164, July 2023. ISSN 1556-6064. 10.1109/LCA.2023.3318857. https://doi.org/10.1109/LCA.2023.3318857 [28] Leo Sünkel, Manik Dawar, and Thomas Gabor. Applying an Evolutionary Algorithm to Minimize Teleportation Costs in Distributed Quantum Computing. In 2024 IEEE International Conference on Quantum Computing and Engineering (QCE), volume 02, pages 167–172, September 2024. 10.1109/QCE60285.2024.10272. https://doi.org/10.1109/QCE60285.2024.10272 [29] Xinyu Chen, Zilu Chen, Xueyun Cheng, and Zhijin Guan. Circuit Partitioning and Transmission Cost Optimization in Distributed Quantum Computing. arXiv preprint, (arXiv:2407.05953), September 2024. 10.48550/arXiv.2407.05953. https://doi.org/10.48550/arXiv.2407.05953 arXiv:2407.05953 [30] Oliver Crampton, Panagiotis Promponas, Richard Chen, Paul Polakos, Leandros Tassiulas, and Louis Samuel. A Genetic Approach to Minimising Gate and Qubit Teleportations for Multi-Processor Quantum Circuit Distribution. Journal of Quantum Computing, 7: 1–15, 2025. ISSN 2579-0137, 2579-0145. 10.32604/jqc.2025.061275. https://doi.org/10.32604/jqc.2025.061275 [31] Waldemir Cambiucci and Regina Melo Silveira.

Hypergraphic Partitioning Framework for Static and Adaptive Quantum Circuits. In 2025 23rd International Symposium on Network Computing and Applications (NCA), pages 174–181, November 2025. 10.1109/NCA67271.2025.00037. https://doi.org/10.1109/NCA67271.2025.00037 [32] Panagiotis Promponas, Akrit Mudvari, Luca Della Chiesa, Paul Polakos, Louis Samuel, and Leandros Tassiulas. Compiler for Distributed Quantum Computing: A Reinforcement Learning Approach. In ICC 2025 - IEEE International Conference on Communications, pages 4615–4621, June 2025. 10.1109/ICC52391.2025.11161115. https://doi.org/10.1109/ICC52391.2025.11161115 [33] Eneet Kaur, Hassan Shapourian, Jiapeng Zhao, Michael Kilzer, Ramana Kompella, and Reza Nejabati. Optimized quantum circuit partitioning across multiple quantum processors.

In Quantum Computing, Communication, and Simulation V, volume 13391, pages 152–156. SPIE, March 2025. 10.1117/12.3042502. https://doi.org/10.1117/12.3042502 [34] Pau Escofet, Anabel Ovide, Medina Bandic, Luise Prielinger, Hans van Someren, Sebastian Feld, Eduard Alarcon, Sergi Abadal, and Carmen Almudever. Revisiting the Mapping of Quantum Circuits: Entering the Multi-core Era. ACM Transactions on Quantum Computing, 6 (1): 4:1–4:26, January 2025. 10.1145/3655029. https://doi.org/10.1145/3655029 [35] Enrico Russo, Elio Vinciguerra, Maurizio Palesi, Davide Patti, Giuseppe Ascia, and Vincenzo Catania. TeleSABRE: Layout Synthesis in Multi-Core Quantum Systems with Teleport Interconnect. arXiv preprint, (arXiv:2505.08928), May 2025. 10.48550/arXiv.2505.08928. https://doi.org/10.48550/arXiv.2505.08928 arXiv:2505.08928 [36] Yingling Mao, Yu Liu, and Yuanyuan Yang. Qubit Allocation for Distributed Quantum Computing. In IEEE INFOCOM 2023 - IEEE Conference on Computer Communications, pages 1–10, May 2023. 10.1109/INFOCOM53939.2023.10228915. https://doi.org/10.1109/INFOCOM53939.2023.10228915 [37] B. W. Kernighan and S. Lin. An efficient heuristic procedure for partitioning graphs.

The Bell System Technical Journal, 49 (2): 291–307, February 1970. ISSN 0005-8580. 10.1002/j.1538-7305.1970.tb01770.x. https://doi.org/10.1002/j.1538-7305.1970.tb01770.x [38] C.M. Fiduccia and R.M. Mattheyses. A Linear-Time Heuristic for Improving Network Partitions. In 19th Design Automation Conference, pages 175–181, June 1982. 10.1109/DAC.1982.1585498. https://doi.org/10.1109/DAC.1982.1585498 [39] L. A. Sanchis. Multiple-Way Network Partitioning. IEEE Trans. Comput., 38 (1): 62–81, January 1989. ISSN 0018-9340. 10.1109/12.8730. https://doi.org/10.1109/12.8730 [40] Jason Cong and M'Lissa Smith. A parallel bottom-up clustering algorithm with applications to circuit partitioning in VLSI design. In Proceedings of the 30th International on Design Automation Conference - DAC '93, pages 755–760, Dallas, Texas, United States, 1993. ACM Press. ISBN 978-0-89791-577-9. 10.1145/157485.165119. https://doi.org/10.1145/157485.165119 [41] Frank M. Johannes. Partitioning of VLSI circuits and systems. In Proceedings of the 33rd Annual Conference on Design Automation Conference - DAC '96, pages 83–87, Las Vegas, Nevada, United States, 1996. ACM Press. ISBN 978-0-89791-779-7. 10.1145/240518.240535. https://doi.org/10.1145/240518.240535 [42] Dennis J.-H. Huang and Andrew B. Kahng. Partitioning-based standard-cell global placement with an exact objective. In Proceedings of the 1997 International Symposium on Physical Design, ISPD '97, pages 18–25, New York, NY, USA, April 1997. Association for Computing Machinery. ISBN 978-0-89791-927-2. 10.1145/267665.267674. https://doi.org/10.1145/267665.267674 [43] George Karypis, Rajat Aggarwal, Vipin Kumar, and Shashi Shekhar. Multilevel hypergraph partitioning: Application in VLSI domain. In Proceedings of the 34th Annual Design Automation Conference, DAC '97, pages 526–529, New York, NY, USA, June 1997. Association for Computing Machinery. ISBN 978-0-89791-920-3. 10.1145/266021.266273. https://doi.org/10.1145/266021.266273 [44] George Karypis and Vipin Kumar. A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs. SIAM Journal on Scientific Computing, 20 (1): 359–392, January 1998. ISSN 1064-8275, 1095-7197. 10.1137/S1064827595287997. https://doi.org/10.1137/S1064827595287997 [45] George Karypis and Vipin Kumar. Multilevel k -way hypergraph partitioning. In Proceedings of the 36th Annual ACM/IEEE Design Automation Conference, pages 343–348, New Orleans Louisiana USA, June 1999. ACM. ISBN 978-1-58113-109-3. 10.1145/309847.309954. https://doi.org/10.1145/309847.309954 [46] Henning Meyerhenke, Peter Sanders, and Christian Schulz.

Partitioning Complex Networks via Size-constrained Clustering. arXiv preprint, (arXiv:1402.3281), March 2014. 10.48550/arXiv.1402.3281. https://doi.org/10.48550/arXiv.1402.3281 arXiv:1402.3281 [47] Sebastian Schlag, Tobias Heuer, Lars Gottesbüren, Yaroslav Akhremtsev, Christian Schulz, and Peter Sanders. High-Quality Hypergraph Partitioning. ACM J. Exp. Algorithmics, 27: 1.9:1–1.9:39, February 2023. ISSN 1084-6654. 10.1145/3529090. https://doi.org/10.1145/3529090 [48] George Karypis and Vipin Kumar. Metis—a software package for partitioning unstructured graphs, partitioning meshes and computing fill-reducing ordering of sparse matrices. 01 1997. [49] Felix Burt, Kuan-Cheng Chen, and Kin K. Leung. Entanglement-efficient distribution of quantum circuits over large-scale quantum networks. In 2025 IEEE International Conference on Quantum Computing and Engineering (QCE), volume 01, pages 1111–1122, 2025. 10.1109/QCE65121.2025.00125. https://doi.org/10.1109/QCE65121.2025.00125 [50] Felix Burt. Felix-burt/DISQCO. https://github.com/felix-burt/DISQCO, 2025. https://github.com/felix-burt/DISQCO [51] Tianyi Peng, Aram Harrow, Maris Ozols, and Xiaodi Wu.

Simulating Large Quantum Circuits on a Small Quantum Computer.

Physical Review Letters, 125 (15): 150504, October 2020. ISSN 0031-9007, 1079-7114. 10.1103/PhysRevLett.125.150504. https://doi.org/10.1103/PhysRevLett.125.150504 [52] Wei Tang, Teague Tomesh, Martin Suchara, Jeffrey Larson, and Margaret Martonosi. CutQC: Using small Quantum computers for large Quantum circuit evaluations. In Proceedings of the 26th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS '21, pages 473–486, New York, NY, USA, April 2021. Association for Computing Machinery. ISBN 978-1-4503-8317-2. 10.1145/3445814.3446758. https://doi.org/10.1145/3445814.3446758 [53] Wei Tang and Margaret Martonosi.

Cutting Quantum Circuits to Run on Quantum and Classical Platforms. arXiv preprint, (arXiv:2205.05836), May 2022. 10.48550/arXiv.2205.05836. https://doi.org/10.48550/arXiv.2205.05836 arXiv:2205.05836 [54] Saikat Basu, Arnav Das, Amit Saha, Amlan Chakrabarti, and Susmita Sur-Kolay. FragQC: An efficient quantum error reduction technique using quantum circuit fragmentation. Journal of Systems and Software, 214: 112085, August 2024. ISSN 0164-1212. 10.1016/j.jss.2024.112085. https://doi.org/10.1016/j.jss.2024.112085 [55] Teague Tomesh, Zain H. Saleem, Michael A. Perlin, Pranav Gokhale, Martin Suchara, and Margaret Martonosi. Divide and Conquer for Combinatorial Optimization and Distributed Quantum Computation. In 2023 IEEE International Conference on Quantum Computing and Engineering (QCE), volume 01, pages 1–12, September 2023. 10.1109/QCE57702.2023.00009. https://doi.org/10.1109/QCE57702.2023.00009 [56] Marvin Bechtold, Johanna Barzen, Frank Leymann, Alexander Mandl, Julian Obst, Felix Truger, and Benjamin Weder. Investigating the effect of circuit cutting in QAOA for the MaxCut problem on NISQ devices. Quantum Science and Technology, 8 (4): 045022, October 2023. ISSN 2058-9565. 10.1088/2058-9565/acf59c. https://doi.org/10.1088/2058-9565/acf59c [57] Turbasu Chatterjee, Arnav Das, Shah Ishmam Mohtashim, Amit Saha, and Amlan Chakrabarti. Qurzon: A Prototype for a Divide and Conquer-Based Quantum Compiler for Distributed Quantum Systems. SN Computer Science, 3 (4): 323, June 2022. ISSN 2661-8907. 10.1007/s42979-022-01207-9. https://doi.org/10.1007/s42979-022-01207-9 [58] Sebastian Brandhofer, Ilia Polian, and Kevin Krsulich. Optimal Partitioning of Quantum Circuits Using Gate Cuts and Wire Cuts. IEEE Transactions on Quantum Engineering, 5: 1–10, 2024. ISSN 2689-1808. 10.1109/TQE.2023.3347106. https://doi.org/10.1109/TQE.2023.3347106 [59] David P. DiVincenzo and IBM.

The Physical Implementation of Quantum Computation. Fortschritte der Physik, 48 (9-11): 771–783, September 2000. ISSN 00158208, 15213978. 10.1002/1521-3978(200009)48:9/113.0.CO;2-E. https://doi.org/10.1002/1521-3978(200009)48:9/113.0.CO;2-E [60] Charles H. Bennett, Gilles Brassard, Claude Crépeau, Richard Jozsa, Asher Peres, and William K. Wootters. Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels.

Physical Review Letters, 70 (13): 1895–1899, March 1993. 10.1103/PhysRevLett.70.1895. https://doi.org/10.1103/PhysRevLett.70.1895 [61] Daniel Gottesman and Isaac L. Chuang. Demonstrating the viability of universal quantum computation using teleportation and single-qubit operations. Nature, 402 (6760): 390–393, November 1999. ISSN 1476-4687. 10.1038/46503. https://doi.org/10.1038/46503 [62] J. Eisert, K. Jacobs, P. Papadopoulos, and M. B. Plenio. Optimal local implementation of nonlocal quantum gates. Physical Review A, 62 (5): 052317, October 2000. 10.1103/PhysRevA.62.052317. https://doi.org/10.1103/PhysRevA.62.052317 [63] Anocha Yimsiriwattana and Samuel J. Lomonaco Jr. Generalized GHZ States and Distributed Quantum Computing. arXiv preprint, (arXiv:quant-ph/0402148), March 2004. arXiv:quant-ph/0402148 [64] Felix Burt, Kuan-Cheng Chen, and Kin K. Leung.

Generalised Circuit Partitioning for Distributed Quantum Computing. In 2024 IEEE International Conference on Quantum Computing and Engineering (QCE), volume 02, pages 173–178, September 2024. 10.1109/QCE60285.2024.10273. https://doi.org/10.1109/QCE60285.2024.10273 [65] Anocha Yimsiriwattana and Samuel J. Lomonaco Jr. Distributed quantum computing: A distributed Shor algorithm.

In Eric Donkor, Andrew R. Pirich, and Howard E. Brandt, editors, Defense and Security, page 360, Orlando, FL, August 2004. 10.1117/12.546504. https://doi.org/10.1117/12.546504 [66] Pablo Andres-Martinez, Tim Forrer, Daniel Mills, Jun-Yi Wu, Luciana Henaut, Kentaro Yamamoto, Mio Murao, and Ross Duncan. Distributing circuits over heterogeneous, modular quantum computing network architectures. Quantum Science and Technology, 9 (4): 045021, August 2024a. ISSN 2058-9565. 10.1088/2058-9565/ad6734. https://doi.org/10.1088/2058-9565/ad6734 [67] Ali Javadi-Abhari, Matthew Treinish, Kevin Krsulich, Christopher J. Wood, Jake Lishman, Julien Gacon, Simon Martiel, Paul D. Nation, Lev S. Bishop, Andrew W. Cross, Blake R. Johnson, and Jay M. Gambetta. Quantum computing with Qiskit. arXiv preprint, (arXiv:2405.08810), June 2024. 10.48550/arXiv.2405.08810. https://doi.org/10.48550/arXiv.2405.08810 arXiv:2405.08810 [68] Seyon Sivarajah, Silas Dilkes, Alexander Cowtan, Will Simmons, Alec Edgington, and Ross Duncan. t|ket$\rangle$: A retargetable compiler for NISQ devices. Quantum Science and Technology, 6 (1): 014003, November 2020. ISSN 2058-9565. 10.1088/2058-9565/ab8e92. https://doi.org/10.1088/2058-9565/ab8e92 [69] Ranjani G. Sundaram, Himanshu Gupta, and C. R. Ramakrishnan. Distribution of Quantum Circuits Over General Quantum Networks. In 2022 IEEE International Conference on Quantum Computing and Engineering (QCE), pages 415–425, September 2022. 10.1109/QCE53715.2022.00063. https://doi.org/10.1109/QCE53715.2022.00063 [70] Giorgio Ausiello and Luigi Laura. Directed hypergraphs: Introduction and fundamental algorithms—A survey.

Theoretical Computer Science, 658: 293–306, January 2017. ISSN 0304-3975. 10.1016/j.tcs.2016.03.016. https://doi.org/10.1016/j.tcs.2016.03.016 [71] Hyunho Cha and Jungwoo Lee. Module-conditioned distribution of quantum circuits. arXiv preprint, (arXiv:2501.11816), January 2025. 10.48550/arXiv.2501.11816. https://doi.org/10.48550/arXiv.2501.11816 arXiv:2501.11816 [72] Andrew W. Cross, Lev S. Bishop, Sarah Sheldon, Paul D. Nation, and Jay M. Gambetta. Validating quantum computers using randomized model circuits. Physical Review A, 100 (3): 032328, September 2019. ISSN 2469-9926, 2469-9934. 10.1103/PhysRevA.100.032328. https://doi.org/10.1103/PhysRevA.100.032328 [73] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A Quantum Approximate Optimization Algorithm. arXiv preprint, (arXiv:1411.4028), November 2014. 10.48550/arXiv.1411.4028. https://doi.org/10.48550/arXiv.1411.4028 arXiv:1411.4028 [74] Ang Li, Samuel Stein, Sriram Krishnamoorthy, and James Ang. Qasmbench: A low-level quantum benchmark suite for nisq evaluation and simulation. ACM Transactions on Quantum Computing, 4 (2), February 2023. 10.1145/3550488. URL https://doi.org/10.1145/3550488. https://doi.org/10.1145/3550488 [75] Pablo Andres-Martinez, Daniel Mills, Tim Forrer, and Luciana Henaut. CQCL/pytket-dqc. Quantinuum Ltd, June 2024b. [76] Joshua Ramette, Josiah Sinclair, Nikolas P. Breuckmann, and Vladan Vuletić. Fault-tolerant connection of error-corrected qubits with noisy links. npj Quantum Information, 10 (1): 1–6, June 2024. ISSN 2056-6387. 10.1038/s41534-024-00855-4. https://doi.org/10.1038/s41534-024-00855-4 [77] C. Ryan-Anderson, N. C. Brown, C. H. Baldwin, J. M. Dreiling, C. Foltz, J. P. Gaebler, T. M. Gatterman, N. Hewitt, C. Holliman, C. V. Horst, J. Johansen, D. Lucchetti, T. Mengle, M. Matheny, Y. Matsuoka, K. Mayer, M. Mills, S. A. Moses, B. Neyenhuis, J. Pino, P. Siegfried, R. P. Stutz, J. Walker, and D. Hayes. High-fidelity teleportation of a logical qubit using transversal gates and lattice surgery. Science, 385 (6715): 1327–1331, September 2024. 10.1126/science.adp6016. https://doi.org/10.1126/science.adp6016 [78] John Stack, Ming Wang, and Frank Mueller. Assessing Teleportation of Logical Qubits in a Distributed Quantum Architecture under Error Correction. arXiv pre-print, (arXiv:2504.05611), April 2025. 10.48550/arXiv.2504.05611. https://doi.org/10.48550/arXiv.2504.05611 arXiv:2504.05611 [79] Dominic Horsman, Austin G Fowler, Simon Devitt, and Rodney Van Meter. Surface code quantum computing by lattice surgery. New Journal of Physics, 14 (12): 123011, December 2012. ISSN 1367-2630. 10.1088/1367-2630/14/12/123011. https://doi.org/10.1088/1367-2630/14/12/123011 [80] Áron Márton, Luis Colmenarez, Lukas Bödeker, and Markus Müller. Lattice surgery-based logical state teleportation via noisy links. Phys. Rev. Res., 7: 033238, Sep 2025. 10.1103/ppng-vbqj. URL https://doi.org/10.1103/ppng-vbqj. https://doi.org/10.1103/ppng-vbqj [81] Alexander Erhard, Hendrik Poulsen Nautrup, Michael Meth, Lukas Postler, Roman Stricker, Martin Ringbauer, Philipp Schindler, Hans J. Briegel, Rainer Blatt, Nicolai Friis, and Thomas Monz. Entangling logical qubits with lattice surgery. Nature, 589 (7841): 220–224, January 2021. ISSN 0028-0836, 1476-4687. 10.1038/s41586-020-03079-6. https://doi.org/10.1038/s41586-020-03079-6 [82] Trond Hjerpekjøn Haug, Timo Hillmann, Anton Frisk Kockum, and Raphaël Van Laer. Lattice surgery with Bell measurements: Modular fault-tolerant quantum computation at low entanglement cost. arXiv pre-print, (arXiv:2510.13541), October 2025. 10.48550/arXiv.2510.13541. https://doi.org/10.48550/arXiv.2510.13541 arXiv:2510.13541 [83] Hugo Jacinto, Élie Gouzien, and Nicolas Sangouard. Network Requirements for Distributed Quantum Computation. arXiv pre-print, (arXiv:2504.08891), April 2025. 10.48550/arXiv.2504.08891. https://doi.org/10.48550/arXiv.2504.08891 arXiv:2504.08891 [84] Mohamed A. Shalby, Renyu Wang, Denis Sedov, and Leonid P. Pryadko. Optimized noise-resilient surface code teleportation interfaces. Physical Review A, 112 (2): L020403, August 2025. 10.1103/xqrn-wdw1. https://doi.org/10.1103/xqrn-wdw1 [85] Theodore J. Yoder, Eddie Schoute, Patrick Rall, Emily Pritchett, Jay M. Gambetta, Andrew W. Cross, Malcolm Carroll, and Michael E. Beverland. Tour de gross: A modular quantum computer based on bivariate bicycle codes. arXiv pre-print, (arXiv:2506.03094), June 2025. 10.48550/arXiv.2506.03094. https://doi.org/10.48550/arXiv.2506.03094 arXiv:2506.03094 [86] Zhiyang He, Alexander Cowtan, Dominic J. Williamson, and Theodore J. Yoder. Extractors: QLDPC Architectures for Efficient Pauli-Based Computation. arXiv pre-print, (arXiv:2503.10390), March 2025. 10.48550/arXiv.2503.10390. https://doi.org/10.48550/arXiv.2503.10390 arXiv:2503.10390 [87] Evan Sutcliffe, Bhargavi Jonnadula, Claire Le Gall, Alexandra E. Moylett, and Coral M. Westoby. Distributed quantum error correction based on hyperbolic floquet codes. In 2025 IEEE International Conference on Quantum Computing and Engineering (QCE), volume 01, pages 649–657, 2025. 10.1109/QCE65121.2025.00076. https://doi.org/10.1109/QCE65121.2025.00076 [88] Oscar Higgott and Nikolas P. Breuckmann. Constructions and Performance of Hyperbolic and Semi-Hyperbolic Floquet Codes. PRX Quantum, 5 (4): 040327, November 2024. ISSN 2691-3399. 10.1103/PRXQuantum.5.040327. https://doi.org/10.1103/PRXQuantum.5.040327Cited byCould not fetch Crossref cited-by data during last attempt 2026-01-22 12:35:13: cURL error 28: Operation timed out after 10001 milliseconds with 0 bytes received Could not fetch ADS cited-by data during last attempt 2026-01-22 12:35:23: No response from ADS or unable to decode the received json data when getting the list of citing works.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. AbstractExecuting quantum algorithms over distributed quantum systems requires quantum circuits to be divided into sub-circuits which communicate via entanglement-based teleportation. Naively mapping circuits to qubits over multiple quantum processing units (QPUs) results in large communication overhead, increasing both execution time and noise. This can be minimised by optimising the assignment of qubits to QPUs and the methods used for covering non-local operations. Formulations that are general enough to capture the spectrum of teleportation possibilities lead to complex problem instances which can be difficult to solve effectively. This highlights a need to exploit the wide range of heuristic techniques used in the graph partitioning literature. This paper formalises and extends existing constructions for graphical quantum circuit partitioning and designs a new objective function that captures further possibilities for non-local operations via $\textit{nested state teleportation}$. We adapt the well-known Fiduccia-Mattheyses heuristic to the constraints and problem objective and explore multilevel techniques that coarsen hypergraphs and partition at multiple levels of granularity. We find that this reduces runtime and improves solution quality of standard partitioning. We place these techniques within a larger framework, through which we can extract full distributed quantum circuits including teleportation instructions. We compare the entanglement requirements and runtimes with state-of-the-art methods, finding that we achieve the lowest entanglement costs in most cases. Averaging over a wide range of circuits, we reduce the entanglement requirements by 35% compared with the next best-performing method. We also find that our techniques can scale to much larger circuit sizes than competing methods, provided the number of partitions is not too large.Featured image: Starting with a fine-grained temporal hypergraph representing a quantum circuit, the time dimension is coarsened away until an ordinary, 'static', hypergraph remains. The time dimension is then gradually re-introduced while iteratively optimising the partitioning, resulting in a low cost final solution.The methods developed in this work are implemented in an open-source software tool called DisQCO (Distributed Quantum Circuit Optimisation), available on GitHub. Popular summaryAs quantum computers grow larger, they are increasingly being built as networks of smaller machines connected by light. In these modular and distributed architectures, multiple matter-based quantum processing units (QPUs) are linked using photonic connections that distribute entanglement between devices. This enables universal quantum computing through teleportation, but at a cost: entanglement generation is typically slow and imperfect, and excessive communication can significantly degrade computational performance. To address this, researchers have developed various techniques for partitioning quantum circuits, which involves breaking a large circuit into smaller pieces that run on separate QPUs while minimising communication between them. Most existing approaches are built around a single, specific way of using teleportation, which makes them powerful in narrow settings but inflexible across the wide diversity of real quantum circuits. In this work, we introduce a circuit partitioning framework based on hypergraphs with an explicit temporal dimension that is agnostic to how entanglement is used for communication. The construction allows the assignment of qubits to QPUs and the kind of teleportation used all to be directly optimised through partitioning. While this generality enables the method to handle a broad range of circuits, scalability remains a key challenge for large problem instances. To address this, we exploit multilevel partitioning techniques. We introduce a temporal coarsening procedure that produces a hierarchy of progressively smaller graphs with decreasing time resolution. Intuitively, this lets the optimiser first reason about a circuit in broad strokes over time, and then refine its decisions at finer and finer temporal scales. By performing partitioning across this hierarchy, we gradually transform a conventional, static hypergraph problem into a fully temporal one, achieving solutions that are both faster to compute and more effective at reducing communication. Using this approach, our framework partitions circuits using, on average, 35% less entanglement than state-of-the-art methods. ► BibTeX data@article{Burt2026multilevelframework, doi = {10.22331/q-2026-01-22-1984}, url = {https://doi.org/10.22331/q-2026-01-22-1984}, title = {A {M}ultilevel {F}ramework for {P}artitioning {Q}uantum {C}ircuits}, author = {Burt, Felix and Chen, Kuan-Cheng and Leung, Kin K.}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {1984}, month = jan, year = {2026} }► References [1] Marcello Caleffi, Michele Amoretti, Davide Ferrari, Jessica Illiano, Antonio Manzalini, and Angela Sara Cacciapuoti. Distributed quantum computing: A survey. Computer Networks, 254: 110672, December 2024. ISSN 1389-1286. 10.1016/j.comnet.2024.110672. https://doi.org/10.1016/j.comnet.2024.110672 [2] Nemanja Isailovic, Yatish Patel, Mark Whitney, and John Kubiatowicz. Interconnection Networks for Scalable Quantum Computers. ACM SIGARCH Computer Architecture News, 34 (2): 366–377, May 2006. ISSN 0163-5964. 10.1145/1150019.1136505. https://doi.org/10.1145/1150019.1136505 [3] M. Akhtar, F. Bonus, F. R. Lebrun-Gallagher, N. I. Johnson, M. Siegele-Brown, S. Hong, S. J. Hile, S. A. Kulmiya, S. Weidt, and W. K. Hensinger. A high-fidelity quantum matter-link between ion-trap microchip modules. Nature Communications, 14 (1): 531, February 2023. ISSN 2041-1723. 10.1038/s41467-022-35285-3. https://doi.org/10.1038/s41467-022-35285-3 [4] V. Krutyanskiy, M. Galli, V. Krcmarsky, S. Baier, D. A. Fioretto, Y. Pu, A. Mazloom, P. Sekatski, M. Canteri, M. Teller, J. Schupp, J. Bate, M. Meraner, N. Sangouard, B. P. Lanyon, and T. E. Northup. Entanglement of Trapped-Ion Qubits Separated by 230 Meters.

Simulating Large Quantum Circuits on a Small Quantum Computer.

Read Original

Source Information

Source: Quantum Science and Technology (arXiv overlay)

Website: https://quantum-journal.org/feed

A Multilevel Framework for Partitioning Quantum Circuits

Tags

Source Information