Current quantum devices face challenges when dealing with large circuits due to error rates as circuit size and the number of qubits increase. The circuit wire-cutting technique addresses this issue by breaking down a large circuit into smaller, more manageable subcircuits. However, the exponential increase in the number of subcircuits and the complexity of reconstruction as more cuts are made poses a great practical challenge. Inspired by ancilla-assisted quantum process tomography and the MUBs-based grouping technique for simultaneous measurement, we propose a new approach that can reduce subcircuit running overhead. The approach first uses ancillary qubits to transform all quantum input initializations into quantum output measurements. These output measurements are then organized into commuting groups for the purpose of simultaneous measurement, based on MUBs-based grouping. This approach significantly reduces the number of necessary subcircuits as well as the total number of shots. Lastly, we provide numerical experiments to demonstrate the complexity reduction.
Current quantum devices face challenges when dealing with large circuits due to error rates as circuit size and the number of qubits increase. The circuit wire-cutting technique addresses this issue by breaking down a large circuit into smaller, more manageable subcircuits. However, the exponential increase in the number of subcircuits and the complexity of reconstruction as more cuts are made poses a great practical challenge. Inspired by ancilla-assisted quantum process tomography and the MUBs-based grouping technique for simultaneous measurement, we propose a new approach that can reduce subcircuit running overhead. The approach first uses ancillary qubits to transform all quantum input initializations into quantum output measurements. These output measurements are then organized into commuting groups for the purpose of simultaneous measurement, based on MUBs-based grouping. This approach significantly reduces the number of necessary subcircuits as well as the total number of shots. Lastly, we provide numerical experiments to demonstrate the complexity reduction.
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.
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.
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
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.
Circuit cutting is a technique for simulating large quantum circuits by partitioning them into smaller subcircuits, which can be executed on smaller quantum devices. The results from these subcircuits are then combined in classical postprocessing to accurately reconstruct the expectation value of the original circuit. Circuit cutting introduces a sampling overhead that grows exponentially with the number of gates and qubit wires that are cut. Many recently developed quasiprobabilistic circuit cutting techniques leverage classical side information, obtained from intermediate measurements within the subcircuits, to enhance the postprocessing step. In this work, we provide a formalization of general circuit cutting techniques utilizing side information through quantum instruments. With this framework, we analyze the advantage that classical side information provides in reducing the sampling overhead of circuit cutting. Surprisingly, we find that in certain scenarios, side information does not yield any reduction in sampling overhead, whereas in others it is essential for circuit cutting to be feasible at all. Furthermore, we present a lower bound for the optimal sampling overhead with side information that can be evaluated efficiently via semidefinite programming and improves on all previously known lower bounds.
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.