Abstract Distributed quantum computing leverages multiple quantum devices collectively to perform computations exceeding each device's capabilities. A currently studied technique to enable this distributed approach is wire cutting, which decomposes a quantum circuit into smaller subcircuits by cutting connecting wires. These subcircuits can be executed on distributed devices, and their results are then classically combined to reconstruct the original computation's result. However, wire cutting requires additional circuit executions to preserve result accuracy, with their number growing exponentially with each cut. Thus, minimizing this sampling overhead is crucial for reducing execution time. Employing shared non‐maximally entangled (NME) states between distributed devices reduces this overhead for single wire cuts, approaching ideal teleportation with maximally entangled states. Extending this approach to jointly cutting multiple wires using NME states remained unexplored. This study addresses this gap by investigating the use of NME states for joint wire cuts, aiming to reduce the sampling overhead further. The three main contributions include (i) determining the minimal sampling overhead for this scenario, (ii) analyzing the overhead when using composite NME states constructed from smaller NME states, and (iii) introducing a wire cutting technique that achieves the optimal sampling overhead with pure NME states, advancing toward wire cutting with arbitrary NME states.
Abstract Distributed quantum computing leverages multiple quantum devices collectively to perform computations exceeding each device's capabilities. A currently studied technique to enable this distributed approach is wire cutting, which decomposes a quantum circuit into smaller subcircuits by cutting connecting wires. These subcircuits can be executed on distributed devices, and their results are then classically combined to reconstruct the original computation's result. However, wire cutting requires additional circuit executions to preserve result accuracy, with their number growing exponentially with each cut. Thus, minimizing this sampling overhead is crucial for reducing execution time. Employing shared non‐maximally entangled (NME) states between distributed devices reduces this overhead for single wire cuts, approaching ideal teleportation with maximally entangled states. Extending this approach to jointly cutting multiple wires using NME states remained unexplored. This study addresses this gap by investigating the use of NME states for joint wire cuts, aiming to reduce the sampling overhead further. The three main contributions include (i) determining the minimal sampling overhead for this scenario, (ii) analyzing the overhead when using composite NME states constructed from smaller NME states, and (iii) introducing a wire cutting technique that achieves the optimal sampling overhead with pure NME states, advancing toward wire cutting with arbitrary NME states.
Distributed quantum computing supports combining the computational power of multiple quantum devices to overcome the limitations of individual devices. Circuit cutting techniques enable the distribution of quantum computations via classical communication. These techniques involve partitioning a quantum circuit into smaller subcircuits, each containing fewer qubits. The original circuit's outcome can be replicated by executing these sub circuits on separate devices and combining their results. However, the number of circuit executions required to achieve a fixed result accuracy with circuit cutting grows exponentially with the number of cuts, posing significant costs. In contrast, quantum teleportation allows the distribution of quantum computations without an exponential increase in circuit executions. Nevertheless, each teleportation requires a pre-shared pair of maximally entangled qubits for transmitting a quantum state, and non-maximally entangled qubits cannot be used for this purpose. Addressing this, our work explores utilizing non-maximally entangled qubit pairs in wire cutting, a specific form of circuit cutting, to mitigate the associated costs. The cost of this cutting procedure reduces with the increasing degree of entanglement in the pre-shared qubit pairs. We derive the optimal sampling overhead in this context and present a wire cutting technique employing pure non-maximally entangled states that achieves this optimal sampling overhead. Hence, this offers a continuum between existing wire cutting and quantum teleportation.
Quantum circuit cutting enables the execution of large circuits on devices with a limited number of qubits by partitioning circuits into independent subcircuits. However, this introduces a sampling overhead, which grows exponentially with the number of cuts, rendering the choice of cut placements critical for practical circuit cutting. Determining optimal cut placements remains computationally challenging, particularly as circuits grow in size. Additionally, existing circuit cutting approaches typically treat gate and wire cuts independently. Those combining both cutting approaches, however, do not take advantage of joint cutting, i.e., identifying common gate groups and cutting them jointly for a reduced overhead. This work presents a unified framework that combines gate and wire cutting within a single partitioning strategy, enabling more efficient circuit decompositions. Moreover, our approach incorporates joint cutting via a novel gate grouping technique, further reducing sampling overhead. By formulating the cut placement problem as a scalable graph partitioning task, our method efficiently identifies near-optimal cut placements for large circuits, also providing diagnostic feedback on whether circuits are suitable for cutting.
Distributed quantum computing combines the computational power of multiple devices to overcome the limitations of individual devices. Circuit cutting techniques enable the distribution of quantum computations through classical communication. These techniques involve partitioning a quantum circuit into smaller subcircuits, each containing fewer qubits. The original circuit's outcome can be replicated by executing these subcircuits on separate devices and combining their results. However, the number of shots required to achieve a fixed result accuracy with circuit cutting grows exponentially with the number of cuts, posing significant costs. In contrast, quantum teleportation allows the distribution of quantum computations without an exponential increase in shots. Nevertheless, each teleportation procedure requires a pre-shared pair of maximally entangled qubits for transmitting a quantum state, and non-maximally entangled qubits cannot be used for this purpose. To address this, we propose a novel circuit cutting technique that leverages non-maximally entangled qubit pairs, effectively reducing the cost associated with circuit cutting. By considering the degree of entanglement in the pre-shared qubit pairs, our technique provides a continuum between existing circuit cutting methods and quantum teleportation, adjusting the cost of circuit cutting accordingly.
A restriction in the quality and quantity of available qubits presents a substantial obstacle to the application of near-term and early fault-tolerant quantum computers in practical tasks. To confront this challenge, some techniques for effectively augmenting the system size through classical processing have been proposed; one promising approach is quantum circuit cutting. The main idea of quantum circuit cutting is to decompose an original circuit into smaller subcircuits and combine outputs from these subcircuits to recover the original output. Although this approach enables us to simulate larger quantum circuits beyond physically available circuits, it needs classical overheads quantified by two metrics: the sampling overhead in the number of measurements to reconstruct the original output, and the number of channels in the decomposition. Thus, it is crucial to devise a decomposition method that minimizes both of these metrics, thereby reducing the overall execution time. This paper studies the problem of decomposing the n -qubit identity channel, i.e., n -parallel wire cutting, into a set of local operations and classical communication; then we give an optimal wire-cutting method composed of channels based on mutually unbiased bases that achieves minimal overheads in both the sampling overhead and the number of channels, without ancilla qubits. This is in stark contrast to the existing method that achieves the optimal sampling overhead yet with ancilla qubits. Moreover, we derive a tight lower bound on the number of channels in parallel wire cutting without ancilla systems and show that only our method achieves this lower bound among the existing methods. Notably, our method shows an exponential improvement in the number of channels, compared to the aforementioned ancilla-assisted method that achieves optimal sampling overhead. Our work significantly alleviates the additional overheads for the wire-cutting method and may provide essential components for the early success of quantum computing. Published by the American Physical Society 2024
Wire cutting is a technique for partitioning large quantum circuits into smaller subcircuits in such a way that observables for the original circuits can be estimated from measurements on the smaller subcircuits. Such techniques provide workarounds for the limited numbers of qubits that are available on near-term quantum devices. Wire cutting, however, introduces multiplicative factors in the number of times such subcircuits need to be executed in order to estimate desired quantum observables to desired levels of statistical accuracy. An optimal wire-cutting methodology has recently been reported that uses ancilla qubits to minimize the multiplicative factors involved as a function of the number of wire cuts. Until just recently, the best-known wire-cutting technique that did not employ ancillas asymptotically converged to the same multiplicative factors, but performed significantly worse for small numbers of cuts. This latter technique also requires inserting measurement and state-preparation subcircuits that are randomly sampled from Clifford 2-designs on a per-shot basis. This paper presents a modified wire-cutting approach for pairs of subcircuits that achieves the same optimal multiplicative factors as wire cutting aided by ancilla qubits, but without requiring ancillas. The paper also shows that, while unitary 2-designs provide a sufficient basis for satisfying the decomposition, 2-designs are not mathematically necessary and alternative unitary designs can be constructed for the decompositions that are substantially smaller in size than 2-designs. As this paper was just about to be released, a similar result was published, so we also include a comparison of the two approaches.
Quasiprobabilistic cutting techniques allow us to partition large quantum circuits into smaller subcircuits by replacing non-local gates with probabilistic mixtures of local gates. The cost of this method is a sampling overhead that scales exponentially in the number of cuts. It is crucial to determine the minimal cost for gate cutting and to understand whether allowing for classical communication between subcircuits can improve the sampling overhead. In this work, we derive a closed formula for the optimal sampling overhead for cutting an arbitrary number of two-qubit unitaries and provide the corresponding decomposition. We find that cutting several arbitrary two-qubit unitaries together is cheaper than cutting them individually and classical communication does not give any advantage.