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

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


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

► References

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

[2] J. Preskill. ``Quantum Computing in the NISQ era and beyond''. Quantum 2, 79 (2018).

[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).

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

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

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

[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).

[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).

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

[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).

[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).

[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).

[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).

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

[15] R. Majumdar and C. J. Wood. ``Error mitigated quantum circuit cutting'' (2022). 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.

[17] W. Tang and M. Martonosi. ``ScaleQC: A scalable framework for hybrid computation on quantum and classical processors'' (2022). 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).

[19] K. Mitarai and K. Fujii. ``Methodology for replacing indirect measurements with direct measurements''. Phys. Rev. Research 1, 013006 (2019).

[20] K. Mitarai and K. Fujii. ``Constructing a virtual two-qubit gate by sampling single-qubit operations''. New J. Phys. 23, 023021 (2021).

[21] K. Mitarai and K. Fujii. ``Overhead for simulating a non-local channel with local channels by quasiprobability sampling''. Quantum 5, 388 (2021).

[22] K. Temme, S. Bravyi, and J. M. Gambetta. ``Error mitigation for short-depth quantum circuits''. Phys. Rev. Lett. 119, 180509 (2017).

[23] C. Piveteau, D. Sutter, and S. Woerner. ``Quasiprobability decompositions with reduced sampling overhead''. NPJ Quantum Inf. 8, 12 (2022).

[24] C. Piveteau. ``Advanced methods for quasiprobabilistic quantum error mitigation''. Master's thesis. ETH Zurich. (2021). url: https:/​/​​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).

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

[27] G. Vidal and R. Tarrach. ``Robustness of entanglement''. Phys. Rev. A 59, 141 (1999).

[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).

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

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

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

[32] S. C. Marshall, C. Gyurik, and V. Dunjko. ``High Dimensional Quantum Machine Learning With Small Quantum Computers''. Quantum 7, 1078 (2023).

[33] B. Coecke and R. Duncan. ``Interacting quantum observables: categorical algebra and diagrammatics''. New J. Phys. 13, 043016 (2011).

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

[35] J. van de Wetering. ``ZX-calculus for the working quantum computer scientist'' (2020). 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).

[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).

[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).

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

[40] ``IBM Quantum''. https:/​/​​. Accessed: 2023-01-23.

[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).

[42] S. Bravyi, G. Smith, and J. A. Smolin. ``Trading classical and quantum computational resources''. Phys. Rev. X 6, 021043 (2016).

[43] ``Github repository MCZ-gate cutting''. https:/​/​​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).

Cited by

[1] 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).

[2] 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.

[3] Sebastian Brandhofer, Ilia Polian, and Kevin Krsulich, "Optimal Partitioning of Quantum Circuits using Gate Cuts and Wire Cuts", arXiv:2308.09567, (2023).

[4] 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).

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

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

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

The above citations are from Crossref's cited-by service (last updated successfully 2024-05-26 03:07:08) and SAO/NASA ADS (last updated successfully 2024-05-26 03:07:08). The list may be incomplete as not all publishers provide suitable and complete citation data.