Univ Lyon, ENS Lyon, UCBL, CNRS, Inria, LIP, F-69342, Lyon Cedex 07,
<EMAIL_ADDRESS>Research Council Project AlgoQIP (grant
no. 851716) Institut Camille Jordan, Université Claude Bernard Lyon 1, 69622
Villeurbanne cedex, France and Department of Mathematics, University of Oslo,
P.O. box 1053, Blindern, 0316 Oslo<EMAIL_ADDRESS>European
Union’s Horizon 2020 research and innovation programme under the Marie
Skłodowska-Curie Action TIPTOP (grant no. 843414) Univ Lyon, ENS Lyon, UCBL,
CNRS, Inria, LIP, F-69342, Lyon Cedex 07,
<EMAIL_ADDRESS>Research Council Project AlgoQIP (grant
no. 851716) Omar Fawzi and Alexander Müller-Hermes and Ala Shayeghi Theory of
computation Quantum computation theory Hardware Quantum error correction and
fault tolerance

###### Acknowledgements.

We would like to thank Cambyse Rouzé and Daniel Stilck França for helpful
discussions.Mark Braverman 1 13th Innovations in Theoretical Computer Science
Conference (ITCS 2022) ITCS 2022 ITCS 2022 January 31–February 3, 2022
Berkeley, CA, USA 215 115

# A lower bound on the space overhead of fault-tolerant quantum computation

Omar Fawzi  Alexander Müller-Hermes  Ala Shayeghi

###### Abstract

The threshold theorem is a fundamental result in the theory of fault-tolerant
quantum computation stating that arbitrarily long quantum computations can be
performed with a polylogarithmic overhead provided the noise level is below a
constant level. A recent work by Fawzi, Grospellier and Leverrier (FOCS 2018)
building on a result by Gottesman (QIC 2013) has shown that the space overhead
can be asymptotically reduced to a constant independent of the circuit
provided we only consider circuits with a length bounded by a polynomial in
the width. In this work, using a minimal model for quantum fault tolerance, we
establish a general lower bound on the space overhead required to achieve
fault tolerance.

For any non-unitary qubit channel $\mathcal{N}$ and any quantum fault
tolerance schemes against $\mathrm{i.i.d.}$ noise modeled by $\mathcal{N}$, we
prove a lower bound of
$\max\left\\{\mathrm{Q}(\mathcal{N})^{-1}n,\alpha_{\mathcal{N}}\log
T\right\\}$ on the number of physical qubits, for circuits of length $T$ and
width $n$. Here, $\mathrm{Q}(\mathcal{N})$ denotes the quantum capacity of
$\mathcal{N}$ and $\alpha_{\mathcal{N}}>0$ is a constant only depending on the
channel $\mathcal{N}$. In our model, we allow for qubits to be replaced by
fresh ones during the execution of the circuit and we allow classical
computation to be free and perfect. This improves upon results that assumed
classical computations to be also affected by noise, and that sometimes did
not allow for fresh qubits to be added. Along the way, we prove an exponential
upper bound on the maximal length of fault-tolerant quantum computation with
amplitude damping noise resolving a conjecture by Ben-Or, Gottesman and
Hassidim (2013). 111An earlier version of this paper appeared in proceedings
of ITCS 2022. In the current version, we have extended our results to the
model with noiseless classical computation for all qubit noise channels.

###### keywords:

Fault-tolerant quantum computation, quantum error correction

###### category:

##  1 Introduction

Quantum computing is capable of solving problems for which no efficient
classical algorithms are known. However, the decoherence of quantum systems
due to inevitable interactions with the environment makes it challenging to
build reliable large-scale quantum computers. To circumvent this obstacle the
theory of quantum error correction and fault tolerance was developed [46, 47,
48].

A quantum fault tolerance scheme receives as input any ideal circuit designed
for noiseless computation and outputs an encoding of the circuit which is
robust against noise. The fault-tolerant threshold theorem was a major
achievement in quantum computing: As long as the noise level in a quantum
computer is below a certain threshold, any arbitrarily long quantum
computation can be reliably performed with a reasonably low overhead, namely,
a polylogarithmic factor in space and time [1, 34, 31, 3]. Since then a lot of
effort has been focused on introducing fault tolerance schemes with lower
resource overheads, improving the lower bounds on the fault-tolerant threshold
for different noise models (see, e.g., [33, 4, 6, 54, 57]). Gottesman [27]
showed that if quantum error correcting codes with certain properties exist,
then the space overhead can be brought down to a constant arbitrarily close to
$1$, for computations in which the number of time steps is at most polynomial
in the number of qubits. Recently, Fawzi _et al._ [26] showed that these
properties are indeed satisfied by quantum expander codes and the statement is
true even for sub-exponential computations. But what is the fundamental limit
on the space overhead for quantum fault-tolerance as a function of the noise
model? This question still remains open. More broadly, the study of general
properties and limitations of quantum fault tolerance schemes has received far
less attention. This is in part due to the difficulty of providing a
definition encompassing the different aspects of quantum fault tolerance. In
this paper, we take a step towards proving general statements about quantum
fault tolerance schemes. In particular, given an _arbitrary_ single qubit
noise channel $\mathcal{N}$, our main result is a lower bound on the
achievable space overhead of quantum fault tolerance schemes against
$\mathrm{i.i.d.}$ errors modeled by $\mathcal{N}$.

Previous works on the limitations of noisy quantum circuits typically proved
statements of the following form (see, e.g., [42, 9, 16, 30]: If the noise
level is too high, then any noisy circuit is “useless” after a limited number
of time steps. These results do not apply to the low-noise regime, i.e., when
the noise channel $\mathcal{N}$ is not far from the identity channel, and in
particular, noise levels below the fault-tolerant threshold. Therefore, they
cannot be used to derive lower bounds on the overhead of fault tolerance
schemes. Moreover, these statements crucially depend on several parameters,
including the circuit model, the noise model, and the measure of uselessness
they consider. Tweaking any of these variables can make a substantial
difference. The circuit model specifies the basic components of the quantum
circuits including the set of possible gates, state preparations, and
measurements, as well as a model of classical computation for the processing
of the measurement outcomes by the circuits. The noise model specifies how
each component of the circuit deviates from its ideal action due the noise.
Different noise models such as depolarizing, dephasing, or amplitude damping
noise are not equivalent in the context of fault tolerance (see, e.g., [9]).
Earlier fault tolerance schemes were designed for generic noise models. In
practice, however, any physical implementation of a quantum computer has some
additional noise structure. With the knowledge of the dominant noise in the
system, one can potentially utilize schemes that are tailored for a specific
noise model for cheaper suppression of the dominant noise. Indeed, biased-
noise fault tolerance beyond the usual Pauli noise models has gained growing
interest in recent years (see, e.g., [5, 44, 12, 51, 28]). Earlier relevant
results on limitations of noisy quantum computation, however, are mostly
focused on a particular noise channel, typically, depolarizing noise (with the
exception of Ref. [52]), and it is not clear if the introduced techniques can
be extended to other noise models.

With current technology, classical computation can be performed with
practically perfect accuracy. Therefore, it is reasonable and conventional to
assume classical computation to be error-free when evaluating the performance
of quantum fault tolerance schemes. For instance, in this context, given
measured syndromes of a quantum stabilizer code, computing a description of a
corresponding error is assumed to be noiseless. While some earlier
impossibility results establish very strong limitations for noisy circuits
(see the discussion in Section 1.3), they do not incorporate the aid of
noiseless classical computation and the adaptivity achieved through classical
control. In these works, the classical systems are not distinguished from the
quantum systems and they are assumed to be subject to the same noise. In fact,
without this assumption, the “uselessness” statements established in these
works fail to hold even for arbitrarily long circuits. Therefore, these
results are not directly applicable to the fault tolerance schemes which rely
on perfect classical computation and control. By allowing this additional
resource in our model, we address a limitation of the previous results on the
power of noisy quantum circuits. Our results apply to adaptive protocols
composed of a hybrid of classical and quantum computation.

Before stating our results more formally, we first need to describe our
quantum circuit model.

###  1.1 Our model

(a)

(b)

Figure 1: Illustration of the circuit model

A (noiseless) quantum circuit $C$ in our model is defined by a sequence
$\left\\{\mathcal{L}_{i}\right\\}_{i\in[T]}$ of arbitrary completely positive
and trace-preserving (CPTP) linear maps, acting on a potentially non-trivial
input system. For any density operator $\rho$ on the input Hilbert space, the
output of the circuit is given by

$C(\rho)\coloneqq\left(\mathcal{L}_{T}\circ\cdots\circ\mathcal{L}_{2}\circ\mathcal{L}_{1}\right)\left(\rho\right)\enspace,$

where we use the same notation $C$ to denote the overall channel corresponding
to the action of the circuit $C$. We use the term _time_ to refer to the
vertical cuts between the layers of computation, as shown in Fig. 1. The
$i$-th _time step_ of the circuit is defined by $\mathcal{L}_{i}$ acting
between $t=i-1$ and $t=i$.

In our model, we distinguish between classical and quantum subsystems and we
allow free and noiseless classical computation. Given a qubit noise channel
$\mathcal{N}$, for any quantum circuit $C$, the noisy implementation of $C$
with $\mathrm{i.i.d.}$ noise modeled by $\mathcal{N}$ is obtained by
interlacing the computational steps $\mathcal{L}_{i}$ with layer of the noise
channel $\mathcal{N}$ acting independently on every qubit, while as shown in
Fig. 1, the classical subsystems are unaffected by the noise. We denote by
$\mathrm{i.i.d._{\mathcal{N}}}(C)$ the overall channel corresponding to the
noisy implementation of $C$. For a circuit $C$, the _width_ $Width(C)$ of the
circuit is the maximum number of _qubits_ at any time step and its _length_
$Length(C)$ is the number of time steps of the circuit. Note that in our
model, we do not count the size of the classical subsystems in $Width(C)$; in
other words, the width of the circuit is determined by the number of qubit
systems that are subject to the noise. Moreover, classical computations do not
contribute to $Length(C)$ in this model.

###  1.2 Discussion of our main results, proof techniques, and related work

Limitations on quantum memory times. We consider noisy quantum circuits in the
$\mathrm{i.i.d.}_{\mathcal{N}}$ error model, for an arbitrary non-unitary
qubit channel $\mathcal{N}$. Our main technical contribution is the following:

######  Theorem 1.1.

Let $\mathcal{I}$ denote the qubit identity channel and $\mathcal{N}$ be a
non-unitary qubit channel. Then there exists a constant $p\in(0,1]$ only
depending on $\mathcal{N}$ such that the following holds: Let $C$ be an
arbitrary circuit of length $T$ and width $n$ such that
$T\geq\left(2/p\right)^{2n}$. Then for any pair of ideal encoding and decoding
maps $\mathcal{E}$ and $\mathcal{D}$ (of appropriate input and output
dimensions), we have

$\left\|\mathcal{D}\circ\mathrm{i.i.d.}_{\mathcal{N}}\left(C\right)\circ\mathcal{E}-\mathcal{I}\right\|_{1}\geq\epsilon_{0}\enspace,$

for some universal constant $\epsilon_{0}\geq 1/128$.

The constant $p=p(\mathcal{N})$ in Theorem 1.1 is given by
$p(\mathcal{N})=\max(p_{1}(\mathcal{N}),p_{2}(\mathcal{N}))$ where

$p_{1}(\mathcal{N})=\max\left\\{q\in\left[0,1\right]:\mathcal{N}\geq
q\mathcal{M},\text{ for an entanglement breaking quantum channel
}\mathcal{M}\right\\}.$

and

$p_{2}(\mathcal{N})=\max\left\\{q^{2}\lambda_{\min}\left(C_{\mathcal{M}^{\dagger}\circ\mathcal{M}}\right)/204800:q\in\left[0,1\right],\leavevmode\nobreak\
\mathcal{N}\geq q\mathcal{M},\text{ for quantum channel
}\mathcal{M}\right\\}.$

Here, we write $\mathcal{N}\geq\mathcal{M}$ for linear maps $\mathcal{N}$ and
$\mathcal{M}$ if the difference $\mathcal{N}-\mathcal{M}$ is completely
positive. We will show that $p_{1}(\mathcal{N})>0$ for any unital qubit
channel $\mathcal{N}$ that is not unitary, and that $p_{2}(\mathcal{N})>0$ for
every non-unital qubit channel $\mathcal{N}$.

We point out that the statement of Theorem 1.1 does not hold as is for quantum
circuits operating on qudits rather than qubits and affected by any non-
unitary noise channel. By taking a direct sum of the ideal quantum channel and
a completely depolarizing channel it is easy to construct non-unitary noise
channels for which quantum information can be stored indefinitely in a
decoherence-free subspace. To obtain an upper bound on the storage time in
these cases, further assumptions are needed.

Theorem 1.1 states that for any noise channel $\mathcal{N}$, no noisy quantum
circuit in the $\mathrm{i.i.d.}_{\mathcal{N}}$ error model is capable of
preserving even a single (unknown) qubit for more than an exponential number
of time steps in its width. We would like to emphasize two features of our
result:

  1. 1.

The quantum channels making up the circuit do not need to be unital.
Therefore, they can remove all the entropy produced by the noise channel along
the computation, for example by introducing ancilla qubits.

  2. 2.

Our results also hold for circuits with free and noiseless classical
computation. Even after long computation times, it is then possible to prepare
orthogonal states conditioned on earlier measurement outcomes that have been
kept in the perfect classical memory.

In order to prove the result, we consider two parallel instances of the
circuit $C$ and prove that for any input state the distance from the set of
separable states with respect to this bipartition is contracted by a factor of
$1-p^{2n}$ (with $p>0$ as above) in each time step. This implies that the
circuit $C$ itself cannot preserve every quantum state for more than
$\left(1/p\right)^{2n}$ time steps.

Ben-Or _et al._ [9] studied the limitations of fault-tolerant quantum
computation under the independent noise model $\mathrm{i.i.d.}_{\mathcal{N}}$,
for different classes of non-unitary qubit channels. Applying such a channel
many times either converges to a limit channel mapping every quantum state to
a point in the Bloch sphere (e.g., for the depolarizing channel), or it
converges to a limit quantum channel mapping every quantum state to a diameter
of the Bloch sphere (e.g., for the dephasing channel). By slightly
generalizing an earlier entropic argument222This argument was stated in [2],
but the proof of a key lemma is not correct. This was corrected in [37]., Ben-
Or _et al._ prove that if the limit channel maps every quantum state to the
maximally mixed state, then it is impossible to compute for more than
$\mathrm{O}(\log n)$ steps and they show how to achieve this bound up to a
polylogarithmic factor in $\log n$. Entropic arguments of this kind are
crucially based on the assumption that entropy cannot be removed during the
execution of the circuit. In particular, these arguments do not apply for our
circuit model (including common settings of fault-tolerance [1, 3]) where the
entropy produced by the noise channel can be removed along the computation
(cf., feature 1 from above). When the limiting quantum channel maps every
quantum state to a diameter of the Bloch sphere (e.g., the dephasing channel),
Ben-Or _et al._ prove that it is impossible to store quantum information for
more than a polynomial number of time steps, however again assuming no fresh
ancilla qubits and no noiseless classical computation. Using standard
threshold theorems, they also show that for this class of channels,
computations involving $\mathrm{O}(n^{a})$ qubits for $\mathrm{O}(n^{b})$ time
steps are possible, provided $a+b<1$. Finally, if the limit channel has a
fixed point other than the center of the Bloch sphere (e.g., the amplitude
damping channel) then exponentially long quantum computations are possible.
This is achieved by using the noise itself as a refrigerator to cool down the
qubits and produce fresh ancillas. They also conjecture that for this class of
channels it is impossible to compute for more than exponential time with no
fresh ancilla qubits. To our knowledge, prior to this work, no proof of this
statement existed. Theorem 1.1 proves this conjecture to be true. In addition,
our result applies even if fresh ancillas are used and the upper bound on the
length becomes $e^{\mathrm{O}(n+m)}$ with $m$ ancilla qubits.

In a related work, Raginsky [40] considers the noise model where a fixed noise
channel $\mathcal{T}$ acts collectively on all the qubits in the quantum
circuit after each computational step. He shows that, for any quantum circuit
involving only unitary operations, if the channel $\mathcal{T}$ modeling the
noise is strictly contractive then the distance of possible output states of
the circuit is exponentially small in the length of the circuit. Moreover, he
shows that the set of strictly contractive channels is dense in the set of all
quantum channels. Using this fact and under the assumption that quantum
operations can be performed only with a finite precision, he argues that
strictly contractive channels serve as a natural abstract model for noise in
any physically realizable quantum computer. Our work can be seen as an
extension of this argument. In particular, we show how to apply a similar
reasoning when the channel $\mathcal{T}$ modeling the noise is given by tensor
powers of an arbitrary non-unitary qubit channel, and we further extend the
argument by taking into account free and perfect classical computation
(obtaining feature 2 from above). Note that in general strict contractivity of
a quantum channel does not necessarily imply the same property for its tensor
powers (see the discussion at the end of Section 3 for more details).

Limitations on quantum fault-tolerance. Inspired by the observation of Theorem
1.1, in Section 4, we provide a natural high-level description of quantum
fault tolerance schemes with minimal assumptions. A fault tolerance scheme is
a circuit encoding associated with a family of quantum error correcting codes.
Intuitively, we only require a fault tolerance scheme to be capable of
implementing any arbitrary logical circuit on _encoded data_ in a code from
the family, up to arbitrary accuracy in the presence of noise. Here, we assume
that the encoding and decoding maps for the quantum error correcting code can
be implemented perfectly. We quantify the accuracy in terms of the induced
trace distance between the channels corresponding to the ideal circuit and its
fault-tolerant implementation with noise. To our knowledge, this requirement
is satisfied by most, if not all, known fault tolerance schemes.

In this work we do not focus on investigating the limitations of _computation_
using noisy quantum circuits. Indeed, our results are shown assuming perfect
classical computation with _unlimited_ power is possible. We are rather
interested in proving limitations of fault tolerance schemes as procedures
which, _oblivious_ to the overall computation being performed, allow the
implementation of any ideal input circuit using noisy components.

Our high-level definition of fault tolerance enables us to recast the problem
of proving a lower bound on the space overhead for fault-tolerant quantum
computation into a more tractable problem in the better understood framework
of quantum Shannon theory. Note that a fault tolerance scheme should naturally
be able to implement a quantum memory. From this alternative perspective, a
quantum memory for $T$ time steps in the $\mathrm{i.i.d.}_{\mathcal{N}}$ noise
model corresponds to one-way point-to-point quantum communication with $T-1$
intermediate relay points on a line, linked by $T$ instances of the noisy
channel $\mathcal{N}$, where the relay points are allowed to perform arbitrary
(noiseless) quantum operations and communicate classically with the following
relay points on the line. Similar communication models have been studied
earlier in the quantum Shannon theory literature (see, e.g., [39]). Here,
given a qubit channel $\mathcal{N}$, we are interested in the optimal rate of
communication over the links for reliably sending $n$ qubits as a function of
$T$ and $n$. The case $T=1$ is well-studied in the quantum Shannon theory
literature and the optimal rate is given by the quantum capacity of
$\mathcal{N}$. Theorem 1.1 implies an upper bound on the achievable rates (or,
equivalently, a lower bound on the necessary overhead) as a function of $T$.
The following is our main result:

######  Theorem 1.2.

Let $\mathcal{N}$ be a non-unitary qubit channel. For any fault tolerance
scheme against the $\mathrm{i.i.d.}_{\mathcal{N}}$ noise model, the number of
physical qubits is at least

$\max\left\\{\mathrm{Q}(\mathcal{N})^{-1}n,\alpha_{\mathcal{N}}\log
T\right\\}\enspace,$

for circuits of length $T$ and width $n$, and any constant accuracy
$\epsilon\leq 1/128$. Here, $\mathrm{Q}(\mathcal{N})$ denotes the quantum
capacity of $\mathcal{N}$ and $\alpha_{\mathcal{N}}=\frac{1}{2\log 2/p}$,
where $p\in(0,1]$ is a constant only depending on the channel $\mathcal{N}$.
In particular, fault tolerance is not possible even for a single time step if
$\mathcal{N}$ has zero quantum capacity or the space overhead is strictly less
than $\mathrm{Q}(\mathcal{N})^{-1}$.

Theorem 1.2 in particular implies that fault-tolerant quantum computation with
constant space overhead is not achievable beyond exponential computations for
any noise channel $\mathcal{N}$.

For the $p$-depolarizing noise given by
$\mathcal{N}(\rho)=(1-p)\rho+p\frac{\mathds{1}}{2}$, the quantum capacity is
known to be zero for $p>\frac{1}{3}$ [15]. Thus, for $p>\frac{1}{3}$, the
lower bound becomes $+\infty$, i.e., fault tolerance is not possible in our
model. This gives stronger limitations compared to previous results [42, 30,
16] (except for a result in [30] where making an assumption on the gate set,
namely CNOT is the only allowed two-qubit gate, they show fault-tolerance is
not possible when $p\geq 29.3\%$). We stress that all these results are
incomparable as the models are different. For $p\leq 1/3$, we cannot rule out
fault tolerance, but we can show a lower bound on the overhead as a function
of the circuit depth.

###  1.3 Related work on limitations of quantum circuits under strong noise

The results discussed below are not directly relevant to our work in the sense
that they do not apply to noise levels below the fault-tolerant threshold.
However, they establish impossibility results for noisy circuits and prove
upper bounds on the threshold for fault-tolerant computation.

Razborov [42] considers $p$-depolarizing $\mathrm{i.i.d.}$ noise model and
circuits with quantum gates which are allowed to be arbitrary quantum
channels. He proves that if $p>1-1/k$ then for any circuit in this model of
width $n$ and length $T$ with gates of fan-in at most $k$, the distance
between the states obtained by applying the circuit on any pair of input
states decreases as $n2^{-\Omega(T)}$. In particular, any computation of
length $T=\Omega(\log n)$ is essentially useless since the output is
independent of the initial state. Such a strong notion of uselessness and
upper bound on $T$ as a function of $n$ is possible in this case because of
the strong assumptions: the noise is sufficiently high and classical
information is subject to noise. If classical information can be stored
perfectly, one can imagine a circuit in which part of the input is measured in
the first step, stored, and then output at the end (as in the second strategy
given above): for arbitrarily large values of $T$ this circuit is not useless.
Moreover, in our circuit model, there is no restriction on the gate set of the
circuit, in particular the fan-in of the gates can be arbitrary. Our bound
applies to the $\mathrm{i.i.d.}$ noise model for any non-unitary qubit noise
channel. Finally, we point out that for the model considered by Razborov, our
techniques can be adapted to recover similar bounds for a large class of
quantum channels.

Using a different approach, Kempe _et al._ [30] improve the threshold upper
bound to $1-\Theta(1/\sqrt{k})$. However, their result is not quite comparable
with Razborov’s earlier result since they are obtained in different models.
Kempe _et al._ consider circuits composed of arbitrary one qubit CPTP gates
which are assumed to be essentially noiseless and $k$-qubit gates that are
probabilistic mixtures of unitary operations preceded by independent
$p$-depolarizing noise on their input qubits. They also assume that the output
is the outcome of a measurement of a designated qubit (or a constant number of
qubits) in the computational basis. They prove that if
$p>1-\Theta(1/\sqrt{k})$ then for any circuit of length $T$ in this model, the
total variation distance between the output distributions for any pair of
input states decreases as $2^{-\Omega(T)}$. Similar to Razborov’s, their model
does not allow noiseless classical computation and classically controlled
operations. Note that a similar bound is known to hold for noisy classical
circuits as well [24, 25].

When classical computation is assumed to be free and perfect, a measure of
“uselessness” for noisy quantum circuits should naturally capture quantum
phenomena that are not observed in classical circuits. One such measure that
has been studied in earlier works [52] is being efficiently simulable
classically. Along this direction, Buhrman _et al._ [16] show that quantum
circuits consisting of noiseless stabilizer operations and arbitrary single
qubit unitary gates followed by $45.3\%$ depolarizing noise can be efficiently
simulated by classical circuits. Their result is incomparable to ours for the
same reasons above.

##  2 Preliminaries

Let $\mathcal{M}_{d}$ denote the set of $d\times d$ matrices with complex
entries. Consider a quantum system described by the $d$-dimensional Hilbert
space ${\mathbb{C}}^{d}$. Quantum states of the system are described by the
set of _density operators_ given by $\left\\{\rho\in\mathcal{M}_{d}:\rho\geq
0,\mathrm{Tr}(\rho)=1\right\\}$. Pure state density operators are rank-one
projectors $\rho=\left|\psi\middle\rangle\middle\langle\psi\right|$. A density
operator $\zeta$ on ${\mathbb{C}}^{d_{A}}\otimes{\mathbb{C}}^{d_{B}}$ is
called _separable_ if it can be written as $\zeta=\sum_{i\in
I}p_{i}\,\rho_{i}\otimes\sigma_{i}\enspace$ for some finite set $I$, a
probability distribution $p:I\rightarrow[0,1]$, and density operators
$\\{\rho_{i}:i\in I\\}$ on ${\mathbb{C}}^{d_{A}}$ and $\\{\sigma_{i}:i\in
I\\}$ on ${\mathbb{C}}^{d_{B}}$. We denote by $\mathrm{Sep(A:B)}$ the set of
all separable state on ${\mathbb{C}}^{d_{A}}\otimes{\mathbb{C}}^{d_{B}}$ with
respect to the bi-partition $A:B$, where the two subsystems are labeled $A$
and $B$. A quantum state is called _entangled_ if it is not separable.

Representation of Quantum channels. A _quantum channel_ is a completely
positive and trace-preserving linear map
$\mathcal{T}:\mathcal{M}_{d_{A}}\rightarrow\mathcal{M}_{d_{B}}$. We denote by
$\mathcal{I}_{d}:\mathcal{M}_{d}\rightarrow\mathcal{M}_{d}$ the identity
channel, i.e., the identity map on $\mathcal{M}_{d}$. Next, we review some
basics about different representations of quantum channels (for more details
see [56]). Let $\mathcal{T}:\mathcal{M}_{d_{A}}\rightarrow\mathcal{M}_{d_{B}}$
be a quantum channel. Let

$C_{\mathcal{T}}=\textstyle\sum_{i,j\in[d]}\mathcal{T}\left(\left|i\middle\rangle\middle\langle
j\right|\right)\otimes\left|i\middle\rangle\middle\langle j\right|\enspace,$
(1)

where $\left\\{\left|i\right\rangle:i\in[d_{A}]\right\\}$ is the standard
basis of ${\mathbb{C}}^{d_{A}}$. The operator $C_{\mathcal{T}}$ is called the
_Choi matrix_ of $\mathcal{T}$. The rank of $C_{\mathcal{T}}$ is called the
Choi rank of $\mathcal{T}$. For any quantum channel $\mathcal{T}$, there
exists a finite set $I$ and linear operators
$K_{i}:{\mathbb{C}}^{d_{A}}\rightarrow{\mathbb{C}}^{d_{B}}$ for any $i\in I$
such that $\sum_{i\in I}K_{i}^{\dagger}K_{i}=\mathds{1}_{d_{A}}$ and
$\mathcal{T}(X)=\sum_{i\in I}K_{i}XK_{i}^{\dagger}$, for all
$X\in\mathcal{M}_{d_{A}}$. Any representation of this form is called a _Kraus
representation_ of the channel $\mathcal{T}$ and the operators
$\left\\{K_{i}\right\\}_{i\in I}$ are called the corresponding _Kraus
operators_. Note that Kraus representation in general is not unique, and the
minimum number of Kraus operators in any Kraus representation of $\mathcal{T}$
is equal to the Choi rank of $\mathcal{T}$ [56, Corollary 2.23]. Important
classes of quantum channels can be defined via their Kraus representation: A
quantum channel is called _unitary_ if it admits a Kraus decomposition with a
single unitary Kraus operator, and it is called _entanglement breaking_ if it
admits a Kraus representation with Kraus operators $K_{i}$ of rank $1$.
Consider quantum systems labelled $A_{1},A_{2},B_{1}$ and $B_{2}$. A bipartite
quantum channel
$\mathcal{T}:\mathcal{M}_{d_{A_{1}}}\otimes\mathcal{M}_{d_{B_{1}}}\rightarrow\mathcal{M}_{d_{A_{2}}}\otimes\mathcal{M}_{d_{B_{2}}}$
is called a _separable quantum channel_ with respect to the bipartition
$(A_{1},A_{2}):(B_{1},B_{2})$ if it admits a Kraus representation with Kraus
operators of the form $K_{i}=K^{A}_{i}\otimes K^{B}_{i}$ with operators
$K^{A}_{i}:{\mathbb{C}}^{d_{A_{1}}}\rightarrow{\mathbb{C}}^{d_{A_{2}}}$ and
$K^{B}_{i}:{\mathbb{C}}^{d_{B_{1}}}\rightarrow{\mathbb{C}}^{d_{B_{2}}}$. We
denote the set of these quantum channels by
$\mathrm{SepC}\left((A_{1},A_{2}):(B_{1},B_{2})\right)$. The set of quantum
channels from $\mathcal{M}_{d_{A}}$ to $\mathcal{M}_{d_{B}}$ is compact and
convex, and its extreme points are given by the quantum channels
$\mathcal{T}:\mathcal{M}_{d_{A}}\rightarrow\mathcal{M}_{d_{B}}$ having a Kraus
representation $\mathcal{T}\left(X\right)=\sum_{i}K_{i}XK_{i}^{\dagger}$ such
that $\left\\{K_{i}^{\dagger}K_{j}\right\\}_{i,j}$ is a linearly independent
set [18]. For any quantum channel
$\mathcal{T}:\mathcal{M}_{d_{A}}\rightarrow\mathcal{M}_{d_{B}}$, there exists
an isometry
$V:{\mathbb{C}}^{d_{A}}\rightarrow{\mathbb{C}}^{d_{B}}\otimes{\mathbb{C}}^{d_{E}}$,
for some $d_{E}\in{\mathbb{N}}$, such that
$\mathcal{T}(X)=\mathrm{Tr}_{E}\left(VXV^{\dagger}\right)$, for every
$X\in{\mathbb{C}}^{d_{A}}$. Any such representation of $\mathcal{T}$ is called
a _Stinespring representation_ and the isometry $V$ is referred to as a
_Stinespring dilation_ of $\mathcal{T}$. The dimension $d_{E}$ can be chosen
to be equal to the Choi rank of $\mathcal{T}$ [56, Corollary 2.27].

Trace-distance, quantum $\chi^{2}$-divergence, and contraction coefficients.
The _induced trace norm_ of a linear map
$\mathcal{T}:\mathcal{M}_{d}\rightarrow\mathcal{M}_{d^{\prime}}$ is defined as

$\left\|\mathcal{T}\right\|_{1}\coloneqq\max\left\\{\left\|\mathcal{T}(X)\right\|_{1}\,:\,X\in\mathcal{M}_{d},\,\left\|X\right\|_{1}\leq
1\right\\}\enspace.$

We will need the _trace-norm contraction coefficient_ of a quantum channel
$\mathcal{T}:\mathcal{M}_{d}\rightarrow\mathcal{M}_{d}$ given by

$\eta_{\text{tr}}\left(\mathcal{T}\right):=\sup_{\rho,\sigma}\frac{\left\|\mathcal{T}(\rho)-\mathcal{T}(\sigma)\right\|_{1}}{\left\|\rho-\sigma\right\|_{1}}\enspace,$
(2)

where the supremum is over all pairs of quantum states. This quantity can be
regarded as a quantum analogue of the Dobrushin ergodicity coefficient [21],
which is an important tool in the study of Markov processes. We will often use
that

$\eta_{\text{tr}}\left(\mathcal{T}\right)=\frac{1}{2}\max_{\psi\perp\phi}\left\|\mathcal{T}\left(|\psi\rangle\\!\langle\psi|-|\phi\rangle\\!\langle\phi|\right)\right\|_{1}\enspace,$
(3)

where the maximum is over orthogonal pairs of pure states (see [43]). In
particular, $\eta_{\text{tr}}(\mathcal{T})=1$ if and only if, there exists a
pure state $\psi\in{\mathbb{C}}^{d}$ for which
$(\mathcal{T}^{\dagger}\circ\mathcal{T})\left(|\psi\rangle\\!\langle\psi|\right)$
is not full-rank.

For a pair of density operators $\rho$ and $\sigma$, the $\chi^{2}$-divergence
is defined by

$\displaystyle\chi^{2}(\rho,\sigma)$
$\displaystyle\coloneqq\mathrm{Tr}\left((\rho-\sigma)\sigma^{-1/2}(\rho-\sigma)\sigma^{-1/2})\right)\
,$

when $\mathrm{supp}(\rho)\subseteq\mathrm{supp}(\sigma)$ and $+\infty$,
otherwise. The operator $\sigma^{-1/2}$ is to be understood as generalized
inverse of $\sigma^{1/2}$. Note that we have
$\chi^{2}(\rho,\sigma)=\mathrm{Tr}(\rho\sigma^{-1/2}\rho\sigma^{-1/2})-1$.

$\chi^{2}$-divergence is monotone under quantum channels and jointly convex,
see e.g., [49, Proposition 7]. Moreover, we have

$\left\|\rho-\sigma\right\|_{1}^{2}\leq\chi^{2}(\rho,\sigma)\enspace,$ (4)

for any pair of density operators $\rho$ and $\sigma$ [49, Lemma 5]. We will
use the _$\chi^{2}$ contraction coefficient_ of a quantum channel
$\mathcal{T}:\mathcal{M}_{d}\rightarrow\mathcal{M}_{d}$ given by

$\displaystyle\eta_{\chi}\left(\mathcal{T}\right)$
$\displaystyle\coloneqq\sup_{\rho,\sigma}\frac{\chi^{2}(\mathcal{T}(\rho),\mathcal{T}(\sigma))}{\chi^{2}(\rho,\sigma)}\enspace,$
(5)

where the supremum is over all pairs of quantum states. For any quantum
channel $\mathcal{T}:\mathcal{M}_{d}\rightarrow\mathcal{M}_{d}$, the following
inequality holds [49, Theorem 14]:

$\eta_{\chi}\left(\mathcal{T}\right)\leq\eta_{\mathrm{tr}}\left(\mathcal{T}\right)\enspace.$
(6)

Quantum capacity. The quantum capacity of a quantum channel is the maximum
rate at which it can reliably transmit quantum information over asymptotically
many uses of the channel.

######  Definition 2.1.

For a quantum channel
$\mathcal{T}:\mathcal{M}_{d_{A}}\rightarrow\mathcal{M}_{d_{B}}$, a
communication rate $R$ is called $\epsilon$-_achievable_ if there exists
$n_{\epsilon}$ such that for all $n\geq n_{\epsilon}$, there is an encoding
quantum channel $\mathcal{E}_{n}:\mathcal{M}^{\otimes
Rn}_{2}\rightarrow\mathcal{M}^{\otimes n}_{d_{A}}$ and a decoding channel
$\mathcal{D}_{n}:\mathcal{M}^{\otimes
n}_{d_{B}}\rightarrow\mathcal{M}^{\otimes Rn}_{2}$ such that
$\left\|(\mathcal{D}_{n}\circ\mathcal{T}^{\otimes
n}\circ\mathcal{E}_{n})(\rho)-\rho\right\|_{1}\leq\epsilon$, for all
$\rho\in\mathcal{M}^{\otimes Rn}_{2}$. A rate $R$ is an _achievable
communication rate_ if it is $\epsilon$-achievable for all $\epsilon\in(0,2]$.
The _quantum capacity_ of $\mathcal{T}$ is the supremum over all achievable
rates.

Representation of qubit channels. Consider the set of single-qubit Pauli
operators $\mathcal{P}=\\{\mathds{1},\mathrm{X},\mathrm{Y},\mathrm{Z}\\}$
defined as

$\mathds{1}=\begin{pmatrix}1&0\\\
0&1\end{pmatrix},\;\mathrm{X}=\begin{pmatrix}0&1\\\
1&0\end{pmatrix},\;\mathrm{Y}=\begin{pmatrix}0&-\mathrm{i}\\\
\mathrm{i}&0\end{pmatrix},\;\mathrm{Z}=\begin{pmatrix}1&0\\\
0&-1\end{pmatrix}.$ (7)

The set of $2\times 2$ Hermitian matrices is a real vector space. One can
easily verify that $\mathcal{P}$ forms an orthogonal basis for this set, with
respect to the Hilbert-Schmidt inner product defined as $\langle
A,B\rangle=\mathrm{Tr}\left(A^{\dagger}B\right)$. In particular, any single-
qubit quantum state $\rho$ can be written in the _Bloch sphere representation_
as

$\rho=\frac{1}{2}\left(\mathds{1}+r\cdot\sigma\right)\enspace,$ (8)

where $r=\left(r_{x},r_{y},r_{z}\right)\in{\mathbb{R}}^{3}$ with
$\left\|r\right\|_{2}\leq 1$ and $\sigma$ is the vector of Pauli matrices
$\left(\mathrm{X},\mathrm{Y},\mathrm{Z}\right)$. It has been shown in [11],
that the action of any qubit channel
$\mathcal{N}:\mathcal{M}_{2}\rightarrow\mathcal{M}_{2}$ can be written as
$\mathcal{N}\left(\rho\right)=U\mathcal{C}_{[t,\lambda]}\>\\!\\!\left(V\rho
V^{\dagger}\right)U^{\dagger}$, with

$\mathcal{C}_{[t,\lambda]}\>\\!\\!\left(\frac{1}{2}\left[\mathds{1}+r\cdot\sigma\right]\right)=\frac{1}{2}\left(\mathds{1}+\left(t+\Lambda
r\right)\cdot\sigma\right)\enspace,$ (9)

where $t=\left(t_{x},t_{y},t_{z}\right)\in{\mathbb{R}}^{3}$ with
$\left\|t\right\|_{2}\leq 1$ and $\Lambda=\mathrm{diag}\left(\lambda\right)$
with
$\lambda=\left(\lambda_{x},\lambda_{y},\lambda_{z}\right)\in{\mathbb{R}}^{3}$
and $\left\|\Lambda\right\|\leq 1$. The qubit channel $\mathcal{N}$ is
_unital_ , i.e., $\mathcal{N}(\mathds{1})=\mathds{1}$, if and only if $t=0$ in
this representation. Imposing complete positivity of the unital map
$\mathcal{C}_{[0,\lambda]}$ is equivalent to restricting the parameters
$\lambda\in{\mathbb{R}}^{3}$ to a regular tetrahedron [11] with corners
corresponding to the conjugation by the Pauli operators
$\mathds{1},\mathrm{X},\mathrm{Y},\mathrm{Z}$, respectively. Specifically, the
set of unital qubit channels is given by

$\left\\{U\mathcal{C}_{[0,\lambda]}\>\\!\\!\left(V\rho
V^{\dagger}\right)U^{\dagger}:U,V\mathrm{unitary},\lambda\in\mathrm{conv}\\!\left\\{\left(1,1,1\right),\left(1,-1,-1\right),\left(-1,1,-1\right),\left(-1,-1,1\right)\right\\}\right\\}.$
(10)

The middle points on the edges of the tetrahedron of Eq. (10) are the
permutations of $\left(\pm 1,0,0\right)$, and they are the vertices of a
regular octahedron corresponding to unital entanglement breaking qubit
channels. From these geometric considerations and the fact that entanglement
breaking channels stay entanglement breaking under composition by unitary
quantum channels, we obtain the following lemma:

######  Lemma 2.2.

Any unital qubit channel
$\mathcal{N}:\mathcal{M}_{2}\rightarrow\mathcal{M}_{2}$ can be written as a
convex combination

$\mathcal{N}=(1-p)\mathcal{T}+p\mathcal{B},$

where $\mathcal{T}:\mathcal{M}_{2}\rightarrow\mathcal{M}_{2}$ is a unitary
quantum channel and $\mathcal{B}:\mathcal{M}_{2}\rightarrow\mathcal{M}_{2}$ is
entanglement breaking.

##  3 Maximal length of noisy quantum computation

Let $C$ be a quantum circuit of width $n$ and length $T$ defined by a sequence
of quantum channels $\left\\{\mathcal{L}_{i}\right\\}_{i\in[T]}$, as depicted
in Fig. 2. For $i\in\\{0,\ldots,T\\}$, let $(A_{i}:B_{i})$ be a bipartition of
the registers of the circuit after $i$ time steps into disjoint subsets such
that
$\mathcal{L}_{i}\in\mathrm{SepC}\left(A_{i-1},A_{i}:B_{i-1},B_{i}\right)$,
i.e., $\mathcal{L}_{i}$ in each time step is a separable channel with respect
to the bipartition of the subsystems into the $A$ and $B$ parts. Furthermore,
for every $i\in\left\\{0,\ldots,T\right\\}$, let $A_{i}=A^{c}_{i}A^{q}_{i}$
and $B_{i}=B^{c}_{i}B^{q}_{i}$, where $A^{c}_{i}$ and $B^{c}_{i}$ are
classical subsystems of $A_{i}$ and $B_{i}$, respectively, of arbitrary finite
dimensions and $A^{q}_{i}$ and $B^{q}_{i}$ are the quantum subsystems which
contain a total of $n_{i}$ qubits. Let $\mathcal{N}$ be an arbitrary non-
unitary qubit channel and consider the noisy implementation of $C$ in the
$\mathrm{i.i.d._{\mathcal{N}}}$ model. Recall that in our model only the
quantum subsystems are subject to the noise channel $\mathcal{N}$. We prove
that $\mathrm{i.i.d.}_{\mathcal{N}}(C)$ is not capable of preserving the
entanglement between the $A$ and $B$ subsystems for more than exponential time
in the width of $C$.

We define

$\displaystyle\chi^{2}_{\mathrm{Sep}\left(A:B\right)}\\!\left(\tau_{AB}\right)$
$\displaystyle=\min_{\sigma\in\mathrm{Sep}\left(A:B\right)}\chi^{2}(\tau_{AB},\sigma_{AB})\
.$

It is simple to see that this measure is monotone under separable quantum
channels and convex in the state.

We denote by $\rho_{AB}^{i}$ the state of the noisy circuit after $i$ time
steps. The following lemma is our main technical contribution which is of
independent interest.

Figure 2: An illustration of $\mathrm{i.i.d._{\mathcal{N}}}(C)$. In each time
step, every qubit is subject to the noise channel $\mathcal{N}$. The classical
subsystems are assumed to be noise-free. The registers are partitioned into
disjoint subsets A and B such that the quantum channels $\mathcal{L}_{i}$ are
separable with respect to this bipartition.

######  Lemma 3.1.

For every non-unitary qubit channel $\mathcal{N}$, there exists a constant
$p\in(0,1]$ such that
$\chi^{2}_{\mathrm{Sep}\left(A:B\right)}\\!\left(\rho^{i+1}_{AB}\right)\leq\left(1-p^{n}\right)\chi^{2}_{\mathrm{Sep}\left(A:B\right)}\\!\left(\rho^{i}_{AB}\right)$,
if $\chi^{2}_{\mathrm{Sep}\left(A:B\right)}\\!\left(\rho^{i}_{AB}\right)\geq
1/16$.

######  Proof 3.2.

In time step $i+1$, each of the $n_{i}$ qubits in the noisy circuit goes
through the noise channel
$\mathcal{N}:\mathcal{M}_{2}\rightarrow\mathcal{M}_{2}$ followed by a
separable channel
$\mathcal{L}_{i+1}\in\mathrm{SepC}\left(A_{i},A_{i+1}:B_{i},B_{i+1}\right)$.
We use two different approaches to prove Lemma 3.1 for unital and non-unital
quantum channels.

Case I: $\mathcal{N}$ is unital. In this case, we prove the contractivity of
$\chi^{2}_{\mathrm{Sep}\left(A:B\right)}\\!$ independent of the initial value
$\chi^{2}_{\mathrm{Sep}\left(A:B\right)}\\!\left(\rho^{i}\right)$. By Lemma
2.2, we may write

$\mathcal{N}=\left(1-p\right)\,\mathcal{T}+p\,\mathcal{B}\enspace,$ (11)

where $\mathcal{T}:\mathcal{M}_{2}\rightarrow\mathcal{M}_{2}$ is a unitary
quantum channel and $\mathcal{B}:\mathcal{M}_{2}\rightarrow\mathcal{M}_{2}$ is
entanglement breaking. Since $\mathcal{N}$ itself is not unitary, we have
$p>0$. There exists a separable quantum channel
$\mathcal{S}:\mathcal{M}_{2^{n_{i}}}\rightarrow\mathcal{M}_{2^{n_{i}}}$ with
respect to the bipartition into $A$ and $B$, such that

$\mathcal{N}^{\otimes
n_{i}}=\left(1-p^{n_{i}}\right)\mathcal{S}+p^{n_{i}}\,\mathcal{B}^{\otimes
n_{i}}\enspace,$ (12)

and we can compute

$\displaystyle\chi^{2}_{\mathrm{Sep}\left(A:B\right)}\\!\left(\rho^{i+1}\right)$
$\displaystyle=\chi^{2}_{\mathrm{Sep}\left(A:B\right)}\\!\left(\left(\mathcal{L}_{i+1}\circ\left(\mathcal{N}^{\otimes
n_{i}}\otimes\mathcal{I}^{A^{c}_{i}B^{c}_{i}}\right)\right)\left(\rho^{i}\right)\right)$
(13)
$\displaystyle\leq\chi^{2}_{\mathrm{Sep}\left(A:B\right)}\\!\left(\left(\mathcal{N}^{\otimes
n_{i}}\otimes\mathcal{I}^{A^{c}_{i}B^{c}_{i}}\right)\left(\rho^{i}\right)\right)$
(14)
$\displaystyle\leq\left(1-p^{n_{i}}\right)\chi^{2}_{\mathrm{Sep}\left(A:B\right)}\\!\left(\left(\mathcal{S}\otimes\mathcal{I}^{A^{c}_{i}B^{c}_{i}}\right)\left(\rho^{i}\right)\right)$
(15) $\displaystyle\hskip
13.99995pt+p^{n_{i}}\,\chi^{2}_{\mathrm{Sep}\left(A:B\right)}\\!\left(\left(\mathcal{B}^{\otimes
n_{i}}\otimes\mathcal{I}^{A^{c}_{i}B^{c}_{i}}\right)\left(\rho^{i}\right)\right)$
(16)
$\displaystyle=\left(1-p^{n_{i}}\right)\chi^{2}_{\mathrm{Sep}\left(A:B\right)}\\!\left(\left(\mathcal{S}\otimes\mathcal{I}^{A^{c}_{i}B^{c}_{i}}\right)\left(\rho^{i}\right)\right)$
(17)
$\displaystyle\leq\left(1-p^{n}\right)\chi^{2}_{\mathrm{Sep}\left(A:B\right)}\\!\left(\rho^{i}\right)\enspace.$
(18)

Here, the first and the last inequalities follow from monotonicity of
$\chi^{2}_{\mathrm{Sep}\left(A:B\right)}\\!$ under separable quantum channels,
and the second inequality follows from convexity of
$\chi^{2}_{\mathrm{Sep}\left(A:B\right)}\\!$. Moreover, the second equality
holds since $\mathcal{B}$ is entanglement breaking and $\rho^{i}$ is classical
on $A^{c}_{i}B^{c}_{i}$.

Case II: $\mathcal{N}$ is non-unital. By Lemma A.3 in the appendix, for
$\epsilon\in(0,1)$ and $\mathcal{T}=\mathcal{N}^{\otimes n_{i}}$, if
$\chi^{2}_{\mathrm{Sep}\left(A:B\right)}\\!\left(\rho^{i}\right)\geq\epsilon$
then we have

$\chi^{2}_{\mathrm{Sep}\left(A:B\right)}\\!\left(\left(\mathcal{N}^{\otimes
n_{i}}\otimes\mathcal{I}^{A^{c}_{i}B^{c}_{i}}\right)\left(\rho^{i}\right)\right)\leq\left(1-\frac{\epsilon^{2}}{100}\left(1-\eta_{\chi}\left(\mathcal{N}^{\otimes
n_{i}}\right)\right)\right)\chi^{2}_{\mathrm{Sep}\left(A:B\right)}\\!\left(\rho^{i}\right)\enspace.$
(19)

By Eq. (6), we have $\eta_{\chi}\left(\mathcal{N}^{\otimes
n_{i}}\right)\leq\eta_{\mathrm{tr}}\left(\mathcal{N}^{\otimes n_{i}}\right)$.
So we focus on bounding $\eta_{\mathrm{tr}}\left(\mathcal{N}^{\otimes
n_{i}}\right)$. The definition (2) of the trace-norm contraction coefficient
might not be easily computable for all channels, and it is unclear how it
behaves under tensor powers. In order to prove the lemma we prove a general
upper bound on the trace-norm contraction coefficient of a quantum channel.

######  Lemma 3.3.

For any quantum channel
$\mathcal{T}:\mathcal{M}_{d}\rightarrow\mathcal{M}_{d}$, we have

$\eta_{\mathrm{tr}}(\mathcal{T})\leq\sqrt{1-\frac{\lambda^{\mathrm{out}}_{\min}\left(\mathcal{T}^{\dagger}\circ\mathcal{T}\right)}{d^{2}}}\enspace.$
(20)

Here, we used the minimal output eigenvalue
$\lambda^{\mathrm{out}}_{\min}\left(\mathcal{T}^{\dagger}\circ\mathcal{T}\right)=\displaystyle{\min_{\psi,\phi}}\,\left\langle\psi\right|(\mathcal{T}^{\dagger}\circ\mathcal{T})(|\phi\rangle\\!\langle\phi|)\left|\psi\right\rangle$,
where the minimum goes over pure quantum states.

######  Proof 3.4.

In [55] the fidelity
$\mathrm{F}(\rho,\sigma)=\|\sqrt{\rho}\sqrt{\sigma}\|^{2}_{1}$ of quantum
states $\rho$ and $\sigma$ on ${\mathbb{C}}^{d}$ is expressed as a
semidefinite program

$\mathrm{F}(\rho,\sigma)=\max\left\\{\left\langle
v\right|W\left|v\right\rangle\leavevmode\nobreak\ :\leavevmode\nobreak\
W_{AE}\geq 0,\mathrm{Tr}_{E}\left(W_{AE}\right)\leq\rho\right\\},$ (21)

where $v\in{\mathbb{C}}^{d}\otimes{\mathbb{C}}^{d_{E}}$ is a purification of
$\sigma$. Consider the case $\rho=\mathcal{T}(|\psi\rangle\\!\langle\psi|)$
and $\sigma=\mathcal{T}(|\phi\rangle\\!\langle\phi|)$ for pure states
$\left|\psi\right\rangle,\left|\phi\right\rangle\in{\mathbb{C}}^{d}$. Let
$V:{\mathbb{C}}^{d}\rightarrow{\mathbb{C}}^{d}\otimes{\mathbb{C}}^{d_{E}}$
denote a Stinespring dilation of $\mathcal{T}$ such that

$\mathcal{T}(X)=\mathrm{Tr}_{E}\left(VXV^{\dagger}\right)\enspace.$ (22)

Note that
$V\left|\phi\right\rangle\in{\mathbb{C}}^{d}\otimes{\mathbb{C}}^{d_{E}}$ is a
purification of $\sigma$. Choosing
$W=\mathcal{T}(|\psi\rangle\\!\langle\psi|)\otimes\frac{\mathds{1}_{E}}{d_{E}}$
we find that

$\mathrm{F}(\rho,\sigma)\geq\left\langle\phi\right|V^{\dagger}\left(\mathcal{T}(|\psi\rangle\\!\langle\psi|)\otimes\frac{\mathds{1}_{E}}{d_{E}}\right)V\left|\phi\right\rangle=\frac{1}{d_{E}}\left\langle\phi\right|\mathcal{T}^{\dagger}\circ\mathcal{T}\left(|\psi\rangle\\!\langle\psi|\right)\left|\phi\right\rangle\enspace,$
(23)

where we used that the adjoint of $\mathcal{T}$ has the Stinespring dilation

$\mathcal{T}^{\dagger}(X)=V^{\dagger}(X\otimes\mathds{1}_{E})V\enspace.$ (24)

Finally, we can apply the well-known Fuchs-van-de-Graaf inequality relating
the trace norm and the fidelity
($\|\rho-\sigma\|_{1}\leq\sqrt{1-\mathrm{F}(\rho,\sigma)}$ for any quantum
states $\rho,\sigma$) to conclude

$\displaystyle\eta_{\text{tr}}(\mathcal{T})$
$\displaystyle=\frac{1}{2}\max_{\psi\perp\phi}\|\mathcal{T}(|\psi\rangle\\!\langle\psi|-|\phi\rangle\\!\langle\phi|)\|_{1}$
$\displaystyle\leq\max_{\psi\perp\phi}\sqrt{1-\mathrm{F}(\mathcal{T}(|\psi\rangle\\!\langle\psi|),\mathcal{T}(|\phi\rangle\\!\langle\phi|))}$
$\displaystyle\leq\max_{\psi\perp\phi}\sqrt{1-\frac{1}{d^{2}}\left\langle\phi\right|\left(\mathcal{T}^{\dagger}\circ\mathcal{T}\right)\left(|\psi\rangle\\!\langle\psi|\right)\left|\phi\right\rangle}$
$\displaystyle\leq\sqrt{1-\frac{\lambda^{\mathrm{out}}_{\min}\left(\mathcal{T}^{\dagger}\circ\mathcal{T}\right)}{d^{2}}}\enspace,$

where we used that $d_{E}\leq d^{2}$ for any quantum channel
$\mathcal{T}:\mathcal{M}_{d}\rightarrow\mathcal{M}_{d}$.

Computing
$\lambda^{\mathrm{out}}_{\min}\left(\mathcal{T}^{\dagger}\circ\mathcal{T}\right)$
might be difficult in general, but for our purposes an easy lower bound
suffices. This bound also behaves nicely under tensor product of channels; an
important property which we use below. For
$\left|\phi\right\rangle=\sum_{i\in[d]}\alpha_{i}\left|i\right\rangle$, let
$\left|\overline{\phi}\right\rangle=\sum_{i\in[d]}\overline{\alpha_{i}}\left|i\right\rangle$,
where $\overline{\alpha_{i}}$ denotes the complex conjugate of $\alpha_{i}$.
Then we have

$\lambda^{\mathrm{out}}_{\min}\left(\mathcal{T}^{\dagger}\circ\mathcal{T}\right)=\min_{\psi,\phi}\,\left\langle\psi\right|(\mathcal{T}^{\dagger}\circ\mathcal{T})(|\phi\rangle\\!\langle\phi|)\left|\psi\right\rangle=\min_{\psi,\phi}\,\left\langle\psi\otimes\overline{\phi}\right|C_{\mathcal{T}^{\dagger}\circ\mathcal{T}}\left|\psi\otimes\overline{\phi}\right\rangle\geq\lambda_{\min}\left(C_{\mathcal{T}^{\dagger}\circ\mathcal{T}}\right).$
(25)

We are now in position to present the proof of the case where $\mathcal{N}$ is
a non-unital qubit channel. We may write

$\mathcal{N}=(1-q)\,\mathcal{M}^{\prime}+q\,\mathcal{M},$ (26)

where $q\in(0,1]$ and $\mathcal{M}$ is a non-unital extreme point of the set
of qubit channels. By the characterization of extreme points of the set of
quantum channels (see preliminaries or [18]), the non-unital extremal qubit
channel $\mathcal{M}$ admits a Kraus decomposition with two Kraus operators
$K_{1},K_{2}:{\mathbb{C}}^{2}\rightarrow{\mathbb{C}}^{2}$ such that the
operators
$K_{1}^{\dagger}K_{1},K_{1}^{\dagger}K_{2},K_{2}^{\dagger}K_{1},K_{2}^{\dagger}K_{2}$
are linearly independent. Since these operators are exactly the Kraus
operators of the completely positive map
$\mathcal{M}^{\dagger}\circ\mathcal{M}$, we conclude that the Choi matrix
$C_{\mathcal{M}^{\dagger}\circ\mathcal{M}}$ is full-rank and that

$\lambda_{\min}\left(C_{\mathcal{N}^{\dagger}\circ\mathcal{N}}\right)\geq
q^{2}\lambda_{\min}\left(C_{\mathcal{M}^{\dagger}\circ\mathcal{M}}\right)>0.$

Setting $\mathcal{T}=\mathcal{N}^{\otimes n_{i}}$ and using (25) and Lemma
3.3, we have

$\displaystyle\eta_{\text{tr}}(\mathcal{T})$
$\displaystyle\leq\sqrt{1-\frac{\lambda_{\min}\left(C_{\mathcal{T}^{\dagger}\circ\mathcal{T}}\right)}{2^{2n_{i}}}}\\!=\\!\sqrt{1-\frac{\lambda_{\min}\left(\left(C_{\mathcal{N}^{\dagger}\circ\mathcal{N}}\right)^{\otimes
n_{i}}\right)}{2^{2n_{i}}}}\\!=\\!\sqrt{1-\left(\frac{\lambda_{\min}\left(C_{\mathcal{N}^{\dagger}\circ\mathcal{N}}\right)}{4}\right)^{n_{i}}}$
$\displaystyle\leq\sqrt{1-\left(\frac{q^{2}\lambda_{\min}\left(C_{\mathcal{M}^{\dagger}\circ\mathcal{M}}\right)}{4}\right)^{n_{i}}}\leq
1-\left(\frac{q^{2}\lambda_{\min}\left(C_{\mathcal{M}^{\dagger}\circ\mathcal{M}}\right)}{8}\right)^{n_{i}}\enspace.$
(27)

Combining Eqs. (19) and (27) and fixing $\epsilon=1/16$, for
$p=\left(q^{2}/204800\right)\lambda_{\min}\left(C_{\mathcal{M}^{\dagger}\otimes\mathcal{M}}\right)>0$,
we have

$\displaystyle\chi^{2}_{\mathrm{Sep}\left(A:B\right)}\\!\left(\rho^{i+1}\right)$
$\displaystyle=\chi^{2}_{\mathrm{Sep}\left(A:B\right)}\\!\left(\left(\mathcal{L}_{i+1}\circ\left(\mathcal{N}^{\otimes
n_{i}}\otimes\mathcal{I}^{A^{c}_{i}B^{c}_{i}}\right)\right)\left(\rho^{i}\right)\right)$
$\displaystyle\leq\chi^{2}_{\mathrm{Sep}\left(A:B\right)}\\!\left(\left(\mathcal{N}^{\otimes
n_{i}}\otimes\mathcal{I}^{A^{c}_{i}B^{c}_{i}}\right)\left(\rho^{i}\right)\right)$
$\displaystyle\leq\left(1-p^{n_{i}}\right)\chi^{2}_{\mathrm{Sep}\left(A:B\right)}\\!\left(\rho^{i}\right)\leq\left(1-p^{n}\right)\chi^{2}_{\mathrm{Sep}\left(A:B\right)}\\!\left(\rho^{i}\right)\enspace.$

Recall the setup of Theorem 1.1: Let $C$ be an arbitrary quantum circuit in
which the gates are allowed to be arbitrary quantum channels acting on several
qubits. A supply of fresh ancilla qubits is available and the number of
ancillas in $C$ in each time step is restricted by the circuit width. We will
now consider two parallel instances of the circuit and apply them to an
entangled state. If the parallel instances of the circuits are affected by the
$\mathrm{i.i.d.}_{\mathcal{N}}$ error model for a non-unitary qubit channel
$\mathcal{N}$, then they cannot keep entanglement for arbitrary long time.
Theorem 1.1 will then follow from the following lemma:

######  Lemma 3.5.

[56, Theorem 3.56] Let
$\mathcal{I}_{d}:\mathcal{M}_{d}\rightarrow\mathcal{M}_{d}$ be the identity
channel. Let $\mathcal{T}:\mathcal{M}_{d}\rightarrow\mathcal{M}_{d}$ be a
quantum channel satisfying
$\left\|\mathcal{T}-\mathcal{I}_{d}\right\|_{1}\leq\epsilon$, for some
$\epsilon\in[0,2]$. Then for any $d^{\prime}\geq 1$, we have

$\left\|\mathcal{T}\otimes\mathcal{I}_{d^{\prime}}-\mathcal{I}_{d}\otimes\mathcal{I}_{d^{\prime}}\right\|_{1}\leq\sqrt{2\epsilon}.$

This in particular implies that $\left\|\mathcal{T}^{\otimes
2}-\mathcal{I}_{d}^{\otimes 2}\right\|_{1}\leq
2\left\|\mathcal{T}\otimes\mathcal{I}_{d}-\mathcal{I}_{d}\otimes\mathcal{I}_{d}\right\|_{1}\leq
2\sqrt{2\epsilon}$.

Combining Lemmas 3.1 and 3.5, we have:

######  Theorem 1.1 (Restated).

Let $\mathcal{I}$ denote the qubit identity channel and $\mathcal{N}$ be a
non-unitary qubit channel. Then there exists a constant $p\in(0,1]$ only
depending on $\mathcal{N}$ such that the following holds: Let $C$ be an
arbitrary circuit of length $T$ and width $n$ such that
$T\geq\left(2/p\right)^{2n}$. Then for any pair of ideal encoding and decoding
maps $\mathcal{E}$ and $\mathcal{D}$ (of appropriate input and output
dimensions), we have

$\left\|\mathcal{D}\circ\mathrm{i.i.d.}_{\mathcal{N}}\left(C\right)\circ\mathcal{E}-\mathcal{I}\right\|_{1}\geq\epsilon_{0}\enspace,$

for some universal constant $\epsilon_{0}\geq 1/128$.

######  Proof 1.2.

Consider two parallel instances of the circuit $C$. By definition of the
$\mathrm{i.i.d.}$ error model, we have
$\mathrm{i.i.d.}_{\mathcal{N}}\left(C^{\otimes
2}\right)=\left(\mathrm{i.i.d.}_{\mathcal{N}}\left(C\right)\right)^{\otimes
2}$. Note that $C^{\otimes 2}$ is a circuit of width $2n$ and length $T$
satisfying the requirements of Lemma 3.1, with $A$ being the registers of the
first copy of $C$ and $B$ being the registers of the second copy. By Lemma A.1
in the appendix, for any input state $\rho^{0}$, we have
$\chi^{2}_{\mathrm{Sep}\left(A:B\right)}\\!\left(\rho^{0}\right)\leq 2^{2n}$.
Therefore, by Lemma 3.1, for $T\geq(2/p)^{2n}$, it is easy to see that
$\chi^{2}_{\mathrm{Sep}\left(A:B\right)}\\!\left(\left(\mathrm{i.i.d.}_{\mathcal{N}}\left(C\right)\right)^{\otimes
2}(\rho^{0})\right)\leq 1/16$. In particular, for any encoding map
$\mathcal{E}$ and any 2-qubit state $\sigma$, we have
$\chi^{2}_{\mathrm{Sep}\left(A:B\right)}\\!\left(\left(\left(\mathrm{i.i.d.}_{\mathcal{N}}\left(C\right)\right)^{\otimes
2}\circ\mathcal{E}^{\otimes 2}\right)(\sigma)\right)\leq 1/16$. For any
decoding map $\mathcal{D}$, since $\mathcal{D}^{\otimes 2}$ is a separable
channel, we have

$\chi^{2}_{\mathrm{Sep}\left(A:B\right)}\\!\left(\left(\mathcal{D}^{\otimes
2}\circ\left(\mathrm{i.i.d.}_{\mathcal{N}}\left(C\right)\right)^{\otimes
2}\circ\mathcal{E}^{\otimes
2}\right)(\sigma)\right)\leq\chi^{2}_{\mathrm{Sep}\left(A:B\right)}\\!\left(\left(\mathrm{i.i.d.}_{\mathcal{N}}\left(C\right)\right)^{\otimes
2}\circ\mathcal{E}^{\otimes 2}\right)(\sigma)\leq\frac{1}{16}.$

Let
$\mathcal{M}\coloneqq\mathcal{D}\circ\mathrm{i.i.d.}_{\mathcal{N}}\left(C\right)\circ\mathcal{E}$.
Then we have

$\left\|\mathcal{M}^{\otimes 2}-\mathcal{I}^{\otimes
2}\right\|_{1}=\sup_{\sigma}\left\|\mathcal{M}^{\otimes
2}(\sigma)-\sigma\right\|_{1}\geq\sup_{\sigma}\;\left(d^{1}_{\mathrm{Sep}\left(A:B\right)}\\!(\sigma)-d^{1}_{\mathrm{Sep}\left(A:B\right)}\\!(\mathcal{M}^{\otimes
2}(\sigma))\right)\enspace,$

where $d^{1}_{\mathrm{Sep}\left(A:B\right)}\\!$ denotes the 1-norm distance
from the set of separable states $\mathrm{Sep}\left(A:B\right)$ defined for a
quantum state $\tau_{AB}$ as
$d^{1}_{\mathrm{Sep}\left(A:B\right)}\\!\left(\tau_{AB}\right)\coloneqq\min_{\zeta\in\mathrm{Sep}\left(A:B\right)}\left\|\tau-\zeta\right\|_{1}$.
For $\sigma$ equal to the maximally entangled state, it is straightforward to
see that $d^{1}_{\mathrm{Sep}\left(A:B\right)}\\!(\sigma)\geq 1/2$. Moreover,
by Eq. (4), we have
$d^{1}_{\mathrm{Sep}\left(A:B\right)}\\!\left(\mathcal{M}^{\otimes
2}(\sigma)\right)\leq\sqrt{1/16}=1/4$, for any 2-qubit state $\sigma$. Hence,
we have $\left\|\mathcal{M}^{\otimes 2}-\mathcal{I}^{\otimes
2}\right\|_{1}\geq 1/4$. The statement of the theorem follows from Lemma 3.5
for $\epsilon_{0}\geq 1/128$.

We should point out a connection between our proof of Theorem 1.1 (including
Lemma 3.3) and the zero-error classical capacity of a quantum channel [36, 8].
The zero-error classical capacity $C_{0}(\mathcal{N})$ of a quantum channel
$\mathcal{N}$ arises as the regularization of the logarithm of the (quantum)
_independence number_ $\alpha(\mathcal{N})$ which equals the maximal number of
orthogonal pure states that are mapped to orthogonal outputs by the channel
$\mathcal{N}$ (see [23] for details). It is clear from this definition that
$\alpha(\mathcal{N})=1$ if and only if $\eta_{\text{tr}}(\mathcal{N})<1$.
Qualitatively, Theorem 1.1 says that a finite-size quantum memory affected by
a non-unitary qubit noise channel $\mathcal{N}$ cannot store information for
arbitrary long times. Using our proof technique, this statement can be
generalized beyond qubit noise channels as follows: If $\mathcal{N}$ arises as
a non-trivial convex combination with an entanglement breaking quantum channel
or satisfies $\alpha(\mathcal{N}^{\otimes k})=1$, for some $k\in{\mathbb{N}}$,
then no quantum memory of width $k$ affected by noise $\mathcal{N}$ can store
information for arbitrary long times. In particular, if
$C_{0}(\mathcal{N})=0$, then no finite width will allow for storing
information for arbitrary long times. The zero-error classical capacity can be
superactivated in the sense that there are quantum channels $\mathcal{N}$ for
which $\alpha(\mathcal{N})=1$ but $\alpha(\mathcal{N}^{\otimes k})>1$ for some
$k\in{\mathbb{N}}$ (see [22, 19]), and it would be interesting to study the
maximal storage times of quantum memories for such examples. Our techniques in
Lemma 3.3 can be used to show more generally that such a superactivation does
not happen for channels of maximal Kraus rank. We remark that the
impossibility of superactivation of the zero-error classical capacity has been
shown previously in [38, 45], for qubit channels. However, unlike Lemma 3.3
these results did not give any quantitative estimate on the trace-norm
contraction coefficient and therefore they do not imply our main quantitative
bound.

##  4 Implications for fault-tolerant quantum computation

###  4.1 A high-level definition of fault tolerance

A _quantum fault tolerance scheme_ is a circuit encoding $FT$ which maps any
ideal quantum circuit $C$ to a family of its _fault-tolerant simulation_
circuits $FT^{\ell}(C)\coloneqq FT\left(\ell,C\right)$. As defined formally
below, the circuit encoding is designed to allow the implementation of the
circuit $C$ even with faulty components.

Let $T=Length(C)$ denote the length of the circuit $C$. We denote by
$n_{t}(C)$ the number of (logical) qubits in the circuit $C$ after
$t\in\\{0,1,\ldots,T\\}$ time steps and use $n=Width(C)$ to denote the width
of $C$, i.e., $n=\max_{t}n_{t}(C)$. Similarly, let
$n^{\prime}=Width(FT^{\ell}(C))$ be the width, i.e, the maximum number of
(physical) qubits and $T^{\prime}=Length\left(FT^{\ell}(C)\right)$ be the
length of $FT^{\ell}(C)$. Note that it is important to distinguish between the
classical and quantum subsystems, as in our circuit model only quantum
subsystems are subject to the noise. For the input circuit $C$, we may assume
without loss of generality that there are no classical inputs, as we can
consider the circuit obtained by conditioning on the state of the classical
input systems.

######  Definition 4.8.

A circuit encoding $FT$ is a fault tolerance scheme against an error model
$\mathscr{E}$ if there exist a family of ideal encoding maps
$\left\\{\mathcal{E}^{\ell}_{n}\right\\}$ and decoding maps
$\left\\{\mathcal{D}^{\ell}_{n}\right\\}$ only depending on $FT$ such that for
every $\epsilon\in(0,2]$ and every quantum circuit $C$, there exists
$\ell_{0}$ such that

$\left\|\mathcal{D}^{\ell}_{n_{T}(C)}\circ\mathscr{E}\left(FT^{\ell}(C)\right)\circ\mathcal{E}^{\ell}_{n_{0}(C)}-C\right\|_{1}\leq\epsilon\,,\quad\forall\ell\geq\ell_{0}\enspace.$
(28)

In the above definition, if the input Hilbert space of $C$ is trivial (e.g.,
if $C$ is a circuit for classical computation), then for every $\ell$, the
circuit $FT^{\ell}(C)$ is also naturally defined to have no input, i.e.,
$\mathcal{E}^{\ell}_{0}$ is fixed to be the identity map on ${\mathbb{C}}$.

Formal definitions of fault tolerance are indeed invaluable in studying
general properties and limitations of fault tolerance schemes. We emphasize
that Definition 4.8 is far from capturing all the different aspects of quantum
fault tolerance. Indeed, there are several different ways of defining fault
tolerance, each with their own advantages and limitations. Here, we aim at
providing a high-level definition with minimal assumptions which is easy to
work with and applies to most known and potential schemes. Below we discuss
some examples of known fault tolerance protocols and explain how they fit into
our definition.

Perhaps the most well-known family of fault tolerance schemes are the schemes
based on concatenation. These schemes typically involve a quantum error
correcting code $Q$ together with fault-tolerant gadgets for the elementary
locations, i.e., state preparation gadgets, gate gadgets for a universal set
of gates, storage gadgets, and measurement gadgets, in addition to error
correction gadgets. For a quantum circuit $C$, the circuit $FT(C)$ is obtained
by replacing the locations in $C$ by the corresponding gadgets, interlaced
with error correction gadgets on the quantum registers, which now correspond
to qubits of $C$ encoded in $Q$. The gadgets are designed to satisfy some
fault tolerance properties, such that they not only act correctly in the
absence of faults, but also control the propagation of errors if the number of
errors is not too high. For $\ell\geq 1$, let
$FT^{\ell}(C)=FT\left(FT^{\ell-1}(C)\right)$, where we define $FT^{0}(C)=C$.
For any such scheme, assuming the distance between the noise channel
$\mathcal{N}$ and the identity channel is below a threshold, the output state
of $\mathrm{i.i.d.}_{\mathcal{N}}\left(FT^{\ell}(C)\right)$ is arbitrarily
close to an encoded version of the output state of $C$ for a sufficiently
large $\ell$ [3].

Fault tolerance schemes based on topological codes are another family of
schemes which have a threshold noise level below which arbitrarily long
quantum computations are possible [20, 53, 41]. For the surface code [32] (and
more generally, low-density parity check codes), a single syndrome bit
measurement only involves a few neighboring qubits. This property allows error
correction to be performed more efficiently for these codes [50, 14].
Moreover, topological properties of surface codes allow for simpler and more
efficient implementation of fault-tolerant gadgets for elementary locations
[20, 17, 29, 13]. This in turn results in a desirable scaling of the overhead
and reduction of the logical error rate when the size of the underlying
surface code is increased. In this case, the index $\ell$ in definition 4.8
corresponds to the size of the surface code.

###  1.2 A lower bound on the space overhead for fault tolerance

For a fault-tolerant simulation circuit $FT^{\ell}(C)$, the ratios
$n^{\prime}/n$ and $T^{\prime}/T$ are respectively called the space overhead
and the time overhead of $FT^{\ell}(C)$. We view a fault tolerance scheme as a
compiler which reads the instructions given by the input circuit $C$ and
encodes them into the fault-tolerant simulation circuits $FT^{\ell}(C)$,
without optimizing the circuit $C$. This should be true even if the input
circuit involves unnecessary steps that are completely independent of the
output of the circuit. While in Eq. (28), we only require the circuit
$FT^{\ell}(C)$ to (approximately) implement the _overall_ logical operation of
the circuit $C$ on a code space, this “faithfulness” property is in fact
necessary to have a meaningful notion of overhead for a fault tolerance
scheme. As a result of this property, we may assume $n^{\prime}\geq n$ and
$T^{\prime}\geq T$, for any input circuit $C$ and any fault-tolerant
simulation circuit $FT^{\ell}(C)$. The faithfulness property also rules out
circuit encodings which map quantum circuits for classical computation to
fully classical (hence, noiseless) circuits.

Our result of the previous section can be used to prove a lower bound on the
space overhead of any universal fault tolerance scheme satisfying Definition
4.8 and the natural requirement that the overhead is at least $1$ for any
fault-tolerant simulation circuit.

######  Theorem 1.2 (Restated).

Let $\mathcal{N}$ be a non-unitary qubit channel. For any fault tolerance
scheme against the $\mathrm{i.i.d.}_{\mathcal{N}}$ noise model, the number of
physical qubits is at least

$\max\left\\{\mathrm{Q}(\mathcal{N})^{-1}n,\alpha_{\mathcal{N}}\log
T\right\\}\enspace,$

for circuits of length $T$ and width $n$, and any constant accuracy
$\epsilon\leq 1/128$. Here, $\mathrm{Q}(\mathcal{N})$ denotes the quantum
capacity of $\mathcal{N}$ and $\alpha_{\mathcal{N}}=\frac{1}{2\log 2/p}$,
where $p\in(0,1]$ is a constant only depending on the channel $\mathcal{N}$.
In particular, fault tolerance is not possible even for a single time step if
$\mathcal{N}$ has zero quantum capacity or the space overhead is strictly less
than $\mathrm{Q}(\mathcal{N})^{-1}$.

######  Proof 1.3.

Let $C$ be a quantum circuit of length $T$ on $n$ qubits in which in every
time step an identity gate is applied on every qubit. Consider a fault
tolerance scheme $FT$ satisfying Definition 4.8. For any constant
$\epsilon\in(0,1/128)$, let $C^{\prime}(\epsilon)$ be a fault-tolerant
encoding of $C$ given by $FT$ satisfying Eq. (28), for a pair of encoding and
decoding maps $\left(\mathcal{E}_{\epsilon},\mathcal{D}_{\epsilon}\right)$.
Then by Theorem 1.1, the width of $C^{\prime}(\epsilon)$ is bounded in terms
of its depth as $n^{\prime}\geq\frac{\log T^{\prime}}{2\log 2/p}$. Since
$T^{\prime}\geq T$ the lower bound of $\alpha_{\mathcal{N}}\log T$ follows for
$\alpha_{\mathcal{N}}=\frac{1}{2\log 2/p}$.

For the second lower bound, consider the quantum channel obtained by removing
the last layer of noise from
$\mathrm{i.i.d.}_{\mathcal{N}}\left(C^{\prime}(\epsilon)\right)$ and let
$\mathcal{E}^{\prime}_{\epsilon}$ denote the composition of
$\mathcal{E}_{\epsilon}$ with this channel. Then for the family of encoding
and decoding maps
$\left(\mathcal{E}^{\prime}_{\epsilon},\mathcal{D}_{\epsilon}\right)$, the
overall channel
$\mathcal{T}_{\epsilon}=\mathcal{D}_{\epsilon}\circ\mathcal{N}^{\otimes
n_{\epsilon}}\circ\mathcal{E}^{\prime}_{\epsilon}$ approximates the qubit
identity channel up to arbitrarily high accuracy. But continuity of the
quantum capacity [35] implies that, for sufficiently small $\epsilon$, the
channel $\mathcal{T}_{\epsilon}$ (and hence $\mathcal{N}$) has a non-zero
quantum capacity. Moreover, the existence of the family of encoding and
decoding maps
$\left(\mathcal{E}^{\prime}_{\epsilon},\mathcal{D}_{\epsilon}\right)$ implies
that, for the channel $\mathcal{N}$, the inverse of the space overhead is an
$\epsilon$-achievable communication rate for any arbitrarily small constant
$\epsilon$ (See Definition 2.1). Therefore, by the definition of quantum
capacity, we have $n^{\prime}\geq\frac{1}{\mathrm{Q}(\mathcal{N})}n$. Since
assistance by noiseless forward classical communication does not increase the
quantum capacity of a channels [7, 10], the lower bound of
$\mathrm{Q}(\mathcal{N})^{-1}n$ is still valid in our circuit model with free
and noiseless classical computation. Finally, note that the above argument is
valid even if there is a single time step of noisy operations. Therefore,
fault tolerance is not achievable even for a single time step if $\mathcal{N}$
has zero quantum capacity, or with an space overhead strictly less than
$1/\mathrm{Q}(\mathcal{N})$.

## References

  * [1] Dorit Aharonov and Michael Ben-Or.  Fault-tolerant quantum computation with constant error.  In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, STOC ’97, pages 176–188, New York, NY, USA, 1997. Association for Computing Machinery.  doi:10.1145/258533.258579.
  * [2] Dorit Aharonov, Michael Ben-Or, Russell Impagliazzo, and Noam Nisan.  Limitations of noisy reversible computation.  Technical Report arXiv:9611028 [quant-ph], arXiv.org, https://arxiv.org/abs/quant-ph/9611028, 1996.
  * [3] Panos Aliferis, Daniel Gottesman, and John Preskill.  Quantum accuracy threshold for concatenated distance-3 codes.  Quantum Info. Comput., 6(2):97–165, March 2006.
  * [4] Panos Aliferis, Daniel Gottesman, and John Preskill.  Accuracy threshold for postselected quantum computation.  Quantum Info. Comput., 8(3):181–244, March 2008.
  * [5] Panos Aliferis and John Preskill.  Fault-tolerant quantum computation against biased noise.  Phys. Rev. A, 78:052331, Nov 2008.  URL: https://link.aps.org/doi/10.1103/PhysRevA.78.052331, doi:10.1103/PhysRevA.78.052331.
  * [6] Panos Aliferis and John Preskill.  Fibonacci scheme for fault-tolerant quantum computation.  Phys. Rev. A, 79:012332, Jan 2009.  URL: https://link.aps.org/doi/10.1103/PhysRevA.79.012332, doi:10.1103/PhysRevA.79.012332.
  * [7] Howard Barnum, Emanuel Knill, and Michael A. Nielsen.  On quantum fidelities and channel capacities.  IEEE Transactions on Information Theory, 46(4):1317–1329, Jul 2000\.  URL: http://dx.doi.org/10.1109/18.850671, doi:10.1109/18.850671.
  * [8] Salman Beigi and Peter W Shor.  On the complexity of computing zero-error and holevo capacity of quantum channels.  arXiv preprint arXiv:0709.2090, 2007.
  * [9] Michael Ben-Or, Daniel Gottesman, and Avinatan Hassidim.  Quantum refrigerator.  arXiv preprint arXiv:1301.1995, 2013.
  * [10] Charles H. Bennett, David P. DiVincenzo, John A. Smolin, and William K. Wootters.  Mixed-state entanglement and quantum error correction.  Physical Review A, 54(5):3824–3851, Nov 1996.  URL: http://dx.doi.org/10.1103/PhysRevA.54.3824, doi:10.1103/physreva.54.3824.
  * [11] Mary Beth Ruskai, Stanislaw Szarek, and Elisabeth Werner.  An analysis of completely-positive trace-preserving maps on m2.  Linear Algebra and its Applications, 347(1):159–187, 2002.  URL: https://www.sciencedirect.com/science/article/pii/S002437950100547X, doi:https://doi.org/10.1016/S0024-3795(01)00547-X.
  * [12] Peter Brooks and John Preskill.  Fault-tolerant quantum computation with asymmetric bacon-shor codes.  Phys. Rev. A, 87:032310, Mar 2013.  URL: https://link.aps.org/doi/10.1103/PhysRevA.87.032310, doi:10.1103/PhysRevA.87.032310.
  * [13] Benjamin J. Brown, Katharina Laubscher, Markus S. Kesselring, and James R. Wootton.  Poking holes and cutting corners to achieve clifford gates with the surface code.  Phys. Rev. X, 7:021029, May 2017.  URL: https://link.aps.org/doi/10.1103/PhysRevX.7.021029, doi:10.1103/PhysRevX.7.021029.
  * [14] Benjamin J. Brown, Daniel Loss, Jiannis K. Pachos, Chris N. Self, and James R. Wootton.  Quantum memories at finite temperature.  Rev. Mod. Phys., 88:045005, Nov 2016.  URL: https://link.aps.org/doi/10.1103/RevModPhys.88.045005, doi:10.1103/RevModPhys.88.045005.
  * [15] Dagmar Bruss, David P. DiVincenzo, Artur Ekert, Christopher A. Fuchs, Chiara Macchiavello, and John A. Smolin.  Optimal universal and state-dependent quantum cloning.  Phys. Rev. A, 57:2368–2378, Apr 1998.  URL: https://link.aps.org/doi/10.1103/PhysRevA.57.2368, doi:10.1103/PhysRevA.57.2368.
  * [16] Harry Buhrman, Richard Cleve, Monique Laurent, Noah Linden, Alexander Schrijver, and Falk Unger.  New limits on fault-tolerant quantum computation.  In 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06), pages 411–419, 2006.  doi:10.1109/FOCS.2006.50.
  * [17] Earl T. Campbell, Barbara M. Terhal, and Christophe Vuillot.  Roads towards fault-tolerant universal quantum computation.  Nature, 549(7671):172–179, Sep 2017.  URL: http://dx.doi.org/10.1038/nature23460, doi:10.1038/nature23460.
  * [18] Man-Duen Choi.  Completely positive linear maps on complex matrices.  Linear Algebra and its Applications, 10(3):285–290, 1975.  URL: https://www.sciencedirect.com/science/article/pii/0024379575900750, doi:https://doi.org/10.1016/0024-3795(75)90075-0.
  * [19] Toby S Cubitt, Jianxin Chen, and Aram W Harrow.  Superactivation of the asymptotic zero-error classical capacity of a quantum channel.  IEEE transactions on information theory, 57(12):8114–8126, 2011\.  doi:10.1109/TIT.2011.2169109.
  * [20] Eric Dennis, Alexei Kitaev, Andrew Landahl, and John Preskill.  Topological quantum memory.  Journal of Mathematical Physics, 43(9):4452–4505, 2002.  arXiv:https://doi.org/10.1063/1.1499754, doi:10.1063/1.1499754.
  * [21] Roland L. Dobrushin.  Central limit theorem for nonstationary markov chains. i.  Theory of Probability & Its Applications, 1(1):65–80, 1956.  arXiv:https://doi.org/10.1137/1101006, doi:10.1137/1101006.
  * [22] Runyao Duan.  Super-activation of zero-error capacity of noisy quantum channels.  arXiv preprint arXiv:0906.2527, 2009.
  * [23] Runyao Duan, Simone Severini, and Andreas Winter.  Zero-error communication via quantum channels, noncommutative graphs, and a quantum lovász number.  IEEE Transactions on Information Theory, 59(2):1164–1174, 2012\.  doi:10.1109/TIT.2012.2221677.
  * [24] William S. Evans and Leonard J. Schulman.  Signal propagation and noisy circuits.  IEEE Transactions on Information Theory, 45(7):2367–2373, 1999\.  doi:10.1109/18.796377.
  * [25] William S. Evans and Leonard J. Schulman.  On the maximum tolerable noise of k-input gates for reliable computation by formulas.  IEEE Transactions on Information Theory, 49(11):3094–3098, 2003\.  doi:10.1109/TIT.2003.818405.
  * [26] Omar Fawzi, Antoine Grospellier, and Anthony Leverrier.  Constant overhead quantum fault-tolerance with quantum expander codes.  In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 743–754. IEEE, 2018.
  * [27] Daniel Gottesman.  Fault-tolerant quantum computation with constant overhead.  Quantum Info. Comput., 14(15-16):1338–1372, November 2014.
  * [28] Jérémie Guillaud and Mazyar Mirrahimi.  Repetition cat qubits for fault-tolerant quantum computation.  Phys. Rev. X, 9:041053, Dec 2019.  URL: https://link.aps.org/doi/10.1103/PhysRevX.9.041053, doi:10.1103/PhysRevX.9.041053.
  * [29] Clare Horsman, Austin G Fowler, Simon Devitt, and Rodney Van Meter.  Surface code quantum computing by lattice surgery.  New Journal of Physics, 14(12):123011, dec 2012.  doi:10.1088/1367-2630/14/12/123011.
  * [30] Julia Kempe, Oded Regev, Falk Uunger, and Ronald de Wolf.  Upper bounds on the noise threshold for fault-tolerant quantum computing.  Quantum Info. Comput., 10(5):361–376, May 2010.
  * [31] Alexey Yu Kitaev.  Quantum computations: algorithms and error correction.  Russian Mathematical Surveys, 52(6):1191–1249, dec 1997.  doi:10.1070/rm1997v052n06abeh002155.
  * [32] Alexey Yu. Kitaev.  Fault-tolerant quantum computation by anyons.  Annals of Physics, 303(1):2–30, 2003.  URL: https://www.sciencedirect.com/science/article/pii/S0003491602000180, doi:https://doi.org/10.1016/S0003-4916(02)00018-0.
  * [33] Emanuel Knill.  Quantum computing with realistically noisy devices.  Nature, 434(7029):39–44, Mar 2005.  URL: http://dx.doi.org/10.1038/nature03350, doi:10.1038/nature03350.
  * [34] Emanuel Knill, Raymond Laflamme, and Wojciech H. Zurek.  Resilient quantum computation: error models and thresholds.  Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences, 454(1969):365–384, Jan 1998\.  URL: http://dx.doi.org/10.1098/rspa.1998.0166, doi:10.1098/rspa.1998.0166.
  * [35] Debbie Leung and Graeme Smith.  Continuity of quantum channel capacities.  Communications in Mathematical Physics, 292(1):201–215, May 2009\.  URL: http://dx.doi.org/10.1007/s00220-009-0833-1, doi:10.1007/s00220-009-0833-1.
  * [36] Rex AC Medeiros and Francisco M De Assis.  Quantum zero-error capacity.  International Journal of Quantum Information, 3(01):135–139, 2005\.  doi:10.1142/S0219749905000682.
  * [37] Alexander Müller-Hermes, Daniel Stilck França, and Michael M Wolf.  Relative entropy convergence for depolarizing channels.  Journal of Mathematical Physics, 57(2):022202, 2016.  doi:10.1063/1.4939560.
  * [38] Jeonghoon Park and Soojoon Lee.  Zero-error classical capacity of qubit channels cannot be superactivated.  Physical Review A, 85(5):052321, 2012.  doi:10.1103/PhysRevA.85.052321.
  * [39] Stefano Pirandola.  End-to-end capacities of a quantum communication network.  Communications Physics, 2(1):51, May 2019.  doi:10.1038/s42005-019-0147-3.
  * [40] Maxim Raginsky.  Strictly contractive quantum channels and physically realizable quantum computers.  Phys. Rev. A, 65:032306, Feb 2002.  URL: https://link.aps.org/doi/10.1103/PhysRevA.65.032306, doi:10.1103/PhysRevA.65.032306.
  * [41] Robert Raussendorf and Jim Harrington.  Fault-tolerant quantum computation with high threshold in two dimensions.  Phys. Rev. Lett., 98:190504, May 2007.  URL: https://link.aps.org/doi/10.1103/PhysRevLett.98.190504, doi:10.1103/PhysRevLett.98.190504.
  * [42] Alexander A. Razborov.  An upper bound on the threshold quantum decoherence rate.  Quantum Info. Comput., 4(3):222–228, May 2004.
  * [43] Mary Beth Ruskai.  Beyond strong subadditivity? improved bounds on the contraction of generalized relative entropy.  Reviews in Mathematical Physics, 6(05a):1147–1161, 1994.  doi:10.1142/s0129055x94000407.
  * [44] Pradeep Kiran Sarvepalli, Andreas Klappenecker, and Martin Rötteler.  Asymmetric quantum codes: constructions, bounds and performance.  Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 465(2105):1645–1672, 2009.  URL: https://royalsocietypublishing.org/doi/abs/10.1098/rspa.2008.0439, arXiv:https://royalsocietypublishing.org/doi/pdf/10.1098/rspa.2008.0439, doi:10.1098/rspa.2008.0439.
  * [45] Maksim Shirokov and Tatiana Shulman.  On superactivation of zero-error capacities and reversibility of a quantum channel.  Communications in Mathematical Physics, 335(3):1159–1179, 2015\.  doi:10.1007/s00220-015-2345-5.
  * [46] Peter W. Shor.  Scheme for reducing decoherence in quantum computer memory.  Phys. Rev. A, 52:R2493–R2496, Oct 1995.  URL: https://link.aps.org/doi/10.1103/PhysRevA.52.R2493, doi:10.1103/PhysRevA.52.R2493.
  * [47] Peter W. Shor.  Fault-tolerant quantum computation.  In Proceedings of 37th Conference on Foundations of Computer Science, pages 56–65, 1996.  doi:10.1109/SFCS.1996.548464.
  * [48] Andrew M. Steane.  Error correcting codes in quantum theory.  Phys. Rev. Lett., 77:793–797, Jul 1996.  URL: https://link.aps.org/doi/10.1103/PhysRevLett.77.793, doi:10.1103/PhysRevLett.77.793.
  * [49] Kristan Temme, Michael J. Kastoryano, Mary B. Ruskai, Michael M. Wolf, and Frank Verstraete.  The $\chi^{2}$-divergence and mixing times of quantum markov processes.  Journal of Mathematical Physics, 51(12):122201, 2010.  doi:10.1063/1.3511335.
  * [50] Barbara M. Terhal.  Quantum error correction for quantum memories.  Rev. Mod. Phys., 87:307–346, Apr 2015.  URL: https://link.aps.org/doi/10.1103/RevModPhys.87.307, doi:10.1103/RevModPhys.87.307.
  * [51] David K. Tuckett, Stephen D. Bartlett, and Steven T. Flammia.  Ultrahigh error threshold for surface codes with biased noise.  Phys. Rev. Lett., 120:050505, Jan 2018.  URL: https://link.aps.org/doi/10.1103/PhysRevLett.120.050505, doi:10.1103/PhysRevLett.120.050505.
  * [52] Shashank Virmani, Susana F. Huelga, and Martin B. Plenio.  Classical simulability, entanglement breaking, and quantum computation thresholds.  Phys. Rev. A, 71:042328, Apr 2005.  URL: https://link.aps.org/doi/10.1103/PhysRevA.71.042328, doi:10.1103/PhysRevA.71.042328.
  * [53] Chenyang Wang, Jim Harrington, and John Preskill.  Confinement-higgs transition in a disordered gauge theory and the accuracy threshold for quantum memory.  Annals of Physics, 303(1):31–58, 2003.  URL: https://www.sciencedirect.com/science/article/pii/S0003491602000192, doi:https://doi.org/10.1016/S0003-4916(02)00019-2.
  * [54] David S. Wang, Austin G. Fowler, and Lloyd C. L. Hollenberg.  Surface code quantum computing with error rates over 1%.  Physical Review A, 83(2), Feb 2011.  URL: http://dx.doi.org/10.1103/PhysRevA.83.020302, doi:10.1103/physreva.83.020302.
  * [55] John Watrous.  Semidefinite programs for completely bounded norms.  arXiv preprint arXiv:0901.4709, 2009.
  * [56] John Watrous.  The Theory of Quantum Information.  Cambridge University Press, 2018.  doi:10.1017/9781316848142.
  * [57] Xing-Can Yao, Tian-Xiong Wang, Hao-Ze Chen, Wei-Bo Gao, Austin G. Fowler, Robert Raussendorf, Zeng-Bing Chen, Nai-Le Liu, Chao-Yang Lu, You-Jin Deng, and et al.  Experimental demonstration of topological error correction.  Nature, 482(7386):489–494, Feb 2012.  URL: http://dx.doi.org/10.1038/nature10770, doi:10.1038/nature10770.

##  Appendix A Appendix

######  Lemma A.1.

Let $\rho_{XYAB}$ be a cc-qq state of the form
$\rho_{XYAB}=\sum_{x,y}p_{xy}|x\rangle\\!\langle
x|_{X}\otimes|y\rangle\\!\langle y|_{Y}\otimes\rho_{AB}^{xy}$. Then, we have

$\displaystyle\chi^{2}_{\mathrm{Sep}\left(XA:BY\right)}\\!(\rho_{XYAB})\leq
d_{A}d_{B}-1\ .$ (29)

In addition, we can express the $\chi^{2}$ divergence to separable states
$\mathrm{Sep}\left(XA:BY\right)$ as

$\displaystyle\chi^{2}_{\mathrm{Sep}\left(XA:BY\right)}\\!(\rho_{XYAB})=\left(\sum_{x,y}p_{xy}\sqrt{\chi^{2}_{\mathrm{Sep}\left(A:B\right)}\\!(\rho^{xy}_{AB})+1}\right)^{2}-1\
.$ (30)

######  Proof A.2.

Consider the separable state
$\sigma_{XYAB}=\sum_{x,y}p_{xy}|x\rangle\\!\langle
x|_{X}\otimes|y\rangle\\!\langle
y|_{Y}\otimes\frac{\mathds{1}_{AB}}{d_{A}d_{B}}$. We get
$\chi^{2}(\rho,\sigma)=\sum_{x,y}p_{xy}d_{A}d_{B}\mathrm{Tr}\left(\left(\rho^{xy}\right)^{2}\right)-1\leq
d_{A}d_{B}-1$. This shows (29).

To show Eq. (30), by the data processing inequality for the $\chi^{2}$
divergence, we have that

$\displaystyle\chi^{2}_{\mathrm{Sep}\left(XA:BY\right)}\\!(\rho_{XYAB})=\min_{\begin{subarray}{c}q_{xy}\\\
\sigma^{xy}\in\mathrm{Sep}(A:B)\end{subarray}}\chi^{2}\left(\rho_{XYAB},\sum_{x,y}q_{xy}|x\rangle\\!\langle
x|_{X}\otimes|y\rangle\\!\langle y|_{Y}\otimes\sigma^{xy}_{AB}\right)\ ,$

where $q_{xy}$ is a probability distribution. Note that for any $x,y$ for
which $q_{xy}>0$, $\sigma^{xy}_{AB}$ has to be separable if
$\sum_{x,y}q_{xy}|x\rangle\\!\langle x|\otimes|y\rangle\\!\langle
y|\otimes\sigma^{xy}_{AB}$ is separable. We can write

$\displaystyle\min_{\begin{subarray}{c}q_{xy}\\\
\sigma^{xy}\in\mathrm{Sep}(A:B)\end{subarray}}$
$\displaystyle\chi^{2}\\!\left(\rho_{XYAB},\sum_{x,y}q_{xy}|x\rangle\\!\langle
x|_{X}\otimes|y\rangle\\!\langle y|_{Y}\otimes\sigma_{AB}^{xy}\right)$
$\displaystyle=\left(\min_{q_{xy}}\sum_{x,y}p_{xy}^{2}q_{xy}^{-1}\min_{\sigma^{xy}_{AB}\in\mathrm{Sep}(A:B)}\mathrm{Tr}\left(\rho^{xy}\left(\sigma^{xy}\right)^{-1/2}\rho^{xy}\left(\sigma^{xy}\right)^{-1/2}\right)\right)-1$
$\displaystyle=\left(\min_{q_{xy}}\sum_{x,y}p_{xy}^{2}q_{xy}^{-1}\left(\chi^{2}_{\mathrm{Sep}}(\rho^{xy}_{AB})+1\right)\right)-1\
.$

By convexity of the function $z\mapsto z^{-1}$ and introducing
$Z=\sum_{x,y}\sqrt{p_{xy}^{2}\left(\chi^{2}_{\mathrm{Sep}\left(A:B\right)}\\!(\rho^{xy}_{AB})+1\right)}$,
we have

$\displaystyle\sum_{x,y}\frac{\sqrt{p_{xy}^{2}\left(\chi^{2}_{\mathrm{Sep}\left(A:B\right)}\\!(\rho^{xy}_{AB})+1\right)}}{Z}\frac{\sqrt{p_{xy}^{2}\left(\chi^{2}_{\mathrm{Sep}\left(A:B\right)}\\!(\rho^{xy}_{AB})+1\right)}}{q_{xy}}$
$\displaystyle\geq\frac{1}{\sum_{x,y}\frac{1}{Z}q_{xy}}=Z\ .$

We also have equality by choosing
$q_{xy}=\frac{\sqrt{p_{xy}^{2}\left(\chi^{2}_{\mathrm{Sep}\left(A:B\right)}\\!(\rho^{xy}_{AB})+1\right)}}{Z}$
and we obtain

$\displaystyle\chi^{2}_{\mathrm{Sep}\left(XA:BY\right)}\\!(\rho_{XYAB})=Z^{2}-1\enspace.$

######  Lemma A.3.

Let $\epsilon\in(0,1)$ and $\rho_{XYA_{1}B_{1}}$ be a cc-qq state of the form
given in Lemma A.1 satisfying
$\chi^{2}_{\mathrm{Sep}\left(XA_{1}:B_{1}Y\right)}\\!\left(\rho_{XYA_{1}B_{1}}\right)\geq\epsilon$.
Then, for any separable quantum channel
$\mathcal{T}\in\mathrm{SepC}\left((A_{1},A_{2}):(B_{1},B_{2})\right)$, we have

$\chi^{2}_{\mathrm{Sep}\left(XA_{2}:B_{2}Y\right)}\\!\left((\mathcal{I}_{XY}\otimes\mathcal{T})\left(\rho_{XYA_{1}B_{1}}\right)\right)\leq\left(1-\frac{\epsilon^{2}}{100}\left(1-\eta_{\chi}(\mathcal{T})\right)\right)\chi^{2}_{\mathrm{Sep}\left(XA_{1}:B_{1}Y\right)}\\!\left(\rho_{XYA_{1}B_{1}}\right)\,.$
(31)

######  Proof A.4.

By Eq. (30), we have

$\displaystyle\chi^{2}_{\mathrm{Sep}\left(XA_{2}:B_{2}Y\right)}\\!$
$\displaystyle\left((\mathcal{I}_{XY}\otimes\mathcal{T})\left(\rho\right)\right)$
(32)
$\displaystyle=\left(\sum_{x,y}p_{xy}\sqrt{\chi^{2}_{\mathrm{Sep}\left(A_{2}:B_{2}\right)}\\!\left(\mathcal{T}(\rho^{xy}_{A_{1}B_{1}})\right)+1}\right)^{2}-1$
(33)
$\displaystyle\leq\left(\sum_{x,y}p_{xy}\min_{\sigma\in\mathrm{Sep(A_{1}:B_{1})}}\sqrt{\chi^{2}\left(\mathcal{T}(\rho^{xy}_{A_{1}B_{1}}),\mathcal{T}(\sigma_{A_{1}B_{1}})\right)+1}\right)^{2}-1$
(34)
$\displaystyle\leq\left(\sum_{x,y}p_{xy}\min_{\sigma\in\mathrm{Sep(A_{1}:B_{1})}}\sqrt{\eta_{\chi}(\mathcal{T})\chi^{2}(\rho^{xy}_{A_{1}B_{1}},\sigma_{A_{1}B_{1}})+1}\right)^{2}-1$
(35)
$\displaystyle=\left(\sum_{x,y}p_{xy}\sqrt{\eta_{\chi}(\mathcal{T})\chi^{2}_{\mathrm{Sep}\left(A_{1}:B_{1}\right)}\\!\left(\rho^{xy}_{A_{1}B_{1}}\right)+1}\right)^{2}-1$
(36)

We want to compare this expression to

$\displaystyle\chi^{2}_{\mathrm{Sep}\left(XA_{1}:B_{1}Y\right)}\\!\left(\rho_{XYA_{1}B_{1}}\right)=\left(\sum_{x,y}p_{xy}\sqrt{\chi^{2}_{\mathrm{Sep}\left(A_{1}:B_{1}\right)}\\!\left(\rho^{xy}_{A_{1}B_{1}}\right)+1}\right)^{2}-1\
.$

First, we note that by the assumption, we have

$\displaystyle\sum_{x,y}p_{xy}\sqrt{\chi^{2}_{\mathrm{Sep}\left(A_{1}:B_{1}\right)}\\!\left(\rho^{xy}_{A_{1}B_{1}}\right)+1}\geq\sqrt{1+\epsilon}\
.$

Now consider the set
$S_{1}=\\{(x,y):\chi^{2}_{\mathrm{Sep}\left(A_{1}:B_{1}\right)}\\!\left(\rho^{xy}_{A_{1}B_{1}}\right)\leq\epsilon/2\\}$
and the complementary set
$S_{2}=\\{(x,y):\chi^{2}_{\mathrm{Sep}\left(A_{1}:B_{1}\right)}\\!\left(\rho^{xy}_{A_{1}B_{1}}\right)>\epsilon/2\\}$.
As $p_{xy}$ forms a probability distribution, we have

$\displaystyle\sum_{(x,y)\in
S_{1}}p_{xy}\sqrt{\chi^{2}_{\mathrm{Sep}\left(A_{1}:B_{1}\right)}\\!\left(\rho^{xy}_{A_{1}B_{1}}\right)+1}\leq\sqrt{1+\epsilon/2}\
.$

As a result,

$\displaystyle\sum_{(x,y)\in
S_{2}}p_{xy}\sqrt{\chi^{2}_{\mathrm{Sep}\left(A_{1}:B_{1}\right)}\\!\left(\rho^{xy}_{A_{1}B_{1}}\right)+1}\geq\sqrt{1+\epsilon}-\sqrt{1+\epsilon/2}\geq\epsilon/8\
.$

Going back to the expression (36), we first upper bound the part of the sum
indexed by the elements in $S_{2}$ as

$\displaystyle\sum_{(x,y)\in S_{2}}p_{xy}$
$\displaystyle\sqrt{\eta_{\chi}(\mathcal{T})\chi^{2}_{\mathrm{Sep}\left(A_{1}:B_{1}\right)}\\!(\rho^{xy}_{A_{1}B_{1}})+1}$
$\displaystyle\hskip
56.9055pt\leq\sqrt{\frac{\eta_{\chi}(\mathcal{T})\epsilon/2+1}{\epsilon/2+1}}\sum_{(x,y)\in
S_{2}}p_{xy}\sqrt{\chi^{2}_{\mathrm{Sep}\left(A_{1}:B_{1}\right)}\\!(\rho^{xy}_{A_{1}B_{1}})+1}\
,$

where we used the fact that the function $z\mapsto\frac{\eta z+1}{z+1}$ is
non-increasing in the interval $[0,\infty)$ for $\eta\in[0,1]$. Using this
same fact, we get that for $a,b\geq 0$ with $a/b\geq c$, we have $\eta
a+b\leq\frac{\eta c+1}{c+1}(a+b)$. Applying this to $a=\sum_{(x,y)\in
S_{2}}p_{xy}\sqrt{\chi^{2}_{\mathrm{Sep}\left(A_{1}:B_{1}\right)}\\!(\rho^{xy}_{A_{1}B_{1}})+1}$
and $b=\sum_{(x,y)\in
S_{1}}p_{xy}\sqrt{\chi^{2}_{\mathrm{Sep}\left(A_{1}:B_{1}\right)}\\!(\rho^{xy}_{A_{1}B_{1}})+1}$
which leads to $c=\frac{\epsilon}{16}$, we get:

$\displaystyle\sum_{x,y}p_{xy}$
$\displaystyle\sqrt{\eta_{\chi}(\mathcal{T})\chi^{2}_{\mathrm{Sep}\left(A_{1}:B_{1}\right)}\\!(\rho^{xy}_{A_{1}B_{1}})+1}$
$\displaystyle\hskip
56.9055pt\leq\sqrt{\frac{\eta_{\chi}(\mathcal{T})\epsilon/2+1}{\epsilon/2+1}}\sum_{(x,y)\in
S_{2}}p_{xy}\sqrt{\chi^{2}_{\mathrm{Sep}\left(A_{1}:B_{1}\right)}\\!(\rho^{xy}_{A_{1}B_{1}})+1}$
$\displaystyle\hskip 68.28644pt+\sum_{(x,y)\in
S_{1}}p_{xy}\sqrt{\chi^{2}_{\mathrm{Sep}\left(A_{1}:B_{1}\right)}\\!(\rho^{xy}_{A_{1}B_{1}})+1}$
$\displaystyle\hskip
56.9055pt\leq\left(\frac{1+\sqrt{\frac{\eta_{\chi}(\mathcal{T})\epsilon/2+1}{\epsilon/2+1}}\frac{\epsilon}{16}}{1+\frac{\epsilon}{16}}\right)\sum_{x,y}p_{xy}\sqrt{\chi^{2}_{\mathrm{Sep}\left(A_{1}:B_{1}\right)}\\!\left(\rho^{xy}_{A_{1}B_{1}}\right)+1}\
.$

As a result,

$\displaystyle\chi^{2}_{\mathrm{Sep}\left(XA_{2}:B_{2}Y\right)}\\!$
$\displaystyle\left((\mathcal{I}\otimes\mathcal{T})\left(\rho\right)\right)$
$\displaystyle\leq\left(\frac{1+\sqrt{\frac{\eta_{\chi}(\mathcal{T})\epsilon/2+1}{\epsilon/2+1}}\frac{\epsilon}{16}}{1+\frac{\epsilon}{16}}\right)^{2}\left(\sum_{x,y}p_{xy}\sqrt{\chi^{2}_{\mathrm{Sep}\left(A_{1}:B_{1}\right)}\\!\left(\rho^{xy}_{A_{1}B_{1}}\right)+1}\right)^{2}-1$
$\displaystyle\leq\left(\frac{1+\sqrt{\frac{\eta_{\chi}(\mathcal{T})\epsilon/2+1}{\epsilon/2+1}}\frac{\epsilon}{16}}{1+\frac{\epsilon}{16}}\right)^{2}\left(\left(\sum_{x,y}p_{xy}\sqrt{\chi^{2}_{\mathrm{Sep}\left(A_{1}:B_{1}\right)}\\!\left(\rho^{xy}_{A_{1}B_{1}}\right)+1}\right)^{2}-1\right)$
$\displaystyle=\left(\frac{1+\sqrt{\frac{\eta_{\chi}(\mathcal{T})\epsilon/2+1}{\epsilon/2+1}}\frac{\epsilon}{16}}{1+\frac{\epsilon}{16}}\right)^{2}\chi^{2}_{\mathrm{Sep}\left(XA_{1}:B_{1}Y\right)}\\!\left(\rho\right)\enspace.$

Finally, using the fact that $\sqrt{1-z}\leq 1-z/2$, it is straightforward to
see that

$\displaystyle\left(\frac{1+\sqrt{\frac{\eta_{\chi}(\mathcal{T})\epsilon/2+1}{\epsilon/2+1}}\frac{\epsilon}{16}}{1+\frac{\epsilon}{16}}\right)^{2}\leq
1-\frac{\epsilon^{2}}{100}\left(1-\eta_{\chi}(\mathcal{T})\right)\enspace.$

This concludes the proof.


* (60) B. Dubetsky and P. R. Berman, Ground-state Ramsey fringes, Phys. Rev. A 56, R1091 (1997).
  * (61) B. Dubetsky and M. A. Kasevich, Atom interferometer as a selective sensor of rotation or gravity, Phys. Rev. A 74, 023615 (2006).
  * (62) K. Bongs, R. Launay, and M. A. Kasevich, High-order inertial phase shifts for time-domain atom interferometers, Appl. Phys. B 84, 599 (2006).
  * (63) B. Dubetsky, S. B. Libby, and P. Berman, Atom interferometry in the presence of an external test mass, Atoms 4, 14 (2016).
  * (64) P. Asenbaum, C. Overstreet, T. Kovachy, D. D. Brown, J. M. Hogan, and M. A. Kasevich, Phase shift in an atom interferometer due to spacetime curvature across its wave function, Phys. Rev. Lett. 118, 183602 (2017).
  * (65) B. Dubetsky and G. Raithel, Nanometer scale period sinusoidal atom gratings produced by a Stern-Gerlach beam splitter, arXiv:physics/0206029 [physics.atom-ph].
  * (66) The inequality (25b) means that during the time $\Delta^{-1}$ one can neglect the changes in the phase of the wave function associated with the Raman frequency detuning $\tilde{\delta}$, with the Doppler shift (18b) and the change in this shift due to the acceleration of the atom $\left|\mathbf{q}_{i}\cdot\mathbf{g}\right|T$, with the recoil frequency (2), with characteristic times of change in the amplitude and phase of the fields $\tau_{f}$ and $\dot{\phi}^{-1}$. Under these conditions, one can eliminate the first term on the right-hand side of Eq. (24c) and then, using integration by parts, arrive at the expression (27) for the level $\left|o\right\rangle$ amplitude.
  * (67) J. M. McGuirk, G. T. Foster, J. B. Fixler, M. J. Snadden, and M. A. Kasevich, Sensitive absolute-gravity gradiometry using atom interferometry, Phys. Rev. A 65, 033608 (2002).
  * (68) A. Louchet-Chauvet, T. Farah, Q. Bodart, A. Clairon, A. Landragin, S. Merlet and F. P. D. Santos, The influence of transverse motion within an atomic gravimeter, New J. Phys. 13 065025 (2011).
  * (69) Another possibility here is to place detunings $\Delta$ between sublevels of the hyperfine structure of the state $o$, so that the contributions to the ac-Stark shift from different sublevels cancel each other.
  * (70) L. D. Landau and E. M. Lishitz, Quantum Mehanics: Non-relativistic Theory (Pergamon, Oxford,1989), translated by J. B. Sykes and J. S. Bell from the fourth edition, Moscow Nauka 1989, p. 205, problem 1.
  * (71) A. Peters, High precision gravity measurements using atom interferometry, Ph. D. thesis, Stanford University, 1998.
  * (72) C. Antoine, Matter wave beam splitters in gravito-inertial and trapping potentials: Generalized ttt scheme for atom interferometry, Appl. Phys. B 84, 585 (2006).
  * (73) A. Bertoldi, F. Minardi, and M. Prevedelli, Phase shift in atom interferometers: Corrections for nonquadratic potentials and finite-duration laser pulses, Phys. Rev. A 99, 033619 (2019).
  * (74) N. F. Ramsey, A New Molecular Beam Resonance Method, Phys. Rev. 76, 996 (1949).
  * (75) V. I. Yudin, A. V. Taichenachev, C. W. Oates, Z. W. Barber, N. D. Lemke, A. D. Ludlow, U. Sterr, C. Lisdat, and F. Riehle, Hyper-Ramsey spectroscopy of optical clock transitions, Phys. Rev. A 82, 011804(R) (2010).
  * (76) N. Huntemann, B. Lipphardt, M. Okhapkin, C. Tamm, E. Peik, A. V. Taichenachev, and V. I. Yudin, Generalized Ramsey Excitation Scheme with Suppressed Light Shift, Phys. Rev. Lett. 109, 213002 (2012).
  * (77) A. C. Carew, Apparatus for inertial sensing with cold atoms, Ph. D. thesis, York University, 2018.
  * (78) B. C. Young, Private communications, 2010.
  * (79) F. Di Pumpo, C. Ufrecht, A. Friedrich, E. Giese, W. P. Schleich, and W. G. Unruh, Gravitational redshift tests with atomic clocks and atom interferometers, PRX Quantum 2, 040333 (2021).
  * (80) B. Fang, N. Mielec, D. Savoie, M. Altorio, A. Landragin, and R. Geiger, Improving the phase response of an atom interferometer by means of temporal pulse shaping, New J. Phys. 20, 023020 (2017).
  * (81) J. F. Clauser, Ultra-high sensitivity accelerometers and gyroscopes using neutral atom matter-wave interferometry in Proceedings of the International Workshop on Matter Wave Interferometry in the Light of Schrodinger’s Wave Mechanics, G. Badurek, H. Rauch and A. Zeilinger editors, 1987, Physica B+C 151, 262  (1988).
  * (82) I. Perrin, M. Cadoret, Y. Bidel, N. Zahzam, C. Blanchard, and A. Bresson, Proof-of-principle demonstration of vertical gravity gradient measurement using a single proof mass double-loop atom interferometer, Phys. Rev. A 99, 013601 (2019).
  * (83) J. K. Stockton, K. Takase, and M. A. Kasevich, Absolute geodetic rotation measurement using atom interferometry, Phys. Rev. Lett. 107, 133001 (2011).
  * (84) L. A. Sidorenkov, R. Gautier, M. Altorio, R. Geiger, and A. Landragin, Tailoring multi-loop atom interferometers with adjustable momentum transfer, Phys. Rev. Lett. 125, 213201 (2020).
  * (85) I. Dutta, D. Savoie, B. Fang, B. Venon, C. L. Garrido Alzar, R. Geiger, and A. Landragin, Continuous cold-atom inertial sensor with 1 nrad/ sec rotation stability, Phys. Rev. Lett. 116, 183003 (2016).
  * (86) R. Gautier, M. Guessoum, L. A. Sidorenkov, Q. Bouton, A. Landragin, and R. Geiger, Accurate measurement of the Sagnac effect for matter waves, Science Advances, 8, eabn8009 (2022).
  * (87) A. P. Kazantsev and G. I. Surdutovich, The Kapitza-Dirac effect for atoms in a strong resonant field, Pis’ma Zh. Eksp. Teor. Fiz. 21, 346 (1975) [JETP Lett. 21, 158 (1975)].
  * (88) A. Turlapov, A. Tonyushkin, and T. Sleator, Talbot-Lau effect for atomic de Broglie waves manipulated with light, Phys. Rev. A 71, 043612 (2005).
  * (89) T. Pfau, C. Kurtsiefer, C. S. Adams, M. Sigel, and J. Mlynek, Magneto-optical beam splitter for atoms, Phys. Rev. Lett. 71, 3427 (1993).
  * (90) R. Grimm, J. Söding, and Yu. B. Ovchinnikov, Coherent beam splitter for atoms based on a bichromatic standing light wave, Opt. Lett. 19, 658 (1994).
  * (91) A. P. Kazantsev, G. I. Surdutovich and V. P. Yakovlev, On the quantum theory of resonance scattering of atoms by light, Pis’ma Zh. Eksp. Teor. Fiz. 31, 542 (1980) [JETP Lett. 31, 509 (1980)].
  * (92) P. L. Gould and D. E. Pritchard, Atoms interacting with standing light waves: Diffraction, diffusion and rectification, in Coherent and Collective Interactions of Particles and Radiation Beams, Proceedings of the International School of Physics “Enrico Fermi,” Course CXXXI, Varenna, 1995, edited by A. Aspect,W. Barletta, and R. Bonifacio (IOS, Amsterdam, 1996), Vol. 131, p. 443\.
  * (93) B. Dubetsky and P. R. Berman, Atom gratings produced by large-angle atom beam splitters, Phys. Rev. A 64, 063612 (2001).
  * (94) W. Gerlach, O. Stern, Der experimentelle nachweis des magnetischen moments des silberatoms. Z. Physik 8, 110 (1922).
  * (95) P. R. Berman, B. Dubetsky, and J. L. Cohen, High-resolution amplitude and phase gratings in atom optics, Phys. Rev. A 58, 4801 (1998).
  * (96) R. Gupta, J. J. McClelland, P. Marte, and R. J. Celotta, Raman-induced avoided crossings in adiabatic optical potentials: Observation of $\lambda/8$ spatial frequency in the distribution of atoms, Phys. Rev. Lett. 76, 4689 (1996).
  * (97) P. S. Jessen and I. H. Deutsch, Optical Lattices, Adv. At. Mol. Opt. Phys. 37, 95 (1996).
  * (98) B. Dubetsky and P. R. Berman, $\lambda/8$-period optical potentials, Phys. Rev. A 66, 045402 (2002).