Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2205.00016 · IEEE Transactions on Information Theory

Circuit Knitting With Classical Communication

Christophe Piveteau, David Sutter

Published Aug 31, 2023• 111 citations
arXivHTMLPDF

Abstract

The scarcity of qubits is a major obstacle to the practical usage of quantum computers in the near future. To circumvent this problem, various circuit knitting techniques have been developed to partition large quantum circuits into subcircuits that fit on smaller devices, at the cost of a simulation overhead. In this work, we study a particular method of circuit knitting based on quasiprobability simulation of nonlocal gates with operations that act locally on the subcircuits. We investigate whether classical communication between these local quantum computers can help. We provide a positive answer by showing that for circuits containing$n$nonlocal CNOT gates connecting two circuit parts, the simulation overhead can be reduced from$O(9^{n})$to$O(4^{n})$if one allows for classical information exchange. Similar improvements can be obtained for general Clifford gates and, at least in a restricted form, for other gates such as controlled rotation gates.

DOI
10.1109/tit.2023.3310797

Related papers

Optimal Wire Cutting With Classical Communication

Lukas Brenner, Christophe Piveteau, David Sutter

Circuit knitting is the process of partitioning large quantum circuits into smaller subcircuits such that the result of the original circuits can be deduced by only running the subcircuits. Such techniques will be crucial for near-term and early fault-tolerant quantum computers, as the limited number of qubits is likely to be a major bottleneck for demonstrating quantum advantage. One typically distinguishes between gate cuts and wire cuts when partitioning a circuit. The cost for any circuit knitting approach scales exponentially in the number of cuts. One possibility to realize a cut is via the quasiprobability simulation technique. In fact, we argue that all existing rigorous circuit knitting techniques can be understood in this framework. Furthermore, we characterize the optimal overhead for wire cuts where the subcircuits can exchange classical information or not. We show that the optimal cost for cuttingnwires without and with classical communication between the subcircuits scales asO(16n) andO(4n), respectively.

arXiv:2302.03366•IEEE Transactions on Information Theory•Aug 20, 2025•21 citations

Simulating quantum circuits with restricted quantum computers

Christophe Piveteau

It is one of the most fundamental objectives in quantum information science to understand the boundary between the computational power of classical and quantum computers. One possible avenue to explore this boundary is to identify classes of quantum circuits that can be efficiently simulated on a classical computer. Instead of simulating a general quantum circuit with a classical device, new schemes have recently emerged to simulate them on a quantum device that is restricted in some manner. As such, these techniques allow us to study how the restrictions impact the computational power of the device. One such technique is called quasiprobability simulation (QPS) and it estimates the result of a quantum circuit with a Monte Carlo procedure that randomly replaces circuit elements with ones that can be executed on the restricted quantum device. The main focus of this thesis is dedicated to the QPS-based simulation of nonlocal quantum computation using local quantum operations. On the practical side, this enables the simulation of large quantum circuits using multiple smaller quantum devices - a procedure that is sometimes called circuit knitting. We uncover a rich mathematical formalism with many connections to the resource theory of entanglement. We characterize the optimal simulation overhead for a broad range of practically relevant nonlocal states and channels and we explicitly provide achieving protocols. Moreover, we also investigate the utility of classical communication between the local parties. Our results address both the single-shot and asymptotic regime. We frame QPS in a quantum resource theoretic framework, which highlights similarities that arise in the different instantiations of the technique. Furthermore, we study the importance of classical side information in the QPS procedure and how it impacts the overhead and expressibility of QPS.

arXiv:2503.21773•Jan 1, 2025•0 citations

Distributed Quantum Computing via Adaptive Circuit Knitting

K. Grace Johnson, Aniello Esposito, Gaurav Gyawali +5 more

Distributing quantum workloads over many Quantum Processing Units (QPUs) is a crucial step in scaling up quantum computers toward practical quantum advantage due to the limitations in size of a single QPU. In the absence of high-fidelity quantum interconnects, circuit knitting could provide a path to computing certain properties of large quantum systems on many QPUs of limited size in a distributed fashion using only classical communication. Circuit knitting partitions large quantum circuits into manageable sub-circuits, however, reconstructing observables in a straightforward manner comes at an exponential cost in sampling and classical post-processing. To mitigate the overhead this technique incurs, we introduce an Adaptive Circuit Knitting (ACK) method that finds efficient partitions of quantum circuits by discovering regions of minimal entanglement between subsystems. We simulate 1D and 2D disordered mixed-field Ising models up to 60 qubits and show that the ACK approach can reduce circuit knitting sampling overheads by up to four orders of magnitude for observables of interest. We highlight our parallel GPU-accelerated implementation and discuss the need for efficient classical simulators to enable distributed quantum algorithm development. Our techniques could enable efficient distribution of quantum simulation for both near-term and fault-tolerant architectures.

quant-pharXiv:2603.12411•Mar 16, 2026•0 citations

A Hardware-Aware Gate Cutting Framework for Practical Quantum Circuit Knitting

Xiangyu Ren, Mengyu Zhang, Antonio Barbalace

Circuit knitting emerges as a promising technique to overcome the limitation of the few physical qubits in near-term quantum hardware by cutting large quantum circuits into smaller subcircuits. Recent research in this area has been primarily oriented towards reducing subcircuit sampling overhead. Unfortunately, these works neglect hardware information during circuit cutting, thus posing significant challenges to the follow on stages. In fact, direct compilation and execution of these partitioned subcircuits yields low-fidelity results, highlighting the need for a more holistic optimization strategy.

arXiv:2409.03870•Oct 27, 2024•12 citations

Circuit knitting facing exponential sampling-overhead scaling bounded by entanglement cost

Mingrui Jing, Chengkai Zhu, Xin Wang

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 with the asymptotic amount of resources using the parallel cut strategy. Specifically, we prove that the regularized sampling overhead assisted with local operations and classical communication of any bipartite quantum channel is lower bounded by the exponential of its exact entanglement cost under separable preserving operations. Furthermore, we develop the faithful lower bounds for the regularized sampling overhead based on channels' $\ensuremath{\kappa}$ entanglement and max-Rains information, providing efficiently computable benchmarks. Our work reveals a profound connection between virtual quantum information processing via quasiprobability decomposition and quantum Shannon theory, highlighting the critical role of entanglement in distributed quantum computing.

Physical Review A•Jan 22, 2025•9 citations

Circuit Knitting Faces Exponential Sampling Overhead Scaling Bounded by Entanglement Cost

Mingrui Jing, Chengkai Zhu, Xin Wang

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 $κ$-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.

arXiv:2404.03619•Apr 4, 2024•0 citations
The scarcity of qubits is a major obstacle to the practical usage of quantum computers in the near future. To circumvent this problem, various circuit knitting techniques have been developed to partition large quantum circuits into subcircuits that fit on smaller devices, at the cost of a simulation overhead. In this work, we study a particular method of circuit knitting based on quasiprobability simulation of nonlocal gates with operations that act locally on the subcircuits. We investigate whether classical communication between these local quantum computers can help. We provide a positive answer by showing that for circuits containingnnnnonlocal CNOT gates connecting two circuit parts, the simulation overhead can be reduced fromO(9n)O(9^{n})O(9n)toO(4n)O(4^{n})O(4n)if one allows for classical information exchange. Similar improvements can be obtained for general Clifford gates and, at least in a restricted form, for other gates such as controlled rotation gates.
Circuit knitting is the process of partitioning large quantum circuits into smaller subcircuits such that the result of the original circuits can be deduced by only running the subcircuits. Such techniques will be crucial for near-term and early fault-tolerant quantum computers, as the limited number of qubits is likely to be a major bottleneck for demonstrating quantum advantage. One typically distinguishes between gate cuts and wire cuts when partitioning a circuit. The cost for any circuit knitting approach scales exponentially in the number of cuts. One possibility to realize a cut is via the quasiprobability simulation technique. In fact, we argue that all existing rigorous circuit knitting techniques can be understood in this framework. Furthermore, we characterize the optimal overhead for wire cuts where the subcircuits can exchange classical information or not. We show that the optimal cost for cuttingnwires without and with classical communication between the subcircuits scales asO(16n) andO(4n), respectively.
It is one of the most fundamental objectives in quantum information science to understand the boundary between the computational power of classical and quantum computers. One possible avenue to explore this boundary is to identify classes of quantum circuits that can be efficiently simulated on a classical computer. Instead of simulating a general quantum circuit with a classical device, new schemes have recently emerged to simulate them on a quantum device that is restricted in some manner. As such, these techniques allow us to study how the restrictions impact the computational power of the device. One such technique is called quasiprobability simulation (QPS) and it estimates the result of a quantum circuit with a Monte Carlo procedure that randomly replaces circuit elements with ones that can be executed on the restricted quantum device. The main focus of this thesis is dedicated to the QPS-based simulation of nonlocal quantum computation using local quantum operations. On the practical side, this enables the simulation of large quantum circuits using multiple smaller quantum devices - a procedure that is sometimes called circuit knitting. We uncover a rich mathematical formalism with many connections to the resource theory of entanglement. We characterize the optimal simulation overhead for a broad range of practically relevant nonlocal states and channels and we explicitly provide achieving protocols. Moreover, we also investigate the utility of classical communication between the local parties. Our results address both the single-shot and asymptotic regime. We frame QPS in a quantum resource theoretic framework, which highlights similarities that arise in the different instantiations of the technique. Furthermore, we study the importance of classical side information in the QPS procedure and how it impacts the overhead and expressibility of QPS.
Distributing quantum workloads over many Quantum Processing Units (QPUs) is a crucial step in scaling up quantum computers toward practical quantum advantage due to the limitations in size of a single QPU. In the absence of high-fidelity quantum interconnects, circuit knitting could provide a path to computing certain properties of large quantum systems on many QPUs of limited size in a distributed fashion using only classical communication. Circuit knitting partitions large quantum circuits into manageable sub-circuits, however, reconstructing observables in a straightforward manner comes at an exponential cost in sampling and classical post-processing. To mitigate the overhead this technique incurs, we introduce an Adaptive Circuit Knitting (ACK) method that finds efficient partitions of quantum circuits by discovering regions of minimal entanglement between subsystems. We simulate 1D and 2D disordered mixed-field Ising models up to 60 qubits and show that the ACK approach can reduce circuit knitting sampling overheads by up to four orders of magnitude for observables of interest. We highlight our parallel GPU-accelerated implementation and discuss the need for efficient classical simulators to enable distributed quantum algorithm development. Our techniques could enable efficient distribution of quantum simulation for both near-term and fault-tolerant architectures.
Circuit knitting emerges as a promising technique to overcome the limitation of the few physical qubits in near-term quantum hardware by cutting large quantum circuits into smaller subcircuits. Recent research in this area has been primarily oriented towards reducing subcircuit sampling overhead. Unfortunately, these works neglect hardware information during circuit cutting, thus posing significant challenges to the follow on stages. In fact, direct compilation and execution of these partitioned subcircuits yields low-fidelity results, highlighting the need for a more holistic optimization strategy.
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 with the asymptotic amount of resources using the parallel cut strategy. Specifically, we prove that the regularized sampling overhead assisted with local operations and classical communication of any bipartite quantum channel is lower bounded by the exponential of its exact entanglement cost under separable preserving operations. Furthermore, we develop the faithful lower bounds for the regularized sampling overhead based on channels' $\ensuremath{\kappa}$ entanglement and max-Rains information, providing efficiently computable benchmarks. Our work reveals a profound connection between virtual quantum information processing via quasiprobability decomposition and quantum Shannon theory, highlighting the critical role of entanglement in distributed quantum computing.
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 κκκ-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.