Circuit Knitting Faces Exponential Sampling Overhead Scaling Bounded by Entanglement Cost

Abstract

Abstract Circuit knitting, a method for connecting quantum circuits across multiple processors to simulate nonlocal quantum operations, is a promising approach for distributed quantum computing. While various techniques have been developed for circuit knitting, we uncover fundamental limitations to the scalability of this technology. We prove that the sampling overhead of circuit knitting is exponentially lower bounded by the exact entanglement cost of the target bipartite dynamic, even for asymptotic overhead in the parallel cut regime. Specifically, we prove that the regularized sampling overhead assisted with local operations and classical communication (LOCC), of any bipartite quantum channel is lower bounded by the exponential of its exact entanglement cost under separable preserving operations. Furthermore, we show that the regularized sampling overhead for simulating a general bipartite channel via LOCC is lower bounded by $\kappa$-entanglement and max-Rains information, providing efficiently computable benchmarks. Our work reveals a profound connection between virtual quantum information processing via quasi-probability decomposition and quantum Shannon theory, highlighting the critical role of entanglement in distributed quantum computing.

Mingrui Jing

PhD Student (2023)

I obtained my BS and MS degrees in physics from the University of Melbourne. My research interests include distributed quantum computing, quantum entanglement and quantum machine learning.

Chengkai Zhu

PhD Student (2023)

I obtained my BS in Applied Mathematics from China Agricultural University under the supervision of Prof. Zhencai Shen. I obtained my MS degree in Cyberspace Security from University of Chinese Academy of Sciences under the supervision of Prof. Zhenyu Huang. My research interests include quantum information theory and quantum computation.

Xin Wang

Associate Professor

Prof. Xin Wang founded the QuAIR lab at HKUST(Guangzhou) in June 2023. His research primarily focuses on better understanding the limits of information processing with quantum systems and the power of quantum artificial intelligence. Prior to establishing the QuAIR lab, Prof. Wang was a Staff Researcher at the Institute for Quantum Computing at Baidu Research, where he concentrated on quantum computing research and the development of the Baidu Quantum Platform. Notably, he spearheaded the development of Paddle Quantum, a Python library designed for quantum machine learning. From 2018 to 2019, Prof. Wang held the position of Hartree Postdoctoral Fellow at the Joint Center for Quantum Information and Computer Science (QuICS) at the University of Maryland, College Park. He earned his doctorate in quantum information from the University of Technology Sydney in 2018, under the guidance of Prof. Runyao Duan and Prof. Andreas Winter. In 2014, Prof. Wang obtained his B.S. in mathematics (with Wu Yuzhang Honor) from Sichuan University.