CuKnit: Optimized Partitioning of Quantum Circuits using Knitting and Cutting

The limited number of qubits is a major challenge for effective near-term quantum computations. Prior art proposed partitioning a quantum computation into a set of sub-circuits using a lower number of qubits than the original computation. These partitioning techniques resolve dependencies within a quantum computation, given either by a qubit-wire or an n-qubit gate, by executing exponential numbers of sub-circuits and classical post-processing. In this work we address the partitioning of quantum circuits by resolving qubit-wire dependencies using circuit knitting and by developing a formal model that allows optimal selection of gate and qubit-wire cuts for dependency resolution.