Cutting multi-control quantum gates with ZX calculus

Christian Ufrecht; Maniraman Periyasamy; Sebastian Rietsch; Daniel D. Scherer; Axel Plinge; Christopher Mutschler

doi:10.22331/q-2023-10-23-1147

Cutting multi-control quantum gates with ZX calculus

Christian Ufrecht, Maniraman Periyasamy, Sebastian Rietsch, Daniel D. Scherer, Axel Plinge, and Christopher Mutschler

Fraunhofer IIS, Fraunhofer Institute for Integrated Circuits IIS, Division Positioning and Networks, Nuremberg, Germany

Published:	2023-10-23, volume 7, page 1147
Eprint:	arXiv:2302.00387v2
Doi:	https://doi.org/10.22331/q-2023-10-23-1147
Citation:	Quantum 7, 1147 (2023).

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

Abstract

Circuit cutting, the decomposition of a quantum circuit into independent partitions, has become a promising avenue towards experiments with larger quantum circuits in the noisy-intermediate scale quantum (NISQ) era. While previous work focused on cutting qubit wires or two-qubit gates, in this work we introduce a method for cutting multi-controlled Z gates. We construct a decomposition and prove the upper bound $\mathcal{O}(6^{2K})$ on the associated sampling overhead, where $K$ is the number of cuts in the circuit. This bound is independent of the number of control qubits but can be further reduced to $\mathcal{O}(4.5^{2K})$ for the special case of CCZ gates. Furthermore, we evaluate our proposal on IBM hardware and experimentally show noise resilience due to the strong reduction of CNOT gates in the cut circuits.

► BibTeX data

@article{Ufrecht2023cuttingmulticontrol,
  doi = {10.22331/q-2023-10-23-1147},
  url = {https://doi.org/10.22331/q-2023-10-23-1147},
  title = {Cutting multi-control quantum gates with {ZX} calculus},
  author = {Ufrecht, Christian and Periyasamy, Maniraman and Rietsch, Sebastian and Scherer, Daniel D. and Plinge, Axel and Mutschler, Christopher},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {7},
  pages = {1147},
  month = oct,
  year = {2023}
}

► References

[1] M. A. Nielsen and I. L. Chuang. ``Quantum computation and quantum information: 10th anniversary edition''. Cambridge University Press. (2010).
https://doi.org/10.1017/CBO9780511976667

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

[3] P.W. Shor. ``Algorithms for quantum computation: discrete logarithms and factoring''. In Proceedings 35th Annual Symposium on Foundations of Computer Science. Page 124. IEEE Comput. Soc. Press (1994).
https://doi.org/10.1109/SFCS.1994.365700

[4] L. K. Grover. ``A fast quantum mechanical algorithm for database search''. In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing. Page 212. New York, NY, USA (1996). Association for Computing Machinery.
https://doi.org/10.1145/237814.237866

[5] E. Farhi, J. Goldstone, and S. Gutmann. ``A quantum approximate optimization algorithm'' (2014). arXiv:1411.4028.
arXiv:1411.4028

[6] ``IBM Development Roadmap 2022''. https://www.ibm.com/quantum/roadmap. Accessed: 2023-01-02.
https://www.ibm.com/quantum/roadmap

[7] T. Peng, A. W. Harrow, M. Ozols, and X. Wu. ``Simulating large quantum circuits on a small quantum computer''. Phys. Rev. Lett. 125, 150504 (2020).
https://doi.org/10.1103/PhysRevLett.125.150504

[8] M. A. Perlin, Z. H. Saleem, M. Suchara, and J. C. Osborn. ``Quantum circuit cutting with maximum-likelihood tomography''. NPJ Quantum Inf. 7, 64 (2021).
https://doi.org/10.1038/s41534-021-00390-6

[9] G. Uchehara, T. M. Aamodt, and O. Di Matteo. ``Rotation-inspired circuit cut optimization''. In 2022 IEEE/ACM Third International Workshop on Quantum Computing Software (QCS). Page 50. Los Alamitos, CA, USA (2022). IEEE Computer Society.
https://doi.org/10.1109/QCS56647.2022.00011

[10] D. Chen, B. Baheri, V. Chaudhary, Q. Guan, N. Xie, and S. Xu. ``Approximate quantum circuit reconstruction''. In 2022 IEEE International Conference on Quantum Computing and Engineering (QCE). Page 509. (2022).
https://doi.org/10.1109/QCE53715.2022.00073

[11] C. Ying, B. Cheng, Y. Zhao, H.-L. Huang, Y.-N. Zhang, M. Gong, Y. Wu, S. Wang, F. Liang, J. Lin, Y. Xu, H. Deng, H. Rong, C.-Z. Peng, M.-H. Yung, X. Zhu, and J.-W. Pan. ``Experimental simulation of larger quantum circuits with fewer superconducting qubits''. Phys. Rev. Lett. 130, 110601 (2023).
https://doi.org/10.1103/PhysRevLett.130.110601

[12] T. Ayral, F.-M. Le Régent, Z. Saleem, Y. Alexeev, and M. Suchara. ``Quantum divide and compute: Hardware demonstrations and noisy simulations''. In 2020 IEEE Computer Society Annual Symposium on VLSI (ISVLSI). Page 138. (2020).
https://doi.org/10.1109/ISVLSI49217.2020.00034

[13] T. Ayral, F.-M. Le Régent, Z. Saleem, Y. Alexeev, and M. Suchara. ``Quantum divide and compute: Exploring the effect of different noise sources''. SN comput. sci. 2, 132 (2021).
https://doi.org/10.1007/s42979-021-00508-9

[14] J. Liu, A. Gonzales, and Z. H. Saleem. ``Classical simulators as quantum error mitigators via circuit cutting'' (2022). arXiv:2212.07335.
arXiv:2212.07335

[15] R. Majumdar and C. J. Wood. ``Error mitigated quantum circuit cutting'' (2022). arXiv:2211.13431.
arXiv:2211.13431

[16] W. Tang, T. Tomesh, M. Suchara, J. Larson, and M. 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. Page 473. ASPLOS 2021New York, NY, USA (2021). Association for Computing Machinery.
https://doi.org/10.1145/3445814.3446758

[17] W. Tang and M. Martonosi. ``ScaleQC: A scalable framework for hybrid computation on quantum and classical processors'' (2022). arXiv:2207.00933.
arXiv:2207.00933

[18] T. Chatterjee, A. Das, S. I. Mohtashim, A. Saha, and A. Chakrabarti. ``Qurzon: A prototype for a divide and conquer-based quantum compiler for distributed quantum systems''. SN Computer Science 3, 323 (2022).
https://doi.org/10.1007/s42979-022-01207-9

[19] K. Mitarai and K. Fujii. ``Methodology for replacing indirect measurements with direct measurements''. Phys. Rev. Research 1, 013006 (2019).
https://doi.org/10.1103/PhysRevResearch.1.013006

[20] K. Mitarai and K. Fujii. ``Constructing a virtual two-qubit gate by sampling single-qubit operations''. New J. Phys. 23, 023021 (2021).
https://doi.org/10.1088/1367-2630/abd7bc

[21] K. Mitarai and K. Fujii. ``Overhead for simulating a non-local channel with local channels by quasiprobability sampling''. Quantum 5, 388 (2021).
https://doi.org/10.22331/q-2021-01-28-388

[22] K. Temme, S. Bravyi, and J. M. Gambetta. ``Error mitigation for short-depth quantum circuits''. Phys. Rev. Lett. 119, 180509 (2017).
https://doi.org/10.1103/PhysRevLett.119.180509

[23] C. Piveteau, D. Sutter, and S. Woerner. ``Quasiprobability decompositions with reduced sampling overhead''. NPJ Quantum Inf. 8, 12 (2022).
https://doi.org/10.1038/s41534-022-00517-3

[24] C. Piveteau. ``Advanced methods for quasiprobabilistic quantum error mitigation''. Master's thesis. ETH Zurich. (2021). url: https://www.research-collection.ethz.ch/handle/20.500.11850/504508.
https://www.research-collection.ethz.ch/handle/20.500.11850/504508

[25] H. Pashayan, J. J. Wallman, and S. D. Bartlett. ``Estimating outcome probabilities of quantum circuits using quasiprobabilities''. Phys. Rev. Lett. 115, 070501 (2015).
https://doi.org/10.1103/PhysRevLett.115.070501

[26] C. Piveteau and D. Sutter. ``Circuit knitting with classical communication'' (2022). arXiv:2205.00016.
arXiv:2205.00016

[27] G. Vidal and R. Tarrach. ``Robustness of entanglement''. Phys. Rev. A 59, 141 (1999).
https://doi.org/10.1103/PhysRevA.59.141

[28] A. Lowe, M. Medvidović, A. Hayes, L. J. O'Riordan, T. R. Bromley, J. M. Arrazola, and N. Killoran. ``Fast quantum circuit cutting with randomized measurements''. Quantum 7, 934 (2023).
https://doi.org/10.22331/q-2023-03-02-934

[29] Z. H. Saleem, T. Tomesh, M. A. Perlin, P. Gokhale, and M. Suchara. ``Divide and conquer for combinatorial optimization and distributed computing'' (2021). arXiv:2107.07532.
arXiv:2107.07532

[30] S. Hadfield. ``Quantum algorithms for scientific computing and approximate optimization'' (2018). arXiv:1805.03265.
arXiv:1805.03265

[31] T. Yamamoto and R. Ohira. ``Error suppression by a virtual two-qubit gate''. J. Appl. Phys. 133, 174401 (2023).
https://doi.org/10.1063/5.0151037

[32] S. C. Marshall, C. Gyurik, and V. Dunjko. ``High Dimensional Quantum Machine Learning With Small Quantum Computers''. Quantum 7, 1078 (2023).
https://doi.org/10.22331/q-2023-08-09-1078

[33] B. Coecke and R. Duncan. ``Interacting quantum observables: categorical algebra and diagrammatics''. New J. Phys. 13, 043016 (2011).
https://doi.org/10.1088/1367-2630/13/4/043016

[34] B. Coecke and R. Duncan. ``Interacting quantum observables''. In L. Aceto, I. Damgård, L. A. Goldberg, M. M. Halldórsson, A. Ingólfsdóttir, and I. Walukiewicz, editors, Automata, Languages and Programming. Page 298. Berlin, Heidelberg (2008). Springer Berlin Heidelberg.
https://doi.org/10.1007/978-3-540-70583-3_25

[35] J. van de Wetering. ``ZX-calculus for the working quantum computer scientist'' (2020). arXiv:2012.13966.
arXiv:2012.13966

[36] A. Kissinger and J. van de Wetering. ``Simulating quantum circuits with zx-calculus reduced stabiliser decompositions''. Quantum Sci. Technol. 7, 044001 (2022).
https://doi.org/10.1088/2058-9565/ac5d20

[37] A. Kissinger, J. van de Wetering, and R. Vilmart. ``Classical simulation of quantum circuits with partial and graphical stabiliser decompositions''. In F.s Le Gall and T. Morimae, editors, 17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022). Volume 232 of Leibniz International Proceedings in Informatics (LIPIcs), page 5:1. Dagstuhl, Germany (2022).
https://doi.org/10.4230/LIPIcs.TQC.2022.5

[38] M. Backens and A. Kissinger. ``ZH: A complete graphical calculus for quantum computations involving classical non-linearity''. Electron. Proc. Theor. Comput. Sci. 287, 23 (2019).
https://doi.org/10.4204/eptcs.287.2

[39] ``van de Wetering, J.''. Private communication.

[40] ``IBM Quantum''. https://quantum-computing.ibm.com/. Accessed: 2023-01-23.
https://quantum-computing.ibm.com/

[41] A. Barenco, C. H. Bennett, R. Cleve, D. P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. A. Smolin, and H. Weinfurter. ``Elementary gates for quantum computation''. Phys. Rev. A 52, 3457 (1995).
https://doi.org/10.1103/PhysRevA.52.3457

[42] S. Bravyi, G. Smith, and J. A. Smolin. ``Trading classical and quantum computational resources''. Phys. Rev. X 6, 021043 (2016).
https://doi.org/10.1103/PhysRevX.6.021043

[43] ``Github repository MCZ-gate cutting''. https://github.com/ChristianUfrecht/MCZgate_cutting.
https://github.com/ChristianUfrecht/MCZgate_cutting

[44] E. van den Berg, Z. K. Minev, and K. Temme. ``Model-free readout-error mitigation for quantum expectation values''. Phys. Rev. A 105, 032620 (2022).
https://doi.org/10.1103/PhysRevA.105.032620

Cited by

[1] Xiaokun Yang, Xinpeng Li, Jeremy W Turner, Cameron D Disomma, Yunhe Feng, Xuechen Zhang, Vipin Chaudhary, and Shuai Xu, Proceedings of the 35th International Symposium on High-Performance Parallel and Distributed Computing 642 (2026) ISBN:9798400726408.

[2] Hiroyuki Harada, Kaito Wada, and Naoki Yamamoto, "Doubly Optimal Parallel Wire Cutting without Ancilla Qubits", PRX Quantum 5 4, 040308 (2024).

[3] Marvin Bechtold, Johanna Barzen, Frank Leymann, Alexander Mandl, and Felix Truger, "Joint Wire Cutting with Non‐Maximally Entangled States", Advanced Quantum Technologies 8 5, 2400555 (2025).

[4] Dong-Sheng Wang, Xiang Xu, and Yuan-Dong Liu, "Quantum simulation in the entanglement picture", Quantum Review Letters 2, 57 (2026).

[5] Shuwen Kan, Zefan Du, Miguel Palma, Samuel A Stein, Chenxu Liu, Wenqi Wei, Juntao Chen, Ang Li, and Ying Mao, 2024 IEEE International Conference on Quantum Computing and Engineering (QCE) 1077 (2024) ISBN:979-8-3315-4137-8.

[6] 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 (2025).

[7] Philipp Seitz, Manuel Geiger, Christian Ufrecht, Axel Plinge, Christopher Mutschler, Daniel D. Scherer, and Christian B. Mendl, 2024 IEEE International Conference on Quantum Computing and Engineering (QCE) 292 (2024) ISBN:979-8-3315-4137-8.

[8] Bruno Jardim, Jaime Santos, and Luís S. Barbosa, Lecture Notes in Computer Science 15551, 112 (2026) ISBN:978-3-031-94747-6.

[9] Maniraman Periyasamy, Christian Ufrecht, Daniel D. Scherer, and Wolfgang Mauerer, 2025 IEEE International Conference on Quantum Computing and Engineering (QCE) 99 (2025) ISBN:979-8-3315-5736-2.

[10] Dedy Septono Catur Putranto, Rini Wisnu Wardhani, and Howon Kim, "Enhancing Quantum Cryptanalysis of Binary Elliptic Curves Through Optimized Out-of-Place Point Addition and ECPM Integration", IEEE Access 13, 148304 (2025).

[11] Xinpeng Li, Vinooth Kulkarni, Daniel T. Chen, Qiang Guan, Weiwen Jiang, Ning Xie, Shuai Xu, and Vipin Chaudhary, 2024 IEEE International Conference on Quantum Computing and Engineering (QCE) 117 (2024) ISBN:979-8-3315-4137-8.

[12] Mar Tejedor, Berta Casas, Javier Conejero, Alba Cervera-Lierta, and Rosa M. Badia, Proceedings of the SC '25 Workshops of the International Conference for High Performance Computing, Networking, Storage and Analysis 1898 (2025) ISBN:9798400718717.

[13] Xiang Xu, Yuan-Dong Liu, Sha Shi, Yun-Jiang Wang, and Dong-Sheng Wang, "Distributed quantum computing with black-box subroutines", Quantum Science and Technology 10 4, 045014 (2025).

[14] Songqinghao Yang and Prakash Murali, 2025 IEEE International Conference on Quantum Computing and Engineering (QCE) 428 (2025) ISBN:979-8-3315-5736-2.

[15] Gideon Uchehara, Tor M. Aamodt, and Olivia Di Matteo, 2024 IEEE International Conference on Quantum Computing and Engineering (QCE) 1120 (2024) ISBN:979-8-3315-4137-8.

[16] Bob Coecke, Aleks Kissinger, Stefano Gogioso, Selma Dündar-Coecke, Caterina Puca, Lia Yeh, Muhammad Hamza Waseem, Emmanuel M. Pothos, Sieglinde Pfaendler, Vincent Wang-Mascianica, Thomas Cervoni, Ferdi Tomassini, Vincent Anandraj, Peter Sigrist, and Ilyas Khan, "High schoolers excel at Oxford quantum course using pictorial mathematics", Journal of Physics: Conference Series 3189 1, 012008 (2026).

[17] Pouya Kananian and Hans-Arno Jacobsen, Quantum Science and Technology 253 (2026) ISBN:978-3-032-11152-4.

[18] Laura S. Herzog, Lukas Burgholzer, Christian Ufrecht, Daniel D. Scherer, and Robert Wille, 2025 62nd ACM/IEEE Design Automation Conference (DAC) 1 (2025) ISBN:979-8-3315-0304-8.

[19] Himanshu Sahu, Hari Prabhat Gupta, Vishnu Vardhan Puvvada, and Rahul Mishra, "DevQCC: Device-Aware Quantum Circuit Cutting framework with applications in quantum machine learning", Quantum Machine Intelligence 7 2, 89 (2025).

[20] Vinooth Kulkarni, Aaron Orenstein, Xinpeng Li, Shuai Xu, Daniel Blankenberg, and Vipin Chaudhary, 2025 Supercomputing India (SCI) 1 (2025) ISBN:979-8-3315-5758-4.

[21] Guangwu Hou, Changhua Zhu, and Yi Sun, "Multi-objective simulated annealing-based quantum circuit cutting for distributed quantum computation", Physica Scripta 99 11, 115108 (2024).

[22] Junxiang Huang, Yunxin Tang, and Xiao Yuan, "Estimating local observables via cluster-level light-cone decomposition", Physical Review A 113 3, 032414 (2026).

[23] Shuwen Kan, Yanni Li, Hao Wang, Sara Mouradian, and Ying Mao, 2025 IEEE/ACM International Conference On Computer Aided Design (ICCAD) 1 (2025) ISBN:979-8-3315-1560-7.

[24] Marvin Bechtold, Johanna Barzen, Frank Leymann, and Alexander Mandl, 2024 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW) 1136 (2024) ISBN:979-8-3503-6460-6.

[25] Christian Ufrecht, Laura S. Herzog, Daniel D. Scherer, Maniraman Periyasamy, Sebastian Rietsch, Axel Plinge, and Christopher Mutschler, "Optimal joint cutting of two-qubit rotation gates", Physical Review A 109 5, 052440 (2024).

[26] Nathaniel Tornow, Emmanouil Giortamis, and Pramod Bhatotia, "QVM: Quantum Gate Virtualization Machine", Proceedings of the ACM on Programming Languages 9 PLDI, 993 (2025).

[27] 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 (2024).

[28] Philipp Seitz, Manuel Geiger, and Christian B. Mendl, ISC High Performance 2024 Research Paper Proceedings (39th International Conference) 1 (2024) ISBN:978-3-9826336-0-2.

[29] Junya Nakamura, Takahiko Satoh, and Shinichiro Sanji, "Improved sampling bounds and scalable partitioning for quantum circuit cutting beyond bipartitions", Physical Review A 112 4, 042422 (2025).

[30] Nathaniel Tornow, Christian B. Mendl, and Pramod Bhatotia, "Quantum-Classical Computing via Tensor Networks", arXiv:2410.15080, (2024).

[31] Maniraman Periyasamy, Christian Ufrecht, Daniel D. Scherer, and Wolfgang Mauerer, "CutReg: A loss regularizer for enhancing the scalability of QML via adaptive circuit cutting", arXiv:2506.14858, (2025).

[32] Alexander Mattick, Maniraman Periyasamy, Christian Ufrecht, Abhishek Y. Dubey, Christopher Mutschler, Axel Plinge, and Daniel D. Scherer, "Optimizing Quantum Circuits via ZX Diagrams using Reinforcement Learning and Graph Neural Networks", arXiv:2504.03429, (2025).

[33] Nathaniel Tornow, Emmanouil Giortamis, and Pramod Bhatotia, "Scaling Quantum Computations via Gate Virtualization", arXiv:2406.18410, (2024).

[34] Gideon Uchehara, Tor M. Aamodt, and Olivia Di Matteo, "Graph-based identification of qubit network (GidNET) for qubit reuse", arXiv:2410.08817, (2024).

[35] Philipp Seitz, Manuel Geiger, and Christian B. Mendl, "Multithreaded parallelism for heterogeneous clusters of QPUs", arXiv:2311.17490, (2023).

[36] Ryo Nagai, Shu Kanno, Yuki Sato, and Naoki Yamamoto, "Quantum channel decomposition with preselection and postselection", Physical Review A 108 2, 022615 (2023).

[37] Philipp Seitz, Manuel Geiger, Christian Ufrecht, Axel Plinge, Christopher Mutschler, Daniel D. Scherer, and Christian B. Mendl, "SCIM MILQ: An HPC Quantum Scheduler", arXiv:2404.03512, (2024).

[38] Tuomas Laakkonen, Konstantinos Meichanetzidis, and John van de Wetering, "Picturing Counting Reductions with the ZH-Calculus", arXiv:2304.02524, (2023).

[39] Chenhui Wang, Weilong Wang, Yangyang Fei, Zhiqiang Fan, Hanshi Zhao, Yuyan Mage, and Zheng Shan, "Time-frequency-correlated Native CCZ Gate in Superconducting Circuits", arXiv:2509.06497, (2025).

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

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.