††thanks: These authors contributed equally to this work.††thanks: These
authors contributed equally to this work.

# A polynomial-time classical algorithm for noisy quantum circuits

Thomas Schuster  Walter Burke Institute for Theoretical Physics and Institute
for Quantum Information and Matter, California Institute of Technology,
Pasadena, California 91125, USA  Chao Yin  Department of Physics and Center
for Theory of Quantum Matter, University of Colorado, Boulder, CO 80309, USA
Xun Gao  Department of Physics and Center for Theory of Quantum Matter,
University of Colorado, Boulder, CO 80309, USA  JILA, University of Colorado,
Boulder, CO 80309, USA  Norman Y. Yao  Department of Physics, Harvard
University, Cambridge, MA 02138, USA

###### Abstract

We provide a polynomial-time classical algorithm for noisy quantum circuits.
The algorithm computes the expectation value of any observable for any
circuit, with a small average error over input states drawn from an ensemble
(e.g. the computational basis). Our approach is based upon the intuition that
noise exponentially damps non-local correlations relative to local
correlations. This enables one to classically simulate a noisy quantum circuit
by only keeping track of the dynamics of local quantum information. Our
algorithm also enables sampling from the output distribution of a circuit in
quasi-polynomial time, so long as the distribution anti-concentrates. A number
of practical implications are discussed, including a fundamental limit on the
efficacy of noise mitigation strategies: any quantum circuit for which error
mitigation is efficient must be classically simulable.

##  I Introduction

Quantum computers are believed to yield exponential computational advantages
over their classical counterparts for certain tasks Feynman (2018); Shor
(1994); Bauer  _et al._ (2020); Dalzell  _et al._ (2023). However, near-term
quantum devices are inevitably impacted by noise. This raises a key question
Aharonov and Ben-Or (1996); Aharonov (2000); Harrow and Nielsen (2003); Kempe
_et al._ (2008); Shor (1996); Aharonov and Ben-Or (1997); Kitaev (1997); Knill
_et al._ (1998); Aharonov  _et al._ (1996); Ben-Or  _et al._ (2013); Dalzell
_et al._ (2021); Deshpande  _et al._ (2022); Chen  _et al._ (2022); Huang  _et
al._ (2020); Liu  _et al._ (2021); Pan and Zhang (2021); Villalonga  _et al._
(2020); Cheng  _et al._ (2021); Noh  _et al._ (2020); White  _et al._ (2018);
Ye  _et al._ (2020); Rakovszky  _et al._ (2022); Von Keyserlingk  _et al._
(2022); White (2023); Yoo  _et al._ (2023); Vovk and Pichler (2022); Chen  _et
al._ (2023); Cheng and Ippoliti (2023); Bremner  _et al._ (2017); Rajakumar
_et al._ (2024); Gao and Duan (2018); Barak  _et al._ (2020); Gao  _et al._
(2021); Aharonov  _et al._ (2023); Yung and Gao (2017); Fontana  _et al._
(2023); Shao  _et al._ (2023); Bouland  _et al._ (2022); Mele  _et al._
(2024); Movassagh and Schenker (2021); Bouland  _et al._ (2022); Fujii (2016);
Kalai and Kindler (2014); García-Patrón  _et al._ (2019); Qi  _et al._ (2020);
Oh  _et al._ (2023a, b); Hangleiter and Gullans (2023): To what degree does
noise _fundamentally_ limit any quantum advantage over classical computation?

The answer to this question is well understood in two limits. On the one hand,
for noise rates above a large threshold, seminal works have shown that noisy
quantum circuits can be simulated classically Aharonov and Ben-Or (1996);
Aharonov (2000); Harrow and Nielsen (2003); Kempe  _et al._ (2008). On the
other hand, for sufficiently low noise rates, one can utilize quantum error
correction to perform fault-tolerant computation Shor (1996); Aharonov and
Ben-Or (1997); Kitaev (1997); Knill  _et al._ (1998). Nevertheless, the
reality of modern quantum experiments lies precisely in between these two
limits: Noise rates are small but error correction is not typically employed.
Progress in this intermediate regime has been restricted to several relatively
specific contexts: bounds on the circuit depth but not the complexity Aharonov
_et al._ (1996); Ben-Or  _et al._ (2013); Dalzell  _et al._ (2021); Deshpande
_et al._ (2022), tasks that assume access to a noiseless oracle Chen  _et al._
(2022), hardness results for sampling with extremely high precision Bouland
_et al._ (2022); Dalzell  _et al._ (2024) or error detection Fujii (2016);
Bremner  _et al._ (2017); Paletta  _et al._ (2024), and classical algorithms
for instantaneous quantum polynomial (IQP) circuits Bremner  _et al._ (2017);
Rajakumar  _et al._ (2024) and random quantum circuits Gao and Duan (2018);
Barak  _et al._ (2020); Gao  _et al._ (2021); Aharonov  _et al._ (2023); Yung
and Gao (2017); Fontana  _et al._ (2023); Shao  _et al._ (2023); Bouland  _et
al._ (2022); Mele  _et al._ (2024). To date, however, there are no rigorous
results on the computational power of general quantum circuits with low noise
rates but without error correction.

In this work, we provide a classical algorithm for simulating _any_ noisy
quantum circuit on almost any input state. The restriction to “almost any”
input state is fundamental, since for a fixed input state and a sufficiently
low noise rate, one can immediately perform quantum error correction. To this
end, with a high probability over input states drawn from an ensemble, our
algorithm succeeds in computing the expectation value of any observable (to
within a small error) for any noisy quantum circuit. We emphasize that our
restriction to ensembles of input states is relatively weak—a wide range of
ensembles are allowed, including the computational basis states. In order to
compute the observable’s expectation value, our algorithm simulates the
Heisenberg time-evolution of the observable in the Pauli basis. The key
insight underlying our algorithm is the close connection between sets of Pauli
operators that are hard-to-classically-simulate, and those that are strongly
affected by noise. By truncating such high-weight Pauli operators, our
algorithm runs in either polynomial or quasi-polynomial time, depending on the
observable and the noise model of interest. For circuits that anti-concentrate
Bremner  _et al._ (2017); Aharonov  _et al._ (2023), our algorithm also
enables sampling from the circuit in quasi-polynomial time.

Our results have wide-ranging consequences for near-term quantum experiments.
First, we show that any strategy for quantum error mitigation Temme  _et al._
(2017); Li and Benjamin (2017); Cai  _et al._ (2023) can only scale
efficiently Quek  _et al._ (2022); Takagi  _et al._ (2022, 2023) for quantum
circuits that are easy to classically simulate. Second, we build upon our
results to construct a simple and strict test for whether a given quantum
circuit can exhibit quantum advantage. We find that any circuit exhibiting
advantage must be macroscopically sensitive to noise. Finally, we provide an
extension of our algorithm to quantum circuits with non-unital noise Fefferman
_et al._ (2023); Mele  _et al._ (2024), provided that the noise is
sufficiently unstructured to avoid no-go results Ben-Or  _et al._ (2013).

Figure 1: (a) Schematic of a noisy quantum circuit. The input state $\rho$ is
acted on by a circuit of arbitrary two-qubit gates (pink) and local noise
channels (dots), and concludes with measurement of an observable $O$. In the
gate-based noise model, the noise only acts on a qubit when a gate is
performed (black dots). In the uniform noise model, even when the qubit is
idle, noise can occur (dashed dots). (b) For circuits with uniform noise, our
classical algorithm decomposes the expectation value of $O$ as a sum of Pauli
paths. We depict each path by a space-time grid, where each square denotes
whether the path is the identity (white) or $X$, $Y$, or $Z$ (red, yellow, or
purple) at that qubit and circuit layer. Our algorithm computes the sum of all
low-weight paths (left), and truncates high-weight paths (right) since they
are strongly damped by noise (fading). (c) For circuits with gate-based noise,
our algorithm instead simulates the Heisenberg time-evolution of $O$ within
the subspace of low-weight Pauli operators. That is, at each layer, we
truncate all Pauli operators with weight above a threshold $\ell$ (dashed red
line). The plot depicts the weight of various components of the time-evolved
operator (blue lines), as they are acted on by noise (fading) and,
potentially, truncated by our algorithm (red scissors).

##  II Classical algorithm for noisy quantum circuits

Consider a noisy quantum circuit on $n$ qubits, of the form

$\mathcal{C}\\{\rho\\}=\mathcal{D}_{0}\\{U_{1}\,\mathcal{D}_{1}\\{\ldots
U_{d}\,\mathcal{D}_{d}\\{\rho\\}\,U_{d}^{\dagger}\ldots\\}\,U_{1}^{\dagger}\\},$
(1)

where $\rho$ is the input state, $U_{t}$ are depth-1 unitaries of arbitrary
two-qubit gates, and $\mathcal{D}_{t}$ are local depolarizing noise channels.
Here, $d$ is the circuit depth, and $t=1,\ldots,d$ indexes the circuit layers
in reverse order. After the circuit is applied, we are interested in either
computing the expectation value of an observable $O$,
$\tr(\mathcal{C}\\{\rho\\}O)$, or sampling from the outcomes when
$\mathcal{C}\\{\rho\\}$ is measured in the computational basis.

We consider two archetypal noise models [Fig. 1(a)]: uniform noise and gate-
based noise. In the _uniform noise_ case, every qubit is affected by noise at
every circuit layer. That is, we take
$\mathcal{D}_{t}=\bigotimes_{j=1}^{n}\mathcal{D}_{j}$, where
$\mathcal{D}_{j}\\{\rho\\}=e^{-\gamma}\rho+(1-e^{-\gamma})\tr_{j}(\rho)$ is a
local depolarizing channel of strength $\gamma$. This noise model is relevant
for many current experiments, in which idle errors affect qubits even when
they are not involved in gates. However, the uniform noise model only allows
computation up to a depth logarithmic in the number of qubits, after which the
system is close to the maximally mixed state Aharonov  _et al._ (1996); fn
(2). To this end, we also consider the so-called _gate-based noise_ model, in
which qubits are only affected by noise when they participate in non-identity
gates, $\mathcal{D}_{t}=\bigotimes_{j\in U_{t}}\mathcal{D}_{j}$; we note that
this is the more standard setting for threshold theorems in fault-tolerant
quantum computation fn (5). In both noise models, we incorporate read-out
noise by taking the final noise channel $\mathcal{D}_{0}$ to act on all
qubits.

|  | IQP
---
circuits
| Random
---
circuits
| Any circuit,
---
almost any input
(uniform noise)
| Any circuit,
---
almost any input
(gate noise)
| Any circuit,
---
any input
(uniform noise)
| Any circuit,
---
any input
(gate noise)
| Expectation
---
values
| poly $n$
---
Ref. Bremner  _et al._ (2017)
| poly $n$
---
Refs. Gao and Duan (2018); Aharonov  _et al._ (2023)
| poly $n$
---
Theorem 1
| quasi-poly $n$
---
Theorem 2
| $\widetilde{\text{QNC}}_{1}$
---
Ref. Aharonov  _et al._ (1996)
| BQP
---
Refs. Shor (1996); Aharonov and Ben-Or (1997); Kitaev (1997); Knill  _et al._
(1998)
| Sampling
---
(∗: with anti-
concentration)
| quasi-poly $n^{*}$
---
Ref. Bremner  _et al._ (2017)
| poly $n^{*}$
---
Ref. Aharonov  _et al._ (2023)
| quasi-poly $n^{*}$
---
Theorem 3a
| quasi-poly $n^{*}$
---
Theorem 3a
| Samp$\widetilde{\text{QNC}}_{1}$
---
Ref. Aharonov  _et al._ (1996)
| SampBQP
---
Refs. Shor (1996); Aharonov and Ben-Or (1997); Kitaev (1997); Knill  _et al._
(1998)
Table 1: Known results on the computational complexity of various classes of
noisy quantum circuits, taking the standard limits
$d,\varepsilon^{-1}=\text{poly}(n)$ and $\gamma^{-1}=\mathcal{O}(1)$. In the
first three columns, expectation values are with respect to observables that
are sums of polynomially many Pauli operators; each runtime increases to
quasi-polynomial otherwise. In the final two columns, entries denote hardness
results arising from quantum error correction Aharonov  _et al._ (1996); Shor
(1996); Aharonov and Ben-Or (1997); Kitaev (1997); Knill  _et al._ (1998). We
use $\widetilde{\text{QNC}}_{1}$ to denote the class of quantum circuits with
depth $d=\mathcal{O}(\log n/\text{poly}\log\log n)$ Aharonov  _et al._ (1996),
which is just below logarithmic. We note that simpler classical simulations
may be obtained for circuits with specific depths or geometric locality, as we
show, for example, in Theorem 3b.

The central framework of our approach is the decomposition of the Heisenberg
time-evolved observable, $O$, in the Pauli basis. Crucially, under uniform
noise, a Pauli operator $P$ with weight $w[P]$ is damped by an amount
$e^{-\gamma w[P]}$, where the weight $w$ is defined as the number of non-
identity elements in the operator. High-weight Pauli operators are thus almost
entirely damped by noise, while low-weight operators are less affected. Since
there are only polynomially many, $\mathcal{O}((3n)^{w}/w!)$, low-weight
operators, this suggests that one might be able to efficiently approximate a
time-evolved observable by only keeping track of such operators. This
intuition has motivated a range of seminal algorithms for classically
simulating noisy quantum circuits by truncating Pauli operators of high weight
Bremner  _et al._ (2017); Gao and Duan (2018); Barak  _et al._ (2020); Gao
_et al._ (2021); Aharonov  _et al._ (2023); Yung and Gao (2017); Fontana  _et
al._ (2023); Shao  _et al._ (2023); White  _et al._ (2018); Ye  _et al._
(2020); Rakovszky  _et al._ (2022); Von Keyserlingk  _et al._ (2022); White
(2023); Yoo  _et al._ (2023). However, whether it is possible to turn this
intuition into a rigorous classical algorithm for general circuits has
remained an essential open question.

There are two challenges. First, although each individual high-weight operator
is strongly damped by noise, there are, in principle, exponentially many such
operators. To address this, existing classical algorithms Gao and Duan (2018);
Barak  _et al._ (2020); Gao  _et al._ (2021); Bouland  _et al._ (2022);
Aharonov  _et al._ (2023); Yung and Gao (2017); Fontana  _et al._ (2023); Shao
_et al._ (2023) utilize a unique property of _random circuits_ in order to
bound the truncation error fn (3). However, this property does not extend to
general circuits. Second, for circuits with gate-based noise, the damping of
each Pauli operator is given by $w_{U_{t}}[P]$, the number of non-identity
elements of $P$ that are acted upon by gates in $U_{t}$111Specifically,
$w_{U_{t}}[P]$ counts the number of qubits that are both in the support of $P$
and acted on by non-identity gates in $U_{t}$.. However, a high-weight
operator might be involved only in a small number of gates in any given
circuit layer. Thus, in combination with the first challenge, any rigorous
approach for bounding the truncation error _must_ keep track of the _history_
of operators across many circuit layers.

In what follows, we will begin by stating our main result (Theorems 1 and 2).
In particular, we provide one classical algorithm for circuits with uniform
noise, which runs in polynomial-time for a large class of observables, and a
second classical algorithm for circuits with gate-based noise, which runs in
quasi-polynomial time. We will then describe our algorithms, with a focus on
delineating the key techniques and insights that allow us to overcome the two
aforementioned challenges.

######  Theorem 1.

_(Classical algorithm for quantum circuits with uniform noise)_ Consider any
noisy quantum circuit $\mathcal{C}$, any observable $O$, and a low-average
ensemble of states $\mathcal{E}=\\{\rho\\}$. Assume the Pauli coefficients of
$O$ and $\rho$ can be efficiently computed. For circuits with uniform noise,
there is a classical algorithm that computes the expectation values
$\tr(\mathcal{C}\\{\rho\\}O)$, in time

$\displaystyle\emph{poly}(n)\cdot(1/\varepsilon)^{\mathcal{O}\left(\frac{\log(1/\gamma)}{\gamma^{2}}\right)},$
if $O$ is a sum of polynomially many Paulis (2) $\displaystyle
n^{\mathcal{O}\left(\frac{\log(1/\gamma)}{\gamma}\right)+\mathcal{O}\left(\frac{\log(1/\varepsilon)}{\gamma
d}\right)}\cdot(1/\varepsilon)^{\mathcal{O}\left(\frac{\log(1/\gamma)}{\gamma^{2}}\right)},$
$\displaystyle\hskip 28.45274pt\text{for any $O$},$ (3)

with root-mean-square error $\varepsilon\cdot\lVert O\rVert_{F}$ over the
ensemble $\mathcal{E}$.

######  Theorem 2.

_(Classical algorithm for quantum circuits with gate-based noise)_ For
circuits with gate-based noise, there is a classical algorithm that runs in
quasi-polynomial time,

$\mathcal{O}\left(d\cdot
n^{\frac{1}{\gamma}\log(\sqrt{d+1}/\varepsilon)-1}\right).$ (4)

for any $O$, with root-mean-square error $\varepsilon\cdot\lVert O\rVert_{F}$
over the ensemble $\mathcal{E}$.

Here, we utilize the normalized Frobenius norm, $\lVert
O\rVert_{F}^{2}=\frac{1}{2^{n}}\text{tr}(O^{\dagger}O)$. Note that the precise
definition of _low-average_ ensembles is provided in Supplementary Section II.
These include any ensemble whose mixture is close to the maximally mixed
state, $(1/|\mathcal{E}|)\sum_{\rho}\rho\approx\mathbbm{1}/2^{n}$, such as the
ensemble of computational basis states, or indeed, any complete basis of
states. Intuitively, our attention to average-case performance excludes error
correction because syndrome qubits will be initialized randomly on average.
Our bounds on the root-mean-square error can be used to upper bound the
probability $\delta$ to have error greater than a threshold
$\tilde{\varepsilon}$, by replacing
$\varepsilon\rightarrow\tilde{\varepsilon}\sqrt{\delta}$ via Markov’s
inequality.

Algorithm 1 Classical algorithm for uniform noise

Input: State $\rho$, circuit $\mathcal{C}$, observable $O$; threshold $\ell$

Output: Approximation of $\tr(\mathcal{C}\\{\rho\\}O)$

1:Enumerate Pauli paths $\vec{P}$ with $\sum_{t}w[P_{t}]\leq\ell$

2:Compute amplitudes $c_{\vec{P}}=\prod_{t}a^{(t)}_{P_{t-1}P_{t}}$

3:Apply noise $c_{\vec{P}}\leftarrow e^{-\gamma\sum_{t}w[P_{t}]}\cdot
c_{\vec{P}}$

4:return $\sum_{\vec{P}}c_{\vec{P}}\tr(\rho P_{d})$

Algorithm 2 Classical algorithm for gate-based noise

Input: State $\rho$, circuit $\mathcal{C}$, observable $O$; threshold $\ell$

Output: Approximation of $\tr(\mathcal{C}\\{\rho\\}O)$

1:Initialize $c_{P}=e^{-\gamma w[P]}\tr(OP)/2^{n}$ for $w[P]\leq\ell$

2:for $t=1$ to $d$ do

3: Update via $c_{Q}\leftarrow e^{-\gamma
w_{U_{t}}[Q]}\sum_{P}a_{PQ}^{(t)}\cdot c_{P}$

4:return $\sum_{P}c_{P}\tr(\rho P)$

###  II.1 Classical algorithm for quantum circuits with uniform noise

Our algorithm for uniform noise (Algorithm 1) estimates the expectation value,
$\tr(\mathcal{C}\\{\rho\\}O)=\text{tr}(\rho\,\mathcal{C}^{\dagger}\\{O\\})$,
by computing an approximation $\tilde{O}$ of the Heisenberg time-evolved
observable $\mathcal{C}^{\dagger}\\{O\\}$. This approximation is given by the
sum of all low-weight _Pauli paths_ that contribute to
$\mathcal{C}^{\dagger}\\{O\\}$. Here, a Pauli path
$\vec{P}=(P_{0},\ldots,P_{d})$ is a sequence of Pauli operators corresponding
to each layer of the circuit [Fig. 1(b)] and the exact time-evolved operator
can immediately be expressed as a sum over Pauli paths,

$\mathcal{C}^{\dagger}\\{O\\}=\sum_{\vec{P}}e^{-\gamma
w[\vec{P}]}\left(\prod_{t=1}^{d}a^{(t)}_{P_{t-1}P_{t}}\right)P_{d},$ (5)

with coefficients given by the transition amplitudes,
$a_{PQ}^{(t)}=\frac{1}{2^{n}}\text{tr}(QU_{t}^{\dagger}PU_{t})$, at each layer
$t$. Each path is damped by a factor $e^{-\gamma w[\vec{P}]}$ due to noise,
where $w[\vec{P}]=\sum_{t}w[P_{t}]$ is the sum of the individual weights at
each circuit layer. Our approximation is given by the sum over all Pauli paths
with weight below a threshold $\ell$,

$\tilde{O}=\sum_{\vec{P}:w[\vec{P}]\leq\ell}e^{-\gamma
w[\vec{P}]}\left(\prod_{t=1}^{d}a^{(t)}_{P_{t-1}P_{t}}\right)P_{d}.$ (6)

The estimated expectation value is $\text{tr}(\rho\tilde{O})$.

We hasten to emphasize that our algorithm is in fact identical to those from
random circuits Gao and Duan (2018); Aharonov  _et al._ (2023). To this end,
our ability to rigorously extend the algorithm to general noisy quantum
circuits owes to substantial improvements in a number of key proof techniques.
In particular, to bound the error in the expectation values, we first prove
the following simple lemma.

######  Lemma 1.

Consider a low-average ensemble $\mathcal{E}=\\{\rho\\}$ and two observables
$O$ and $\tilde{O}$. The root-mean-square difference between the expectation
value of $O$ and $\tilde{O}$ is less than $\lVert O-\tilde{O}\rVert_{F}$.

Thus, if we are able to bound the Frobenius norm of the sum of truncated Pauli
paths, then we can bound the root-mean-square error in our algorithm.

To bound the norm, we group the exponentially many Pauli paths according to
their weight at each circuit layer. This organization is naturally viewed via
a tree structure [Fig. 2(a)]. Each layer $t$ of the tree corresponds to a
layer of the quantum circuit, ordered from $t=d,\ldots,1$. At every layer,
each vertex branches into up to $n$ additional vertices, which correspond to
Pauli paths with weight $w_{t}=1,\ldots,n$ at that layer. In this manner, each
Pauli path $\vec{P}$ is uniquely associated with a particular downward
sequence of vertices, $(w_{d}),(w_{d},w_{d-1}),\ldots,(w_{d},\ldots,w_{0})$,
through the tree.

The key benefits of the Pauli tree are that: (i) the paths associated with
each vertex are damped by at least
$e^{-\gamma\sum_{t^{\prime}=t}^{d}w_{t^{\prime}}}$ due to noise, and (ii) the
tree organization naturally enables us to bound the norm of sums of Pauli
paths, by using the orthogonality of Pauli operators at each circuit layer. We
now outline how these properties enable a tight bound on the error of
Algorithm 1. Let $\delta O(w,t)$ denote the sum of all Pauli paths from layer
$0$ to $t$ with weight above $w$. We are interested in the Frobenius norm of
$\delta O(\ell,d)=\mathcal{C}^{\dagger}\\{O\\}-\tilde{O}$, which bounds the
root-mean-square error of Algorithm 1 via Lemma 1. To analyze the Frobenius
norm, we leverage properties (i) and (ii) above to decompose it as a sum of
contributions from each weight $w_{d}$ at the final circuit layer,
$\lVert\delta
O(\ell,d)\rVert_{F}^{2}=\sum_{w_{d}}\lVert\mathcal{P}_{w_{d}}\\{\delta
O(\ell,d)\\}\rVert_{F}^{2}$, where $\mathcal{P}_{w_{d}}$ projects onto Pauli
operators of weight $w_{d}$. We can associate each term in the sum with a
vertex, $(w_{d})$, in the top layer of the Pauli tree. We can then bound the
contribution of each vertex as $\lVert\mathcal{P}_{w_{d}}\\{\delta
O(\ell,d)\\}\rVert_{F}^{2}\leq e^{-2\gamma w_{d}}\lVert\delta O(\ell-
w_{d},d-1)\rVert_{F}^{2}$, since any Pauli path with weight $w_{d}$ at the
final layer, and total weight above $\ell$, must have total weight above
$\ell-w_{d}$ on the preceding layers (see Supplementary Section III for
details). Combined with the first equality, we see that the norm of high-
weight Pauli paths at layer $d$ is bounded by a sum of analogous norms at
layer $d-1$.

To complete our proof, we recursively apply this bound down each layer of the
Pauli tree. That is, we bound the contribution of each top layer vertex,
$(w_{d})$, as a sum of contributions of vertices at the following layer,
$(w_{d},w_{d-1})$. Each such contribution arises from Pauli paths with weight
above $\ell-w_{d}-w_{d-1}$ on layers up to $d-2$, and incurs an associated
damping, $e^{-2\gamma(w_{d}+w_{d-1})}$. We then bound these contributions in
terms of vertices at the next layer, $(w_{d},w_{d-1},w_{d-2})$, and so on. We
halt each sequence of recursions once the summed weight,
$\sum_{t^{\prime}=t}^{d}w_{t^{\prime}}$, surpasses $\ell-t$; from here, one
can directly bound the remaining contribution by $e^{-2\gamma(\ell+1)}\lVert
O\rVert_{F}^{2}$, since every Pauli path from layer $0$ to $t-1$ has weight at
least $t$ fn (1). In effect, this recursive process groups the truncated Pauli
paths according to their earliest sub-sequence of weights that sum to above
$\ell-t$. Each grouping can be viewed as a single collective truncation by the
algorithm [Fig. 2(a)]. The total error of the algorithm is determined by the
number of such truncations, which a simple counting argument shows is
${\ell\choose d}$. This leads to a total error ${\ell\choose
d}e^{-2\gamma(\ell+1)}\lVert O\rVert_{F}^{2}$. We refer to Supplementary
Section III for full details.

From this error bound, we determine the runtime of Algorithm 1 by setting
$\ell\approx\gamma^{-1}d+\gamma^{-1}\log(1/\varepsilon)$ to achieve a desired
error $\varepsilon$. For circuits with uniform noise, the maximum non-trivial
depth is $d=\mathcal{O}(\gamma^{-1}\log(1/\varepsilon))$, since after this
depth, expectation values become $\varepsilon$-close to zero and the circuit
can be trivially simulated fn (7). The runtime of our classical algorithm is
determined by the number of Pauli paths with weight below $\ell$. This is
upper bounded by $n^{\ell/d}\cdot 2^{\mathcal{O}(\ell)}$ for any $O$ Aharonov
_et al._ (2023), and $m\cdot 2^{\mathcal{O}(\ell)}$ when $O$ is a sum of $m$
Pauli operators (see Supplementary Section III). Plugging in the above values
of $\ell$ and $d$ yields Theorem 1.

###  II.2 Classical algorithm for quantum circuits with gate-based noise

Although Algorithm 1 is quite efficient for quantum circuits with uniform
noise, where the depth $d$ is at most logarithmic, this efficiency does not
extend to circuits with gate-based noise, where the depth $d$ may be large. In
such circuits, the runtime of Algorithm 1 diverges exponentially in $d$ owing
to the ${\ell\choose d}$ truncations.

Figure 2: (a) The Pauli tree framework used to prove Theorem 1, which groups
Pauli paths according to their weight $w_{t}$ at each circuit layer $t$. Our
algorithm truncates paths with a summed weight above $\ell$. We group these
truncations into ${\ell\choose d}$ individual truncations (red scissors),
which enables a tight bound on the algorithm’s error. In the example shown,
the branchings at each node correspond to weights $w=1,\ldots,5$ and we set
$\ell=6,d=2$. (b) To prove Theorem 2, we analyze the flow of Pauli operators
from one weight to another under circuit gates. Here, each bubble depicts the
set of Pauli operators of a given weight, and arrows indicate flow from one
weight to another. We show that this flow is lossy in the presence of gate-
based noise, in the sense that a decrease $-J$ in support at weight $w$ can
increase the support at weight $w+1$ by at most $e^{-2\gamma}J$. This leads to
our bound on the cumulative operator weight distribution in Lemma 2.

To address this, our algorithm for gate-based noise (Algorithm 2) performs
only a single truncation at each circuit layer, of all Pauli operators with
weight greater than $\ell$. In particular, at each layer $t$ we store an
approximation of the time-evolved operator within the subspace of low-weight
Pauli operators,

$\tilde{O}^{(t)}=\sum_{P:w[P]\leq\ell}\tilde{c}_{P}^{(t)}P.$ (7)

The coefficients are updated from layer to layer via standard Heisenberg time-
evolution,

$\tilde{c}_{Q}^{(t)}=e^{-\gamma
w_{U_{t}}[Q]}\sum_{P:w[P]\leq\ell}a_{PQ}^{(t)}\,\tilde{c}_{P}^{(t-1)}.$ (8)

At the final circuit layer, we compute the expectation value
$\text{tr}(\rho\tilde{O}^{(d)})$.

By performing only $d+1$ truncations in total, Algorithm 2 avoids the
exponential blow-up of Algorithm 1 at large depths. In particular, if we
denote the truncated operators at layer $t$ as $\delta
O^{(t)}\equiv\mathcal{P}_{>\ell}\\{\mathcal{D}_{t}\\{U_{t}^{\dagger}\tilde{O}^{(t-1)}U_{t}\\}\\}$,
where $\mathcal{P}_{>\ell}=\sum_{w=\ell+1}^{n}\mathcal{P}_{w}$, then we
immediately have $\lVert\delta
O\rVert_{F}^{2}\leq(d+1)\sum_{t=0}^{d}\lVert\delta O^{(t)}\rVert_{F}^{2}$ by
the Cauchy-Schwarz inequality. The trade-off is a moderate increase in runtime
compared to Algorithm 1 at the same value of $\ell$. In particular, Algorithm
2 performs $d$ updates on $\mathcal{O}(n^{\ell})$ low-weight Pauli
coefficients, and thus has runtime $\mathcal{O}(dn^{\ell})$; see Supplementary
Section IV for full details.

The central difficulty in proving Theorem 2 is to bound the truncation norms,
$\lVert\delta O^{(t)}\rVert_{F}$, within the gate-based noise model. This
would be straightforward within the uniform noise model, since a single
application of uniform depolarizing noise damps the norm of any operator with
weight above $\ell$ by at least $e^{-\gamma(\ell+1)}$. However, as
aforementioned, it is not clear whether such a bound applies to the gate-based
noise model, where the effect of noise can accumulate gradually over many
circuit layers.

To show that the bound indeed extends to circuits with gate-based noise, our
core idea is to track the _flow_ of operator norm from one weight to another
under each circuit gate [Fig. 2(b)]. Intuitively, each two-qubit gate can
transfer operator norm from a weight $w$ to adjacent weights $w\pm 1$. Thus,
for a component of the operator to reach a high weight, it must participate in
a high number of circuit gates, and thereby accrue a large damping due to
noise. Despite its simplicity, formalizing this intuition can be remarkably
subtle, due to processes wherein an operator component grows to high weight,
then shrinks back to low weight, and then grows to high weight again. Our
focus on the flow of the operator norm allows us to simultaneously capture
damping during the growth in operator weight, while avoiding over-counting due
to shrinking and re-growth processes.

In more detail, to quantify the norm of a time-evolved operator $O^{(g)}$ at
weight $w$, we leverage an object of recent interest in many-body physics: the
_operator weight distribution_ Roberts  _et al._ (2018); Schuster and Yao
(2023),

$P^{(g)}(w)=\frac{1}{2^{n}}\tr\big(O^{(g)}\cdot\mathcal{P}_{w}\\{O^{(g)}\\}\big{missing}).$
(9)

Here, we track the evolution through each circuit gate $g$ instead of each
circuit layer $t$. In keeping with our intuition, we show that the weight
distribution changes in a “local” manner when any unitary two-qubit gate $g$
is applied,

$P^{(g)}(w)=P^{(g-1)}(w)+J^{(g)}(w)-J^{(g)}(w+1),$ (10)

where $J^{(g)}(w)$ measures the flow in operator norm from weight $w-1$ to $w$
under $g$. The crucial insight of our proof is to show that this flow becomes
_lossy_ for quantum circuits with gate-based noise, in the sense that

$P^{(g)}(w)\leq P^{(g-1)}(w)+\\{1,e^{-2\gamma}\\}\cdot
J^{(g)}(w)-\\{1,e^{-2\gamma}\\}\cdot J^{(g)}(w+1),\\\ $ (11)

where the bound holds for any choices of the constants $1$ or $e^{-2\gamma}$
in each of the terms. The strongest bound is obtained by taking $e^{-2\gamma}$
when the term is positive, and $1$ when negative. In the former case, the
bound shows that increases in operator norm due to flows inward to weight $w$
are damped by $e^{-2\gamma}$ due to noise; in the latter case, decreases in
the norm due to outward flows are not damped [Fig. 2(b)].

To bound the truncation error, we apply Eq. (11) for every circuit gate $g$
and sum over weights $w>\ell$. The currents between high weights cancel, and
we find that the total norm above weight $\ell$ is less than the _net current_
from $\ell$ to $\ell+1$, $\sum_{g}J^{(g)}(\ell)$, damped by $e^{-2\gamma}$. By
bounding the norm in terms of the net current, we naturally avoid subtleties
due to shrinking and re-growth processes. Furthermore, the net current from
weight $\ell$ to $\ell+1$ is necessarily bounded by the maximum norm at weight
$\ell$. This is, by a similar inequality, less than the net current from
$\ell-1$ to $\ell$ damped $e^{-2\gamma}$. Iterating $\ell$ times, we find that
the total norm above weight $\ell$ is less than $e^{-2\gamma(\ell+1)}\lVert
O\rVert_{F}^{2}$ for any circuit with gate-based noise (see Supplementary
Section IV for full details).

######  Lemma 2.

_(Upper bound on weight distributions in noisy quantum circuits)_ Consider the
time-evolution $O^{(g)}$ of an observable $O$ in any quantum circuit with
gate-based noise. The cumulative weight distribution is less than

$\sum_{w^{\prime}=w+1}^{\infty}P^{(g)}(w^{\prime})\leq
e^{-2\gamma(w+1)}\cdot\lVert O\rVert_{F}^{2}$ (12)

for all $\gamma,w,t$. This also holds if we replace $O^{(g)}$ with our
classical approximation $\tilde{O}^{(g)}$.

Applying the lemma to Algorithm 2, we find that the total truncation error is
less than $(d+1)e^{-2\gamma(\ell+1)}\lVert O\rVert_{F}^{2}$. Setting
$\ell\approx\gamma^{-1}\,\text{log}(\sqrt{d}/\varepsilon)$ to ensure a small
root-mean-square error gives Theorem 2. We remark that our proof of Lemma 2,
as outlined above, introduces substantially new techniques compared to any
previous Pauli truncation algorithm that we are aware of.

###  II.3 Classical algorithms for sampling from noisy quantum circuits

Our classical algorithms can also be leveraged to sample from noisy quantum
circuits. In sampling, we are interested in reproducing the statistics when
the final state of the circuit is measured in the computational basis. From
Born’s rule, each measurement produces an $n$-bit string $z$ with probability
$p_{\rho,\mathcal{C}}(z)=\bra{z}\mathcal{C}\\{\rho\\}\ket{z}$. In general,
sampling is a strictly harder task than computing expectation values, since
the distribution $p_{\rho,\mathcal{C}}(z)$ contains information about
exponentially many expectation values in the computational basis.

We provide three algorithms for sampling from noisy quantum circuits. The
first two are direct extensions of Theorems 1 and 2, and apply to any circuit
on almost any input state. Similar to previous works Bremner  _et al._ (2017);
Aharonov  _et al._ (2023), we require one additional assumption: that the
output distribution of the circuit _anti-concentrates_ , in the sense that
$(1/|\mathcal{E}|)\sum_{\rho}\sum_{z}p_{\rho,\tilde{\mathcal{C}}}(z)^{2}=\mathcal{O}(2^{-n})$
for the ensemble $\mathcal{E}=\\{\rho\\}$. Here, $\tilde{\mathcal{C}}$ denotes
the circuit $\mathcal{C}$ with the read-out noise channel omitted. Anti-
concentration guarantees that most expectation values in the computational
basis are close to zero. In the presence of read-out noise, this enables one
to sample from $p_{\rho,\mathcal{C}}(z)$ by computing only a small number of
low-weight expectation values Bremner  _et al._ (2017), which we show can be
done efficiently using our Algorithms 1 and 2 (see Supplementary Section V for
details).

######  Theorem 3a.

_(Sampling from noisy quantum circuits)_ Consider a noisy quantum circuit
$\mathcal{C}$ and a low-average ensemble $\mathcal{E}=\\{\rho\\}$ whose Pauli
coefficients can be efficiently computed. Assume the output distribution anti-
concentrates,
$(1/|\mathcal{E}|)\sum_{\rho}\sum_{z}p_{\rho,\tilde{\mathcal{C}}}(z)^{2}=\mathcal{O}(2^{-n})$.
Then for either uniform or gate-based noise, there is a classical algorithm to
sample from $p_{\rho,\mathcal{C}}(z)$ within root-mean-square total
variational distance $\varepsilon$ in quasi-polynomial time.

Figure 3: Schematic of our results’ implications for quantum error mitigation.
For concreteness, we depict a specific error mitigation strategy, zero noise
extrapolation, in which one measures an expectation value $\langle O\rangle$
for several different noise rates (orange lines), and performs an
extrapolation (green arrow and dashed line) to estimate the ideal expectation
value (black line). (a) If error mitigation succeeds in recovering the ideal
expectation value, then the expectation value must be dominated by low-weight
Pauli operators (green). Thus, our classical algorithm can also compute the
ideal expectation value. (b) On the other hand, if the ideal expectation value
is hard to compute classically, then it must contain contributions from high-
weight Pauli operators (red). Error mitigation cannot capture these
contributions, since they are exponentially suppressed by noise. Thus, the
extrapolated expectation value necessarily differs from the ideal value (red
arrows).

Our third sampling algorithm specializes to quantum circuits with low depth.
In such circuits, one can exactly compute low-weight expectation values by
restricting to the light-cone of the observable of interest. Using this
property, we show that one can classically sample from any low-depth circuit
with _read-out_ noise, as long as the output distribution of the circuit anti-
concentrates. This holds even when the circuit gates themselves are noiseless.

######  Theorem 3b.

_(Sampling from low-depth quantum circuits with read-out noise)_ Consider a
quantum circuit $\mathcal{C}$ with depolarizing read-out noise, and a state
$\rho$ whose Pauli coefficients can be efficiently computed. Assume the output
distribution anti-concentrates,
$\sum_{z}p_{\rho,\tilde{\mathcal{C}}}(z)^{2}=\mathcal{O}(2^{-n})$. If the
circuit has depth $d=\mathcal{O}(\log n)$ and is geometrically local, or has
depth $d=\mathcal{O}(\log\log n)$ more generally, then there is classical
algorithm to sample from $p_{\rho,\mathcal{C}}(z)$ within total variational
distance $\varepsilon$ in quasi-polynomial time.

Quantum advantages for sampling from low-depth circuits are highly sought,
since low-depth circuits are generally less susceptible to experimental noise.
Nonetheless, our result shows that in many cases, even a small amount of read-
out noise can preclude any such advantage fn (8).

##  III Applications and Implications

Let us now consider the implications of our algorithms. We summarize a few of
the most prominent ones below, and direct the interested reader to the
Supplementary Information for details and additional results.

Failure of quantum error mitigation—Error mitigation refers to a general class
of strategies for estimating the output of an ideal quantum circuit via
experiments on noisy quantum circuits Cai  _et al._ (2023); Li and Benjamin
(2017); Temme  _et al._ (2017); Bonet-Monroig  _et al._ (2018); McArdle  _et
al._ (2019); Rubin  _et al._ (2018); Czarnik  _et al._ (2021); Huggins  _et
al._ (2021); O’Brien  _et al._ (2021). Although error mitigation has
undoubtedly been useful for moderate-sized circuits, the number of
experimental shots that it requires are known to grow exponentially in the
number of qubits in certain cases Quek  _et al._ (2022); Takagi  _et al._
(2022, 2023). At the same time, this worst-case performance clearly does not
extend to all circuits; for instance, a circuit of entirely single-qubit gates
can be error mitigated with resources independent of the system size. This
raises an essential open question: Can error mitigation scale efficiently for
any non-trivial quantum circuit? Unfortunately, within the settings we
consider, our results imply a strictly negative answer. The reason is simple.
If one can recover an ideal expectation value from a series of noisy quantum
experiments, then one can also compute the ideal expectation value
classically, by substituting our algorithms’ output for the experiments’
results. Thus, error mitigation can only scale efficiently for circuits that
have efficient classical simulations. We state this formally and provide a
detailed proof in Supplementary Section VIII.

Quantum advantage beyond sampling—While the focus of our work has been on
noisy quantum circuits, our results also have broader implications in the
search for near-term experiments that exhibit a quantum advantage. Namely, by
inverting our Theorem 2, we show that any quantum circuit that is
exponentially hard to simulate classically _must fail_ in the presence of even
a macroscopically small noise rate, $\gamma=\tilde{\Omega}(1/n)$
(Supplementary Section IX). This criteria can function as a simple and
rigorous “test” for whether a given quantum circuit can feature an advantage
over classical computation. Thus far, demonstrations of quantum advantage have
been restricted to sampling experiments Arute  _et al._ (2019); Wu  _et al._
(2021), which are by their nature almost maximally sensitive to noise Boixo
_et al._ (2018); Morvan  _et al._ (2023). When moving beyond sampling, it can
be difficult to design experiments whose expectation values are
macroscopically sensitive to noise in a non-trivial manner. This is
highlighted by recent experiments on IBM’s quantum processor Kim  _et al._
(2023), which, despite involving many qubits and high gate fidelities, were
rapidly simulated classically by follow-up works Tindall  _et al._ (2023);
Begušić and Chan (2023); Kechedzhi  _et al._ (2023); Anand  _et al._ (2023);
Rudolph  _et al._ (2023); Begušić and Chan (2023). In light of our work, this
can be understood as a consequence of the experiments’ insensitivity to noise
fn (4).

Non-unital noise models—We can also ask how our results extend to quantum
circuits with _non-unital noise_ , such as spontaneous emission Ben-Or  _et
al._ (2013); Fefferman  _et al._ (2023). Unfortunately, an immediate extension
of Theorems 1, 2 to non-unital noise models is not possible, since for general
quantum circuits with non-unital noise one can perform fault-tolerant
computation Ben-Or  _et al._ (2013). Nevertheless, we find that our classical
algorithms can be used to prove a sharp counterpoint to this result: quantum
circuits with non-unital noise _can_ be classically simulated, provided that
the noise is _unstructured_ with respect to the gates of the circuit
(Supplementary Section VII). Our result represents only the second rigorous
algorithm for any class of quantum circuits with non-unital noise, and
drastically improves upon previous work Mele  _et al._ (2024) in both runtime
and the range of circuits to which it applies.

Noisy quantum circuits on highly mixed state—Finally, we can extend our
results to apply to any, fixed input state within one physically relevant
scenario: when the state is highly mixed (Supplementary Section X). This
follows directly from Theorems 1, 2 because the ensemble composed of a single
highly mixed input state is low-average. Experiments with highly mixed input
states are commonplace in several quantum technologies, including nuclear
magnetic resonance spectroscopy Jones (2010) and solid-state quantum
simulators Doherty  _et al._ (2013); Zu  _et al._ (2021). Formally, these are
captured by the so-called DQC1 model of computation Knill and Laflamme (1998).
Our results show that any noisy DQC1 computation can be classically simulated
in polynomial time.

##  IV Outlook

Our results provide the most extensive evidence yet, that noisy quantum
circuits without error correction can be efficiently classically simulated. In
the long-term, this emphasizes the necessity of quantum error correction for
achieving a scalable quantum advantage over classical computation. For
experiments without error correction, our results demonstrate the necessity of
improving the noise rate proportional to the number of qubits. Moreover, even
at sufficiently low noise rates, our results provide a rigorous test for
whether a given circuit can yield a quantum advantage, by establishing,
perhaps counterintuitively, that such circuits must be highly sensitive to
noise.

Our work opens the door to a number of intriguing directions. First, is it
possible to devise analogous classical algorithms for continuous-time dynamics
instead of quantum circuits? Second, to what extent do our results carry over
to more general errors, such as dephasing or thermal noise? Finally, can
insights from our proof techniques be used to improve numerical algorithms for
classically simulating quantum systems? In particular, we speculate that our
approach may provide a fruitful starting point for simulating highly-connected
circuit architectures, where tensor network methods typically struggle.

_Acknowledgements_ —We are grateful to Matthias C. Caro, Andreas Elben, Bill
Fefferman, Soumik Ghosh, Greg Kahanamoku-Meyer, John Preskill, Dominik Wild,
and Mike Zalatel for valuable discussions and insights. T.S. acknowledges
support from the Walter Burke Institute for Theoretical Physics at Caltech.
C.Y. is supported by the Department of Energy under Quantum Pathfinder Grant
DE-SC0024324. X.G. acknowledges support from NSF PFC grant No. PHYS 2317149
and start-up grants from CU Boulder. N.Y.Y acknowledges support from the NSF
via the QLCI program (grant number OMA-2016245) and the STAQ II Program. The
Institute for Quantum Information and Matter, with which TS is affiliated, is
an NSF Physics Frontiers Center.

## References

  * Feynman (2018) R. P. Feynman, in  _Feynman and computation_ (CRC Press, 2018) pp. 133–153.
  * Shor (1994) P. W. Shor, in  _Proceedings 35th annual symposium on foundations of computer science_ (Ieee, 1994) pp. 124–134.
  * Bauer  _et al._ (2020) B. Bauer, S. Bravyi, M. Motta, and G. K.-L. Chan, Chemical Reviews 120, 12685 (2020).
  * Dalzell  _et al._ (2023) A. M. Dalzell, S. McArdle, M. Berta, P. Bienias, C.-F. Chen, A. Gilyén, C. T. Hann, M. J. Kastoryano, E. T. Khabiboulline, A. Kubica, _et al._ , arXiv preprint arXiv:2310.03011 (2023).
  * Aharonov and Ben-Or (1996) D. Aharonov and M. Ben-Or, in  _Proceedings of 37th Conference on Foundations of Computer Science_ (IEEE, 1996) pp. 46–55.
  * Aharonov (2000) D. Aharonov, Physical Review A 62, 062311 (2000).
  * Harrow and Nielsen (2003) A. W. Harrow and M. A. Nielsen, Physical Review A 68, 012308 (2003).
  * Kempe  _et al._ (2008) J. Kempe, O. Regev, F. Unger, and R. De Wolf, in  _International Colloquium on Automata, Languages, and Programming_ (Springer, 2008) pp. 845–856.
  * Shor (1996) P. W. Shor, in  _Proceedings of 37th conference on foundations of computer science_ (IEEE, 1996) pp. 56–65.
  * Aharonov and Ben-Or (1997) D. Aharonov and M. Ben-Or, in  _Proceedings of the twenty-ninth annual ACM symposium on Theory of computing_ (1997) pp. 176–188.
  * Kitaev (1997) A. Y. Kitaev, Russian Mathematical Surveys 52, 1191 (1997).
  * Knill  _et al._ (1998) E. Knill, R. Laflamme, and W. H. Zurek, Science 279, 342 (1998).
  * Aharonov  _et al._ (1996) D. Aharonov, M. Ben-Or, R. Impagliazzo, and N. Nisan, arXiv preprint quant-ph/9611028 (1996).
  * Ben-Or  _et al._ (2013) M. Ben-Or, D. Gottesman, and A. Hassidim, arXiv preprint arXiv:1301.1995 (2013).
  * Dalzell  _et al._ (2021) A. M. Dalzell, N. Hunter-Jones, and F. G. Brandão, arXiv preprint arXiv:2111.14907 (2021).
  * Deshpande  _et al._ (2022) A. Deshpande, P. Niroula, O. Shtanko, A. V. Gorshkov, B. Fefferman, and M. J. Gullans, PRX Quantum 3, 040329 (2022).
  * Chen  _et al._ (2022) S. Chen, J. Cotler, H.-Y. Huang, and J. Li, arXiv preprint arXiv:2210.07234 (2022).
  * Huang  _et al._ (2020) C. Huang, F. Zhang, M. Newman, J. Cai, X. Gao, Z. Tian, J. Wu, H. Xu, H. Yu, B. Yuan, _et al._ , arXiv preprint arXiv:2005.06787 (2020).
  * Liu  _et al._ (2021) Y. Liu, X. Liu, F. Li, H. Fu, Y. Yang, J. Song, P. Zhao, Z. Wang, D. Peng, H. Chen, _et al._ , in  _Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis_ (2021) pp. 1–12.
  * Pan and Zhang (2021) F. Pan and P. Zhang, arXiv preprint arXiv:2103.03074 (2021).
  * Villalonga  _et al._ (2020) B. Villalonga, D. Lyakh, S. Boixo, H. Neven, T. S. Humble, R. Biswas, E. G. Rieffel, A. Ho, and S. Mandrà, Quantum Science and Technology 5, 034003 (2020).
  * Cheng  _et al._ (2021) S. Cheng, C. Cao, C. Zhang, Y. Liu, S.-Y. Hou, P. Xu, and B. Zeng, Physical Review Research 3, 023005 (2021).
  * Noh  _et al._ (2020) K. Noh, L. Jiang, and B. Fefferman, Quantum 4, 318 (2020).
  * White  _et al._ (2018) C. D. White, M. Zaletel, R. S. Mong, and G. Refael, Physical Review B 97, 035127 (2018).
  * Ye  _et al._ (2020) B. Ye, F. Machado, C. D. White, R. S. Mong, and N. Y. Yao, Physical Review Letters 125, 030601 (2020).
  * Rakovszky  _et al._ (2022) T. Rakovszky, C. von Keyserlingk, and F. Pollmann, Physical Review B 105, 075131 (2022).
  * Von Keyserlingk  _et al._ (2022) C. Von Keyserlingk, F. Pollmann, and T. Rakovszky, Physical Review B 105, 245101 (2022).
  * White (2023) C. D. White, Physical Review B 107, 094311 (2023).
  * Yoo  _et al._ (2023) Y. Yoo, C. D. White, and B. Swingle, Physical Review B 107, 115118 (2023).
  * Vovk and Pichler (2022) T. Vovk and H. Pichler, Physical Review Letters 128, 243601 (2022).
  * Chen  _et al._ (2023) Z. Chen, Y. Bao, and S. Choi, arXiv preprint arXiv:2306.17161 (2023).
  * Cheng and Ippoliti (2023) Z. Cheng and M. Ippoliti, arXiv preprint arXiv:2306.16455 (2023).
  * Bremner  _et al._ (2017) M. J. Bremner, A. Montanaro, and D. J. Shepherd, Quantum 1, 8 (2017).
  * Rajakumar  _et al._ (2024) J. Rajakumar, J. D. Watson, and Y.-K. Liu, arXiv preprint arXiv:2403.14607 (2024).
  * Gao and Duan (2018) X. Gao and L. Duan, arXiv preprint arXiv:1810.03176 (2018).
  * Barak  _et al._ (2020) B. Barak, C.-N. Chou, and X. Gao, arXiv preprint arXiv:2005.02421 (2020).
  * Gao  _et al._ (2021) X. Gao, M. Kalinowski, C.-N. Chou, M. D. Lukin, B. Barak, and S. Choi, arXiv preprint arXiv:2112.01657 (2021).
  * Aharonov  _et al._ (2023) D. Aharonov, X. Gao, Z. Landau, Y. Liu, and U. Vazirani, in  _Proceedings of the 55th Annual ACM Symposium on Theory of Computing_ (2023) pp. 945–957.
  * Yung and Gao (2017) M.-H. Yung and X. Gao, arXiv preprint arXiv:1706.08913 (2017).
  * Fontana  _et al._ (2023) E. Fontana, M. S. Rudolph, R. Duncan, I. Rungger, and C. Cîrstoiu, arXiv preprint arXiv:2306.05400 (2023).
  * Shao  _et al._ (2023) Y. Shao, F. Wei, S. Cheng, and Z. Liu, arXiv preprint arXiv:2306.05804 (2023).
  * Bouland  _et al._ (2022) A. Bouland, B. Fefferman, Z. Landau, and Y. Liu, in  _2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)_ (IEEE, 2022) pp. 1308–1317.
  * Mele  _et al._ (2024) A. A. Mele, A. Angrisani, S. Ghosh, S. Khatri, J. Eisert, D. S. França, and Y. Quek, arXiv preprint arXiv:2403.13927 (2024).
  * Movassagh and Schenker (2021) R. Movassagh and J. Schenker, Physical Review X 11, 041001 (2021).
  * Fujii (2016) K. Fujii, arXiv preprint arXiv:1610.03632 (2016).
  * Kalai and Kindler (2014) G. Kalai and G. Kindler, arXiv preprint arXiv:1409.3093 (2014).
  * García-Patrón  _et al._ (2019) R. García-Patrón, J. J. Renema, and V. Shchesnovich, Quantum 3, 169 (2019).
  * Qi  _et al._ (2020) H. Qi, D. J. Brod, N. Quesada, and R. García-Patrón, Physical review letters 124, 100502 (2020).
  * Oh  _et al._ (2023a) C. Oh, L. Jiang, and B. Fefferman, arXiv preprint arXiv:2301.11532 (2023a).
  * Oh  _et al._ (2023b) C. Oh, M. Liu, Y. Alexeev, B. Fefferman, and L. Jiang, arXiv preprint arXiv:2306.03709 (2023b).
  * Hangleiter and Gullans (2023) D. Hangleiter and M. J. Gullans, arXiv preprint arXiv:2306.00083 (2023).
  * Dalzell  _et al._ (2024) A. M. Dalzell, N. Hunter-Jones, and F. G. Brandão, Communications in Mathematical Physics 405, 78 (2024).
  * Paletta  _et al._ (2024) L. Paletta, A. Leverrier, A. Sarlette, M. Mirrahimi, and C. Vuillot, Quantum 8, 1337 (2024).
  * Temme  _et al._ (2017) K. Temme, S. Bravyi, and J. M. Gambetta, Physical review letters 119, 180509 (2017).
  * Li and Benjamin (2017) Y. Li and S. C. Benjamin, Physical Review X 7, 021050 (2017).
  * Cai  _et al._ (2023) Z. Cai, R. Babbush, S. C. Benjamin, S. Endo, W. J. Huggins, Y. Li, J. R. McClean, and T. E. O’Brien, Reviews of Modern Physics 95, 045005 (2023).
  * Quek  _et al._ (2022) Y. Quek, D. S. França, S. Khatri, J. J. Meyer, and J. Eisert, arXiv preprint arXiv:2210.11505 (2022).
  * Takagi  _et al._ (2022) R. Takagi, S. Endo, S. Minagawa, and M. Gu, npj Quantum Information 8, 114 (2022).
  * Takagi  _et al._ (2023) R. Takagi, H. Tajima, and M. Gu, Physical Review Letters 131, 210602 (2023).
  * Fefferman  _et al._ (2023) B. Fefferman, S. Ghosh, M. Gullans, K. Kuroiwa, and K. Sharma, arXiv preprint arXiv:2306.16659 (2023).
  * fn (2) As a consequence, our algorithms for uniform noise can be thought of as working explicitly in the regime $d=\mathcal{O}(\gamma^{-1}\log(n/\varepsilon))$. After this depth, one can approximate any expectation value with its value in the maximally mixed state Aharonov  _et al._ (1996) .
  * fn (5) In particular, threshold theorems typically assume two ingredients Shor (1996); Aharonov and Ben-Or (1997); Kitaev (1997); Knill  _et al._ (1998): mid-circuit measurement and feedforward operations, and the ability to insert “fresh qubits” unaffected by idle errors. In effect, both noise models allow mid-circuit measurement and feedforward operations, since one can implement the feedforward operations via controlled quantum gates. (For a fixed input state, this can be made fault-tolerant by encoding the state of the “measured” qubit in a classical error correcting code at the layer at which it is “measured”.) Crucially however, the gate-based noise model allows the insertion of fresh qubits, while the uniform noise model does not .
  * fn (3) Namely, previous results on random circuits require that different Pauli operators at a given circuit layer do not, on average, interfere coherently at a later circuit layer (see Ref. Aharonov  _et al._ (2023), where this is referred to as “orthogonality”). This requirement is satisfied in random circuits, where averaged properties of operator time-evolution are governed by an incoherent classical Markov process, but not more generally .
  * fn (1) At this halting step, we also group together all weights above the threshold in order to achieve a tighter bound on the error. See Supplementary Section III for full details .
  * fn (7) We note that the maximum non-trivial depth for quantum circuits with random input states, $d=\mathcal{O}(\gamma^{-1}\log(1/\varepsilon))$, is slightly shorter than the maximum depth for quantum circuits with a fixed input state, $d=\mathcal{O}(\gamma^{-1}\log(n/\varepsilon))$ Aharonov  _et al._ (1996). See Supplementary Section III for further details .
  * Roberts  _et al._ (2018) D. A. Roberts, D. Stanford, and A. Streicher, Journal of High Energy Physics 2018, 1 (2018).
  * Schuster and Yao (2023) T. Schuster and N. Y. Yao, Physical Review Letters 131, 160402 (2023).
  * fn (8) To suppress the effect of read-out noise, one can consider implementing classical error correction prior to measurement (e.g. via a repetition code on each qubit). In this case, the output distribution does not anti-concentrate and so our theorem does not apply .
  * Bonet-Monroig  _et al._ (2018) X. Bonet-Monroig, R. Sagastizabal, M. Singh, and T. O’Brien, Physical Review A 98, 062339 (2018).
  * McArdle  _et al._ (2019) S. McArdle, X. Yuan, and S. Benjamin, Physical review letters 122, 180501 (2019).
  * Rubin  _et al._ (2018) N. C. Rubin, R. Babbush, and J. McClean, New Journal of Physics 20, 053020 (2018).
  * Czarnik  _et al._ (2021) P. Czarnik, A. Arrasmith, P. J. Coles, and L. Cincio, Quantum 5, 592 (2021).
  * Huggins  _et al._ (2021) W. J. Huggins, S. McArdle, T. E. O’Brien, J. Lee, N. C. Rubin, S. Boixo, K. B. Whaley, R. Babbush, and J. R. McClean, Physical Review X 11, 041036 (2021).
  * O’Brien  _et al._ (2021) T. E. O’Brien, S. Polla, N. C. Rubin, W. J. Huggins, S. McArdle, S. Boixo, J. R. McClean, and R. Babbush, PRX Quantum 2, 020317 (2021).
  * Arute  _et al._ (2019) F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. Brandao, D. A. Buell, _et al._ , Nature 574, 505 (2019).
  * Wu  _et al._ (2021) Y. Wu, W.-S. Bao, S. Cao, F. Chen, M.-C. Chen, X. Chen, T.-H. Chung, H. Deng, Y. Du, D. Fan, _et al._ , Physical review letters 127, 180501 (2021).
  * 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, Nature Physics 14, 595 (2018).
  * Morvan  _et al._ (2023) A. Morvan, B. Villalonga, X. Mi, S. Mandra, A. Bengtsson, P. Klimov, Z. Chen, S. Hong, C. Erickson, I. Drozdov, _et al._ , arXiv preprint arXiv:2304.11119 (2023).
  * 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, _et al._ , Nature 618, 500 (2023).
  * Tindall  _et al._ (2023) J. Tindall, M. Fishman, M. Stoudenmire, and D. Sels, arXiv preprint arXiv:2306.14887 (2023).
  * Begušić and Chan (2023) T. Begušić and G. K. Chan, arXiv preprint arXiv:2306.16372 (2023).
  * Kechedzhi  _et al._ (2023) K. Kechedzhi, S. Isakov, S. Mandrà, B. Villalonga, X. Mi, S. Boixo, and V. Smelyanskiy, arXiv preprint arXiv:2306.15970 (2023).
  * Anand  _et al._ (2023) S. Anand, K. Temme, A. Kandala, and M. Zaletel, arXiv preprint arXiv:2306.17839 (2023).
  * Rudolph  _et al._ (2023) M. S. Rudolph, E. Fontana, Z. Holmes, and L. Cincio, arXiv preprint arXiv:2308.09109 (2023).
  * fn (4) A similar but less precise connection was made in Ref. Kechedzhi  _et al._ (2023) .
  * Jones (2010) J. A. Jones, arXiv preprint arXiv:1011.1382 (2010).
  * Doherty  _et al._ (2013) M. W. Doherty, N. B. Manson, P. Delaney, F. Jelezko, J. Wrachtrup, and L. C. Hollenberg, Physics Reports 528, 1 (2013).
  * Zu  _et al._ (2021) C. Zu, F. Machado, B. Ye, S. Choi, B. Kobrin, T. Mittiga, S. Hsieh, P. Bhattacharyya, M. Markham, D. Twitchen, _et al._ , Nature 597, 45 (2021).
  * Knill and Laflamme (1998) E. Knill and R. Laflamme, Physical Review Letters 81, 5672 (1998).

See pages 1 of supp_info.pdf

See pages 2 of supp_info.pdf

See pages 3 of supp_info.pdf

See pages 4 of supp_info.pdf

See pages 5 of supp_info.pdf

See pages 6 of supp_info.pdf

See pages 7 of supp_info.pdf

See pages 8 of supp_info.pdf

See pages 9 of supp_info.pdf

See pages 10 of supp_info.pdf

See pages 11 of supp_info.pdf

See pages 12 of supp_info.pdf

See pages 13 of supp_info.pdf

See pages 14 of supp_info.pdf

See pages 15 of supp_info.pdf

See pages 16 of supp_info.pdf

See pages 17 of supp_info.pdf

See pages 18 of supp_info.pdf

See pages 19 of supp_info.pdf

See pages 20 of supp_info.pdf

See pages 21 of supp_info.pdf

See pages 22 of supp_info.pdf