Quantum computing has shown great potential in addressing traditional computational challenges, but due to its high error rates and noise issues, classical simulation has become an essential tool for verifying its performance. However, the superposition and entanglement properties of quantum systems pose significant challenges for simulation, especially when memory is limited. Although circuit cutting methods can decompose large-scale quantum circuits into smaller computational tasks to reduce computational load, previous research primarily focused on their application to quantum computers, without fully considering their effectiveness in quantum circuit simulation. This study fills that gap by proposing an optimization scheme based on a heuristic cutting algorithm and subcircuit state vector reuse to address memory limitations in simulations. By incorporating global computational cost considerations and an integer programming model, the heuristic method proposed in this paper not only optimizes the cutting process but also combines subcircuit state vector reuse to reduce redundant calculations and memory usage. Experimental results show that compared to current popular circuit cutting methods, the proposed approach significantly improves simulation speed while reducing memory requirements, effectively addressing the challenges in quantum circuit simulation. The overall average speedup achieved 46%.
Quantum computing has shown great potential in addressing traditional computational challenges, but due to its high error rates and noise issues, classical simulation has become an essential tool for verifying its performance. However, the superposition and entanglement properties of quantum systems pose significant challenges for simulation, especially when memory is limited. Although circuit cutting methods can decompose large-scale quantum circuits into smaller computational tasks to reduce computational load, previous research primarily focused on their application to quantum computers, without fully considering their effectiveness in quantum circuit simulation. This study fills that gap by proposing an optimization scheme based on a heuristic cutting algorithm and subcircuit state vector reuse to address memory limitations in simulations. By incorporating global computational cost considerations and an integer programming model, the heuristic method proposed in this paper not only optimizes the cutting process but also combines subcircuit state vector reuse to reduce redundant calculations and memory usage. Experimental results show that compared to current popular circuit cutting methods, the proposed approach significantly improves simulation speed while reducing memory requirements, effectively addressing the challenges in quantum circuit simulation. The overall average speedup achieved 46%.
Quantum computing has the potential to accelerate various fields by solving specific problems significantly faster than classical computers. Solving more complex problems generally requires a larger number of qubits. However, current quantum devices are constrained by limited qubit counts and environmental noise. Quantum circuit cutting bridges the gap between the theoretical requirements of large quantum circuits and the practical limitations of current quantum hardware by decomposing large circuits into smaller subcircuits. Tang et al. introduced CutQC, a framework that reduces the number of generated subcircuits and reconstructs the complete quantum state with limited memory consumption. Despite these advances, CutQC faces performance bottlenecks in classical postprocessing, leading to long execution times. To address this limitation, we propose QCutSim, an efficient simulation-based framework guided by insights from the postprocessing stage. It improves performance through optimized simulation and reconstruction strategies, along with computational optimizations such as vectorization and parallelization. QCutSim demonstrates that even consumer-grade systems can efficiently simulate 100-qubit circuits and achieves a speedup of up to 5.1x compared to prior work on the same hardware. In the worst-case scenario of reconstructing dense solution circuits, QCutSim achieves a speedup of 6 to 8 orders of magnitude.
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.
Circuit cutting partitions a large quantum circuit into smaller subcircuits that can be executed independently and recombined by classical post-processing. In classical state-vector simulation with full-state reconstruction, the runtime is governed by a trade-off between reduced subcircuit size and the overheads of exponentially many subcircuits and full-state reconstruction. For equal partitioning, we derive threshold conditions on the number of cuts below which cutting reduces the wall-clock time. State-vector experiments validate the predicted speedup boundary up to 24 qubits, and a runtime breakdown up to 30 qubits identifies crossovers at q≈18 and q≈22 where merging overtakes first preprocessing and then subcircuit simulation. As a practical guideline, we show that under a 10-minute wall-clock budget, two-way cutting extends the maximum feasible qubit count by 4 to 6 qubits relative to simulation without 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
Executing large quantum circuits is not feasible using the currently available NISQ (noisy intermediate-scale quantum) devices. The high costs of using real quantum devices make it further challenging to research and develop quantum algorithms. As a result, performing classical simulations is usually the preferred method for researching and validating large-scale quantum algorithms. However, these simulations require a huge amount of resources, as each additional qubit exponentially increases the computational space required. Distributed Quantum Computing (DQC) is a promising alternative to reduce the resources required for simulating large quantum algorithms at the cost of increased runtime. This study presents a comparative analysis of two simulation methods: circuit-splitting and full-circuit execution using distributed memory, each having a different type of overhead. The first method, using CutQC, cuts the circuit into smaller subcircuits and allows us to simulate a large quantum circuit on smaller machines. The second method, using Qiskit-Aer-GPU, distributes the computational space across a distributed memory system to simulate the entire quantum circuit. Results indicate that full-circuit executions are faster than circuit-splitting for simulations performed on a single node. However, circuit-splitting simulations show promising results in specific scenarios as the number of qubits is scaled.
A limited number of qubits, high error rates, and limited qubit connectivity are major challenges for effective near-term quantum computations. Quantum circuit partitioning divides a quantum computation into classical postprocessing steps and a set of smaller-scale quantum computations that individually require fewer qubits, lower qubit connectivity, and typically incur less error. However, as partitioning generally increases the duration of a quantum computation exponentially in the required partitioning effort, it is crucial to select optimal partitioning points, so-called cuts, and to use optimal cut realizations. In this work, we develop the first optimal partitioning method relying on quantum circuit knitting for optimal cut realizations and an optimal selection of wire cuts and gate cuts that trades off ancilla qubit insertions for a decrease in quantum computing time. Using this combination, the developed method demonstrates a reduction in quantum computing runtime by 41% on average compared to previous quantum circuit partitioning methods. Furthermore, the qubit requirement of the evaluated quantum circuits was reduced by 40% on average for a runtime budget of one hour and a sampling frequency of 1 kHz. These results highlight the optimality gap of previous quantum circuit partitioning methods and the possible extension in the computational reach of near-term quantum computers.