Yihui Quek

Daniel Stilck França

Sumeet Khatri

Johannes Jakob Meyer

Jens Eisert

Exponentially tighter bounds on limitations of quantum error mitigation

Quantum error mitigation has been proposed as a means to combat unwanted and unavoidable errors in near-term quantum computing by classically post-processing outcomes of multiple quantum circuits. It does so in a fashion that requires no or few additional quantum resources, in contrast to fault-tolerant schemes that come along with heavy overheads. Error mitigation leads to noise reduction in small schemes of quantum computation. In this work, however, we identify strong limitations to the degree to which quantum noise can be effectively 'undone' for larger system sizes. We start out by presenting a formal framework that rigorously encapsulates large classes of meaningful and practically applied schemes for quantum error mitigation, including virtual distillation, Clifford data regression, zero-noise extrapolation and probabilistic error cancellation. With the framework in place, our technical contribution is to construct families of random circuits that are highly sensitive to noise, in the sense that even at log log(n) depth, a whisker beyond constant, quantum noise is seen to super-exponentially rapidly scramble their output into the maximally-mixed state.

Our results exponentially tighten arguments that have been used in the literature for error mitigation, but they go beyond that: with modifications, our arguments can be applied to kernel estimation for quantum machine learning or to compute the depth at which barren plateaus emerge, implying that the scrambling due to noise kicks in at exponentially smaller depths than thought in prior works. Finally, our results also say that a noisy device must be sampled exponentially-many times (in the number of gates in the light-cone of the observable) to estimate an expectation value of an observable. There are classical algorithms that exhibit the same scaling in complexity. While improvements in quantum hardware will push noise levels down, if error mitigation is used, ultimately this can only lead to an exponential time algorithm with a better exponent when compared with classical algorithms, putting up a strong obstruction to the hope for exponential quantum speedups in this setting.

CONTENTS

I. Motivation and overview

A. Our results B. Consequences of our results 1. Loss of quantum advantage at log log n depth 2. Extending previous distinguishability bounds for unital noise to non-unital noise 3. A construction of random quantum circuits whose distance to the ground state decays exponentially in both depth and system size 4. Consequences for near-term applications 5. No exponential quantum speedups to estimate expectation values on noisy devices C. Related work D. Organization of this work II. Error mitigation: The lay of the land A. Preliminaries: Relative entropy and derived quantities B. Relation to practical error mitigation protocols C. Error mitigation setting D. Relationship between notions of error mitigation 1. Weak error mitigation implies strong error mitigation only with exponentially-many observables III. Conceptual background and contributions A. Preliminaries 1. Pauli operators and their properties

Quantum computers promise to efficiently solve some computational tasks out of reach of classical supercomputers. As early as in the 1980s [START_REF] Feynman | Quantum mechanical computers[END_REF][START_REF] Deutsch | Quantum theory, the Church-Turing principle and the universal quantum computer[END_REF], it was suspected that quantum devices may have computational capabilities that go substantially beyond those of classical Turing machines and hence of classical computers. Shor's algorithm, presented in the mid 1990s, confirmed this suspicion by presenting an efficient quantum algorithm for factoring for which no efficient classical algorithm is known [START_REF] Shor | Algorithms for quantum computation: discrete logarithms and factoring[END_REF]. Since then, the quantum computer has been a hugely inspiring theoretical idea. It also served as a guiding principle in devising actual quantum devices. Soon, it became clear that unwanted interactions with an environment and hence the concomitant decoherence would be the major threat against realizing quantum computers as actual physical devices.

Early fears that decoherence could not be overcome in principle, fortunately, could be proven wrong. The field of quantum error correction presented ideas that show that even if one cannot read out logical quantum information along the way without necessarily perturbing the very same quantum information, one can still correct for errors, in fact arbitrary unknown errors [START_REF] Shor | Scheme for reducing decoherence in quantum computer memory[END_REF][START_REF] Steane | Error correcting codes in quantum theory[END_REF]. This key insight triggered a development that led to the blueprint of what is called the fault-tolerant quantum computer [START_REF] Gottesman | An introduction to quantum error correction and fault-tolerant quantum computation[END_REF][START_REF] Campbell | Roads towards fault-tolerant universal quantum computation[END_REF], a (so far still fictitious) device that allows for arbitrary errors and can still maintain an arbitrarily long and complex quantum computation. That said, known schemes for fault tolerance come along with demanding, possibly prohibitive overheads. In the most popular of fault tolerant schemes, one would think of realizing surface codes, while computation would be performed by so-called lattice surgery and magic state distillation. This means that logical qubits are encoded in a number of physical qubits that is vastly larger [START_REF] Campbell | Roads towards fault-tolerant universal quantum computation[END_REF][START_REF] Litinski | A game of surface codes: Large-scale quantum computing with lattice surgery[END_REF]. For the quantum devices that have been experimentally developed in recent years-extremely impressive devices after all the time of quantum computers being primarily objects of theoretical thoughts-such prescriptions still seem by far out of scope.

For this reason, techniques of quantum error mitigation have been developed [START_REF] Li | Efficient variational quantum simulator incorporating active error minimization[END_REF][START_REF] Temme | Error mitigation for short-depth quantum circuits[END_REF][START_REF] Endo | Practical quantum error mitigation for near-future applications[END_REF][START_REF] Suchsland | Algorithmic error mitigation scheme for current quantum processors[END_REF][START_REF] Kim | Scalable error mitigation for noisy quantum circuits produces competitive expectation values[END_REF][START_REF] Piveteau | Error mitigation for universal gates on encoded qubits[END_REF][START_REF] Russo | Testing platform-independent quantum error mitigation on noisy quantum computers[END_REF][START_REF] Cai | Quantum error mitigation[END_REF], methods that would largely undo quantum errors by classical means, with no or little overheads in physical hardware. This is a compelling idea. Refs. [START_REF] Li | Efficient variational quantum simulator incorporating active error minimization[END_REF][START_REF] Temme | Error mitigation for short-depth quantum circuits[END_REF] on the one hand specifically discuss situations in which a quantum circuit is operated at the minimum possible quantum noise level, repeating the sequence having deliberately increased the physical error rate. Based on the available data, one conceivably can interpolate to the estimate of the zero-error value, presuming that the error sources had scaled proportionately. Ref. [START_REF] Czarnik | Error mitigation with Clifford quantum-circuit data[END_REF] on the other hand have proposed to use a learning-based approach where data from the quantum device is amended with known outputs of quantum circuits that are efficiently simulatable.

But how far can this go?

To what extent can one effectively "undo" quantum noise? Identifying the potential and limitations of this idea seems of pivotal importance to assess the capabilities of near-term quantum computing without quantum error correction. This is no detail: What is at stake is no less than the question whether noise can be effectively canceled in near-term quantum devices. Hence, the elephant in the room is the question to what extent there is scope for quantum computing before the advent of fault tolerant quantum computers. We model the noise acting on C by interleaving its layers with layers of a given noise channel. In general, our model encompasses those error mitigation protocols that modify C on each iteration. In section II B, we will show that this model applies to practical error mitigation protocols such as virtual distillation [START_REF] Huggins | Virtual distillation for quantum error mitigation[END_REF][START_REF] Koczor | Exponential error suppression for near-term quantum devices[END_REF], Clifford data regression (CDR) [START_REF] Czarnik | Error mitigation with Clifford quantum-circuit data[END_REF], zero-noise extrapolation (ZNE) [START_REF] Temme | Error mitigation for short-depth quantum circuits[END_REF] and probabilistic error cancellation (PEC) [START_REF] Temme | Error mitigation for short-depth quantum circuits[END_REF][START_REF] Piveteau | Quasiprobability decompositions with reduced sampling overhead[END_REF][START_REF] Endo | Practical quantum error mitigation for near-future applications[END_REF]. We will study how m, the number of noisy circuit runs, scales with n and D.

In this work, we identify striking and compelling limitations to such prescriptions, by resorting to notions of statistical learning theory. While ideas and methods of quantum error mitigation are surely useful for a class of small noisy quantum devices, we find fundamental limitations of quantum error mitigation by proving lower bounds on its worst-case complexity. Since this work is aimed at providing rigorous bounds, we have to be precise what we exactly mean by a quantum error mitigation protocol. We basically discuss two types of schemes. In the first type, the error mitigation algorithm is provided a classical description of a noiseless circuit and has access to several specimens of the noisy circuit's output state, for some fixed input state. On this output, arbitrary measurements can be performed. The goal of the quantum error mitigation algorithm is to output a collection of expectation values of the noiseless circuit's output state. We refer to this family of algorithms as expectation-value-error mitigation or weak error mitigation. This approach is particularly important in variational quantum circuits [START_REF] Li | Efficient variational quantum simulator incorporating active error minimization[END_REF][START_REF] Mcclean | The theory of variational hybrid quantum-classical algorithms[END_REF], an important family of circuits for near-term quantum devices. In other situations, it is desired to output a sample from the computational basis of the anticipated clean output state. We refer to this family of methods as sample-error mitigation or strong error mitigation. For both families of methods, we prove rigorous limitations. While the language and framework used is that of mathematical physics, to come up with precise statements, it should be clear that it captures practically minded algorithms as they are actually being used in today's laboratories around the word.

Although our results show stark limitations of error mitigation when the depth goes slightly above constant in the worst case, it also invites the question of how to design unitary circuits in such a way that they are more resilient to noise to avoid such behavior. Furthermore, it also motivates the study of whether other models of quantum computation, say dissipative preparation [START_REF] Verstraete | Quantum computation and quantum-state engineering driven by dissipation[END_REF], could offer good and more robust alternatives to the circuit model in the NISQ era. Another interesting question that is raised by our work is what is the most effective way to obtain sample error-mitigation protocols, that is, obtaining samples from the noiseless circuit given access to a noisy device.

A. Our results

To establish the framework, we start off by defining what constitutes 'error mitigation' in the rest of this work. In the literature, the term 'error mitigation' has been used to describe protocols that reduce the unwanted effect of noise on a quantum circuit by measuring it and classically post-processing the results. At its core, an error mitigation algorithm is one that converts noisy quantum states to a classical representation of the noiseless quantum state. The appropriate representation varies: error mitigation is often appended after a quantum algorithm, to revert its outputs to their noiseless version, so the error mitigation should output the desired output of the quantum 'outer loop' into which it is inserted; see Fig. 1 for a schematic depiction.

In slightly more detail, let us consider the following problem, where σ and σ denote the noiseless and noisy circuit's output state respectively and C and C denote the noiseless circuit and noisy circuit we wish to run, respectively:

Problem 1 (Error mitigation, informal definition). Given as input:

• Classical descriptions of a noiseless circuit C, some noise map that transforms C to C and a set M = {O i } of observables.

• Copies of σ , and the ability to measure those copies.

Output either:

• Estimates of the expectation values Tr(O i σ) for each O i ∈ M. We call this weak error mitigation; denote the number of copies of σ needed as m EM,weak .

• Samples from a probability distribution which is approximately that associated with measuring σ in the computational basis, i.e., x ∼ Tr(|x x|σ). We call this strong error mitigation; denote the number of copies of σ needed as m EM,strong .

We refer the reader to Definitions 2 and 3 for rigorous definitions of error mitigation algorithms, and to Section II B that shows that lower bounds against this model translate into lower bounds on well-known protocols such as zero-noise extrapolation and probabilistic error cancellation-that, for instance, run C with varying levels of noise, or apply simple quantum post-processing to C, or adapt their classical/quantum post-processing steps based on the output of intermediate measurements.

In this work, we take the perspective that error mitigation can be cast a statistical inference problem on quantum states-where 'statistical inference' is an umbrella term for problems that deal with identifying underlying parameters of an underlying distribution based on (possibly corrupted) samples. In this view, the underlying distribution in error mitigation comes from the noiseless state, and the samples are those from measuring the noisy state. Moreover, 'good' error mitigation should act as an effective denoiser, allowing one to distinguish one state from another, even if the states can only be accessed by measuring their noisy versions. This motivates us to consider the following problem: Problem 2 (Noisy state discrimination (informal)). Given as input:

• Classical descriptions of a set of n-qubit states S = {ρ 0 , ρ 1 , . . . , ρ N }, a noiseless circuit C, and some noise map that transforms C to C .

• m dist copies of an unknown C (ρ i ) for i ∈ {0, . . . , N } and the ability to measure those copies.

Output: î ∈ {0, . . . , N } such that î = i ("success") with high probability.

A central observation in this work is that noisy state discrimination for a particular choice of S and C reduces to weak error mitigation. Therefore if it is known that at least a certain number of copies of the noisy state are needed for successful discrimination for that choice of S and C (solving Problem 2), then at least the same number of copies are needed for successful weak error mitigation (solving Problem 1). We use the generalized Fano method for multiple hypothesis testing to provide the aforementioned information-theoretic lower bound for noisy state discrimination. The implication for error mitigation is encapsulated in the following central lemma:

Lemma 1 (Central lemma). Let P i be the distribution over the outputs of an algorithm A for noisy state discrimination (Problem 2) when the unknown state is C (ρ i ). Let us define α as an upper-bound to the following quantity for N ≥ 2:

1 N + 1 N k=0 D(P k P N ) ≤ log(N ) • α, (1)
where D(• •) is the (classical) relative entropy. Then A succeeds with probability at most 1α. Moreover, there is a set of instances of Problem 2, such that an algorithm for weak error mitigation (Problem 1) suffices to solve these instances. This implies that

m EM,weak ≥ m dist (2)
This lemma implies an immediate lower bound on the number of copies m dist required to ensure a constant probability of success in Problem 2: Namely, the number required for α (generically a function of the number n of qubits, the depth D of the circuit, and m dist ) to be a constant.

Proof Sketch. The bound on the probability of success originates from Ref. [START_REF] Tsybakov | Introduction to non-parametric estimation[END_REF] (Corollary 2.6). We refer the reader to Lemma 8 for an extended statement. We now prove the reduction, i.e., Inequality [START_REF] Deutsch | Quantum theory, the Church-Turing principle and the universal quantum computer[END_REF], by exhibiting the aforementioned set of instances. In the setting of noisy state discrimination (Problem 2), let the set S consist of ρ N := I/2 n , the maximally-mixed state; and for x ∈ {0, 1} n , ρ x := |x x|. Consider then solving Problem 1 (weak EM) with the observables M = {C † (Z i )} i∈[n] , and note that such a solution consists in estimates of the expectation values on the noiseless state, Tr(Z i ρ x ). If the unknown state had been σ = C (ρ x ) for x ∈ {0, 1} n , then Tr(ρ x Z i ) = 2x i -1; while if the unknown state had been σ = C (ρ N ), Tr(ρ N Z i ) = 0 ∀i ∈ [n]. The output of Problem 1 thus completely identifies the label of the state, i, thus solving Problem 2.

In words, the quantity (N + 1) -1 N k=0 D(P k P N ) can be understood as a sort of 'average distance' between the noisy states C (ρ k ) and the maximally-mixed state (one application of data-processing suffices to see this). This quantity is central to our techniques. The novelty of our results hinges on controlling this quantity precisely, using properties of quantum relative entropies, unital and non-unital quantum noise and Clifford 2-designs to construct C that yields small values of α.

With this perspective, we are able to establish fundamental information-theoretic limits on error mitigation. Specifically, we are able to answer the following questions:

How many noisy copies of σ are required for mitigating depolarizing noise? One might expect that this number-the sample complexity of error mitigation-should scale in the complexity of the circuit, C and the amount of noise affecting it. Indeed, existing error mitigation protocols require a number of samples that scales exponentially in the number of gates in the light-cone of the observable of interest, with the exponent depending on the noise levels [START_REF] Endo | Practical quantum error mitigation for near-future applications[END_REF]. Thus, it is natural to ask if such a scaling is unavoidable or one could hope for better protocols.

We start off by considering the complexity of mitigating circuits affected by local depolarizing noise and arbitary unitary circuits. That is, denoting the noiseless circuit by C, the noise channel by N , and the noisy output state of the circuit by σ C,N , we obtain the following statement, which has many basic features of our main results:

Theorem 1 (Appetizer: mitigating depolarizing noise). Let A be a weak error mitigation algorithm that mitigates the errors in a D-layer quantum circuit C affected by local depolarizing noise N of parameter p. A requires at least p -Ω(D) copies of σ C,N .

We refer readers to Theorem 8 for the full statement. Our proof uses the relation to noisy state distinguishability and various properties of the quantum relative entropy to compute α in Eq. ( 1). The idea of studying the rate of convergence of a circuit's output state to the maximally-mixed state is not new: fast convergence is disastrous for error mitigation [START_REF] Takagi | Fundamental limits of quantum error mitigation[END_REF][START_REF] Takagi | Universal sample lower bounds for quantum error mitigation[END_REF][START_REF] Palma | Limitations of variational quantum algorithms: a quantum optimal transport approach[END_REF][START_REF] Wang | Can error mitigation improve trainability of noisy variational quantum algorithms?[END_REF], kernel estimation [START_REF] Thanasilp | Exponential concentration and untrainability in quantum kernel methods[END_REF] in quantum machine learning, as well as the depth at which quantum advantage from sampling noisy random quantum circuits [START_REF] Deshpande | Tight bounds on the convergence of noisy random circuits to the uniform distribution[END_REF] or variational quantum algorithms [START_REF] Palma | Limitations of variational quantum algorithms: a quantum optimal transport approach[END_REF][START_REF] Stilck Franca | Limitations of optimization algorithms on noisy quantum devices[END_REF][START_REF] Wang | Noise-induced barren plateaus in variational quantum algorithms[END_REF] can obtained. However, these results a la Theorem 1 share the common feature that they are only able to show an exponential-in-depth contraction of the circuit's output state towards the maximally-mixed state and only show that the distance to the maximally mixed state goes below constant order at logarithmic depth. But we are now able to show that they are not tight in general.

Theorem 2 (Mitigating depolarizing noise requires exponential-in-n, D samples). Let A be a weak error mitigation algorithm that mitigates the errors in an n-qubit, D-layer quantum circuit C affected by local depolarizing noise N of parameter p. For some parameter s > 0 and depths D ≥ Ω(log 2 (n/s)), A requires as input at least s -1 p -Ω(n D/s) copies of σ C,N in the worst case.

We refer readers to Theorem 10 for the full statement. To prove this bound, this time we engineer a family of circuits C that converge very fast to the maximally mixed state under noise. This is our technical contribution. By picking, e.g., the parameter s = Ω(n/ log 2 (n)), we see that even at depths D = poly log log(n), error mitigation requires a number of samples that is super-polynomial in n. Setting s = O(1), we see that our construction shows that at poly-logarithmic depth already an exponential number of samples is required to perform error mitigation. The circuit construction used to prove this result builds on a construction by Ref. [START_REF] Cleve | Near-linear constructions of exact unitary 2-designs[END_REF] that uses 2-qubit Clifford gates to obtain a 2-design in short depth. While this construction requires all-to-all connectivity, we show that for circuits on a d dimensional lattice the same effects kick in at depths Õ(n 1/d ), which is the minimal depth required to ensure that all qubits have a lightcone proportional to the system's size. Thus, these constructions showcase that, in general, error mitigation protocols will indeed require a number of samples that grows exponentially with the number of gates in the light-cone of observables.

How many noisy copies of σ are required for mitigating non-unital noise? Our previous bounds relied critically on the structure of depolarizing noise-namely, the fact that a depolarizing noise channel can be expressed as a linear combination of Pauli noise channels. Moving beyond the toy model of depolarizing noise, we are also able to show sample complexity bounds for circuits affected by non-unital noise in another simplified setting. We show that also for non-unital noise, whenever a family of circuits is highly entangling, which we model through the assumption that it forms a 2-design, mitigating local noise typically requires a number of samples that is exponential both in the number of channel applications and number of qubits.

Theorem 3 (Mitigating non-unital noise also requires exponential-in-n, D samples). Let A be a weak error mitigation algorithm that mitigates the errors in an n-qubit, -layer quantum circuit C affected by non-unital product noise N = ⊗ n i=1 N i , such that the noisy circuit takes the form T D = t=1 N • U t , where U t are drawn independently from a 2-design. Then, in expectation, A requires as input at least c -Ω(n ) copies of σ C,N for some constant c that depends on the quantum channel N .

The reader may refer to Theorem 13 for the full statement. The proof of this statement is based on computing the expected value of the overlap of two quantum states after we apply a unitary stemming from a 2-design followed by a noisy channel. From that, we obtain a formula for the expected overlap after D uses that only depends on the initial overlap and constants that depend on the noisy channel. From these computations we can then infer the expected Hilbert Schmidt distance between two inputs of the noisy circuits and use it to upper-bound the trace distance.

While our model of only applying local noise after a (global) unitary is simplified, to our knowledge this is the first result to study error mitigation under non-unital noise beyond the setting of the variational algorithms studied in Ref. [START_REF] Palma | Limitations of variational quantum algorithms: a quantum optimal transport approach[END_REF]. With Theorem 3, we expect our results under depolarizing noise to also transfer to the non-unital case: as long as the underlying noisy circuit is highly entangling and errors are not corrected, the cost of error mitigation is exponential in the depth and the number of qubits.

Theorems 1, 2, 3 were proven in the setting of weak error mitigation, assuming the error mitigation algorithm does not use knowledge of the input state to the circuit. While this is the setting most often used in practice, it does not cover all proposals in the literature. We now ask if our results can be extended to close variants of this setting which are also practically relevant.

How does fixing the input state change the picture? Our definition of error mitigation enables us to derive strong sample complexity lower bounds using tools from statistical inference, but it comes at the cost of requiring that error mitigation does not use any information about the input state to the noisy circuit-hence that it is input-state agnostic. Does lifting this restriction-thereby including input-state aware mitigation protocols-change the picture significantly? A first observation is that now, we can no longer rule out the possibility of successful error mitigation with sub-exponential worst-case sample complexity-simply because classical simulation with no resort to the noisy quantum device at all is a valid error mitigation algorithm that takes zero samples. However, we prove that an error mitigation algorithm that makes use of a noisy quantum device must use exponentially many copies of the noisy state to produce an output meaningfully different from a procedure which does not invoke the quantum device: Theorem 4 (Resource cost of successful error mitigation). A successful weak error mitigation algorithm A must use m = c O(nD) copies of the noisy output state σ in the worst case or there there exists an equivalent algorithm A with purely classical inputs such that the output of A is indistinguishable from the output of A.

For the full statement, see Theorem 9. In this way, we show that our constructions apply both to the input state-agnostic and input state-aware setting, with, however, different implications. Does strong error mitigation imply weak error mitigation, or vice versa? We also study the relationship between the two types of error mitigation algorithms we have defined (weak and strong). We ask if the output of one is sufficient to obtain the output of the other. One direction of this question is easy to answer-classically, samples of a probability distribution suffice to estimate expectation values of bounded functions. The quantum generalization of this is that for local observables, strong error mitigation implies weak error mitigation. However, in some cases, weak error mitigation of noisy circuits does not quite achieve the algorithmic goal: for instance in solving hard combinatorial optimization problems, at this point almost a canonical proposed application of noisy quantum devices, a class that includes the famous quantum approximate optimization algorithm (QAOA) [START_REF] Mcclean | The theory of variational hybrid quantum-classical algorithms[END_REF][START_REF] Farhi | A quantum approximate optimization algorithm[END_REF][START_REF] Zhou | Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near-term devices[END_REF]. In that case, one is not only necessarily interested in the optimal value of the cost function (which one could obtain through weak error mitigation), but also in an assignment that achieves that value (which could be obtained through strong error mitigation). This then motivates the question if it is possible to obtain strong error mitigation (i.e., samples) from weak error mitigation (i.e., expectation values). We give a partial negative answer that rules out certain types of protocols: Theorem 5 ((Informal statement) Exponentially-many observables (in the same eigenbasis) are needed to output samples from the same basis). Suppose we have a weak error mitigation algorithm that, given a set of observables M = {O i } i in the same eigenbasis, outputs their expectation value estimates {ô i }. In general, at least exp(n)-many distinct ôi s must be queried by any algorithm that takes as input the {ô i } and outputs samples from their eigenbasis.

We refer readers to Theorem 7 for the full statement. The proof of this statement takes the perspective of expectation value estimates as statistical queries [START_REF] Feldman | A general characterization of the statistical query complexity[END_REF][START_REF] Reyzin | Statistical queries and statistical algorithms: Foundations and applications[END_REF][START_REF] Blum | Weakly learning DNF and characterizing statistical query learning using Fourier analysis[END_REF], and leverages existing results on optimality guarantees of hypothesis selection [START_REF] Yatracos | Rates of convergence of minimum distance estimators and Kolmogorov's entropy[END_REF] and on the statistical query hardness of learning a class of distributions known as PARITIES.

B. Consequences of our results

Loss of quantum advantage at log log n depth

In the course of proving Theorem 2, we prove the existence of very rapidly mixing circuits: circuits whose output states converge exponentially fast, in both number of qubits (n) and circuit depth (D), to the maximally-mixed state. The idea of studying the rate of convergence (according to various distance measures) of a circuit's output state to the maximally-mixed state is not new: fast convergence is disastrous for error mitigation [START_REF] Takagi | Fundamental limits of quantum error mitigation[END_REF][START_REF] Takagi | Universal sample lower bounds for quantum error mitigation[END_REF][START_REF] Palma | Limitations of variational quantum algorithms: a quantum optimal transport approach[END_REF][START_REF] Wang | Can error mitigation improve trainability of noisy variational quantum algorithms?[END_REF], kernel estimation [START_REF] Thanasilp | Exponential concentration and untrainability in quantum kernel methods[END_REF] in quantum machine learning, as well as the depth at which quantum advantage from sampling noisy random quantum circuits [START_REF] Deshpande | Tight bounds on the convergence of noisy random circuits to the uniform distribution[END_REF] or variational quantum algorithms [START_REF] Palma | Limitations of variational quantum algorithms: a quantum optimal transport approach[END_REF][START_REF] Stilck Franca | Limitations of optimization algorithms on noisy quantum devices[END_REF][START_REF] Wang | Noise-induced barren plateaus in variational quantum algorithms[END_REF] can obtained. However, these results share the common feature that they are only able to show an exponential-in-depth contraction of the circuit's output state towards the maximally-mixed state and only show that the distance to the maximally mixed state goes below constant order at logarithmic depth. Furthermore, one can show that such results are tight for trivial circuits consisting solely of the identity gate.

We point out that the applications mentioned above are all intended to be run on noisy intermediate-scale quantum (NISQ) processors. The quantum circuits employed in these applications are shallow, which means that their depth scales like d = O(log(n)), implying that their claimed rate of convergence is inverse polynomial in n. Our results thus imply an exponentially-faster rate of convergence than previous thought. In fact, a variation of our main result shows that even at log log(n) depth, increasing the number of qubits already brings about a superexponential drop in distinguishability from the maximally-mixed state, with all the above-mentioned attendant implications.

The consequence of this is two-fold: Firstly, we open up a new research direction: how does the amount of entanglement generated by a quantum circuit relate to noise sensitivity? Indeed our circuit construction comprises highly-entangling gates, showcasing the intuition that such circuits are exponentially more sensitive to noise than are general circuits. Secondly, and more pragmatically, we now have quantum circuits that converge to the uniform distribution superpolynomially fast even at log log(n) depth, implying that for all the above applications (robustness to errors, kernel estimation, random circuit sampling, variational quantum optimization) quantum advantage is lost exponentially earlier than originally anticipated.

Extending previous distinguishability bounds for unital noise to non-unital noise

In addition, all of the above references can only show exponential convergence under the assumption that the quantum circuit is affected by unital noise. In our work, we go one step further and establish results for a toy model of circuits affected by non-unital noise interspersed by global 2-designs in Section V. We show that even when the noise is non-unital, we are still able to obtain a decay in distinguishability between different inputs that is exponential in both the depth and the number of qubits. Such an extension is important because many physically relevant noise models, such as amplitude damping, are not unital. Our toy model illustrates that as long as the circuit is entangling enough the decay in distinguishability will be exponential in number of qubits.

3. A construction of random quantum circuits whose distance to the ground state decays exponentially in both depth and system size

Additionally, in order to prove Theorem 2, we do not just construct a single circuit, but a random ensemble of circuits. We are able to prove that, on expectation, their relative entropy from the maximally-mixed state displays the stated exponential decay. A result with a particularly close setting to this one is that of Ref. [START_REF] Deshpande | Tight bounds on the convergence of noisy random circuits to the uniform distribution[END_REF], which has shown that on expectation, the total variation distance between a noisy random quantum circuit output distribution D and the uniform distribution decays exponentially in depth only, that is

E B [ D -U T V ] = Ω(exp(-CD)) ( 3
)
where B is an ensemble of random quantum circuits that differs from the one we consider. Indeed, the authors of [START_REF] Deshpande | Tight bounds on the convergence of noisy random circuits to the uniform distribution[END_REF] consider the model of applying uniformly random 2 qubit Clifford gates at each step, whereas we consider more structured random circuits that mix faster. Let us quickly give an (over)simplified summary of the proof of Eq. ( 3). Suppose for simplicity that we are actually considering an ensemble of random Clifford circuits. A constant fraction of Clifford gates acting on 2 qubits are a product of 1 qubit gates. Thus, at each step there is a constant probability q > 0 that the gate we pick to act on qubit 1 is product. As the gates at different layers are independent, at depth D with probability at least q D the first qubit of the system will be in a product state with the rest. And in that case the effect of the noise on that qubit cannot depend on the system's size. Thus, we see that in some sense the argument relies in conditioning on the circuit not being too entangling. However, our examples show that if the circuits are picked from a random ensemble that is highly entangling, then the effect of the noise is much more pronounced and the decay can also depend on the system's size.

Consequences for near-term applications

It is hoped that applying currently available noise near-term quantum devices to computational problems can bring forth some sort of quantum advantage before the era of quantum error correction and fault-tolerance is reached. Error mitigation is touted as a means towards this end. However, our results further strengthen already known obstructions for these methods.

When optimizing the energy of a Hamiltonian, the outputs of noisy quantum circuits concentrate strongly [START_REF] Palma | Limitations of variational quantum algorithms: a quantum optimal transport approach[END_REF][START_REF] Stilck Franca | Limitations of optimization algorithms on noisy quantum devices[END_REF] which causes any possibility of quantum advantage to be lost when the depth exceeds Ω(p -1 ), an argument that follows a similar route as our work. Our contributions show that this generic bound can be loose in the worst case where a system size dependent error probability p = O((nD) -1 ) is required to ensure potentially good solutions. These arguments go hand in hand with the fact that any circuit that aims at preparing the ground state has to have at least logarithmic depth for important classes of local Hamiltonians [START_REF] Palma | Limitations of variational quantum algorithms: a quantum optimal transport approach[END_REF][START_REF] Bravyi | Obstacles to variational quantum optimization from symmetry protection[END_REF][START_REF] Farhi | The quantum approximate optimization algorithm needs to see the whole graph: Worst case examples[END_REF][START_REF] Eldar | Local Hamiltonians whose ground states are hard to approximate[END_REF][START_REF] Anshu | NLTS Hamiltonians from good quantum codes[END_REF]. For highly entangled ground states of non-local Hamiltonians, we expect even larger lower bounds on the depth, as entanglement has to be built between distant sites. Building entanglement, however, is also the key of our construction for a system-size dependent decay to the maximally mixed state.

Together these statements imply that noisy variational ground state preparation is mostly a lose-lose proposition: Either the depth is insufficient to reach a good approximation of the ground state or it is so high that noise takes over.

No exponential quantum speedups to estimate expectation values on noisy devices

Having defined the task of estimating the expectation value of a noiseless circuit, the question of successful error mitigation immediately turns into a question about its complexity relative to noisy quantum devices. Our results show that, typically, the number of samples from a noisy device required to estimate the expectation value of the clean circuit will scale exponentially in the number of gates in the light-cone of the observable and therefore rules out the possibility of exponential quantum advantages for this task on noisy devices, as there are classical algorithms that exhibit the same scaling in complexity [START_REF] França | Efficient classical simulation and benchmarking of quantum processes in the Weyl basis[END_REF][START_REF] Rall | Simulation of qubit quantum circuits via Pauli propagation[END_REF][START_REF] Bravyi | Classical algorithms for quantum mean values[END_REF]. As such, one can only hope for better exponents in the worst-case complexity.

C. Related work

As a critical enabler in the IBM road map for near-term quantum computation, error mitigation has been the subject of intense study in the past few years [START_REF] Li | Efficient variational quantum simulator incorporating active error minimization[END_REF][START_REF] Temme | Error mitigation for short-depth quantum circuits[END_REF][START_REF] Endo | Practical quantum error mitigation for near-future applications[END_REF][START_REF] Suchsland | Algorithmic error mitigation scheme for current quantum processors[END_REF][START_REF] Kim | Scalable error mitigation for noisy quantum circuits produces competitive expectation values[END_REF][START_REF] Piveteau | Error mitigation for universal gates on encoded qubits[END_REF][START_REF] Russo | Testing platform-independent quantum error mitigation on noisy quantum computers[END_REF][START_REF] Cai | Quantum error mitigation[END_REF]. Prior art typically falls into two camps: 'go' results, which propose new error mitigation algorithms and (often numerically) study their guarantees, and 'no-go' theorems, which demarcate the resource limitations of these algorithms. In Section II B, we will show that our framework encompasses many 'go' algorithms. While our main results fall into the latter 'no-go' category, they are by no means an island. We will now review other findings in this category. Before mentioning more quantitative arguments identifying limitations of quantum error mitigation, it is worth noting that there is a body of heuristic evidence of instances of quantum error mitigation to perform poorly in certain cases. For example, Ref. [START_REF] Li | Efficient variational quantum simulator incorporating active error minimization[END_REF] discusses limitations of the extrapolation method to the noise-free case being unable to approach the mean of the error-free circuit.

More specifically related to the concrete results of our work, Refs. [START_REF] Takagi | Fundamental limits of quantum error mitigation[END_REF] and [START_REF] Takagi | Universal sample lower bounds for quantum error mitigation[END_REF] also study the sample complexity of weak error mitigation under depolarizing noise. They do not mention strong error mitigation. Similar to us, their bounds are information-theoretic, and arise from considering how noise affects the distinguishability of quantum states. We clarify that their sample complexity bounds do not apply to input state-aware protocols if our metric of success is approximating the expectation value of a set of observables. For these papers implicitly assume knowledge of the noiseless circuit-and with knowledge of the input state on top of that, an error mitigation algorithm could produce expectation value estimates without taking even a single sample, simply by simulating the circuit on the input state, even if it takes an exponential amount of computation. Thus, we need to be a bit more careful when we define in which sense error mitigation is doomed to fail in the case where the observables, noiseless circuit and input state are known to the algorithm.

Ref. [START_REF] Takagi | Universal sample lower bounds for quantum error mitigation[END_REF] consider two desiderata for the error mitigation algorithm: a metric, similar to our Eq. ( 27), that requires the algorithm to be probably-approximately correct on each observable [47]; and the maximum bias/standard deviation of the estimators. While they also study the relative entropy decay to the maximally-mixed state, their ultimate sample complexity lower bound decays exponentially only in the depth D of the circuit-and polynomially in the number of qubits n. By contrast, our sample complexity lower bounds (Theorem 10) decay exponentially in both n and D-indicating that their bounds are exponentially loose. Moreover, we make an incursion into proving our results for non-unital noise models. At the time of writing, Appendix G of Ref. [START_REF] Takagi | Universal sample lower bounds for quantum error mitigation[END_REF], which attempts to do the same, contained an error: Eq. (G6) claims that the channel composed by interleaving the layers of non-unital noise with the layers of the noiseless circuit, contracts towards the fixed point. However, it is unclear how they obtain the stated contraction coefficient, as when the fixed point of the noise is not the identity, one cannot remove the intermediate unitaries to obtain the contraction coefficient.

Ref. [START_REF] Tsubouchi | Universal cost bound of quantum error mitigation based on quantum estimation theory[END_REF] studies weak error mitigation from the perspective of Fisher information. More precisely, the authors show that the quantum Fisher information associated with layered noisy circuits decays exponentially with circuit depth, which thus also lower bounds the variance of any unbiased estimator of expectation values. However, we have our reservations about using estimator variance as a metric of resources required, as it gives a very loose bound on the sample complexity to attain a certain estimation error. Take, for instance, the random variable which is e n with probability e -n/2 , -e n with probability e -n/2 and 0 otherwise. This zero-mean random variable has exponential variance, but with a sub-exponential number of samples, the empirical mean is overwhelmingly likely to be exactly the true mean. Of course, such pathological examples use the fact that the underlying random variables take exponentially large values, but this is also the case the case for some error mitigation protocols.

D. Organization of this work

This work is organized as follows:

• In Section II, we introduce our error mitigation setting as well as two variants of error mitigation that we call weak and strong respectively. We further argue that this setting encompasses many error-mitigation protocols used in practice, including virtual distillation [START_REF] Huggins | Virtual distillation for quantum error mitigation[END_REF][START_REF] Koczor | Exponential error suppression for near-term quantum devices[END_REF], Clifford data regression (CDR) [START_REF] Czarnik | Error mitigation with Clifford quantum-circuit data[END_REF], zero-noise extrapolation (ZNE) [START_REF] Temme | Error mitigation for short-depth quantum circuits[END_REF] and probabilistic error cancellation (PEC) [START_REF] Temme | Error mitigation for short-depth quantum circuits[END_REF][START_REF] Endo | Practical quantum error mitigation for near-future applications[END_REF][START_REF] Piveteau | Quasiprobability decompositions with reduced sampling overhead[END_REF]. While most theoretical analyses of error mitigation have focussed exclusively on the weak error mitigation setting, here we argue with reference to the practical protocols that the strong setting is equally relevant, and we make a first attempt at relating the two settings. We also show that many existing error mitigation protocols fit into the model that we will work with.

• Section III presents our conceptual contribution. Here we prove the 'Appetizer' theorem 8 which studies the limitations of error mitigation under depolarizing noise. While this Appetizer theorem implies a weaker scaling of error mitigation complexity as compared to our main theorems, we elect to start here as the proof already introduces the conceptual 'outer loop' that we will use in the rest of our theorems, namely the application of the generalized Fano's lemma to relate error mitigation to the noisy state discrimination problem.

• In Section IV we present our main theorem (Theorem 10), and fill out the technical 'inner loop' of our argument under depolarizing noise. The proof of Theorem 10 is our first technical contribution: the worst-case circuit ensemble that we construct, which has the property that the relative entropy of its average output state to the maximally-mixed state-and hence error mitigation's sample complexity-scales, in the worst case, exponentially in both n and D. We conclude the section by further refining our results so that they hold for local circuits and even lower depths than before.

• Section V contains our second technical contribution: we extend all our previous conclusions to error mitigation under a new class of noise models, non-unital noise, although under the toy model of local non-unital local noise interspersed by global 2-designs. We arrive at the same conclusions in this toy model, the sample complexity for error mitigation is exponential.

• Finally we conclude with an outlook in Section VI.

II. ERROR MITIGATION: THE LAY OF THE LAND

The aim of an error mitigation procedure is to produce a representation of the output of a noiseless quantum circuit given access to the actual noisy quantum device. Before we formally define different error mitigation tasks, we outline the model for noisy quantum circuits that is used throughout this work. We consider quantum circuits of depth D acting on n qubits. In the quantum channel picture, such circuits take the form

C = C (D) • • • • • C (2) • C (1) (4)
where each C (1) , . . . , C (D) denotes a layer of unitary quantum gates. We will then assume that in the noisy version, a quantum channel will act after each unitary we implement. That is, for such a circuit, we take its noisy version to be

Φ C,N (D) ,•••N (1) = N (D) • C (D) • • • • • N (2)
• C (2) • N (1) • C (1) ,

where N (1) , N (2) , . . . , N (D) are quantum channels that describe the noise.

For simplicity, we will often consider the case in which every layer has an identical noise channel acting on it; in that case we will denote the noisy version of the circuit as Φ C,N , or in cases when the noise channel N can be described by a parameter p, Φ C,p . However, our results extend to the case where the noise is not uniform, or not unital. For pedagogical reasons, our results are initially derived for local depolarizing noise and then extended to other noise models.

A. Preliminaries: Relative entropy and derived quantities

At the heart of many of our technical arguments are notions of relative entropies-measures of distance between two quantum states-and how they contract under noise. We first define distance measures on classical probability distributions. Let R, S be two probability measures on the same support X . It will suffice for our purposes to let X be a finite set.

• Total variation (TV) distance. This is defined as

d T V (R, S) := sup A⊆X |R(A) -S(A)| = 1 2 x∈X |R(x) -S(x)|. (6)
• Kullback-Leibler (KL) divergence, or classical relative entropy. The classical relative entropy is defined as

D(R||S) := x∈X R(x) log R(x) S(x) = E x∼R log R(x) S(x) , (7)
where throughout the manuscript we take log to be base 2.

Now we introduce distance measures on quantum states. The primary such measure we will consider is quantum relative entropy, which can be understood as a quantum generalization of classical KL divergence. For this reason, we will use the same notation, D(• •), for both quantum relative entropy and classical relative entropy.

Let ρ, σ be two quantum states in D(H n ) (though in general these quantities are defined with σ any positive semi-definite operator). We will use the following divergences:

• Relative entropy. If supp(ρ) ⊆ supp(σ), we define the (quantum) relative entropy as

D(ρ σ) := Tr(ρ log ρ) -Tr(ρ log σ). (8)
• Petz-Rényi relative entropy. For a parameter α ∈ (0, 1) ∪ (1, ∞),

D α (ρ σ) := 1 α -1 log Tr ρ α σ 1-α . (9)
In the limit α → ∞, the Petz-Rényi relative entropy reduces to the max-relative entropy,

D ∞ (ρ σ) = D max (ρ σ) := inf {γ : ρ ≤ 2 γ σ} , (10)
while in the limit α → 1, it reduces to the quantum relative entropy, i.e., D(ρ σ).

It will often be illuminating to fix the second argument of the relative entropy to be the maximally mixed state, while putting the state of interest in the first argument of the relative entropy. Relative entropies of this form may even be upper-bounded explicitly in terms of quantities relating to the state of interest, as we now show the following.

Lemma 2 (Purity controls relative entropy to the maximally mixed state). For any ρ on n qubits,

D ρ I 2 n ≤ n + log(Tr(ρ 2 )). ( 11
)
Proof. The statement follows from the fact that relative entropy is upper-bounded by 2-Rényi relative entropy

D 2 (ρ σ) := log Tr ρ 2 σ -1 . (12)
This can be seen from the fact that the Petz-Rényi relative entropies for α ∈ (0, 1)∪(1, ∞) satisfy an ordering property [START_REF] Mosonyi | On the quantum Rényi relative entropies and related capacity formulas[END_REF], i.e.,

for α > β > 0 : D α (ρ σ) ≥ D β (ρ σ), (13)
and

lim α→1 D α (ρ σ) = D(ρ σ). (14)
For any ρ on n qubits and σ the maximally mixed state, we thus have

D ρ I 2 n ≤ D 2 ρ I 2 n = log Tr ρ 2 I 2 n -1 = n + log(Tr(ρ 2 )) (15)
as stated.

B. Relation to practical error mitigation protocols

In this subsection, we list some broad classes of error mitigation protocols that have been proposed in the literature, briefly explain how they work, and describe to what our extent our results apply to them. In all of the following, ω C,N refers to the output state of the circuit affected by noise, while |ψ refers to the output state of the noiseless circuit.

1. Virtual distillation [START_REF] Huggins | Virtual distillation for quantum error mitigation[END_REF][START_REF] Koczor | Exponential error suppression for near-term quantum devices[END_REF]: This protocol takes as input k copies of the noisy circuit output state ω C,N outputs

ω k C,N / Tr{ω k C,N } (instead of |ψ ψ|) with probability Tr{ω k C,N }.
The intention of this is to amplify the dominant eigenvector in the eigen-decomposition of ω C,N , as under some assumptions, this dominant eigenvector has a large overlap with the noiseless output state vector |ψ ψ|.

For circuits affected by unital noise, Ref. [START_REF] Palma | Limitations of variational quantum algorithms: a quantum optimal transport approach[END_REF] has shown that the probability of success of virtual distillation decays exponentially both in the number of qubits and depth of the circuit. Here we will show that the same holds for local non-unital noise for circuits that form a 2-design. As we show in Section V C, after we apply a 2-design followed by one layer of product noise, the purity of the system is already exponentially small in expectation. This allows us to conclude that also the success probability of virtual distillation will be exponentially small. [START_REF] Czarnik | Error mitigation with Clifford quantum-circuit data[END_REF]: One runs classically simulatable circuits, in this case Clifford circuits with finitely many T s, to generate the training pairs (X noisy i , X exact i ) i , which are expectation values of the observable on noisy and noiseless circuits. The noisy expectation values are obtained via running the actual circuits; the noiseless expectation values are obtained by classical simulation. One then makes the ansatz that X noisy i and X exact i , for classes of observables or circuits, are related via some functional relation-Ref. [START_REF] Czarnik | Error mitigation with Clifford quantum-circuit data[END_REF] uses a linear ansatz-and fits the parameters of the ansatz using the training pairs. Let C 1 , . . . , C r be the r distinct Clifford circuits that are run in the process of generating the training data, and suppose each circuit is run g times and measured after each run. Let Train be the algorithm that generates the training data-that is, Train takes in

Clifford data regression (CDR)

ω ⊗g C1,N ⊗ ω ⊗g C2,N ⊗ . . . ω ⊗g Cr,N , (16)
(here we do not specify the input to the circuits used to generate the training data because it is irrelevant), makes a quantum measurement on ω ⊗g C1,N to generate X noisy i and classically simulates it to generate X exact i , for all i. Further, let A be the error mitigation algorithm that takes as input m copies of Φ C,N , the noisy output state of the actual circuit C, and the training data (which is the output of Train), and outputs the expectation values Ô ∈ R m where Ô[i] is the estimate for ψ| O i |ψ . We denote the probability distribution of this algorithm over outputs Ô when the circuit input is |k k| as P k . Then

D(P k P N ) = D A Φ ⊗m C,N ,ρ k ⊗ Train(ω ⊗g C1,N ⊗ ω ⊗g C2,N ⊗ . . . ω ⊗g Cr,N ) A I 2 n ⊗m ⊗ Train(ω ⊗g C1,N ⊗ ω ⊗g C2,N ⊗ . . . ω ⊗g Cr,N ) . ( 17
)
≤ D Φ ⊗m C,N ,ρ k ⊗ Train(ω ⊗g C1,N ⊗ ω ⊗g C2,N ⊗ . . . ω ⊗g Cr,N ) I 2 n ⊗m ⊗ Train(ω ⊗g C1,N ⊗ ω ⊗g C2,N ⊗ . . . ω ⊗g Cr,N ) ≤ mD Φ C,N ,ρ k I 2 n + D Train(ω ⊗g C1,N ⊗ ω ⊗g C2,N ⊗ . . . ω ⊗g Cr,N ) Train(ω ⊗g C1,N ⊗ ω ⊗g C2,N ⊗ . . . ω ⊗g Cr,N ) ≤ mD Φ C,N ,ρ k I 2 n , (18)
where the first inequality follows by data processing and the second follows from the tensorization of relative entropy. Plugging Eq. ( 18) into the Central Lemma (Lemma 1), we then get the desired result.

3. Zero-noise extrapolation (ZNE) [START_REF] Temme | Error mitigation for short-depth quantum circuits[END_REF]: Given the circuit C with noise strength λ, one runs it at n different amplified noise levels c j λ (c j > 1), computes expectation values on each such circuit, and combines the noisy estimates into an estimate for the expectation value without noise. Variations on the theme include considering other noise models and interpolation schemes [START_REF] Endo | Practical quantum error mitigation for near-future applications[END_REF][START_REF] Giurgica-Tiron | Digital zero noise extrapolation for quantum error mitigation[END_REF][START_REF] Cai | Multi-exponential error extrapolation and combining error mitigation techniques for NISQ applications[END_REF].

We comment now on how our results apply to the proposal of Ref. [START_REF] Temme | Error mitigation for short-depth quantum circuits[END_REF]. The extension to other variations of this scheme should be similar. Here, to run a circuit at noise level cλ where c ≥ 1, each gate is run for a time cT , where c = 1 corresponds to the noise rate in the original circuit. Ref. [START_REF] Temme | Error mitigation for short-depth quantum circuits[END_REF] further prescribes that the final estimate should be computed as

Ê = n j=1 γ j Ê(c j λ) , (19)
where n j=0 γ j = 1 and n j=0 γ j c k j = 0 for k = 1, . . . , n. If the evolution of the original circuit is

∂ ∂t ρ = -i[K(t), ρ] + λL(ρ) , (20)
where K(t) is the coherent circuit and L represents the noise we want to mitigate, then stretching all gate times by c has the effect of replacing λ ← cλ for c > 1 in the above equation. In the quantum circuit picture, if we assume that each circuit is acted upon by local depolarizing noise with depolarizing parameter p after each gate, this has the effect of replacing the parameter p ← p c . Let us assume that c is the minimum noise level at which the circuit is run. Indeed, it cannot be assumed that we can pick c arbitrarily small, as in this case error mitigation would not be required. Then, letting P k denote the probability distribution over Ê when the input to the circuit is |k k|, we can make a similar replacement in Theorem 10 to obtain that

1 N + 1 N k=0 D(P k P N ) ≤ p cnD . ( 21
)
The Central Lemma then applies.

4. Probabilistic error cancellation [START_REF] Temme | Error mitigation for short-depth quantum circuits[END_REF][START_REF] Endo | Practical quantum error mitigation for near-future applications[END_REF][START_REF] Piveteau | Quasiprobability decompositions with reduced sampling overhead[END_REF]: In this protocol, one rewrites a noiseless circuit U in terms of a linear combination of noisy circuits F i : U = i a i F i where a i ∈ R could be negative. Similarly, any desired expectation value of interest (of the observable M , say) can be decomposed as the following convex combination:

Tr(M U(•)) = i a i Tr(M F i (•)) = γ i p i sign(a i ) Tr(M F i (•)) . (22)
Then with probability p i , Tr(M F i (•)) is estimated by running the noisy circuit F i g times. This is repeated r times, the results are averaged and the estimate is multiplied by γ.

Our analysis applies here too, because we can model the computation of the desired quantity (the right-hand-side of Eq. ( 22)) with a quantum channel M, as follows: Consider the state

ω ⊗r k = r j=1 i p i |i i| Aj ⊗ (F i (|k k|) ⊗g ) Bj , (23)
and the channel M which consists in 1) Applying j P Aj on this state, where P Aj is a projector on the classical system A j ; 2) On each of the r systems, measuring M ⊗g on B j and averaging the result; 3) Classically averaging the results across the r systems and multiplying by γ.

Then let the output of this channel be denoted by P k , for k ∈ {0, 1} n , while let P N denote M acting on the state

σ ⊗r = r j=1 i p i |i i| Aj ⊗ I 2 n ⊗g Bj . ( 24
)
Then we follow similar steps as before to obtain

D(P k P N ) = D M(ω ⊗r k ) M σ ⊗r ≤ rD (ω k σ) (25) ≤ r i p i D |i i| ⊗ (F i (|k k|) ⊗g ) |i i| ⊗ I 2 n ⊗g = rg i p i D F i (|k k|) I 2 n .
The Central Lemma then applies.

5.

Variable noise Clifford data regression (vnCDR) [START_REF] Lowe | Unified approach to data-driven quantum error mitigation[END_REF]: This work generalizes ZNE and CDR. Given an input circuit, one constructs as similar as possible classically simulatable circuits, i.e., Clifford + const. T , and runs them on different noise levels, as in ZNE. Then, again one performs regression on this data to obtain a correction function (which the authors again take to be a simple linear function). Such protocols are input state-aware, but they can be analyzed using a combination of our previous tools and the framework we propose in Section III C to deal with the input state dependence.

C. Error mitigation setting

The protocols listed in Subsection II B are but a slice of the wealth of error mitigation techniques that have so far been proposed. In this section we aim to unify all of these techniques in introducing the model of error mitigation that we will be using in the rest of this work. As explained in Subsection II B, lower bounds against the model we will introduce imply lower bounds for many of those protocols. We will take the input of an error mitigation protocol to be the following.

Definition 1 (Resources for error mitigation). An error mitigation algorithm predicts properties of the noiseless output state of a quantum circuit C(ρ) given:

• Classical descriptions of C and the noise channel N acting on C.

• (Optional) A classical description of the input state to the circuit, ρ. If the algorithm utilizes this classical description, we call the algorithm input-state aware. If the algorithm doesn't utilize this classical description, we call it input-state agnostic.

• The ability to perform collective quantum measurements on multiple copies of the noisy circuit output state Φ C,N (ρ) (see the remarks below for the case of randomized families of circuits).

We now make several remarks about this definition. Firstly, our goal is to demarcate the information-theoretic limits of error mitigation. This we do by studying the sample complexity of error mitigation in our model-how many copies of the noisy output state are required to achieve the desired error mitigation output-rigorously quantifying how this number scales in the complexity of C and the noise N . We note that sample complexity lower bounds computational complexity, and so lower bounds for sample complexity are also lower bounds for computational complexity.

Secondly, the practical scope of our model is broader than meets the eye. It encompasses even those protocols that run multiple different circuits with varying levels of noise, or take as additional input 'training data' which are pairs of (experimental) noisy and (simulated) noiseless expectation values for different circuits. In this case, we can always identify a representative circuit/noise level out of the class of circuits that may be run; it is this circuit whose parameters will determine the complexity of error mitigation. The reader is referred to the discussion in the Subsection II B for more details.

Thirdly, we start in Section III by proving lower bounds against input-state agnostic protocols, and then in Section III C we extend the results to input-state aware protocols. Input-state agnostic protocols are a natural starting point, because they cannot possibly work by simulating the circuit C, no matter how shallow that circuit is-simply because they do not know the input to the circuit. In fact, many existing error mitigation protocols in the literature are already covered by the input state-agnostic model, because the classical description of the input state is not a parameter in the protocol.

Fourthly, note that we have allowed for the ability to perform arbitrary collective measurements. This requires access to a quantum memory, a nontrivial quantum resource that might be out of reach. Because of this, most error mitigation protocols in the literature do not require this ability. However, our conclusions hold up even against algorithms that have such additional power.

Error mitigation is not an end in itself; typically it is used as the last step in a pipeline to solve some (quantum) computational task. Depending on what kind of task that is, different outputs of the mitigation procedure are required. Arguably, the most popular intended application for near-term quantum computers are variational quantum algorithms [START_REF] Mcclean | The theory of variational hybrid quantum-classical algorithms[END_REF][START_REF] Cerezo | Variational quantum algorithms[END_REF][START_REF] Bharti | Noisy intermediate-scale quantum algorithms[END_REF] where a quantum state is prepared through a parametrized quantum circuit and the parameters are iteratively adjusted to optimize a function L( O 1 , O 2 , . . . ) of expectation values of operators evaluated on said state. The archetypal variational quantum algorithm is the variational quantum eigensolver [START_REF] Peruzzo | A variational eigenvalue solver on a photonic quantum processor[END_REF] where the function

L(|ψ ) = i ψ| O i |ψ = i O i ( 26
)
is the expectation value of a Hamiltonian H = i O i . In this case, the ground state of H yields the solution to the optimization problem, and so the optimized parametrized quantum circuit should ideally prepare a state close to the ground state of H. However, such circuits are noisy and the goal of error mitigation is to correct this. It stands to reason then that an error mitigation protocol should output estimates of the expectation values O i on the state output by the noiseless version of these circuits. We can formally capture this task in the following definition of weak error mitigation. In all of the definitions below, let |ψ = C(ρ) be the state output by the noiseless circuit.

P[|ô i -o i | ≤ for all 1 ≤ i ≤ ] ≥ 1 -δ. ( 27
)
Here the probability in Eq. ( 27) is over the randomness of the error mitigation algorithm. This randomness could come from using classical random bits or from making measurements of the quantum states available as input.

The task of computing expectation values is ubiquitous in near-term quantum computing. Most error mitigation algorithms in the literature address the weak error mitigation task, including all protocols listed in Section II B. However, in some applications, knowing expectation values is not sufficient. In these cases, we would like to represent the strongest possible access, on par with access to the quantum computer, which is sampling of the circuit's output. This leads us to a definition of strong error mitigation: Definition 3 (Strong error mitigation (sample error mitigation)). An ( , δ) strong error mitigation algorithm A with resources as in Definition 1 outputs a bitstring z sampled according to a distribution z ∼ µ such that with probability

1 -δ, d TV (µ, D |ψ ) ≤ , (additive error ) (28)
or alternatively

D |ψ (z) µ(z) ≤ κ for all z ∈ {0, 1} n , (multiplicative error κ) (29)
where D |ψ is the distribution arising from a computational basis measurement of |ψ .

As the strong error mitigation task is more difficult than the weak error mitigation task-as we will show below, strong error mitigation implies weak error mitigation-and weak error mitigation is usually sufficient for near-term applications, there are fewer methods available that achieve this, an example being virtual distillation [START_REF] Huggins | Virtual distillation for quantum error mitigation[END_REF][START_REF] Koczor | Exponential error suppression for near-term quantum devices[END_REF]. The two notions of error are related-κ multiplicative error implies

= 1 - 1 κ (30)
additive error. To see this, note that the multiplicative error requirement can be re-written as

D |ψ (z) µ(z) ≤ κ → D ∞ (D |ψ µ) ≤ log(κ) . (31)
By the monotonicity of relative entropies, we then have

D KL (D |ψ µ) = D 1 (D |ψ µ) ≤ D ∞ (D |ψ µ) ≤ log(κ) . ( 32
)
By the Bretagnolle-Huber inequality [START_REF] Bretagnolle | Estimation des densités : Risque minimax[END_REF], we can then relate this to total variation distance as

d T V (D |ψ , µ) ≤ 1 -exp(-D KL (D |ψ µ)) ≤ 1 - 1 κ . (33)
On the other hand, it is easy to check that additive error does not imply multiplicative error for any setting of the parameters.

The additive-error requirement for strong error mitigation makes intuitive sense when sampling access to the noiseless quantum state is required and it is not important that the samples generated by the error-mitigated algorithm should come from any particular subset of the support. However, this is not the case for some of the near-term quantum algorithms that one might want to error mitigate. Consider for example variational quantum optimization algorithms like the quantum approximate optimization problem [START_REF] Farhi | A quantum approximate optimization algorithm[END_REF], where a diagonal Hamiltonian H encodes a hard combinatorial optimization problem. Here, computational basis states of low energy correspond to approximate solutions of the combinatorial optimization problem. If the noiseless state |ψ has an overlap of O(1/ poly(n)) with the low-energy subspace of H, polynomially many samples from the noiseless distribution D |ψ are sufficient to solve the optimization problem with high probability. And then the same would hold for sampling from an error mitigated distribution with multiplicative error κ = O(1/ poly(n)): such distribution must also have an inverse polynomially small weight on the set of low-energy strings. Such important examples motivate our definition of the multiplicative error mitigation.

D. Relationship between notions of error mitigation

Having established that a comprehensive study of error mitigation must consider both weak and strong versions, we now ask: how are they related? We are particularly interested in understanding if the output of one kind of error mitigation can be used, in polynomial time, to compute the output of another kind of error mitigation. A first observation is that strong error mitigation implies weak error mitigation with local observables. Let A be a strong error mitigation algorithm. Definition 3 requires A to output a sample from the computational basis of the noiseless circuit's output state. However, if O i is a local observable (say a product Pauli observable) and we assume that the cost of strong error mitigation on C does not increase significantly by appending a layer of product unitaries to C, then A can also output samples from the probability distribution associated with measuring C in an eigenbasis of O i . After applying the strong error mitigation procedure to obtain enough clean samples from the eigenbasis of O i , we can estimate the expectation value Tr(O i C(ρ)) empirically to a desired precision, thereby achieving weak error mitigation. One of the main questions asked in this work is whether we can hope for the other direction to hold. That is, whether weak error mitigation protocols can be used to also obtain samples from the noiseless circuit. The remainder of this subsection answers this question.

Weak error mitigation implies strong error mitigation only with exponentially-many observables

Let us now consider the problem of using the outputs of a weak error mitigation algorithm to obtain a strong error mitigation algorithm. That is, what is the minimum number of expectation values required to produce samples from the noiseless circuit? Here we allow arbitrarily complex post-processing steps because our focus is on sample complexity, or fundamental information-theoretic limits. Restricting our focus to bounded-time (i.e., realistic) computations would only further limit the set of protocols under consideration. First note that in the limit of exponentially many error-mitigated expectation values, obtaining a (potentially inefficient) strong error mitigation algorithm is possible. Indeed, suppose we were able to perform weak error mitigation, outputting estimates of all n-qubit Paulis

Tr(C(ρ)P i ) ∀P i ∈ Q n . ( 34
)
up to exponentially small precision. This allows us to perform full tomography on the noiseless output C(ρ) [START_REF] Gross | Quantum state tomography via compressed sensing[END_REF]-if we were allowed to query exponentially-many such expectation values (since there are exponentially many members of Q n ). However, this procedure would clearly be inefficient and likely more costly than just simulating the circuit classically. Thus, the more interesting question is: could there be an algorithm that only needs to see polynomially-many expectation values from the output of weak error-mitigation to obtain strong error mitigation?

We proceed to provide a partial negative answer to this question, showing that there cannot exist such an algorithm if the expectation values are all of observables diagonal in the same eigenbasis. To do so, we showcase an instance of weak error mitigation that provides an explicit counterexample to the conjecture. First, we will need to introduce the notion of a statistical query [START_REF] Kearns | Efficient noise-tolerant learning from statistical queries[END_REF]: Definition 4 (Statistical query). A statistical query is a pair (q, τ ) with

• a function q : {0, 1} n × {0, 1} → {0, 1}.
• τ : a tolerance parameter τ ≥ 0. Now we are ready to define a statistical query oracle.

Definition 5 (Statistical query oracle). Fix an unknown function c : {0, 1} n → {0, 1} and a probability distribution D over the domain {0, 1} n . The statistical query oracle, SQ(q, τ ), when given a statistical query, returns any value in the range as

[E x∼D [q(x, c(x))] -τ, E x∼D [q(x, c(x))] + τ ]. (35)
We will also need to use the observation that the problem of PARITIES on n bits (which we now define) can be solved with poly(n) samples but requires exp(n) statistical queries.

Definition 6 (PARITIES). The class of PARITIES is the set of functions {c

s : {0, 1} n → {0, 1}} s∈{0,1} n where c s (x) = x • s for s ∈ {0, 1} n . ( 36
)
We may define the associated PARITIES distribution P s : {0, 1} n+1 → [0, 1] via

P s (x y) = 2 -n , if y = x • s 0 , else , (37)
where x ∈ {0, 1} n , y ∈ {0, 1}, and the symbol means concatenation. That is, the PARITIES distribution on n + 1 bits corresponding to a secret n-bit-string s, is the distribution which is supported uniformly on those bit-strings whose last bit is the parity of the subset of the first n bits that are indexed by the string s.

There are three important facts about PARITIES distributions that we will use.

1. For every s ∈ {0, 1} n , there exists an n+1-qubit quantum circuit C s that 'encodes' the PARITIES distribution P s , in the following sense: when initialized on the all-0s state, the output state has support only on the computational basis states whose labels are in the support of the distribution P s :

C s |0 ⊗n+1 = 1 √ 2 n x∈{0,1} n |x c s (x) , (38)
for the parity function c s (x) = x • s. This is proven in, for example, Ref. [START_REF] Hinsche | A single t-gate makes distribution learning hard[END_REF].

2. PARITIES are not solvable with sub-exponentially-many statistical queries [START_REF] Blum | Weakly learning DNF and characterizing statistical query learning using Fourier analysis[END_REF] (see Refs. [START_REF] Reyzin | Statistical queries and statistical algorithms: Foundations and applications[END_REF][START_REF] Kanade | Advanced machine learning -Hilary term 2017 7: Statistical query learning[END_REF] for tutorials):

Lemma 3 (SQ-hardness of PARITIES [START_REF] Blum | Weakly learning DNF and characterizing statistical query learning using Fourier analysis[END_REF]). Any algorithm for learning the class of n-bit PARITIES to constant accuracy and probability of success and which makes statistical queries of the form (χ, τ ), where τ ≥ τ 0 for each query, must make Ω(τ 2 0 • 2 n ) queries.

3. We can lower-bound the total variation distance between any two PARITIES distributions as follows:

Lemma 4. For any two s, s ∈ {0, 1} k , d T V (P s , P s ) ≥ 1/2.
Proof. Le Cam's two point method says that the failure probability of any binary hypothesis test Ψ : X → {P, Q} on two distributions P, Q : X → [0, 1] each chosen with probability 1/2, is lower bounded as follows:

min Ψ P error (Ψ) ≥ 1 -d T V (P, Q) 2 . ( 39
)
For any two strings s, s ∈ {0, 1} k , let P = P s and Q = P s . We wish to bound d T V (P s , P s ). To do so we will exhibit a hypothesis test on P s versus P s that has error probability 1/4. Plugging this into Eq. ( 39) yields the desired lower bound on d T V (P s , P s ). A simple test is then as follows: given a string x c drawn from either P s or P s , where c is one bit, we compute the parity of x with s and s . In Case 1, we have x • s = x • s . Then we output s or s uniformly at random. This succeeds with probability 1/2. Otherwise (call this Case 2) x • s = x • s . Then we output whichever string s or s yields the right parity c. This succeeds with probability 1 in distinguishing the two distributions. So the probability of error of the test we have described is simply

P error = P (Case 1)1/2 . ( 40
)
Now let us compute P (Case 1) = 1 -P (Case 2). As the x part of the string is chosen uniformly from {0, 1} n , computing P (Case 2) boils down to computing the number of x's that either satisfy the equations x • s = 0 and x • s = 1 or x • s = 1 and x • s = 0. In both cases, x must satisfy two linearly independent relations. Thus, we conclude that the strings that satisfy x • s = 0 and x • s = 1 form a vector space of dimension n -2, which contains 2 n-2 strings. Thus, the number of strings that satisfy either x • s = 0 and x • s = 1 or x • s = 1 and x • s = 0 is 2 n-1 which is half of all the strings x. Thus, P (Case 2) = P (Case 1) = 1/2, and so the overall

P error = 1/2 * 1/2 = 1/4.
In addition, we will need the notion of hypothesis selection and an algorithm that achieves a good approximation guarantee for it, due to Yatracos [START_REF] Yatracos | Rates of convergence of minimum distance estimators and Kolmogorov's entropy[END_REF]: Theorem 6 (3-proper hypothesis selection). Fix a class of distributions Q = {q 1 , . . . , q k } and , δ > 0. Given O(log |Q|/ 2 ) samples from a target distribution p (which may not be in Q), there is an algorithm to output a distribution q * ∈ Q satisfying

d T V (p, q * ) ≤ 3 min i∈[k] d T V (p, q i ) + ( 41
)
with probability at least 1δ.

Here, the word proper refers to the fact that the output distribution is required to be in Q, a feature that we will require for the argument we are about to make. The connection between expectation values (the output of weak error mitigation) and statistical queries is encapsulated in the following observations (where for b ∈ {0, 1} n ,

Z b := Z b1 ⊗ Z b2 ⊗ • • • ⊗ Z bn ):
Lemma 5 (Weak error mitigation on the circuits C s outputs statistical queries to the PARITIES s distribution). Consider error mitigation on the n+1-qubit PARITIES circuit C s (see Def. 6). That is, let M = {(I+Z b )/2} b∈{0,1} n+1 , and suppose we have a weak error mitigation algorithm A(C s , N , M) that, with probability 1δ, outputs τ -accurate estimates

|ô i -Tr[C s (|0 0| ⊗n+1 )O b )]| < τ for all O b ∈ M . ( 42
)
The outputs ôi are valid responses to statistical queries with tolerance τ for the distribution P s .

The observation that weak error mitigation outputs statistical queries was also made in Ref. [START_REF] Arunachalam | Quantum statistical query learning[END_REF] which introduced the notion of a quantum statistical query (QSQs) in the quantum PAC learning setting. We will come back to this after we state our main theorem.

Proof. We will prove that each τ -accurate expectation value output by A that satisfies Eq. ( 42) takes the form of a response of a statistical query oracle to a statistical query of tolerance τ , by specifying what c, q, D from Definition 5 correspond to. Let us denote the circuit's clean output state vector as

C s |0 n+1 = |ψ = 2 -n/2 x∈{0,1} n |x c s (x) .
Then it is easy to see, from inspecting the basis vectors in the support of |ψ , that the desired expectation values can be rewritten as

Tr(|ψ ψ|(I + Z b )/2) = E z∼Ps [q b (z)] = E x∼Unif{0,1} n [q b (x, c s (x))] , (43)
where q b : {0, 1} n+1 → {0, 1} is defined as

q b (z) = 1 + z|Z b |z 2 . ( 44
)
That is, q = q b , c = c s and D = Unif{0, 1} n .

The re-scaling of the observables Z b is cosmetic; it is merely to obtain a set of observables whose eigenvalues take values in {0, 1} due to the way we have defined statistical queries in Def 5. In a similar fashion, while this lemma is written for the observables Z b , one could write an analogous lemma for observables that are all diagonal in some other common eigenbasis, by simply applying the corresponding basis change at the end of the circuit C s and re-scaling the value of the tolerance parameter τ for the statistical query. This observation will be crucial to the main theorem of this section (Theorem 7), which states that with subexponentially-many expectation values of observables which share the same eigenbasis, weak error mitigation cannot imply strong error mitigation in the worst-case. We now state this more formally:

d T V (p, D |ψ ) ≤ 1/16 , (45)
where D |ψ is the computational basis distribution on |ψ .

After we prove this, we will remark that not even the power to choose the observables adaptively will make it possible to transform a sub-exponential number of expectation values into linearly-many samples.

Proof of Theorem 7. Ref. [START_REF] Hinsche | A single t-gate makes distribution learning hard[END_REF] has shown that there is a class of n-qubit Clifford circuits whose output distributions are exactly the set of PARITIES distributions. Suppose to the contrary that for some circuit C in this class whose output distribution is some P s ∈ PARITIES, there exists some set of observables M with |M| = o(τ 2 • 2 n ) and some algorithm B, which takes as input the estimates ẑi of weak error mitigation up to error τ and outputs O(n) samples from some distribution p such that d T V (p, P s ) ≤ 1/16.

We will show that we can use these samples to solve for the hidden string and thus solve the problem of PARITIES. However, this would imply a contradiction: Recall from Lemma 5 that each expectation value estimate is a statistical query to some distribution from the class of PARITIES, but as stated in Lemma 3, there is no statistical query algorithm to solve PARITIES with o(τ 2 • 2 n ) statistical queries.

In the rest of this proof, we will explain how to use the samples output by the presumed B to solve PARITIES. The key is simply to run the hypothesis selection algorithm of Ref. [START_REF] Yatracos | Rates of convergence of minimum distance estimators and Kolmogorov's entropy[END_REF] (Theorem 6), with the set of candidate hypotheses being the set of all Clifford distributions encoding PARITIES. This algorithm will take as input the O(n) samples from p and by the guarantees of Theorem 6, will output a distribution P s ∈ PARITIES such that

d T V (p, P s ) ≤ 3 min s∈{0,1} n d T V (p, P s) + 1/16 . (46)
Now, consider that by the guarantees of B, 3d T V (p, P s ) + 1/16 = 1/4 and so Eq. ( 46) yields that d T V (p, P s ) < 1/4. But as stated in Lemma 4, for all s, s ,

d T V (P s , P s ) ≥ 1/2 , ( 47
)
and so by the triangle inequality,

arg min s∈{0,1} n d T V (p, P s) = s (48)
i.e., hypothesis selection recovers the hidden string of the PARITIES problem successfully. This implies the contradiction.

Extensions of our proof. We remark that our bound holds against even an adaptive choice of observables in error mitigation because the statistical query hardness of PARITIES holds against an adaptive choice of statistical queries. However, we reiterate a limitation of our result: we can only rule out obtaining strong error mitigation from weak error mitigation with sub-exponentially-many observables whose eigenbasis is the basis we desire to sample from. It is natural to ask if we can lift this restriction. Here, we point out that the discussion in Ref. [START_REF] França | A game of quantum advantage: Linking verification and simulation[END_REF] shows that for 'flat' circuit output distributions, and a specially-crafted set of observables with multiple different eigenbases, only polynomially-many expectation values are needed to obtain a sampler (hence we cannot lift the restriction in general). We could also take a different tack: our proof is based on the hardness of PARITIES from classical statistical queries. As observed by Ref. [START_REF] Arunachalam | Quantum statistical query learning[END_REF], it is also possible to define quantum statistical queries for a given unknown distribution D, and unknown function c, and QSQs generalize classical statistical queries by allowing for observables not diagonal in the eigenbasis defined by c. Hence, if we knew of a problem that was hard for certain classes of quantum statistical queries (in the sense that exponentially-many QSQs are needed to solve them), our proof technique could then be applied to say something about the hardness of obtaining strong error mitigation from weak error mitigation without the restriction mentioned at the beginning of this paragraph. Unfortunately we do not know of any such problems.

III. CONCEPTUAL BACKGROUND AND CONTRIBUTIONS

We first show a basic version of our theorem bounding the sample complexity of error mitigation in a circuit subject to depolarizing noise. This theorem already has all the features of our main results but is weaker, in the sense that we will only be able to show an exponential-in-D dependence of the sample complexity, while our main result improves this to an exponential in both n, D.

A. Preliminaries

Pauli operators and their properties

We denote the single-qubit Pauli operators by I, X, Y, Z. Furthermore, for a = (a 1 , a 2 , . . . , a n ) ∈ {0, 1} n , we let

Z a := Z a1 ⊗ Z a2 ⊗ • • • ⊗ Z an , (49) X a := X a1 ⊗ X a2 ⊗ • • • ⊗ X an , (50)
where

Z ai = I a i = 0, Z a i = 1, (51)
X ai = I a i = 0, X a i = 1. ( 52
)
We then define the Pauli group.

Definition 7 (Pauli group and Pauli weight). Let n ∈ {1, 2, . . . }. The Pauli group P n , by definition, consists of all operators of the form i k X a Z b , where k ∈ {0, 1, 2, 3} and a, b ∈ {0, 1} n . Let Q n := P n /{±1, ±i} be the quotient group that results from disregarding global phases in P n . For every Pauli operator P ∈ Q n , we denote by w(P ) the weight of P , which is the number of qubits on which P acts non-trivially.

In the following Lemma, we mention some basic facts about Pauli operators that we use repeatedly.

Lemma 6 (Properties of Pauli operators). We list some properties of the Pauli group.

1. Trace of products of Paulis.

For n-qubit Paulis P, Q ∈ Q n ,

Tr(P • Q) = 2 n P = Q, 0 otherwise. ( 53
)
2. Pauli basis expansions.

The n-fold Paulis form an orthogonal basis for all Hermitian operators in H ⊗n ; in particular, for a ∈ {0, 1} n ,

|a a| = 1 2 n b∈{0,1} n (-1) a•b Z b , ( 54
)
where a • b = a 1 b 1 + a 2 b 2 + • • • + a n b n (mod 2).
D (d) p (M ) := pM + (1 -p) Tr[M ] I d , p ∈ [-1/(d 2 -1), 1]. ( 55
)
When the superscript for the dimension is omitted, we implicitly refer to the single-qubit depolarizing channel (with d = 2):

D p (M ) := D (2) p (M ) = pM + (1 -p) Tr[M ] I 2 , p ∈ [-1/3, 1]. ( 56
)
We note that the single-qubit depolarizing channel has an alternate representation in terms of the Pauli operators

D p (ρ) = q X XρX + q Y Y ρY + q Z ZρZ + q I ρ, (57)
where

q X = q Y = q Z = 1 -p 4 ( 58
)
and

q I = 1 + 3p 4 . (59)

A

Weak error mitigation Lemma 8 (Corollary 2.6 of Ref. [START_REF] Tsybakov | Introduction to non-parametric estimation[END_REF]). Let P 0 , . . . , P N be probability measures on some state space X such that

ρ i ∈ {|i⟩⟨i|} 2 n -1 i=0 ∪ I/2 n C ′ (ρ i ) ⊗m Classical descriptions of N , C. Classical description of M = {O j } n j=1 , O j := C † (Z j ).

Estimates of

Tr(O j C(ρ i )) = Tr(Z j ρ i ), j ∈ {1,
1 N + 1 N k=0 D(P k P 0 ) ≤ α log(N ) ( 66
)
for 0 < α < 1. Then the minimum average probability of error over tests ψ : X → {0, 1, . . . , N } that distinguish the probability distributions P 0 , . . . , P N which we define as pe,N := inf

ψ 1 N + 1 N j=0 P j (ψ = j) (67)
satisfies:

pe,N ≥ log(N + 1) -log(2) log(N ) -α. (68)
Let us explain what this Lemma implies about the sample complexity of state discrimination in the presence of noise (Problem 3). Intuitively, dialing up the noise on the circuit C makes the various output states Φ C,N (ρ i ) less distinguishable from each other-and so, more copies of Φ C,N (ρ i ) must be taken to determine the true identity of the input state. This Lemma formalizes this intuition. For let P 0 , . . . , P N be distributions over the output of the m-copy distinguisher in Problem 3 when the true state is ρ 0 . . . ρ N , respectively. One can then show that, for N being depolarizing noise of parameter p on generic depth-D circuits, the average distance of P 1 , . . . , P N to P 0 (the left-hand-side of (66)) scales as α log(N ) = p 2D log(N ). To get a constant probability of error in [START_REF] Hirche | On contraction coefficients, partial orders and approximation of capacities for quantum channels[END_REF], α must be constant. In order for α to be constant, one needs to choose m scaling as p -2D .

We can go one step further and use Lemma 8 to bound the performance of error mitigation. The proof proceeds according to the following two basic steps:

1. Embed an error mitigation protocol into a solver for a state discrimination problem. This means, we identify a state discrimination problem such that an error mitigation algorithm can be transformed, with no additional copies required, into a distinguisher that solves the state discrimination problem.

2. Compute Fano's lower bound for the number of copies needed for the state discrimination problem.

More formally, we now state and prove the following theorem:

Theorem 8 (Appetizer: Error mitigation under depolarizing noise requires exponential-in-depth samples). Let A be an input state-agnostic weak error mitigation algorithm (see Definition 2) that takes as input m noisy copies Φ C,p (ρ). Suppose that for any circuit C acted upon by depolarizing noise of parameter p, and any set of observables

M = {O i } i∈[n] ,
A is able to produce estimates {ô i } i∈[n] such that with probability at least 1δ,

|ô i -Tr [O i C(ρ)]| ≤ for all i ∈ [n]. ( 69
)
Then there exists an observable set M and a set of input states ρ such that, as long as < 1/2, the number of noisy copies, m, needed by A, is lower-bounded as

m = Ω(p -2D ) ( 70
)
for any circuit C on n qubits of depth D.

After we prove this theorem, we remark on extensions of our proof to EM protocols with other types of input state access, including those protocols that are input state-aware.

Proof of Theorem 8. Let A be an input state-agnostic weak error mitigation algorithm and consider the observable set M = {C † (Z j )} n j=1 where Z j is the Pauli Z acting on qubit j. For ease of notation, we will denote by ẑj the estimate of Tr[C † (Z j )C(ρ i )]. We are going to identify a set S of states (which is also the set of states referenced in the Theorem), such that to solve Problem 3 when the unknown state is chosen from S, it suffices to run A on copies of the unknown state and then do simple post-processing.

a.

Step 1: A noisy state identification problem that can be solved by weak error mitigation. Consider choosing the unknown state ρ i , i ∈ [2 n + 1] in Problem 3 from the following N + 1 = 2 n + 1 options:

• ρ N = I/2 n , the maximally-mixed state. If this option is chosen, say we are in Case 1.

• {ρ x := |x x|} x∈{0,1} n . If one of these options is chosen, say we are in Case 2.

(We emphasize that the state discrimination algorithm must output i, the label of the state, rather than simply decide whether it is in Case 1 or 2.) We will now show that Problem 3 can be solved with access to an error mitigation algorithm A. First suppose hypothetically that the error mitigation algorithm were perfect; i.e., when given m copies of Φ C,N (ρ i ), A outputs estimates ẑj that are exact:

ẑj = Tr[C † (Z j )C(ρ i )] = Tr[Z j ρ i ] ∀j ∈ [n] . (71)
(Later we will show that the analysis below goes through if we assume only approximate estimates.) But consider that, in Case 1, where ρ i is ρ N = I/2 n , the true expected value of the observables is

Tr[Z j I/2 n ] = 0 ∀j ∈ [n] (72)
i.e., a perfect error mitigation algorithm should estimate ẑj = 0 for every observable.

On the other hand, in Case 2, when ρ i = ρ x for some x = (x 1 , x 2 , . . . , x n ) ∈ {0, 1} n , the true expected value of the observables is

Tr[|x x|Z j ] = 2x j -1 ∀j ∈ [n] , (73)
i.e., a perfect error mitigation algorithm would output the estimate ẑj = 1 if x j = 1 and ẑj = -1 if x j = 0. Hence, if the error mitigation algorithm were perfect, one could perfectly distinguish Case 1 and Case 2; furthermore in the latter case, concatenating the set {(1 + ẑj )/2} n j=1 results in an n-bit string corresponding to x = (x 1 , x 2 , . . . , x n ), the label of the actual input state. A perfect error mitigation algorithm thus solves the state identification problem perfectly.

Now we argue that state identification can still be solved by an error mitigation algorithm that returns only approximate estimates. By assumption, with probability 1δ, the estimates are accurate up to additive error . As long as < 1/2, we find

|ẑ j -Tr[ρ i Z j ]| ≤ 1/2 ∀j ∈ [n] , (74)
(c.f. Eq. ( 71)). The true values, of course, remain the same: Eq. ( 72) and Eq. ( 73) still hold in Case 1 and Case 2 respectively. In particular, let ẑ = (ẑ 1 , ẑ2 , . . . , ẑn ) be the estimates produced by A when the input state is ρ N = I/2 n (Case 1) and let ẑx = (ẑ 1,x , ẑ2,x , . . . , ẑn,x ) be the estimates produced by A when the input state is ρ x = |x x| (Case 2). Then Eq. ( 74) says that with probability 1δ,

- 1 2 < ẑi < 1 2
∀i (Case 1) and

1 2 < ẑj,x < 3 2 if x j = 0, -3 2 < ẑj,x < -1 2 if x j = 1. (Case 2) (75)
Now, let EstInput be the algorithm that takes the output of A, which is the set of estimates {ẑ j } j∈[n] , and does the following:

1. If there exists j ∈ [n] such that ẑj ∈ (-1/2, 1/2), it outputs that x = N , i.e., the unknown state is ρ N .

2. Else, it computes the n-bit string

x = (x 1 , x2 , . . . , xn ) ∈ {0, 1} n as xj = 0 if ẑj ≥ 0 1 if ẑj < 0 , ( 76
)
and outputs that the unknown state is ρ x.

It is easy to see from Eq. ( 75) that this procedure correctly identifies the unknown state, and hence solves Problem 3 with success probability 1δ. b.

Step 2: Computing Fano's lower bound for state identification The string x output by the above procedure is probabilistic. In particular, let P i (x) for i ∈ [2 n + 1] be the probability that running EstInput • A on the unknown state ρ i will output x. Since the last step of our procedure is to sample from P i and then report the output, this last step is a single-sample test to distinguish probability distributions. By Fano's Lemma (Lemma 8), any such test must fail with probability no less than log(N + 1)log( 2)

log(N ) -α N large -→ 1 -α (77)
where α log(N ) is defined to be an upper bound to the quantity

1 N + 1 N k=0 D(P k P N ) . ( 78
)
We will show later (in Proposition 1) that we can bound the average relative entropy between P k and P N as follows:

1 N + 1 N k=0 D(P k P N ) ≤ p 2D m log(N ), ( 79
)
so it suffices to set α = p 2D m. Therefore, in order for the test to have a constant failure probability δ, it must take at least m = p -2D (1δ)-many samples.

Eq. ( 78) is a critical quantity in Fano's Lemma and our argument, so let us interpret it: take the maximally-mixed state I/2 n to be the reference state and the probability distribution output by our noisy state discrimination algorithm on I/2 n to be the reference probability distribution P N . Eq. ( 78) examines the divergence between the output of the algorithm initialized with one of the states ρ x , and that when initialized on the reference state. Intuitively, if this quantity is high, it indicates that the states are "far apart", and hence the distinguishing algorithm could potentially have a lower probability of error.

Indeed, bounding the distinguishability of the states in our set (which becomes the left-hand-side of Eq. ( 78) after one application of data-processing) is the technical crux of our argument. We present a basic bound in Proposition 1 and we will gradually refine this bound in the next few sections to get progressively more severe dependencies of the sample complexity of error mitigation on various parameters of the problem. In this Proposition, we will use notation that is more explicit about the inputs to error mitigation: A(C, p, M, ρ x ) will mean the error mitigation algorithm provided with m copies of the noisy input state Φ C,p (ρ x ) and where the task is to predict the observables in the set M.

Proposition 1 (Simple bound on average divergence). Let P 0 , P 1 , . . . , P N -1 for N = 2 n be the probability distributions over the outputs of the algorithm for noisy state discrimination described in the proof of Theorem 8, run on the different input states ρ 0 , . . . , ρ N -1 . That is, P x for x ∈ {0, 1} n is the probability distribution output by

EstInput • A(C, p, M, ρ x ) , (80)
and similarly let P N be the probability distribution over the output of

EstInput • A(C, p, M, I/2 n ) . (81)
Then it holds that

1 N + 1 N k=0 D(P k P N ) ≤ p 2D m log(N ), ( 82
)
where m is the number of times A(C, p, M, ρ x ) has to invoke the noisy circuit Φ C,p .

Proof. Firstly, note that since ρ N := (I/2 n ) ⊗m , we can explicitly write down the output of the noisy circuit on this state as Φ C,p (ρ N ) = (I/2 n ) ⊗m , as the maximally-mixed state is the fixed point of depolarizing noise.

Since P k = EstInput • A(C, p, M, ρ k ) and P N = EstInput • A(C, p, M, I/2 n ), by the data-processing inequality we have

D(P k P N ) ≤ D(Φ C,p (ρ k ) ⊗m I/2 n ),
and so it suffices to bound the quantity D(Φ C,p (ρ k ) ⊗m I/2 n ). The rest of this proof shows that for k ∈ {0, 1} n :

D(Φ C,p (ρ k ) ⊗m (I/2 n ) ⊗m ) ≤ p 2D nm (83)
by the unitary invariance of the relative entropy, the strong data-processing inequality for depolarizing noise and the additivity of the relative entropy. To see this, observe that

D(Φ C,p (ρ k ) ⊗m (I/2 n ) ⊗m ) = mD(Φ C,p (ρ k ) I/2 n ) (84) ≤ m p 2D D(ρ k I/2 n ) (85) = m p 2D D(U † (|k k|) I/2 n ) (86) = m p 2D D(|k k| I/2 n ) (87) = p 2D mn, (88)
where the first equality follows from additivity of relative entropy, the first inequality is strong data-processing for D layers of depolarizing noise with parameter p, [68]

D(Φ C,p (ρ k ) I/2 n ) ≤ p 2D D(ρ k I/2 n ), (89)
the third equality follows from unitary invariance of relative entropy, and the fourth equality follows from calculation. Lastly, we clearly have

D(P N ||P N ) = 0 < p 2D nm. Therefore 1 N + 1 N k=0 D(P k P N ) < p 2D nm (90) as desired.
Theorem 8 states that a general input state-agnostic error mitigation protocol should have a worst-case sample complexity scaling exponentially in D. So far, our proof method does not encompass input state-aware error mitigation protocols, which are those that, in addition to knowing the noiseless circuit, also know its input state. Such knowledge would be an unauthorized 'back door' for the error mitigation algorithm used inside the solver for noisy state discrimination.

Can we remedy this lack? We offer two affirmative answers. The first follows immediately from close inspection of our proof method: our results extend to even error mitigation protocols working with a guarantee that the input state is chosen from a known set of size N + 1-a situation somewhere between input-state agnosticism and full input-state awareness. Secondly, we will next show that a modification of our argument allows us to make a statement about the complexity of fully input-state aware error mitigation algorithms.

C. The input-state aware case

We cannot expect lower bounds on the sample complexity of the general error mitigation task in the input-state aware setting, because there always exists a trivial error mitigation algorithm that does not access the quantum device-hence uses zero samples-and instead simulates the quantum circuit to obtain the desired properties of the noiseless state. This would, of course, not be possible in the setting of the previous subsection, without the additional information about the input state to the circuit. While we previously found sample complexity bounds on any input state-agnostic error mitigation algorithm outputting expectation value estimates, we now change our perspective: we ask how many samples would be needed by an error mitigation algorithm whose outputs are meaningfully different from one that obtains comparable results through purely classical means. In other words, if an error mitigation algorithm is successful but it invokes the quantum device an insufficient number of times, then there exists an equivalent classical algorithm. A tool we will use is the following bound on two-hypothesis testing due to Le Cam: Lemma 9 (Two-hypothesis testing [START_REF] Tsybakov | Introduction to non-parametric estimation[END_REF], Theorem 2.2iii)). For two probability distributions P 0 , P 1 satisfying

P 0 -P 1 T V ≤ α , (91)
the minimum probability of error of any test that draws a single sample and distinguishes P 0 and P 1 is

P error ≥ 1 -α 2 . ( 92
)
Our results on the convergence of random quantum circuits to the maximally mixed state can easily be used to obtain bounds in the total variation distance by an application of Pinker's inequality and the data processing inequality.

In the following theorem we prove that our construction can be used to make a statement about the sample complexity of input state aware error mitigation under depolarizing noise, as long as one demands that such error mitigation makes meaningful use of the quantum inputs. We then remark on how our technique can be extended even to the case of non-unital noise.

Theorem 9 (Input state-awareness does not break the curse of exponentiality). Let A be an input state-aware weak error mitigation algorithm that takes:

• Quantum input: At most m copies of the noisy output state Φ C,N (ρ).

• Classical input, CL(C, N , ρ): Classical descriptions of C, the noise channel N acting on C and the input state to C, which we call ρ, and outputs a distribution over possible outcomes. Then either:

• Case I: For some c > 1, mc -Õ(nD) = Ω(1), i.e., even for input-state aware error mitigation algorithms, exponential in n, D samples are needed; or

• Case II: no algorithm exists can distinguish between the outputs of A(Φ C,N (ρ) ⊗m and A((I/2) ⊗n , CL(C, N , ρ)) with an error probability significantly bounded away from 2/3.

Proof. Suppose we are not in Case I. This implies that mc -Õ(nD) = Θ(1). In Sections IV and V we proved there exists a circuit C * such that for any algorithm A run on either m copies of the state Φ C * ,N (ρ) or m copies of the maximally-mixed state,

D(A(Φ C * ,N (ρ) ⊗m , CL(C * , N , ρ)) A(I/2 n⊗m , CL(C * , N , ρ))) ≤ mD(Φ C * ,N (ρ) I/2 n ) ≤ mc -Õ(nD) = Θ(1) , (93)
therefore Lemma 9 implies that the minimum probability of error distinguishing the output of A(Φ C * ,N (ρ) ⊗m , CL(C, N , ρ)) from the output of A((I/2 n ) ⊗m , CL(C, N , ρ)) is 1/2o(1), proving the claim.

We can prove a similar statement in the case of non-unital noise. However, unitary circuits affected by product non-unital noise are qualitatively different: whereas in the case of unital circuits the outputs will converge to the maximally mixed state asymptotically, non-unital random circuits do not converge to a single state. For instance, as we will show later in the setting of our toy example of noise being applied after 2-design, what happens instead is that after we apply D layers of 2-designs followed by noise, yielding the evolution T D , we have

E [ T D (ρ i -ρ j ) 1 ] ≤ 2 n+1 2 q D 2 n , (94)
where q n = O(c n 1 ) for c 1 < 1 is an exponentially small in n parameter that depends on the noise channel and ρ i , ρ j orthogonal inputs. That is, any two inputs will be mapped to essentially the same state σ D after D applications of the circuit. However, it is in general not possible to compute this state efficiently to simulate it classically and unless the noise is unital the sequence σ 1 , σ 2 , . . . does not converge. Thus, in the argument we used above, the maximally mixed state would have to be replaced by this state σ D . Thus, the same conclusions would hold, but the output of the error mitigation algorithm would be indistinguishable from the output given as input copies of a fixed state σ D that is independent of the input ρ. We cannot exclude the possibility that sampling from σ D gives some extra computational power, but as in general there is no way to compute σ D , it is unclear how to profit from it. In summary, the output of the error mitigation algorithm given the samples from the noisy device would be indistinguishable from that of the same error mitigation algorithm given as input copies of a state σ D that is independent of the input.

Interlude -Let us review the conceptual contribution of this section and look ahead to the next. Theorem 8 leveraged a relation between a noisy state distinguishability problem and a related error mitigation problem to show that the worst-case sample complexity of error mitigation needs to depend exponentially on the depth of the circuit whose errors are being mitigated. The proof of this theorem depended crucially on upper-bounding the quantity

1 N + 1 N k=0 D(Φ C,p (ρ k ) Φ C,p (I/2 n )) , (95)
which is a sort of average distance between the output of the noisy circuit (whose errors we would like to mitigate) and its fixed point, which is the maximally-mixed state. This quantity controls the sample complexity of noisy state discrimination via Fano's Lemma, and in the chain of inequalities (84) to (88) of the proof of Proposition 1, we upperbounded it by α log N where we computed α in terms of m and D. Plugging into Fano's Lemma then completed the argument and yielded the lower bound on sample complexity m.

In the next section, we will refine the upper-bound on (95), so that α has an exponential dependence not only on D, but also on n. Plugging this into Fano's Lemma yields, in turn, a worst-case sample complexity m that depends exponentially on both of these quantities. We will achieve this improvement by carefully constructing the input states C -1 (|x x|). In fact, the key will be a perspicacious choice of C, which leads to a worst-case-bound better than the bound on the right-hand-side of Eq. ( 89), which was proven for general C.

IV. TECHNICAL BACKGROUND AND CONTRIBUTIONS

In this section, we show that there exists a 'rapidly mixing' quantum circuit C * . In so doing we prove a stronger version of our theorem. This circuit is rapidly mixing in the sense that, its output states

Φ C * ,p (I/2 n ⊗ |0 0| ⊗s ), Φ C * ,p (ρ k ⊗ |0 0| ⊗s ), k ∈ {0, 1} n , (96)
for the input states {ρ k } and the maximally mixed state (concatenated with ancilla qubits), satisfies

1 N + 1 N k=0 D(Φ C * ,p (ρ k ⊗ |0 0| ⊗s ) Φ C * ,p (I/2 n ⊗ |0 0| ⊗s )) < c Ω(nD) , (97)
for some constant c < 1 (c.f. Eq. ( 95)). In the previous section, in Eq. ( 90), for a generic C, we could only prove that the average distinguishability could be bounded by p Ω(D) nm, which does not have the n dependence. Thus when D = O(log n), the old bound is exponentially weaker in n. After we prove the improved bound for our particular circuit C * , we will then wrap up by again plugging this bound into the information-theoretic outer loop of our argument, which uses the sample complexity of noisy state distinguishability to lower bound that of error mitigation.

A. Technical background

In fact, we do not construct C * explicitly. Instead, we let C * be a concatenation of blocks, i.e.,

C * = C • • • • • C 2 • C 1 , (98)
where every block is a circuit C j sampled independently from an ensemble of circuits (described in Lemma 10). We will then show that the expected C * , when affected by depolarizing noise and run on the input states I/2 n and ρ k , k ∈ {0, 1} n , displays the scaling we claim in Eq. (97). We can then use the probabilistic method to conclude that there exists one particular circuit that achieves the same bound. Every block in C * is constructed via the following prescription by Cleve, Leung, Liu and Wang [START_REF] Cleve | Near-linear constructions of exact unitary 2-designs[END_REF]:

Lemma 10 (Exact unitary 2-designs from Clifford gates [START_REF] Cleve | Near-linear constructions of exact unitary 2-designs[END_REF]). With circuits C consisting of O(n log 2 n log log n) single-and two-qubit Clifford gates and Õ(n) auxiliary qubits, in O(log 2 (n)) depth, it is possible to implement an exact unitary 2-design on n qubits. The auxiliary qubits all start in the state |0 0| and are returned to this state at the end of the circuit.

In other words, the above is a prescription for constructing Clifford circuits C that form unitary 2 designs on a subset of the qubits. Each such circuit has the property that

C(ρ ⊗ |0 0| ⊗s ) = C(ρ) ⊗ |0 0| ⊗s , ( 99
)
where s is the number of auxiliary qubits and C is a unitary sampled from an exact unitary 2-design.

We want to consider a noisy version of the circuit C * defined in (98). This means that in between every layer of single-and two-qubit Clifford gates comprising each circuit C j , there is a layer of depolarizing noise on every qubit. In particular, the noisy version of the block C j is of the form

Φ Cj , pj = D ⊗(n+s) p D • C (D ) j • • • • • D ⊗(n+s) p2 • C (2) j • D ⊗(n+s) p1 • C (1) j , (100)
where p j = (p 1 , p 2 , . . . , p D ) is a vector of single-qubit depolarizing noise parameters and D is the depth of the construction of Ref. [START_REF] Cleve | Near-linear constructions of exact unitary 2-designs[END_REF], as specified in Lemma 10 above. The superscript indexes the layer of the circuit and the subscript indexes the block. The noisy version of the overall circuit C * , which is the subject of our analysis, is then

Φ C * , p := Φ C , p • • • • • Φ C2, p2 • Φ C1, p1 . (101)
We now show that we can simplify the form of this noisy circuit by making use of an important property of Clifford gates, which can even be taken to be their defining property, which is that they map Pauli operators to other Pauli, up to a sign. This leads to the following result.

n qubits . . . Lemma 11. Let P be a Pauli channel and let C be a Clifford unitary. Then there exists a Pauli channel P such that

s qubits Φ C 1 ,⃗ p 1 Φ C 2 ,⃗ p 2 Φ C ℓ ,
• • • • • • • • • (a)
C • P = P • C. (102)
Proof. Let P = C•P•C † . It is clear that Eq. (102) holds. Furthermore, we see that letting P = P ∈{I,X,Y,Z} ⊗n q P P (•)P, then

P (ρ) = P ∈{I,X,Y,Z} ⊗n q P CP C † (•)C † P C.
As C is a Clifford unitary, CP C † will also be a Pauli string, up to a sign. Thus, we conclude that the Pauli operators of P are also Paulis and it is a Pauli channel.

Lemma 12 (Pushing Paulis to the end of the circuit). Consider the noisy circuit defined in Eq. (101). There exists a Pauli channel P n+s , acting on all n + s qubits, such that

N = P n+s • (D ⊗n p ⊗ id s ) • C • • • • • (D ⊗n p2 ⊗ id s ) • C 2 • (D ⊗n p1 ⊗ id s ) • C 1 . (103)
In other words, all of the noise acting on the s auxiliary qubits and within the circuit for each design can be pushed to the end.

Proof. First, note that all gates of the circuit are Clifford and all the noisy channels are assumed to be product of 1-qubit Pauli noise channels. As observed in Lemma 11, given a Pauli channel followed by a Clifford gate, we can always obtain the same transformation by first applying the gate followed by a (typically different) Pauli channel. Furthermore, Pauli channels all commute with each other. To see this, note that Pauli strings are the eigenvalues of Pauli channels. As they share a common eigenbasis, they all commute. Thus, we can take all the individual depolarizing channels either acting on the auxiliary systems or within the blocks that generate each design and commute them to end of the circuit. This gives the desired representation.

We briefly remark on how the above calculations will be used in our proof. We will again use the observation of Eq. ( 2) of the Central Lemma 1, but now with the noisy circuits we have specially constructed: C = Φ C * , p . That is, consider a new instance of the noisy state distinguishability problem (Problem 3), in which the task is to identify the label k given a noisy state from the set

Φ C * , p (|k k| ⊗ |0 0| ⊗s ), k ∈ {0, 1} n , and Φ C * , p (I n /2 n ⊗ |0 0| ⊗s ) (104)
Let us denote ρ k = |k k| ⊗ |0 0| ⊗s . We then want to consider the quantity

D(Φ C * , p (ρ k ) Φ C * , p (I n /2 n ⊗ |0 0| ⊗s )). ( 105
)
Lemma 12 will simplify the task of bounding this quantity. Recall the result in (103). In particular, let

N := (D ⊗n p ⊗ id s ) • C • • • • • (D ⊗n p2 ⊗ id s ) • C 2 • (D ⊗n p1 ⊗ id s ) • C 1 , (106)
so that Φ C * , p = P n+s • N . This re-writing is useful because recursive application of (99) implies that the state I n /2 n ⊗ |0 0| ⊗s is a fixed-point of N , a fact that we use in Eq. ( 107) below. From the data-processing inequality, we obtain

D(Φ C * , p (ρ k ) Φ C * , p (I n /2 n ⊗ |0 0| ⊗s )) = D((P n+s • N )(ρ k ) (P n+s • N )(I n /2 n ⊗ |0 0| ⊗s )) (107) ≤ D( N (ρ k ) I n /2 n ⊗ |0 0| ⊗s ) ≤ D j=1 D ⊗n pj • C j (|k k|) ⊗ |0 0| ⊗s N (I n /2 n ⊗ |0 0| ⊗s ) = D j=1 D ⊗n pj • C j (|k k|) I n /2 n ,
where we note that the channel j=1 D ⊗n pj • C j acts only on the n system qubits and not on the auxiliary ones. We can thus focus on the quantity

D j=1 D ⊗n pj • C j (|k k|) I n /2 n (108)
for the remainder of this section, where the circuits C j are independently drawn from a unitary 2-design. Since the uniform ensemble of Clifford unitaries forms a unitary 2-design, we assume from now on that the C j are Clifford unitary channels.

B. Bound for multiple layers of depolarizing noise

Let us recall that our goal is to bound the average distinguishability quantity

1 N + 1 N k=0 D(P k P N ). ( 109
)
It turns out that we can obtain a k-independent bound on D(P k P N ); to do so, we invoke the following consequence of Lemma 2, which says that we can bound the expected relative entropy for each k by calculating the expected purity

E C∼E D j=1 D ⊗n pj • C j (|k k|) I 2 n ≤ n + E C∼E log Tr j=1 D ⊗n pj • C j (|k k|)) 2 ≤ (110) n + log E C∼E Tr j=1 D ⊗n pj • C j (|k k|)) 2 ,
where k ∈ {0, 1} n and the last step follows from Jensen's inequality. Let us now compute that purity. In Section V we will compute the expected purity of the outcome of l applications of a channel with a 2-design for arbitrary channels.

In particular, in Prop. 4 we show that:

E C∼E Tr j=1 D ⊗n pj • C j (|k k|)) 2 = q n + 2 -n , (111)
where for a qubit depolarizing channel with depolarizing probability p we have:

q n = 1 -3 4 p(2 -p) n -2 -2n 1 -2 -2n . ( 112
)
Inserting this bound in Eq. ( 110) we conclude that:

E C∼E D j=1 D ⊗n pj • C j (|k k|) I 2 n ≤ n + log(q n + 2 -n ) = log(2 n q n + 1) ≤ 2 n q n (113)
In particular, if

> 1 2 -log 2 (4 -3p(2 -p)) , (114)
then

2 n q n ≤ c n (115)
for a constant c < 1.

C. Putting it all together

We finally feed the results of the previous subsections into the information-theoretic outer loop already used in Section III, and obtain a tighter bound on sample complexity. For conciseness, we state Theorem 10 for depolarizing noise that acts with the same strength after every circuit layer; however, as demonstrated in Section IV B, the theorem holds with minor modifications for the case when the noise parameter differs for every layer.

Theorem 10 (Error mitigation with depolarizing noise requires exponential-in-n, D samples). Let A be an input state-agnostic weak error mitigation algorithm (see Definition 2) that takes as input m noisy copies of the output state of a circuit C acted upon by local depolarizing noise of parameter p. Suppose that for any circuit C acting on n qubits of depth D, where

D = Ω   log 2 (n) log 4 1+3p 2   , (116)
and the set of observables M = {Z i } n i=1 , A(C, M, p) is able to produce estimates {ẑ i } i∈[n] such that with probability at least 1δ,

|ẑ i -Tr [Z i C(ρ)]| ≤ for all i ∈ [n]. ( 117
)
Then as long as < 1/2, there exists a constant c ≥ 1, such that the number of noisy copies, m, needed by A(C, M, p), is lower-bounded as

m = c -Õ(nD) , (118)
where the notation Õ() hides polylogarithmic factors in n.

Proof. Let us first note that we must rescale n by a constant factor because it now refers to the size of both system and ancillas (the constant factor is because only s = Õ(n) ancillas are required, according to [START_REF] Cleve | Near-linear constructions of exact unitary 2-designs[END_REF]), while our bounds from the previous subsections were in terms of only the number of system qubits.

From Equation ( 113) and linearity of expectation we conclude that

E C 1 N + 1 N k=0 D C(|k k| ⊗ |0 0|) E p(E) I 2 n ⊗ σ E ≤ c Ω(n ) ) . (119)
Here, the expectation is over the distribution induced by constructing a circuit C by sequentially performing the randomized circuit construction of Ref. [START_REF] Cleve | Near-linear constructions of exact unitary 2-designs[END_REF], ≥

1 log 4 1+3p 2
times. Here we note that, as stated in the previous subsection, the ancillary states σ E are a function of C. By the probabilistic method, there thus exists at least one circuit C of this form, with corresponding states {σ E } E , such that the average relative entropy is upper-bounded by the same quantity: the circuit's output states

ρk := C(|k k| ⊗ |0 0|) for k = 0, . . . , N -1, (120) ρN
:= C E p(E) I 2 n ⊗ σ E (121)
for N = 2 n , satisfy

1 N + 1 N k=0 D(ρ k ||ρ N ) ≤ c O(n ) = c O(nD/ log 2 (n)) . ( 122
)
Wrapping up, we plug this into the Central Lemma (Lemma 1): we lower bound the sample complexity of mitigating the depolarizing noise in the circuit C by the sample complexity of noisy state discrimination of the states {ρ 0 , . . . ρN }. This proceeds in much the same way as we proved Theorem 8, except that we do not even require all the estimates output by weak error mitigation for the state discrimination problem: we may throw away the information in the estimates ẑj for j > n (i.e., the Paulis on the ancillary qubits).

D. Strengthening our results

In this last subsection, we strengthen our results so that they hold for circuits that are restricted to use local gates only. We also improve the depth dependence and introduce a dependence on the light-cone size.

Geometrically local circuits

Our circuit construction works by iterating the construction of Ref. [START_REF] Cleve | Near-linear constructions of exact unitary 2-designs[END_REF] D times. The reader may observe, however, that the above construction requires all-to-all connectivity. Bearing in mind that error mitigation is usually applied to near-term quantum circuits for which only some geometrically local architecture is available, we now discuss how our results transfer to the case when we limit our attention only to error mitigation on such circuits. We observe that, for one-dimensional circuit architectures, every gate between non-nearest neighbor qubits can be replaced by at most O(n) nearest-neighbor gates, by first doing a cascade of n -1 sequential SWAPs to bring the two input qubits next to each other, and then applying the appropriate gate on these now-nearest neighbors. In d dimensions, the number of swaps that must be done is at most O(n 1/d )-as the maximum distance between two qubits scales as the radius of the circuit architecture graph. Thus, unsurprisingly, with limited connectivity, the exponential in n cost of error mitigation implied by our results only kicks in at depths in which the light-cone of all qubits is the entire system. And, for d dimensional architectures, this is O(n 1/d ).

Smaller depths and light-cone size dependence

Furthermore, we can easily use the construction above to also obtain a large relative entropy contraction at smaller depths. Indeed, suppose we partition the qubits into s disjoint subsets S 1 , . . . , S s such that each subset has maximal size n/s . After that, we independently apply the construction above on each subset. Then at depth

D ≥ O   log 2 (n/s) log 4 1+3p 2   (123)
on each block the relative entropy will satisfy

1 N + 1 N k=0 D(ρ k ||ρ N ) ≤ O(c -nD/s ). ( 124
)
As the state will be product across different subsets, the total relative entropy will be at most

O sc -nd/s . (125)
In particular, by picking, say s ∼ n/ log 2 (n), we see that there are circuits such that at depths O(poly(log log(n)), the relative entropy will decay towards 0 faster than any polynomial in the number of qubits. Furthermore, another property this construction enjoys is that it only involves quantum circuits with light-cones of size at most n/s . Indeed, as each of the unitaries only acts on subset of qubits of this size, the light-cone of each qubit is of that size. From this we obtain the following.

Theorem 11 (Error mitigation with depolarizing noise with small depth and light-cones). Let A be an input stateagnostic weak error mitigation algorithm (see Definition 2) that takes as input m noisy copies of the output state of a circuit C acted upon by local depolarizing noise of parameter p. Suppose that for some L > 0 for any circuit C with light-cone of size L acting on n qubits of depth D, where

D ≥ O   log 2 (L) log 4 1+3p 2   , (126)
and the set of observables M = {Z i } n i=1 , A(C, M, p) is able to produce estimates {ẑ i } i∈[n] such that with probability at least 1δ,

|ẑ i -Tr [Z i C(ρ)]| ≤ for all i ∈ [n]. (127)
Then as long as < 1/2, there exists a constant c ≥ 1, such that the number of noisy copies, m, needed by A(C, M, p), is lower-bounded as

m = L n c -Õ(LD) , (128)
where the notation Õ() hides polylogarithmic factors in n. In particular, by picking L = Ω(log 2 (n)), we see that there circuits of depth poly(log log(n)) that require a superpolynomial number of samples to error-mitigate.

The theorem above shows that as long as light-cones are slightly above log(n) (namely log 2 (n)) and depths are slightly above constant (log 2 (log(n)), error mitigation is no longer efficient in general. However, note that it is possible to compute the expectation value of observables with light-cones of size O(log(n)) efficiently classically. This proves that in general error mitigation can only provide a better exponent in the scaling of an algorithm to estimate expectation values when compared with classical algorithms.

V. BEYOND UNITAL NOISE

So far all the results we have discussed only apply to local random circuits with unital noise. It is thus natural to ask how the picture changes when the noise is non-unital. This is because many physically relevant noise models, such as amplitude damping, are non-unital. However, going beyond the non-unital model brings with it several technical complications. First, as we show, in general the noisy circuit will not converge anymore to a fixed point. Second, the entropy of a state does not necessarily increase under a non-unital map. As our previous results were based on entropic considerations, our arguments do not apply anymore. Furthermore, if the outputs of the noisy circuit are not full-rank, as could be the case for noise models like amplitude damping, the relative entropy between the outputs given different inputs might even be infinitely large. This motivates us to look at a different distance measure as well. Indeed, we resort in this section to the standard technique of controlling the trace distance through the Hilbert-Schmidt distance.

In light of these complications, we now discuss a toy model for the convergence of noisy circuits where it is still possible to obtain explicit bounds on their convergence. More precisely, we consider the model in which we have a circuit composed of (global) 2-designs followed by a noisy channel, and then we iterate this construction.

We show below that if the noisy channel is a qubit product channel, in expectation the trace distance between outputs are exponentially small in both the depth and the number of qubits. Although global 2-designs require at least polylogarithmic depth to implement and we only consider the case in which the noise acts after we implement it, we believe that our results illustrate that in principle our conclusions in the previous sections should carry over to the non-unital setting for deep enough unitary circuits. We start by computing moments of noisy random circuits that will be crucial for our conclusions later on.

A. Purity and overlap change after one noisy gate

Consider the state

ρ out,i := (N • U)(ρ i ), (129)
where ρ i is an arbitrary d-dimensional state, N is a quantum channel, and U(•) = U (•)U † , with U a unitary. The idea is that N represents the noise after we apply the gate. Let us investigate how the overlap and purity of states changes after we apply the 2-designs and the noise on top. Note that by controlling overlaps and purities it is then straightforward to control the Hilbert-Schmidt distance. Let us start by expressing the overlap in a more convenient way. The overlap between the two output states ρ out,i , ρ out,j is given by

Tr[ρ out,i ρ out,j ] = Tr[(N • U)(ρ i )(N • U)(ρ j )] (130) = Tr[F ((N • U)(ρ i ) ⊗ (N • U)(ρ j ))] ,
where F is the swap operator. Now, suppose that N has the following Kraus decomposition

N (•) = r =1 K (•)K † . (131)
Using this, we get that the expected overlap of the output states for U a 2-design is

E U [Tr[ρ out,i ρ out,j ]] = r , =1 E U Tr F (K ⊗ K )(U ⊗ U )(ρ i ⊗ ρ j )(U † ⊗ U † )(K † ⊗ K † ) (132) = α r , =1 Tr F ((K ⊗ K )(K † ⊗ K † )) + β r , =1 Tr F (K ⊗ K )F (K † ⊗ K † ) ,
where for the last line we used the general fact (see, e.g., Ref. [START_REF] Watrous | The theory of quantum information[END_REF]Example 7.25]) that for 2-designs

E U [(U ⊗ U )X(U † ⊗ U † )] = Tr[X] d 2 -1 - Tr[F X] d(d 2 -1) α I ⊗ I + Tr[F X] d 2 -1 - Tr[X] d(d 2 -1) β F. (133)
The involved quantities take the values

Tr F ((K ⊗ K )(K † ⊗ K † )) = Tr[K K † K K † ], (134)
Tr

F (K ⊗ K )F (K † ⊗ K † ) = Tr[K K † ⊗ K K † ] = | Tr[K K † ]| 2 , (135)
for all , ∈ {1, 2, . . . , r} and

α = 1 d 2 -1 - Tr[ρ i ρ j ] d(d 2 -1) , (136)
β = Tr[ρ i ρ j ] d 2 -1 - 1 d(d 2 -1) . (137)
We can rephrase these quantities in terms of global properties of the channel as

r =1 K K † = N (I), (138) r
, =1 | Tr[K K † ]| 2 = Tr[(Γ N ) 2 ], (139)
where

Γ N := (id ⊗ N )(|Γ Γ|), |Γ := d-1 j=0 |j, j , (140)
is the Choi representation of N . Therefore, the expected overlap of the output states is

E U [Tr[ρ out,i ρ out,j ]] = 1 d 2 -1 - Tr[ρ i ρ j ] d(d 2 -1) Tr[N (I) 2 ] + Tr[ρ i ρ j ] d 2 -1 - 1 d(d 2 -1) Tr[(Γ N ) 2 ]. (141)
Note that both Tr[(Γ N ) 2 ] and Tr[N (I) 2 ] scale with the underlying dimension of the space. In order to more easily grasp the scaling of the formula above, it is fruitful to look at the rescaled quantities

η = Tr[N (I/d) 2 ], ν = Tr[(Γ N ) 2 /d 2 ]. (142)
Note that η is just the purity of the output of the maximally mixed state and, thus, takes values in [d -1 , 1], whereas ν is just the purity of the output of the maximally entangled state if we act with the channel on one half of the system (i.e., the Choi state) and takes values in [d -2 , 1]. In terms of these newly defined quantities, we obtain

E U [Tr[ρ out,i ρ out,j ]] = d 2 d 2 -1 - d Tr[ρ i ρ j ] (d 2 -1) η + d 2 Tr[ρ i ρ j ] d 2 -1 - d (d 2 -1) ν. (143)
Remark 12. It is well-known that twirling any quantum channel with a unitary 2-design will lead to a global depolarizing noise in expectation, i.e.,

E U ∼Haar U † • N • U = D (d) p [70]
. Note, however, that the problem at hand is slightly different, as we are interested in an expectation value that contains two copies of the channel. In that case, the resulting action cannot be effectively of a global depolarizing channel. To illustrate this point more concretely, assume that the noise is actually a unitary gate. In that case, the purity or overlap between two different initial states should remain constant for all unitaries, which differs from the depolarizing noise picture discussed before. For example, let us assume that N is a unitary channel and ρ i = ρ j = ρ, which means that N (I) = I and Tr[(Γ N ) 2 ] = d 2 . Then, we obtain

E U [Tr[ρ out,i ρ out,j ]] = αd + βd 2 (144) = d 1 d 2 -1 - Tr[ρ 2 ] d(d 2 -1) + d 2 Tr[ρ 2 ] d 2 -1 - 1 d(d 2 -1) = Tr[ρ 2 ],
as expected.

B. Convergence of global random circuits

From Eq. (143), we obtain a recursive formula for the overlap and/or purity of outputs of independent 2-designs interspersed by noise. Letting

T t = t l=1 N • U l (145)
and ρ i,t = T t (ρ i ) for some initial state ρ i we have:

E U [
The structure of the recursion becomes more apparent when discussed in abstract terms. We have that

f (t) = Af (t -1) + B (148) = A(Af (t -2) + B) + B = A 2 f (t -2) + AB + B = A 2 (Af (t -3) + B) + (A + 1)B = A 3 f (t -3) + (A 2 + A + 1)B = A t f (0) + (A t-1 + • • • + A + 1)B.
The right term is nothing but a geometric series, which under the assumption 0 ≤ A < 1 yields

f (t) = A t f (0) + 1 -A t 1 -A B. (149)
Applied to our setting, we obtain

The exponential behavior in t of this quantity and the applicability of the geometric series is determined by the term d(dνη)/(d 2 -1). The fact that this term is always positive and strictly smaller than 1 if the channel is not unitary, indicating an exponential decay in t, is a consequence of the following proposition: I is a normalized vector with respect to the Hilbert-Schmidt norm. Furthermore, let X i , 1 ≤ i ≤ d 2 -1 be an orthonormal, self-adjoint basis for the space of traceless matrices.

Then, using the fact that

|Γ Γ| = I √ d ⊗ I √ d + d 2 -1 i=1 X i ⊗ X i , (153)
we obtain

ν = d -2 Tr[N † N ] = d -2 Tr[N (d -1 2 I) 2 ] + d -2 d -1 i=1 Tr[N (X i ) 2 ] = d -1 η + d -2 d -1 i=1 Tr[N (X i ) 2 ]. ( 154
)
As the second term in the sum above is clearly positive, we obtain the claim in Eq. (151). To obtain the claim in Eq. ( 152), note that the expression is clearly monotone increasing in ν and decreasing in η. The maximum value for ν is 1, which is attained for a unitary channel (pure Choi states are unitaries). Furthermore, for unitary channels we have η = d -1 . In this case, the constant contribution of Eq. ( 146) vanishes as expected.

In particular, it follows that unless the channel is unitary, the expected trace norm between outputs will be exponentially small. To conclude that, we will first study the convergence in the Hilbert-Schmidt norm. Proposition 3. Let T = l=1 N • U l be a random quantum channel where N : M d → M d is a fixed quantum channel and U t are drawn independently from a unitary 2-design on a d-dimensional space. Furthermore, let η, ν be defined as in Eq. (142) and

q = d(dν -η) d 2 -1 . ( 155
)
Then, for any orthogonal pure states ρ i , ρ j we have

E U T D (ρ i -ρ j ) 2 2 = 2q D (156)
and

E U [ T (ρ i -ρ j ) 1 ] ≤ 2dq D (157)
Proof. First, observe that

E U T (ρ i -ρ j ) 2 2 = E U [Tr[ρ 2 ,i ]] + E U [Tr[ρ 2 ,j ]] -2E U [Tr[ρ ,i ρ ,j ]], (158)
where ρ ,i = T (ρ i ). Inserting the expression in Eq. ( 150) for each term we get

E U T (ρ i -ρ j ) 2 2 = q Tr[ρ 2 i ] + Tr[ρ 2 j ] -2 Tr[ρ i ρ j ] , (159)
as the rest of the terms cancel. Using that Tr[ρ i ρ j ] = 0 and Tr[ρ 2 i ] = Tr[ρ 2 j ] = 1 we arrive at Eq. (156). Next, from Jensen's inequality, it follows that

E [ T (ρ i -ρ j ) 1 ] 2 ≤ E T (ρ i -ρ j ) 2 1 . (160)
Furthermore, we have the standard inequality X 1 ≤ √ d X 2 for all Hermitian X. Combining this observation with the claim in Eq. (160) yields Eq. (157).

Let us investigate the case of d = 2 n (n qubits) and N = n i=1 N i (i.e., N is a product channel) in a bit more detail. Furthermore, assume for simplicity that all N i are the same. As the purity is multiplicative, we obtain η N = η n Ni , ν N = ν n Ni and

q n = 2 2n ν n Ni -2 n η n Ni 2 2n -1 . (161)
Thus, we see that the 2-norm decays exponentially in the number of qubits, even after one layer. In particular, we obtain the following corollary.

Corollary 1. In the same setting of Proposition 3, assume further that N is an n-qubit product channel and define q n as in Eq. (161). Then we have

E [ T (ρ i -ρ j ) 1 ] ≤ 2 n+1 2 q 2 n . (162)
Proof. The statement then follows from Proposition 3 and the discussion above, as

E [ T (ρ i -ρ j ) 1 ] ≤ 2 n+1 2 q 2 n . (163)
We can combine the statement above with sub-additivity of the trace distance to conclude that for m copies of the outputs of the noisy circuit we have

E T ⊗m (ρ ⊗m i -ρ ⊗m j ) 1 ≤ m2 n+1 2 2 2n ν n Ni -2 n η n Ni 2 2n -1 2 . ( 164
)
As explained before, successful error mitigation can be used to distinguish orthogonal input states. However, it is well-known that the trace distance bounds the probability of successful distinction between two states. Thus, we conclude the following.

Theorem 13 (Error mitigation with non-unital noise). Any input agnostic error mitigation procedure that works successfully for outputs of T would require a number of copies m that grows as

m ≥ 2 -n+1 2 2 2n ν n Ni -2 n η n Ni 2 2n -1 -2 . ( 165
)
As discussed before, ν Ni < 1 unless we have a unitary channel. Thus m will be Ω(c -n ) for some some c < 1 at a number of iterations = O(1), as

2 2n ν n Ni -2 n η n Ni 2 2n -1 2 ≤ 2 -n+1 2 (166)
for D = O(1).

The input aware case is a bit more subtle. What we conclude from the results above is that all input states will be mapped by T D to the same state up to an exponential small correction. Thus, the noisy circuit is essentially a replacer channel and any error mitigation algorithm with sub-exponential samples would have the same performance given copies of this one state. However, unlike it was the case with the maximally mixed state, it is unclear that it is possible to classically simulate that state or that it is not a valuable computational resource. However, it is of course also unclear how a practical error mitigation might profit from access to samples from an (unknown) fixed state.

C. Bounds on the probability of successful virtual distillation

It is straightforward to use the result introduced above to bound the probability of virtual distillation protocols [START_REF] Huggins | Virtual distillation for quantum error mitigation[END_REF][START_REF] Koczor | Exponential error suppression for near-term quantum devices[END_REF] succeeding under non-unital noise. As discussed before, the probability of such protocols succeeding is bounded by Tr[ρ 2 ]. If we introduce the quantity

r n = 2 2n η n Ni -2 n ν n Ni 2 2n -1 , (167)
we can show the following: Proposition 4. In the same setting of Proposition 3, assume further that N is an n-qubit product channel and define q n as in Eq. (161) and r n as in Eq. (167). Then we have for all pure states ρ

E Tr T (ρ) 2 = q n + (1 -q n )r n 1 -q n . (168)
Furthermore, both r n and q n are exponentially small in n unless the quantum channel N i is unitary or a replacer channel for a pure state, i.e., N i (σ) = |ψ ψ| for all σ and some |ψ .

Proof. The claim in Eq. (168) follows from Eq. ( 150), inserting the definition of q n and r n . As q n ≤ ν n N i 1-2 -2n and ν Ni = 1 if, and only if, N i is a unitary channel, we see that q n will decay exponentially unless the channel is unitary. Let us now analyse r n , assuming the channel is not unitary. Note that it will also decay exponentially if we manage to show that η Ni < 1 if the channel is not a replacer with a pure state. As η Ni is the purity of the output of the maximally mixed state, if η Ni = 1 then the maximally mixed state is mapped to a pure state |ψ ψ|. We will now show that this implies that all states are mapped to the same pure state. By linearity, it suffices to show the claim for a pure input state |φ φ|. For this, note that The fact that 1 2 N i (|φ φ|) ≤ |ψ ψ| implies that 1 2 N i (|φ φ|) = 1 2 |ψ ψ|. Indeed, if it was not the case, N i (|φ φ|) would have nonzero support on the subspace orthogonal to |ψ , which would contradict the inequality. Thus, we conclude that η Ni < 1 for non-replacer channels and hence that r n is exponentially small in n.

Thus, it follows that the probability of success of virtual distillation, which is upper-bounded by Eq. (168) will also be exponentially small even after a single layer of noise unless we are in the unitary or replacer case. But for unitary errors virtual distillation does not have any effect, as the input state is anyways pure. And for replacer channels it is clear that, even though the procedure will succeed with probability 1, we will just output a fixed pure product state. So in the cases where the success probability is not exponentially small, the procedure is of no use. However, note that it will not converge to the minimal possible value of the purity (2 -n ) unless the channel is unital, but rather to r n . This is to be expected, as the noisy quantum circuit will not converge to the maximally mixed state in this case.

VI. OUTLOOK

In this work, we have established a general rigorous framework that encapsulates large classes of schemes for quantum error mitigation that are being used in practice, but also others that are primarily of conceptual value. For these schemes, all of which come along with little additional experimental effort, we have identified severe informationtheoretic limitations, limitations that are exponentially tighter than what was previously known. As our results feature a worst-case construction of circuits, further empirical investigation is needed to determine whether typical circuit instances for near-term quantum algorithms will fall into the regime we have described. These results do not imply that one should not perform quantum error mitigation to tackle suitably small noise levels in existing quantum architectures. At the same time, this work identifies substantial limitations that arise when one aims at scaling up such ideas to near-term quantum devices. In fact, this work can be seen as a strong indication that in the medium term, some form of quantum error correction involving quantum redundancy will presumably be necessary. It may also mean new schemes might be required that are intermediate between mere quantum error mitigation and resource expensive fault tolerant quantum computing. It is the hope that the present work inspires such further steps aimed at combating quantum noise in near-term quantum devices, to move universal quantum computers closer to reality.

FIG. 1 .

 1 FIG. 1. (a) Idealization of near-term quantum algorithms without quantum noise: Most such algorithms work by running an n-qubit quantum circuit C, measuring it and outputting expectation values of specified observables or samples. (b) The model of error mitigation used in this work. C i is the i-th run of C , the noisy version of C.We model the noise acting on C by interleaving its layers with layers of a given noise channel. In general, our model encompasses those error mitigation protocols that modify C on each iteration. In section II B, we will show that this model applies to practical error mitigation protocols such as virtual distillation[START_REF] Huggins | Virtual distillation for quantum error mitigation[END_REF][START_REF] Koczor | Exponential error suppression for near-term quantum devices[END_REF], Clifford data regression (CDR)[START_REF] Czarnik | Error mitigation with Clifford quantum-circuit data[END_REF], zero-noise extrapolation (ZNE)[START_REF] Temme | Error mitigation for short-depth quantum circuits[END_REF] and probabilistic error cancellation (PEC)[START_REF] Temme | Error mitigation for short-depth quantum circuits[END_REF][START_REF] Piveteau | Quasiprobability decompositions with reduced sampling overhead[END_REF][START_REF] Endo | Practical quantum error mitigation for near-future applications[END_REF]. We will study how m, the number of noisy circuit runs, scales with n and D.

Definition 2 (

 2 Weak error mitigation (expectation value error mitigation)). An ( , δ) weak error mitigation algorithm A with resources as in Definition 1 takes as input a classical description of a set of observables M = {O 1 , . . . , O } satisfying O i ≤ 1 and outputs estimates ôi of o i = ψ| O i |ψ such that

Theorem 7 (

 7 Exponentially-many expectation values of observables in the same eigenbasis are required to output samples from that basis). There is a class of n-qubit circuits, such that for every circuit C in the class (denote the clean circuit output state as |ψ = C(|0 )) and the set of observables M = {Z b } b∈{0,1} n+1 with m = o(τ 2 • 2 n ), the following holds: No algorithm B exists that takes as input the output of weak error mitigation A(C, N , M)-the estimates {ẑ b } b∈{0,1} m with |ẑ b -ψ| Z b |ψ | < τ for all b-and outputs O(n)-many samples from some distribution p where

2. Depolarizing noise Definition 8 (

 8 Depolarizing channels). For M ∈ L(C d ), the d-dimensional depolarizing channel D (d) p , for d ≥ 2, is defined as

FIG. 3 .

 3 FIG.3. A sketch of the constructions used in this subsection. Figurea) depicts the noisy circuit that results from our prescription of iterating the construction in Ref.[START_REF] Cleve | Near-linear constructions of exact unitary 2-designs[END_REF] times (refer to Eq. (101)) and using our model of local depolarizing noise. Figureb) depicts how we can re-write the circuit in Figurea) by pushing the depolarizing noise on the ancilla qubits to the end of the circuit, by invoking Lemma 12.

E- 1 t

 1 U [Tr[ρ t,i ρ t,j ]] = d(dνη) d 2 Tr[ρ 0,i ρ 0,j ] + 1 -d(dνη) d 2 -1 t d(dην) d 2 -1d(dνη).

Proposition 2 .

 2 Let N : M d → M d be a quantum channel. Define η and ν as in Eq. (142). Then dνη ≥ 0. if the underlying channel is unitary. Proof. First, note that for any linear superoperator L we have Tr[|Γ Γ|(id ⊗ L)(|Γ Γ|)] = Tr[L], where by Tr[L] we mean the trace of L as a linear map. Thus, we see that ν = d -2 Tr[N † N ] is just the average of the square of the singular values of quantum channel. Now, note that d -1 2

2 =

 2 |φ φ|) ≤ N i I |ψ ψ|.

  2, . . . , n}.

	Noisy state distinguishability
	Simple classical post-processing	î
	FIG. 2. To lower-bound the sample complexity of weak error mitigation, we show that it can be used as a subroutine to solve
	a constructed problem of distinguishing states under noise.

  Tr[ρ i,t+1 ρ j,t+1 ]] =

	=	d 2 d 2 -1 d(dν -η) -d 2 -1 Tr[ρ i,t ρ j,t ] + d Tr[ρ i,t ρ j,t ] (d 2 -1)	η + d(dη -ν) d 2 Tr[ρ i,t ρ j,t ] d 2 -1 d 2 -1 .	-	d (d 2 -1)	ν	(146)

VII. ACKNOWLEDGMENTS

This work has been supported by the BMBF (RealistiQ), the BMWK (PlanQK), the DFG (CRC 183), the Einstein Foundation (Einstein Research Unit on Quantum Devices), the Quant-ERA (HQCC), and the Alexander von Humboldt Foundation. The research is also part of the Munich Quantum Valley (K-8), which is supported by the Bavarian state government with funds from the Hightech Agenda Bayern Plus. DSF acknowledges financial support from the VILLUM FONDEN via the QMATH Centre of Excellence (Grant no. 10059), the QuantERA ERA-NET Cofund in Quantum Technologies implemented within the European Union's Horizon 2020 Program (QuantAlgo) via the Innovation Fund Denmark and from the European Research Council (grant agreement no. 81876). DSF acknowledges that this work benefited from a government grant managed by the Agence Nationale de la Recherche under the Plan

In the context of depolarizing noise acting within an n-qubit circuit, a global depolarizing channel is simply a 2 ndimensional depolarizing channel. Using [START_REF] Cerezo | Variational quantum algorithms[END_REF], we find that the global depolarizing channel on n qubits can be written as

Alternatively, one could also model the noise within a circuit as an n-fold local (single-qubit) depolarizing channel D ⊗n p . In particular, the single-qubit depolarizing channel has the property that

Based on these calculations, we make the following observation.

Lemma 7 (Action of depolarizing noise on a Pauli string). For all p ∈ [-1/3, 1] and P ∈ P n ,

Proof. This follows immediately from [START_REF] Gross | Quantum state tomography via compressed sensing[END_REF] and the definition of D ⊗n p .

Unitary 2-designs and Clifford unitaries

where the integral on the right-hand side is with respect to the Haar measure on the unitary group. We are finally ready to present our 'appetizer' theorem. Let us first establish the notation:

Definition 9 (Circuit with depolarizing noise). For any noiseless circuit C of depth D acting on n qubits, define the noisy circuit with noise parameter p, Φ C,p , as follows:

where C (i) represents the i th layer of the circuit C, and D p is a local, single-qubit depolarizing channel. Furthermore, denote the output state of the noisy circuit with input state ρ by

We will now present the key reduction we will use to bound the sample complexity of error mitigation. This reduction is visually represented in Figure 2.

To do so, let us step away from the error mitigation setting for a moment, and first consider the following problem of state discrimination in the presence of noise: Problem 3 (State discrimination in the presence of noise). Fix a set {ρ 0 , ρ 1 , . . . , ρ N } of N + 1 quantum states and a circuit C acted upon by noise N . Suppose that a distinguisher has knowledge of C and N , and is given access to copies of the state Φ C,N (ρ i ), defined analogously to [START_REF] Gottesman | Stabilizer codes and quantum error correction[END_REF], with the index i ∈ {0, 1, . . . , N } unknown. What is the fewest number of copies of Φ C,N (ρ i ) needed in order to identify i with high probability, in terms of the noise strength?

The following variation of Fano's lemma can be used to address this question: