  One of the central problems for near-term quantum devices is to understand
their ultimate potential and limitations. We address this problem in terms of
quantum error mitigation by introducing a framework taking into account the
full expressibility of near-term devices, in which the optimal resource cost
for the probabilistic error cancellation method can be formalized. We provide a
general methodology for evaluating the optimal cost by connecting it to a
resource-theoretic quantifier defined with respect to the noisy operations that
devices can implement. We employ our methods to estimate the optimal cost in
mitigating a general class of noise, where we obtain an achievable cost that
has a generic advantage over previous evaluations, as well as a fundamental
lower bound applicable to a broad class of noisy implementable operations. We
improve our bounds for several noise models, where we give the exact optimal
costs for the depolarizing and dephasing noise, precisely characterizing the
overhead cost while offering an operational meaning to the resource measure in
terms of error mitigation. Our result particularly implies that the heuristic
approach presented by Temme et al. [K. Temme, S. Bravyi, and J. M. Gambetta,
Phys. Rev. Lett. 119, 180509 (2017)] is optimal even in our extended framework,
putting fundamental limitations on the advantage provided by the extra degrees
of freedom inherent in near-term devices for this noise model.
