We propose a new method to extend the size of a quantum computation beyond the number of physical qubits available on a single device. This is accomplished by randomly inserting measure-and-prepare channels to express the output state of a large circuit as a separable state across distinct devices. Our method employs randomized measurements, resulting in a sample overhead that is O~(4k/ε2) , where ε is the accuracy of the computation and k the number of parallel wires that are "cut" to obtain smaller sub-circuits. We also show an information-theoretic lower bound of Ω(2k/ε2) for any comparable procedure. We use our techniques to show that circuits in the Quantum Approximate Optimization Algorithm (QAOA) with p entangling layers can be simulated by circuits on a fraction of the original number of qubits with an overhead that is roughly 2O(pκ) , where κ is the size of a known balanced vertex separator of the graph which encodes the optimization problem. We obtain numerical evidence of practical speedups using our method applied to the QAOA, compared to prior work. Finally, we investigate the practical feasibility of applying the circuit cutting procedure to large-scale QAOA problems on clustered graphs by using a 30 -qubit simulator to evaluate the variational energy of a 129 -qubit problem as well as carry out a 62 -qubit optimization.
We propose a new method to extend the size of a quantum computation beyond the number of physical qubits available on a single device. This is accomplished by randomly inserting measure-and-prepare channels to express the output state of a large circuit as a separable state across distinct devices. Our method employs randomized measurements, resulting in a sample overhead that is O~(4k/ε2) , where ε is the accuracy of the computation and k the number of parallel wires that are "cut" to obtain smaller sub-circuits. We also show an information-theoretic lower bound of Ω(2k/ε2) for any comparable procedure. We use our techniques to show that circuits in the Quantum Approximate Optimization Algorithm (QAOA) with p entangling layers can be simulated by circuits on a fraction of the original number of qubits with an overhead that is roughly 2O(pκ) , where κ is the size of a known balanced vertex separator of the graph which encodes the optimization problem. We obtain numerical evidence of practical speedups using our method applied to the QAOA, compared to prior work. Finally, we investigate the practical feasibility of applying the circuit cutting procedure to large-scale QAOA problems on clustered graphs by using a 30 -qubit simulator to evaluate the variational energy of a 129 -qubit problem as well as carry out a 62 -qubit optimization.
Current quantum computers suffer from a limited number of qubits and high error rates, limiting practical applicability. Different techniques exist to mitigate these effects and run larger algorithms. In this work, we analyze one of these techniques called quantum circuit cutting. With circuit cutting, a quantum circuit is decomposed into smaller sub-circuits, each of which can be run on smaller quantum hardware. We compare the performance of quantum circuit cutting with different cutting strategies, and then apply circuit cutting to a QAOA algorithm. Using simulations, we first show that Randomized Clifford measurements outperform both Pauli and random unitary measurements. Second, we show that circuit cutting has trouble providing correct answers in noisy settings, especially as the number of circuits increases.
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.
Quantum Approximate Optimization Algorithms (QAOA) have demonstrated a strong potential in addressing graph-based optimization problems. However, the execution of large-scale quantum circuits remains constrained by the limitations of current quantum hardware. In this work, we introduce QuantCut, an automatic framework for circuit cutting that enables efficient execution of large quantum circuits by decomposing entangling two-qubit gates into manageable sub-circuits. Specifically, we focus on gate-cutting techniques. We apply QuantCut to a 71-qubit QAOA circuit ansatz for portfolio diversification in the S&P 500 stock market, aiming to maximize asset diversification. Our approach iteratively optimizes the expectation value while leveraging circuit-cutting strategies to reduce the qubit register size. To validate our framework, we first conduct experiments on a toy model using quantum noise simulations for the Max-Cut problem, analyzing performance improvements with an increasing number of layers. Subsequently, we extend our methodology to a real-world financial optimization scenario, showing competitive results. The results suggest that QuantCut effectively facilitates large-scale quantum computations with circuit-cutting technologies.
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 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.
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