# Noise-induced shallow circuits and absence of barren plateaus

Antonio Anna Mele<EMAIL_ADDRESS>Dahlem Center for Complex Quantum
Systems, Freie Universität Berlin, 14195 Berlin, Germany  Armando Angrisani
<EMAIL_ADDRESS>LIP6, CNRS, Sorbonne Université, 75005 Paris, France
Institute of Physics, Ecole Polytechnique Fédérale de Lausanne (EPFL), CH-1015
Lausanne, Switzerland  Soumik Ghosh  Department of Computer Science,
University of Chicago, Chicago, Illinois 60637, USA
Sumeet Khatri  Dahlem Center for Complex Quantum Systems, Freie Universität
Berlin, 14195 Berlin, Germany  Jens Eisert  Dahlem Center for Complex Quantum
Systems, Freie Universität Berlin, 14195 Berlin, Germany  Fraunhofer Heinrich
Hertz Institute, 10587 Berlin, Germany  Daniel Stilck França
<EMAIL_ADDRESS>Univ Lyon, ENS Lyon, UCBL, CNRS, Inria, LIP,
F-69342, Lyon Cedex 07, France  Yihui Quek<EMAIL_ADDRESS>Departments of
Mathematics and Physics, Massachusetts Institute of Technology, 182 Memorial
Drive, Cambridge, MA 02138, USA

(September 3, 2024)

###### Abstract

Motivated by realistic hardware considerations of the pre-fault-tolerant era,
we comprehensively study the impact of uncorrected noise on quantum circuits.
We first show that any noise ‘truncates’ most quantum circuits to effectively
logarithmic depth, in the task of computing Pauli expectation values. We then
prove that quantum circuits under any non-unital noise exhibit lack of barren
plateaus for cost functions composed of local observables. But, by leveraging
the effective shallowness, we also design a classical algorithm to estimate
Pauli expectation values within inverse-polynomial additive error with high
probability over the ensemble. Its runtime is independent of circuit depth and
it operates in polynomial time in the number of qubits for one-dimensional
architectures and quasi-polynomial time for higher-dimensional ones. Taken
together, our results showcase that, unless we carefully engineer the circuits
to take advantage of the noise, it is unlikely that noisy quantum circuits are
preferable over shallow quantum circuits for algorithms that output Pauli
expectation value estimates, like many variational quantum machine learning
proposals. Moreover, we anticipate that our work could provide valuable
insights into the fundamental open question about the complexity of sampling
from (possibly non-unital) noisy random circuits.

##  I Introduction

One of the most important questions for quantum computers of today is to
understand the behavior and impact of noise [1]. It is crucial to understand
whether noisy quantum computers provide any advantage, both for practically
relevant problems [2, 3], or even as proof-of-principle [4], or whether we
ultimately need error-corrected logical qubits to achieve this goal [5]. Past
years have seen a tussle between demonstrations of quantum advantage [4, 6, 7,
8, 3] and subsequent efficient classical simulation [9, 10, 11, 12, 13, 14,
15, 16, 17, 18, 19]. The issue of noise shows up in a multi-faceted way in
various areas of near-term quantum computation. In quantum machine learning,
certain types of noises cause ‘barren plateaus’ in optimization landscapes –
that is, the optimization landscape becomes flat, and any quantum signal is
destroyed [20, 21]. In random quantum circuit sampling [8], a popular
framework for demonstrations of quantum advantage, certain type of noise makes
it possible to simulate the systems efficiently classically [22]. However, the
vast majority of prior work assumes the noise to be local, unital, and
primitive (e.g., depolarizing)—where a quantum channel is deemed unital if it
maps the maximally mixed state onto itself, and primitive if any state
converges to the maximally mixed state if the channel is applied often enough.
However, for a number of current physical platforms, it is by far more natural
and realistic to consider the noise as non-unital [23, 4, 24, 25], which can
decrease the entropy of the system – to the extent that depolarizing noise can
be a misleading model. Previous results have studied the qualitatively
different behavior of this noise in certain contexts; for instance, fault
tolerance [26] and random circuit sampling [27].

In this work, we make significant strides in presenting a comprehensive
understanding of the impact of possibly non-unital noise on typical quantum
circuits. Our assumptions about the noise are minimal, in particular we
consider it to be _local_ and _incoherent_ , i.e., the noise present in the
device has a tensor product structure and it is not given by a unitary
channel. Our main results can be succinctly stated as follows:

  * •

Effective depth: We show that deep random quantum circuits, under _any_
uncorrected, possibly non-unital noise, effectively get ‘truncated’ in the
following sense: the influence of gates on Pauli expectation values decreases
exponentially in their distance from the last layer, i.e., only the last
layers contribute significantly to the expectation value.

  * •

Lack of barren plateaus: Because the effective circuit is always ‘shallow’, we
get a provable lack of barren plateaus for cost functions made out of local
observables—that is, the cost landscape is never flat, and the gradient of the
cost function never vanishes—at any depth, under non-unital noise. This also
implies that local expectation values of arbitrary deep random quantum
circuits with non-unital noise are _not too concentrated_ towards a fixed
value, in stark contrast to the unital noise scenario. This phenomenon,
however, is not good news for variational quantum algorithms [21], as we show
that such circuits behave like shallow circuits, which have limited
computational power.

  * •

Classical simulation: Furthermore, by exploiting the effective shallowness of
the circuits, we show how to classically simulate, on average over the class
of noisy quantum circuits, expectation values of any local observable, up to
$\varepsilon$ additive precision, at any depth, within runtime
$\mathrm{exp}(O(\mathrm{log}^{\mathrm{D}}(\varepsilon^{-2})))$,where
$\mathrm{D}$ is the spatial dimension of the system. So, for constant
precision, the algorithm is efficient for any constant spatial dimension, and
for inverse polynomial precision, the algorithm is efficient for one-
dimensional architectures.

Figure 1: For most of the quantum circuits with non-unital noise only the last
$O(\log(n))$ influence significantly the expectation values of local
observables. Here, $n$ is the number of qubits.

In summary, our results show that _most_ quantum circuits with non-unital
noise at _any_ depth behave qualitatively as (noisy) shallow quantum circuits
for the task of estimating Pauli expectation values. Beyond this task, we
further establish that the majority of noisy quantum circuits $\Phi$, with a
depth at least linear in the number of qubits, become independent to the
initial states – specifically, for any two states $\rho$ and $\sigma$, the
trace distance between $\Phi(\rho)$ and $\Phi(\sigma)$ vanishes exponentially
in the number of qubits.

Note that although we are significantly more general than many previous
results when it comes to noise model, our results hold only on average over a
well-motivated class of quantum circuits and do not apply to every circuit in
the class. However, this limitation is necessary; specifically, it reflects
the fact that not every quantum circuit without access to fresh auxiliary
systems becomes computationally trivial after a certain number of operations
under more general noise, unlike circuits subjected to depolarizing noise
[28]. For instance, Ref. [26] has shown that it is possible to perform
exponentially long quantum computations under non-unital noise, with specially
constructed circuits. Because of this, we cannot expect to prove our
statements for _all_ quantum circuits with non-unital noise.

From a technical perspective, our results rely on bounding various second
moments of observable expectation values under noisy random quantum circuits.
In particular, we show how combining a normal form of qubit channels [29] with
a reduction to ensembles of random Clifford circuits renders most computations
tractable. The only assumption we need is satisfied for any architecture where
the local gates form $2$-designs [30, 31], making our results widely
applicable. Taken together, our results substantially advance our
understanding of the noise impact on near-term quantum computation and
showcase that, unless we carefully engineer the circuits to take advantage of
the noise (e.g., as in Ref. [26]), it is unlikely that a quantum computer with
non-unital noise is preferable over one with depolarizing noise.

####  I.0.1 Related works

Previous studies have shown that circuits subjected to possibly non-unital
noise can produce output states that are effectively independent from their
input states [32, 33], i.e., they present a notion of an _effective depth_.
However, these studies explore regimes significantly and distinctly different
from ours. Specifically, Ref. [32] has shown that the output states of any
circuit with depth more than exponential in the number of qubits $n$, when
interleaved with non-unital noise, become effectively independent of the input
state. In our work, instead, we show that even linear-depth circuits can
accomplish this – although only on average over the circuit class. The same
cannot be shown for worst-case circuits because non-unital noise can be
leveraged to perform fault-tolerant quantum computation up to $O(\exp(n))$
depth without needing fresh ancillary qubits [26]. Furthermore, Ref. [33] has
shown that circuits, composed of $\Omega(n)$ layers of global $2$-designs
interspersed with non-unital noise, yield output states that are effectively
independent of their initial states. In contrast, we only assume that each of
the local two-qubit gate forms a $2$-design, which is arguably a more
realistic circuit model. Moreover, Refs. [34, 35] provide contraction bounds
for quantum annealers and limitations for the _quantum approximate
optimization algorithm_ (QAOA) which holds for several families of non-unital
noise. Here, we show that most quantum circuits with non-unital noise behave
like shallow quantum circuits for the task of computing Pauli expectation
values. In this regard, a line of research has delved into the limitations of
shallow quantum circuits in terms of their computational capabilities.
Notably, across a broad spectrum of combinatorial optimization problems,
classical algorithms outperform quantum algorithms implemented by shallow
quantum circuits [36, 37, 38, 34, 35, 39]. On the other hand, it has been
shown that shallow quantum circuits are unconditionally more powerful than
shallow classical circuits [40, 41, 42].

The interplay between barren plateaus, random circuits and noise has been
thoroughly explored by the previous literature in the context of _variational
quantum algorithms_ (VQAs) [21]. In the noiseless scenario, it has been
highlighted [43, 44] that if the parameter distribution underlying the
parametrized quantum circuit forms a global $2$-design [45], then any
associated cost function exhibits barren plateaus. The influence of the
locality of observables on the onset of barren plateaus has been explored in
Refs. [46, 47, 48]. Methods for avoiding or mitigating barren plateaus in
noiseless scenarios have been proposed, primarily relying on specific
heuristic-based initialization strategies [49, 50, 51, 52, 53, 44, 54], as
well as by constraining the circuit expressibility [55, 56, 57, 58, 59, 60,
61, 62, 63, 64]. Furthermore, it has been recently conjectured that methods to
‘provably’ avoid barren plateaus typically enable also efficient classical
simulation, either with purely classical resources or after an initial data
acquisition phase which may require a quantum computer [65]. In the context of
noisy scenarios, Ref. [20] showed that under the action of unital noise, both
cost functions and gradients experience exponential decay in the circuit
depth. This phenomenon has been dubbed ‘ _noise-induced barren plateaus_ ’
(NIBPs), and it has been considered as a major hurdle for VQAs since NIBPs
kick in regardless of the used initialization strategy [20] – crucially,
assuming unital noise. Another recent work [66] shows how barren plateaus can
emerge even with non-unital noise when the circuit is made by global
$2$-designs interleaved by non-unital noise. Our work is different from [66],
because we consider the arguably more realistic model in which the noise acts
after each local gate that composes the circuit. In Ref. [67], the authors
observed that properly engineered Markovian noise can prevent barren plateaus,
although their analysis holds for a single noisy layer.

In our work, we show how non-unital noise leads to strikingly different
conclusions than unital noise (e.g., depolarizing) in the context of barren
plateaus. We prove that parametrized quantum circuits made by $2$-qubit gates
(each of them being drawn from a $2$-design) do not exhibit exponential cost
function concentration at any depth, and that the gates in the last
$O(\log(n))$ layers of the circuit are (the only) trainable, implying absence
of barren plateaus. In contrast, in the depolarizing noise case, no gates are
trainable for sufficiently deep circuits [20], implying exponential cost
function concentration and the onset of barren plateaus. In other contexts, it
has been pointed out how non-unital noise can lead to drastically different
conclusions compared to unital noise. For example, in the context of fault-
tolerant quantum computation, it was shown [26] that while in the non-unital
noise scenario quantum computation is possible up to $O(\exp(n))$ depth
without the need for introducing _fresh_ ancillary qubits, in the depolarizing
noise scenario the same is possible only up to $O(\log(n))$ depth [68, 28], or
in the case of dephasing noise only up to $O(\mathrm{poly}(n))$ depth.
Moreover, Ref. [27] showed how existing easiness and hardness proofs [69, 70,
71] of random circuit sampling break down, under non-unital noise, because the
output distribution of the circuit is not ‘flat enough’—or in more technical
terms, it does not ‘anticoncentrate’ [72].

The pursuit of efficient classical simulation algorithms for quantum circuits
has also been addressed in previous research. The task of simulating
expectation values was addressed in several works (see, for instance, Ref.
[73] for shallow circuits and Ref. [74] for circuits interspersed by Pauli
noise). In particular, if the circuit is shallow and the observable is local,
then it is well-known that standard light-cone arguments suffice to compute
efficiently the expectation value [75, 73]. (See Ref. [76] for a discussion on
the strategy of considering light-cone arguments for estimating expectation
values of local observables with respect to tensor network states.) In the
case of noisy tensor network quantum states [77, 76], it has already been
pointed out that only the last layers of the circuit preparing such states are
sufficient for the estimation of local observables. In our work, we show that
most of the states prepared by arbitrary deep noisy random quantum circuits
have this property, leading to an efficient (average-case) classical
simulation algorithm leveraging this effective shallowness and light-cone
arguments. While for sufficiently deep circuits affected by depolarizing
noise, estimating the expectation value merely requires outputting the result
obtained from the maximally mixed state [28, 20]—yielding zero for Pauli
observables—in scenarios involving non-unital noise, such an approach does not
work, as we show that local expectation values of random quantum circuits with
non-unital noise are not very concentrated around a fixed value. For the task
of approximately generating samples from the output distribution of random
circuits interspersed by depolarizing noise, an efficient classical algorithm
has been provided in Ref. [22]. However, the same analysis of [22] does not
straightforwardly generalize to non-unital noise, as noted in Ref. [27],
because of the very peaked nature of the output distribution. Thus, designing
an efficient classical algorithm for this sampling task under non-unital noise
remains an open problem to date.

### Overview of the results

Our work is organized as follows:

  * -

In Subsection I.1, we prove the effective depth picture. Namely, we show that
the layers preceding the last $\Theta(\log(n))$ have negligible influence for
the task of estimating Pauli expectation values. Notably, here the only
assumption on the noise is that the associated channel is not a unitary
channel. Then, we also show that the trace distance between two arbitrary
states affected by the same linear depth noisy random quantum circuit becomes
exponentially small. In addition, we also investigate the impact of non-unital
noise on worst-case (i.e., any possible) quantum circuit. In particular, we
prove that, if the noise strength _exceeds_ a certain threshold, the layers at
superlogarithmic distance from the end bear a negligible influence on the
output state of _any_ circuit.

  * -

In Subsection I.2, leveraging the concept of effective shallowness, we present
a classical simulation algorithm for estimating local expectation values of
arbitrary deep noisy random quantum circuits. The algorithm’s core idea
capitalizes on the fact that local expectation values of shallow quantum
circuits can be computed efficiently through standard light-cone arguments.
Furthermore, we discuss a _verification condition_ that certifies the success
of the classical simulation for a given fixed circuit.

  * -

In Subsection I.3, we show that expectation values of local observables of
random quantum circuits with non-unital noise are not exponentially
concentrated towards a fixed value, in stark contrast to the unital noise
scenario. Moreover, we complement the results in Subsection I.1 by revealing
that the last $\Theta(\log(n))$ layers of random quantum circuits with non-
unital noise have a non-trivial impact on local expectation values. This
implies that non-unital noise induces an absence of barren plateaus at _any_
depth, for cost functions defined with respect to local expectation values.
Furthermore, we observe that cost functions defined with respect to global
Pauli observables exhibit exponential cost-concentation and barren plateaus at
any depth. Similarly, we show that fidelity quantum kernels [78, 79, 80],
well-studied quantities in the context of quantum machine learning, experience
exponential concentration at any depth under various noise models, including
both unital and non-unital channels – in contrast to projected quantum kernels
[81, 78]. For the special case of unital noise, we also present upper bounds
for barren plateaus and fidelity kernels with a substantial improvement
compared to previous results [82, 78], which are restricted only to certain
types of unital noise, whereas our results holds for general unital noise and
have a tighter dependence on the circuit depth.

The detailed technical aspects are covered extensively in the Supplementary
Material – here we give an overview of the main results.

####  I.0.2 Preliminaries and definitions

As many of our results rely on understanding how noise behaves _on average_
over circuits, we first introduce the circuit ensembles over which these
averages are taken. We consider $n$-qubit quantum circuits $\Phi$ consisting
of layers of two-qubit gates interleaved by local (single-qubit) noise, with a
final layer of single-qubit gates. All gates are assumed to be drawn from a
$2$-design, and we make no assumptions about geometric locality, except where
explicitly mentioned. We express our circuits as

$\displaystyle\Phi\coloneqq\mathcal{V}^{\mathrm{single}}\circ\mathcal{N}^{\otimes
n}\circ\mathcal{U}_{L}\circ\cdots\circ\mathcal{N}^{\otimes
n}\circ\mathcal{U}_{1},$ (1)

where $\mathcal{V}^{\mathrm{single}}\coloneqq V(\cdot)V^{\dagger}$, with
$V\coloneqq\bigotimes^{n}_{i=1}U_{i}$, is a layer of single-qubit gates, $L$
represents the number of layers, also referred to as circuit depth,
$\mathcal{U}_{i}$ corresponds to the channel associated with the $i$-th
unitary circuit layer for $i\in[L]\coloneqq\\{1,2,\dotsc,L\\}$, and
$\mathcal{N}$ is a single-qubit quantum channel. Exploiting the fact that we
draw gates from a two-qubit 2-design and we consider up to second-moment
quantities, without loss of generality, the underlying distributions of
unitaries do not change if we conjugate $\mathcal{N}$ on the left and right by
arbitrary unitary channels. Then, using the so-called ‘normal’ form
representation of the channel [29, 83], without loss of generality,
$\mathcal{N}$ can be defined in terms of two real vectors
$\mathbb{t}\coloneqq(t_{X},t_{Y},t_{Z})\in\mathbb{R}^{3}$ and
$\mathbb{D}\coloneqq(D_{X},D_{Y},D_{Z})\in\mathbb{R}^{3}$, describing its
action on a quantum state written in its Bloch sphere representation as

$\displaystyle\mathcal{N}\\!\left(\frac{I+\mathbb{w}\cdot\boldsymbol{\sigma}}{2}\right)=\frac{I}{2}+\frac{1}{2}(\mathbb{t}+D\mathbb{w})\cdot\boldsymbol{\sigma},$
(2)

where $D\coloneqq\mathrm{diag}(\mathbb{D})$, $\mathbb{w}\in\mathbb{R}^{3}$
with $\|\mathbb{w}\|_{2}\leq 1$, and $\boldsymbol{\sigma}\coloneqq(X,Y,Z)$ is
the vector of single-qubit Pauli matrices. In our work, it is crucial to
consider the constant
$c\coloneqq\frac{1}{3}(\|\mathbb{D}\|^{2}_{2}+\|\mathbb{t}\|^{2}_{2})$, as we
show that it quantifies the contraction rate with respect to the depth of our
noisy random circuits. Particularly, we show that $c\leq 1$, and the equality
holds if and only if $\mathcal{N}$ is a unitary channel. We will often analyze
noisy circuits in the Heisenberg picture. In particular, the adjoint channel
$\mathcal{N}^{*}$ acts on $Q\in\\{X,Y,Z\\}$ as

$\displaystyle\mathcal{N}^{*}(Q)=t_{Q}I+D_{Q}Q$ (3)

and on $I$ as $\mathcal{N}^{*}(I)=I$. Note that if the noise is unital, i.e.,
$\mathcal{N}(I)=I$, then we have $t_{Q}=0$ for all $Q\in\\{X,Y,Z\\}$.

###  I.1 Noise-induced effective shallow circuits

Here, we first present a high-level motivation for our investigation of the
effective depth of noisy quantum circuits with respect to the task of
estimating Pauli observables and then move to present our results formally.

#### Effective depth: a high-level motivation

The question of how uncorrected noise affects quantum computation has gained
prominence in the era of _noisy intermediate-scale quantum devices_ (NISQ) [1,
84], where resources for fault-tolerance are scarce. To address this question
for a commonly studied task, we investigate how non-unital noise impacts
quantum computations whose output is given by the expectation value of some
observable of interest, e.g., a Pauli observable $P$, or an estimation
thereof. A centerpiece of our work is the bound

$\mathbb{E}_{\Phi}[|\Tr(P\Phi(\rho-\sigma))|]\leq\exp(-\Omega(\mathrm{depth}(\Phi))),$
(4)

which holds for any two input states $\rho$ and $\sigma$. Here the expected
value $\mathbb{E}_{\Phi}$ is taken over the local gates that compose the
(possibly non-unital) noisy circuit $\Phi$ and that are assumed to be
distributed according to a local $2$-design. Several early results [68, 22,
85, 20] assumed that the noise in a circuit could be modeled as _single-qubit
depolarizing noise_. One result in this line [28] asserts that any circuit
$\Phi^{\mathrm{dep}}$ with depth $L=\Omega(\log(n))$ interspersed with layers
of depolarizing noise outputs the maximally-mixed state up to error which
vanishes exponentially in $L$ in trace distance as

$\lVert\Phi^{\mathrm{dep}}(\rho)-\mathbb{I}/2^{n}\rVert_{1}\leq
O(\sqrt{n}b^{L}),$ (5)

for some constant $b\in(0,1)$ that is independent of the state $\rho$. This
implies that also $|\Tr(P\Phi^{\mathrm{dep}}(\rho-\sigma))|$ is bounded from
above by $O(\sqrt{n}b^{L})$, for any two states $\rho$ and $\sigma$ and any
Pauli operator $P$. We refer to Section E.1 for a concise derivation of Eq.
(5). What is notable about this expression is that a single state—the
maximally-mixed state—is the ‘limit’ to which all circuits affected by
depolarizing noise converge, independent of what gates are actually in the
circuit, or its input state. The depolarizing noise assumption, if true,
enormously constrains noisy quantum algorithms outputting expectation values
and without access to fresh auxiliary qubits: to perform useful computation,
they should be executable within $O(\log(n))$ depth. According to Eq. (5), any
noisy circuit with depth larger than $O(\log(n))$ cannot be efficiently
distinguished by the maximally mixed state. Thus, for estimating Pauli
expectation values $P$ up to inverse polynomial error, one can always output
the fixed quantity $\Tr(P\,\mathbb{I}/2^{n})=0$. If the depth is
$O(\log(n)^{1/\mathrm{D}})$, where $\mathrm{D}$ is the spatial dimensionality
of the circuit, then Pauli expectation values of any quantum circuit
interspersed with depolarizing noise can be computed efficiently by standard
light-cone arguments (if the observable is local) or by exploiting the fact
that Pauli expectation values are exponentially suppressed with the Pauli
weight (if the observable is global). For one-dimensional architectures, this
provides an efficient classical simulation algorithm to estimate Pauli
expectation values of any circuit under depolarizing noise at any depth
111However, for spatial dimension $\mathrm{D}>1$, if the depth is between
$O(\log(n)^{1/\mathrm{D}})$ and $O(\log(n))$, to our knowledge it is not yet
known whether there is an efficient classical simulation algorithm..

However, one could justifiably raise concerns about this conclusion on
physical grounds. First, the noise in real hardware is not necessarily
depolarizing or even unital [23, 4, 24, 25]; secondly, even a slight departure
from the depolarizing noise assumption causes the picture to change
dramatically. For instance, consider the single-qubit dephasing noise
$\mathcal{D}$, which acts as
$\mathcal{D}(\rho)=(1-p)\rho+p\operatorname{diag}(\rho_{0,0},\rho_{1,1})$ for
some $p\in[0,1]$. Dephasing noise preserves the diagonal elements of its input
and thus still falls within the category of unital noise. Now, consider a
three-qubit circuit consisting of $L$ consecutive layers of Toffoli gates
interspersed with layers of dephasing noise: this noisy circuit acts as the
identity on the input states $\rho_{0}=\outerproduct{0,0,0}{0,0,0}$ and
$\sigma_{0}=\outerproduct{1,0,0}{1,0,0}$, no matter how deep it is. For these
two input states, Eq. (5) does not hold. This example illustrates the
impossibility of drawing any conclusions about expectation values like
$\Tr(Z_{1}\Phi(\rho))$ that depend only on the depth of the circuit—when the
noise is non-depolarizing, the actual gates in the circuit, as well as the
input state $\rho$, can affect the result very much.

Broadening our scope to general non-unital noise, the non-trivial nature of
analyzing arbitrary circuits under such noise arises from the following
intuition. Unital noise preserves the maximally-mixed state, and so does any
unitary. Thus, a circuit consisting of alternating layers of unitaries and
unital noise has both its unitary and noise components acting ‘in tandem’ to
drive the state towards the maximally-mixed state. When the noise is non-
unital, however, the unitary and the noise components of the circuit do not
have the same fixed point, and thus can be understood to be acting ‘in
different directions’. Little is known about the behaviour of these noisy
circuit ensembles—a debate to which we hope to contribute with Eq. (4). The
expected value $\mathbb{E}_{\Phi}$ in Eq. (4) is taken to avoid pathological
cases: as previously noticed, on worst-case circuits the quantity
$|\Tr(P\Phi(\rho-\sigma))|$ may attain a constant value independent of depth
for certain kinds of noise, such as the dephasing channel. Moreover, the so-
called _quantum refrigerator_ construction [26] shows surprisingly how non-
unital noise can be leveraged to perform fault-tolerant quantum computation
for up to exponential depth with circuits similar to ours. Therefore, for
these special classes of circuits, we do not expect this worst-case upper
bound to hold.

Although contraction results for worst-case circuits have appeared in the
literature [28, 34, 87], they encompass a less general class of channels than
those considered in the present work. Thus, proving a contraction result for
general—possibly non-unital—noise is far from trivial, and to our knowledge,
our work provides the strongest result in this regard, by crucially leveraging
the randomness of the circuit.

#### Effective depth: formal result

In this subsection, we formally present our results concerning the effective
depth of arbitrary deep random quantum circuits under possibly non-unital
noise, with respect the task of estimating Pauli expectation values. Our
results reveal that the influence of gates on Pauli expectation values
decreases exponentially with their distance from the last layer. See Fig. 1
for a graphical representation. Our main result can be stated as follows.

######  Proposition 1 (Effective logarithmic depth).

Let $P\in\\{I,X,Y,Z\\}^{\otimes n}$, $\rho_{0}$ be any initial state, $L$ be
the depth of the noisy circuit $\Phi$, and $l\in\mathbb{N}$. We assume that
the noise in the circuit is not a unitary channel. Then, we have

$\displaystyle\mathbb{E}_{\Phi}[|\Tr(P\Phi(\rho_{0}))-\Tr(P\Phi_{[L-l,L]}(\rho_{0}))|]\leq\exp(-\Omega(l)).$
(6)

Here, $\Phi_{[L-l,L]}(\cdot)$ refers to the noisy circuit where only the last
$l$ layers are considered, the average $\mathbb{E}_{\Phi}$ is taken with
respect to the $2$-design distribution of every two-qubit gate that composes
the circuit, and $\Omega(\cdot)$ hides noise parameters.

By Markov’s inequality, this result directly implies that, for most noisy
arbitrary deep quantum circuits, considering only the last $\Theta(\log(n))$
layers suffices to obtain an estimate of any Pauli expectation value with
precision scaling inverse-polynomially with the number of qubits. This result
is a particular case of the following more general statement.

######  Theorem 2 (General scaling).

Let $\rho$ and $\sigma$ be arbitrary quantum states,
$P\in\\{I,X,Y,Z\\}^{\otimes n}$ with Pauli weight $|P|$, and $L$ be the depth
of the noisy circuit. Assuming that the noise is not a unitary channel, we
have

$\displaystyle\mathbb{E}_{\Phi}[\Tr(P\Phi(\rho-\sigma))^{2}]\leq\exp(-\Omega(L+|P|)).$
(7)

Specifically, the upper bound that we prove is $O(c^{L+|P|})$, where $c<1$ is
the constant defined in the preliminary Subsection I.0.2. We now provide a
sketch of the proof of Theorem 2. At a high level, the proof works by going
into the Heisenberg picture, ‘peeling off’ a unitary and noisy layer of the
depth-$L$ circuit, and then applying the adjoint of these layers to the Pauli
$P$. Using properties of the random circuit and that of the noise channel, we
then show that this recovers a Pauli expectation value on a noisy circuit of
depth $L-1$, which puts us in the position to reiterate the argument.

###### Proof sketch of Theorem 2.

Because our local two-qubit gates are drawn from a $2$-design and we are
computing a second moment, we can assume that all gates are Clifford [88] and
that the noise channels are in their normal form. Let $\tilde{\Phi}$ be a
noisy circuit of depth $L-1$ and let $\Phi$ be a noisy circuit of depth $L$.
That is, $\Phi=\mathcal{V}^{\mathrm{single}}\circ\mathcal{N}^{\otimes
n}\circ\mathcal{U}_{L}\circ\tilde{\Phi}$, where we used the same notation
defined in Eq. (1). Averaging over the last layer of single-qubit unitaries,
we have

$\displaystyle\mathbb{E}[\Tr(P\Phi(\rho-\sigma))^{2}]=\frac{1}{3^{|P|}}\sum_{\begin{subarray}{c}Q\in\\{I,X,Y,Z\\}^{\otimes
n}:\\\
\operatorname{supp}(Q)=\operatorname{supp}(P)\end{subarray}}\mathbb{E}\left[\Tr(Q\,\mathcal{N}^{\otimes
n}\circ\mathcal{U}_{L}\circ\tilde{\Phi}(\rho-\sigma))^{2}\right].$

Taking the adjoint of the layer of noise $\mathcal{N}^{\otimes n}$ and using
properties of the random gates that compose the unitary layer
$\mathcal{U}_{L}$, we have

$\displaystyle\mathbb{E}\\!\left[\Tr(Q\,\mathcal{N}^{\otimes
n}\circ\mathcal{U}_{L}\circ\tilde{\Phi}(\rho-\sigma))^{2}\right]$
$\displaystyle=\sum_{a\in\\{0,1\\}^{|Q|}}\prod_{j\in\operatorname{supp}(Q)}(t^{a_{j}}_{Q_{j}}D^{1-a_{j}}_{Q_{j}})^{2}\mathbb{E}\\!\left[\Tr(\left(\bigotimes_{j\in\operatorname{supp}(Q)}Q^{1-a_{j}}_{j}\right)\mathcal{U}_{L}\circ\tilde{\Phi}(\rho-\sigma))^{2}\right].$

Thus, taking the adjoint of the last unitary layer on the Pauli and using the
fact that it is made of Clifford gates, which map a Pauli observable to
another Pauli observable, we have

$\displaystyle\mathbb{E}[\Tr(P\Phi(\rho-\sigma))^{2}]$
$\displaystyle\leq\frac{1}{3^{|P|}}\sum_{\begin{subarray}{c}Q\in\\{I,X,Y,Z\\}^{\otimes
n}:\\\
\operatorname{supp}(Q)=\operatorname{supp}(P)\end{subarray}}\sum_{a\in\\{0,1\\}^{|Q|}}\prod_{j\in\operatorname{supp}(Q)}(t^{a_{j}}_{Q_{j}}D^{1-a_{j}}_{Q_{j}})^{2}\max_{Q\in\\{I,X,Y,Z\\}^{\otimes
n}}\mathbb{E}\\!\left[\Tr(Q\,\tilde{\Phi}(\rho-\sigma))^{2}\right]$
$\displaystyle=\frac{1}{3^{|P|}}(\|\mathbb{D}\|^{2}_{2}+\|\mathbb{t}\|^{2}_{2})^{|P|}\max_{Q\in\\{I,X,Y,Z\\}^{\otimes
n}}\mathbb{E}\\!\left[\Tr(Q\tilde{\Phi}(\rho-\sigma))^{2}\right]$ (8)
$\displaystyle=c^{|P|}\max_{Q\in\\{I,X,Y,Z\\}^{\otimes
n}}\mathbb{E}\\!\left[\Tr(Q\tilde{\Phi}(\rho-\sigma))^{2}\right],$

where we have used the multinomial theorem and the definition of $c$ given in
Subsection I.0.2. In the Supplementary Material, we prove that $c<1$ for every
single-qubit channel that is not unitary. Moreover, we can assume that the
maximum over the Paulis is not achieved by the identity because otherwise the
RHS would be zero since $\tilde{\Phi}$ is trace preserving and $\rho-\sigma$
is traceless. Reiterating the argument to the remaining circuit layers
establishes the claim. ∎

By Jensen’s inequality, we obtain

$\mathbb{E}[|\Tr(P\Phi(\rho))-\Tr(P\Phi(\sigma))|]\leq\exp(-\Omega(L+|P|)).$
(9)

Particularly, this also directly proves Proposition 1. As an implication of
the previous result, we can show that at linear depth $L=\Omega(n)$, the
average trace distance between two states affected by the same noisy quantum
circuit becomes exponentially small in the number of qubits:

$\displaystyle\mathbb{E}_{\Phi}[\norm*{\Phi(\rho)-\Phi(\sigma)}_{1}]\leq\exp(-\Omega(n)).$
(10)

This implies that the application of the same linear depth random circuit
affected by any amount of noise on two different input states renders them
effectively indistinguishable (because of the Holevo-Helstrom theorem [89]).
To our knowledge, this is the first result of this kind; except for the result
of Ref. [32], which only applies to exponential depths but which holds for
worst-case circuits, whereas our statement hold on average. As mentioned in
Subsection I.1, it is in principle not possible to prove our result for worst-
case circuits, because there are some special classes of circuits [26] that
would violate a worst-case version of our inequality (i.e., Eq. (10) without
the expectation value). However, when the noise strength exceeds a certain
threshold, we can show a worst-case upper bound on the trace distance that
decays exponentially in the number of qubits. Specifically, we show the
following.

######  Proposition 3 (Worst-case effective depth with high noise).

For a given noise channel, let $b\coloneqq
12\max_{P\in\\{X,Y,Z\\}}\frac{D_{P}}{1-D_{P}}$, where $D_{P}$ with
$P\in\\{X,Y,Z\\}$ is the noise parameter defined in the preliminary Subsection
I.0.2. Let $\Phi$ be a noisy random quantum circuit with of depth $L$, then
the trace distance satisfies

$\displaystyle\|\Phi(\rho)-\Phi(\sigma)\|_{1}\leq nb^{L}\|\rho-\sigma\|_{1}.$
(11)

Thus, for any $\varepsilon>0$, assuming that $b<1$ and
$L\geq\frac{1}{\log(b^{-1})}\Omega\\!\left(\log(\frac{n}{\varepsilon})\right)$,
we have that $\norm*{\Phi(\rho)-\Phi(\sigma)}_{1}\leq\varepsilon$.

The proof relies on passing to the quantum Wasserstein distance of order $1$
[35], computing contraction coefficients and passing back to the trace
distance using techniques laid out in Ref. [35]. Such results are known in the
literature as reverse threshold theorems, as they show that for high enough
noise rate error correction is not possible [90, 91, 92]. In contrast to
previous results, we also extend them to non-unital channels.

###  I.2 Classical simulation of random quantum circuits with possibly non-
unital noise

We have shown that the presence of any non-unitary noise renders _most_
circuits effectively shallow, for the task of estimating Pauli expectation
values. Specifically, Theorem 2 establishes that for any $L$-depth circuit
$\Phi$ and Pauli $P$, the inequality

$\displaystyle\mathbb{E}_{\Phi}[|\Tr(P\Phi(\outerproduct{0^{n}}{0^{n}}))-\Tr(P\Phi_{[L-l,L]}(\outerproduct{0^{n}}{0^{n}}))|]\leq\exp(-\Omega(l+|P|))$
(12)

holds, where $\Phi_{[L-l,L]}(\cdot)$ refers to the noisy circuit where only
the last $l$ layers are considered. Eq. (12) leads to a simple classical
algorithm for estimating local Pauli expectation values to additive error:
work in the Heisenberg picture and ‘propagate’ the local Pauli $P$ only a few
layers backward; compute the matrix $P_{l}\coloneqq\Phi^{*}_{[L-l,L]}(P)$ and
evaluate $\Tr(P_{l}\outerproduct{0^{n}}{0^{n}})$. Assuming a geometrically
local circuit architecture with constant dimension $\mathrm{D}$, this
algorithm has a total time complexity bounded above by
$\exp(O((|P|+l)^{\mathrm{D}}))$, independent of the number of qubits (because
of light-cone arguments). Its guarantees can be proven via Markov inequality
applied to Eq. (12). More specifically, we have the following.

######  Proposition 4 (Average classical simulation of local expectation
values).

Let $\varepsilon,\delta>0$. Consider $P\in\\{I,X,Y,Z\\}^{\otimes n}$, and let
$\rho_{0}\coloneqq\outerproduct{0^{n}}{0^{n}}$. For a noisy
$\mathrm{D}$-dimensional geometrically-local quantum circuit $\Phi$ of depth
$L$, sampled according to the described circuit distribution, there exists a
classical algorithm that outputs a value $\hat{C}$ satisfying

$\displaystyle|\hat{C}-\Tr(P\Phi(\rho_{0}))|\leq\varepsilon$ (13)

with at least $1-\delta$ probability of success. Specifically, the classical
algorithm involves computing $\hat{C}\coloneqq\Tr(P\Phi_{[L-l,L]}(\rho_{0}))$
with

$\displaystyle
l\coloneqq\left\lceil\frac{1}{\log(c^{-1})}\log(\frac{4}{\delta\varepsilon^{2}})\right\rceil,$
(14)

where $c$ is the noise parameter defined in the preliminary Subsection I.0.2.
Its runtime is bounded from above as

$\displaystyle\mathrm{Runtime}\leq\exp\\!\left[O\\!\left(\left(|P|+\frac{1}{\log(c^{-1})}\log\\!\left(\frac{1}{\varepsilon^{2}\delta}\right)\right)^{\mathrm{D}}\right)\right].$
(15)

In particular, the runtime is polynomial in the inverse of the precision for
one-dimensional architectures, and quasi-polynomial for higher-dimensional
architectures. Furthermore, in the Supplementary Material, we provide an
alternative _early-break condition_ that, if met at some step $t$, guarantees
an $\varepsilon$ approximation. This allows us to stop ’unraveling’ the
circuit and simply output $P_{t}\coloneqq\Phi^{*}_{[L-t,L]}(P)$ with the
current value of $P_{t}$. The condition to check is

$\min_{c\in\mathbb{R}}\,\lVert P_{t}-cI\rVert_{\infty}\leq\varepsilon/2.$ (16)

Moreover, if this condition is satisfied, we can be certain to have
successfully estimated the expectation value. Checking this condition can be
done with runtime $\exp(O((|P|+t)^{\mathrm{D}}))$ by solving a semi-definite
problem (SDP) with an analytical solution which we provide in the
Supplementary Material. The intuition behind this verification step is that if
$P_{t}$ were proportional to the identity, then adding further (adjoint)
layers would not change the matrix $P_{t}$, due to unitality of the adjoint
channel.

Upon inspecting our proof of Theorem 2, it is evident that we often make
conservative estimates on the contraction at each step, as it is proportional
to exponential in the locality of the input Pauli, and we always bound this
from below by $1$. Thus, by incorporating a finer analysis of the dynamics of
the weight, we conjecture that it is possible to show that this early-break
condition will be met before the runtime stated in Proposition 4 with high
probability. We leave the proof of this conjecture open for future work.

The above algorithm is efficient if the weight of the Pauli $P$ is
$|P|=O(\log(n))$ (i.e., its time complexity runs polynomially in the number of
qubits), and it is no longer efficient otherwise. However, in the regime of
high Pauli weight, no algorithm execution is necessary. Instead, we can simply
output zero and ensure, with high probability, an inverse-polynomial accuracy
in the number of qubits, as detailed in our Supplementary Material. This stems
from the fact that for any noise that is not a unitary channel, we have

$\displaystyle\mathbb{E}_{\Phi}(\Tr(P\Phi(\rho_{0})))=0,\quad\mathrm{Var}_{\Phi}(\Tr(P\Phi(\rho_{0})))\leq\exp(\Omega(-|P|)),$
(17)

followed by an application of Chebyshev’s inequality. We can then summarize
our result as follows.

######  Remark 5 (Estimating classically any Pauli expectation value).

There is an algorithm for estimating any Pauli expectation value of noisy
random quantum circuits at any depth, up to an inverse polynomial precision in
the number of qubits. The runtime of the algorithm is polynomial in the number
of qubits for one-dimensional architectures and quasi-polynomial for higher-
dimensional ones.

It is worth mentioning that quantum circuits with non-unital noise can have
Pauli expectation values of local observables significantly far from zero also
in the high-depth regime. We show this in the next section. This is in stark
contrast to the case of circuits with, e.g., depolarizing noise, in which
Pauli expectation values decay exponentially to zero in the circuit depth [28,
20], which implies that outputting zero suffices to estimate accurately the
expectation value for sufficiently deep circuits. This strategy does not work
as a classical simulation algorithm for circuits affected non-unital noise,
for the reason mentioned in the first sentence of this paragraph.

###  I.3 Lack of barren plateaus with non-unital noise, but only the last
$\Theta(\log(n))$ layers matter

The _barren plateaus phenomenon_ [43, 20], has been considered one of the main
hurdles for _variational quantum algorithms_ (VQAs) [21]. These algorithms
involve encoding the solution to a problem in the minimization of a cost
function, typically defined in terms of expectation values of observables,
with the free parameters for optimization being the gate parameters. Barren
plateaus are characterized by the phenomenon where the norm of the gradient of
the cost function, on average, vanishes exponentially in the number $n$ of
qubits. Consequently, in the presence of barren plateaus, randomly selecting
an instance of the parameterized circuit would overwhelmingly lead to a
circuit instance situated within a region of the landscape necessitating an
exponential number of measurements to navigate, implying loss of any potential
quantum advantage. There are two signatures of barren plateaus: exponential
concentration of the cost function around a fixed value, and the fact that the
norm of the gradient of the cost function is exponentially small. We show that
both are avoided in the non-unital noise scenario for cost functions made by
local observables. However, we will see that this absence of barren plateaus
is only due to the last $\Theta(\log(n))$ layers of the circuit, while the
gradient contribution coming from the preceding layers is negligible. This is
essentially a consequence of what we have explored in the preceding sections:
we are working with circuits that exhibit an effective logarithmic depth.

####  I.3.1 Lack of exponential concentration for local cost functions with
non-unital noise

We consider a circuit $\Phi$ as we have described in Subsection I.0.2, where
the local noise channels are characterized by the parameters of their normal
form representation $\mathbb{t}\coloneqq(t_{X},t_{Y},t_{Z})$ and
$\mathbb{D}\coloneqq(D_{X},D_{Y},D_{Z})$, which we assume to be constants with
respect to the number of qubits. Our first main theorem is the following.

######  Theorem 6 (Variance of expectation values of random circuits with non-
unital noise).

Let $H\coloneqq\sum_{P\in\\{I,X,Y,Z\\}^{\otimes n}}a_{P}P$ be an arbitrary
Hamiltonian, with $a_{P}\in\mathbb{R}$ for $P\in\\{I,X,Y,Z\\}^{\otimes n}$.
Let $\rho$ be a quantum state. We assume that the noise is non-unital and that
$\norm*{\mathbb{t}}_{2}=\Theta(1)$. Then, at any depth, we have

$\displaystyle\mathrm{Var}_{\Phi}[\Tr(H\Phi(\rho))]=\sum_{P\in\\{I,X,Y,Z\\}^{\otimes
n}}a_{P}^{2}\exp(-\Theta(|P|)).$ (18)

The proof of this theorem is provided in the Supplementary Material. Note that
the variance scaling in the non-unital noise scenario is independent of the
circuit depth, which contrasts sharply with noiseless random quantum circuits
or circuits with unital noise [48, 20], where the variance becomes
exponentially small in the number of qubits at sufficiently high depth. Our
Theorem 6 directly implies that, under non-unital noise, the variance of
_local cost functions_ —i.e., expectation values of local observables, e.g.,
$\Tr(Z_{1}\Phi(\rho))$—is significantly large.

######  Corollary 7 (Lack of exponential concentration for local cost
functions).

Let $\rho$ be any quantum state, $P$ be a local Pauli ($|P|=\Theta(1)$), and
$\Phi$ be the noisy random circuit ansatz. Under the same noise assumptions as
above, at any circuit depth, we have

$\displaystyle\mathrm{Var}_{\Phi}[\Tr(P\Phi(\rho))]=\Theta(1).$ (19)

In particular, the lower bound on the variance that we prove is
$\frac{1}{3}\|\mathbb{t}\|^{2|P|}_{2}$. Here, $\|\mathbb{t}\|_{2}$ is the
noise-parameter, which quantifies the non-unitality of the channel. As
expected, if the noise is unital ($\|\mathbb{t}\|_{2}=0$), we get a vacuous
zero lower bound. It is interesting to note that even a _tiny_ deviation from
the unitality assumption, i.e., if the non-unital noise parameter
$\|\mathbb{t}\|_{2}$ scales inverse-polynomially with the number of qubits,
the variance is not exponentially small. This implies that local expectation
values under non-unital noise are not ‘too concentrated’ around their mean
value $\mathbb{E}_{\Phi}[\Tr(P\Phi(\rho))]=0$, in contrast with the
depolarizing noise scenario, in which case the variance decays exponentially
with the depth [20]. However, we show that global cost functions—i.e.,
expectation values of high Pauli weight observables, e.g., $\Tr(Z^{\otimes
n}\Phi(\rho))$—still exhibit exponential concentration, as in the noiseless
case [46, 48] and in the depolarizing noise scenario. Formally, we find the
following cost concentration.

######  Corollary 8 (Cost concentration for global expectation values).

Let $P\in\\{I,X,Y,Z\\}^{\otimes n}$ with Pauli weight $|P|=\Theta(n)$.
Assuming that the noise is not a unitary channel, for any constant noise
parameters, we have

$\displaystyle\mathrm{Var}_{\Phi}[\Tr(P\Phi(\rho))]\leq\exp(-\Omega(n)).$ (20)

####  I.3.2 Lack of vanishing gradients for local cost functions, but only the
last $\Theta(\log(n))$ layers are trainable

The effective depth of noisy random circuits, elucidated in Section I.1,
implies that, on average, changing the gates in the layers preceding the last
$\Theta(\log(n))$ will not significantly influence the Pauli expectation
value. This suggests that only the last few layers of the circuit can
substantially alter the expectation value. We analyze this formally using the
notion of ‘trainability’ of a parametrized gate. As is common in the
literature [21, 65], we refer to a cost function $C$ as trainable with respect
to a parametrized gate labeled by $\mu$ if and only if
$\mathrm{Var}[\partial_{\mu}C]=\Omega(1/\mathrm{poly}(n))$, that is, the
variance of the cost function partial derivative with respect to such a
parameter vanishes no more than inverse-polynomially in the number of qubits.
For a formal definition of cost function partial derivatives and detailed
proofs of the following results, we refer to the Supplementary Material. We
rigorously show that for local cost functions, under non-unital noise, only
the last $\Theta(\log(n))$ layers of the circuit are trainable, meaning they
have significantly large partial derivatives.

######  Theorem 9 (Only the last few layers are trainable for local cost
functions).

Let $C=\Tr(P\Phi(\rho_{0}))$ be a cost function associated with a local Pauli
$P$ (with Pauli weight $|P|=\Theta(1)$), an initial state $\rho_{0}$, and a
depth-$L$ noisy random circuit ansatz $\Phi$ in arbitrary constant dimension.
Let $\mu$ be a parameter (in the light cone) of the $k$-th layer. Assume that
the noise is not unital and it is not a replacer channel (i.e., it does not
output a fixed state). Then, we have

$\displaystyle\mathrm{Var}[\partial_{\mu}C]=\exp(-\Theta(L-k)).$ (21)

Theorem 9 states that local cost functions are mostly sensitive to changes of
parameters in the last few layers. This is in stark contrast to the case of
depolarizing noise or the noiseless case, in which the partial derivative
variances with respect to gates in _all_ the layers are exponentially
suppressed with the number of qubits at sufficiently high depth [20, 93, 48].

As a corollary of the previous theorem, we have that the norm of the gradient
of local cost functions does not exponentially vanish in the number of qubits
at any depth. Crucially, this fact is only due to the last few layers of the
circuits, which we have shown to be trainable.

######  Corollary 10 (Non-vanishing gradient for local cost functions with
non-unital noise).

Let $\rho_{0}$ be any quantum state and $P$ be a local Pauli. Let
$C:=\Tr(P\Phi(\rho_{0}))$ be the cost function associated with a noisy random
quantum circuit ansatz of any depth. We assume that the noise is non-unital
and it is not a replacer channel (i.e., it does not output a fixed state).
Then, we have

$\displaystyle\mathbb{E}[\norm*{\nabla C}_{2}^{2}]=\Theta(1).$ (22)

In the Supplementary Material, we also show that global cost functions—i.e.,
those cost functions associated with high-weight Pauli observables—have all
partial derivative variances exponentially vanishing in the number of qubits,
and therefore also their gradients. Furthermore, in the Supplementary
Material, we present numerical simulations that corroborate our findings and
attempt to extend beyond the assumptions of our theorems, such as the
assumption that two-qubit gates are sampled from a $2$-design. We provide
evidence that even for more restricted classes of ansätze, such as QAOA [94],
the same qualitative behavior is observed.

####  I.3.3 Improved upper bounds for barren plateaus in the unital noise
scenario

The technical tools developed in this work also allow us, in the unital-noise
scenario, to improve upon the barren plateaus upper bounds presented in Ref.
[20]. In particular, we establish the following.

######  Proposition 11 (Improved upper bound on the partial derivative for
unital noise).

Let $C\coloneqq\Tr(P\Phi(\rho))$ be the cost function, where $P$ is a Pauli,
$\rho$ is an arbitrary initial state, and $\Phi$ is a random quantum circuit
ansatz of depth $L$ in arbitrary dimension. We assume that the noise is unital
and not unitary. Let $\mu$ denote a parameter of any $2$-qubit gate
$\exp(-i\theta_{\mu}H_{\mu})$ in the circuit such that
$\norm*{H_{\mu}}_{\infty}\leq 1$. Then, we have

$\displaystyle\mathrm{Var}[\partial_{\mu}C]\leq\exp(-\Omega(|P|+L)).$ (23)

It is noteworthy that the upper bound of Ref. [20] has no dependence on the
Pauli weight, unlike ours. Furthermore, the upper bound of Ref. [20] includes
an $n^{1/2}$ factor in front of the exponential decay in $L$, making it
meaningful only at depths $\Omega(\log(n))$, whereas our result is without
such a factor. Moreover, our result is more general than that shown in [20]
because it extends to any unital noise, whereas the results shown in Ref. [20]
apply only to primitive Pauli noise, which is only a particular type of unital
noise (e.g., dephasing is not included in this class).

####  I.3.4 Exponential concentration and lack thereof in noisy kernels

As a complementary result, we demonstrate how quantum kernels [78, 79, 80]
exhibit a similar behavior to cost functions under the influence of non-unital
noise. We show that fidelity quantum kernels [78, 79, 80] can incur an
exponential concentration at any depth, whereas projected quantum kernels [81,
78] never exhibit exponential concentration. This stark discrepancy is
analogous to that witnessed for global cost functions and local cost
functions. In particular, assuming that the noise parameters satisfy
$\|\mathbb{t}\|_{2}^{2}+\|\mathbb{D}\|_{2}^{2}<1$, we show that

$\mathbb{E}_{\Phi,\Phi^{\prime}}[\Tr[\Phi(\rho)\Phi^{\prime}(\rho)]]\leq\mathrm{exp}(-\Omega(n)),$
(24)

for any two noisy quantum circuits $\Phi$ and $\Phi^{\prime}$, where the
expectation is taken over the random gates in both the circuits. This result
follows by upper bounding the overlap of two states in terms of their purities
by the Cauchy-Schwarz inequality, expanding the expected purities in the Pauli
basis, and upper bounding the contribution of each Pauli by means of Theorem
6.

Furthermore, we are able to show worst-case concentration bounds by
introducing an additional assumption on the noise model. In particular, we
assume that the noise channel $\widetilde{\mathcal{N}}$ is the composition of
the depolarizing channel ${\mathcal{N}_{p}^{(\mathrm{dep})}}$ with constant
$p>0$ and an arbitrary noise channel with $\norm*{\mathbb{t}}_{2}<1$, i.e.,
$\widetilde{\mathcal{N}}:=\mathcal{N}\circ{\mathcal{N}_{p}^{(\mathrm{dep})}}$.
Thus, we obtain that

$\Tr[\Phi(\rho)\Phi^{\prime}(\rho)]\leq 2^{n(\delta_{L}-1)},$ (25)

where
$\delta_{L}\coloneqq(1-p)^{2L}+\|\mathbb{t}\|_{2}\frac{1-(1-p)^{2L}}{2p-p^{2}}$.

We emphasize that, when the noise is purely depolarizing, i.e.
$\norm*{\mathbb{t}}_{2}=0$, this bound predicts exponential concentration at
any depth, thus improving a previous result given in Ref. [78], predicting
exponential concentration at linear depth.

As for the projected quantum kernels [81, 78], we show the result

$\displaystyle\mathrm{Var}_{\Phi,\Phi^{\prime}}\\!\left[\sum_{k=1}^{n}\left[\|\Phi_{k}(\rho)-\Phi^{\prime}_{k}(\rho)\|_{2}^{2}\right]\right]\geq\Omega(n\|\mathbb{t}\|^{4}_{2}),$
(26)

where $\Phi_{k}(\rho)=\Tr_{[n]\setminus\\{k\\}}\Phi(\rho)$. We remark that the
analysis of projected quantum kernels involves some additional assumptions on
the families of random circuits, which are formally defined in Section D.2.

##  II Conclusions

Our work substantially advances our understanding of how quantum
circuits—specifically, random quantum circuits—behave under possibly non-
unital noise on several fronts, developing a comprehensive picture of the
impact of noise. First, we have shown what we called the effective depth
picture, establishing that most quantum circuits under non-unital noise behave
like shallow circuits, no matter how deep they are. We have also shown that
the output is essentially independent of the input state or the initial gates
in the circuit. These statements have followed from various average
contraction results.

We have then used our effective depth picture to argue that, in contrast to
the noiseless and unital cases, in the presence of non-unital noise,
variational quantum algorithms do not suffer from barren plateaus. This is a
striking insight in its own right. But it is important to contextualize this
result and not think that it is good news: Indeed, we show that the lack of
barren plateaus emerges from the fact that these circuits behave similarly to
shallow circuits and that just the last few layers are trainable.

We have also used this fact to come up with a simple classical simulation
algorithm for estimating Pauli expectation values of quantum circuits under
non-unital noise, on average over the ensemble. Furthermore, we have shown
that the algorithm is efficient for inverse-polynomial precision even for
arbitrarily deep circuits in one-dimensional architectures, and for constant
precision in any spatial dimensions. In short, a good way of summarizing our
results is that we show that, unless we carefully exploit the structure of the
noise affecting the quantum device, as long as we are interested in using a
noisy quantum device to estimate Pauli expectation values, it is unlikely that
one affected by local depolarizing noise is preferable over one with non-
unital with a similar rate. The result can also be seen as an invitation to
more carefully investigate the underlying noise to draw precise conclusions
about the anticipated quantum application, and that overly simplified models
can be misleading.

### Open problems

Our results invite a number of follow-up research questions. In particular,
they leave open two important problems about random circuits with non-unital
noise.

#### Sampling from random quantum circuits under non-unital noise

In Ref. [22], an algorithm has been presented to efficiently sample from
random quantum circuits under local depolarizing noise of $\Theta(\log(n))$
depth. However, the techniques outlined in Ref. [22] do not seem to be
applicable under non-unital noise due to the fact that such circuits do not
anticoncentrate, i.e., their output distribution never becomes sufficiently
uniform [27]. In addition, unlike circuits with depolarizing noise [95, 28] or
most circuits with other unital noise sources [96], non-unital noisy circuits
do not converge to the maximally mixed state. Thus, the complexity of sampling
from random quantum circuits with non-unital noise remains an interesting open
question. See also the discussion related to this open question in Ref. [27].
Our work brings a new perspective that may provide new insights to address
this fundamental open question. Specifically, our work suggests that random
quantum circuits with non-unital noise behave effectively as logarithmic-depth
noisy circuits—in particular, only the last $O(\log(n)))$ layers seem to
matter. Moreover, Ref. [27] has shown that the outcome probability
distribution of random quantum circuits under non-unital noise is never ‘too
flat’, i.e., it is quite peaked. These results impose quite a lot of structure
on such random circuits with non-unital noise—it seems that we are dealing
with effective noisy random quantum circuits that are both shallow and peaked.
Interestingly, it has recently been shown how to efficiently sample
classically from two-dimensional (constant depth) shallow peaked circuits [97]
– even though their definition of a distribution being ‘peaked’ is stronger
than that used in Ref. [27], and their definition of a circuit being ‘shallow’
refers to a constant depth circuit, whereas for us, it refers to a logarithmic
depth circuit. However, the algorithm proposed in Ref. [97] works for all
circuits (worst-case scenario) – whereas in our case we only need an average
case statement, since we consider random circuits, which could potentially
simplify the problem due to the fact that we are asking to generate
approximately correct samples ‘only’ with high probability over the ensemble
and not in the worst case. That said, we leave to future work the rigorous
exploration of whether the ideas developed in our work can be used to design
such a classical sampling algorithm or to establish that the task is hard for
classical computers.

#### Estimating Pauli expectation values efficiently in arbitrary dimension
within inverse-polynomial precision

The classical algorithm we formulated in Section I.2 to estimate Pauli
expectation values with precision $O(1/\mathrm{poly}(n))$ runs in polynomial
time for $1$-D architectures, but in quasipolynomial time for $2$-D
architectures. Other classical algorithms for estimating Pauli expectation
values of constant depth quantum circuits [98] also run in quasi-polynomial
time. It remains open whether we could construct a polynomial time algorithm
to estimate, within inverse-polynomial precision, expectation values of local
observables, under random circuits with non-unital noise, in $2$-D. It must be
also pointed out that our algorithm might be improved by use of more
sophisticated techniques, like tensor network methods. Additionally, it also
remains open whether the early break condition in Eq. (16) is met with high
probability over the ensemble.

#### Acknowledgements

AAM thanks Lennart Bittel for useful discussions regarding the partial
derivative lower bound. AAM and AA thank Marco Cerezo and Samson Wang for
useful discussions on their previous work [20]. AA thanks Giacomo De Palma and
Isabella Uta Meyer for discussions about channel distinguishability. SG thanks
Bill Fefferman, Kunal Sharma, Michael Gullans, and Kohdai Kuroiwa for
insightful discussions regarding the Heisenberg picture and optimization
problems under noise. DSF acknowledges funding from the European Union under
Grant Agreement 101080142 and the project EQUALITY. The Berlin team has been
supported by the BMBF (DAQC, MUNIQC-Atoms), the Munich Quantum Valley (K-4 and
K-8), the Quantum Flagship (PasQuans2, Millenion), QuantERA (HQCC), the
Cluster of Excellence MATH+, the DFG (CRC183), the Einstein Foundation
(Einstein Research Unit on Quantum Devices), and the ERC (DebuQC). AA
acknowledges financial support from the QICS (Quantum Information Center
Sorbonne).

## References

  * Preskill [2018] J. Preskill, Quantum computing in the NISQ era and beyond, Quantum 2, 79 (2018).
  * Cai [2023] J.-Y. Cai, Shor’s algorithm does not factor large integers in the presence of noise (2023), arXiv:2306.10072 .
  * Kim  _et al._ [2023] Y. Kim, A. Eddins, S. Anand, K. X. Wei, E. van den Berg, S. Rosenblatt, H. Nayfeh, Y. Wu, M. Zaletel, K. Temme, and A. Kandala, Evidence for the utility of quantum computing before fault tolerance, Nature 618, 500–505 (2023).
  * Arute  _et al._ [2019] F. Arute _et al._ , Quantum supremacy using a programmable superconducting processor, Nature 574, 505 (2019).
  * Bluvstein  _et al._ [2024] D. Bluvstein, S. J. Evered, A. A. Geim, S. H. Li, H. Zhou, T. Manovitz, S. Ebadi, M. Cain, M. Kalinowski, D. Hangleiter, J. P. Bonilla Ataides, N. Maskara, I. Cong, X. Gao, P. Sales Rodriguez, T. Karolyshyn, G. Semeghini, M. J. Gullans, M. Greiner, V. Vuletić, and M. D. Lukin, Logical quantum processor based on reconfigurable atom arrays, Nature 626, 58–65 (2024).
  * Zhu  _et al._ [2022] Q. Zhu, S. Cao, F. Chen, M.-C. Chen, X. Chen, T.-H. Chung, H. Deng, Y. Du, D. Fan, M. Gong, C. Guo, C. Guo, S. Guo, L. Han, L. Hong, H.-L. Huang, Y.-H. Huo, L. Li, N. Li, S. Li, Y. Li, F. Liang, C. Lin, J. Lin, H. Qian, D. Qiao, H. Rong, H. Su, L. Sun, L. Wang, S. Wang, D. Wu, Y. Wu, Y. Xu, K. Yan, W. Yang, Y. Yang, Y. Ye, J. Yin, C. Ying, J. Yu, C. Zha, C. Zhang, H. Zhang, K. Zhang, Y. Zhang, H. Zhao, Y. Zhao, L. Zhou, C.-Y. Lu, C.-Z. Peng, X. Zhu, and J.-W. Pan, Quantum computational advantage via 60-qubit 24-cycle random circuit sampling, Science Bulletin 67, 240 (2022).
  * Madsen  _et al._ [2022] L. S. Madsen, F. Laudenbach, M. F. Askarani, F. Rortais, T. Vincent, J. F. F. Bulmer, F. M. Miatto, L. Neuhaus, L. G. Helt, M. J. Collins, A. E. Lita, T. Gerrits, S. W. Nam, V. D. Vaidya, M. Menotti, I. Dhand, Z. Vernon, N. Quesada, and J. Lavoie, Quantum computational advantage with a programmable photonic processor, Nature 606, 75 (2022).
  * Hangleiter and Eisert [2023] D. Hangleiter and J. Eisert, Computational advantage of quantum random sampling, Rev. Mod. Phys. 95, 035001 (2023).
  * Pan and Zhang [2021] F. Pan and P. Zhang, Simulating the Sycamore quantum supremacy circuits (2021), arXiv:2103.03074 .
  * Bulmer  _et al._ [2022] J. F. F. Bulmer, B. A. Bell, R. S. Chadwick, A. E. Jones, D. Moise, A. Rigazzi, J. Thorbecke, U.-U. Haus, T. V. Vaerenbergh, R. B. Patel, I. A. Walmsley, and A. Laing, The boundary for quantum advantage in Gaussian boson sampling, Science Adv. 8, eabl9236 (2022).
  * Clifford and Clifford [2020] P. Clifford and R. Clifford, Faster classical boson sampling (2020), arXiv:2005.04214 .
  * Gao and Duan [2018] X. Gao and L. Duan, Efficient classical simulation of noisy quantum computation (2018), arXiv:1810.03176 .
  * Pan and Zhang [2022] F. Pan and P. Zhang, Simulation of quantum circuits using the big-batch tensor network method, Phys. Rev. Lett. 128, 030501 (2022).
  * Kechedzhi  _et al._ [2024] K. Kechedzhi, S. Isakov, S. Mandrà, B. Villalonga, X. Mi, S. Boixo, and V. Smelyanskiy, Effective quantum volume, fidelity and computational cost of noisy quantum processing experiments, Future Generation Computer Systems 153, 431–441 (2024).
  * Begušić and Chan [2023] T. Begušić and G. K.-L. Chan, Fast classical simulation of evidence for the utility of quantum computing before fault tolerance (2023), arXiv:2306.16372 .
  * Liao  _et al._ [2023] H.-J. Liao, K. Wang, Z.-S. Zhou, P. Zhang, and T. Xiang, Simulation of IBM’s kicked Ising experiment with projected entangled pair operator (2023), arXiv:2308.03082 .
  * Rudolph  _et al._ [2023a] M. S. Rudolph, E. Fontana, Z. Holmes, and L. Cincio, Classical surrogate simulation of quantum systems with lowesa (2023a), arXiv:2308.09109 .
  * Begušić  _et al._ [2024] T. Begušić, J. Gray, and G. K.-L. Chan, Fast and converged classical simulations of evidence for the utility of quantum computing before fault tolerance, Science Adv. 10, eadk4321 (2024).
  * Patra  _et al._ [2023] S. Patra, S. S. Jahromi, S. Singh, and R. Orus, Efficient tensor network simulation of IBM’s largest quantum processors (2023), arXiv:2309.15642 .
  * Wang  _et al._ [2021a] S. Wang, E. Fontana, M. Cerezo, K. Sharma, A. Sone, L. Cincio, and P. J. Coles, Noise-induced barren plateaus in variational quantum algorithms, Nature Comm. 12, 6961 (2021a).
  * Cerezo  _et al._ [2021a] M. Cerezo, A. Arrasmith, R. Babbush, S. C. Benjamin, S. Endo, K. Fujii, J. R. McClean, K. Mitarai, X. Yuan, L. Cincio, and P. J. Coles, Variational quantum algorithms, Nature Rev. Phys. 3, 625 (2021a).
  * Aharonov  _et al._ [2023] D. Aharonov, X. Gao, Z. Landau, Y. Liu, and U. Vazirani, A polynomial-time classical algorithm for noisy random circuit sampling, in  _Proceedings of the 55th Annual ACM Symposium on Theory of Computing_, STOC ’23 (ACM, 2023).
  * Kandala  _et al._ [2017] A. Kandala, A. Mezzcapo, K. Temme, M. Takita, M. Brink, J. W. Chow, and J. M. Gambetta, Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets, Nature 549, 242 (2017).
  * Chirolli and Burkard [2008] L. Chirolli and G. Burkard, Decoherence in solid-state qubits, Adv. Phys. 57, 225 (2008).
  * J.  _et al._ [2021] J., M. Pino, J. M. Dreiling, C. Figgatt, J. P. Gaebler, S. A. Moses, M. S. All-man, C. H. Baldwin, M. Foss-Feig, D. Hayes, K. Mayer, C. Ryan-Anderson, and B. Neyenhuis, Demonstration of the trapped-ion quantum ccd computer architecture, Nature 592, 209–213 (2021).
  * Ben-Or  _et al._ [2013] M. Ben-Or, D. Gottesman, and A. Hassidim, Quantum refrigerator (2013), arXiv:1301.1995 .
  * Fefferman  _et al._ [2023] B. Fefferman, S. Ghosh, M. Gullans, K. Kuroiwa, and K. Sharma, Effect of non-unital noise on random circuit sampling (2023), arXiv:2306.16659 .
  * Müller-Hermes  _et al._ [2016] A. Müller-Hermes, D. Stilck França, and M. M. Wolf, Relative entropy convergence for depolarizing channels, J. Math. Phys. 57, 022202 (2016).
  * King and Ruskai [2001] C. King and M. Ruskai, Minimal entropy of states emerging from noisy quantum channels, IEEE Trans. Inf. Th. 47, 192–209 (2001).
  * Mele [2023] A. A. Mele, Introduction to Haar measure tools in quantum information: A beginner’s tutorial (2023), arXiv:2307.08956v2 .
  * Gross  _et al._ [2007] D. Gross, K. Audenaert, and J. Eisert, Evenly distributed unitaries: On the structure of unitary designs, J. Math. Phys. 48, 052104 (2007).
  * Fawzi  _et al._ [2022] O. Fawzi, A. Müller-Hermes, and A. Shayeghi, A lower bound on the space overhead of fault-tolerant quantum computation, in  _13th Innovations in Theoretical Computer Science Conference (ITCS 2022)_ (Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022).
  * Quek  _et al._ [2023] Y. Quek, D. S. França, S. Khatri, J. J. Meyer, and J. Eisert, Exponentially tighter bounds on limitations of quantum error mitigation (2023), arXiv:2210.11505 .
  * Stilck França and García-Patrón [2021] D. Stilck França and R. García-Patrón, Limitations of optimization algorithms on noisy quantum devices, Nature Phys. 17, 1221–1227 (2021).
  * De Palma  _et al._ [2021] G. De Palma, M. Marvian, D. Trevisan, and S. Lloyd, The quantum Wasserstein distance of order 1, IEEE Trans. Inf. Th. 67, 6627 (2021).
  * Bravyi  _et al._ [2020a] S. Bravyi, A. Kliesch, R. Koenig, and E. Tang, Obstacles to variational quantum optimization from symmetry protection, Phys. Rev. Lett. 125, 260505 (2020a).
  * Farhi  _et al._ [2020a] E. Farhi, D. Gamarnik, and S. Gutmann, The quantum approximate optimization algorithm needs to see the whole graph: Worst case examples (2020a), arXiv:2005.08747 .
  * Farhi  _et al._ [2020b] E. Farhi, D. Gamarnik, and S. Gutmann, The quantum approximate optimization algorithm needs to see the whole graph: A typical case (2020b), arXiv:2004.09002 .
  * Anshu and Metger [2023] A. Anshu and T. Metger, Concentration bounds for quantum states and limitations on the QAOA from polynomial approximations, Quantum 7, 999 (2023).
  * Bravyi  _et al._ [2018] S. Bravyi, D. Gosset, and R. König, Quantum advantage with shallow circuits, Science 362, 308–311 (2018).
  * Watts and Parham [2024] A. B. Watts and N. Parham, Unconditional quantum advantage for sampling with shallow circuits (2024), arXiv:2301.00995 .
  * Bravyi  _et al._ [2020b] S. Bravyi, D. Gosset, R. König, and M. Tomamichel, Quantum advantage with noisy shallow circuits, Nature Physics 16, 1040–1045 (2020b).
  * McClean  _et al._ [2018a] J. R. McClean, S. Boixo, V. N. Smelyanskiy, R. Babbush, and H. Neven, Barren plateaus in quantum neural network training landscapes, Nature Comm. 9, 4812 (2018a).
  * Holmes  _et al._ [2022] Z. Holmes, K. Sharma, M. Cerezo, and P. J. Coles, Connecting ansatz expressibility to gradient magnitudes and barren plateaus, PRX Quantum 3, 010313 (2022).
  * Brandão  _et al._ [2016] F. G. S. L. Brandão, A. W. Harrow, and M. Horodecki, Local random quantum circuits are approximate polynomial-designs, Commun. Math. Phys. 346, 397 (2016).
  * Cerezo  _et al._ [2021b] M. Cerezo, A. Sone, T. Volkoff, L. Cincio, and P. J. Coles, Cost function dependent barren plateaus in shallow parametrized quantum circuits, Nature Comm. 12, 1791 (2021b).
  * Uvarov and Biamonte [2021] A. Uvarov and J. D. Biamonte, On barren plateaus and cost function locality in variational quantum algorithms, J. Phys. A 54, 245301 (2021).
  * Napp [2022] J. Napp, Quantifying the barren plateau phenomenon for a model of unstructured variational ansätze (2022), arXiv:2203.06174 .
  * Grant  _et al._ [2019] E. Grant, L. Wossnig, M. Ostaszewski, and M. Benedetti, An initialization strategy for addressing barren plateaus in parametrized quantum circuits, Quantum 3, 214 (2019).
  * Sack  _et al._ [2022] S. H. Sack, R. A. Medina, A. A. Michailidis, R. Kueng, and M. Serbyn, Avoiding barren plateaus using classical shadows, PRX Quantum 3, 020365 (2022).
  * Mele  _et al._ [2022] A. A. Mele, G. B. Mbeng, G. E. Santoro, M. Collura, and P. Torta, Avoiding barren plateaus via transferability of smooth solutions in a hamiltonian variational ansatz, Phys. Rev. A 106, L060401 (2022).
  * Rudolph  _et al._ [2023b] M. S. Rudolph, J. Miller, D. Motlagh, J. Chen, A. Acharya, and A. Perdomo-Ortiz, Synergy between quantum circuits and tensor networks: Short-cutting the race to practical quantum advantage (2023b), arXiv:2208.13673 .
  * Jain  _et al._ [2022] N. Jain, B. Coyle, E. Kashefi, and N. Kumar, Graph neural network initialisation of quantum approximate optimisation, Quantum 6, 861 (2022).
  * Shi and Shang [2024] X. Shi and Y. Shang, Avoiding barren plateaus via Gaussian mixture model (2024), arXiv:2402.13501 .
  * Schatzki  _et al._ [2022] L. Schatzki, M. Larocca, Q. T. Nguyen, F. Sauvage, and M. Cerezo, Theoretical guarantees for permutation-equivariant quantum neural networks (2022), arXiv:2210.09974 .
  * Zhang  _et al._ [2020] K. Zhang, M.-H. Hsieh, L. Liu, and D. Tao, Toward trainability of quantum neural networks (2020), arXiv:2011.06258 .
  * Volkoff and Coles [2021] T. Volkoff and P. J. Coles, Large gradients via correlation in random parameterized quantum circuits, Quant. Sc. Tech. 6, 025008 (2021).
  * Pesah  _et al._ [2021] A. Pesah, M. Cerezo, S. Wang, T. Volkoff, A. T. Sornborger, and P. J. Coles, Absence of barren plateaus in quantum convolutional neural networks, Phys. Rev. X 11, 041011 (2021).
  * Liu  _et al._ [2022] X. Liu, G. Liu, J. Huang, H.-K. Zhang, and X. Wang, Mitigating barren plateaus of variational quantum eigensolvers (2022), arXiv:2205.13539 .
  * Meyer  _et al._ [2023] J. J. Meyer, M. Mularski, E. Gil-Fuster, A. A. Mele, F. Arzani, A. Wilms, and J. Eisert, Exploiting symmetry in variational quantum machine learning, PRX Quantum 4, 010328 (2023).
  * Park and Killoran [2023] C.-Y. Park and N. Killoran, Hamiltonian variational ansatz without barren plateaus (2023), arXiv:2302.08529 .
  * Larocca  _et al._ [2022] M. Larocca, F. Sauvage, F. M. Sbahi, G. Verdon, P. J. Coles, and M. Cerezo, Group-invariant quantum machine learning, PRX Quantum 3, 030341 (2022).
  * Zhang  _et al._ [2022] K. Zhang, L. Liu, M.-H. Hsieh, and D. Tao, Escaping from the barren plateau via gaussian initializations in deep variational quantum circuits, Adv. Neur. Inf. Proc. Sys. 35, 18612 (2022).
  * Park  _et al._ [2024] C.-Y. Park, M. Kang, and J. Huh, Hardware-efficient ansatz without barren plateaus in any depth (2024), arXiv:2403.04844 .
  * Cerezo  _et al._ [2023] M. Cerezo, M. Larocca, D. García-Martín, N. L. Diaz, P. Braccia, E. Fontana, M. S. Rudolph, P. Bermejo, A. Ijaz, S. Thanasilp, E. R. Anschuetz, and Z. Holmes, Does provable absence of barren plateaus imply classical simulability? or, why we need to rethink variational quantum computing (2023), arXiv:2312.09121 .
  * Schumann  _et al._ [2023] M. Schumann, F. K. Wilhelm, and A. Ciani, Emergence of noise-induced barren plateaus in arbitrary layered noise models (2023), arXiv:2310.08405 .
  * Sannia  _et al._ [2023] A. Sannia, F. Tacchino, I. Tavernelli, G. L. Giorgi, and R. Zambrini, Engineered dissipation to mitigate barren plateaus (2023), arXiv:2310.15037 .
  * Aharonov  _et al._ [1996] D. Aharonov, M. Ben-Or, R. Impagliazzo, and N. Nisan, Limitations of noisy reversible computation (1996), arXiv:quant-ph/9611028 .
  * Boixo  _et al._ [2018] S. Boixo, S. V. Isakov, V. N. Smelyanskiy, R. Babbush, N. Ding, Z. Jiang, M. J. Bremner, J. M. Martinis, and H. Neven, Characterizing quantum supremacy in near-term devices, Nature Phys. 14, 595 (2018).
  * Deshpande  _et al._ [2022a] A. Deshpande, P. Niroula, O. Shtanko, A. V. Gorshkov, B. Fefferman, and M. J. Gullans, Tight bounds on the convergence of noisy random circuits to the uniform distribution, PRX Quantum 3, 040329 (2022a).
  * Harrow and Mehraban [2023] A. W. Harrow and S. Mehraban, Approximate unitary t-designs by short random quantum circuits using nearest-neighbor and long-range gates, Commun. Math. Phys. 401, 1531 (2023).
  * Dalzell  _et al._ [2022] A. M. Dalzell, N. Hunter-Jones, and F. G. Brandão, Random quantum circuits anticoncentrate in log depth, PRX Quantum 3, 010333 (2022).
  * Bravyi  _et al._ [2020c] S. Bravyi, D. Gosset, R. König, and M. Tomamichel, Quantum advantage with noisy shallow circuits, Nature Phys. 16, 1040–1045 (2020c).
  * Fontana  _et al._ [2023] E. Fontana, M. S. Rudolph, R. Duncan, I. Rungger, and C. Cîrstoiu, Classical simulations of noisy variational quantum circuits (2023), arXiv:2306.05400 .
  * Bravyi  _et al._ [2006] S. Bravyi, M. B. Hastings, and F. Verstraete, Lieb-Robinson Bounds and the generation of correlations and topological quantum order, Phys. Rev. Lett. 97, 050401 (2006).
  * Schwarz  _et al._ [2017] M. Schwarz, O. Buerschaper, and J. Eisert, Approximating local observables on projected entangled pair states, Phys. Rev. A 95, 060102 (2017).
  * Borregaard  _et al._ [2021] J. Borregaard, M. Christandl, and D. Stilck França, Noise-robust exploration of many-body quantum states on near-term quantum devices, npj Quant. Inf. 7, 45 (2021).
  * Thanasilp  _et al._ [2022] S. Thanasilp, S. Wang, M. Cerezo, and Z. Holmes, Exponential concentration and untrainability in quantum kernel methods (2022), arXiv:2208.11060 .
  * Jerbi  _et al._ [2023] S. Jerbi, L. J. Fiderer, H. Poulsen Nautrup, J. M. Kübler, H. J. Briegel, and V. Dunjko, Quantum machine learning beyond kernel methods, Nature Comm. 14, 517 (2023).
  * Schuld and Killoran [2019] M. Schuld and N. Killoran, Quantum machine learning in feature Hilbert spaces, Phys. Rev. Lett. 122, 040504 (2019).
  * Huang  _et al._ [2021] H.-Y. Huang, M. Broughton, M. Mohseni, R. Babbush, S. Boixo, H. Neven, and J. R. McClean, Power of data in quantum machine learning, Nature Comm. 12, 2631 (2021).
  * Wang  _et al._ [2021b] S. Wang, E. Fontana, M. Cerezo, K. Sharma, A. Sone, L. Cincio, and P. J. Coles, Noise-induced barren plateaus in variational quantum algorithms, Nature Comm. 12, 6961 (2021b).
  * Beth Ruskai  _et al._ [2002] M. Beth Ruskai, S. Szarek, and E. Werner, An analysis of completely-positive trace-preserving maps on M2, Linear Algebra and its Applications 347, 159 (2002).
  * Chen  _et al._ [2022] S. Chen, J. Cotler, H.-Y. Huang, and J. Li, The complexity of NISQ (2022), arXiv:2210.07234 .
  * Dalzell  _et al._ [2021] A. M. Dalzell, N. Hunter-Jones, and F. G. S. L. Brandão, Random quantum circuits transform local noise into global white noise (2021), arXiv:2111.14907 .
  * Note [1] However, for spatial dimension $\mathrm{D}>1$, if the depth is between $O(\log(n)^{1/\mathrm{D}})$ and $O(\log(n))$, to our knowledge it is not yet known whether there is an efficient classical simulation algorithm.
  * Hirche  _et al._ [2022] C. Hirche, C. Rouzé, and D. S. França, On contraction coefficients, partial orders and approximation of capacities for quantum channels, Quantum 6, 862 (2022).
  * Gottesman [1998] D. Gottesman, The Heisenberg representation of quantum computers (1998), arXiv:quant-ph/9807006 .
  * Wilde [2013] M. M. Wilde,  _Quantum information theory_ (Cambridge University Press, 2013).
  * Razborov [2003] A. A. Razborov, An upper bound on the threshold quantum decoherence rate (2003), arXiv:quant-ph/0310136 .
  * Kempe  _et al._ [2008] J. Kempe, O. Regev, F. Unger, and R. De Wolf, Upper bounds on the noise threshold for fault-tolerant quantum computing, in  _International Colloquium on Automata, Languages, and Programming_ (Springer, 2008) pp. 845–856.
  * Hirche  _et al._ [2023] C. Hirche, C. Rouzé, and D. S. França, Quantum differential privacy: An information theory perspective, IEEE Trans. Inf. Th. 69, 5771 (2023).
  * McClean  _et al._ [2018b] J. R. McClean, S. Boixo, V. N. Smelyanskiy, R. Babbush, and H. Neven, Barren plateaus in quantum neural network training landscapes, Nature Comm. 9, 4812 (2018b).
  * Farhi  _et al._ [2014] E. Farhi, J. Goldstone, and S. Gutmann, A Quantum Approximate Optimization Algorithm (2014), arXiv:1411.4028 .
  * Aharonov and Ben-Or [1996] D. Aharonov and M. Ben-Or, Polynomial simulations of decohered quantum computers, in  _Proceedings of 37th Conference on Foundations of Computer Science_ (1996) pp. 46–55, quant-ph/9611029 .
  * Deshpande  _et al._ [2022b] A. Deshpande, P. Niroula, O. Shtanko, A. V. Gorshkov, B. Fefferman, and M. J. Gullans, Tight bounds on the convergence of noisy random circuits to the uniform distribution, PRX Quantum 3, 040329 (2022b).
  * Bravyi  _et al._ [2023] S. Bravyi, D. Gosset, and Y. Liu, Classical simulation of peaked shallow quantum circuits (2023), arXiv:2309.08405 .
  * Bravyi  _et al._ [2021] S. Bravyi, D. Gosset, and R. Movassagh, Classical algorithms for quantum mean values, Nature Phys. 17, 337–341 (2021).
  * Aaronson and Gottesman [2004] S. Aaronson and D. Gottesman, Improved simulation of stabilizer circuits, Phys. Rev. A 70, 052328 (2004).
  * Webb [2016] Z. Webb, The Clifford group forms a unitary 3-design (2016), arXiv:1510.02769 .
  * Zhu  _et al._ [2016] H. Zhu, R. Kueng, M. Grassl, and D. Gross, The Clifford group fails gracefully to be a unitary 4-design (2016), arXiv:1609.08172 .
  * Bhatia [2007] R. Bhatia,  _Positive definite matrices_ (Princeton University Press, Princeton, 2007).
  * Landau and Lifshitz [1981] L. D. Landau and L. M. Lifshitz,  _Quantum mechanics non-relativistic theory, third edition: Volume 3_ , 3rd ed. (Butterworth-Heinemann, 1981).
  * Wang  _et al._ [2021c] S. Wang, P. Czarnik, A. Arrasmith, M. Cerezo, L. Cincio, and P. J. Coles, Can error mitigation improve trainability of noisy variational quantum algorithms? (2021c), arXiv:2109.01051 .
  * Crooks [2019] G. E. Crooks, Gradients of parameterized quantum gates using the parameter-shift rule and gate decomposition (2019), arXiv:1905.13311 .
  * De Palma  _et al._ [2023] G. De Palma, M. Marvian, C. Rouzé, and D. S. França, Limitations of variational quantum algorithms: A quantum optimal transport approach, PRX Quantum 4, 010309 (2023).
  * Mosonyi and Hiai [2010] M. Mosonyi and F. Hiai, On the quantum renyi relative entropies and related capacity formulas (2010), arXiv:0912.1286 [quant-ph] .
  * Christandl and Müller-Hermes [2017] M. Christandl and A. Müller-Hermes, Relative entropy bounds on quantum, private and repeater capacities, Commun. Math. Phys. 353, 821 (2017).
  * Rubboli  _et al._ [2023] R. Rubboli, R. Takagi, and M. Tomamichel, Mixed-state additivity properties of magic monotones based on quantum relative entropies for single-qubit states and beyond (2023), arXiv:2307.08258 .
  * Liu  _et al._ [2021] Y. Liu, S. Arunachalam, and K. Temme, A rigorous and robust quantum speed-up in supervised machine learning, Nature Phys. 17, 1013 (2021).
  * Havlíček  _et al._ [2019] V. Havlíček, A. D. Córcoles, K. Temme, A. W. Harrow, A. Kandala, J. M. Chow, and J. M. Gambetta, Supervised learning with quantum-enhanced feature spaces, Nature 567, 209 (2019).
  * Schuld [2021] M. Schuld, Supervised quantum machine learning models are kernel methods (2021), arXiv:2101.11020 .
  * Shalev-Shwartz and Ben-David [2014] S. Shalev-Shwartz and S. Ben-David,  _Understanding machine learning: From theory to algorithms_ (Cambridge university press, 2014).
  * Canonne [2022] C. L. Canonne, A short note on an inequality between KL and TV (2022), arXiv:2202.07198 .
  * Angrisani  _et al._ [2023] A. Angrisani, M. Doosti, and E. Kashefi, A unifying framework for differentially private quantum algorithms (2023), arXiv:2307.04733 .

Supplementary Material

###### Contents

  1. I Introduction
    1. I.0.1 Related works
    2. I.0.2 Preliminaries and definitions
    3. I.1 Noise-induced effective shallow circuits
    4. I.2 Classical simulation of random quantum circuits with possibly non-unital noise
    5. I.3 Lack of barren plateaus with non-unital noise, but only the last $\Theta(\log(n))$ layers matter
      1. I.3.1 Lack of exponential concentration for local cost functions with non-unital noise
      2. I.3.2 Lack of vanishing gradients for local cost functions, but only the last $\Theta(\log(n))$ layers are trainable
      3. I.3.3 Improved upper bounds for barren plateaus in the unital noise scenario
      4. I.3.4 Exponential concentration and lack thereof in noisy kernels
  2. II Conclusions
  3. A Preliminaries
    1. A.1 Notation and basic definitions
    2. A.2 Haar measure and unitary designs
      1. A.2.1 Properties of layers of single-qubit random gates
    3. A.3 Quantum channels
      1. A.3.1 Pauli transfer matrix representation of a quantum channel
      2. A.3.2 Normal form representation of a quantum channel
    4. A.4 Circuit and noise model
  4. B Pauli expectation values of noisy random quantum circuits
    1. B.1 Variance lower bound: Local expectation values with non-unital noise are not exponentially concentrated
    2. B.2 Variance upper bound: Global expectation values are exponentially concentrated
    3. B.3 Effective shallow circuits
    4. B.4 Indistinguishability of quantum states affected by noisy quantum circuits
      1. B.4.1 Worst-case upper bound on the trace distance
    5. B.5 Classical simulation of Pauli expectation values of noisy random quantum circuits
  5. C Quantum machine learning under non-unital noise: Barren plateaus
    1. C.1 Preliminaries on barren plateaus
    2. C.2 Gradients: useful lemmas
    3. C.3 Absence of barren plateaus, but only few layers are trainable
      1. C.3.1 Partial derivative upper bound: Layers before the last $O(\log(n))$ are not trainable
      2. C.3.2 Partial derivative lower bound: the last $\Theta(\log(n))$ layers are the only trainable
    4. C.4 Improved upper bounds for unital noise
  6. D Purity and kernel methods under non-unital noise
    1. D.1 Purity of average and worst-case circuits
    2. D.2 Quantum machine learning under non-unital noise: Kernel methods
      1. D.2.1 Fidelity quantum kernels: Exponential concentration at any depth
      2. D.2.2 Projected quantum kernels: Absence of exponential concentration at any depth
  7. E Miscellaneous
    1. E.1 Trace distance decay for worst-case circuits under local depolarizing noise
    2. E.2 Numerical simulations

##  Appendix A Preliminaries

###  A.1 Notation and basic definitions

Throughout this work, we employ the following notation and conventions.

  * •

$\mathcal{L}(\mathbb{C}^{d})$ denotes the set of linear operators that act on
the $d$-dimensional complex vector space $\mathbb{C}^{d}$.

  * •

The _unitary group_ , denoted as $\mathrm{U}(d)$, comprises operators
$U\in\mathcal{L}(\mathbb{C}^{d})$ satisfying $U^{\dagger}U=I$, with $I$
representing the identity operator. Additionally, we use $[d]$ to represent
the set of integers from $1$ to $d$, i.e., $[d]\coloneqq\\{1,\dots,d\\}$.

  * •

Given a vector $v\in\mathbb{C}^{d}$ and a value $p\in\left[1,\infty\right]$,
we denote the $p$-norm of $v$ as $\norm*{v}_{p}$, defined as

$\norm*{v}_{p}\coloneqq\left(\sum_{i=1}^{d}|v_{i}|^{p}\right)^{1/p}.$

  * •

Norms: For a matrix $A\in\mathcal{L}\left(\mathbb{C}^{d}\right)$, its
_Schatten $p$-norm_ is
$\norm*{A}_{p}\coloneqq\Tr\small(\small(\sqrt{A^{\dagger}A}\small)^{p}\small)^{1/p}$,
corresponding to the $p$-norm of the vector of singular values of $A$.

The trace norm and Hilbert-Schmidt norm, specific instances of Schatten
$p$-norms, are, respectively, denoted as $\norm*{\cdot}_{1}$ and
$\norm*{\cdot}_{2}$.

The infinity norm, $\norm*{\cdot}_{\infty}$, of a matrix is the maximum
singular value, which is equal to the limit of the Schatten $p$-norm as $p$
approaches infinity.

The Hilbert-Schmidt norm arises from the scalar product $\langle
A,B\rangle_{HS}\coloneqq\Tr\\!\left(A^{\dagger}B\right)$ for
$A,B\in\mathcal{L}\left(\mathbb{C}^{d}\right)$.

The _Hölder inequality_ , $\lvert\langle
A,B\rangle_{HS}\rvert\leq\norm*{A}_{p}\norm*{B}_{q},$ holds for $1\leq
p,q\leq\infty$ such that $p^{-1}+q^{-1}=1$.

For all matrices $A$ and $1\leq p\leq q$, we have
$\norm*{A}_{q}\leq\norm*{A}_{p}$ and
$\norm*{A}_{p}\leq\mathrm{rank}(A)^{(p^{-1}-q^{-1})}\norm*{A}_{q}$. In
particular, we have that $\norm*{A}_{1}\leq\sqrt{d}\norm*{A}_{2}$.

  * •

Quantum states: The set of density matrices (_quantum states_) is

$\mathcal{S}\\!\left(\mathbb{C}^{d}\right)\coloneqq\\{\rho\in\mathcal{L}\left(\mathbb{C}^{d}\right)\,:\,\rho\geq
0,\,\Tr(\rho)=1\\}.$

We adopt the bra-ket notation, denoting a vector $v\in\mathbb{C}^{d}$ as
$\ket{v}$ and its adjoint as $\bra{v}$. A vector $\ket{\psi}\in\mathbb{C}^{d}$
is a (pure) state vector if $\norm*{\ket{\psi}}_{2}=1$. The canonical basis of
$\mathbb{C}^{d}$ is $\\{\ket{i}\\}_{i=1}^{d}$, and the non-normalized
maximally entangled state vector is given by
$\ket{\Omega}\coloneqq\sum^{d}_{i=1}\ket{i}\otimes\ket{i}=\sum^{d}_{i=1}\ket{i,i}.$

  * •

Given an element of
$A\in\mathcal{L}(\mathbb{C}^{d_{1}}\otimes\mathbb{C}^{d_{2}})$, we indicate
with $\Tr_{1}(A)$ the partial trace of $A$ with respect the first subsystem,
and similarly for $\Tr_{2}(A)$, for partial trace of $A$ with respect the
second subsystem.

  * •

When addressing a system of $n$ qubits, we use $I$ to denote the identity
operator on the Hilbert space $\mathbb{C}^{2}$ of one qubit, while
$I_{n}=I^{\otimes n}$ denotes the identity on the Hilbert space of $n$ qubits.

  * •

Pauli basis: Let $d=2^{n}$, where $n\in\mathbb{N}$. Elements of the Pauli
basis $\\{I,X,Y,Z\\}^{\otimes n}$ are Hermitian, unitary, trace-less, they
square to the identity and they are orthogonal to each other with respect the
Hilbert-Schmidt Scalar product. The Pauli basis forms an orthogonal basis for
the linear operators $\mathcal{L}\left(\mathbb{C}^{d}\right)$. We denote
$\boldsymbol{\sigma}\coloneqq(X,Y,Z)$ the vector of single qubit Pauli
matrices.

Given $P\in\\{I,X,Y,Z\\}^{\otimes n}$ such that $P=Q_{1}\leavevmode\nobreak\
\otimes\cdots\otimes\leavevmode\nobreak\ Q_{n}$, we define $\left[P\right]$
the set $\left[P\right]\coloneqq\\{Q_{1},\dotsc,Q_{n}\\}$.

    * –

Support: We define the _support of_ $P\in\\{I,X,Y,Z\\}^{\otimes n}$ as the set
of integers containing the non-identity terms in $\left[P\right]$, i.e.,

$\mathrm{supp}(P)\coloneqq\\{i\in[n]\,:\,\,Q_{i}\in\left[P\right]\text{ and
}Q_{i}\neq I\\}.$

For example, $\mathrm{supp}(X\otimes I\otimes Y)=\\{1,3\\}$.

Similarly, if $H$ is an operator expressed in the Pauli basis as
$H=\sum^{M}_{i=1}c_{i}P_{i}$, where $\\{c_{i}\\}^{M}_{i=1}$ are real non-zero
numbers, and $\\{P_{i}\\}^{M}_{i=1}$ are elements of the Pauli basis, then

$\displaystyle\mathrm{supp}(H)\coloneqq\bigcup^{M}_{i=1}\operatorname{supp}(P_{i}).$
(27)

    * –

Pauli weight: The _Pauli-weight_ of $P$, denoted as $|P|$, is the number of
Pauli in the tensor product decomposition of $P$ different from $I$, namely
$|P|\coloneqq|\mathrm{supp}(P)|$. For example $|X\otimes I\otimes
Y|=|\\{1,3\\}|=2$. The Pauli-$X$ weight of $P$, denoted as $|P|_{X}$,
corresponds to the number of Pauli-$X$ operators in the tensor-product
decomposition of $P$. Similarly, the Pauli-$Y$ weight of $P$, denoted as
$|P|_{Y}$, represents the number of Pauli-$Y$ operators in the decomposition
of $P$. Analogously, the Pauli-$Z$ weight is denoted as $|P|_{Z}$.

    * –

Locality of an observable: The _locality_ of a Hermitian operator $H$ is
defined as $|\operatorname{supp}(H)|$.

    * –

Light cone: The light-cone of a Hermitian operator $H$ with respect to a
linear map $\Phi$ is defined as

$\displaystyle\mathrm{Light}(\Phi,H)\coloneqq\operatorname{supp}(\Phi^{*}(H)),$
(28)

where $\Phi^{*}$ denotes the adjoint of $\Phi$ with respect the Hilbert-
Schmidt scalar product.

  * •

Asymptotic notation: Big-O Notation: For a function $f(n)$, if there exists a
constant $c$ and a specific input size $n_{0}$ such that $f(n)\leq c\cdot
g(n)$ for all $n\geq n_{0}$, where $g(n)$ is a well-defined function, then we
express it as $f(n)=O(g(n))$. This notation signifies the upper limit of how
fast a function grows in relation to $g(n)$.

Big-Omega Notation: For a function $f(n)$, if there exists a constant $c$ and
a specific input size $n_{0}$ such that $f(n)\geq c\cdot g(n)$ for all $n\geq
n_{0}$, where $g(n)$ is a well-defined function, then we express it as
$f(n)=\Omega(g(n))$. This notation signifies the lower limit of how fast a
function grows in relation to $g(n)$.

Big-Theta Notation: For a function $f(n)$, if $f(n)=O(g(n))$ and if
$f(n)=\Omega(g(n))$, where $g(n)$ is a well-defined function, then we express
it as $f(n)=\Theta(g(n))$.

Little-Omega Notation: For a function $f(n)$, if for any constant $c$, there
exists an input size $n_{0}$ such that $f(n)>c\cdot g(n)$ for all $n\geq
n_{0}$, where $g(n)$ is a well-defined function, then then we express it as
$f(n)=\omega(g(n))$. This notation implies that the function grows strictly
faster than the provided lower bound.

###  A.2 Haar measure and unitary designs

In the following, for our proofs it will be useful to have some familiarity
with the Haar measure, which formalizes the notion of uniform distribution
over unitaries. For a more detailed explanation we refer to Ref. [30] – here
we state a few crucial properties that will be useful later on. We define as
the _Haar measure_ $\mu_{H}(\mathrm{U}(d))$ the (unique) probability
distribution over the unitary group $\mathrm{U}(d)$ which is left and right
invariant, which means that for any integrable function $f$, we have

$\displaystyle\underset{U\sim\mu_{H}}{\mathbb{E}}\left[f(U)\right]=\underset{U\sim\mu_{H}}{\mathbb{E}}\left[f(UV)\right]=\underset{U\sim\mu_{H}}{\mathbb{E}}\left[f(VU)\right],$
(29)

for any $U,V\in\mathrm{U}(d)$. In the last equation, we have used
$\mu_{H}\equiv\mu_{H}(\mathrm{U}(d))$, that is, we omitted to specify the
group $\mathrm{U}(d)$, and we will do the same in subsequent
sections.Moreover, it holds that

$\displaystyle\underset{U\sim\mu_{H}}{\mathbb{E}}\left[f(U)\right]=\underset{U\sim\mu_{H}}{\mathbb{E}}\left[f(U^{\dagger})\right].$
(30)

#### Useful relations

We define the _identity_ $\mathbb{I}$ and the _flip operator_ $\mathbb{F}$,
also known as the permutation operators associated to a tensor product of two
Hilbert spaces, as

$\displaystyle\mathbb{I}\coloneqq\sum^{d}_{i,j=1}\outerproduct{i,j}{i,j},\quad\quad\quad\mathbb{F}\coloneqq\sum^{d}_{i,j=1}\outerproduct{i,j}{j,i}.$
(31)

From this definition, it can be observed that they satisfy

$\displaystyle\mathbb{I}\left(\ket{\psi}\otimes\ket{\phi}\right)=\ket{\psi}\otimes\ket{\phi},\quad\quad\mathbb{F}\left(\ket{\psi}\otimes\ket{\phi}\right)=\ket{\phi}\otimes\ket{\psi},$
(32)

for all $\ket{\psi},\ket{\phi}\in\mathbb{C}^{d}$. Useful properties of the
flip operator are the _swap-trick_ and the _partial-swap-trick_

$\displaystyle\Tr(A\otimes B\mathbb{F})=\Tr(AB),\quad\Tr_{2}(A\otimes
B\mathbb{F})=AB,$ (33)

equalities that can be easily verified in terms of tensor network diagrams.

Let $n$ now be the number of qubits in a system. If $d=2^{n}$, then the flip
operator can be written in terms of the Pauli basis as

$\displaystyle\mathbb{F}=\frac{1}{d}\sum_{P\in\\{I,X,Y,Z\\}^{\otimes
n}}P\otimes P,$ (34)

where we have used the fact that the Pauli basis is an orthogonal basis and
the _swap-trick_.

Two formulas, involving expected values over the Haar measure and permutation
operators, will be crucial in our proofs. Given
$O\in\mathcal{L}\left(\mathbb{C}^{d}\right)$, we have the so called _first-
moment formula_ , given by

$\displaystyle\underset{U\sim\mu_{H}}{\mathbb{E}}\left[UOU^{\dagger}\right]$
$\displaystyle=\frac{\Tr\\!\left(O\right)}{d}I.$ (35)

Given $O\in\mathcal{L}((\mathbb{C}^{d})^{\otimes 2})$, we have the second-
moment formula

$\displaystyle\underset{U\sim\mu_{H}}{\mathbb{E}}\left[U^{\otimes
2}OU^{\dagger\otimes
2}\right]=c_{\mathbb{I},O}\mathbb{I}+c_{\mathbb{F},O}\mathbb{F},$ (36)

where

$\displaystyle
c_{\mathbb{I},O}=\frac{\Tr\\!\left(O\right)-d^{-1}\Tr\\!\left(\mathbb{F}O\right)}{d^{2}-1}\quad\text{and}\quad
c_{\mathbb{F},O}=\frac{\Tr\\!\left(\mathbb{F}O\right)-d^{-1}\Tr\\!\left(O\right)}{d^{2}-1}.$
(37)

(see Ref. [30] for a proof of the previous two equations). A probability
distribution over unitaries $\nu$ is defined to be a _$k$ -design_ [31], for
$k\in\mathbb{N}$, if and only if

$\displaystyle\underset{U\sim\mu_{H}}{\mathbb{E}}\left[U^{\otimes
k}OU^{\dagger\otimes k}\right]=\underset{V\sim\nu}{\mathbb{E}}\left[V^{\otimes
k}OV^{\dagger\otimes k}\right].$ (38)

If the distribution $\nu$ is a $(k+1)$-design, then it is also a $k$-design.
An important set of unitaries which will be useful in our work is the Clifford
group [88].

######  Definition 12 (Clifford group [88, 99]).

The Clifford group $\mathrm{Cl}(n)$ is the set of unitaries which sends the
Pauli group
$\mathcal{P}_{n}\coloneqq\\{i^{k}\\}^{3}_{k=0}\times\\{I,X,Y,Z\\}^{\otimes n}$
in itself under the adjoint operation:

$\displaystyle\mathrm{Cl}(n)\coloneqq\\{U\in\mathrm{U}(2^{n})\colon
UPU^{\dagger}\in\mathcal{P}_{n}\text{ for all $P\in\\{I,X,Y,Z\\}^{\otimes
n}$}\\}.$ (39)

and it is equivalent to the set of unitaries generated by
$\\{\operatorname{H},\operatorname{CNOT},\operatorname{S}\\}$ where
$\operatorname{H}$, $\operatorname{CNOT}$, and $\operatorname{S}$ are,
respectively, the $\mathrm{Hadamard}$, $\mathrm{Controlled}$-$\mathrm{NOT}$,
and $\mathrm{Phase}$ gates.

We make extensive use of the following seminal result throughout our work.

######  Lemma 13 (Clifford group is a $2$-design [100, 101]).

The uniform distribution over the Clifford group $\mathrm{Cl}(n)$ is a
$2$-design.

The Clifford group is actually also a $3$-design [100, 101], but in our work
we need only its $2$-design property. Now, we state an important formula – the
Pauli mixing formula – that we use in many of the proofs.

######  Lemma 14 (Pauli mixing).

Let $d=2^{n}$ and consider $\nu$ to be a $2$-design distribution. If
$P_{1},P_{2}\in\\{I,X,Y,Z\\}^{\otimes n}$ are elements of the Pauli basis,
then

$\displaystyle\underset{U\sim\nu}{\mathbb{E}}\left[U^{\otimes 2}(P_{1}\otimes
P_{2})U^{\dagger\otimes 2}\right]$
$\displaystyle=\delta_{P_{1},P_{2}}\underset{U\sim\nu}{\mathbb{E}}\left[U^{\otimes
2}(P_{1}\otimes P_{1})U^{\dagger\otimes 2}\right]$ (40)
$\displaystyle=\begin{cases}I\otimes I&\text{if }P_{1}=P_{2}=I,\\\
\frac{1}{d^{2}-1}\sum_{P\in\\{I,X,Y,Z\\}^{\otimes n}\setminus I_{n}}P\otimes
P&\text{if }P_{1}=P_{2}\neq I,\\\ 0&\text{if }P_{1}\neq P_{2}.\end{cases}$
(41)

This can be shown using the second-moment formula previously introduced and
the decomposition of the flip operator in terms of the Pauli basis.

####  A.2.1 Properties of layers of single-qubit random gates

In our work, frequent calculations involve averages over the tensor product of
single-qubit $2$-design gates. To facilitate these calculations, we introduce
two Lemmas that will be instrumental in later sections of our work.

######  Lemma 15 (A layer of $1$-qubit Haar random gates is a global
$1$-design).

Let $\nu$ be a distribution over the tensor product of single-qubit $1$-design
gates, namely over unitaries $U$ of the form $U=\bigotimes^{n}_{i=1}u_{i}$,
where $u_{i}$ is a single-qubit unitary acting on the $i$-th qubit. Then,
$\nu$ is a $n$-qubit $1$-design.

###### Proof.

Let $O\in\mathcal{L}\left(\mathbb{C}^{d}\right)$ with $d=2^{n}$. By writing it
in the Pauli basis, we have

$\displaystyle\underset{U\sim\nu}{\mathbb{E}}\left[UOU^{\dagger}\right]=\frac{1}{d}\sum_{P\in\\{I,X,Y,Z\\}^{\otimes
n}}\Tr(OP)\underset{U\sim\nu}{\mathbb{E}}\left[UPU^{\dagger}\right]=\frac{\Tr(O)}{d}I_{n},$
(42)

where in the last equality we have used the first-moment formula (Eq. (35)) on
each of the qubits and used that the Pauli are trace-less. ∎

As a consequence of the Pauli mixing property, we have the following lemma.

######  Lemma 16 (Second moments of single-qubit random gates layers).

Let $\nu$ be a distribution over the tensor product of single-qubit $2$-design
gates, namely over unitaries $U$ of the form $U=\bigotimes^{n}_{i=1}u_{i}$,
where $u_{i}$ is a single-qubit unitary acting on the $i$-th qubit. Let $\rho$
be any quantum state. Then we have

  1. 1.

Let $O\coloneqq\sum_{P\in\\{I,X,Y,Z\\}^{\otimes n}}a_{P}P$, with
$a_{P}\in\mathbb{R}$ for any $P\in\\{I,X,Y,Z\\}^{\otimes n}$. We have

$\displaystyle\underset{U\sim\nu}{\mathbb{E}}\left[\Tr(OU\rho
U^{\dagger})^{2}\right]=\sum_{P\in\\{I,X,Y,Z\\}^{\otimes
n}}a_{P}^{2}\underset{U\sim\nu}{\mathbb{E}}\left[\Tr(PU\rho
U^{\dagger})^{2}\right].$ (43)

  2. 2.

For any $P\in\\{I,X,Y,Z\\}^{\otimes n}$, we have

$\displaystyle\underset{U\sim\nu}{\mathbb{E}}\left[\Tr(PU\rho
U^{\dagger})^{2}\right]=\frac{1}{3^{|P|}}\sum_{\begin{subarray}{c}Q\in\\{I,X,Y,Z\\}^{\otimes
n}:\\\
\operatorname{supp}(Q)=\operatorname{supp}(P)\end{subarray}}\Tr(Q\rho)^{2}.$
(44)

###### Proof.

We have

$\displaystyle\underset{U\sim\nu}{\mathbb{E}}[\Tr(OU\rho U^{\dagger})^{2}]$
$\displaystyle=\underset{U\sim\nu}{\mathbb{E}}[\Tr(O^{\otimes 2}U^{\otimes
2}\rho^{\otimes 2}U^{\dagger\otimes 2})]$ (45)
$\displaystyle=\sum_{P,Q\in\\{I,X,Y,Z\\}^{\otimes
n}}a_{P}a_{Q}\underset{U\sim\nu}{\mathbb{E}}[\Tr((P\otimes Q)U^{\otimes
2}\rho^{\otimes 2}U^{\dagger\otimes 2})]$
$\displaystyle=\sum_{P,Q\in\\{I,X,Y,Z\\}^{\otimes
n}}a_{P}a_{Q}\underset{U\sim\nu}{\mathbb{E}}[\Tr(U^{\dagger\otimes 2}(P\otimes
Q)U^{\otimes 2}\rho^{\otimes 2})]$
$\displaystyle=\sum_{P\in\\{I,X,Y,Z\\}^{\otimes
n}}a_{P}^{2}\underset{U\sim\nu}{\mathbb{E}}[\Tr(U^{\dagger\otimes 2}(P\otimes
P)U^{\otimes 2}\rho^{\otimes 2})]$
$\displaystyle=\sum_{P\in\\{I,X,Y,Z\\}^{\otimes
n}}a_{P}^{2}\underset{U\sim\nu}{\mathbb{E}}[\Tr(PU\rho U^{\dagger})^{2}],$

where for the fourth equality we have used the fact that
$U=\bigotimes^{n}_{i=1}u_{i}$ is a layer of single-qubit $2$-design unitaries,

$\underset{U\sim\mu_{H}}{\mathbb{E}}\left[f(U)\right]=\underset{U\sim\mu_{H}}{\mathbb{E}}\left[f(U^{\dagger})\right]$
(46)

for any measurable function $f$, and the Pauli mixing property in Eq. (40) for
each of the single-qubit unitaries to conclude that
$\underset{u_{i}\sim\mu_{H}}{\mathbb{E}}[u_{i}^{\otimes 2}(P_{1}\otimes
P_{2})u_{i}^{\dagger\otimes 2}]=0$ for two different single-qubit Pauli
$P_{1}$ and $P_{2}$.

Similarly, for $P\in\\{I,X,Y,Z\\}^{\otimes n}$ such that $P=P_{1}\otimes
P_{2}\otimes\dotsb\otimes P_{n}$, we use the Pauli-mixing property in Eq.
(41), along with the fact that $U=\bigotimes_{i=1}^{n}u_{i}$ is a tensor
product of single-qubit unitaries from a 2-design, to obtain

$\displaystyle\underset{U\sim\nu}{\mathbb{E}}[\Tr(PU\rho U^{\dagger})^{2}]$
$\displaystyle=\underset{U\sim\nu}{\mathbb{E}}[\Tr(U^{\dagger\otimes
2}(P\otimes P)U^{\otimes 2}\rho^{\otimes 2})]$ (47)
$\displaystyle=\Tr\\!\left(\underset{U\sim\nu}{\mathbb{E}}\left[\bigotimes_{i=1}^{n}u_{i}^{\otimes
2}(P_{i}\otimes P_{i})u_{i}^{\dagger\otimes 2}\right]\rho^{\otimes 2}\right)$
$\displaystyle=\Tr\\!\left(\underset{U\sim\nu}{\mathbb{E}}\left[\bigotimes_{i\in\operatorname{supp}(P)}u_{i}^{\otimes
2}(P_{i}\otimes P_{i})u_{i}^{\dagger\otimes 2}\right]\rho^{\otimes 2}\right)$
$\displaystyle=\Tr\\!\left(\left(\bigotimes_{i\in\operatorname{supp}(P)}\frac{1}{3}\sum_{Q_{i}\in\\{X,Y,Z\\}}Q_{i}\otimes
Q_{i}\right)\rho^{\otimes 2}\right)$
$\displaystyle=\frac{1}{3^{|P|}}\sum_{\begin{subarray}{c}Q\in\\{I,X,Y,Z\\}^{\otimes
n}:\\\
\operatorname{supp}(Q)=\operatorname{supp}(P)\end{subarray}}\Tr(Q^{\otimes
2}\rho^{\otimes 2}),$

which is the desired result, because $\Tr(Q^{\otimes 2}\rho^{\otimes
2})=\Tr(Q\rho)^{2}$. ∎

###  A.3 Quantum channels

A _quantum channel_
$\mathcal{N}:\mathcal{L}(\mathbb{C}^{d})\rightarrow\mathcal{L}(\mathbb{C}^{d})$
is a linear, completely positive, and trace-preserving map. Completely
positive means that for all positive operators
$\sigma\in\mathcal{L}(\mathbb{C}^{d}\otimes\mathbb{C}^{D})$, for any
$D\in\mathbb{N}$, the operator $(\mathcal{N}\otimes\mathcal{I})(\sigma)$ is
positive. The trace-preserving property means that
$\Tr(\mathcal{N}(A))=\Tr(A)$ for any
$A\in\mathcal{L}\left(\mathbb{C}^{d}\right)$. Here,
$\mathcal{I}:\mathcal{L}\left(\mathbb{C}^{D}\right)\rightarrow\mathcal{L}\left(\mathbb{C}^{D}\right)$
denotes the identity map. Any quantum channel $\mathcal{N}$ can be represented
in terms of at most $d^{2}$ Kraus operators $\\{K_{i}\\}^{d^{2}}_{i=1}$, i.e.,

$\mathcal{N}\left(\cdot\right)=\sum^{d^{2}}_{i=1}K_{i}\left(\cdot\right)K^{\dagger}_{i},$
(48)

with the condition $\sum^{d^{2}}_{i=1}K^{\dagger}_{i}K_{i}=I$ to satisfy
trace-preservation. Given a quantum channel $\mathcal{N}$, we say that
$\mathcal{N}$ is _unital_ if and only if it maps the identity operator to the
identity operator, i.e., $\mathcal{N}(I)=I$. Otherwise, we say that
$\mathcal{N}$ is _non-unital_. Given a quantum channel
$\mathcal{N}:\mathcal{L}(\mathbb{C}^{d})\rightarrow\mathcal{L}(\mathbb{C}^{d})$,
its adjoint map
$\mathcal{N}^{\ast}:\mathcal{L}(\mathbb{C}^{d})\rightarrow\mathcal{L}(\mathbb{C}^{d})$
is defined as the linear map such that

$\langle\mathcal{N}^{\ast}(A),B\rangle_{HS}=\langle
A,\mathcal{N}(B)\rangle_{HS}$ (49)

for any $A,B\in\mathcal{L}\left(\mathbb{C}^{d}\right)$. If
$\\{K_{i}\\}^{d^{2}}_{i=1}$ is a set of Kraus operators for $\mathcal{N}$,
then the adjoint channel $\mathcal{N}^{*}$ can be expressed as

$\mathcal{N}^{*}(\cdot)=\sum^{d^{2}}_{i=1}K^{\dagger}_{i}(\cdot)K_{i}.$ (50)

Note that $\mathcal{N}^{*}$ is always unital, $\mathcal{N}^{*}(I)=I$,
inherited from the property of the channel being trace-preserving. However the
adjoint is not necessarily trace-preserving: it holds that $\mathcal{N}^{*}$
is trace preserving if and only if $\mathcal{N}$ is unital. If the Kraus
operators of the quantum channel $\mathcal{N}$ are Hermitian, then the adjoint
channel coincides with the quantum channel $\mathcal{N}^{*}=\mathcal{N}$. If
$\mathcal{N}_{1}$, $\mathcal{N}_{2}$ are two quantum channels, then
$(\mathcal{N}_{1}\circ\mathcal{N}_{2})^{*}=\mathcal{N}_{2}^{*}\circ\mathcal{N}_{1}^{*}$.
Moreover
$(\mathcal{N}_{1}\otimes\mathcal{N}_{2})^{*}=\mathcal{N}_{1}^{*}\otimes\mathcal{N}_{2}^{*}$.
For any Hermitian operator $O$, we have [102]

$\norm*{\mathcal{N}^{*}(O)}_{\infty}\leq\norm*{O}_{\infty}.$ (51)

####  A.3.1 Pauli transfer matrix representation of a quantum channel

In this subsection, we introduce the Pauli transfer matrix representation of a
single-qubit quantum channel. Let
$\mathcal{N}:\mathcal{L}(\mathbb{C}^{2})\rightarrow\mathcal{L}(\mathbb{C}^{2})$
be a linear map. Any linear map can be expressed in terms of its action on the
Pauli basis, i.e.

$\displaystyle\mathcal{N}(P)=\sum_{Q\in\\{I,X,Y,Z\\}}T_{Q,P}Q,$ (52)

where $T_{Q,P}\coloneqq\frac{1}{2}\Tr(Q\mathcal{N}(P))$. Assuming that
$\mathcal{N}$ represents a quantum channel, it inherently preserves
Hermiticity, implying that $T_{Q,P}\in\mathbb{R}$. Furthermore, by employing
the _Hölder inequality_ , we establish that $|T_{Q,P}|\leq 1$ for all
$P,Q\in\\{I,X,Y,Z\\}$. Given that a quantum channel is trace-preserving and
the Pauli matrices are all trace-less except for the identity, we deduce that
$T_{I,P}=\delta_{I,P}$. Consequently, we have

$\displaystyle\mathcal{N}(I)$ $\displaystyle=I+T_{X,I}X+T_{Y,I}Y+T_{Z,I}Z,$
(53) $\displaystyle\mathcal{N}(X)$ $\displaystyle=T_{X,X}X+T_{Y,X}Y+T_{Z,X}Z,$
(54) $\displaystyle\mathcal{N}(Y)$ $\displaystyle=T_{X,Y}X+T_{Y,Y}Y+T_{Z,Y}Z,$
(55) $\displaystyle\mathcal{N}(Z)$ $\displaystyle=T_{X,Z}X+T_{Y,Z}Y+T_{Z,Z}Z.$
(56)

From Eqs. (53)-(56), we can see that considering a non-unital noise channel is
equivalent to assuming that at least one of the parameters $T_{X,I}$,
$T_{Y,I}$, or $T_{Z,I}$ must be non-zero.

We define the Pauli transfer matrix $\mathrm{T}(\mathcal{N})$ of the channel
$\mathcal{N}$ as the matrix with components defined as
$[\mathrm{T}(\mathcal{N})]_{Q,P}\coloneqq\frac{1}{2}\Tr(Q\mathcal{N}(P))=T_{Q,P}$
for all $Q,P\in\\{I,X,Y,Z\\}$, i.e.,

$\mathrm{T}(\mathcal{N})=\begin{bmatrix}1&0&0&0\\\
T_{X,I}&T_{X,X}&T_{X,Y}&T_{X,Z}\\\ T_{Y,I}&T_{Y,X}&T_{Y,Y}&T_{Y,Z}\\\
T_{Z,I}&T_{Z,X}&T_{Z,Y}&T_{Z,Z}\\\ \end{bmatrix}.$ (57)

It is important to note that any single-qubit quantum channel can be expressed
in such a form. However, not every linear map of this form represents a valid
quantum channel. Furthermore, utilizing the definition of the adjoint map, we
can easily verify that the adjoint map $\mathcal{N}^{*}$ is given by
$\mathcal{N}^{*}(P)=\sum_{Q\in\\{I,X,Y,Z\\}}T_{P,Q}Q$. This results in the
fact that the Pauli transfer matrix of the adjoint channel is the transpose of
the Pauli transfer matrix of the channel, i.e.,

$\displaystyle\mathrm{T}(\mathcal{N}^{*})=\mathrm{T}(\mathcal{N})^{T}.$ (58)

Given two quantum channels $\mathcal{N}^{(A)}$ and $\mathcal{N}^{(B)}$, we
have that the Pauli transfer matrix associated to their composition is given
by the multiplication of their Pauli transfer matrices:

$\displaystyle\mathrm{T}(\mathcal{N}^{(A)}\circ\mathcal{N}^{(B)})=\mathrm{T}(\mathcal{N}^{(A)})\cdot\mathrm{T}(\mathcal{N}^{(B)}).$
(59)

####  A.3.2 Normal form representation of a quantum channel

We now present a quantum channel representation [29, 83] that will be useful
when dealing with noisy random circuits. In words, it says that the Pauli
transfer matrix of a single-qubit noise channel, up to unitary rotations, is
diagonal in the sub-block corresponding to the non-identity Pauli matrices. We
include here the lemma and proof of this representation for easy reference.

######  Lemma 17 (Normal form of a quantum channel [29, 83]).

Any single-qubit quantum channel $\mathcal{N}$ can be written in the so called
‘normal’ form:

$\displaystyle\mathcal{N}(\cdot)=U\mathcal{N}^{\prime}(V^{{\dagger}}(\cdot)V)U^{{\dagger}},$
(60)

where $U$, $V$ are unitaries and $\mathcal{N}^{\prime}(\cdot)$ is a quantum
channel with Pauli transfer matrix

$\mathrm{T}(\mathcal{N}^{\prime})=\begin{bmatrix}1&0&0&0\\\ t_{X}&D_{X}&0&0\\\
t_{Y}&0&D_{Y}&0\\\ t_{Z}&0&0&D_{Z}\\\ \end{bmatrix},$ (61)

where $\mathbb{t}\coloneqq(t_{X},t_{Y},t_{Z})$ and
$\mathbb{D}\coloneqq(D_{X},D_{Y},D_{Z})\in\mathbb{R}^{3}$, such that the
entries of $\mathbb{D}$ have all the same sign.

###### Proof.

Let us consider the Pauli transfer matrix of $\mathcal{N}$, which is
characterized by the real $3\times 3$ matrix $B\in\mathcal{L}(\mathbb{R}^{3})$
and the vector $\boldsymbol{b}=(b_{X},b_{Y},b_{Z})\in\mathbb{R}^{3}$:

$\displaystyle\mathrm{T}(\mathcal{N})=\begin{bmatrix}1&0&0&0\\\
b_{X}&B_{X,X}&B_{X,Y}&B_{X,Z}\\\ b_{Y}&B_{Y,X}&B_{Y,Y}&B_{Y,Z}\\\
b_{Z}&B_{Z,X}&B_{Z,Y}&B_{Z,Z}\\\ \end{bmatrix}.$ (62)

Any single qubit quantum state $\rho$ can be written as
$\rho=(I+\mathbb{w}\cdot\boldsymbol{\sigma})/2$, where
$\mathbb{w}\coloneqq(w_{X},w_{Y},w_{Z})\in\mathbb{R}^{3}$ with
$\norm*{w}_{2}\leq 1$ and $\boldsymbol{\sigma}\coloneqq(X,Y,Z)$. Then, we have

$\displaystyle\mathcal{N}(\rho)=\mathcal{N}\\!\left(\frac{I}{2}\right)+\frac{1}{2}\mathcal{N}\\!\left(\mathbb{w}\cdot\boldsymbol{\sigma}\right)=\left(\frac{I}{2}+\frac{1}{2}\boldsymbol{b}\cdot\boldsymbol{\sigma}\right)+\frac{1}{2}(B\mathbb{w})\cdot\boldsymbol{\sigma}=\frac{I}{2}+\frac{1}{2}(\boldsymbol{b}+B\mathbb{w})\cdot\boldsymbol{\sigma}.$
(63)

Next, because $B$ is real, we can perform a real singular value decomposition
of $B$ and have $B=R_{1}DR^{T}_{2}$, where $D$ is a diagonal matrix with the
non-negative diagonal elements $(D_{X},D_{Y},D_{Z})\in\mathbb{R}^{3}$ and
$R_{1},R_{2}$ are in general orthogonal $\mathrm{O}(3)$ matrices. Now, every
orthogonal matrix has determinant equal to $\pm 1$. This fact, along with the
fact that $\textrm{det}(-R)=(-1)^{3}\textrm{det}(R)=-\textrm{det}(R)$ for
every $R\in\mathrm{O}(3)$, means that we can, without loss of generality,
assume that $R_{1}$ and $R_{2}$ both have determinant equal to $1$. In other
words, we can assume that $R_{1}$ and $R_{2}$ are both special-orthogonal
matrices in $\textrm{SO}(3)$. The diagonal elements $(D_{X},D_{Y},D_{Z})$ are
then not necessarily non-negative, but they all have the same sign. We now use
the fact that for every special-orthogonal matrix $R\in\mathrm{SO}(3)$, there
exists a unitary $U\in\mathrm{U}(2)$ such that [103]:

$\displaystyle(R\boldsymbol{v})\cdot\boldsymbol{\sigma}=U(\boldsymbol{v}\cdot\boldsymbol{\sigma})U^{\dagger},$
(64)

for all $\boldsymbol{v}\in\mathbb{R}^{3}$. The previous identity can be easily
verified by choosing
$U\coloneqq\exp(-i\frac{\theta}{2}\hat{n}\cdot\boldsymbol{\sigma})$, where
$\hat{n}$ and $\theta$ are, respectively, the unit-norm vector and the
rotation angle which characterizes the special-orthogonal matrix
$R\in\mathrm{SO}(3)$. Thus, we have that

$\displaystyle\mathcal{N}(\rho)=U\left(\frac{I}{2}+\frac{1}{2}(R^{T}_{1}\boldsymbol{b}+DR^{T}_{2}\mathbb{w})\cdot\boldsymbol{\sigma}\right)U^{\dagger}=U\mathcal{N}^{\prime}\left(\frac{I+(R^{T}_{2}\mathbb{w})\cdot\boldsymbol{\sigma}}{2}\right)U^{\dagger}=U\mathcal{N}^{\prime}\left(V^{{\dagger}}\left(\frac{I+\mathbb{w}\cdot\boldsymbol{\sigma}}{2}\right)V\right)U^{\dagger},$
(65)

where $U$ and $V$ are the unitaries associated to the special-orthogonal
matrices $R_{1}$ and $R_{2}$, and $\mathcal{N}^{\prime}$ is the linear map
such that
$\mathcal{N}^{\prime}(\frac{I+\mathbb{w}\cdot\boldsymbol{\sigma}}{2})=\frac{I+(\mathbb{t}+D\mathbb{w})\cdot\boldsymbol{\sigma}}{2}$,
where $\mathbb{t}\coloneqq R^{T}_{1}\boldsymbol{b}$. Hence, we have shown that
$\mathcal{N}(\rho)$ can be written as
$\mathcal{N}(\rho)=U\mathcal{N}^{\prime}\left(V^{{\dagger}}\rho
V\right)U^{\dagger}$, where the Pauli transfer matrix of
$\mathcal{N}^{\prime}$ is the one in Eq. (61). ∎

Thus, every single-qubit quantum channel $\mathcal{N}$ can be expressed as
$\mathcal{N}(\cdot)=U\mathcal{N}^{\prime}(V^{{\dagger}}(\cdot)V)U^{{\dagger}}$,
where $U$, $V$ are unitaries, and $\mathcal{N}^{\prime}$ is a quantum channel
such that it acts on a quantum state written in its Bloch sphere
representation as

$\displaystyle\mathcal{N}^{\prime}\\!\left(\frac{I+\mathbb{w}\cdot\boldsymbol{\sigma}}{2}\right)=\frac{I}{2}+\frac{1}{2}(\mathbb{t}+D\mathbb{w})\cdot\boldsymbol{\sigma},$
(66)

where $\mathbb{w}\in\mathbb{R}^{3}$ with $\|\mathbb{w}\|_{2}\leq 1$,
$\mathbb{t}\coloneqq(t_{X},t_{Y},t_{Z})\in\mathbb{R}^{3}$ and
$D\coloneqq\mathrm{diag}(\mathbb{D})$ with
$\mathbb{D}\coloneqq(D_{X},D_{Y},D_{Z})\in\mathbb{R}^{3}$.

We now prove that the parameters of the normal form representation satisfy a
particular constrain. Such constrain will be crucial in our following
discussion.

######  Lemma 18 (Contraction coefficient in terms of the normal form
parameters).

For any single-qubit quantum channel, the parameters
$\mathbb{t},\mathbb{D}\in\mathbb{R}^{3}$ of its normal form representation
satisfy:

$\displaystyle
c\coloneqq\frac{1}{3}(t^{2}_{X}+D^{2}_{X}+t^{2}_{Y}+D^{2}_{Y}+t^{2}_{Z}+D^{2}_{Z})\leq
1,$ (67)

and the equality is saturated if and only if the channel is unitary.
Furthermore, it also holds $\norm*{\mathbb{t}}_{2}\leq 1$.

###### Proof.

Because of the previous Lemma, any single-qubit quantum channel $\mathcal{N}$
can be expressed as
$\mathcal{N}(\cdot)=U\mathcal{N}^{\prime}(V^{{\dagger}}(\cdot)V)U^{{\dagger}}$,
where $U$, $V$ are unitaries, and $\mathcal{N}^{\prime}$ such that it holds
Eq. (66). Let $\rho$ be an arbitrary qubit quantum state. Noting that
$\mathcal{N}^{\prime}$ is a quantum channel, on account of being a composition
of quantum channels, it holds that
$\norm*{\mathcal{N}^{\prime}(\rho)}_{\infty}\leq 1$. If we let
$\mathbb{w}\in\mathbb{R}^{3}$ be the Bloch vector corresponding to $\rho$,
then because $\norm*{\mathcal{N}^{\prime}(\rho)}_{\infty}$ is equal to the
largest eigenvalue of $\mathcal{N}^{\prime}(\rho)$, we find that

$\displaystyle
1\geq\norm*{\mathcal{N}^{\prime}(\rho)}_{\infty}=\frac{1}{2}(1+\norm*{\mathbb{t}+D\mathbb{w}}_{2}).$
(68)

Hence, we get

$\displaystyle(t_{X}+D_{X}w_{x})^{2}+(t_{Y}+D_{Y}w_{y})^{2}+(t_{Z}+D_{Z}w_{z})^{2}=\norm*{\mathbb{t}+D\mathbb{w}}^{2}_{2}\leq
1.$ (69)

Now, recall that $\norm*{\mathbb{w}}_{2}\leq 1$. If $\mathbb{w}=0$, then we
get $\norm*{\mathbb{t}}_{2}\leq 1$. In particular by choosing $w=(\pm 1,0,0)$,
we get

$\displaystyle(t_{X}\pm D_{X})^{2}\leq 1,$ (70)

and similarly for $Y$ and $Z$. Now, assume that the entries of $\mathbb{D}$
are all non-negative (remember that they have the same sign). Together with
the previous equation, this implies that

$\displaystyle
t_{X}^{2}+D^{2}_{X}+t_{Y}^{2}+D^{2}_{Y}+t_{Z}^{2}+D^{2}_{Z}\leq(t_{X}+\mathrm{sign}(t_{X})D_{X})^{2}+(t_{Y}+\mathrm{sign}(t_{Y})D_{Y})^{2}+(t_{Z}+\mathrm{sign}(t_{Z})D_{Z})^{2}\leq
3.$ (71)

Similarly, if the entries of $\mathbb{D}$ are all negative, we have

$\displaystyle
t_{X}^{2}+D^{2}_{X}+t_{Y}^{2}+D^{2}_{Y}+t_{Z}^{2}+D^{2}_{Z}\leq(t_{X}-\mathrm{sign}(t_{X})D_{X})^{2}+(t_{Y}-\mathrm{sign}(t_{Y})D_{Y})^{2}+(t_{Z}-\mathrm{sign}(t_{Z})D_{Z})^{2}\leq
3.$ (72)

This proves Eq. (67).

Finally, we show that Eq. (67) is saturated if and only if $\mathcal{N}$ is
unitary. If $\mathcal{N}$ is unitary, then also $\mathcal{N}^{\prime}$ is
unitary. This implies that $\mathbb{t}=0$, because unitary channels are also
unital. Moreover, it also implies that the purity of any state must remain the
same, so the diagonal matrix $D\coloneqq\mathrm{diag}(\mathbb{D})$ must be
norm-preserving, hence orthogonal. Therefore, we have
$D=\pm\mathrm{diag}(1,1,1)$. This saturates inequality (67). Now, let us
assume that

$\displaystyle\frac{1}{3}(t^{2}_{X}+D^{2}_{X}+t^{2}_{Y}+D^{2}_{Y}+t^{2}_{Z}+D^{2}_{Z})=1.$
(73)

From the inequality (70), we get also that $t_{X}^{2}+D^{2}_{X}\leq 1$, and
the same for $Y$ and $Z$. Hence, Eq. (73) implies $t_{X}^{2}+D^{2}_{X}=1$, and
the same for $Y$ and $Z$. Using this with Eq. (70), we have that the possible
values for $t_{X}^{2}$ and $D_{X}^{2}$ are, respectively, $1$ and $0$, or vice
versa. Similarly for $Y$ and $Z$. From Eq. (69), we deduce that the only
possibility is that $\mathbb{t}=0$ and that $D_{X}^{2}=D_{Y}^{2}=D_{Z}^{2}=1$.
Hence, we have that the Pauli transfer matrix of $\mathcal{N}^{\prime}$ is
equal, up to a possible minus sign factor, to the identity matrix. This
implies that $\mathcal{N}^{\prime}$ must be the identity channel and that
$\mathcal{N}$ is unitary. ∎

Here, we give examples of normal form parameters
$\mathbb{t}=(t_{X},t_{Y},t_{Z})$ and $\mathbb{D}=(D_{X},D_{Y},D_{Z})$ for
standard noise channels. The single-qubit depolarizing channel with parameter
$p\in[0,1]$ can be defined as

$\displaystyle\mathcal{N}_{p}^{(\mathrm{\mathrm{dep}})}(\sigma)=(1-p)\sigma+p\Tr(\sigma)\frac{I}{2}.$
(74)

Its normal form parameters are $\mathbb{t}=(0,0,0)$ and
$\mathbb{D}=(1-p,1-p,1-p)$. The amplitude damping channel
$\mathcal{N}_{q}^{(\text{amp})}$, parameterized by $q\in[0,1]$, is given in
the computational basis as

$\mathcal{N}_{q}^{(\text{amp})}(\sigma)=\begin{pmatrix}\sigma_{0,0}+q\sigma_{1,1}&\sqrt{1-q}\sigma_{0,1}\\\
\sqrt{1-q}\sigma_{1,0}&(1-q)\sigma_{1,1}\\\ \end{pmatrix},$ (75)

where $\sigma_{i,j}\coloneqq\bra{i}\sigma\ket{j}$. Here, $\mathbb{t}=(0,0,q)$
and $\mathbb{D}=(\sqrt{1-q},\sqrt{1-q},1-q)$. The single-qubit dephasing
channel $\mathcal{N}_{p}^{(\text{deph})}$ with $p\in[0,1]$ can be defined as

$\mathcal{N}_{p}^{(\text{deph})}(\sigma)=\begin{pmatrix}\sigma_{0,0}&(1-p)\sigma_{0,1}\\\
(1-p)\sigma_{1,0}&\sigma_{1,1}\\\ \end{pmatrix}.$ (76)

Its normal form parameters are $\mathbb{t}=(0,0,0)$ and
$\mathbb{D}=(1-p,1-p,1)$.

###  A.4 Circuit and noise model

In our work, we examine $n$-qubit quantum circuits $\Phi$ formed by layers of
two-qubit random unitary gates interleaved by local noise, with a final layer
of random single qubit gates. For example, the standard brickwork circuit
architecture is within our model (Figure 2). Mathematically,

$\displaystyle\Phi\coloneqq\mathcal{V}^{\mathrm{single}}\circ\mathcal{N}^{\otimes
n}\circ\mathcal{U}_{L}\circ\cdots\circ\mathcal{N}^{\otimes
n}\circ\mathcal{U}_{1},$ (77)

where $\mathcal{V}^{\mathrm{single}}\coloneqq V(\cdot)V^{\dagger}$ with
$V\coloneqq\bigotimes^{n}_{i=1}u_{i}$ is a layer of single-qubit gates,
$\mathcal{U}_{i}\coloneqq U_{i}(\cdot)U^{{\dagger}}_{i}$ corresponds to the
$n$-qubit unitary channel associated with the $i$-th unitary layer $U_{i}$ for
$i\in[L]$, and $\mathcal{N}$ is a single-qubit quantum channel.

Figure 2: Example of the architecture that our model encompasses: A brickwork
circuit composed of two-qubit gates followed by local noise (depicted with
yellow circles).

#### Assumption on the circuit distribution

Firstly, we assume that each single-qubit gate in the layer
$\bigotimes^{n}_{i=1}u_{i}$ is distributed according to a single-qubit
$2$-design (e.g., Haar random). Moreover, we assume that each unitary layer
$\mathcal{U}_{i}\coloneqq U_{i}(\cdot)U^{\dagger}_{i}$, for $i\in[L]$,
consists of two-local qubit gates, each forming a local $2$-design. More
precisely, we assume that each $U_{i}$ for $i\in[L]$ is distributed according
to a $2$-local $2$-design layer distribution, defined as follows:

######  Definition 19 ($2$-local $2$-design layer distribution).

We say that $\nu$ is a $2$-local $2$-design layer distribution if and only if
it is a probability distribution over quantum circuits formed by local
$2$-qubit gates, where each of them is distributed accordingly to a local
$2$-design and each qubit is acted on by at least one of the gates.

Moreover, we point out that we consider an arbitrary circuit
geometry/architecture, i.e., we do not make any particular assumptions on the
geometric dimensionality of our circuit, except when explicitly mentioned.
Note that our model is in stark contrast to works [66, 33] where the unitary
layers are chosen as global $n$-qubit $2$-designs, and we expect that the
model that we consider is more realistic.

#### Noise model

Moreover, since before and after any noise channel $\mathcal{N}$ there is a
gate that is distributed according to a $2$-design and in our work we consider
up to second moment quantities, because of the normal form representation of
the channel and unitary invariance, we can restrict the noise channels
$\mathcal{N}$ to have a sparse Pauli transfer matrix of the form of Eq. (61),
characterized by two real vectors $\mathbb{t}\coloneqq(t_{X},t_{Y},t_{Z})$ and
$\mathbb{D}\coloneqq(D_{X},D_{Y},D_{Z})$. In particular, the adjoint channel
$\mathcal{N}^{*}$ acts on $Q\in\\{X,Y,Z\\}$ as

$\displaystyle\mathcal{N}^{*}(Q)=t_{Q}I+D_{Q}Q=\sum_{a\in\\{0,1\\}}D_{Q}^{a}t_{Q}^{1-a}Q^{a}.$
(78)

Since we work with at most second-moment quantities, we often single out ‘for
free’ from each $2$-local $2$-design unitary layer
$\\{\mathcal{U}_{i}\\}^{L}_{i=1}$ layers of single qubit Haar random gates,
due to the invariance of the Haar measure and because each qubit is a acted on
by at least one of the $2$-local $2$-design gates. Specifically, without loss
of generality, we can consider equivalently circuits of the form

$\displaystyle\Phi=(\mathcal{V}_{L}^{\,\mathrm{single}}\circ\mathcal{N}^{\otimes
n}\circ\mathcal{U}_{L})\circ\cdots\circ(\mathcal{V}_{1}^{\,\mathrm{single}}\circ\mathcal{N}^{\otimes
n}\circ\mathcal{U}_{1}),$ (79)

where $\\{\mathcal{V}_{k}^{\mathrm{single}}\\}^{L}_{k=1}$ are layers of
single-qubit gates distributed according a single-qubit $2$-design. However,
such single qubits layers, apart from $\mathcal{V}_{L}^{\,\mathrm{single}}$,
do not play a fundamental role in our model and can be removed. We will often
denote circuits derived from $\Phi$ by removing the last layer of single-qubit
gates and the last layer of noise. In this case, we use the notation

$\displaystyle\Phi^{\prime}$ $\displaystyle\coloneqq(\mathcal{N}^{\otimes
n}\circ\mathcal{U}_{L})\circ\cdots\circ(\mathcal{V}_{1}^{\,\mathrm{single}}\circ\mathcal{N}^{\otimes
n}\circ\mathcal{U}_{1}),$ (80) $\displaystyle\Phi^{\prime\prime}$
$\displaystyle\coloneqq\mathcal{U}_{L}\circ\cdots\circ(\mathcal{V}_{1}^{\,\mathrm{single}}\circ\mathcal{N}^{\otimes
n}\circ\mathcal{U}_{1}).$ (81)

Here, $\Phi^{\prime}$ denotes the circuit without the final layer of single-
qubit gates, while $\Phi^{\prime\prime}$ denotes the circuit without the final
layer of single-qubit gates layer and also without the final layer of noise.

We also often need to denote circuits derived from $\Phi$ by retaining certain
layers from the start or from the end. In these cases, we use subscripts to
indicate the relevant layers. That is, for $a\leq b\in[L]$,

$\displaystyle\Phi_{[a,b]}$
$\displaystyle\coloneqq(\mathcal{V}_{b}^{\mathrm{single}}\circ\mathcal{N}^{\otimes
n}\circ\mathcal{U}_{b})\circ\cdots\circ(\mathcal{V}_{a}^{\mathrm{single}}\circ\mathcal{N}^{\otimes
n}\circ\mathcal{U}_{a}).$ (82)

Whenever we write an expectation value, $\mathbb{E}[\cdot]$ or
$\mathrm{Var}[\cdot]$, without explicitly specifying the underlying
distribution, we consider the probability distribution over the defined random
circuit.

##  Appendix B Pauli expectation values of noisy random quantum circuits

In this section, we analyze expectation values of random quantum circuits
under possibly non-unital noise. We make here a summary of our results that we
analyze in detail in their respective subsections. We consider a circuit
$\Phi$ as we described in subsection A.4, where the local noise channels are
characterized by the parameters of their normal form representation
$\mathbb{t}\coloneqq(t_{X},t_{Y},t_{Z})$ and
$\mathbb{D}\coloneqq(D_{X},D_{Y},D_{Z})$, which we assume to be constants with
respect to the number of qubits. Our first main theorem is the following.

######  Theorem 20 (Variance of expectation values of random circuits with
non-unital noise).

Let $H\coloneqq\sum_{P\in\\{I,X,Y,Z\\}^{\otimes n}}a_{P}P$, with
$a_{P}\in\mathbb{R}$ for $P\in\\{I,X,Y,Z\\}^{\otimes n}$, be an arbitrary
Hamiltonian. Let $\rho$ be a quantum state. We assume that the noise is non-
unital, specifically $\norm*{\mathbb{t}}_{2}=\Theta(1)$. Then, at any depth of
the noisy circuit $\Phi$, as defined in Eq. (77), we have

$\displaystyle\mathrm{Var}[\Tr(H\Phi(\rho))]=\sum_{P\in\\{I,X,Y,Z\\}^{\otimes
n}}a_{P}^{2}\exp(-\Theta(|P|)).$ (83)

To prove Theorem 20, we make use of results we show in subsection B.1 and
subsection B.2, where we respectively show a lower bound on the variance
(Proposition 23) and a matching upper bound (Proposition 25).

Theorem 20 directly implies that the variance of expectation value of local
observables (i.e., _local expectation values_) can be significantly large,
e.g., $\mathrm{Var}[\Tr(Z_{1}\Phi(\rho))]=\Omega(1)$. This means that local
expectation values can deviate significantly from their mean value
$\mathbb{E}[\Tr(H\Phi(\rho))]$. This is in stark contrast to the behaviour of
noiseless random quantum circuits or circuits with unital noise [48, 20].
Theorem 20 also implies that the variance of expectation value of global
observables (i.e., _global expectation values_) are exponentially concentrated
to their mean value, e.g., $\mathrm{Var}[\Tr(Z^{\otimes
n}\Phi(\rho))]=\exp(-\Omega(n))$.

Moreover, based on the results shown in Subsection B.3 and in Subsection B.4,
we prove the following result.

######  Theorem 21 (Average distance between two quantum states).

Let $P\in\\{I,X,Y,Z\\}^{\otimes n}$. Let $\rho$ and $\sigma$ be any quantum
states. Let $\Phi$ be any noisy random quantum circuit with depth $L$, as
defined in Eq. (77). We assume that the noise is not a unitary channel. Then,

$\displaystyle\mathbb{E}[|\Tr(P\Phi(\rho))-\Tr(P\Phi(\sigma))|]\leq\exp\\!\left(-\Omega\\!\left(L+|P|\right)\right),$
(84)

This implies that for $L=\Omega(n)$, we have

$\displaystyle\mathbb{E}[\norm*{\Phi(\rho)-\Phi(\sigma)}_{1}]\leq\exp(-\Omega(n)).$
(85)

The average trace distance upper bound is proven in Subsection B.4, where we
prove also a worst-case trace distance upper bound (i.e., without the expected
value) that holds in the high-noise regime. Note that we cannot hope to prove
a worst-case upper bound on the trace distance that is valid for every noise
regime. This is because there are quantum error correction methods, such as
the so-called _quantum refrigerator_ construction [26], which can leverage
non-unital noise to perform fault-tolerant quantum computation in a model
similar to ours, up to depths that are exponential in the number of qubits.