Improved sampling bounds and scalable partitioning for quantum circuit cutting beyond bipartitions

We propose a new method for identifying cutting locations for quantum circuit cutting, with a primary focus on partitioning circuits into three or more parts. Under the assumption that the classical postprocessing function is decomposable, we derive a new upper bound on the sampling overhead resulting from both timelike and spacelike cuts. We show that this bound improves upon the previously known bound by orders of magnitude in cases of three or more partitions. Based on this bound, we formulate an objective function ${L}_{Q}$ and present a method to determine cutting locations that minimize it. Our method is shown to outperform a previous approach in terms of computation time. Moreover, the quality of the obtained partitioning is found to be comparable to or better than that of the baseline in all but a few cases, as measured by ${L}_{Q}$. These results are obtained by identifying cutting locations in a number of benchmark circuits of the size and type expected in quantum computations that outperform classical computers.