  The inevitable accumulation of errors in near-future quantum devices
represents a key obstacle in delivering practical quantum advantages,
motivating the development of various quantum error-mitigation methods. Here,
we derive fundamental bounds concerning how error-mitigation algorithms can
reduce the computation error as a function of their sampling overhead. Our
bounds place universal performance limits on a general error-mitigation
protocol class. We use them to show (1) that the sampling overhead that ensures
a certain computational accuracy for mitigating local depolarizing noise in
layered circuits scales exponentially with the circuit depth for general
error-mitigation protocols and (2) the optimality of probabilistic error
cancellation among a wide class of strategies in mitigating the local dephasing
noise on an arbitrary number of qubits. Our results provide a means to identify
when a given quantum error-mitigation strategy is optimal and when there is
potential room for improvement.
