# Fundamental limits of quantum error mitigation

Ryuji Takagi<EMAIL_ADDRESS>Nanyang Quantum Hub, School of Physical
and Mathematical Sciences, Nanyang Technological University, 637371, Singapore
Suguru Endo<EMAIL_ADDRESS>NTT Computer and Data Science
Laboratories, NTT Corporation, Musashino, 180-8585, Tokyo, Japan  Shintaro
Minagawa<EMAIL_ADDRESS>Graduate School of Informatics, Nagoya
University, Chikusa-ku, 464-8601, Nagoya, Japan  Mile Gu
<EMAIL_ADDRESS>Nanyang Quantum Hub, School of Physical and
Mathematical Sciences, Nanyang Technological University, 637371, Singapore
Centre for Quantum Technologies, National University of Singapore, 3 Science
Drive 2, 117543, Singapore

###### Abstract

The inevitable accumulation of errors in near-future quantum devices
represents a key obstacle in delivering practical quantum advantages. Yet,
such quantum devices are often unable to perform adaptive quantum operations,
disallowing quantum error correction. These constraints motivated the
development of various quantum error-mitigation methods, each presenting a
technique to improve the accuracy of our computation by repeated sampling of
various pre-configured circuits. What are the performance limits imposed on
such protocols? Here we derive fundamental bounds concerning how such
algorithms can reduce the computation error as a function of their extra
sampling overhead. We use it to show that (1) the sampling overhead that
ensures a certain computational accuracy in mitigating local depolarizing
noise for layered circuits — such as the ones used for variational quantum
algorithms — 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 a single-qubit
dephasing noise. Our results provide a means to identify when a given quantum
error-mitigation strategy is optimal and when there is potential room for
improvement.

##  I Introduction

Recent advances in quantum technologies have resulted in the availability of
noisy intermediate-scale quantum (NISQ) devices, promising advantages of
quantum information processing by control of tens to hundreds of qubits [1,
2]. However, inevitable noise remains a critical roadblock for their practical
use; every gate has a chance of error, and their continuing accumulation will
eventually destroy any potential quantum advantage.

Figure 1: Quantum error mitigation. (A) A major goal of many near-term
algorithms is to estimate the expectation value of some observable $A$, when
acting on the output $\psi$ of some idealized computation $U$ applied to some
input $\psi_{\rm in}$. (B) However, noise prevents the exact synthesis of
$\psi$. Quantum error-mitigation protocols attempt to estimate the true
expectation value $\langle A\rangle=\operatorname{Tr}(A\psi)$ without using
the adaptive quantum operations necessary in general error correction. This is
done by (1) using available NISQ devices to synthesize $N$ distorted quantum
states $\\{\mathcal{E}_{n}(\psi)\\}_{n=1}^{N}$ and (2) acting some physical
process $\mathcal{P}$ on these distorted states to produce a random variable
$E_{A}$ that approximates $A$. This procedure can then be repeated over $M$
rounds to draw $M$ samples of $E_{A}$, whose mean is used to estimate $\langle
A\rangle$. (C) We can characterize the efficacy of such protocol by (1) its
spread $\Delta e_{A}$, the difference between maximum and minimum possible of
$E_{A}$ and (2) the bias $b_{A}(\psi)=\left\langle E_{A}\right\rangle-\langle
A\rangle$. Here we derive ultimate bounds on $\Delta e_{A}$ for each given
bias that no such error-mitigation protocol can exceed, as well as tighter
bounds when $\mathcal{P}$ is restricted only to coherent interactions over $Q$
noisy devices at a time. This then tells us how many times $\mathcal{P}$ must
be executed to estimate $\langle A\rangle$ within some desired accuracy and
failure probability.

NISQ devices often lack the capability to adaptively execute different quantum
operations depending on measurement outcomes during a computation — an
essential component necessary for general quantum error correction [3, 4].
This technological hurdle has motivated a heated search for alternatives that
avoid adaptive quantum operations, resulting in a diverse collection of
techniques often referred to as _error-mitigation algorithms_. Notable
examples include zero-error noise extrapolation [5, 6, 7, 8, 9, 10],
probabilistic error cancellation [11, 12, 5, 13, 14, 15], and virtual
distillation [16, 17, 18, 19, 20, 21]. Common among all of them is their
greatly reduced technological requirements. Instead of measuring error
syndromes and making adaptive quantum corrections, error-mitigation algorithms
suppress errors by sampling available NISQ devices many times and classically
post-processing these measurement outcomes. While such techniques do not
promise continued scalability, they provide crucial NISQ compatible methods
for suppressing errors that are compatible with other NISQ algorithms (e.g.,
variational algorithms for estimating the ground state energy in quantum
chemistry [22, 23, 24, 25]).

The performance of these techniques is typically analyzed on a case-by-case
basis. While this is often sufficient for understanding the value of the
methodology in the context of a specific application, it leaves open more
fundamental questions. Are these approaches near-optimal, or could there exist
a more effective method of error mitigation yet undiscovered? What are the
ultimate limitations of all such non-adaptive strategies?

Here, we initiate a research program toward answering these questions. We
present a framework to formally define error mitigation as strategies that
require no adaptive quantum operations (see Fig. 1), and introduce universal
quantifiers for their performance. We use these to derive fundamental lower
bounds for the maximum estimator spread — the difference between the maximum
and minimum values of an estimator for the physical observable of interest.
This in turn tells us how many extra samples of a NISQ device guarantees that
the computation outputs are within a desired accuracy threshold. Our bounds
are represented in terms of the reduction in the distinguishability of quantum
states due to the noise effect, establishing the connection between the
information-theoretic measures of state distinguishability and the operational
cost of error mitigation.

We illustrate two immediate consequences. The first is in the context of
mitigating local depolarizing noise in variational quantum circuits [22, 26].
We show that the maximum estimator spread grows exponentially with circuit
depth for the general error-mitigation protocol, illustrating that the well-
known exponential growing estimation error in several existing error-
mitigation techniques [5, 27] is an unavoidable consequence of avoiding active
error-correction methods. Our second study shows that probabilistic error
cancellation — a prominent method of error mitigation — minimizes the maximum
estimator spread among a general class of methods to mitigate single-qubit
dephasing noise. These results showcase how our bounds can reveal when
existing error-mitigation methods are already near-optimal among other
potential error-mitigation strategies, including the ones yet to be
discovered.

##  II Results

Framework — Our framework begins by introducing a formal definition of error
mitigation. Consider an ideal computation described by (1) application of some
circuit $U$ to some input $\psi_{\rm in}$ (2) measurement of the output state
$\psi$ in some arbitrary observable $A$ (See Fig.1A). In realistic situations,
however, there is noise, such that we have only access to NISQ devices capable
of preparing some certain distorted states $\mathcal{E}(\psi)$. The aim is
then to retrieve desired output data specified by $\langle
A\rangle=\operatorname{Tr}(A\psi)$. Here, assume $-\mathbb{I}/2\leq
A\leq\mathbb{I}/2$ without loss of generality. This is because any observable
$O$ can be shifted and rescaled to some $A$ satisfying this condition, from
which full information of $O$ can be recovered 111For instance, if we are
interested in a non-identity Pauli operator $P$, which has eigenvalues $\pm
1$, we instead consider an observable $A=P/2$. Note also that while $\psi$ is
pure in many practically relevant instances, our analysis applies equally when
$\psi$ is mixed.

We consider NISQ devices with no capacity to execute adaptive quantum
operations. That is, they cannot enact different quantum operations
conditioned on a measurement outcome. We then refer to an algorithm aimed to
estimate $\langle A\rangle$ under such constrained devices an _error-
mitigation strategy_. Each error-mitigation strategy involves sampling NISQ
devices configured in $N$ settings for some integer $N$. Denote the states
generated by these configurations by
$\mathcal{E}_{1}(\psi),\dots,\mathcal{E}_{N}(\psi)$, with effective noise
channels $\\{\mathcal{E}_{i}\\}_{i=1}^{N}$. The effective noise channel is a
map that connects an ideal state to a distorted state and may be different
from the actual noise channel that happens in the NISQ device. Nevertheless,
one can always find such an effective noise channel given the descriptions of
the actual noise channels and the idealized circuit $U$. The strategy then
further describes some physical process $\mathcal{P}$ — which is independent
of either the input $\psi_{\rm in}$ or the ideal output $\psi$ — that takes
these distorted states as input and outputs some classical estimate random
variable $E_{A}$ of $\operatorname{Tr}(A\psi)$ (See Fig.1B). The aim is to
generate $E_{A}$ such that its expected value $\langle E_{A}\rangle$ is close
to $\operatorname{Tr}(A\psi)$. Each _round_ of the protocol involves
generating a sample of $E_{A}$. $M$ rounds of this procedure then enable us to
generate $M$ samples of $E_{A}$, whose mean is used to estimate
$\operatorname{Tr}(A\psi)$.

Figure 2: Schematic of a $(Q,K)$-error mitigation protocol. A $(Q,K)$-error
mitigation protocol is motivated when practical considerations limit the
maximum number of distorted states that our mitigation process $\mathcal{P}$
can coherently interact to $Q$. A general approach then divides these into
$K=\lceil N/Q\rceil$ groups of size $Q$. To estimate $\langle A\rangle$ of
some ideal output state $\psi$, each round of $(Q,K)$-mitigation involves
first using available NISQ devices to generate $Q$ copies of each distorted
states $\mathcal{E}_{q}^{(k)}(\psi)$, for each of $k=1,\ldots K$. These
distorted states are then grouped together as inputs into $K$ experiments,
where each group consists of a single copy of each
$\mathcal{E}_{q}^{(k)}(\psi)$. The $k^{\mathrm{th}}$ experiment then involves
applying some general (possibly entangling) POVM $\\{M_{i^{(k)}}^{(k)}\\}$ on
the $k^{\mathrm{th}}$ grouping, resulting in measurement outcome $i^{(k)}$.
Classical computing is then deployed to produce an estimate
$e_{A}(i^{(1)},\dots,i^{(K)})$ whose average after $M$ rounds of the above
process is used to estimate $\mathrm{Tr}(A\psi)$. Note that there can be
additional quantum operations before the POVM measurements
$\\{M_{i^{(k)}}^{(k)}\\}$, but these can be absorbed into the description of
the POVMs without loss of generality.

Each error-mitigation strategy can then be entirely described by its choice of
$\mathcal{P}$ and $\\{\mathcal{E}_{i}\\}_{i=1}^{N}$. Our performance bounds
pertain to all possible choices. However, we can often make these bounds
tighter as further practical limitations often constrain how many distorted
states $\mathcal{P}$ can coherently interact. Error mitigation protocols under
such constraints typically select $N=KQ$ to a multiple of $Q$, such that the
$N$ distorted states are divided into $K$ clusters, each containing $Q$
distorted states. We label these as
$\\{\mathcal{E}_{q}^{(k)}(\psi)\\}_{q=1,k=1}^{Q,K}$ for convenience.
$\mathcal{P}$ is then constrained to represent (1) local measurement
procedures $M^{(k)}$ that can coherently interact distorted states within the
$k^{\mathrm{th}}$ cluster (i.e.,
$\\{\mathcal{E}_{q}^{(k)}(\psi)\\}_{q=1}^{Q}$) to produce some classical
interim outputs $i^{(k)}$ and (2) classical post-processing $e_{A}$ that
transform the interim outputs $\\{i^{(k)}\\}_{k=1}^{K}$ into a sample of
$E_{A}$.

We name such a protocol as _$(Q,K)$ -error mitigation_, and refer to the
generation of each $i^{(k)}$ as _an experiment_. Each round of a $(Q,K)$-error
mitigation protocol thus contains $K$ experiments on systems of up to $Q$
distorted states 222In principle, one can consider a different number of
inputs $Q_{k}$ for each $k^{\mathrm{th}}$ experiment, which may find a better
fit to a recent proposal [34]. Such scenarios are still encompassed in the
present framework by setting $Q=\max_{k}Q_{k}$, but it may result in a tighter
bound in Theorem 1.. We also summarize the above procedure in Fig. 2 and give
a formal mathematical definition in Methods. Fig. 3 and accompanying captions
discuss how several prominent error-mitigation methods fit into this
framework.

Several comments on our error-mitigation framework are in order. We first note
that, for a given set of noisy circuits that result in effective noise
channels $\\{\mathcal{E}_{i}\\}_{i=1}^{N}$, our framework assumes to apply an
additional process $\mathcal{P}$ _after_ the noisy circuits and does not
include processes within the initial noisy circuits. Our framework thus
excludes error correction, which employs complicated adaptive processes
integrated in noisy circuits. This allows our framework to differentiate error
mitigation from error correction and makes it useful to investigate the
limitations imposed particularly on the former. One might think that this
would overly restrict the scope of error mitigation, which could also use some
processes in noisy circuits. This can be avoided by considering that such
processes are already integrated into the description of effective noise
channels $\\{\mathcal{E}_{i}\\}_{i=1}^{N}$. In other words, the effective
noise channels can be considered as a set of processes accessible to a given
near-term device, and the error mitigation process $\mathcal{P}$ is an
additional process that follows them. This is manifested in the $R$-th order
noise extrapolation in Fig. 3 B, in which $R$ different noise levels realized
on a near-term device are represented by the set
$\\{\mathcal{E}_{i}\\}_{i=1}^{R}$ of effective noise channels.

We also remark that our framework leaves the freedom of how to choose the
round number $M$ and the sample number $N=KQ$ per round for a given shot
budget; if the total shot budget is $T$, one is free to choose any $N$ and $M$
such that $T=NM$. As we describe shortly, our results in Theorem 1 and
Corollary 2 are concerned with the number of rounds $M$, and they apply to any
choice of shot allocation. However, our results become most informative by
choosing as large $M$ (equivalently, as small $N$) as possible. The strategies
in Fig. 3 admit small $N$’s that do not scale with the total shot budget,
representing examples for which our results give fruitful insights into their
round number $M$. On the other hand, some strategies that employ highly
nonlinear computation on the measurement outcomes (e.g., exponential noise
extrapolation [13], subspace expansion [30]) require a large $N$, in which
case our results on the round number $M$ can have a large gap from the actual
sampling cost.

Our framework also allows one to assume some _pre-knowledge_ prior to the
error-mitigation process. For instance, this includes the information about
the underlying noise or some pre-computation that error-mitigation process can
use in its strategy. The results in Theorem 1 and Corollary 2 then give
information about the round number $M$ given such pre-knowledge. Since the
process of obtaining the pre-knowledge itself may be considered as a part of
error-mitigation process, there are many possible divisions between the pre-
computation and the error-mitigation process. Our results apply to any choice
of pre-knowledge, and this can be flexibly chosen depending on one’s interest.
For instance, $R$-copy virtual distillation can be considered as a
$(R,1)$-error mitigation (that is, $N=R$) as in Fig. 3 C under the pre-
knowledge of the largest eigenvalue of the noisy state, which is one of the
settings discussed in the original proposal [16] (see also Methods). This pre-
knowledge allows for a small choice of $N$, making the estimation of the round
number $M$ by our method insightful. Another example includes the Clifford
Data Regression [31], which can employ a linear regression based on a pattern
learned from a training set. By considering the first learning step as the
pre-computation, our results provide a meaningful bound for the sampling cost
in the latter stage in which the output from the circuit of interest is
compared to the model estimated from the training set.

Up to the flexibility described above, our framework encompasses a broad class
of error-mitigation strategies proposed so far [5, 6, 13, 30, 32, 16, 17, 33,
34, 35, 31].

Figure 3: Error-mitigation protocols. Our framework encompasses all commonly
used error-mitigation protocols, a sample of which we outline here. (A)
Probabilistic error cancellation [5] assumes we can only act a single coherent
state each round, where it seeks to undo a given noise map $\mathcal{E}$ by
applying a suitable stochastic operation $\mathcal{B}$. Thus it corresponds to
the case of $Q=K=1$. (B) $R^{\mathrm{th}}$ order noise extrapolation assumes
[5, 6] the capacity to synthesize $R+1$ NISQ devices whose outputs represent
distortions of $\psi$ at various noise strengths. It then uses individual
measurements of an observable $A$ on these distorted states to estimate the
observable expectation value on the zero-noise limit. Thus it is an example
where $Q=1$ and $K=R+1$. (C) Meanwhile, $R$-copy virtual distillation [16, 17]
involves running an available NISQ device $R$ times to synthesize $R$ copies
of a distorted state $\mathcal{E}(\psi)$. Coherent interaction $\mathcal{D}$
over these copies followed by a suitable measurement $M_{A}$ then enables
improved estimation of $\langle A\rangle$. Thus it is an example where $K=1$
and $Q=R$. In the main text and Methods, we provide a detailed account of each
protocol and how it fits within our framework.

Quantifying performance — The performance of an error-mitigation protocol is
determined by how well the random variable $E_{A}$ governing each estimate
aligns with $\operatorname{Tr}(A\psi)$. We can characterize this by (1) its
bias, representing how close $\langle E_{A}\rangle$ is to the ideal
expectation value $\operatorname{Tr}(A\psi)$ and (2) its spread, representing
the amount of intrinsic randomness within $E_{A}$.

A protocol’s bias quantifies the absolute minimum error with which it can
estimate $\mathrm{Tr}(A\psi)$, given no restrictions on how many rounds it can
run (i.e., samples of $E_{A}$ it can draw). Mathematically, this is
represented by the difference $b_{A}(\psi)=\langle
E_{A}\rangle-\operatorname{Tr}(A\psi)$. Since the error-mitigation strategy
should work for arbitrary state $\psi$ and observables $A$, we can introduce
the _maximum bias_

$\displaystyle b_{\max}\coloneqq\max_{-\mathbb{I}/2\leq
A\leq\mathbb{I}/2}\max_{\psi}\,[\langle
E_{A}\rangle-\operatorname{Tr}(A\psi)]$ (1)

to bound the bias of an error-mitigation protocol in estimating expectation
values over all output states and observables of interest. Hereafter, we will
also assume $b_{\max}\leq 1/2$, as this condition must be satisfied for any
meaningful error-mitigation protocol. This is because a maximum bias of $1/2$
can always be achieved by the trivial ‘error-mitigation’ protocol outputs
$e_{A}=0$ regardless of $\psi$ or $A$.

Of course, having $b_{\max}=0$ still does not guarantee an effective error-
mitigation protocol. Each sample of $E_{A}$ will also deviate from
$\operatorname{Tr}(A\psi)$ due to intrinsic random error. The greater this
randomness, the more samples we need from $E_{A}$ to ensure that the mean of
our samples is a reliable estimate of its true expectation value $\langle
E_{A}\rangle$. The relation is formalized by Hoeffding’s inequality [36].
Namely, suppose $\\{x_{i}\\}_{i=1}^{M}$ are $M$ samples of a random variable
$X$ with $x_{i}\in[a,b]$, the number $M$ of samples that ensures an estimation
error $|\left\langle X\right\rangle-\sum_{i}x_{i}/M|<\delta$ with probability
$1-\varepsilon$ is given by
$\frac{2|a-b|^{2}}{\delta^{2}}\log(2/\varepsilon)\propto|a-b|^{2}$. In our
context, the latter quantity corresponds to the _maximum spread_ in the
outcomes of estimator function $e_{A}$ defined by

$\displaystyle\Delta e_{\max}\coloneqq\max_{-\mathbb{I}/2\leq
A\leq\mathbb{I}/2}\Delta e_{A},$ (2)

where $\Delta e_{A}$ is the difference between the maximum and minimum
possible values that $E_{A}$ can take 333Mathematically, $\Delta
e_{A}=e_{A,\max}-e_{A,\min}$ where $\Delta e_{A,\max}=\max_{i^{(1)}\dots
i^{(K)}}e_{A}(i^{(1)}\dots i^{(K)})$ and $e_{A,\min}=\min_{i^{(1)}\dots
i^{(K)}}e_{A}(i^{(1)}\dots i^{(K)})$.

$\Delta e_{\max}$ thus directly relates to the sampling cost of an error-
mitigation protocol. Given an error-mitigation protocol whose estimates have
maximum spread $\Delta e_{\max}$, it uses sample $E_{A}$ of order
$\Omega(\Delta e_{\max}^{2}\log(1/\varepsilon)/\delta^{2})$ times to ensure
that its estimate of $\langle E_{A}\rangle$ has accuracy $\delta$ and failure
rate $\varepsilon$. Therefore, we may think of $\Delta e_{\max}$ as a measure
of computational cost or feasibility. Its exponential scaling with respect to
the circuit depth, for example, would imply eventual intractability in
mitigating associated errors in a class of non-shallow circuits.

We note that if the variance of $E_{A}$ happens to be small, the actual
sampling cost required to achieve the accuracy $\delta$ and failure rate
$\varepsilon$ can be smaller than the estimate based on the maximum spread. In
this sense, $\Delta e_{\max}$ quantifies the round number $M$ that one would
practically use in the worst-case scenario. However, knowing the variance of
$E_{A}$ beforehand is a formidable task in general, and the worst-case
estimate gives a useful benchmark to assess the feasibility of a given error-
mitigation strategy in such situations.

Fundamental limits — Our main contribution is to establish a universal lower
bound on $\Delta e_{\max}$. Our bound then determines the number of times an
error-mitigation method samples $E_{A}$ (and thus the number of times we
invoke a NISQ device) to estimate $A$ within some tolerable error.

To state the bound formally, we utilize measures of state distinguishability.
Consider the scenario where Alice prepares a quantum state in either $\rho$
and $\sigma$ and challenges Bob to guess which is prepared. The trace distance
$D_{\rm tr}(\rho,\sigma)=\frac{1}{2}\|\rho-\sigma\|_{1}$ (where
$\|\cdot\|_{1}$ is the trace norm) then represents the quantity such that
Bob’s optimal probability of guessing correctly is $\frac{1}{2}(1+D_{\rm
tr}(\rho,\sigma))$. When $\rho$ and $\sigma$ describe states on $K$-partite
systems $S_{1}\otimes\dots\otimes S_{K}$, we can also consider the setting in
which Bob is constrained to local measurements, resulting in the optimal
guessing probability $\frac{1}{2}(1+D_{\rm LM}(\rho,\sigma))$ where $D_{\rm
LM}$ is the local distinguishability measure [38] (see also Methods). In our
setting, we identify each local subsystem $S_{k}$ with a system corresponding
to the $k^{\mathrm{th}}$ experiment in Fig. 2. We are then in a position to
state our main result:

######  Theorem 1.

Consider an arbitrary $(Q,K)$-mitigation protocol with maximum bias
$b_{\max}$. Then, its maximum spread $\Delta e_{\max}$ is lower bounded by

$\displaystyle\Delta e_{\max}$
$\displaystyle\geq\max_{\begin{subarray}{c}\psi,\phi\end{subarray}}\frac{D_{\rm
tr}(\psi,\phi)-2b_{\max}}{D_{\rm
LM}\left(\tilde{\psi}_{Q}^{(K)},\tilde{\phi}_{Q}^{(K)}\right)}$ (3)

where
$\tilde{\psi}_{Q}^{(K)}\coloneqq\otimes_{k=1}^{K}\otimes_{q=1}^{Q}\left[\mathcal{E}_{q}^{(k)}(\psi)\right]$
and
$\tilde{\phi}_{Q}^{(K)}\coloneqq\otimes_{k=1}^{K}\otimes_{q=1}^{Q}\left[\mathcal{E}_{q}^{(k)}(\phi)\right]$
are distorted states corresponding to the $QK$ copies of some ideal outputs
$\psi$ and $\phi$, and $\mathcal{E}_{q}^{(k)}$ is the effective noise channel
for the $q^{\mathrm{th}}$ input in the $k^{{\mathrm{th}}}$ experiment.

Combining this with Hoeffding’s inequality leads to the following bound on the
sampling cost.

######  Corollary 2.

Consider an arbitrary $(Q,K)$-mitigation protocol with maximum bias
$b_{\max}$. Then, an estimation error of $b_{\max}+\delta$ is realized with
probability $1-\varepsilon$ when the number of samples $M$ satisfies

$\displaystyle M$
$\displaystyle\geq\left[\max_{\begin{subarray}{c}\psi,\phi\end{subarray}}\frac{D_{\rm
tr}(\psi,\phi)-2b_{\max}}{D_{\rm
LM}\left(\tilde{\psi}_{Q}^{(K)},\tilde{\phi}_{Q}^{(K)}\right)}\right]^{2}\frac{2\log(2/\varepsilon)}{\delta^{2}}$
(4)

where
$\tilde{\psi}_{Q}^{(K)}\coloneqq\otimes_{k=1}^{K}\otimes_{q=1}^{Q}\left[\mathcal{E}_{q}^{(k)}(\psi)\right]$
and
$\tilde{\phi}_{Q}^{(K)}\coloneqq\otimes_{k=1}^{K}\otimes_{q=1}^{Q}\left[\mathcal{E}_{q}^{(k)}(\phi)\right]$.

Theorem 1 and Corollary 2 offer two qualitative insights. The first is the
potential trade-off between sampling cost and systematic error — we may reduce
the sampling cost by increasing tolerance for bias. The second is a direct
relation between sampling cost and distinguishability — the more a noise
source degrades distinguishability between states, the more costly the error
is to mitigate.

The intuition behind this relation rests on the observation that the error-
mitigation process is a quantum channel. Thus, any error-mitigation procedure
must obey data-processing inequalities for distinguishability. On the other
hand, error mitigation aims to improve our ability to estimate expectation
values of various observables, which would enhance our ability to distinguish
between noisy states. The combination of these observations then implies that
distinguishability places a fundamental constraint on required sampling costs
to mitigate error. For details of the associated proof, see Methods.

We note also that our bound involves the local distinguishability
$D_{\textrm{LM}}(\rho,\sigma)$ rather than the standard trace distance $D_{\rm
tr}(\rho,\sigma)$. This is due to the constraints we placed of $\mathcal{P}$
that limits it to coherently interacting the outputs of a finite number of
NISQ devices — reflecting the hybrid nature of quantum error mitigation
utilizing quantum and classical resources in tandem. Indeed, since $D_{\rm
tr}(\rho,\sigma)\geq D_{\textrm{LM}}(\rho,\sigma)$ (as constraining
measurements to be local cannot ever improve distinguishability), our theorem
also implies

$\displaystyle\Delta e_{\max}$
$\displaystyle\geq\max_{\begin{subarray}{c}\psi,\phi\end{subarray}}\frac{D_{\rm
tr}(\psi,\phi)-2b_{\max}}{D_{\rm
tr}\left(\tilde{\psi}_{Q}^{(K)},\tilde{\phi}_{Q}^{(K)}\right)}$ (5)

as an immediate corollary, giving another lower bound on the sampling cost as
in Corollary 2. This bound represents the ultimate performance limits of all
$(Q,K)$ error-mitigation protocols that coherently operate on $N=QK$ distorted
states each round.

While the bounds derived above in terms of distinguishability have a clear
operational meaning, its evaluation in realistic settings can face two
significant hurdles. (1) It involves evaluating the distinguishability between
two quantum states whose dimensions scale exponentially with $KQ$, making its
evaluation costly for protocols that require many NISQ samples per round. (2)
It requires that we have tomographic knowledge of the effective noise channels
$\mathcal{E}_{q}^{(k)}$.

We can alleviate (1) by using a fidelity bound for the state
distinguishability: $D_{\rm tr}(\rho,\sigma)\leq\sqrt{1-F(\rho,\sigma)}$ for
any pair of states $\rho$ and $\sigma$ [39], where
$F(\rho,\sigma)\coloneqq\left(\operatorname{Tr}\sqrt{\sigma^{1/2}\rho\sigma^{1/2}}\right)^{2}$
is the (squared) fidelity [39]. Applying this to Eq. (5) implies

$\displaystyle\Delta e_{\max}$
$\displaystyle\geq\max_{\begin{subarray}{c}\psi,\phi\end{subarray}}\frac{D_{\rm
tr}(\psi,\phi)-2b_{\max}}{\sqrt{1-\prod_{q=1}^{Q}\prod_{k=1}^{K}F\left(\mathcal{E}_{q}^{(k)}(\psi),\mathcal{E}_{q}^{(k)}(\phi)\right)}}.$
(6)

This form only involves the computation of the trace distance and fidelity of
single-copy states, both of which can be computed by semidefinite programming
[40].

Meanwhile, the need for tomographic knowledge of $\mathcal{E}_{q}^{(k)}$ can
be mitigated by using sub-fidelity [41]

$\displaystyle
E(\rho,\sigma)\coloneqq\operatorname{Tr}(\rho\sigma)+\sqrt{2\left[\left\\{\operatorname{Tr}(\rho\sigma)\right\\}^{2}-\operatorname{Tr}(\rho\sigma\rho\sigma)\right]}.$
(7)

The sub-fidelity bounds $F(\rho,\sigma)$ from below, and thus also lower
bounds the maximum spread:

$\displaystyle\Delta e_{\max}$
$\displaystyle\geq\max_{\begin{subarray}{c}\psi,\phi\end{subarray}}\frac{D_{\rm
tr}(\psi,\phi)-2b_{\max}}{\sqrt{1-\prod_{q=1}^{Q}\prod_{k=1}^{K}E\left(\mathcal{E}_{q}^{(k)}(\psi),\mathcal{E}_{q}^{(k)}(\phi)\right)}}.$
(8)

Sub-fidelity between two unknown states can be measured by a quantum computer
using a circuit of constant depth [42, 43] (see also Methods). This obviates
the need for tomographical data, while its low depth means that the noise in
this process is typically much smaller than the noise in our circuits of
interest. In addition, the maximum in the right-hand side of (8) does not need
to be evaluated exactly; any choice of states $\psi$ and $\phi$ provides a
valid lower bound for the maximum spread. We also remark that, instead of
using the sub-fidelity, one could use an alternative quantity that lower
bounds the fidelity that can be estimated by NISQ devices, e.g., truncated
fidelity [44].

Application: error-mitigating layered circuits — Quantitatively, the above
bounds enable us to determine the ultimate performance limits of error
mitigation given a particular set of imperfect quantum devices specified by
error channels $\\{\mathcal{E}_{q}^{(k)}\\}$. We now illustrate how this
enables the identification of sampling overheads when performing error
mitigation on a common class of NISQ algorithms — layered circuits used
extensively in variational quantum eigensolvers [45]. Variational algorithms
typically assume a quantum circuit consisting of multiple layers of unitary
gates $\\{U_{l}\\}_{l=1}^{L}$ acting on an $n$-qubit system. Indeed, as
designed with NISQ applications in mind, they are a key candidate for
benchmarking of error-mitigation protocols [9, 46, 47].

Figure 4: Noise mitigation in layered circuits. Layered circuits are used
extensively in variational algorithms for NISQ devices. They involve repeated
layers of gates, each consisting of some unitary $U_{l}$. A standard noise
model for such circuits involves the action of local depolarizing noise
$\mathcal{D}_{\epsilon}$ on each qubit during each layer of the circuit. The
$k^{\mathrm{th}}$ experiment in a general $(Q,K)$-protocol involves running
this circuit $Q$ times to produce a distorted state
$\otimes_{q=1}^{Q}\mathcal{E}_{q}^{(k)}(\psi)$ with some noise strength
$\epsilon_{k}$ — which possibly varies over different experiments. The
protocol then measures each $\otimes_{q=1}^{Q}\mathcal{E}_{q}^{(k)}(\psi)$ for
$k=1,\dots,K$ and outputs an estimate $E_{A}$ through classical post-
processing of the measurements results.

In particular, consider a local depolarizing noise [48, 26], in which the
depolarizing channel
$\mathcal{D}_{\epsilon}(\rho)\coloneqq(1-\epsilon)\rho+\epsilon\mathbb{I}/2$
acts on each qubit. A general approach to mitigate this error is to employ an
$(Q,K)$-mitigation protocol for some $Q$ and $K$, in which the
$k^{\mathrm{th}}$ experiment involves depolarizing noise with noise strength
$\epsilon_{k}$ (Fig. 4).

Taking $U=U_{L}\cdots U_{2}\,U_{1}$ in Fig. 2 and applying Theorem 1 to this
setting, we obtain the following bound (See the Appendix for the proof).

######  Theorem 3.

For an arbitrary $(Q,K)$-error mitigation with maximum bias $b_{\max}$ applied
to $n$-qubit circuits with $L$-layer unitaries under local depolarizing noise,
the maximum spread is lower bounded as

$\displaystyle\Delta e_{\max}\geq\frac{1-2b_{\max}}{\sqrt{2\ln
2}\sqrt{nQ}\,K}\left(\frac{1}{1-\epsilon_{\min}}\right)^{L/2},$ (9)

where $\epsilon_{\min}\coloneqq\min_{k}\epsilon_{k}$ is the minimum noise
strength among $K$ experiments.

Theorem 3 suggests that error-mitigation strategies encompassed in our
framework will use exponentially many samples with respect to the circuit
depth $L$. This validates our intuition that information should quickly get
degraded due to the sequential noise effects, incurring exponential overhead
to remove the accumulated noise effect.

We also remark that, although we here focus on the exponential growth of the
maximum spread with respect to the circuit depth $L$ for the sake of
generality, one can expect that the maximum spread grows exponentially with
the total gate number $nQKL$ rather than just the layer number $L$ in many
practical cases.

Application: protocol benchmarking — Theorems 1 and 3 place strategy-
independent bounds on the maximum spread for each $Q$ and $K$ and available
noise channels $\mathcal{E}_{q}^{(k)}$, enabling us to identify the ultimate
potential of error mitigation under various noise settings and operational
constraints. Comparing this limit with that achieved by specific known methods
of error mitigation then provides a valuable benchmark, helping us assess
their optimality and quantify the potential room for improvement. We
illustrate this here by considering probabilistic error cancellation [5],
while we discuss how our framework can be applied to other prominent error-
mitigation protocols in Methods.

Probabilistic error cancellation is an error-mitigation protocol that produces
an estimate of $\operatorname{Tr}(A\psi)$ using a distorted state
$\mathcal{E}(\psi)$ each round (see Fig 3A). It then fulfills the criteria of
being a $(1,1)$-protocol, i.e., $Q=K=1$. Here, we assume that the description
of the noise channels is given as pre-knowledge, in which case the estimator
becomes unbiased, i.e., $b_{\max}=0$. Probabilistic error cancellation
operates by identifying a complete basis of processes
$\\{\mathcal{B}_{j}\\}_{j}$ such that
$\mathcal{E}^{-1}=\sum_{j}c_{j}\mathcal{B}_{j}$ for some set of real (but
possibly negative) numbers $\\{c_{j}\\}_{j}$. Setting
$\gamma\coloneqq\sum_{j}|c_{j}|$, the protocol then (1) applies
$\mathcal{B}_{j}$ to the noisy state $\mathcal{E}(\psi)$ with probability
$p_{j}=|c_{j}|/\gamma$, (2) measures $A$ to get outcome $a_{j}$, and (3)
multiplies each outcome by $\gamma\,\mathrm{sgn}(c_{j})$ and takes the
average.

In the context of our framework, we can introduce a quantum operation
$\mathcal{B}$ that represents first initializing a classical register to a
state $j$ with probability $p_{j}$ and applying $\mathcal{B}_{j}$ to
$\mathcal{E}(\psi)$ conditioned on $j$. Meanwhile, $M_{A}$ represents an
$A$-measurement of the resulting quantum system combined with a measurement of
the register, resulting in the outcome pair $(a_{j},j)$. Taking $e_{A}^{\rm
PEC}\left((a_{j},j)\right)=\gamma\operatorname{sgn}(c_{j})a_{j}$, we see that
the maximum spread of this estimator is given by

$\displaystyle\Delta e_{\max}^{\rm PEC}=\gamma,$ (10)

a well-studied quantity that is already associated with the sampling overhead
of probabilistic error cancellation [5].

The optimal sampling cost $\gamma_{\rm opt}$ is then achieved by minimizing
such $\gamma$ over all feasible $\\{\mathcal{B}_{j}\\}_{j}$ [49]. Once
computed for a specific noise channel $\mathcal{E}$, we can compare it to the
lower bounds in Theorem 1 to determine if there is possible room for
improvement.

In the case of qubit dephasing
$\mathcal{Z}_{\epsilon}(\rho)\coloneqq(1-\epsilon)\rho+\epsilon Z\rho Z$, the
optimal cost was obtained as [49, 50, 51]

$\displaystyle\gamma_{\rm opt}=\Delta e_{\max}^{\rm
PEC}=\frac{1}{1-2\epsilon}.$ (11)

This can be compared to the bound for $\Delta e_{\rm max}$ from Theorem 1 that
applies to every mitigation protocol with $Q=K=1$. Note that, since $K=1$,
$D_{\rm LM}=D_{\operatorname{tr}}$. We then get 444The lower bound can be
obtained by considering a specific choice of $\psi$ and $\phi$, e.g.,
$\ket{\psi}=\ket{+}$ and $\ket{\phi}=\ket{-}$ where
$\ket{\pm}\coloneqq(\ket{0}\pm\ket{1})/\sqrt{2}$.

$\displaystyle\max_{\psi,\phi}\frac{D_{\operatorname{tr}}(\psi,\phi)}{D_{\operatorname{tr}}(\mathcal{Z}_{\epsilon}(\psi),\mathcal{Z}_{\epsilon}(\phi))}$
$\displaystyle\geq\frac{1}{1-2\epsilon}.$ (12)

Remarkably, the two quantities — the maximum spread for the probabilistic
error cancellation and the lower bound for arbitrary unbiased mitigation
strategies with $Q=K=1$ — exactly coincide. This shows that the probabilistic
error cancellation achieves the ultimate performance limit of unbiased
$(1,1)$-protocols for correcting qubit-dephasing noise.

We can also consider the $d$-dimensional depolarizing noise
$\mathcal{D}_{\epsilon}^{d}(\rho)=(1-\epsilon)\rho+\epsilon\mathbb{I}/d$. The
bound from Theorem 1 for this noise is obtained as

$\displaystyle\max_{\psi,\phi}\frac{D_{\operatorname{tr}}(\psi,\phi)}{D_{\operatorname{tr}}(\mathcal{D}_{\epsilon}^{d}(\psi),\mathcal{D}_{\epsilon}^{d}(\phi))}=\frac{1}{1-\epsilon},$
(13)

which is slightly lower than $\Delta e_{\max}^{\rm
PEC}=\frac{1+(1-2/d^{2})\epsilon}{1-\epsilon}$ [49, 50, 51], with difference
being $O(\epsilon)$. This suggests that probabilistic error cancellation is
nearly optimal for this noise model, while still leaving the possibility for a
better protocol to exist.

##  III Discussions

We introduced a general framework for quantum error mitigation that considers
estimating the expected measurement outcomes of ideal quantum circuits by
performing measurements on noisy circuits. We employed this framework to
derive a universal performance analysis that estimates how many extra
repetitions an error-mitigation protocol uses to ensure estimates to fall
within a given accuracy range with some guaranteed probability of success. Our
bounds have immediate consequences. For layered circuits under the local
depolarizing noise, they imply that the sampling overhead for error mitigation
to ensure a certain accuracy scales exponentially with respect to the circuit
depth. Meanwhile, we illustrated that probabilistic error cancellation can
saturate such bounds for a single-qubit dephasing noise, implying its provable
optimality. Despite its simplicity, the successful application of our
framework to this noise model suggests the usefulness of our bounds in
providing a means of identifying when current state-of-the-art error
mitigation methods have the greatest room for improvement, motivating further
investigation on more complex noise models.

We note that our performance bounds have focused on the scaling of $M$,
representing how many rounds an error-mitigation protocol should be run to get
a reliable estimate of some observable $\langle A\rangle$. Although this
analysis is sufficient for many present methods of error mitigation, it is
possible to also improve estimates of $\langle A\rangle$ by scaling the number
of distorted outputs we process in a single round (e.g., extrapolation [13]
and subspace expansion [30]). While our framework in Fig. 1 encompasses such
methodologies — and as such all bounds on estimation error apply — full
understanding of the performance of such protocols would involve further
investigation on how estimation error scales with respect to $N$ or $K$. This
then presents a natural direction for future research.

Our results also offer potential insights into several related fields. Non-
Markovian dynamics have shown promise in decreasing sampling costs in error
mitigation [53]. Since non-Markovianity is known to be deeply related to the
trace distance [54], our newly established relations between trace distance
and quantum error mitigation hint at promising relations between the two
fields. The second direction is to relate our general framework of quantum
error mitigation to the established theory of quantum error correction.
Quantum error correction concerns algorithms that prevent degrading the trace
distance between suitably encoded logical states, while our results indicate
that less reduction in trace distance can enable smaller error mitigation
costs. Thus, our work provides a toolkit for identifying fundamental bounds in
the transition from error mitigation to error correction as we proceed from
NISQ devices towards scalable quantum computing. This then complements
presently active research in error suppression that combines the two
techniques [55, 56, 57, 58]. Beyond error suppression, quantum protocols in
many diverse settings also share the structure of classical post-processing of
quantum measurements — from quantum metrology and illumination to hypothesis
testing and stochastic analysis [59, 60, 61, 62, 63]. Our framework — suitably
extended — could thus identify new performance bounds in each of these
settings.

Note added.—During the completion of our manuscript, we became aware of an
independent work by Wang et al. [64], which showed a result related to our
Theorem 3 on the exponential scaling of resource overhead.

## Methods

Formal definition of $(Q,K)$-error mitigation — Here, we give a formal
definition of $(Q,K)$-error mitigation as a quantum operation. Since POVM
measurements in different experiments are independent of each other, the whole
measurement process can be represented as a tensor product of each POVM. Then,
the classical post-processing following the measurement is a classical-
classical channel such that the expected value of the output will serve as an
estimate of the desired expectation value. We can then formalize an error-
mitigation process as a concatenation of these two maps.

######  Definition 4 ($(Q,K)$-error mitigation).

For an arbitrary observable $A$ satisfying $-\mathbb{I}/2\leq
A\leq\mathbb{I}/2$, a $(Q,K)$-mitigation protocol — involving $Q$ inputs and
$K$ experiments — is a concatenation of quantum-classical channel
$\Lambda_{A}$ and classical-classical channel $\hat{e}_{A}$ as
$\hat{e}_{A}\circ\Lambda_{A}$. Here, $\Lambda_{A}$ has a form

$\displaystyle\Lambda_{A}(\cdot)$ $\displaystyle=\sum_{\bf
i}\operatorname{Tr}(\cdot\,M_{i^{(1)}}^{(1)}\otimes\dots\otimes
M_{i^{(K)}}^{(K)})\,|{\bf i}\rangle\\!\langle{\bf i}|$ (14)

where $\\{M_{i^{(k)}}^{(k)}\\}$ is the POVM for the $k^{\mathrm{th}}$
experiment acting on $Q$ copies of $n$-qubit noisy states, and ${\bf
i}\coloneqq i^{(1)}\dots i^{(K)}$ denotes a collection of measurement outcomes
with $\ket{\bf i}=\ket{i^{(1)}\dots i^{(K)}}$ being a classical state acting
on $K$ subsystems. The channel $\hat{e}_{A}$ implements a $K$-input classical
function $e_{A}$ such that

$\displaystyle\sum_{\bf i}p_{\bf i}e_{A}({\bf
i})=\operatorname{Tr}(A\psi)+b_{A}(\psi)$ (15)

for some function $b_{A}(\psi)$ called bias, and

$\displaystyle p_{\bf
i}\coloneqq\prod_{k=1}^{K}\operatorname{Tr}[\mathcal{E}_{1}^{(k)}(\psi)\otimes\cdots\otimes\mathcal{E}_{Q}^{(k)}(\psi)\,M_{i^{(k)}}^{(k)}]$
(16)

is the probability of getting outcomes ${\bf i}=i^{(1)}\dots i^{(K)}$ for the
input noisy states $\\{\mathcal{E}_{q}^{(k)}(\psi)\\}_{q=1,k=1}^{Q,K}$.

We also summarize the general error-mitigation procedure as an algorithm in
Table 1.

Algorithm $(Q,K)$-error mitigation

1:Distorted states $\\{\mathcal{E}_{q}^{(k)}(\psi)\\}_{q=1,k=1}^{Q,K}$

2:Estimate of $\operatorname{Tr}(A\psi)$

3:for $m=1~{}\text{{to}}~{}M$ do

4: for $k=1~{}\text{{to}}~{}K$ do

5: Input $\mathcal{E}^{(k)}_{1}(\psi),\dots,\mathcal{E}^{(k)}_{Q}(\psi)$ into
a quantum circuit for error mitigation.

6: Perform a POVM measurement $\\{M^{(k)}_{i^{(k)}}\\}$ for the output state
and get an outcome $i^{(k)}$.

7: end for

8: Using the series of outputs $i^{(1)},\dots,i^{(K)}$ as an input, apply a
classical post-processing to obtain an estimate $e_{A,m}\coloneqq
e_{A}(i^{(1)},\dots,i^{(K)})$.

9:end for

10:return $\frac{1}{M}\sum_{m=1}^{M}e_{A,m}$.

Table 1: General procedure of $(Q,K)$-error mitigation.

Proof of Theorem 1 — The intuition behind Theorem 1 lies in the intimate
relation between the effect of error mitigation and distinguishability of
quantum states. Recall that the goal of quantum error mitigation is to
estimate the expectation value of an arbitrary observable $A$ for an arbitrary
ideal state $\psi$ only using the noisy state $\mathcal{E}(\psi)$. Although
$\operatorname{Tr}(A\mathcal{E}(\psi))$ can deviate from
$\operatorname{Tr}(A\psi)$, error mitigation correctly allows us to estimate
$\operatorname{Tr}(A\psi)$, which appears to have eliminated noise effects.
Since each error-mitigation strategy should also work for another state
$\phi$, it should be able to remove the noise and estimate
$\operatorname{Tr}(A\phi)$ out of $\operatorname{Tr}(A\mathcal{E}(\phi))$.
Does this “removal” of noise imply that error mitigation can help distinguish
$\mathcal{E}(\psi)$ and $\mathcal{E}(\phi)$?

The subtlety of this question can be seen by looking at how quantum error
mitigation works. The estimation of $\operatorname{Tr}(A\mathcal{E}(\psi))$
without error mitigation is carried out by making a measurement with respect
to the eigenbasis of $A=\sum_{a}a|{a}\rangle\\!\langle{a}|$, which produces a
probability distribution $p(a|\mathcal{E}(\psi),A)$ over possible outcomes
$\\{a\\}$. Because of the noise, the expectation value of this distribution is
shifted from $\operatorname{Tr}(A\psi)$. Similarly, the same measurement for a
state $\mathcal{E}(\phi)$ produces a probability distribution
$p(a|\mathcal{E}(\phi),A)$, whose expectation value may also be shifted from
$\operatorname{Tr}(A\phi)$. Error-mitigation protocol applies additional
operations, measurements and classical post-processing to produce other
probability distributions $p_{\rm EM}(a|\mathcal{E}(\psi),A)$ and $p_{\rm
EM}(a|\mathcal{E}(\phi),A)$ whose expectation values get closer to the
original ones. As a result, although the expectation values of the two error-
mitigated distributions get separated from each other, they also get broader,
which may increase the overlap between the two distributions, possibly making
it even harder to distinguish two distributions. (See Fig. 5.)

One can see that this intuition that error mitigation does not increase the
distinguishability is indeed right by looking at the whole error-mitigation
process as a quantum channel. Then, the data-processing inequality implies
that the distinguishability between any two states should not be increased by
the application of quantum channels. This motivates us to rather use this
observation as a basis to put a lower bound for the necessary overhead.

$\mathrm{Tr}(A\mathcal{E}(\psi))$$\mathrm{Tr}(A\mathcal{E}(\phi))$$\mathrm{Tr}(A\psi)$$\mathrm{Tr}(A\phi)$$\mathrm{Tr}(A\psi)$$\mathrm{Tr}(A\phi)$
Figure 5: The top schematic illustrates the probability distribution of an
observable $A$ for two noisy states $\mathcal{E}(\psi)$ and
$\mathcal{E}(\phi)$. The expectation values are shifted from the true values
due to the noise effects. As in the bottom schematic, error mitigation
converts them to other distributions whose expectation values are closer to
the true values than the initial noisy distributions are. However, the
converted distributions get broader, and the overlap between two distributions
increases in general.

Let us recall that the trace distance admits the following form

$\displaystyle D_{\rm tr}(\rho,\sigma)$
$\displaystyle=\frac{1}{2}\|\rho-\sigma\|_{1}$ (17) $\displaystyle=\max_{0\leq
M\leq\mathbb{I}}\operatorname{Tr}\left[M(\rho-\sigma)\right],$

and similarly the local distinguishablity measure can be written as [38]

$\displaystyle D_{\textrm{LM}}(\rho,\sigma)$
$\displaystyle=\max_{\\{M_{i}\\}\in\textrm{LM}}\frac{1}{2}\|\mathcal{M}(\rho)-\mathcal{M}(\sigma)\|_{1}$
(18)
$\displaystyle=\max_{\\{M,\mathbb{I}-M\\}\in\textrm{LM}_{2}}\operatorname{Tr}[M(\rho-\sigma)]$

where $\mathrm{LM}$ is the set of POVMs that take the form
$M_{i^{(1)}}^{(1)}\otimes\dots\otimes M_{i^{(K)}}^{(K)}$, where
$M_{i^{(k)}}^{(k)}$ represents some POVM local to system $S_{k}$, and
$\textrm{LM}_{2}$ is the set of two-outcome measurements realized by local
measurements together with classical post-processing. The second forms for the
above measures particularly tell that they quantify how well two states can be
distinguished by accessible quantum measurements. By definition, it is clear
that

$\displaystyle D_{\operatorname{tr}}(\rho,\sigma)\geq D_{\rm LM}(\rho,\sigma)$
(19)

for all state $\rho$ and $\sigma$, and the inequality often becomes strict
[65, 66].

The local distinguishability measure satisfies the data-processing inequality
under all local measurement channels. Namely, for all states $\rho$ and
$\sigma$ defined on a composite system $\otimes_{k=1}^{K}S_{k}$, and for an
arbitrary quantum-classical channel
$\Lambda(\cdot)=\sum_{i}\operatorname{Tr}\left(\,\cdot\,M_{i^{(1)}}^{(1)}\otimes\cdots\otimes
M_{i^{(K)}}^{(K)}\right)|{i^{(1)}\dots i^{(K)}}\rangle\\!\langle{i^{(1)}\dots
i^{(K)}}|$,

$\displaystyle D_{\textrm{LM}}(\Lambda(\rho),\Lambda(\sigma))$
$\displaystyle=\max_{\mathcal{M}\in{\rm
LM}}\frac{1}{2}\|\mathcal{M}\circ\Lambda(\rho)-\mathcal{M}\circ\Lambda(\sigma)\|_{1}$
(20) $\displaystyle\leq\max_{\mathcal{M}\in{\rm
LM}}\frac{1}{2}\|\mathcal{M}(\rho)-\mathcal{M}(\sigma)\|_{1}$
$\displaystyle=D_{\textrm{LM}}(\rho,\sigma)$

where in the inequality we used that the set of local measurement channels is
closed under concatenation.

Let us define

$\displaystyle\tilde{\psi}_{Q}^{(K)}$
$\displaystyle\coloneqq\otimes_{k=1}^{K}\otimes_{q=1}^{Q}\left[\mathcal{E}_{q}^{(k)}(\psi)\right],$
(21) $\displaystyle\tilde{\phi}_{Q}^{(K)}$
$\displaystyle\coloneqq\otimes_{k=1}^{K}\otimes_{q=1}^{Q}\left[\mathcal{E}_{q}^{(k)}(\phi)\right].$

Since the channel $\Lambda_{A}$ in Definition 4 is a local measurement
channel, we employ (20) to get

$\displaystyle
D_{\textrm{LM}}\left(\tilde{\psi}_{Q}^{(K)},\tilde{\phi}_{Q}^{(K)}\right)$
$\displaystyle\geq
D_{\textrm{LM}}\left(\Lambda_{A}\left(\tilde{\psi}_{Q}^{(K)}\right),\Lambda_{A}\left(\tilde{\phi}_{Q}^{(K)}\right)\right)$
(22) $\displaystyle=D_{\textrm{LM}}(\hat{p},\hat{q})$

where

$\displaystyle\hat{p}$ $\displaystyle=\sum_{\bf i}p_{\bf i}\,|{\bf
i}\rangle\\!\langle{\bf i}|,\quad\hat{q}$ $\displaystyle=\sum_{\bf i}q_{\bf
i}|{\bf i}\rangle\\!\langle{\bf i}|$ (23)

and $p_{\bf i}$ and $q_{\bf i}$ are classical distributions defined in
$\eqref{eq:outcome distribution}$ for $\psi$ and $\phi$ respectively, which
satisfy

$\displaystyle\sum_{\bf i}p_{\bf i}e_{A}({\bf i})$
$\displaystyle=\operatorname{Tr}(A\psi)+b_{A}(\psi),$ (24)
$\displaystyle\sum_{\bf i}q_{\bf i}e_{A}(\bf i)$
$\displaystyle=\operatorname{Tr}(A\phi)+b_{A}(\phi).$

When $\hat{p}$ and $\hat{q}$ are tensor products of classical states, i.e.,
$\hat{p}=\hat{p}^{(1)}\otimes\dots\otimes\hat{p}^{(K)}$ and
$\hat{q}=\hat{q}^{(1)}\otimes\dots\otimes\hat{q}^{(K)}$, it holds that

$\displaystyle D_{\textrm{LM}}(\hat{p},\hat{q})=D_{\rm tr}(\hat{p},\hat{q}).$
(25)

This can be seen as follows. Let $M^{\star}$ be the optimal POVM element
achieving the trace distance in (17). Then, we get

$\displaystyle D_{\rm tr}(\hat{p},\hat{q})$
$\displaystyle=\operatorname{Tr}[M^{\star}(\hat{p}-\hat{q})]$ (26)
$\displaystyle=\operatorname{Tr}[\Delta(M^{\star})(\hat{p}-\hat{q})]$

where

$\displaystyle\Delta(\cdot)\coloneqq\sum_{\bf i}|{\bf i}\rangle\\!\langle{\bf
i}|\cdot|{\bf i}\rangle\\!\langle{\bf i}|$ (27)

is a classical dephasing channel. The effective POVM element
$\Delta(M^{\star})$ has the form

$\displaystyle\Delta(M^{\star})=\sum_{\bf i}\braket{{\bf i}}{M^{\star}}{{\bf
i}}|{\bf i}\rangle\\!\langle{\bf i}|.$ (28)

Since each $|{\bf i}\rangle\\!\langle{\bf i}|$ is a local POVM element and
$0\leq\braket{{\bf i}}{M^{\star}}{{\bf i}}\leq 1$ because $0\leq
M^{\star}\leq\mathbb{I}$, the two-outcome measurement
$\\{\Delta(M^{\star}),\mathbb{I}-\Delta(M^{\star})\\}$ can be realized by a
local measurement and classical post-processing, and thus belongs to ${\rm
LM_{2}}$. This, together with (18), implies
$D_{\operatorname{tr}}(\hat{p},\hat{q})\leq D_{\textrm{LM}}(\hat{p},\hat{q})$,
and further combining (19) gives (25).

Combining (22) and (25) gives

$\displaystyle D_{\operatorname{tr}}(\hat{p},\hat{q})\leq D_{\rm
LM}\left(\tilde{\psi}_{Q}^{(K)},\tilde{\phi}_{Q}^{(K)}\right).$ (29)

We now connect (29) to the expression (24) of the expectation value and bias.
Let us first suppose
$\operatorname{Tr}(A\psi)+b_{A}(\psi)\geq\operatorname{Tr}(A\phi)+b_{A}(\phi)$.
Let $\mathcal{I}^{\star}\coloneqq\left\\{\left.{\bf
i}\;\rule{0.0pt}{9.5pt}\right|\;p_{\bf i}-q_{\bf i}\geq 0\right\\}$ and let
$\bar{\mathcal{I}}^{\star}$ be the complement set. Let us also define
$A^{\prime}=A+\mathbb{I}/2$, which satisfies $0\leq A^{\prime}\leq\mathbb{I}$
due to $-\mathbb{I}/2\leq A\leq\mathbb{I}/2$. Then, we get

$\displaystyle\operatorname{Tr}[A^{\prime}(\psi-\phi)]+b_{A}(\psi)-b_{A}(\phi)$
(30)
$\displaystyle=\operatorname{Tr}[(A+\mathbb{I}/2)(\phi-\psi)]+b_{A}(\phi)-b_{A}(\psi)$
$\displaystyle=\operatorname{Tr}[A(\phi-\psi)]+b_{A}(\phi)-b_{A}(\psi)$
$\displaystyle=\sum_{\bf i}(p_{\bf i}-q_{\bf i})e_{A}(\bf i)$
$\displaystyle\leq\sum_{\bf i\in\mathcal{I}^{\star}}(p_{\bf i}-q_{\bf
i})e_{A,\max}+\sum_{{\bf i}\in\bar{\mathcal{I}}^{\star}}(p_{\bf i}-q_{\bf
i})e_{A,\min}$
$\displaystyle=D_{\operatorname{tr}}(\hat{p},\hat{q})(e_{A,\max}-e_{A,\min})$

where in the third line we used (24), in the fourth line we used the maximum
and minimum estimator values

$\displaystyle e_{A,\max}\coloneqq\max_{\bf i}e_{A}({\bf i}),\quad
e_{A,\min}\coloneqq\min_{\bf i}e_{A}({\bf i}),$ (31)

and in the last line we used that

$\displaystyle\sum_{{\bf i}\in\bar{\mathcal{I}}^{\star}}(p_{\bf i}-q_{\bf
i})=-\sum_{{\bf i}\in\mathcal{I}^{\star}}(p_{\bf i}-q_{\bf i})$ (32)

and that the trace distance reduces to the total variation distance

$\displaystyle D_{\operatorname{tr}}(\hat{p},\hat{q})=\sum_{i:p_{i}-q_{i}\geq
0}(p_{i}-q_{i})$ (33)

for all classical states $\hat{p}=\sum_{i}p_{i}|{i}\rangle\\!\langle{i}|$ and
$\hat{q}=\sum_{i}q_{i}|{i}\rangle\\!\langle{i}|$. Combining (29) and (30), we
get

$\displaystyle
e_{A,\max}-e_{A,\min}\geq\frac{\operatorname{Tr}[A^{\prime}(\psi-\phi)]+b_{A}(\psi)-b_{A}(\phi)}{D_{\rm
LM}\left(\tilde{\psi}_{Q}^{(K)},\tilde{\phi}_{Q}^{(K)}\right)}.$ (34)

On the other hand, if
$\operatorname{Tr}(A\psi)+b_{A}(\psi)\leq\operatorname{Tr}(A\phi)+b_{A}(\phi)$,
we flip the role of $\psi$ and $\phi$ to get

$\displaystyle
e_{A,\max}-e_{A,\min}\geq-\frac{\operatorname{Tr}[A^{\prime}(\psi-\phi)]+b_{A}(\psi)-b_{A}(\phi)}{D_{\rm
LM}\left(\tilde{\psi}_{Q}^{(K)},\tilde{\phi}_{Q}^{(K)}\right)}.$ (35)

These two can be summarized as

$\displaystyle
e_{A,\max}-e_{A,\min}\geq\frac{\left|\operatorname{Tr}[A^{\prime}(\psi-\phi)]+b_{A}(\psi)-b_{A}(\phi)\right|}{D_{\rm
LM}\left(\tilde{\psi}_{Q}^{(K)},\tilde{\phi}_{Q}^{(K)}\right)}.$ (36)

Optimizing over $A$, $\phi$, and $\psi$ on both sides, we reach

$\displaystyle\Delta e_{\max}$
$\displaystyle\geq\max_{\begin{subarray}{c}\psi,\phi\\\ -\mathbb{I}/2\leq
A\leq\mathbb{I}/2\end{subarray}}\frac{|\operatorname{Tr}[A^{\prime}(\psi-\phi)]+b_{A}(\psi)-b_{A}(\phi)|}{D_{\rm
LM}\left(\tilde{\psi}_{Q}^{(K)},\tilde{\phi}_{Q}^{(K)}\right)}$ (37)
$\displaystyle=\max_{\begin{subarray}{c}\psi,\phi\\\ -\mathbb{I}/2\leq
A\leq\mathbb{I}/2\end{subarray}}\frac{\operatorname{Tr}[A^{\prime}(\psi-\phi)]+b_{A}(\psi)-b_{A}(\phi)}{D_{\rm
LM}\left(\tilde{\psi}_{Q}^{(K)},\tilde{\phi}_{Q}^{(K)}\right)}$
$\displaystyle\geq\max_{\begin{subarray}{c}\psi,\phi\end{subarray}}\frac{D_{\rm
tr}(\psi,\phi)+b_{A^{\star}}(\psi)-b_{A^{\star}}(\phi)}{D_{\rm
LM}\left(\tilde{\psi}_{Q}^{(K)},\tilde{\phi}_{Q}^{(K)}\right)}$
$\displaystyle\geq\max_{\begin{subarray}{c}\psi,\phi\end{subarray}}\frac{D_{\rm
tr}(\psi,\phi)-2b_{\max}}{D_{\rm
LM}\left(\tilde{\psi}_{Q}^{(K)},\tilde{\phi}_{Q}^{(K)}\right)}$

where in the second line we used that we can always take the numerator
positive by appropriately flipping $\psi$ and $\phi$, in the third line we
fixed ${A^{\prime}}^{\star}=A^{\star}+\mathbb{I}/2$ to the one that achieves
the trace distance
$\operatorname{Tr}[{A^{\prime}}^{\star}(\psi-\phi)]=D_{\operatorname{tr}}(\psi,\phi)$
as in (17), and in the fourth line we used the definition of $b_{\max}$.

∎

Measuring sub-fidelity — To estimate the sub-fidelity (7) for $n$-qubit states
$\rho$ and $\sigma$, it suffices to measure the two quantities,
$\operatorname{Tr}(\rho\sigma)$ and $\operatorname{Tr}(\rho\sigma\rho\sigma)$,
which can be measured by a quantum computer [42, 43]. For readers’
convenience, here we summarize several methods that can measure the sub-
fidelity and see that the measurement can be done by a constant-depth quantum
circuit.

Let us begin by $\operatorname{Tr}(\rho\sigma)$. Note that
$\operatorname{Tr}(\rho\sigma)=\operatorname{Tr}(S\,\rho\otimes\sigma)$ where
$S$ is the $n$-qubit SWAP operator defined by
$S\ket{\psi}\otimes\ket{\phi}=\ket{\phi}\otimes\ket{\psi}$ with $\ket{\psi}$
and $\ket{\phi}$ being arbitrary $n$-qubit pure states. This can be famously
measured by the SWAP test [42] that uses one ancillary qubit and $n$-qubit
SWAP gate controlled on the ancillary qubit. Since the $n$-qubit SWAP gate can
be realized by swapping individual qubits, the SWAP test runs with $n$ uses of
qubit SWAP gates controlled on the ancillary qubit, taking the circuit depth
$n$.

One can significantly reduce the circuit depth by employing the destructive
SWAP test [67]. Note that
$\operatorname{Tr}(\rho\sigma)=\operatorname{Tr}(S_{2}^{\otimes
n}\rho\otimes\sigma)$ where
$S_{2}\coloneqq\sum_{i,j=0}^{1}|{ij}\rangle\\!\langle{ji}|$ is the qubit SWAP
operator. This is obtained by measuring $\rho\otimes\sigma$ with respect to
the eigenbasis of $S_{2}^{\otimes n}$, which is just a tensor product of the
eigenbasis of $S_{2}$. Therefore, such a measurement can be accomplished by
individually measuring a pair of qubits from $\rho$ and $\sigma$ with respect
to the eigenbasis of $S_{2}$, for which one can use, e.g., Bell measurement.
These measurements can run in parallel and thus only needs a constant depth
circuit with respect to $n$ (in fact, depth 2) that involves $n$ two-qubit
gates.

We remark that, at this point, we have already obtained a valid lower bound of
$\Delta e_{\max}$ because the second term in (7) is positive, only improving
the lower bound. Nevertheless, evaluating the second term, which involves
$\operatorname{Tr}(\rho\sigma\rho\sigma)$, can significantly improve the bound
particularly when $\rho$ and $\sigma$ are highly noisy and their purity is
small.

$\operatorname{Tr}(\rho\sigma\rho\sigma)$ can be measured by a similar
strategy to the one for $\operatorname{Tr}(\rho\sigma)$ with two copies of
$\rho$ and $\sigma$. Instead of the SWAP operator $S$, consider the CYCLE
operator $C$ defined as
$C\left(\otimes_{i=1}^{4}\ket{\psi_{i}}\right)=\otimes_{i=1}^{4}\ket{\psi_{i+1}}$
where $\ket{\psi_{i}},i=1,2,3,4$ is an arbitrary $n$-qubit pure state with
$\ket{\psi_{5}}\coloneqq\ket{\psi_{1}}$. Then, it is straightforward to check
that
$\operatorname{Tr}(\rho\sigma\rho\sigma)=\operatorname{Tr}(C\,\rho\otimes\sigma\otimes\rho\otimes\sigma)$.
This can be measured by a generalization of the SWAP test where CYCLE gate $C$
is controlled on the single ancillary qubit. Similarly to the case of SWAP,
the CYCLE gate $C$ can be decomposed into $C=C_{2}^{\otimes n}$ where $k^{\rm
th}$ $C_{2}$ gate (for any $k=1,\dots,n$) acts on the four-qubit state that
consists of the $k^{\rm th}$ qubit of $\rho$, $\sigma$, $\rho$, and $\sigma$.
Since $C_{2}$ can be realized by three SWAP gates, one can measure
$\operatorname{Tr}(\rho\sigma\rho\sigma)$ with $3n$ uses of qubit-SWAP gates
controlled on the ancillary qubit, taking the circuit depth $3n$.

Similarly to the case of $\operatorname{Tr}(\rho\sigma)$, we can realize a
significant reduction in the circuit depth by making the measurement
destructive. All we have to do is to measure individual four-qubit states that
each $C_{2}$ gate acts on with respect to the eigenbasis of $C_{2}$. Since the
measurement of each $C_{2}$ can be run in parallel and each measurement
circuit has a depth independent of $n$, this results in a constant-depth
circuit that measures $C=C_{2}^{\otimes n}$.

We note the apparent similarity between the construction above and the circuit
used in virtual distillation [16, 17]. In particular, the strategy of
destructive measurement was extensively discussed in Ref. [17]. It is
interesting to see that a construction that is highly relevant to a specific
error-mitigation protocol provides a bound applicable to a general class of
error-mitigation protocols.

Applications to other error-mitigation protocols — Here, we discuss how our
framework can be applied to other two prominent error-mitigation protocols,
noise extrapolation and virtual distillation.

Extrapolation methods [5, 6] are used in scenarios where there is no clear
analytical noise model. These strategies consider a family of noise channels
$\\{\mathcal{N}_{\xi}\\}_{\xi}$, where $\xi$ corresponds to the noise
strength. The assumption here is that the description of $\mathcal{N}_{\xi}$
is unknown, but we have the ability to “boost” $\xi$ such that
$\xi\geq\tilde{\xi}$ where $\tilde{\xi}$ is the noise strength present in some
given noisy circuit. The idea is that by studying how the expectation value of
an observable depends on $\xi$, we can extrapolate what its value would be if
$\xi=0$. In particular, the $R^{\mathrm{th}}$ order Richardson extrapolation
method work as follows. Let us take constants $\\{\gamma_{r}\\}_{r=0}^{R}$ and
$\\{c_{r}\\}_{r=0}^{R}$ such that

$\displaystyle\sum_{r=0}^{R}\gamma_{r}=1,\ \
\sum_{r=0}^{R}\gamma_{r}c_{r}^{t}=0\quad t=1,\dots,R.$ (38)

Using these constants, one can show that

$\displaystyle\sum_{r=0}^{R}\gamma_{r}\operatorname{Tr}[A\mathcal{N}_{c_{r}\tilde{\xi}}(\psi)]=\operatorname{Tr}(A\psi)+b_{A}(\psi)$
(39)

where $b_{A}(\psi)=\mathcal{O}(\tilde{\xi}^{R+1})$. This allows us to estimate
the true expectation value using noisy states under multiple noise levels, as
long as $\tilde{\xi}$ is sufficiently small.

Richardson extrapolation is an instance of $(1,R+1)$-error mitigation. In
particular, we have

$\displaystyle\mathcal{E}^{(k)}=\mathcal{N}_{c_{k-1}\tilde{\xi}}\quad
k=1,\dots,R+1$ (40)

in Definition 4. For an observable $A=\sum_{a}a\Pi_{a}$ where $\Pi_{a}$ is the
projector corresponding to measuring outcome $a$, the POVMs
$\\{M_{a^{(k)}}^{(k)}\\}_{k=1}^{R+1}$ and classical estimator function $e_{A}$
take the forms

$\displaystyle M_{a^{(k)}}^{(k)}=\Pi_{a^{(k)}}\quad k=1,\dots,R+1,$ (41)
$\displaystyle
e_{A}(a^{(1)},\dots,a^{(R+1)})=\sum_{k=1}^{R+1}\gamma_{k-1}a^{(k)},$ (42)

where $\\{\gamma_{k}\\}_{k=0}^{R}$ are the constants determined by (38). One
can easily check that plugging the above expressions in the form of Definition
4 leads to (39).

Because of the constraint $-\mathbb{I}/2\leq A\leq\mathbb{I}/2$, every
eigenvalue $a$ satisfies $-1/2\leq a\leq 1/2$. This implies that

$\displaystyle e_{A,\max}$ $\displaystyle\leq\frac{1}{2}\sum_{r:\gamma_{r}\geq
0}\gamma_{r}-\frac{1}{2}\sum_{r:\gamma_{r}<0}\gamma_{r}$ (43)
$\displaystyle=\frac{1}{2}\sum_{r=0}^{R}|\gamma_{r}|$

and

$\displaystyle e_{A,\min}$
$\displaystyle\geq-\frac{1}{2}\sum_{r:\gamma_{r}\geq
0}\gamma_{r}+\frac{1}{2}\sum_{r:\gamma_{r}<0}\gamma_{r}$ (44)
$\displaystyle=-\frac{1}{2}\sum_{r=0}^{R}|\gamma_{r}|,$

leading to $\Delta e_{\max}\leq\sum_{r=0}^{R}|\gamma_{r}|$. On the other hand,
any observable $A$ having $\pm 1/2$ eigenvalues saturates this inequality.
Therefore, we get the exact expression of the maximum spread for the
extrapolation method as

$\displaystyle\Delta e_{\max}^{\rm EX}=\sum_{r=0}^{R}|\gamma_{r}|.$ (45)

Next, we discuss virtual distillation [16, 17], which is an example of
$(Q,1)$-error mitigation. Let $\psi$ be an ideal pure output state from a
quantum circuit. We consider a scenario where the noise in the circuit acts as
an effective noise channel $\mathcal{E}$ that brings the ideal state to a
noisy state of the form

$\displaystyle\mathcal{E}(\psi)=\lambda\psi+\sum_{k=2}^{d}\lambda_{k}\psi_{k}$
(46)

for a certain $\\{\lambda_{k}\\}_{k=1}^{d}$ with
$\lambda_{1}\coloneqq\lambda>1/2$, where $d$ is the dimension of the system
and $\\{\psi_{k}\\}_{k=1}^{d}$ constructs an orthonormal basis with
$\psi_{1}\coloneqq\psi$. We also assume that $\lambda$ is given as pre-
knowledge. This form reflects the intuition that, as long as the noise is
sufficiently small, the dominant eigenvector should be close to the ideal
state $\psi$. For a more detailed analysis of the form of this spectrum, we
refer readers to Ref. [68].

The $Q$-copy virtual distillation algorithm aims to estimate
$\operatorname{Tr}(W\psi)$ for a unitary observable $W$ satisfying
$W^{2}=\mathbb{I}$ (e.g., Pauli operators) by using $Q$ copies of
$\mathcal{E}(\psi)$. The mitigation circuit consists of a controlled
permutation and unitary $W$, followed by a measurement on the control qubit
with the Hadamard basis. The probability of getting outcome 0 (projecting onto
$|{+}\rangle\\!\langle{+}|$) is

$\displaystyle p_{0}$
$\displaystyle=\frac{1}{2}\left(1+\operatorname{Tr}\left[W\mathcal{E}(\psi)^{Q}\right]\right)$
(47)
$\displaystyle=\frac{1}{2}\left[1+\lambda^{Q}\operatorname{Tr}(W\psi)+\sum_{k=2}^{d}\lambda_{k}^{Q}\operatorname{Tr}(W\psi_{k})\right].$

This implies that

$\displaystyle(2p_{0}-1)\lambda^{-Q}=\operatorname{Tr}(W\psi)+\sum_{k=2}^{d}\left(\frac{\lambda_{k}}{\lambda}\right)^{Q}\operatorname{Tr}(W\psi_{k}),$
(48)

providing a way of estimating $\operatorname{Tr}(W\psi)$ with the bias
$|\sum_{k=2}^{d}(\lambda_{k}/\lambda)^{Q}\operatorname{Tr}(W\psi_{k})|\leq\sum_{k=2}^{d}(\lambda_{k}/\lambda)^{Q}$.

We can see that this protocol fits into our framework with $K=1$ and
$\mathcal{E}_{q}=\mathcal{E}$ for $q=1,\dots,Q$ as follows. For an arbitrary
observable $A$ with $-\mathbb{I}/2\leq A\leq\mathbb{I}/2$, we can always find
a decomposition with respect to the Pauli operators $\\{P_{i}\\}$ as

$\displaystyle A=\sum_{i}c_{i}P_{i}$ (49)

for some set of real numbers $\\{c_{i}\\}$. We now apply the virtual
distillation circuit for $P_{i}$ at probability $|c_{i}|/\sum_{j}|c_{j}|$ and
— similarly to the case of probabilistic error cancellation — employ an
estimator function defined as

$\displaystyle e_{A}(i0)$
$\displaystyle\coloneqq\gamma\mathrm{sgn}(c_{i})\lambda^{-Q}$ (50)
$\displaystyle e_{A}(i1)$
$\displaystyle\coloneqq-\gamma\mathrm{sgn}(c_{i})\lambda^{-Q}$

with $\gamma\coloneqq\sum_{i}|c_{i}|$, where we treat $i$ as a part of the
measurement outcome. Then, we get

$\displaystyle\sum_{i}\left[p_{i0}\,e_{A}(i0)+p_{i1}e_{A}(i1)\right]=\operatorname{Tr}(A\psi)+b_{A}(\psi)$
(51)

where $p_{i0}$ is the probability (47) with $W=P_{i}$, $p_{i1}=1-p_{i0}$, and
$b_{A}(\psi)\coloneqq\sum_{k=2}^{d}(\lambda_{k}/\lambda)^{Q}\operatorname{Tr}(A\psi_{k})$.
Optimizing over observables $-\mathbb{I}/2\leq A\leq\mathbb{I}/2$, we have

$\displaystyle\Delta e_{\max}^{\rm
VD}=\max\left\\{\left.2\lambda^{-Q}\sum_{i}|c_{i}|\;\rule{0.0pt}{9.5pt}\right|\;-\mathbb{I}/2\leq\sum_{i}c_{i}P_{i}\leq\mathbb{I}/2\right\\}$
(52)

and

$\displaystyle b_{\max}^{\rm
VD}=\sum_{k=2}^{d}\frac{1}{2}\left(\frac{\lambda_{k}}{\lambda}\right)^{Q}.$
(53)

###### Acknowledgements.

We thank Yuichiro Matsuzaki, Yuuki Tokunaga, Hideaki Hakoshima, Kaoru
Yamamoto, and Francesco Buscemi for fruitful discussions. This research is
supported by the Singapore Ministry of Education Tier 1 Grant RG162/19 and
RG146/20, the National Research Foundation (NRF) Singapore, under its NRFF
Fellow program (Award No. NRF-NRFF2016-02), the FQXi-RFP-IPW-1903 project,
’Are quantum agents more energetically efficient at making predictions?’ from
the Foundational Questions Institute, Fetzer Franklin Fund, a donor advised
fund of Silicon Valley Community Foundation, and the Lee Kuan Yew Postdoctoral
Fellowship at Nanyang Technological University Singapore. Any opinions,
findings and conclusions or recommendations expressed in this material are
those of the author(s) and do not reflect the views of National Research
Foundation or the Ministry of Education, Singapore. S.E. is supported by
ERATO, JST, Grant No. JPMJER1601; Moonshot R&D, JST, Grant No. JPMJMS2061;
MEXT Q-LEAP Grant No. JPMXS0120319794 and JPMXS0118068682.

## References

  * Preskill [2018] J. Preskill,  _Quantum Computing in the NISQ era and beyond_ , Quantum 2, 79 (2018).
  * Arute et al. [2019] F. Arute et al.,  _Quantum supremacy using a programmable superconducting processor_ , Nature 574, 505 (2019).
  * Fowler  _et al._ [2012] A. G. Fowler, M. Mariantoni, J. M. Martinis, and A. N. Cleland,  _Surface codes: Towards practical large-scale quantum computation_ , Phys. Rev. A 86, 032324 (2012).
  * Campbell  _et al._ [2017] E. T. Campbell, B. M. Terhal, and C. Vuillot,  _Roads towards Fault-Tolerant Universal Quantum Computation_ , Nature 549, 172 (2017).
  * Temme  _et al._ [2017] K. Temme, S. Bravyi, and J. M. Gambetta,  _Error Mitigation for Short-Depth Quantum Circuits_ , Phys. Rev. Lett. 119, 180509 (2017).
  * Li and Benjamin [2017] Y. Li and S. C. Benjamin,  _Efficient Variational Quantum Simulator Incorporating Active Error Minimization_ , Phys. Rev. X 7, 021050 (2017).
  * Giurgica-Tiron  _et al._ [2020] T. Giurgica-Tiron, Y. Hindy, R. LaRose, A. Mari, and W. J. Zeng,  _Digital zero noise extrapolation for quantum error mitigation_ , 2020 IEEE International Conference on Quantum Computing and Engineering (QCE) , 306 (2020).
  * He  _et al._ [2020] A. He, B. Nachman, W. A. de Jong, and C. W. Bauer,  _Zero-noise extrapolation for quantum-gate error mitigation with identity insertions_ , Phys. Rev. A 102, 012426 (2020).
  * Kandala  _et al._ [2019] A. Kandala, K. Temme, A. D. Córcoles, A. Mezzacapo, J. M. Chow, and J. M. Gambetta,  _Error mitigation extends the computational reach of a noisy quantum processor_ , Nature 567, 491 (2019).
  * Dumitrescu  _et al._ [2018] E. F. Dumitrescu, A. J. McCaskey, G. Hagen, G. R. Jansen, T. D. Morris, T. Papenbrock, R. C. Pooser, D. J. Dean, and P. Lougovski,  _Cloud Quantum Computing of an Atomic Nucleus_ , Phys. Rev. Lett. 120, 210501 (2018).
  * [11] F. Buscemi, M. Dall’Arno, M. Ozawa, and V. Vedral,  _Direct observation of any two-point quantum correlation function_ , arXiv:1312.4240 .
  * Buscemi  _et al._ [2014] F. Buscemi, M. Dall’Arno, M. Ozawa, and V. Vedral,  _Universal optimal quantum correlator_ , Int. J. Quantum Inf. 12, 1560002 (2014).
  * Endo  _et al._ [2018] S. Endo, S. C. Benjamin, and Y. Li,  _Practical Quantum Error Mitigation for Near-Future Applications_ , Phys. Rev. X 8, 031027 (2018).
  * Song  _et al._ [2019] C. Song, J. Cui, H. Wang, J. Hao, H. Feng, and Y. Li,  _Quantum computation with universal error mitigation on a superconducting quantum processor_ , Sci. Adv. 5, eaaw5686 (2019).
  * Zhang  _et al._ [2020] S. Zhang, Y. Lu, K. Zhang, W. Chen, Y. Li, J.-N. Zhang, and K. Kim,  _Error-mitigated quantum gates exceeding physical fidelities in a trapped-ion system_ , Nat. Commun. 11, 587 (2020).
  * Koczor [2021a] B. Koczor,  _Exponential Error Suppression for Near-Term Quantum Devices_ , Phys. Rev. X 11, 031057 (2021a).
  * Huggins  _et al._ [2021] W. J. Huggins, S. McArdle, T. E. O’Brien, J. Lee, N. C. Rubin, S. Boixo, K. B. Whaley, R. Babbush, and J. R. McClean,  _Virtual Distillation for Quantum Error Mitigation_ , Phys. Rev. X 11, 041036 (2021).
  * Czarnik  _et al._ [2021a] P. Czarnik, A. Arrasmith, L. Cincio, and P. J. Coles,  _Qubit-efficient exponential suppression of errors_ , (2021a), arXiv:2102.06056 .
  * Cai [2021] Z. Cai,  _Resource-efficient Purification-based Quantum Error Mitigation_ , (2021), arXiv:2107.07279 .
  * Huo and Li [2021] M. Huo and Y. Li,  _Dual-state purification for practical quantum error mitigation_ , (2021), arXiv:2105.01239 .
  * Xiong  _et al._ [2021] Y. Xiong, S. X. Ng, and L. Hanzo,  _Quantum error mitigation relying on permutation filtering_ , (2021), arXiv:2107.01458 .
  * Kandala  _et al._ [2017] A. Kandala, A. Mezzacapo, K. Temme, M. Takita, M. Brink, J. M. Chow, and J. M. Gambetta,  _Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets_ , Nature 549, 242 (2017).
  * McArdle  _et al._ [2020] S. McArdle, S. Endo, A. Aspuru-Guzik, S. C. Benjamin, and X. Yuan,  _Quantum computational chemistry_ , Rev. Mod. Phys. 92, 015003 (2020).
  * Cao  _et al._ [2019] Y. Cao, J. Romero, J. P. Olson, M. Degroote, P. D. Johnson, M. Kieferová, I. D. Kivlichan, T. Menke, B. Peropadre, N. P. Sawaya, _et al._ ,  _Quantum chemistry in the age of quantum computing_ , Chem. Rev. 119, 10856 (2019).
  * McArdle  _et al._ [2019] S. McArdle, X. Yuan, and S. Benjamin,  _Error-Mitigated Digital Quantum Simulation_ , Phys. Rev. Lett. 122, 180501 (2019).
  * Wang  _et al._ [2021a] S. Wang, E. Fontana, M. Cerezo, K. Sharma, A. Sone, L. Cincio, and P. J. Coles,  _Noise-induced barren plateaus in variational quantum algorithms_ , Nat. Commun. 12, 6961 (2021a).
  * Yuan  _et al._ [2016] X. Yuan, Z. Zhang, N. Lütkenhaus, and X. Ma,  _Simulating single photons with realistic photon sources_ , Phys. Rev. A 94, 062305 (2016).
  * Note [1] For instance, if we are interested in a non-identity Pauli operator $P$, which has eigenvalues $\pm 1$, we instead consider an observable $A=P/2$.
  * Note [2] In principle, one can consider a different number of inputs $Q_{k}$ for each $k^{\mathrm{th}}$ experiment, which may find a better fit to a recent proposal [34]. Such scenarios are still encompassed in the present framework by setting $Q=\mathop{max}\displaylimits_{k}Q_{k}$, but it may result in a tighter bound in Theorem 1.
  * McClean  _et al._ [2017] J. R. McClean, M. E. Kimchi-Schwartz, J. Carter, and W. A. de Jong,  _Hybrid quantum-classical hierarchy for mitigation of decoherence and determination of excited states_ , Phys. Rev. A 95, 042308 (2017).
  * Czarnik  _et al._ [2021b] P. Czarnik, A. Arrasmith, P. J. Coles, and L. Cincio,  _Error mitigation with Clifford quantum-circuit data_ , Quantum 5, 592 (2021b).
  * Bonet-Monroig  _et al._ [2018] X. Bonet-Monroig, R. Sagastizabal, M. Singh, and T. E. O’Brien,  _Low-cost error mitigation by symmetry verification_ , Phys. Rev. A 98, 062339 (2018).
  * Bravyi  _et al._ [2021] S. Bravyi, S. Sheldon, A. Kandala, D. C. Mckay, and J. M. Gambetta,  _Mitigating measurement errors in multiqubit experiments_ , Phys. Rev. A 103, 042605 (2021).
  * Yoshioka  _et al._ [2021] N. Yoshioka, H. Hakoshima, Y. Matsuzaki, Y. Tokunaga, Y. Suzuki, and S. Endo,  _Generalized quantum subspace expansion_ , (2021), arXiv:2107.02611 .
  * McClean  _et al._ [2020] J. R. McClean, Z. Jiang, N. C. Rubin, R. Babbush, and H. Neven,  _Decoding quantum errors with subspace expansions_ , Nat. Commun. 11, 636 (2020).
  * Hoeffding [1963] W. Hoeffding,  _Probability Inequalities for Sums of Bounded Random Variables_ , J. Am. Stat. Assoc. 58, 13 (1963).
  * Note [3] Mathematically, $\Delta e_{A}=e_{A,\mathop{max}\displaylimits}-e_{A,\mathop{min}\displaylimits}$ where $\Delta e_{A,\mathop{max}\displaylimits}=\mathop{max}\displaylimits_{i^{(1)}\dots i^{(K)}}e_{A}(i^{(1)}\dots i^{(K)})$ and $e_{A,\mathop{min}\displaylimits}=\mathop{min}\displaylimits_{i^{(1)}\dots i^{(K)}}e_{A}(i^{(1)}\dots i^{(K)})$.
  * Matthews  _et al._ [2009] W. Matthews, S. Wehner, and A. Winter,  _Distinguishability of Quantum States Under Restricted Families of Measurements with an Application to Quantum Data Hiding_ , Commun. Math. Phys. 291, 813 (2009).
  * Nielsen and Chuang [2000] M. A. Nielsen and I. Chuang,  _Quantum computation and quantum information_ (Cambridge University Press, 2000).
  * Watrous [2018] J. Watrous,  _The Theory of Quantum Information_ (Cambridge University Press, Cambridge, 2018).
  * Miszczak  _et al._ [2009] J. A. Miszczak, Z. Puchała, P. Horodecki, A. Uhlmann, and K. Życzkowski,  _Sub– and super–fidelity as bounds for quantum fidelity_ , Quantum Inf. Comput. 9, 0103 (2009).
  * Ekert  _et al._ [2002] A. K. Ekert, C. M. Alves, D. K. L. Oi, M. Horodecki, P. Horodecki, and L. C. Kwek,  _Direct Estimations of Linear and Nonlinear Functionals of a Quantum State_ , Phys. Rev. Lett. 88, 217901 (2002).
  * Bacon  _et al._ [2006] D. Bacon, I. L. Chuang, and A. W. Harrow,  _Efficient Quantum Circuits for Schur and Clebsch-Gordan Transforms_ , Phys. Rev. Lett. 97, 170502 (2006).
  * Cerezo  _et al._ [2020] M. Cerezo, A. Poremba, L. Cincio, and P. J. Coles,  _Variational Quantum Fidelity Estimation_ , Quantum 4, 248 (2020).
  * Peruzzo  _et al._ [2014] A. Peruzzo, J. McClean, P. Shadbolt, M.-H. Yung, X.-Q. Zhou, P. J. Love, A. Aspuru-Guzik, and J. L. O’brien,  _A variational eigenvalue solver on a photonic quantum processor_ , Nat. Commun. 5, 4213 (2014).
  * Kim  _et al._ [2021] Y. Kim, C. J. Wood, T. J. Yoder, S. T. Merkel, J. M. Gambetta, K. Temme, and A. Kandala,  _Scalable error mitigation for noisy quantum circuits produces competitive expectation values_ , (2021), arXiv:2108.09197 .
  * Sagastizabal  _et al._ [2019] R. Sagastizabal, X. Bonet-Monroig, M. Singh, M. A. Rol, C. C. Bultink, X. Fu, C. H. Price, V. P. Ostroukh, N. Muthusubramanian, A. Bruno, M. Beekman, N. Haider, T. E. O’Brien, and L. DiCarlo,  _Experimental error mitigation via symmetry verification in a variational quantum eigensolver_ , Phys. Rev. A 100, 010302 (2019).
  * Müller-Hermes  _et al._ [2016] A. Müller-Hermes, D. Stilck França, and M. M. Wolf,  _Relative entropy convergence for depolarizing channels_ , J. Math. Phys. 57, 022202 (2016).
  * Takagi [2021] R. Takagi,  _Optimal resource cost for error mitigation_ , Phys. Rev. Research 3, 033178 (2021).
  * Jiang  _et al._ [2021] J. Jiang, K. Wang, and X. Wang,  _Physical Implementability of Linear Maps and Its Application in Error Mitigation_ , Quantum 5, 600 (2021).
  * Regula  _et al._ [2021] B. Regula, R. Takagi, and M. Gu,  _Operational applications of the diamond norm and related measures in quantifying the non-physicality of quantum maps_ , Quantum 5, 522 (2021).
  * Note [4] The lower bound can be obtained by considering a specific choice of $\psi$ and $\phi$, e.g., $\mathinner{|{\psi}\rangle}=\mathinner{|{+}\rangle}$ and $\mathinner{|{\phi}\rangle}=\mathinner{|{-}\rangle}$ where $\mathinner{|{\pm}\rangle}\coloneqq(\mathinner{|{0}\rangle}\pm\mathinner{|{1}\rangle})/\sqrt{2}$.
  * Hakoshima  _et al._ [2021] H. Hakoshima, Y. Matsuzaki, and S. Endo,  _Relationship between costs for quantum error mitigation and non-Markovian measures_ , Phys. Rev. A 103, 012611 (2021).
  * Breuer  _et al._ [2016] H.-P. Breuer, E.-M. Laine, J. Piilo, and B. Vacchini,  _Colloquium: Non-Markovian dynamics in open quantum systems_ , Rev. Mod. Phys. 88, 021002 (2016).
  * Suzuki  _et al._ [2020] Y. Suzuki, S. Endo, K. Fujii, and Y. Tokunaga,  _Quantum error mitigation for fault-tolerant quantum computing_ , (2020), arXiv:2010.03887 .
  * Lostaglio and Ciani [2021] M. Lostaglio and A. Ciani,  _Error Mitigation and Quantum-Assisted Simulation in the Error Corrected Regime_ , Phys. Rev. Lett. 127, 200506 (2021).
  * Piveteau  _et al._ [2021] C. Piveteau, D. Sutter, S. Bravyi, J. M. Gambetta, and K. Temme,  _Error Mitigation for Universal Gates on Encoded Qubits_ , Phys. Rev. Lett. 127, 200505 (2021).
  * Xiong  _et al._ [2020] Y. Xiong, D. Chandra, S. X. Ng, and L. Hanzo,  _Sampling Overhead Analysis of Quantum Error Mitigation: Uncoded vs. Coded Systems_ , IEEE Access 8, 228967 (2020).
  * Lloyd [2008] S. Lloyd,  _Enhanced sensitivity of photodetection via quantum illumination_ , Science 321, 1463 (2008).
  * Giovannetti  _et al._ [2006] V. Giovannetti, S. Lloyd, and L. Maccone,  _Quantum Metrology_ , Phys. Rev. Lett. 96, 010401 (2006).
  * Audenaert  _et al._ [2008] K. M. Audenaert, M. Nussbaum, A. Szkoła, and F. Verstraete,  _Asymptotic error rates in quantum hypothesis testing_ , Commun. Math. Phys. 279, 251 (2008).
  * Binder  _et al._ [2018] F. C. Binder, J. Thompson, and M. Gu,  _Practical Unitary Simulator for Non-Markovian Complex Processes_ , Phys. Rev. Lett. 120, 240502 (2018).
  * Blank  _et al._ [2021] C. Blank, D. K. Park, and F. Petruccione,  _Quantum-enhanced analysis of discrete stochastic processes_ , npj Quantum Inf. 7, 1–9 (2021).
  * Wang  _et al._ [2021b] S. Wang, P. Czarnik, A. Arrasmith, M. Cerezo, L. Cincio, and P. J. Coles,  _Can Error Mitigation Improve Trainability of Noisy Variational Quantum Algorithms?_ , (2021b), arXiv:2109.01051 .
  * Lami  _et al._ [2018] L. Lami, C. Palazuelos, and A. Winter,  _Ultimate Data Hiding in Quantum Mechanics and Beyond_ , Commun. Math. Phys. 361, 661 (2018).
  * Corrêa  _et al._ [2021] W. H. G. Corrêa, L. Lami, and C. Palazuelos,  _Maximal gap between local and global distinguishability of bipartite quantum states_ , (2021), arXiv:2110.04387 .
  * Garcia-Escartin and Chamorro-Posada [2013] J. C. Garcia-Escartin and P. Chamorro-Posada,  _SWAP test and Hong-Ou-Mandel effect are equivalent_ , Phys. Rev. A 87, 052330 (2013).
  * Koczor [2021b] B. Koczor,  _The dominant eigenvector of a noisy quantum state_ , New J. Phys. 23, 123047 (2021b).
  * Hiai  _et al._ [1981] F. Hiai, M. Ohya, and M. Tsukada,  _Sufficiency, KMS condition and relative entropy in von Neumann algebras._ , Pac. J. Math. 96, 99 (1981).

##  Appendix A Proof of Theorem 3

###### Proof.

For an arbitrary unitary channel $\mathcal{V}$, Eq. (3) in Theorem 1 can also
be written as

$\displaystyle\Delta e_{\max}$
$\displaystyle\geq\max_{\psi,\phi}\frac{D_{\operatorname{tr}}(\psi,\phi)-2b_{\max}}{D_{\rm
LM}\left(\otimes_{k=1}^{K}\otimes_{q=1}^{Q}\mathcal{E}_{q}^{(k)}(\psi),\otimes_{k=1}^{K}\otimes_{q=1}^{Q}\mathcal{E}_{q}^{(k)}(\phi)\right)}$
(54)
$\displaystyle=\max_{\psi,\phi}\frac{D_{\operatorname{tr}}(\mathcal{V}^{\dagger}(\psi),\mathcal{V}^{\dagger}(\phi))-2b_{\max}}{D_{\rm
LM}\left(\otimes_{k=1}^{K}\otimes_{q=1}^{Q}\mathcal{E}_{q}^{(k)}\circ\mathcal{V}(\mathcal{V}^{\dagger}(\psi)),\otimes_{k=1}^{K}\otimes_{q=1}^{Q}\mathcal{E}_{q}^{(k)}\circ\mathcal{V}(\mathcal{V}^{\dagger}(\phi))\right)}$
$\displaystyle=\max_{\psi_{\rm in},\phi_{\rm
in}}\frac{D_{\operatorname{tr}}(\psi_{\rm in},\phi_{\rm in})-2b_{\max}}{D_{\rm
LM}\left(\otimes_{k=1}^{K}\otimes_{q=1}^{Q}\mathcal{E}_{q}^{(k)}\circ\mathcal{V}(\psi_{\rm
in}),\otimes_{k=1}^{K}\otimes_{q=1}^{Q}\mathcal{E}_{q}^{(k)}\circ\mathcal{V}(\phi_{\rm
in})\right)},$

where in the second line we used the unitary invariance of the trace distance,
and in the third line we changed the variables as
$\mathcal{V}^{\dagger}(\psi)\to\psi_{\rm in}$,
$\mathcal{V}^{\dagger}(\phi)\to\phi_{\rm in}$ and used the fact that the
application of a fixed unitary does not affect the optimization taken over all
states.

The noise model for layered circuits typically assumes the application of a
noise channel after each layer. Let $\mathcal{N}_{q,l}^{(k)}$ be a noise
channel after the $l^{\mathrm{th}}$ layer for the $q^{\mathrm{th}}$ input in
the $k^{\mathrm{th}}$ experiment. Then, a noisy circuit for the
$q^{\mathrm{th}}$ input in the $k^{\mathrm{th}}$ experiment is described by

$\displaystyle\mathcal{N}_{q,L}^{(k)}\circ\mathcal{U}_{L}\circ\cdots\circ\mathcal{N}_{q,1}^{(k)}\circ\mathcal{U}_{1}$
(55)

while the ideal output given input state $\psi_{\rm in}$ is
$\psi=\mathcal{U}_{L}\circ\cdots\circ\mathcal{U}_{1}(\psi_{\rm in})$. The
effective noise channel for the $q^{\mathrm{th}}$ input in the
$k^{\mathrm{th}}$ experiment is then given by

$\displaystyle\mathcal{E}_{q}^{(k)}=\mathcal{N}_{q,L}^{(k)}\circ\mathcal{U}_{L}\circ\cdots\circ\mathcal{N}_{q,1}^{(k)}\circ\mathcal{U}_{1}\circ\mathcal{U}_{1}^{\dagger}\circ\mathcal{U}_{2}^{\dagger}\circ\cdots\circ\mathcal{U}_{L}^{\dagger}.$
(56)

Plugging (56) into (54) while taking
$\mathcal{V}=\mathcal{U}_{L}\circ\cdots\circ\mathcal{U}_{1}$, we get

$\displaystyle\Delta e_{\max}$ $\displaystyle\geq\max_{\psi_{\rm in},\phi_{\rm
in}}\frac{D_{\operatorname{tr}}(\psi_{\rm in},\phi_{\rm in})-2b_{\max}}{D_{\rm
LM}\left(\otimes_{k=1}^{K}\otimes_{q=1}^{Q}\prod_{l=1}^{L}\left[\mathcal{N}_{q,l}^{(k)}\circ\mathcal{U}_{l}\right](\psi_{\rm
in}),\otimes_{k=1}^{K}\otimes_{q=1}^{Q}\prod_{l=1}^{L}\left[\mathcal{N}_{q,l}^{(k)}\circ\mathcal{U}_{l}\right](\phi_{\rm
in})\right)},$ (57)

where we used the notation

$\displaystyle\prod_{l=1}^{L}\left[\mathcal{N}_{q,l}^{(k)}\circ\mathcal{U}_{l}\right]\coloneqq\mathcal{N}_{q,L}^{(k)}\circ\mathcal{U}_{L}\circ\cdots\circ\mathcal{N}_{q,1}^{(k)}\circ\mathcal{U}_{1}$
(58)

The denominator of the right-hand side of (57) can be bounded as

$\displaystyle D_{\rm
LM}\left(\otimes_{k=1}^{K}\otimes_{q=1}^{Q}\prod_{l=1}^{L}\left[\mathcal{N}_{q,l}^{(k)}\circ\mathcal{U}_{l}\right](\psi_{\rm
in}),\otimes_{k=1}^{K}\otimes_{q=1}^{Q}\prod_{l=1}^{L}\left[\mathcal{N}_{q,l}^{(k)}\circ\mathcal{U}_{l}\right](\phi_{\rm
in})\right)$ (59) $\displaystyle\leq D_{\rm
tr}\left(\otimes_{k=1}^{K}\otimes_{q=1}^{Q}\prod_{l=1}^{L}\left[\mathcal{N}_{q,l}^{(k)}\circ\mathcal{U}_{l}\right](\psi_{\rm
in}),\otimes_{k=1}^{K}\otimes_{q=1}^{Q}\prod_{l=1}^{L}\left[\mathcal{N}_{q,l}^{(k)}\circ\mathcal{U}_{l}\right](\phi_{\rm
in})\right)$ $\displaystyle\leq D_{\rm
tr}\left(\otimes_{k=1}^{K}\otimes_{q=1}^{Q}\prod_{l=1}^{L}\left[\mathcal{N}_{q,l}^{(k)}\circ\mathcal{U}_{l}\right](\psi_{\rm
in}),\frac{\mathbb{I}}{2^{KQn}}\right)+D_{\rm
tr}\left(\otimes_{k=1}^{K}\otimes_{q=1}^{Q}\prod_{l=1}^{L}\left[\mathcal{N}_{q,l}^{(k)}\circ\mathcal{U}_{l}\right](\phi_{\rm
in}),\frac{\mathbb{I}}{2^{KQn}}\right)$
$\displaystyle\leq\sum_{k=1}^{K}\left[D_{\rm
tr}\left(\otimes_{q=1}^{Q}\prod_{l=1}^{L}\left[\mathcal{N}_{q,l}^{(k)}\circ\mathcal{U}_{l}\right](\psi_{\rm
in}),\frac{\mathbb{I}}{2^{Qn}}\right)+D_{\rm
tr}\left(\otimes_{q=1}^{Q}\prod_{l=1}^{L}\left[\mathcal{N}_{q,l}^{(k)}\circ\mathcal{U}_{l}\right](\phi_{\rm
in}),\frac{\mathbb{I}}{2^{Qn}}\right)\right]$

where the first inequality is due to (19), the second inequality is due to the
triangle inequality, and in the last line we bounded each term by sequentially
applying the triangle inequality as

$\displaystyle D_{\rm
tr}\left(\otimes_{k=1}^{K}\otimes_{q=1}^{Q}\prod_{l=1}^{L}\left[\mathcal{N}_{q,l}^{(k)}\circ\mathcal{U}_{l}\right](\psi_{\rm
in}),\frac{\mathbb{I}}{2^{KQn}}\right)$ (60) $\displaystyle\leq D_{\rm
tr}\left(\otimes_{k=1}^{K}\otimes_{q=1}^{Q}\prod_{l=1}^{L}\left[\mathcal{N}_{q,l}^{(k)}\circ\mathcal{U}_{l}\right](\psi_{\rm
in}),\frac{\mathbb{I}}{2^{Qn}}\otimes_{k=2}^{K}\otimes_{q=1}^{Q}\prod_{l=1}^{L}\left[\mathcal{N}_{q,l}^{(k)}\circ\mathcal{U}_{l}\right](\psi_{\rm
in})\right)$ $\displaystyle\quad+D_{\rm
tr}\left(\frac{\mathbb{I}}{2^{Qn}}\otimes_{k=2}^{K}\otimes_{q=1}^{Q}\prod_{l=1}^{L}\left[\mathcal{N}_{q,l}^{(k)}\circ\mathcal{U}_{l}\right](\psi_{\rm
in}),\frac{\mathbb{I}}{2^{Qn}}\otimes\frac{\mathbb{I}}{2^{Qn(K-1)}}\right)$
$\displaystyle=D_{\rm
tr}\left(\otimes_{q=1}^{Q}\prod_{l=1}^{L}\left[\mathcal{N}_{q,l}^{(1)}\circ\mathcal{U}_{l}\right](\psi_{\rm
in}),\frac{\mathbb{I}}{2^{Qn}}\right)+D_{\rm
tr}\left(\otimes_{k=2}^{K}\otimes_{q=1}^{Q}\prod_{l=1}^{L}\left[\mathcal{N}_{q,l}^{(k)}\circ\mathcal{U}_{l}\right](\psi_{\rm
in}),\frac{\mathbb{I}}{2^{Qn(K-1)}}\right)$ $\displaystyle\leq\dots$
$\displaystyle\leq\sum_{k=1}^{K}D_{\rm
tr}\left(\otimes_{q=1}^{Q}\prod_{l=1}^{L}\left[\mathcal{N}_{q,l}^{(k)}\circ\mathcal{U}_{l}\right](\psi_{\rm
in}),\frac{\mathbb{I}}{2^{Qn}}\right),$

and similarly for the second term. The last expression in (59) can be further
upper bounded as

$\displaystyle\leq\sqrt{\frac{\ln
2}{2}}\sum_{k=1}^{K}\left(\sqrt{S\left(\otimes_{q=1}^{Q}\prod_{l=1}^{L}\left[\mathcal{N}_{q,l}^{(k)}\circ\mathcal{U}_{l}\right](\psi_{\rm
in})\,\Big{\|}\,\frac{\mathbb{I}}{2^{Qn}}\right)}+\sqrt{S\left(\otimes_{q=1}^{Q}\prod_{l=1}^{L}\left[\mathcal{N}_{q,l}^{(k)}\circ\mathcal{U}_{l}\right](\phi_{\rm
in})\,\Big{\|}\,\frac{\mathbb{I}}{2^{Qn}}\right)}\right),$ (61)

where we used the quantum Pinsker’s inequality [69]

$\displaystyle D_{\operatorname{tr}}(\rho,\sigma)\leq\sqrt{\frac{\ln
2}{2}}\,\sqrt{S(\rho\|\sigma)}$ (62)

for all states $\rho$, $\sigma$, where
$S(\rho\|\sigma)\coloneqq\operatorname{Tr}(\rho\log\rho)-\operatorname{Tr}(\rho\log\sigma)$
is the relative entropy.

We now recall Theorem 6.1 of Ref. [48] (see also Supplementary Lemma 5 of Ref.
[26]), which evaluates the entropy increase due to the local depolarizing
noise.

######  Lemma 5 ([48]).

Let $\mathcal{D}_{\epsilon}^{d}(\rho)=(1-\epsilon)\rho+\epsilon\mathbb{I}/d$
be a $d$-dimensional depolarizing channel. Then, for an arbitrary $n$-qudit
state $\rho_{n}$, it holds that

$\displaystyle S\left(\left({\mathcal{D}_{\epsilon}^{d}}\right)^{\otimes
n}(\rho_{n})\,\Big{\|}\,\mathbb{I}/d^{n}\right)\leq(1-\epsilon)S(\rho_{n}\,\|\,\mathbb{I}/d^{n}).$
(63)

Then, for $\mathcal{N}_{q,l}^{(k)}=\mathcal{D}_{\epsilon_{k}}^{\otimes n}$
where $\mathcal{D}_{\epsilon_{k}}$ is a qubit depolarizing channel (see also
Fig. 6), we get

$\displaystyle
S\left(\otimes_{q=1}^{Q}\prod_{l=1}^{L}\left[\mathcal{N}_{q,l}^{(k)}\circ\mathcal{U}_{l}\right](\psi_{\rm
in})\,\Big{\|}\,\frac{\mathbb{I}}{2^{Qn}}\right)$
$\displaystyle=S\left(\prod_{l=1}^{L}\left[\mathcal{D}_{\epsilon_{k}}^{\otimes
Qn}\circ\mathcal{U}_{l}^{\otimes Q}\right](\psi_{\rm in}^{\otimes
Q})\,\Big{\|}\,\frac{\mathbb{I}}{2^{Qn}}\right)$ (64)
$\displaystyle\leq(1-\epsilon_{k})\,S\left(\mathcal{U}_{L}^{\otimes
Q}\prod_{l=2}^{L}\left[\mathcal{D}_{\epsilon_{k}}^{\otimes
Qn}\circ\mathcal{U}_{l}^{\otimes Q}\right](\psi_{\rm in}^{\otimes
Q})\,\Big{\|}\,\frac{\mathbb{I}}{2^{Qn}}\right)$
$\displaystyle=(1-\epsilon_{k})\,S\left(\prod_{l=2}^{L}\left[\mathcal{D}_{\epsilon_{k}}^{\otimes
Qn}\circ\mathcal{U}_{l}^{\otimes Q}\right](\psi_{\rm in}^{\otimes
Q})\,\Big{\|}\,\frac{\mathbb{I}}{2^{Qn}}\right)$
$\displaystyle\leq(1-\epsilon_{k})^{L}\,S\left(\psi_{\rm in}^{\otimes
Q}\,\Big{\|}\,\frac{\mathbb{I}}{2^{Qn}}\right)$
$\displaystyle\leq(1-\epsilon_{k})^{L}Qn,$

where the second line follows from Lemma 5, the third line is due to the
unitary invariance of the relative entropy, in the fourth line we sequentially
applied the same argument for $L$ times, and the fifth line is from the upper
bound of the relative entropy, which is saturated by pure state $\psi_{\rm
in}$.

$\psi_{\rm
in}$$\mathcal{U}_{1}$$\mathcal{D}_{\epsilon_{k}}$$\mathcal{D}_{\epsilon_{k}}$$\mathcal{D}_{\epsilon_{k}}$$\mathcal{U}_{L}$$\mathcal{D}_{\epsilon_{k}}$$\mathcal{D}_{\epsilon_{k}}$$\mathcal{D}_{\epsilon_{k}}$$q=Q$$\underbrace{\quad\qquad}_{\mathcal{U}_{1}^{\otimes
Q}}$$\underbrace{\qquad}_{\mathcal{D}_{\epsilon_{k}}^{\otimes
Qn}}$$\underbrace{\quad\qquad}_{\mathcal{U}_{L}^{\otimes
Q}}$$\underbrace{\qquad}_{\mathcal{D}_{\epsilon_{k}}^{\otimes Qn}}$$\psi_{\rm
in}$$\mathcal{U}_{1}$$\mathcal{D}_{\epsilon_{k}}$$\mathcal{D}_{\epsilon_{k}}$$\mathcal{D}_{\epsilon_{k}}$$\mathcal{U}_{L}$$\mathcal{D}_{\epsilon_{k}}$$\mathcal{D}_{\epsilon_{k}}$$\mathcal{D}_{\epsilon_{k}}$$q=1$
Figure 6: Noisy layered circuit for the $k^{\mathrm{th}}$ experiment under
local depolarizing noise $\mathcal{D}_{\epsilon_{k}}$. Each experiment
contains $Q$ copies of the noisy circuit.

Using (64), we can put a further bound on (61) as

$\displaystyle\leq\sqrt{2\ln 2}\sqrt{Qn}\sum_{k=1}^{K}(1-\epsilon_{k})^{L/2}$
(65) $\displaystyle\leq\sqrt{2\ln 2}\sqrt{Qn}K\,(1-\epsilon_{\min})^{L/2},$

where $\epsilon_{\min}\coloneqq\min_{k}\epsilon_{k}$. This evaluates the lower
bound of (57) as

$\displaystyle\Delta e_{\max}$ $\displaystyle\geq\max_{\psi_{\rm in},\phi_{\rm
in}}\frac{D_{\operatorname{tr}}(\psi_{\rm in},\phi_{\rm
in})-2b_{\max}}{\sqrt{2\ln
2}\sqrt{Qn}\,K}\left(\frac{1}{1-\epsilon_{\min}}\right)^{L/2}.$ (66)

Noting $\max_{\psi_{\rm in},\phi_{\rm in}}D_{\operatorname{tr}}(\psi_{\rm
in},\phi_{\rm in})=1$ concludes the proof. ∎