Extended Quantum Computing Patterns

How to partition the computation of a quantum circuit into multiple smaller computations fitting the capabilities of available quantum devices?

The maximum circuit width that a quantum device is able to execute is determined by its qubit count. As a result, devices with a limited number of qubits are restricted to executing circuits of small widths. Additionally, current NISQ devices face further limitations, such as high error rates and low coherence times, which impose restrictions on the number of gates that can be executed successfully in a circuit.

For smaller quantum devices, limited by their number of qubits and successfully executable gates, to contribute to the computation of a larger quantum circuit, it is necessary to divide the larger circuit into several smaller computations. Each of these smaller computations must require fewer resources, while collectively they must preserve the original circuit's result. However, several factors hinder the partitioning of a quantum circuit into multiple smaller computations. First, multi-qubit gates in a quantum circuit can create entanglement between the qubits on which they operate, resulting in the interdependence of their states. As a result, a quantum circuit with all qubits interconnected by multi-qubit gates cannot be partitioned into smaller, disconnected circuits that can be independently computed and then combined to produce the same result as the original circuit. Furthermore, removing multi-qubit gates to partition the circuit alters the computation's result. Moreover, the absence of shared entanglement or other means of quantum communication between quantum devices renders the distribution of a quantum circuit computation over multiple devices impossible.

Employ circuit cutting to divide a quantum circuit's computation into the computation of smaller circuits [Peng et al., 2020 Mitarai et al., 2021] as shown in the sketch. In the first step, the circuit is divided into multiple different variations of it, known as subcircuits. Each of these subcircuits can be partitioned along a cutting line, allowing the individual execution of its disconnected parts in the second step. In the final third step, these separate results can be combined for each subcircuit, and their outcomes are then merged to obtain the original circuit's output using classical post-processing.

Each individual subcircuit execution requires fewer qubits and gates, consequently reducing the hardware requirements of the quantum devices and enhancing the overall computation's robustness against errors and decoherence. Replacing the original circuit with a linear combination of subcircuits resulting from the cut enables replicating the effect of entanglement and, consequently, also the result. Each partitioned subcircuit can be executed successively on one or concurrently on multiple quantum devices to decrease the overall runtime of the computation [Bravyi et al, 2022]. However, compared to directly executing the original circuit, more shots are needed due to the multiplicative factor each cut introduces for estimating the expectation value with desired statistical accuracy [Piveteau et al, 2024]. To minimize the resulting additional overhead and error propagation, the placement of cuts, e.g. WIRE CUTs and GATE CUTs, and the structure of the subcircuits should be optimized [Casciola et al., 2022]. Achieving this optimization can be automated through the utilization of mixed-integer programming techniques [Tang et al., 2021].

–

Circuit cutting uses the GATE CUT and WIRE CUT patterns to decompose quantum circuits. The ORCHESTRATED EXECUTION can manage the control and data flow for circuit cutting, while PRIORITIZED EXECUTION can speed up subcircuit execution. Circuit cutting can be applied in VQAs, e.g., VQE or QAOA. It can also be used in combination with quantum error handing techniques, such as READOUT ERROR MITIGATION or GATE ERROR MITIGATION.

Circuit cutting has been utilized in several works to extend the width of executable circuits beyond a device's qubit limit [Tang et al., 2021, Ying et al., 2023] and improve results [Ayral et al., 2021, Bechtold et al.,2023]. Implementations are integrated into Pennylane and Qiskit's Circuit Knitting Toolbox. Additionally, a workflow modeling extension has been introduced for orchestrating circuit cutting [Beisel et al., 2023].