Exponentially tighter bounds on limitations of quantum error mitigation

The paper asks how effectively quantum error mitigation (QEM) can reverse noise on near-term quantum devices using only classical post-processing of measurement outcomes. While QEM avoids the heavy overheads of fault-tolerant error correction, its true scalability and limits remain unclear. The authors frame QEM as either estimating expectation values of observables (weak QEM) or sampling from the noiseless output distribution (strong QEM), reflecting key targets in variational algorithms and combinatorial optimization. The central hypothesis is that substantial, intrinsic information-theoretic limitations constrain QEM’s sample efficiency well before circuit depths where prior bounds suggested issues, especially once entanglement spreads. By connecting QEM to a statistical inference (noisy state discrimination) problem and tracking how noise contracts distinguishability, the work aims to show superpolynomial-to-exponential sample complexity for QEM even at very shallow depths when circuit width (number of qubits) is taken into account. The study is important for setting realistic expectations for near-term quantum advantage and guiding the design of circuits and mitigation protocols.

Prior works established information-theoretic lower bounds on QEM sample complexity under depolarizing and related Pauli/thermal noise models, showing exponential dependence on circuit depth but not on width, implying feasibility up to O(log n) depths. Additionally, it is known that depolarizing noise drives states toward the maximally mixed state at rates exponential in depth, suggesting the loss of advantage beyond logarithmic depth without error correction. However, these analyses typically ignore width scaling and often assume identity or simple circuit structures. The present work tightens bounds by introducing explicit dependence on the number of qubits n and by analyzing non-unital noise (e.g., T1 decay), a key noise source in superconducting qubits. It contrasts with ensembles of noisy random Clifford circuits whose mixing toward uniformity is exponential in depth alone, arguing that highly entangling, Pauli-mixing Clifford two-design constructions scramble faster and thus are more sensitive to noise. The authors also connect to broader consequences in variational algorithms (noise-induced barren plateaus), kernel methods, and limits on noisy sampling advantage.

- Formalization of QEM tasks: The authors define weak QEM (estimating expectation values of a set of observables for the noiseless output state) and strong QEM (producing samples from the noiseless output distribution up to additive or multiplicative error). The model allows knowledge of the noiseless circuit and noise channel, optional knowledge of the input state (input-state-aware vs agnostic), and even collective measurements across multiple copies of the noisy output state. - Reduction to statistical inference: QEM is related to a noisy state discrimination problem: given copies of C′(ρ_i) (noisy outputs) and classical descriptions of the candidate states/circuit, identify i. If state discrimination requires at least m samples, then weak QEM requires at least m samples. The generalized Fano method for multiple hypotheses provides lower bounds on sample complexity via decay of distinguishability (quantum relative entropy) under noise. - Information-theoretic quantity: The key control parameter is the quantum relative entropy to the maximally mixed state, D(σ || I/2^n), with upper bounds obtained via the 2-Rényi entropy (purity) Tr(σ^2). The inverse decay rate of D(·||I/2^n) gives lower bounds on the sample complexity. - Circuit constructions: The authors design circuits from highly entangling, Pauli-mixing Clifford two-design layers interleaved with local noise. Pauli mixing spreads amplitudes uniformly over non-identity Pauli strings, pushing weight to higher Hamming-weight Paulis. Depolarizing (and more generally Pauli) noise damps higher-weight Pauli strings exponentially in their weight, causing fast purity decay, hence rapid contraction in relative entropy to the maximally mixed state. - Purity and Pauli-weight analysis: Expanding states in the Pauli basis, the contribution of weight-k Pauli strings to purity after alternating two-design and noise layers is quantified. Depolarizing noise scales a weight-k Pauli component by p^k; Pauli mixing ensures equal weighting over Paulis of the same weight, so entanglement growth makes the state disproportionately sensitive to noise. - Noise models and locality: Results cover unital depolarizing noise (local and global), extend to non-unital noise (e.g., T1-type channels), and consider geometrically local circuits on d-dimensional lattices. For non-unital noise, the analysis uses expected overlaps after alternating global two-design unitaries and local noise. - Input-state awareness and strong vs weak QEM: The study proves lower bounds for input-state-agnostic algorithms and extends to input-state-aware settings by showing that, unless exponentially many noisy copies are used, a classical algorithm can match the mitigator’s output. It further analyzes when weak QEM outputs can or cannot be bootstrapped to strong QEM outputs, showing exponential query requirements in general.

- Exponential sample complexity with width and depth (Theorem 1): For weak QEM on n-qubit, D-layer circuits under local depolarizing noise with parameter p, the required number of noisy copies scales at least as s′ p^{−(nD)/s} for suitable s>0, implying exponential dependence on the product nD. Consequently, even at depths as small as poly log log(n), superpolynomially many samples are required in the worst case. Prior bounds only scaled exponentially with depth; introducing width leads to exponentially tighter limitations. - Geometric locality: For d-dimensional geometrically local circuits, exponentially many samples are required already at depths O(n^{1/d} poly log n), and even at depths O(log n · poly log log n), the sample complexity is superpolynomial. The difficulty is governed by the number of gates in the light cone of the observable, not just circuit depth. - Non-unital noise (Theorem 2): For circuits formed by alternating layers from a unitary two-design and local non-unital noise N^{⊗n}, weak QEM typically requires a number of samples exponential in both the number of noise applications (depth) and the number of qubits. Formally, at least c^{−cD} (for some noise-dependent 0<c<1) copies are needed, expressing an exponential-in-D lower bound; combined with n-fold locality, this yields exponential scaling in n and D. - Necessity of quantum samples vs classical baselines (Theorem 3): Any successful weak QEM algorithm must, in the worst case, use m = c^{(nD)} copies of the noisy output, or else there exists a purely classical algorithm with indistinguishable output. Thus, leveraging the noisy quantum device to outperform classical post-processing alone requires exponentially many samples in worst-case instances. - Weak-to-strong bootstrapping barrier (Theorem 4): To convert weak QEM (expectation values) into strong QEM (samples) when observables share an eigenbasis, an algorithm generally must query exp(n) distinct observables, ruling out efficient bootstrapping protocols of this kind. - Earlier onset of scrambling and loss of advantage: The constructed circuits exhibit decay of relative entropy to the maximally mixed state at depths as small as poly log log(n), far earlier than the O(log n) depths suggested by prior analyses. This precipitates early failure of QEM, earlier noise-induced barren plateaus in variational algorithms, constraints on kernel estimation, and rules out exponential quantum speed-ups for expectation value estimation in the presence of noise. - Implications for ground-state preparation: In worst-case settings and for circuits of depth polylogarithmic in n, unless error probability p scales as O((nD)^{-1}), noisy outputs concentrate around energies that preclude quantum advantage, indicating a lose-lose trade-off between sufficient depth for expressivity and noise-induced concentration.

The results show that when entanglement spreads rapidly—as in Pauli-mixing, highly entangling two-design constructions—noise contracts distinguishability from the maximally mixed state at rates exponential in both qubit number and depth. This fundamentally limits the efficacy of error mitigation: even with knowledge of the noise and access to collective measurements, QEM must expend exponentially many samples in worst-case instances at very shallow depths. The findings bridge QEM with statistical decision theory: effective mitigation implies the ability to discriminate noisy states, and limits on relative entropy decay yield sample lower bounds. They also clarify that observed exponential sampling costs for practical protocols like zero-noise extrapolation and probabilistic error cancellation are near-optimal in the worst case unless tailored to special circuit structures. Practically, the work suggests designing circuits with limited entanglement spread or geometric locality to delay noise-induced scrambling, potentially improving QEM performance at the cost of expressivity. Conceptually, it highlights a core tension: the entanglement needed for quantum advantage also accelerates noise propagation, undermining mitigation.

This work establishes exponentially tighter, information-theoretic lower bounds on the sample complexity of quantum error mitigation by incorporating circuit width into the analysis. By recasting QEM as noisy state discrimination and leveraging purity/relative-entropy decay under interleaved Clifford two-designs and realistic noise models (including non-unital noise), the authors prove that superpolynomial to exponential samples are required even at depths as small as poly log log(n). They further show barriers to bootstrapping weak into strong QEM and demonstrate that in the worst case, quantum sampling is necessary to outperform purely classical procedures. The implications are broad: earlier loss of quantum advantage in noisy settings, constraints on variational and kernel methods, and severe limits on noisy ground-state preparation. Future work includes relaxing global connectivity assumptions to purely local architectures, developing circuit designs that limit entanglement spread while maintaining utility, and creating intermediate, parsimonious error-correction schemes that bridge QEM and full fault tolerance.

- Worst-case focus: Bounds are worst-case and may not reflect typical instances or specially structured circuits used in practice. - Circuit constructions: The primary constructions rely on highly entangling, Pauli-mixing two-design layers with all-to-all connectivity to achieve rapid mixing; extending tight results to strictly local architectures remains an open direction (though partial results are provided for d-dimensional lattices). - Noise modeling: While both unital (depolarizing) and non-unital noise are analyzed, some non-unital results assume alternating global unitaries with layer-wise local noise, a simplified but insightful model. - Resource assumptions: Lower bounds hold even allowing collective measurements and exact noise knowledge; practical protocols may have stricter constraints, but the model’s power means the bounds are fundamental rather than artifact of restricted access. - Input-state awareness: Although extended to input-state-aware algorithms, conclusions rely on indistinguishability from classical procedures unless exponentially many samples are used, leaving room for specialized strategies on specific input families.