Learning Enables Exponential-to-Polynomial Sampling Overhead Scaling in Quantum Divide-and-Conquer for Tree-Structured Circuits

Abstract

Quantum circuit cutting and knitting are divide-and-conquer methods that enable large-scale quantum computations on hardware with limited qubit resources and connectivity by decomposing a target computation into smaller local experiments. Existing methods, however, typically incur a sampling overhead that grows exponentially with the number of cut locations, leaving open the question of whether this barrier is intrinsic. Here we show that this barrier is not universal by introducing a learning-based cutting protocol tailored to the target observable. At each cut, the protocol locally learns a Heisenberg-picture effective observable that captures the downstream information relevant to the final measurement and uses it to construct an observable-adaptive cut. This replaces the multiplicative variance amplification of conventional cutting with additive bias accumulation controlled by local learning accuracy. We apply this framework to finite tree-structured circuits. For any finite rooted tree with $K$ cut wires and cut-system dimension at most $d$, the protocol estimates the target expectation value within additive error $\hat{I}\mu$ with high probability using $\tilde{O}(d^3{K}^3/\hat{I}{\mu }^2)$ measurements, including the local learning cost. Moreover, for two-layer trees with $R$ cut wires, we prove an information-theoretic exponential separation between our learning-based protocol and learning-free wire-cutting protocols based on pre-specified randomized cutting rules: even with arbitrary classical post-processing, any such learning-free protocol requires $\hat{I}\text{c◯}((d+1{)}^R/\hat{I}{\mu }^2)$ measurements, whereas our protocol uses $\tilde{O}(d^3{R}^3/\hat{I}{\mu }^2)$. These results identify local learning, rather than the tree structure alone, as the key mechanism driving the exponential-to-polynomial reduction in sampling overhead.

67 pages, 9 figures. Substantially updated version: generalized tree analysis, strengthened lower-bound formulation, expanded relation to prior work, and numerical simulations