Overhead for simulating a non-local channel with local channels by quasiprobability sampling

Kosuke Mitarai1,2,3 and Keisuke Fujii1,2,4

1Graduate School of Engineering Science, Osaka University, 1-3 Machikaneyama, Toyonaka, Osaka 560-8531, Japan.
2Center for Quantum Information and Quantum Biology, Institute for Open and Transdisciplinary Research Initiatives, Osaka University, Japan.
3JST, PRESTO, 4-1-8 Honcho, Kawaguchi, Saitama 332-0012, Japan.
4Center for Emergent Matter Science, RIKEN, Wako Saitama 351-0198, Japan

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

Abstract

As the hardware technology for quantum computing advances, its possible applications are actively searched and developed. However, such applications still suffer from the noise on quantum devices, in particular when using two-qubit gates whose fidelity is relatively low. One way to overcome this difficulty is to substitute such non-local operations by local ones. Such substitution can be performed by decomposing a non-local channel into a linear combination of local channels and simulating the original channel with a quasiprobability-based method. In this work, we first define a quantity that we call channel robustness of non-locality, which quantifies the cost for the decomposition. While this quantity is challenging to calculate for a general non-local channel, we give an upper bound for a general two-qubit unitary channel by providing an explicit decomposition. The decomposition is obtained by generalizing our previous work whose application has been restricted to a certain form of two-qubit unitary. This work develops a framework for a resource reduction suitable for first-generation quantum devices.

► BibTeX data

► References

[1] F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, Nature 574, 505 (2019).
https:/​/​doi.org/​10.1038/​s41586-019-1666-5

[2] J. Preskill, Quantum 2, 79 (2018).
https:/​/​doi.org/​10.22331/​q-2018-08-06-79

[3] A. Peruzzo, J. McClean, P. Shadbolt, M.-H. Yung, X.-Q. Zhou, P. J. Love, A. Aspuru-Guzik, and J. L. O'Brien, Nature Communications 5, 4213 (2014).
https:/​/​doi.org/​10.1038/​ncomms5213

[4] S. McArdle, S. Endo, A. Aspuru-Guzik, S. C. Benjamin, and X. Yuan, Rev. Mod. Phys. 92, 015003 (2020).
https:/​/​doi.org/​10.1103/​RevModPhys.92.015003

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

[6] K. Mitarai, M. Negoro, M. Kitagawa, and K. Fujii, Phys. Rev. A 98, 032309 (2018).
https:/​/​doi.org/​10.1103/​PhysRevA.98.032309

[7] E. Farhi and H. Neven, ``Classification with quantum neural networks on near term processors,'' (2018), arXiv:1802.06002 [quant-ph].
arXiv:1802.06002

[8] C. Bravo-Prieto, R. LaRose, M. Cerezo, Y. Subasi, L. Cincio, and P. J. Coles, ``Variational quantum linear solver,'' (2019), arXiv:1909.05820 [quant-ph].
arXiv:1909.05820

[9] R. LaRose, A. Tikku, E. O'Neel-Judy, L. Cincio, and P. J. Coles, npj Quantum Information 5, 8 (2019).
https:/​/​doi.org/​10.1038/​s41534-019-0167-6

[10] T. Peng, A. W. Harrow, M. Ozols, and X. Wu, Phys. Rev. Lett. 125, 150504 (2020).
https:/​/​doi.org/​10.1103/​PhysRevLett.125.150504

[11] K. Mitarai and K. Fujii, New Journal of Physics , accepted (2020).
https:/​/​doi.org/​10.1088/​1367-2630/​abd7bc

[12] K. Temme, S. Bravyi, and J. M. Gambetta, Phys. Rev. Lett. 119, 180509 (2017).
https:/​/​doi.org/​10.1103/​PhysRevLett.119.180509

[13] S. Endo, S. C. Benjamin, and Y. Li, Phys. Rev. X 8, 031027 (2018).
https:/​/​doi.org/​10.1103/​PhysRevX.8.031027

[14] H. Pashayan, J. J. Wallman, and S. D. Bartlett, Phys. Rev. Lett. 115, 070501 (2015).
https:/​/​doi.org/​10.1103/​PhysRevLett.115.070501

[15] M. Howard and E. Campbell, Phys. Rev. Lett. 118, 090501 (2017).
https:/​/​doi.org/​10.1103/​PhysRevLett.118.090501

[16] S. Bravyi, G. Smith, and J. A. Smolin, Phys. Rev. X 6, 021043 (2016).
https:/​/​doi.org/​10.1103/​PhysRevX.6.021043

[17] R. S. Bennink, E. M. Ferragut, T. S. Humble, J. A. Laska, J. J. Nutaro, M. G. Pleszkoch, and R. C. Pooser, Phys. Rev. A 95, 062337 (2017).
https:/​/​doi.org/​10.1103/​PhysRevA.95.062337

[18] J. R. Seddon and E. T. Campbell, Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 475, 20190251 (2019).
https:/​/​doi.org/​10.1098/​rspa.2019.0251

[19] B. Kraus and J. I. Cirac, Phys. Rev. A 63, 062309 (2001).
https:/​/​doi.org/​10.1103/​PhysRevA.63.062309

[20] J. Zhang, J. Vala, S. Sastry, and K. B. Whaley, Phys. Rev. A 67, 042313 (2003).
https:/​/​doi.org/​10.1103/​PhysRevA.67.042313

[21] F.-Z. Kong, J.-L. Zhao, M. Yang, and Z.-L. Cao, Phys. Rev. A 92, 012127 (2015).
https:/​/​doi.org/​10.1103/​PhysRevA.92.012127

[22] Y. Ibe, Y. O. Nakagawa, T. Yamamoto, K. Mitarai, Q. Gao, and T. Kobayashi, ``Calculating transition amplitudes by variational quantum eigensolvers,'' (2020), arXiv:2002.11724 [quant-ph].
arXiv:2002.11724

[23] K. Mitarai and K. Fujii, Phys. Rev. Research 1, 013006 (2019).
https:/​/​doi.org/​10.1103/​PhysRevResearch.1.013006

[24] H. Buhrman, R. Cleve, J. Watrous, and R. de Wolf, Phys. Rev. Lett. 87, 167902 (2001).
https:/​/​doi.org/​10.1103/​PhysRevLett.87.167902

[25] J. C. Garcia-Escartin and P. Chamorro-Posada, Phys. Rev. A 87, 052330 (2013).
https:/​/​doi.org/​10.1103/​PhysRevA.87.052330

Cited by

[1] J Knörzer, X Liu, B F Schiffer, and J Tura, "Distributed quantum information processing: a review of recent progress", Reports on Progress in Physics 89 7, 074401 (2026).

[2] Juan C. Boschero, Niels M. P. Neumann, Ward van der Schoot, Thom Sijpesteijn, and Robert Wezeman, Lecture Notes in Networks and Systems 1423, 100 (2025) ISBN:978-3-031-92601-3.

[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] Laszlo Gyongyosi and Sandor Imre, "Networked Quantum Services†", Quantum Information & Computation 25 2, 97 (2025).

[5] Christophe Piveteau and David Sutter, "Circuit Knitting With Classical Communication", IEEE Transactions on Information Theory 70 4, 2734 (2024).

[6] Christian Ufrecht, Maniraman Periyasamy, Sebastian Rietsch, Daniel D. Scherer, Axel Plinge, and Christopher Mutschler, "Cutting multi-control quantum gates with ZX calculus", Quantum 7, 1147 (2023).

[7] Gian Gentinetta, Friederike Metz, and Giuseppe Carleo, "Overhead-constrained circuit knitting for variational quantum dynamics", Quantum 8, 1296 (2024).

[8] Jinzhao Sun, Suguru Endo, Huiping Lin, Patrick Hayden, Vlatko Vedral, and Xiao Yuan, "Perturbative Quantum Simulation", Physical Review Letters 129 12, 120505 (2022).

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

[10] Shiplu Sarker, Wenyang Qian, Soham Pal, Robert Basili, Mary Eshaghian-Wilner, Ashfaq Khokhar, Glenn Luecke, and James P. Vary, 2024 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW) 1068 (2024) ISBN:979-8-3503-6460-6.

[11] Yuki Takeuchi, Yasuhiro Takahashi, Tomoyuki Morimae, and Seiichiro Tani, "Divide-and-conquer verification method for noisy intermediate-scale quantum computation", Quantum 6, 758 (2022).

[12] Chong Ying, Bin Cheng, Youwei Zhao, He-Liang Huang, Yu-Ning Zhang, Ming Gong, Yulin Wu, Shiyu Wang, Futian Liang, Jin Lin, Yu Xu, Hui Deng, Hao Rong, Cheng-Zhi Peng, Man-Hong Yung, Xiaobo Zhu, and Jian-Wei Pan, "Experimental Simulation of Larger Quantum Circuits with Fewer Superconducting Qubits", Physical Review Letters 130 11, 110601 (2023).

[13] Lukas Brenner, Christophe Piveteau, and David Sutter, "Optimal Wire Cutting With Classical Communication", IEEE Transactions on Information Theory 71 10, 7742 (2025).

[14] Aram W. Harrow and Angus Lowe, "Optimal Quantum Circuit Cuts with Application to Clustered Hamiltonian Simulation", PRX Quantum 6 1, 010316 (2025).

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

[16] Tian-Ren Jin, Yu-Ran Zhang, Kai Xu, and Heng Fan, "Noisy probabilistic error cancellation and generalized physical implementability", Communications Physics 8 1, 296 (2025).

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

[18] Zhixing Chen and Lin Chen, "Virtual quantum Markov chain of four-qubit systems", Communications in Theoretical Physics 78 7, 075101 (2026).

[19] Elias X. Huber, Benjamin Y. L. Tan, Paul R. Griffin, and Dimitris G. Angelakis, "Exponential qubit reduction in optimization for financial transaction settlement", EPJ Quantum Technology 11 1, 52 (2024).

[20] Angus Lowe, Matija Medvidović, Anthony Hayes, Lee J. O'Riordan, Thomas R. Bromley, Juan Miguel Arrazola, and Nathan Killoran, "Fast quantum circuit cutting with randomized measurements", Quantum 7, 934 (2023).

[21] Aniello Esposito and Tamuz Danzig, 2024 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW) 1088 (2024) ISBN:979-8-3503-6460-6.

[22] Mario Motta, Kevin J. Sung, and James Shee, "Quantum Algorithms for the Variational Optimization of Correlated Electronic States with Stochastic Reconfiguration and the Linear Method", The Journal of Physical Chemistry A 128 40, 8762 (2024).

[23] Shigeo Hakkaku, Kosuke Mitarai, and Keisuke Fujii, "Sampling-based quasiprobability simulation for fault-tolerant quantum error correction on the surface codes under coherent noise", Physical Review Research 3 4, 043130 (2021).

[24] Sean R. Garner, Nathan M. Myers, Meng Wang, Samuel Stein, Chenxu Liu, and Ang Li, "Simulation of thermal-relaxation noise for quantum error correction", Physical Review Research 8 2, 023134 (2026).

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

[26] Theodora Adufu and Yoonhee Kim, "DAScut: density-and-structure-aware circuit cutting for scalable quantum simulations", Cluster Computing 29 3, 163 (2026).

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

[28] Xuanqiang Zhao, Lei Zhang, Benchi Zhao, and Xin Wang, "Power of quantum measurement in simulating unphysical operations", Physical Review Research 7 1, 013334 (2025).

[29] Keisuke Fujii, Kaoru Mizuta, Hiroshi Ueda, Kosuke Mitarai, Wataru Mizukami, and Yuya O. Nakagawa, "Deep Variational Quantum Eigensolver: A Divide-And-Conquer Method for Solving a Larger Problem with Smaller Size Quantum Computers", PRX Quantum 3 1, 010346 (2022).

[30] Yu-Ao Chen, Chengkai Zhu, Keming He, Mingrui Jing, and Xin Wang, "Virtual Quantum Markov Chains", IEEE Transactions on Information Theory 71 7, 5387 (2025).

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

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

[33] Simon C. Marshall, Casper Gyurik, and Vedran Dunjko, "High Dimensional Quantum Machine Learning With Small Quantum Computers", Quantum 7, 1078 (2023).

[34] Xuanqiang Zhao, Xin Wang, and Giulio Chiribella, "Shadow Simulation of Quantum Processes", Physical Review Letters 133 12, 120804 (2024).

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

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

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

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

[39] Christophe Piveteau, Lukas Schmitt, and David Sutter, "Circuit cutting with classical side information", Physical Review Research 7 3, 033063 (2025).

[40] 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 (2023).

[41] Debarthi Pal and Ritajit Majumdar, "Low overhead circuit cutting with operator backpropagation", Quantum Information Processing 25 8, 274 (2026).

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

[43] Xiao Yuan, Jinzhao Sun, Junyu Liu, Qi Zhao, and You Zhou, "Quantum Simulation with Hybrid Tensor Networks", Physical Review Letters 127 4, 040501 (2021).

[44] Valter Uotila, Ilmo Salmenperä, Leo Becker, Arianne Meijer - van de Griend, Aakash Ravindra Shinde, and Jukka K. Nurminen, 2025 IEEE International Conference on Quantum Software (QSW) 01 (2025) ISBN:979-8-3315-6720-0.

[45] Kelvin Onggadinata, Andrew Tanggara, Mile Gu, and Dagomir Kaszlikowski, "Ideal stochastic process modeling with post-quantum quasiprobabilistic theories", Quantum 10, 2005 (2026).

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

[47] Ismael Faro, Iskandar Sitdikov, David Garcia Valiñas, Francisco Jose Martin Fernandez, Christopher Codella, and Jennifer Glick, 2023 IEEE International Conference on Quantum Software (QSW) 1 (2023) ISBN:979-8-3503-0479-4.

[48] Lirandë Pira and Chris Ferrie, "An invitation to distributed quantum neural networks", Quantum Machine Intelligence 5 2, 23 (2023).

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

[50] Cameron Ibrahim, Teague Tomesh, Zain Saleem, and Ilya Safro, 2024 IEEE International Conference on Quantum Computing and Engineering (QCE) 545 (2024) ISBN:979-8-3315-4137-8.

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

[52] Mingrui Jing, Chengkai Zhu, and Xin Wang, "Circuit knitting facing exponential sampling-overhead scaling bounded by entanglement cost", Physical Review A 111 1, 012433 (2025).

[53] Takahiro Yamamoto and Ryutaro Ohira, "Error suppression by a virtual two-qubit gate", Journal of Applied Physics 133 17, 174401 (2023).

[54] Gian Gentinetta, Friederike Metz, and Giuseppe Carleo, "Correcting and Extending Trotterized Quantum Many-Body Dynamics", PRX Quantum 6 3, 030361 (2025).

[55] Lukas Schmitt, Christophe Piveteau, and David Sutter, "Cutting circuits with multiple two-qubit unitaries", Quantum 9, 1634 (2025).

[56] Yasunari Suzuki, Suguru Endo, Keisuke Fujii, and Yuuki Tokunaga, "Quantum Error Mitigation as a Universal Error Reduction Technique: Applications from the NISQ to the Fault-Tolerant Quantum Computing Eras", PRX Quantum 3 1, 010345 (2022).

[57] Christophe Piveteau and David Sutter, "Circuit knitting with classical communication", arXiv:2205.00016, (2022).

[58] Lukas Brenner, Christophe Piveteau, and David Sutter, "Optimal wire cutting with classical communication", arXiv:2302.03366, (2023).

[59] Keisuke Fujii, Kaoru Mizuta, Hiroshi Ueda, Kosuke Mitarai, Wataru Mizukami, and Yuya O. Nakagawa, "Deep Variational Quantum Eigensolver: a divide-and-conquer method for solving a larger problem with smaller size quantum computers", arXiv:2007.10917, (2020).

[60] Shao-Hua Hu and Ray-Kuang Lee, "Circuit Knitting for Continuous-Variable Quantum States", arXiv:2509.07947, (2025).

[61] Yasunari Suzuki, Suguru Endo, Keisuke Fujii, and Yuuki Tokunaga, "Quantum error mitigation as a universal error-minimization technique: applications from NISQ to FTQC eras", arXiv:2010.03887, (2020).

[62] Ritajit Majumdar and Christopher J. Wood, "Error mitigated quantum circuit cutting", arXiv:2211.13431, (2022).

[63] Juan C. Boschero, Niels M. P. Neumann, Ward van der Schoot, Thom Sijpesteijn, and Robert Wezeman, "Distributed Quantum Computing: Applications and Challenges", arXiv:2410.00609, (2024).

[64] Shuwen Kan, Zefan Du, Miguel Palma, Samuel A Stein, Chenxu Liu, Wenqi Wei, Juntao Chen, Ang Li, and Ying Mao, "Scalable Circuit Cutting and Scheduling in a Resource-constrained and Distributed Quantum System", arXiv:2405.04514, (2024).

[65] Niels M. P. Neumann, Carlos M. R. Rocha, Jasper Verbree, and Marc van Vliet, "Probability distribution reconstruction using circuit cutting applied to a variational classifier", arXiv:2510.03077, (2025).

[66] Laura S. Herzog, Lukas Burgholzer, Christian Ufrecht, Daniel D. Scherer, and Robert Wille, "Joint Cutting for Hybrid Schrödinger-Feynman Simulation of Quantum Circuits", arXiv:2502.06959, (2025).

[67] Valter Uotila, Ilmo Salmenperä, Leo Becker, Arianne Meijer- van de Griend, Aakash Ravindra Shinde, and Jukka K. Nurminen, "Perspectives on Utilization of Measurements in Quantum Algorithms", arXiv:2507.04325, (2025).

[68] Shuwen Kan, Yanni Li, Hao Wang, Sara Mouradian, and Ying Mao, "Circuit Folding: Scalable and Graph-Based Circuit Cutting via Modular Structure Exploitation", arXiv:2412.18705, (2024).

The above citations are from Crossref's cited-by service (last updated successfully 2026-08-09 09:40:18) and SAO/NASA ADS (last updated successfully 2026-08-08 20:02:56). 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 09:40:18: Cannot retrieve data from ADS due to rate limitations.