Universal Sampling Lower Bounds for Quantum Error Mitigation

Introduction — As recent technological developments have started to realize controllable small-scale quantum devices, a central problem in quantum information science has been to pin down what can and cannot be accomplished with noisy intermediate-scale quantum (NISQ) devices [1]. One of the most relevant issues in understanding the ultimate capability of quantum hardware is to characterize how well noise effects could be circumvented. This is especially so for NISQ devices, as today’s quantum devices generally cannot accommodate full quantum error correction that requires scalable quantum architecture. As an alternative to quantum error correction, quantum error mitigation has recently attracted much attention as a potential tool to help NISQ devices realize useful applications [2, 3]. It is thus of primary interest from practical and foundational viewpoints to understand the ultimate feasibility of quantum error mitigation.

Quantum error mitigation protocols generally involve running available noisy quantum devices many times. The collected data is then post-processed to infer classical information of interest. While this avoids the engineering challenge in error correction, it comes at the price of sampling cost — computational overhead in having to sample a noisy device many times. This sampling cost represents the crucial quantity determining the feasibility of quantum error mitigation. If the required sampling cost becomes too large, then such quantum error mitigation protocol becomes infeasible under a realistic time constraint. Various prominent quantum error mitigation methods face this problem, where sampling cost grows exponentially with circuit size [4, 5, 6, 7, 8]. The crucial question then is whether there is hope to come up with a new error mitigation strategy that avoids this hurdle or if this is a universal feature shared by all quantum error mitigation protocols. To answer this question, we need a characterization of the sampling cost that is universally required for the general error-mitigation protocols, which has hitherto been unknown.

Here, we provide a solution to this problem. We derive lower bounds for the number of samples fundamentally required for general quantum error mitigations to realize the target performance. We then show that the required samples for a wide class of mitigation protocols to error-mitigate layered circuits under various noise models — including the depolarizing and stochastic Pauli noise — must grow exponentially with the circuit depth to achieve the target performance. This turns the conjecture that quantum error mitigation would generally suffer from the exponential sampling overhead into formal relations, extending the previous results on the exponential resource overhead required for noisy circuits without postprocessing [9, 10, 11]. We accomplish these by employing an information-theoretic approach, which establishes the novel connection between the state distinguishability and operationally motivated error-mitigation performance measures. Our results place the fundamental limitations imposed on the capability of general error-mitigation strategies that include existing protocols [5, 6, 12, 13, 7, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 8, 25, 26, 27, 28, 29, 30, 31] and the ones yet to be discovered, being analogous to the performance converse bounds established in several other disciplines — such as thermodynamics [32, 33, 34], quantum communication [35, 36], and quantum resource theories [37, 38] — that contributed to characterizing the ultimate operational capability allowed in each physical setting.

Our work complements and extends several recent advancements in the field. Ref. [39] introduced a general framework of quantum error mitigation and established lower bounds for the maximum estimator spread, i.e., the range of the outcomes of the estimator, imposed on all error mitigation in the class, which provides a sufficient number of samples to ensure the target accuracy. Those bounds were then employed to show that the maximum spread grows exponentially with the circuit depth to mitigate local depolarizing noise. Ref. [40] showed a related result where for the class of error-mitigation strategies that only involve linear postprocessing, in which the target expectation value can be represented by a linear combination of the actually observed quantities, either the maximum estimator spread or the sample number needs to grow exponentially with the circuit depth to mitigate local depolarizing noise. The severe obstacle induced by noise in showing a quantum advantage for variational quantum algorithms has also recently been studied [41, 42, 43]. Our results lift the observations made in these works to rigorous bounds for the necessary sampling cost required for general error mitigation, including the ones involving nonlinear postprocessing that constitute a large class of protocols [12, 13, 7, 14, 15, 16, 17, 25, 27, 29, 30, 21, 22, 24, 44, 19, 31].

Framework — Suppose we wish to obtain the expectation value of an observable $A\in\mathbb{O}$ for an ideal state $\rho\in\mathbb{S}$ where $\mathbb{O}$ and $\mathbb{S}$ are some sets of observables and states. We assume that the ideal quantum state $\rho$ is produced by a unitary quantum circuit $\mathcal{U}$ applied to the initial state $\rho_{\rm ini}\in\mathbb{S}_{\rm in}$ as $\rho=\mathcal{U}(\rho_{\rm ini})$ where $\mathbb{S}_{\rm in}$ is the set of possible input states. The noise in the circuit, however, prevents us from preparing the state $\rho$ exactly. We consider quantum error mitigation protocols that aim to estimate the true expectation value under the presence of noise in the following manner [39] (see also Fig. 1).

In the mitigation procedure, one can first modify the circuit, e.g., use a different choice of unitary gates with potential circuit simplification, apply nonadaptive operations (enabling, e.g., dynamical decoupling [45, 46] and Pauli twirling [6]), and supply ancillary qubits — the allowed modifications are determined by the capability of the available device. Together with the noise present in the modified circuit, this turns the original unitary $\mathcal{U}$ into some quantum channel $\mathcal{F}$, which produces a distorted state $\rho^{\prime}$. The distorted state can be represented in terms of the ideal state $\rho$ by $\rho^{\prime}=\mathcal{E}(\rho)$ where we call $\mathcal{E}\coloneqq\mathcal{F}\circ\mathcal{U}^{\dagger}$ an effective noise channel.

The second step consists of collecting $N$ samples $\{\mathcal{E}_{n}(\rho)\}_{n=1}^{N}$ of distorted states represented by a set of effective noise channels $\mathbb{E}\coloneqq\{\mathcal{E}_{n}\}_{n=1}^{N}$ and applying a trailing quantum process $\mathcal{P}_{A}$ over them. The effective noise channels in $\mathbb{E}$ can be different from each other in general, as noisy hardware could have different noise profiles each time, or could purposely change the noise strength [47, 5]. The trailing process $\mathcal{P}_{A}$ then outputs an estimate represented by a random variable $\hat{E}_{A}(\rho)$ for the true expectation value $\operatorname{Tr}(A\rho)$. The main focus of our study is the sampling number $N$, the total number $N$ of distorted states used in the error mitigation process.

We quantify the performance of an error-mitigation protocol by how well the protocol can estimate the expectation values for a given set $\mathbb{O}$ of observables and a set $\mathbb{S}$ of ideal states, which we call target observables and target states respectively. We keep the choices of these sets general, and they can be flexibly chosen depending on one’s interest. For instance, if one is interested in error mitigation protocols designed to estimate the Pauli observables (e.g., virtual distillation [15, 16, 21]), $\mathbb{O}$ can be chosen as the set of Pauli operators. As the trailing process includes a measurement depending on the observable, an error-mitigation strategy with target observables $\mathbb{O}$ is equipped with a family of trailing processes $\{\mathcal{P}_{A}\}_{A\in\mathbb{O}}$. Similarly, our results hold for an arbitrary choice of $\mathbb{S}$, where one can, for instance, choose this as the set of all quantum states, which better describes the protocols such as probabilistic error cancellation [47, 5, 48, 49, 50, 51, 52], or as the set of states in a certain subspace, which captures the essence of subspace expansion [12, 14, 17].

This framework includes many error-mitigation protocols proposed so far [5, 6, 12, 13, 7, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 8, 25, 26, 27, 28, 29, 30, 31]. It is worth noting that our framework includes protocols that involve nonlinear postprocessing of the measurement outcomes. Error-mitigation protocols typically work by (1) making some set of (usually Pauli) measurements for observables $\{O_{i}\}_{i}$, (2) estimating their expectation values $\{\left\langle O_{i}\right\rangle\}_{i}$ for distorted states, and (3) applying a classical postprocessing function $f$ over them. The protocols with linear postprocessing functions, i.e., the ones with the form $f(\left\langle O_{i}\right\rangle_{i})=\sum_{i}c_{i}\left\langle O_{i}\right\rangle$, are known to admit simpler analysis [40, 39], but numerous protocols — including virtual distillation [15, 16, 21], symmetry verification [13], and subspace expansion [12, 14, 17] — come with nonlinear postprocessing functions. In our framework, the sampling number $N$ is the total number of samples used, where we consider the output represented by $\hat{E}_{A}(\rho)$ as our final guess and thus do not generally assume repeating some procedure many times and take a statistical average. This enables us to have any postprocessing absorbed in the trailing process $\mathcal{P}_{A}$, making our results valid for the protocols with nonlinear postprocessing functions.

We also remark that our framework includes protocols with much more operational power than existing protocols, as we allow the trailing process to apply any coherent interaction over all distorted states. Our results thus provide fundamental limits on the sampling overhead applicable to an arbitrary protocol in this extended class of error-mitigation protocols.

Sampling lower bounds — We now consider the required samples to ensure the target performance. The performance of quantum error mitigation can be defined in multiple ways. Here, we consider two possible performance quantifiers that are operationally relevant.

Our first performance measure is the combination of the accuracy of the estimate and the success probability. This closely aligns with the operational motivation, where one would like an error mitigation strategy to be able to provide a good estimate for each observable in $\mathbb{O}$ and an ideal state in $\mathbb{S}$ at a high probability. This can be formalized as a condition

where $\delta$ is the target accuracy and $1-\varepsilon$ is the success probability (see also Fig. 1).

The problem then is to identify lower bounds on the number $N$ of distorted states needed to achieve this condition as a function of $\delta$ and $\varepsilon$. We address this by observing that the trailing process of quantum error mitigation is represented as an application of a quantum channel and thus can never increase the state distinguishability. To formulate our result, let us define the observable-dependent distinguishability with respect to a set $\mathbb{O}$ of observables as

This quantity can be understood as the resolution in distinguishing two quantum states by using the measurements of the observables in $\mathbb{O}$. We note that when $\mathbb{O}=\{A\,|0\leq A\leq\mathbb{I}\}$ ¹¹1Here, we consider the standard matrix inequality with respect to the positive semidefinite cone, i.e., $M_{1}\leq M_{2}$ for two matrices $M_{1}$ and $M_{2}$ means that the matrix $M_{2}-M_{1}$ is positive semidefinite., the quantity in (2) becomes the trace distance $D_{\operatorname{tr}}(\rho,\sigma)=\frac{1}{2}\|\rho-\sigma\|_{1}$ [54].

We then obtain the following sampling lower bounds applicable to an arbitrary given set $\mathbb{E}$ of effective noise channels. (Proof in Appendix A ²²2See the Supplemental Material for detailed proofs and discussions of our main results, which includes Refs. [56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80].)

This result tells that if the noise effect brings states close to each other, it incurs an unavoidable sampling cost to error mitigation. The minimization over $\mathbb{E}$ chooses the effective noise channel that least reduces the infidelity and the relative entropy respectively. On the other hand, the maximum over the ideal states represents the fact that to mitigate two states $\rho$ and $\sigma$ that are separated further than $2\delta$ in terms of observables in $\mathbb{O}$, the sample number $N$ that achieves the accuracy $\delta$ and the success probability $1-\varepsilon$ must satisfy the lower bounds with respect to $\rho$ and $\sigma$. The maximization over such $\rho$ and $\sigma$ then provides the tightest lower bound. This also reflects the observation that error mitigation accommodating a larger set $\mathbb{O}$ of target observables would require a larger number of samples.

We remark that although the set $\mathbb{E}$ — which depends on how one modifies the noisy circuit — ultimately depends on a specific error-mitigation strategy in mind, fixing $\mathbb{E}$ to a certain form already provides useful insights as we see later in the context of noisy layered circuits. We also stress that the above bounds hold for an arbitrary choice of $\mathbb{E}$, providing the general relation between the error mitigation performance and the information-theoretic quantity.

The bounds in Theorem 1 depend on the accuracy $\delta$ implicitly through the constraints on $\rho$ and $\sigma$ in the maximization. For instance, if one sets $\delta=0$, one can find that both bounds diverge, as the choice of $\sigma=\rho$ would be allowed in the maximization. In Appendix B, we report an alternative bound that has an explicit dependence on the accuracy $\delta$.

Let us now consider our second performance measure based on the standard deviation and the bias of the estimate. Let $\sigma_{A}^{\operatorname{QEM}}(\rho)$ be the standard deviation of $\hat{E}_{A}(\rho)$ for an observable $A\in\mathbb{O}$, which represents the uncertainty of the final estimate of an error mitigation protocol. Since a good error mitigation protocol should come with a small fluctuation in its outcome, the standard deviation of the underlying distribution for the estimate can serve as a performance quantifier. However, the standard deviation itself is not sufficient to characterize the error mitigation performance, as one can easily come up with a useless strategy that always outputs a fixed outcome, which has zero standard deviation. This issue can be addressed by considering the deviation of the expected value of the estimate from the true expectation value called bias, defined as $b_{A}(\rho)\coloneqq\left\langle\hat{E}_{A}(\rho)\right\rangle-\operatorname{Tr}(A\rho)$ for a state $\rho\in\mathbb{S}$ and an observable $A\in\mathbb{O}$ (see also Fig. 1).

To assess the performance of error-mitigation protocols, we consider the worst-case error among possible ideal states and measurements. This motivates us to consider the maximum standard deviation $\sigma_{\max}^{\operatorname{QEM}}\coloneqq\max_{A\in\mathbb{O}}\max_{\rho\in\mathbb{S}}\sigma_{A}^{\operatorname{QEM}}(\rho)$ and the maximum bias $b_{\max}\coloneqq\max_{A\in\mathbb{O}}\max_{\rho\in\mathbb{S}}b_{A}(\rho)$. Then, we obtain the following sampling lower bound in terms of these performance quantifiers. (Proof in Appendix C.)

This result represents the trade-off between the standard deviation, bias, and the required sampling cost. To realize the small standard deviation and bias, error mitigation needs to use many samples; in fact, the lower bound diverges at the limit of $\sigma_{\max}^{\operatorname{QEM}}\to 0$ whenever there exist states $\rho,\sigma\in\mathbb{S}$ such that $D_{\mathbb{O}}(\rho,\sigma)\geq 2b_{\max}$. On the other hand, a larger bias results in a smaller sampling lower bound, indicating a potential to reduce the sampling cost by giving up some bias.

The bounds in Theorems 1, 2 are universally applicable to arbitrary error mitigation protocols in our framework. Therefore, our bounds are not expected to give good estimates for a given specific error-mitigation protocol in general, just as there is a huge gap between the Carnot efficiency and the efficiency of most of the practical heat engines. Nevertheless, it is still insightful to investigate how our bounds are compared to existing mitigation protocols. In Appendix D, we compare the bound in Theorem 1 to the sampling cost for several error-mitigation methods, showing that our bound can provide nontrivial lower bounds with the gap being the factor of 3 to 6. Although this does not guarantee that our bound behaves similarly for other scenarios in general, this ensures that there is a setting in which the bound in Theorem 1 can provide a nearly tight estimate. We further show in Appendix E that the scaling of the lower bound in Theorem 2 with noise strength can be achieved by the probabilistic error cancellation method in a certain scenario. This shows that probabilistic error cancellation serves as an optimal protocol in this specific sense, complementing the recent observation on the optimality of probabilistic error cancellation established for the maximum estimator spread measure [39].

Noisy layered circuits — The above results clarify the close relation between the sampling cost and state distinguishability. As an application of our general bounds, we study the inevitable sample overhead to mitigate noise in the circuits consisting of multiple layers of unitaries. Although we here focus on the local depolarizing noise, our results can be extended to a number of other noise models as we discuss later.

Suppose that an $M$-qubit quantum circuit consists of layers of unitaries, each of which is followed by a local depolarizing noise, i.e., a depolarizing noise of the form $\mathcal{D}_{p}=(1-p)\operatorname{id}+p\mathbb{I}/2$ where $p$ is a noise strength, applies to each qubit. We aim to estimate ideal expectation values for the target states $\mathbb{S}$ and observables $\mathbb{O}$ by using $N$ such noisy layered circuits. Although the noise strength can vary for different locations, we suppose that $L$ layers are followed by the local depolarizing noise with noise strength of at least $\gamma$. We call these layers $U_{1},U_{2},\dots,U_{L}$ and let $\gamma_{n,l,m}$ denote the noise strength of the local depolarizing noise on the $m^{\rm th}$ qubit after the $l^{\rm th}$ unitary layer $U_{l}$ in the $n^{\rm th}$ noisy circuit, where $m\leq M,\,l\leq L,\,n\leq N$. This gives the expression of the local depolarizing noise after $l^{\rm th}$ layer in the $n^{\rm th}$ noisy circuit as $\otimes_{m=1}^{M}\mathcal{D}_{\gamma_{n,l,m}}$, where $\gamma_{n,l,m}\geq\gamma\,\forall n,l,m$.

Here, we focus on the error-mitigation protocols that apply an arbitrary trailing process over $N$ distorted states and any unital operations (i.e., operations that preserve the maximally mixed state) before and after $U_{l}$ (Fig. 2). This structure ensures that error correction does not come into play here, as the size of input and output spaces of the intermediate unital channels is restricted to $M$ qubits, as well as that unital channels do not serve as good decoders for error correction.

We show that the necessary number of samples required to achieve the target performance grows exponentially with the number of layers in both performance quantifiers introduced above.

The proof can be found in Appendix F. This result particularly shows that the required number of samples must grow exponentially with the circuit depth $L$. We remark that the bound always holds under the mild condition, i.e., $D_{\mathbb{O}}(\rho,\sigma)\geq 2\delta$ for some $\rho,\sigma\in\mathbb{S}$. This reflects that, to achieve the desired accuracy $\delta$ satisfying this condition, error mitigation really needs to extract the expectation values about the observables in $\mathbb{O}$ and the states in $\mathbb{S}$, prohibiting it from merely making a random guess.

In Appendix G, we obtain a similar exponential growth of the required sample overhead for a fixed target bias and standard deviation. We also obtain in Appendix H alternative bounds that are tighter in the range of small $\varepsilon$.

With a suitable modification of allowed unitaries and intermediate operations, we extend these results to a wide class of noise models, including stochastic Pauli, global depolarizing, and thermal noise. The case of thermal noise particularly provides an intriguing physical interpretation: the sampling cost $N$ required to mitigate thermal noise after time $t$ is characterized by the loss of free energy $N=\Omega(1/[F(\rho_{t})-F_{\rm eq}])$ where $\rho_{t}$ is the state at time $t$ and $F_{\rm eq}$ is the equilibrium free energy. This in turn shows that the necessary sampling cost grows as $N=\Omega(e^{\alpha_{\rm ent}t})$ where $\alpha_{\rm ent}$ is a constant characterized by the minimum entropy production rate. We provide details on these extensions in Appendix I.

We remark that Theorem 3 (and related results discussed in the Appendices) extends the previous results showing the exponential resource overhead required for noisy circuits without postprocessing [9, 10, 11]. In Appendix J, we provide further clarifications about the differences between the settings considered in the previous works and ours.

Conclusions — We established sampling lower bounds imposed on the general quantum error-mitigation protocols. Our results formalize the idea that the reduction in the state distinguishability caused by noise and error-mitigation processes leads to the unavoidable computational overhead in quantum error mitigation. We then showed that error-mitigation protocols with certain intermediate operations and an arbitrary trailing process require the number of samples that grows exponentially with the circuit depth to mitigate various types of noise. We presented these bounds with respect to multiple performance quantifiers — accuracy and success probability, as well as the standard deviation and bias — each of which has its own operational relevance.

Our bounds provide fundamental limitations that universally apply to general mitigation protocols, clarifying the underlying principle that regulates error-mitigation performance. As a trade-off, they may not give tight estimates for a given specific error-mitigation strategy, analogously to many other converse bounds established in other fields that typically give loose bounds for most specific protocols. A thorough study to identify in what setting our bounds can give good estimates will make an interesting future research direction.

Note added. — During the completion of our manuscript, we became aware of an independent work by Tsubouchi et al. [81] that obtained a result related to our Theorem S.2 in Appendix G, in which they showed an alternative exponential sample lower bound applicable to error-mitigation protocols that achieve zero bias using quantum estimation theory.

Universal Sampling Lower Bounds for Quantum Error Mitigation
Supplemental Material