Published in Quantum on 25th April 2017: https://doi.org/10.22331/q...
Limits on the storage of quantum information in a
volume of space
Steven T. Flammia
1 2
, Jeongwan Haah
3 2
, Michael J. Kastoryano
4
, and Isaac H. Kim
5 6 7
1
Centre for Engineered Quantum Systems, School of Physics, The University of Sydney, Australia
2
Center for Theoretical Physics, Massachusetts Institute of Technology, Cambridge, USA
3
Station Q Quantum Architectures and Computation Group, Microsoft Research, Redmond, Washington, USA
4
NBIA, Niels Bohr Institute, University of Copenhagen, Denmark
5
IBM T. J. Watson Research Center, Yorktown Heights, New York, USA
6
Perimeter Institute for Theoretical Physics, Waterloo ON N2L 2Y5, Canada
7
Institute for Quantum Computing, University of Waterloo, Waterloo ON N2L 3G1, Canada
March 30, 2017
We study the fundamental limits on the reliable storage of quantum information in lattices
of qubits by deriving tradeoff bounds for approximate quantum error correcting codes. We
introduce a notion of local approximate correctability and code distance, and give a number
of equivalent formulations thereof, generalizing various exact error-correction criteria. Our
tradeoff bounds relate the number of physical qubits n, the number of encoded qubits k, the
code distance d, the accuracy parameter δ that quantifies how well the erasure channel can
be reversed, and the locality parameter ` that specifies the length scale at which the recovery
operation can be done. In a regime where the recovery is successful to accuracy δ that is
exponentially small in `, which is the case for perturbations of local commuting projector codes,
our bound reads kd
2
D−1
≤ O
n(log n)
2D
D−1
for codes on D-dimensional lattices of Euclidean
metric. We also find that the code distance of any local approximate code cannot exceed
O
`n
(D−1)/D
if δ ≤ O(`n
−1/D
). As a corollary of our formulation of correctability in terms
of logical operator avoidance, we show that the code distance d and the size
˜
d of a minimal
region that can support all approximate logical operators satisfies
˜
dd
1
D−1
≤ O
n`
D
D−1
, where
the logical operators are accurate up to O
(nδ/d)
1/2
in operator norm. Finally, we prove that
for two-dimensional systems if logical operators can be approximated by operators supported
on constant-width flexible strings, then the dimension of the code space must be bounded.
This supports one of the assumptions of algebraic anyon theories, that there exist only finitely
many anyon types.
1 Introduction
Quantum information is susceptible to decoherence, but the effect can be mitigated by redundantly
encoding the information in a quantum error correcting code. Since a reliable qubit is a scarce resource,
it is desirable to achieve maximal protection with a minimum effort, and one of the most promising
approaches for achieving this is to incorporate geometric locality into the structure of the code.
Jeongwan Haah: jwhaah@microsoft.com
1
arXiv:1610.06169v2 [quant-ph] 29 Mar 2017
Local quantum error correcting codes have been thoroughly studied over the past decade [1], with
most of the work focusing on (topological) stabilizer or subsystem codes. A quantum code is said to be
local if its stabilizer or gauge generators are supported on a geometrically local and bounded region of a
lattice embeddable in some metric space. These codes, like most classical and quantum error correcting
codes, are often characterized by three numbers [[n, k, d]]: n is the number of physical, error-prone qubits
comprising the code, k is the maximal number of logical qubits that can be reliably encoded, and d is the
distance of the code, i.e. the minimum number of qubits that must be modified to perform a nontrivial
logical operation.
Not all values of the triple [[n, k, d]] are achievable, and locality in particular imposes additional
constraints. In addition to the constraints imposed by local codes, which we review below, the no-
cloning bound implies that exact quantum error-correcting codes cannot correct n/4 arbitrary single-qudit
errors [2]. In its smallest instance, the bound shows that there is no code on four physical qubits that
exactly corrects an arbitrary single-qudit error.
However, the main goal of quantum error correction is to reduce effective error rates, and it suffices to
only approximately correct errors for this purpose, provided that the approximation error is sufficiently
low. Interestingly, the no-cloning bound breaks down when one considers such approximate quantum
error correcting codes. Leung et al. [3] have shown this explicitly by constructing a four-qubit code that
approximately corrects an arbitrary single-qubit amplitude damping error. This effect was demonstrated
even more dramatically by Cr´epeau et al. [4], who constructed approximate codes that can approximately
correct b(n −1)/2c arbitrary single qudit errors, with an approximation error that is exponentially small
in n. This demonstrates that approximate codes can radically outperform exact codes by some measures.
Many local quantum codes can be represented as ground spaces of gapped local Hamiltonians. Often
these systems have an exact unfrustrated ground space, but there are much more general systems where
we expect code properties to hold with some suitable notion of approximation. Known examples include
fractional quantum Hall states [5] and Kiteav’s honeycomb model in the gapped phase [6]. Might these
more general systems allow for unique possibilities for storing quantum information? Many aspects of the
unfrustrated Hamiltonian quantum codes remain stable under small perturbations, such as the energy
splitting in the ground space and the gap [7]. It is also known that the logical operators, once perturbed,
become dressed operators that are quasi-local [8, 9]. However, in light of the examples of Refs. [3, 4], the
stability of all code properties for general systems deserves a careful and thorough examination.
Motivated by these observations, we initiate the study of local approximate quantum error-correcting
codes (local AQEC). It is one of the aims of the present paper to establish a framework allowing the analysis
of code properties of subspaces in sufficient generality to encompass many of the interesting gapped many-
body models, not necessarily represented by commuting projector Hamiltonians or unfrustrated ground
spaces. Our contributions are threefold.
In the first part, we comprehensively analyze the abstract theory of AQEC codes. We introduce
a number of different notions of approximate quantum error correction and study the relations between
them. In particular, we propose a notion of locally correctable codes for which the class of local commuting
projector codes are a subclass. The different notions of correctability that we introduce are all exactly
equivalent when the approximation parameter δ vanishes, and the relations we establish show that different
notions in fact have varying levels of robustness once δ > 0.
In the second part, we use these relations to generalize the existing tradeoff bounds for the parameters
of local commuting projector codes. These results include the parameter bounds derived by Bravyi,
Poulin, and Terhal [10] and the constraints on the structure of the logical operator derived by Haah
and Preskill [11] as special cases. Our bounds are only slightly weaker than the prior results for exact
codes, implying that local AQEC cannot significantly outperform exact codes by these measures. We
furthermore establish a condition under which one of the key axioms of (2+1)-dimensional topological
quantum field theory can be derived: If the logical operators can be continuously deformed away from
2
any disk-like region, the ground state degeneracy is bounded by a constant independent of the system
size. Roughly, the number of anyon species in 2D is finite.
Our proof techniques make significant departures from much of the previous literature on local codes
in that we make heavy use of information-theoretic ideas and methods. We provide information-theoretic
generalizations of well known tools from the theory of local codes, including more general forms of the
Union Lemma and the Cleaning Lemma. Our proofs and definitions do not require the codes to have
local generators; rather all of our analysis is done at the level of subspaces. Locality in only invoked at
the level of the recovery operations.
By construction, our results are trivially applicable to local commuting projector codes, but more
importantly, every step in our derivations is applicable to the perturbation of such codes so long as the
perturbed Hamiltonian remains in the same gapped phase. This class includes explicit models such as
the Kitaev’s honeycomb model [6], the [4,2,2]-concatenated toric code [12, 13], and codes based on entan-
glement renormalization that generate holographic quantum codes that are only approximate codes [14].
Thus, we establish that error correction in realistic Hamiltonian systems that only approximate local
commuting projector codes is indeed robust to small imperfections.
Prior Work
Previous work on exact quantum codes has placed limits on the achievable code parameters. Beyond
the no-cloning bound [2] mentioned above that holds for general exact codes, locality imposes further
constraints on the code parameters. Bravyi and Terhal [15] have shown that stabilizer and subsystem
codes in D spatial dimensions obey the bound d ≤ O(L
D−1
) where n = L
D
is the number of physical qubits
in the code in a Euclidean lattice. The result on stabilizer codes was extended to the larger class of local
commuting projector codes by Bravyi, Poulin, and Terhal [10], who also showed that kd
2/(D−1)
≤ O(n).
Delfosse [16] showed that these arguments can also be adapted to hyperbolic lattices, and showed that
surface codes and color codes (with D = 2) satisfy kd
2
≤ O
n(log n)
2
, and that this is scaling is
achievable. The result on subsystem codes was adapted by Bravyi [17] to show that subsystem codes
satisfy the bound kd
1/(D−1)
≤ O(n). Quantum stabilizer codes based on the toric code saturate these
bounds for D = 2, and subsystem codes that saturate for D = 2 [17] or nearly saturate for D ≥ 3 [18] are
also known.
For the class of AQEC, no prior work has shown nontrivial tradeoff bounds like the ones above,
and most of the relevant work (such as Ref. [4] above) is confined to codes without any evident locality
structure. Known examples of AQEC have generally all been applied to the study of amplitude damping
channels (see e.g. [3, 19–21]). Conditions for approximate correction have been derived in terms of
the coherent information [22] as well as in terms of error metrics that relate to the Knill-Laflamme
conditions for exact error correction [23, 24]. Some progress has also been made on finding explicit
efficient representations of logical operators for approximate codes [25, 26].
Overview of results
Our results depend on defining appropriate measures of locality and approximation. We will precisely
define the relevant measures in Definitions 1 and 2, but, roughly speaking, ` will denote a length scale (in
lattice spacing units) for the action of a recovery map for erasure errors, and δ will denote the accuracy
of the recovery.
Our first contribution is to relate five operationally distinct notions of correctability, decoupling, and
cleaning. We will establish similarities between these notions in the approximate recovery setting by
deriving inequalities among them without any dimensional factors of the Hilbert spaces involved. When
the approximation parameter vanishes, these notions become exactly equivalent.
3
Decompose the lattice into disjoint regions as Λ = ABC and let R denote a purifying system (see
e.g. Fig. 1, though there is no restriction on the geometry of the regions). We denote an operator supported
on a subsystem using superscripts; for example, ρ
AB
is a state supported on AB, and ρ
A
is its partial
trace supported on A. Then we have our first main result.
Result 1 (Imprecise formulation). The following statements are equivalent.
(I) There exists a local quantum channel R
AB
B
with support on AB approximately recovering the erasure
of region A: R
AB
B
(ρ
BCR
) ≈ ρ
ABCR
.
(II) There exists a disentangling unitary U
B
on B = B
1
B
2
that approximately turns any code state into
a product state between AB
1
and B
2
C: U
B
ρ
ABCR
U
B†
≈ ω
AB
1
⊗ ρ
B
2
CR
.
(III) Tracing out B approximately decouples A from C: ρ
ACR
≈ ρ
A
⊗ ρ
CR
.
(IV) Any logical operator U
ABC
is associated with another operator V
BC
supported on the complement
of A that act equivalently when restricted to the code space Π: U
ABC
|
Π
≈ V
BC
|
Π
.
In particular, we have
(I) =
`
(II) ∼
`
(III) ∼ (IV), (1)
where ‘∼’ means that the magnitude of the error is not preserved in the implication, and the subscript ‘`’
means that the equivalence holds with locality.
Here we have been imprecise about the exact nature of the equivalence, and in particular we have not
quantified or defined our notion of approximation or what it means for the equivalence to hold with
locality. These statements are given precise formulations and proofs beginning in Section 2 as follows:
(I) Definition 2, (II) Corollary 4, (III) Theorems 3, 5, and (IV) Theorems 7, 8.
Our next main result shows that for AQECs that have local correctability parametrized by an approx-
imation parameter δ and a length scale `, we have a tradeoff between the capacity and the reliability of
encoded information. Consider a Euclidean D-dimensional lattice of linear size L for which we intention-
ally do not specify any boundary conditions.
Result 2. For a D-dimensional AQEC with parameters [[n, k, d, δ, `]], it holds that
1 − c log(1/)
kd
2
D−1
≤ c
0
n`
2D
D−1
, (2)
where = nδ/d, and c, c
0
> 0 are absolute constants.
In the case that δ = 0 and ` is constant, as is the case for local commuting projector codes, we recover
the tradeoff bounds of Bravyi, Poulin, and Terhal [10] as a special case. Moreover, we show that for
relevant examples (like perturbed versions of local commuting projector codes) the approximation error δ
vanishes sufficiently quickly that the inequality remains meaningful in spite of the n dependence inside the
parentheses. When the accuracy is exponentially small in ` we obtain the bound quoted in the abstract
of kd
2
D−1
≤ O
n(log n)
2D
D−1
. This result is restated and proven as Theorem 9 in Section 3. Using the
approximate cleaning lemma from Section 2 and similar methods as in the proof of Theorem 9 we prove
tradeoff bounds on the support of logical operators of the code (a logical operator is one that preserves
the code subspace).
4
Result 3. For a D-dimensional AQEC with parameters [[n, k, d, δ, `]] on a lattice of linear size L, if
10Lδ < `, then the code distance is bounded from above by 5`L
D−1
. Furthermore, there exists a region Y
that contains
˜
d qubits such that every unitary logical operator U can be approximated by an operator V
on Y where
k(U − V )Πk ≤ O
p
nδ/d
and
˜
dd
1
D−1
≤ O
n`
D
D−1
. (3)
Finally, we show how the framework of AQEC can be used to derive one of the axioms of topological
quantum field theory in (2+1) dimensions: the ground space degeneracy is constant independent of system
size. We first define a notion of “flexible” logical operator that is made precise in Definition 14, which
asserts roughly that logical operators can be deformed across the lattice without changing much how they
act on the code space. We then derive the following result.
Result 4. For any code space Π of a 2-dimensional system admitting flexible logical operators, it holds
that
dim Π ≤ exp
c `
2
, (4)
where c > 0 is an absolute constant and ` is the width of the strip that supports sufficiently faithful logical
operators.
The precise formulation and proof of this statement can be found in Section 4.
Notation and conventions
As mentioned above, Λ is a regular D dimensional lattice of side length L without any specified boundary
conditions. We consider Λ ⊂ Z
D
to be embedded in R
D
with a Euclidean metric. Each site is occupied
with a qubit C
2
. The assumption that a qubit, rather than a qudit, occupies each site is not a restriction;
a higher density of degrees of freedom can be accounted for by rescaling the metric. We use letters
A, B, C, D, E, X, Y, Z ∈ Λ to denote subsystems. We use Π to denote a subspace of the joint Hilbert
space of these subsystems, which we identify as a code space. Unless otherwise specified, different letters
stand for disjoint subsystems. We will often say, for example, that a code Π is on ABC when the system
into which the code is embedded is divided into three disjoint subsystems. The letter R is reserved for a
purifying space of the code space Π. Therefore, as complex vector spaces, Π and the Hilbert space of R
are isomorphic. We will use the same symbol Π to denote the projection operator onto the code space.
Also, we will write ρ ∈ Π to mean ρ = Πρ = ρΠ. If a state ρ is pure, we will sometimes use |ρi to denote
a state vector.
When it is necessary to clarify the domain and the codomain of a linear operator, we will use subscripts
for domain, and superscripts for codomain. For example, V
AE
B
denotes a linear operator from B to AE.
The subscript will be omitted when the domain is equal to the codomain. For example, V
A
is an operator
on A. (Under strict practice of our notation, V
A
could mean a map from C to the Hilbert space of A,
which would specify a state vector, but we never use such a map.) The same rule applies for quantum
channels (i.e. completely positive and trace preserving maps). For example, Tr
A
is the erasure channel
for system A, mapping from A to scalars. If a channel is tensored with the identity channel, the identity
component will be omitted. For instance, we will write R
AD
B
(σ
BC
), which is a density operator on ACD,
in place of (R
AD
B
⊗ id
C
C
)(σ
BC
). If ρ
AB
is clear from the context, we will simply write ρ
B
in place of
Tr
A
(ρ
AB
).
Noise will be modeled by quantum channels N. It will be convenient to represent the noise in Stine-
spring form, where N(ρ) = Tr
E
(V ρ ⊗ϕ
E
V
†
) with E denoting the purifying system (environment) whose
dimension can be taken as the dimension of the channel’s input, ϕ
E
is some (pure) state of the purifying
5
system, and V is a unitary operator on the system and purifying space. The complementary channel is
obtained by tracing out the system:
ˆ
N(ρ) = Tr
S
(V (ρ ⊗ ϕ
E
)V
†
). We will mainly consider erasure noise.
Specifically, N is chosen to be N(·) = Tr
X
(·) for some subsystem X.
For any two density operators ρ and σ, the trace distance is defined as
T(ρ, σ) =
1
2
kρ − σk
1
. (5)
We will mostly use the one-norm directly instead of the symbol T. The fidelity and Bures distance are
defined as
F(ρ, σ) = Tr
q
√
σ ρ
√
σ = max
|ψ
ρ
i,|ψ
σ
i
|hψ
ρ
|ψ
σ
i|, (6)
B(ρ, σ) =
p
1 − F(ρ, σ), (7)
where the second equality for the fidelity follows from Uhlmann’s theorem [27]. The Bures distance is a
metric and satisfies the triangle inequality. These quantities satisfy the Fuchs-van de Graaf relations [28]
F
2
+ T
2
≤ 1 ≤ F + T, (8)
2B
2
(ρ, σ) ≤ kρ − σk
1
≤ 2
√
2B(ρ, σ). (9)
We will often encounter optimizations of the form
max
ρ
ABR
B(ρ
AR
, ρ
A
⊗ ρ
R
) (10)
where a code Π resides on AB. In such an expression, ρ
ABR
denotes any density matrix of the code
vectors possibly entangled with R. Since our discussion will be only for finite dimensional Hilbert spaces,
the set of all density matrices is compact under the usual subspace topology inherited from R
N
, which is
the metric topology under any mentioned metric. This means that the supremum is always attained at
some state.
All log and exp functions have base e ' 2.718.
2 Notions of Approximate Quantum Error Correction
Most generally, an error correction scheme should be defined in terms of encoding and decoding quantum
algorithms [4]. This definition is so general that it includes schemes where a superposition of physical
states that are outputs of the encoding algorithm may not correspond to a possible output of the encoding
algorithm, e.g. Ref. [4]. In this paper, we restrict ourselves to subspace codes. Namely, we identify a code
with a subspace of an n-qubit system, and the encoding map is an isometry from C
2
k
to (C
2
)
⊗n
, where
k is the number of encoded qubits.
An exact quantum error correcting code has a distance d if any measurement on fewer than d qubits
reveals no information about the encoded state. In other words, a distance d code admits a recovery map
that can perfectly reverse the erasure of any d −1 qubits: for any M ⊆ Λ such that |M| < d, there exists
a completely-positive trace-preserving map R such that
R ◦ Tr
M
(ρ) = ρ (11)
for all states ρ in the code subspace. An equivalent formulation of the error correction condition, known
as the Knill-Laflamme condition [29], expresses Eq. (11) in terms of the Kraus operators of the noise
channel.
6
A
B
C
R
`
Figure 1: Decomposition of the lattice in the definitions of local approximate quantum error correction.
B shields A from C by a distance at least `, and R represents the purifying space of the code.
As remarked earlier, the recovery map will never be perfect in practice and does not have to be perfect;
rather, the recovery should be of high enough fidelity to suit the purpose of the code. We use the best
recovery map in terms of Bures distance to define approximate quantum error correction.
Definition 1. We say that a region A ⊂ Λ = AB is δ-correctable on Π if there exists a recovery
operation R
AB
B
such that
B
R
AB
B
(ρ
BR
), ρ
ABR
≤ δ, (12)
for any code state ρ
AB
∈ Π and ρ
ABR
is any purification. The code distance of an approximate error
correction code Π is defined as the largest integer d such that any region A ⊆ Λ of size |A| < d is
δ-correctable on Π.
The perfect quantum error correction condition corresponds to the δ = 0 case. In our definition, the
code space Π alone does not determine the accuracy paramter δ or the code distance d; rather, the code
space gives a function from δ to d. Note that under this definition, the code distance is a non-decreasing
function of δ.
Our main intuition for local error correcting codes comes from topological systems such as the toric
code. There, errors appear as excitation pairs (anyons), that get annihilated when brought together. The
recovery of such errors therefore consists of bringing anyon pairs together. In this picture, error recovery
is a local operation. This observation motivates the following notion of a locally correctable region for
general lattice models.
Definition 2. We say that a region A ⊂ Λ = ABC, with AB = A
+`
is the region that includes all qubits
within a distance ` of A, and C is the complement of AB in Λ, as in Fig. 1, is (δ, `)-correctable on Π
if there exists a recovery operation R
AB
B
with support on AB such that
B
R
AB
B
(ρ
BCR
), ρ
ABCR
≤ δ, (13)
for any code state ρ
ABC
∈ Π and ρ
ABCR
is any purification. A code encoding k qubits on n physical qubits
is said to have parameters [[n, k, d, δ, `]] if every region of size less than d is (δ, `)-correctable.
By definition, any region that is (δ, `)-correctable is δ-correctable.
One of the central insights of quantum error correction is the information-disturbance tradeoff: the
existence of a recovery map implies that the environment knows almost nothing about the state, and vice
versa. A very general information disturbance tradeoff was derived in Ref. [23]. See also Refs. [24, 30, 31].
Here, we adapt it to our setting by assuming that the noise operation is the partial trace over a given
region A. We further sharpen the statement to accommodate for local recovery.
7
Theorem 3 (Information-Disturbance tradeoff). Let A ⊂ Λ = ABC, as in Fig. 1, and define the constant
δ
`
(A) := min
ω
A
sup
ρ
ABCR
B
ω
A
⊗ ρ
CR
, ρ
ACR
, (14)
then
inf
R
AB
B
sup
ρ
ABCR
B
R
AB
B
(ρ
BCR
), ρ
ABCR
= δ
`
(A), (15)
where the inf in Eqn. (15) is over all channels with support on AB.
The proof of Theorem 3 in App. A is quite similar to the ones in Refs. [23, 30].
As a corollary of the information disturbance tradeoff, we show that a region is locally correctable if
and only if it can be disentangled from its complement by a unitary on the boundary.
Corollary 4. Let Π be a code space on ABC = Λ, and R be a purifying auxiliary system. Let V
B
0
B
00
B
=
V · V
†
denote any isometry channel, where B
0
is some auxiliary system and B
00
is a copy of AB. Then,
δ
`
(A) = inf
ω
AB
0
,V
B
0
B
00
B
sup
ρ
ABCR
B
V
B
0
B
00
B
(ρ
ABCR
), ω
AB
0
⊗ ρ
B
00
CR
(16)
where ρ
B
00
CR
is the same as ρ
ABCR
but supported on B
00
instead of AB.
The proof of the Corollary is in Appendix D.
In Ref. [10], it is shown that for perfect error correcting codes defined by local commuting projectors,
there exists a disentangling unitary on the boundary of a correctable region such that it maps any code
vector into a product state. Moreover the tensor factor of the product state on the correctable region
is the same for any code vector. In view of our expression (16), the result in Ref. [10] corresponds to
a situation where B
00
and B
0
are subsystems of B. Although our formulation requires B
0
B
00
to have, in
general, larger dimension than that of B, our result immediately implies that of Ref. [10] when δ
`
(A) = 0.
This is because for local commuting projector codes, any code state obeys an area law of entanglement
Hartley (zeroth R´enyi) entropy. This means that there is a unitary transformation that can “compress”
the Schmidt components in B
0
B
00
of ω
AB
0
⊗ ρ
B
00
CR
into B, yielding a disentangling unitary within B.
The quantity δ
`
(A) roughly expresses how weakly a correctable region A is correlated with the far-
separated region. Indeed, it is the principle of error correction that the environment, interaction with
which would corrupt encoded information, learns nothing about the encoded states. Put differently, the
mutual information between a correctable region and the reference system is always small. The quantity
δ
`
(A) does not directly give the mutual information, but is very similar (proof in Appendix B):
Theorem 5 (Decoupling-Correctibility). Let A ⊂ Λ = ABC as in Fig. 1, then
1
9
δ
`
(A)
2
≤ sup
ρ
ABCR
B(ρ
ACR
, ρ
A
⊗ ρ
CR
) ≤ 2δ
`
(A) (17)
Schumacher and Nielsen [32] defined the coherent information, which is equivalent to the mutual
information I(A : R) between the purifying system R and the correctable region A. They argued that
if the coherent information does not degrade, then perfect error correction is possible. Schumacher and
Westmoreland [22] generalized this to an approximate setting, and argued that the change in the coherent
information bounds the recovery fidelity. However, in their argument the recovery map was constructed
from a code state, and was not shown to be applicable for all code states. This is not satisfactory for
error correction since any correcting map must not know about the code state. In the perfect error
8
correction setting, this is no longer an issue due to the Knill-Laflamme condition [29]. (See also [33].) We
were unable to find a reference that proves the existence of a recovery map that would work for all code
vectors in the approximate error correction setting, so we proved our own in Theorem 5. Schumacher and
Westmoreland’s claim follows qualitatively with a recovery map that depends only on Π because [34, 35]
I
ρ
(A : R) ≥ −2 log F(ρ
AR
, ρ
A
⊗ ρ
R
)
≥ 2B
2
(ρ
AR
, ρ
A
⊗ ρ
R
). (18)
Note that the continuity of the mutual information (see Appendix F) implies
I
ρ
(A : R) ≤18
√
2 δ
`
(A) log
dim Π
2
√
2δ
`
(A)
. (19)
No attempt has been made to optimize this inequality, and in fact we will only use a weaker statement
with log dim Π = k log 2 ≥ 1 and δ
`
(A) ≤ 1/e,
I
ρ
(A : R) ≤ O
kδ
`
(A) log(1/δ
`
(A))
(20)
since some of the formulas become simpler.
2.1 Cleanability as an alternative notion of correctability
Here we characterize the correctability of a region by logical operator avoidance. If all logical operations
can be done outside a region A, then, tautologically, for any logical operator U one can achieve the
equivalent action on the code space without touching A. Thus, the region A is cleaned of U. In a perfect
error correction setting, it is known that a correctable region can be cleaned of any logical operator,
and hence the name “cleaning lemma” [11, 15, 36]. We prove a generalization of the cleaning lemma in
the approximate setting, and complement it with the converse statement. This establishes another error
correction criterion based on the support of logical operators.
Definition 6. An operator U is logical if it commutes with the code space projector Π.
Theorem 7 (A correctable region avoids logical operators.). Suppose A is a (δ, `)-correctable region of
the lattice ABC = Λ; i.e., there exists R
AB
B
such that
sup
ρ
ABC
B
R
AB
B
(ρ
BCR
), ρ
ABCR
≤ δ (21)
where AB is the `-neighborhood of A. Then, for any logical unitary U
ABC
, the pull-back V
BC
=
(R
AB
B
)
∗
(U
ABC
) satisfies
(U
ABC
− V
BC
)Π
≤ 4
√
δ, (22)
Π(U
ABC
− V
BC
)
≤ 4
√
δ.
The converse without the locality of the recovery map is also true:
Theorem 8 (A region avoiding logical operators is correctable.). Given the lattice AB = Λ, suppose for
any logical unitary U
AB
there exists an operator
V
B
≤ 1 supported on B such that
(U
AB
− V
B
)Π
≤ δ,
Π(U
AB
− V
B
)
≤ δ. (23)
9
X
Y
Z
R
Figure 2: Decomposition of the lattice in 2D leading to the tradeoff bound of Theorem 9.
Then there exists ω
A
such that
sup
ρ
ABR
ρ
AR
− ω
A
⊗ ρ
R
1
≤ 5δ, (24)
and A is
p
5δ/2-correctable.
Theorems 7 and 8 are proved in Appendix C.
3 Tradeoff bounds for locally correctable codes
Our first main result is a tradeoff bound between the number of encoded qubits and the distance of a
code on the lattice. The proof is similar in essence to the tradeoff bound proved for local commuting
projector codes by Bravyi, Poulin, and Terhal [10]. However, the details vary in several respects because
we are dealing with approximate error correcting codes rather than exact ones. Especially, Ref. [10] uses
an algebraic decomposition of the Hilbert space resulting from the representation theory of commuting
operators. In the approximate setting we cannot use such a decomposition, but instead we use a decoupling
characterization of locally correctable codes. We state and prove the theorem for a two-dimensional
Euclidean lattice of qubits for clarity of presentation, but the proof generalizes easily to D-dimensional
lattices with D ≥ 2. Having a Euclidean geometry will be important in the final statement because we
are going to use the fact that the surface area of a ball of radius r grows like r
D−1
. We note that the
technique below, which is borrowed from Ref. [10], will be applicable for other geometries.
Theorem 9. Let Π be a local error correcting code with parameters [[n, k, d, δ, `]] defined on a D-
dimensional Euclidean lattice of qubits. It holds that
1 − c
nδ
d
log
d
nδ
kd
2
D−1
≤ c
0
n`
2D
D−1
. (25)
where c, c
0
> 0 are constants independent of any parameters n, k, d, δ, `.
Obviously, this is meaningful only if the factor in the parenthesis is positive; we must have sufficiently
small δ. For local commuting projector codes, δ = 0 for ` such that every local projector is contained
in ` × ` square. We then recover the bound kd
2/(D−1)
≤ O(n) of Ref. [10]. Note that we did not need
to invoke any form of local generators of the code, rather we based our proof exclusively on the natural
locality structure of the subspace. If δ = δ(`) ∼ exp(−`/ξ) (as we later show is the case for perturbations
of commuting projector codes), then we obtain
kd
2
D−1
≤ O
n(log n)
2D
D−1
(26)
10
by choosing ` ∼ ξ log n ∼ ξ log(L), where L = n
1/D
is the linear system size.
The proof largely consists of three steps. We divide the whole lattice into three subsystems X, Y, Z,
each of which is a collection of disjoint correctable simply connected regions. They are depicted in Fig. 2
for D = 2. The first step is to choose the disconnected components of X and Y as large as possible. The
second step is to show that the union X or Y of those components is still correctable. For this, each
component should be sufficiently separated. In both steps, the locality of the error correcting map will
be important. The third step is to employ a technique in a proof of the quantum Singleton bound [37] to
bound the code space dimension by the volume of Z.
We will need two lemmas below, which allow us to construct regular correctable regions with weight
larger than the distance. The expansion lemma gives a prescription on how to grow a correctable region,
and the union lemma shows that the union of two distant correctable regions is again correctable.
Lemma 10 (Expansion Lemma). Let AB = A
+`
be the `-neighborhood of a region A. If A is (
A
, `)-
correctable and B is (
B
, `)-correctable, then A ∪ B is (
A
+
B
, `)-correctable.
Proof. Let ABC = A
+2`
, and let D be the rest of the lattice. Fix ω
A
that saturates the optimum for
δ
l
(A). From the correctability of region B, there exists a local recovery map R
ABC
AC
such that
B
ρ
ABCDR
, R
ABC
AC
(ρ
ACDR
)
≤
B
(27)
for any code state ρ
ABCDR
. Define a channel R
ABC
C
by
R
ABC
C
σ
C
:= R
ABC
AC
ω
A
⊗ σ
C
(28)
for any state σ
C
. Now, for an arbitrary code state ρ
ABCDR
B
R
ABC
C
(ρ
CDR
), ρ
ABCDR
=B
R
ABC
AC
(ω
A
⊗ ρ
CDR
), ρ
ABCDR
≤B
R
ABC
AC
(ω
A
⊗ ρ
CDR
), R
ABC
AC
(ρ
ACDR
)
+ B
R
ABC
AC
(ρ
ACDR
), ρ
ABCDR
≤B
ω
A
⊗ ρ
CDR
, ρ
ACDR
+
B
≤
A
+
B
, (29)
where we used monotonicity of the Bures distance. Therefore, the map R
ABC
C
recovers AB from C up to
error
A
+
B
.
Lemma 11 (Union Lemma). Suppose two regions A and B are separated by distance at least `, where A
is (
A
, `)-correctable and B is
B
-correctable. Then the union AB is (
A
+
B
)-correctable.
Proof. Fix ω
A
and ω
B
that saturate the optima for δ
`
(A) and δ
`
(B). The claim is proved as
B(ρ
ABR
, ω
A
ω
B
ρ
R
) ≤B(ρ
ABR
, ω
A
ρ
BR
)
+ B(ω
A
ρ
BR
, ω
A
ω
B
ρ
R
)
≤
A
+ B(ρ
BR
, ω
B
ρ
R
) (30)
≤
A
+
B
(31)
for any code state ρ
ABCR
.
11
A
0
B
1
B
2
B
3
C
R
Figure 3: Construction of the largest correctable square by successively adding rings of size at most d.
Proof of Theorem 9. The statement becomes vacuous if d ≤ `. So, assume d > `.
(Step 1) Since d > `, a single site is (δ, `)-correctable. Its boundary contains O(`
D
) qubits. If this is
less than d, then it is also (δ, `)-correctable, and by Lemma 10 an enlarged hypercube of linear size of
order ` is (2δ, `)-correctable. After m steps of induction, we obtain a hypercube of linear size of order m`
that is (O(mδ), `)-correctable. The induction must stop if the hypercube is so large that the boundary
“area” O(m
D−1
`
D
) becomes larger than d. Thus, m can be as large as O
d/`
D
1
D−1
. Therefore, we
conclude that any hypercube of linear size O
(d/`)
1
D−1
is
O
δ
d/`
D
1
D−1
, `
-correctable.
(Step 2) Consider a decomposition of the lattice into three regions XY Z = Λ, where X and Y are,
respectively, the unions of disconnected hypercubes of linear size O
(d/`)
1
D−1
constructed in Step 1 with
their (D−2)-dimensional “corners” of width ` removed. The hypercubes of X and Y are arranged in a high-
dimensional checkerboard. Z is the rest of the lattice. See Fig. 2 for an illustration of the decomposition for
D = 2. Let L be the linear system size. The collections X and Y consist of O
L(`/d)
1
D−1
D
hypercubes,
respectively. Applying Lemma 11 inductively over all squares of X, we see that X is -correctable where
= O(1)
L(`/d)
1
D−1
D
·
δ(d/`
D
)
1
D−1
= O(1)
nδ
d
. (32)
Similarly, Y is also -correctable.
(Step 3) Let ρ
XY Z
= Π/ dim Π be the maximally mixed code state, and ρ
XY ZR
be a purification. By
definition, S(ρ
R
) = log dim Π = k log 2. Since X and Y are -correctable, respectively, by Eq. (20), the
mutual information to R must be small:
S(ρ
X
) + S(ρ
R
) − S(ρ
XR
) ≤ O(1)k log(1/), (33)
S(ρ
Y
) + S(ρ
R
) − S(ρ
Y R
) ≤ O(1)k log(1/). (34)
Adding the two inequalities and using the fact that ρ
XY ZR
is pure, we obtain
S(ρ
X
) + S(ρ
Y
) + 2k log 2 − S(ρ
Y Z
) − S(ρ
XZ
) ≤ O(1)k log(1/).
By the subadditivity of entropy (where
˜
O hides log factors), it follows that
k(1 −
˜
O()) ≤ O(1)S(ρ
Z
) ≤ O(|Z|). (35)
The region Z consists of a grid of “bar segments”, separating the individual hypercubes in X and Y . A
bar segment has two sides of length ` and D − 2 sides of length O(d/`)
1/(D−1)
. There are as many bar
12
segments as there are the hypercubes of X and Y , the number of which is O(n)(`/d)
D/(D−1)
. Therefore,
k(1 −
˜
O()) ≤ O(n)(`/d)
D
D−1
· `
2
· O(d/`)
D−2
D−1
= O(n)`
2D
D−1
d
−2
D−1
. (36)
This complete the proof of Theorem 9.
3.1 Support of Logical Operators
As corollaries of the preceding results, we can also derive constraints on the support of logical operators.
Bravyi and Terhal [15] have shown that for stabilizer codes defined by local stabilizer generators on a
Euclidean lattice there always exists a nontrivial logical operator that is supported on a thin slab ((D−1)-
dimensional). This result was generalized to local commuting projector codes [11]. In two-dimensional
lattices, this suggests that under generic interaction of the system with an environment there would be
a process subject to a constant energy penalty that implements a nontrivial logical operation, i.e., an
error, on the encoded state. This is a strong argument against self-correction in two-dimensional systems
under a thermalizing interaction where the code space is the ground space. In other words, either bit-flip
errors or phase errors would occur by thermalization on an encoded qubit at a rate independent of code
distance.
However, this does not immediately rule out the possibility that only one of bit or phase information is
corrupted by thermalization, but the other information is protected. Indeed, any ferromagnetic (symmetry
broken) system is protected from bit-flip errors. For this observation, Haah and Preskill [11] have asked
whether it is possible to have a partially self-correcting quantum memory in two-dimensions where the
code distance is high, but, e.g., bit-flip errors are suppressed under thermalization. It was found that in
any two-dimensional local commuting projectors code if the code distance d, then all logical operators
can be supported on a region that contains
˜
d = O(L
2
/d) physical qubits. This is a negative result towards
partial self-correction because having a large distance d ∼ L implies that any other logical operator lives
on a network of finitely many string-like regions.
We generalize these results using the machinery we have developed.
Theorem 12. For any (δ, `)-correctable code Π with dim Π > 1 on a D-dimensional lattice of linear size
L, if 10Lδ < `, then the code distance is bounded from above by 5`L
D−1
.
Proof. The argument is essentially one-dimensional, and it suffices to prove the theorem for D = 1.
Suppose on the contrary to the claim that any segment of length 5` is (δ, `)-correctable. In particular,
a segment of length 5` is (δ, `)-correctable, and its two-component boundary B of size 2` is also (δ, `)-
correctable. The expansion lemma 10 implies that the union AB of length 7` is (2δ, `)-correctable. The
two-component boundary of AB is also (δ, `)-correctable, and we can again apply the expansion lemma 10
to have (3δ, `)-correctable region of length 9`. After O(L/`) times of iteration, we see that entire system
is (δL/`)-correctable. This is a contradiction since the entire system is certainly not -correctable with
< 1.
The conclusion is the most meaningful when applied to a family of codes parametrized by L, which
in turn makes it necessary for the theorem that δ be parametrically small in `. For example, if δ ∼ e
−`
,
then we can choose ` = log L so that Lδ ` and d ≤ O(L
D−1
log L).
This code distance bound is intimately related to the absence of topological order (without any sym-
metry) in one dimension D = 1. If we regard the ground space as a code space, then having a small
code distance means that there is an operator of small support that takes different expectation values for
distinct ground states, indicating that the degeneracy will be lifted upon perturbation by that operator.
In particular, if the ground space is strictly locally correctable (i.e., δ = 0 for some constant `), which is
the case if the quantum phase of the one-dimensional system is represented by a commuting Hamiltonian
13
X
R
Figure 4: Decomposition of the lattice used for Theorem 13.
by the results in Section 5 below, then the ground space degeneracy, if any, is lifted by perturbations. For
fermionic systems, this only says the ground space is not locally correctable, or a degeneracy-lifting local
operator of fermion parity even or odd should exist.
Theorem 13. For any (δ, `)-correctable code of code distance d on a D-dimensional lattice with Euclidean
geometry of linear size L, there exists a region Y that contains
˜
d qubits such that every logical operator
U can be approximated by an operator V on Y where
k(U − V )Πk ≤ O
p
nδ/d
˜
dd
1
D−1
≤ O(n`
D
D−1
) (37)
If δ becomes exactly zero at some `, independent of L, then the conclusion becomes that of Ref. [11].
Proof. We divide the system as in Fig. 4, where each hypercube is separated by a distance at least `.
Each hypercube in X has linear size at most O(d/`)
1
D−1
, and is at least
O(δ(d/`
D
)
1
D−1
), `
-correctable
by Step 1 in the proof of Theorem 9. The union X of all such squares is O(nδ/d)-correctable by the
union lemma 11. (See Eq. (32)). Then, Theorem 7 (cleaning lemma) implies that the complement, on
which there are O(n)(`/d)
D
D−1
·` · O(d/`) qubits, supports all logical operators to accuracy O(
p
nδ/d) in
operator norm.
4 Flexible strings imply finite degeneracy
Here we apply Theorem 8 to topologically ordered two-dimensional systems, to show that under a mild
condition the degeneracy can be at most a constant independent of system size. This constant degeneracy
holds for all examples we know of with a stable ground state subspace subject to arbitrary perturbations,
and is intimately related to one of the core assumptions of algebraic anyon theories (modular tensor cat-
egories) that there are only finitely many superselection sectors (simple objects). Without the finiteness,
any interesting computation in the algebraic anyon theory would contain an infinite sum, rendering the
theory substantially different from what we understand with the finiteness. For instance Vafa’s theo-
rem [38] stating that the topological spin is rational would not hold without the finiteness.
We consider periodic boundary conditions, though it will not be too important whether the boundary
conditions are open or periodic. The overall topology of the system is a 2-torus. In a topologically ordered
two-dimensional system, it is expected that
14
X
Y
Z
R
Figure 5: Decomposition of the lattice in 2D used to define flexible logical operators. The diameter of
the disk Z is `.
(◦) there exists a complete set of operators acting within the ground space Π (logical operators) such
that they are supported along a narrow strip (string) wrapping around non-contractible loops of the
system.
It is also expected that the string can be bent while implementing the same action on the ground space
as long as the support remains isotopic to the initial one. These properties can be regarded as the
mathematical defining properties of topological order.
Assuming the existence of a complete set of such operators acting within Π, we now bound the
degeneracy. Consider four squares with corners removed that fills the system as in Fig. 5. The corners
are occupied by four regions comprising Z. The two squares on one diagonal comprise X, and the other
two squares comprise Y . The size of a disk in Z has diameter ` so that the two squares in either X
or Y are separated by distance `. According to the property (◦), we can find a complete set of logical
operators supported on XZ since XZ contains two essential non-contractible loops of the torus. It may be
unreasonable to assume that all operators that strictly preserve the ground space are supported entirely
on XZ. Instead, we may reasonably assume that such an operator can be approximated by one that is
supported entirely on XZ, and the approximation becomes better as we increase `.
Hence, we are well motivated to define the notion of flexible logical operators as follows:
Definition 14. A subspace Π on a two-dimensional system admits flexible (logical) operators if for
any logical unitary operator U
XY Z
there exist operators V
Y Z
1
supported on Y Z and V
XZ
2
on XZ such
that kV
i
k ≤ 1, kΠ(U − V
i
)k ≤
`
, and k(U − V
i
)Πk ≤
`
, where i = 1, 2 and
`
is independent of system
size and vanishes as ` → ∞.
From this definition Theorem 8 asserts that the complement Y = (XZ)
c
is
p
5
`
/2-correctable. In-
terchanging X and Y , we conclude that Y is also
p
5
`
/2-correctable. Next, we employ the technique of
Step 3 in the proof of Theorem 9. Recalling the continuity of mutual information Eq. (20), we deduce
that
1 −
˜
O
1/2
`
log dim Π ≤ S(ρ
Z
) ≤ `
2
log 2. (38)
Choosing ` sufficiently large (and hence
`
sufficiently small), we have
dim Π ≤ exp(O(`
2
)). (39)
In summary, the bound on the degeneracy dim Π is determined by the width of the strip that can
support sufficiently faithful logical operators. It is noteworthy that the error from restricting the logical
operator onto the strip only has to be suppressed to an absolute constant. Also, the exponent `
2
being
quadratic in ` is optimal; `
2
copies of the toric code can be laid on a lattice to achieve this quadratic
scaling.
15
We remark that our argument that the assumption of flexible string operators implies constant degen-
eracy is unique to two dimensions in the following sense. A higher dimensional analogue of the flexible
string operators is a set of faithful logical operators supported on noncontractible hypersurfaces. We
can say logical operators are “flexible” if there are equivalent operators on isotopic hypersurfaces. This
applies to every known example of a gapped phase with robust ground state degeneracy. Discrete gauge
theories such as the three-dimensional toric code have surface operators and line operators, all of which
are supported on the union of three deformable planes. In general, however, flexible logical operators on
hypersurfaces do not imply constant degeneracy. As a trivial example one can consider a stack of two-
dimensional toric codes, of which the string operators are lurking within hyperplanes. The degeneracy
(the code space dimension) is exponential in the height of the stack. More complicated examples are
quantum glass or fracton models [39–42], for which the fact that there is a set of faithful logical operators
on planes can be shown by the cleaning lemma (Theorem 7) applied to the bulk. Here, the degeneracy is
exponential in the linear system size, too [43].
5 Robustness of local commuting projector codes
The results so far use properties of subspaces, and do not hinge on particular code constructions. Here we
will show that our results apply to a class of local approximate error correction codes that are in the same
gapped phase as certain exact codes. Let H
0
= −
P
k∈Λ
h
k
be a local unfrustrated commuting projector
Hamiltonian. That is, each term is a projector h
k
= h
2
k
, commutes with any other term [h
k
, h
j
] = 0, and
is supported on a region around site k of diameter less than w (the interaction range), and any ground
state |ψi satisfies h
k
|ψi = |ψi. The code subspace is identified with the ground state subspace of H
0
:
Π =
Q
k∈Λ
h
k
. We summarize the error correction properties of these local commuting projector codes in
the following lemma:
Lemma 15. Let Π be a commuting projector code, and ABC = Λ be decomposition of the lattice such
that the distance between A and C is at least ` ≥ w, the interaction range ( e.g. as in Fig. 3.) Then the
following are equivalent:
(i) Topological Quantum Order (TQO): for any observable O
A
with support on A, any two ground states
|φi and |ψi give the same expectation value, hφ|O
A
|φi = hψ|O
A
|ψi.
(ii) Decoupling: For any ρ ∈ Π, we have I
ρ
(A : CR) = 0.
(iii) Error correction: There exists a recovery map acting on AB such that R
AB
B
(ρ
BC
) = ρ
ABC
for any
ρ ∈ Π.
(iv) Disentangling unitary: For any ρ ∈ Π, there exists a unitary U
B
, such that U
B
ρU
B†
= ω
AB
1
⊗ρ
B
2
C
,
for some state ω
AB
1
.
(v) Cleaning: For any unitary U preserving the code space, there exists a unitary V
BC
such that U |
Π
=
V
BC
|
Π
.
The condition (i) is Knill-Laflamme [29] condition for correctability. The implication from (iii) to (iv)
was derived in Ref. [10] with slightly larger B. The implication from (iv) to (v) was derived in Ref. [11]
with a slightly larger B.
Proof. (i) ⇒ (ii): (i) is equivalent to ΠO
A
Π = c(O
A
)Π for some scalar c(O
A
). Then, it suffices to look
16
at the correlation function between A and C;
hψ|O
A
O
C
|ψi (40)
= hψ|ΠO
A
Y
k:`-away from A
h
k
Y
k:`-away from C
h
k
O
C
Π |ψi (41)
= hψ|ΠO
A
ΠO
C
Π |ψi (42)
= c(O
A
)c(O
C
) = hψ|O
A
|ψihψ|O
C
|ψi. (43)
(ii) ⇔ (iii) ⇔ (iv) by Theorem 3, Corollary 4, and Theorem 5 with δ
`
(A) = 0.
(iii) ⇒ (v) by Theorem 7 with δ = 0.
(v) ⇒ (i): Theorem 8 with δ = 0 implies that the reduced density matrix for A is the same for all
code states.
We now consider sufficiently weak perturbations of commuting projector codes. We assume that the
code distance (Definition 1) grows with the system size by a power law (d = Ω(n
γ
) for some γ > 0). In
addition, we assume that the Hamiltonian H
0
obeys the “local TQO” condition of Refs. [7, 9]. These
conditions ensure that a perturbed Hamiltonian H
1
= H
0
+
P
k
V
k
has a gapped energy spectrum above
the ground state subspace, where the V
k
are local and kV
k
k ≤ for a constant that only depends on the
spatial dimension and the interaction range w, but the V
k
are otherwise arbitrary.
The local TQO condition is similar to the TQO condition, but eliminates effects from the correctable
region’s boundary. H
0
is said to obey local TQO if
Π
A
w
O
A
Π
A
w
= c(O
A
)Π
A
w
(44)
where Π
A
w
=
Y
k:dist(k,A)≤w
h
k
(45)
for any region A of size less than d. In other words, if any state |ψi satisfies h
k
|ψi = |ψi for h
k
around a
correctable region A, then the reduced density matrix for A of |ψi is determined and unique.
The gap stability result implies that for any sufficiently weak perturbation V there is a gap (inde-
pendent of system size) in the energy spectrum of H
1
= H
0
+ V above the m lowest energy eigenstates
where m = dim Π
0
. Furthermore, if Π
1
denotes the projector onto these m lowest energy eigenstates of
H
1
, then there is a locality-preserving unitary U [8, 44, 45] such that
Π
1
= UΠ
0
U
†
, (46)
UO
X
U
†
− V
X
+r
O
X
(V
X
+r
)
†
≤ c
1
O
X
exp
−c
2
r/ log
2
r
. (47)
Here, X is an arbitrary region, and V
X
+r
is strictly supported on the r-neighborhood of X, and c
1
, c
2
> 0
are constants. The particular form of the function on the right-hand side of (47) is from Ref. [45,
Theorem 3.4].
We are now in position to state the main theorem of this section:
Theorem 16. Let H be a local commuting frustration-free Hamiltonian, whose ground state subspace Π
0
is an [[n, k, d]] quantum error correcting code with d = Ω(n
γ
) for some γ > 0. An arbitrary but sufficiently
weak local pertubation of H defines an [[n, k, d − 2`, δ(`), `]] approximate error correcting code Π
1
, where
δ(`) ≤ c
1
e
−c
2
`/ log
2
`
for some constant c
1
, c
2
> 0.
17
Proof. The locality-preserving property of (47) can be cast into a more convenient form in the following.
For any channel X
M
M
on a region M there exists a channel Y
M
+r
M
+r
such that
sup
η
ABCR
B
U
†
X
M
U(η
ABCR
), Y
M
+r
(η
ABCR
)
≤ , (48)
where U denotes the unitary conjugation channel by U , and η is any state, not necessarily a code state.
This claim (48) with =
p
2Ce
−cr/ log
2
r
follows by setting Y = V
M
+r
from (47) and the triangle inequality
of trace norm. Then, we can turn any correcting map for the unperturbed code space to a correcting map
for the perturbed one, by sacrificing the locality and accuracy a little:
Lemma 17. If a region A is (δ, `)-correctable with respect to a code Π, then the region Z = A
−r
is
(δ + 2, ` + 2r)-correctable with respect to the code UΠU
†
.
The lemma is proved in Appendix E.
The locality-preserving unitary U in the sense of Eq. (47) exists under a sole condition that there
exists a gapped Hamiltonian path whose ground spaces are Π
0
and Π
1
[8]. Hence, by Lemma 17, the
notion of locally correctable region is an invariant property of gapped phases of matter.
6 Outlook
In this paper, we have introduced a coherent framework for analyzing local approximate quantum error
correcting codes on lattices, which naturally includes weak local perturbations of commuting projector
codes. Based only on very general properties of recovery maps on the code subspace, we have proved a
tradeoff bound between n, k, d (Theorem 9), and given a constraints on the shape of logical operators
(Theorem 13), resembling the results for commuting projector codes in Ref. [10, 11]. Furthermore, we
have shown that if the logical operators of a code in 2D can be approximated by flexible string operators
of constant width, then the degeneracy of the code subspace is constant, supporting one of the core
assumptions of algebraic anyon theories.
We have assumed that there is one qubit (C
2
) per unit volume of the lattice. One can translate all
our results to a situation where the local Hilbert space dimension is q ≥ 2, simply by redefining the unit
length as 1 → (log q)
1/D
. It is thus important for the last result on the degeneracy bound under the
assumption of flexible strings that the local Hilbert space dimension is finite.
A number of important problems remain open, and we outline a few below.
Eastin and Knill [46] have proved that no exact error correcting code can have a universal set of
transversal gates. This no-go result has been sharpened for local stabilizer codes on lattices by Bravyi
and K¨onig [47], where it was shown that any transversal logical gate in a D-dimensional local stabilizer
code is contained in the Dth level of the Clifford hierarchy. In general, it is important to understand
whether approximate error correcting codes would provide an avenue to local universal fault-tolerance in
2D or 3D that circumvents these no-go results.
As remarked in the Introduction, our notion of local recovery map is in part motivated by topological
systems with anyons where pair-annihilation amounts to error recovery. We indeed have shown that
the local recovery map exists for the ground space of a local commuting projector Hamiltonian and its
perturbation. However, we have not explicitly discussed any larger class of phases of mattter that do
not necessarily have commuting Hamiltonian representatives, yet have a ground space that is a local
approximate quantum error correcting code. One may wonder if, for any gapped Hamiltonian with stable
gap against perturbations, the ground space can be regarded as a local approximate error correcting code.
A more concrete problem would be to ask about the optimal relation between the parameters ` and δ
under the local TQO condition for unfrustrated Hamiltonians [7].
18
Since our code is identified with a subspace of a physical Hilbert space, we have excluded subsystem
codes [48] or more general subalgebra codes [49]. Also neglected is the thermal encoding, which has been
studied in regards to self-correcting quantum memory [50–52]. B´eny and Oreshkov [23, 49] have discussed
information-disturbance tradeoffs for subalgebra codes, but it remains to be seen how these would apply
with the local recovery maps. Extensions to these more general error correction schemes with approximate
recovery maps might be relevant in connection to field theories with holographic duals [53, 54].
Acknowledgments
STF was supported by the Australian Research Council via EQuS project number CE11001013 and by
an Australian Research Council Future Fellowship FT130101744. JH was supported by the Pappalardo
Fellowship in Physics while at MIT. MJK was supported by the Carlsberg fund and the Villum foundation.
IK’s research at Perimeter Institute was supported by the Government of Canada through Industry
Canada and by the Province of Ontario through the Ministry of Economic Development and Innovation.
References
[1] B. M. Terhal, “Quantum error correction for quantum memories,” Rev. Mod. Phys. 87, 307 (2015),
arXiv:1302.3428 .
[2] D. Gottesman, “An introduction to quantum error correction and fault-tolerant quantum compu-
tation,” in Quantum Information Science and Its Contributions to Mathematics, Vol. 68, edited by
S. J. Lomonaco, Jr. (American Mathematical Society, 2010) pp. 24–69, arXiv:0904.2557 .
[3] D. W. Leung, M. A. Nielsen, I. L. Chuang, and Y. Yamamoto, “Approximate quantum error cor-
rection can lead to better codes,” Phys. Rev. A 56, 2567–2573 (1997).
[4] C. Cr´epeau, D. Gottesman, and A. Smith, “Approximate quantum error-correcting codes and secret
sharing schemes,” in Advances in Cryptology – EUROCRYPT 2005: 24th Annual International Con-
ference on the Theory and Applications of Cryptographic Techniques, Aarhus, Denmark, May 22-26,
2005. Proceedings, edited by R. Cramer (Springer Berlin Heidelberg, Berlin, Heidelberg, 2005) pp.
285–301, quant-ph/0503139 .
[5] G. Moore and N. Read, “Nonabelions in the fractional quantum hall effect,” Nuclear Physics B 360,
362–396 (1991).
[6] A. Kitaev, “Anyons in an exactly solved model and beyond,” Annals of Physics 321, 2–111 (2006),
cond-mat/0506438 .
[7] S. Michalakis and J. P. Zwolak, “Stability of frustration-free Hamiltonians,” Communications in
Mathematical Physics 322, 277–302 (2013), arXiv:1109.1588 .
[8] M. B. Hastings and X.-G. Wen, “Quasiadiabatic continuation of quantum states: The stability of
topological ground-state degeneracy and emergent gauge invariance,” Physical Review B 72, 045141
(2005), cond-mat/0503554 .
[9] S. Bravyi, M. B. Hastings, and S. Michalakis, “Topological quantum order: stability under local
perturbations,” Journal of Mathematical Physics 51, 093512 (2010), arXiv:1001.0344 .
[10] S. Bravyi, D. Poulin, and B. Terhal, “Tradeoffs for reliable quantum information storage in 2D
systems,” Phys. Rev. Lett. 104, 050503 (2010), arXiv:0909.5200 .
19
[11] J. Haah and J. Preskill, “Logical operator tradeoff for local quantum codes,” Phys. Rev. A 86, 032308
(2012), 1011.3529 .
[12] C. G. Brell, S. T. Flammia, S. D. Bartlett, and A. C. Doherty, “Toric codes and quantum doubles
from two-body Hamiltonians,” New Journal of Physics 13, 053039 (2011), arXiv:1011.1942 .
[13] B. Criger and B. Terhal, “Noise thresholds for the [4,2,2]-concatenated toric code,” Quant. Inf.
Comput. 16, 1261 (2016), arXiv:1604.04062 .
[14] I. H. Kim and M. J. Kastoryano, “Entanglement renormalization, quantum error correction, and
bulk causality,” (2017), arXiv:1701.00050 .
[15] S. Bravyi and B. Terhal, “A no-go theorem for a two-dimensional self-correcting quantum memory
based on stabilizer codes,” New Journal of Physics 11, 043029 (2009), arXiv:0810.1983 .
[16] N. Delfosse, “Tradeoffs for reliable quantum information storage in surface codes and color codes,”
in 2013 IEEE International Symposium on Information Theory (Institute of Electrical & Electronics
Engineers (IEEE), 2013) arXiv:1301.6588 .
[17] S. Bravyi, “Subsystem codes with spatially local generators,” Phys. Rev. A 83, 012320 (2011),
arXiv:1008.1029 .
[18] D. Bacon, S. T. Flammia, A. W. Harrow, and J. Shi, “Sparse Quantum Codes from Quantum
Circuits,” in Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing,
STOC ’15 (ACM Press, New York, NY, USA, 2015) pp. 327–334, arXiv:1411.3334 .
[19] C. Cafaro and P. van Loock, “Approximate quantum error correction for generalized amplitude-
damping errors,” Phys. Rev. A 89, 022316 (2014), arXiv:1308.4582 .
[20] Y. Ouyang, “Permutation-invariant quantum codes,” Phys. Rev. A 90, 062317 (2014),
arXiv:1302.3247 .
[21] M. Grassl, L. Kong, Z. Wei, Z.-Q. Yin, and B. Zeng, “Quantum Error-Correcting Codes for Qudit
Amplitude Damping,” arXiv:1509.06829 (2015), arXiv:1509.06829 .
[22] B. Schumacher and M. D. Westmoreland, “Approximate quantum error correction,” Quant. Info.
Process. 1, 5–12 (2002), quant-ph/0112106 .
[23] C. B´eny and O. Oreshkov, “General conditions for approximate quantum error correction and near-
optimal recovery channels,” Phys. Rev. Lett. 104, 120501 (2010), arXiv:0907.5391 .
[24] H. K. Ng and P. Mandayam, “Simple approach to approximate quantum error correction based on
the transpose channel,” Phys. Rev. A 81, 062342 (2010), arXiv:0909.0931 .
[25] J. C. Bridgeman, S. T. Flammia, and D. Poulin, “Detecting Topological Order with Ribbon Oper-
ators,” Phys. Rev. B 94, 205123 (2016), arXiv:1603.02275 .
[26] C. T. Chubb and S. T. Flammia, “Approximate symmetries of Hamiltonians,” (2016),
arXiv:1608.02600 .
[27] A. Uhlmann, “The “transition probability” in the state space of a ∗-algebra,” Reports on Mathe-
matical Physics 9, 273–279 (1976).
20
[28] C. A. Fuchs and J. van de Graaf, “Cryptographic distinguishability measures for quantum-mechanical
states,” IEEE Trans. Inf. Theory 45, 1216 (1999), quant-ph/9712042 .
[29] E. Knill and R. Laflamme, “Theory of quantum error-correcting codes,” Phys. Rev. A 55, 900–911
(1997).
[30] D. Kretschmann, D. Schlingemann, and R. F. Werner, “The information-disturbance tradeoff and the
continuity of Stinespring’s representation,” IEEE Transactions on Information Theory 54, 1708–1717
(2008), quant-ph/0605009 .
[31] P. Hayden and A. Winter, “Weak decoupling duality and quantum identification,” IEEE Transactions
on Information Theory 58, 4914–4929 (2012), arXiv:1003.4994 .
[32] B. Schumacher and M. A. Nielsen, “Quantum data processing and error correction,” Phys. Rev. A
54, 2629–2635 (1996), quant-ph/9604022 .
[33] A. Y. Kitaev, A. H. Shen, and M. N. Vyalyi, Classical and Quantum Computation (American
Mathematical Society, 2002).
[34] M. M¨uller-Lennert, F. Dupuis, O. Szehr, S. Fehr, and M. Tomamichel, “On quantum R´enyi entropies:
a new generalization and some properties,” J. Math. Phys. 54, 122203 (2013), arXiv:1306.3142 .
[35] S. Beigi, “Sandwiched R´enyi divergence satisfies data processing inequality,” J. Math. Phys. 54,
122202 (2013), arXiv:1306.5920 .
[36] B. Yoshida and I. L. Chuang, “Framework for classifying logical operators in stabilizer codes,” Phys.
Rev. A 81, 052302 (2010), arXiv:1002.0085 .
[37] J. Preskill, “Quantum error correction, Lecture notes for Physics 219, Caltech,” (1999).
[38] C. Vafa, “Toward classification of conformal theories,” Physics Letters B 206, 421–426 (1988).
[39] C. Chamon, “Quantum glassiness,” Phys. Rev. Lett. 94, 040402 (2005), cond-mat/0404182 .
[40] S. Bravyi, B. Leemhuis, and B. M. Terhal, “Topological order in an exactly solvable 3D spin model,”
Annals of Physics 326, 839–866 (2011), arXiv:1006.4871 .
[41] J. Haah, “Local stabilizer codes in three dimensions without string logical operators,” Phys. Rev. A
83, 042330 (2011), arXiv:1310.4507 .
[42] S. Vijay, J. Haah, and L. Fu, “A new kind of topological quantum order: A dimensional hierarchy
of quasiparticles built from stationary excitations,” Phys. Rev. B 92, 235136 (2015), 1505.02576 .
[43] J. Haah, “Commuting Pauli Hamiltonians as maps between free modules,” Commun. Math. Phys.
324, 351–399 (2013), arXiv:1204.1063 .
[44] M. B. Hastings, “Lieb-Schultz-Mattis in higher dimensions,” Physical Review B 69, 104431 (2004),
cond-mat/0305505 .
[45] S. Bachmann, S. Michalakis, B. Nachtergaele, and R. Sims, “Automorphic equivalence within gapped
phases of quantum lattice systems,” Communications in Mathematical Physics 309, 835–871 (2012),
arXiv:1102.0842 .
[46] B. Eastin and E. Knill, “Restrictions on transversal encoded quantum gate sets,” Physical Review
Letters 102, 110502 (2009), arXiv:0811.4262 .
21
[47] S. Bravyi and R. K¨onig, “Classification of topologically protected gates for local stabilizer codes,”
Phys. Rev. Lett. 110, 170503 (2013), arXiv:1206.1609 .
[48] D. Poulin, “Stabilizer formalism for operator quantum error correction,” Phys. Rev. Lett. 95, 230504
(2005), quant-ph/0508131 .
[49] C. B´eny, “Conditions for the approximate correction of algebras,” in Theory of Quantum Computa-
tion, Communication, and Cryptography (Springer, 2009) pp. 66–75, arXiv:0907.4207 .
[50] E. Dennis, A. Kitaev, A. Landahl, and J. Preskill, “Topological quantum memory,” Journal of
Mathematical Physics 43, 4452–4505 (2002), quant-ph/0110143 .
[51] R. Alicki, M. Horodecki, P. Horodecki, and R. Horodecki, “On thermal stability of topological qubit
in kitaev’s 4d model,” Open Systems & Information Dynamics 17, 1–20 (2010), arXiv:0811.0033 .
[52] B. J. Brown, D. Loss, J. K. Pachos, C. N. Self, and J. R. Wootton, “Quantum memories at finite
temperature,” Rev. Mod. Phys. 88, 045005 (2016), arXiv:1411.6643 .
[53] F. Pastawski, B. Yoshida, D. Harlow, and J. Preskill, “Holographic quantum error-correcting codes:
Toy models for the bulk/boundary correspondence,” Journal of High Energy Physics 2015, 149
(2015), arXiv:1503.06237 .
[54] D. Harlow, “The Ryu-Takayanagi formula from quantum error correction,” (2016), arXiv:1607.03901
.
[55] K. M. R. Audenaert, “A sharp continuity estimate for the von Neumann entropy,” Journal of Physics
A: Mathematical and Theoretical 40, 8127–8136 (2007), quant-ph/0610146 .
[56] R. Alicki and M. Fannes, “Continuity of quantum conditional information,” J. Phys. A: Math. Gen.
37, L55–L57 (2004), quant-ph/0312081 .
A Proof of Theorem 3: Information-disturbance tradeoff
Theorem 18 (More general version of Theorem 3). Let Π be a subspace on QC, and R a purifying space
for Π. Given a Stinespring purification V
QE
of a channel N : ρ 7→ Tr
E
(V
QE
ρV
QE†
) for ρ = Πρ = ρΠ,
let N
c
: ρ 7→ Tr
Q
(V
QE
ρV
QE†
) be the complementary channel. Similarly, fix a purification W
QE
of a
channel M on Q, and define the complementary channel M
c
. Then, we have
inf
R
sup
ρ
QCR
B
M(ρ
QCR
), R◦ N(ρ
QCR
)
= inf
S
sup
ρ
QCR
B
S ◦ M
c
(ρ
QCR
), N
c
(ρ
QCR
)
. (49)
This theorem with the subsystem C being empty (C = C) was stated in Ref. [23]. The proof in
Ref. [23] omits the last step to replace an operator of norm at most 1 with a unitary operator [30]. Our
statement is only different from that of Ref. [23] in that it includes a subsystem C explicitly. This enables
us to accommodate locality. The domain and the codomain of the channels N, M being the same is
mere convenience of presentation; more general cases reduce to the present one. The theorem implies in
particular that when a code is defined on a physical system ABC (Q = AB), if N = Tr
A
, N
c
= Tr
B
,
M = id, and M
c
outputs a fixed state ω, then
inf
R
AB
B
sup
ρ
ABCR
B
ρ
ABCR
, R
AB
B
(ρ
BCR
)
= inf
ω
A
sup
ρ
ABCR
B
ω
A
⊗ ρ
CR
, ρ
ACR
, (50)
which is Theorem 3.
22
Proof. Let X
QE
0
denote a purification of the channel R. The new environment E
0
is arbitrary here,
unlike the subsystem E that is fixed by our choice of the complementary channel. Any channel (CPTP
map) with d
i
-dimensional input and d
o
-dimensional output can be represented with a (d
i
d
o
)-dimensional
environment, which implies that the domain of all channels R and S is compact. However, for the present
proof, it is useful to note that the optimizations over the channels R, S are with arbitrary environments.
Since the fidelity F = 1−B
2
is concave in the arguments, the maximization over ρ
QCR
can be restricted
to pure states ρ
QCR
. Assuming ρ
QCR
is pure, let us express the fidelity on the left-hand side of Eq. (49)
using Uhlmann’s theorem.
LHS = sup
X
QE
0
inf
ρ
QCR
sup
Y
EE
0
hρ
QCR
0
EE
0
|W
QE†
Y
EE
0
X
QE
0
V
QE
|ρ
QCR
0
EE
0
i (51)
= sup
X
QE
0
inf
ρ
Q
sup
Y
EE
0
Tr
h
ρ
Q
0
EE
0
W
QE†
Y
EE
0
X
QE
0
V
QE
i
(52)
In the second line, the domain of ρ
Q
is convex. (Indeed, tρ
Q
1
+(1 −t)ρ
Q
2
is reduced from tρ
QC
1
+(1 −t)ρ
QC
2
,
where ρ
QC
1,2
are some code states from the definition of ρ
Q
1,2
, which can be purified using R.) Even if we
relax the domain of Y
QE
0
to those of the operator Z
QE
0
of norm at most 1, the inner-most supremum
always occurs when Z
QE
0
is a unitary. This follows because sup
U:kU k≤1
Re Tr AU = kAk
1
for any matrix
A where the supremum is achieved by a unitary from the singular value decomposition of A. After such
a relaxation, we can apply the minimax theorem to the bilinear objective function to obtain
LHS = sup
X
QE
0
sup
Z
EE
0
inf
ρ
Q
Tr
h
ρ
Q
0
EE
0
W
QE†
Z
EE
0
X
QE
0
V
QE
i
(53)
= sup
X
QE
0
sup
Z
EE
0
inf
ρ
Q
Tr
h
ρ
Q
0
E
W
QE†
h0
E
0
|Z
EE
0
X
QE
0
|0
E
0
iV
QE
i
. (54)
The second line is a rearrangement to make the linear operator h0
E
0
|Z
EE
0
X
QE
0
|0
E
0
i : QE → QE
more visible. Since Z
EE
0
has norm at most 1, we can introduce another subsystem E
00
= C
2
and
find a unitary S
EE
0
E
00
such that Z
EE
0
= h0
E
00
|S
EE
0
E
00
|0
E
00
i by Lemma 20 below. Then we can replace
h0
E
0
|Z
EE
0
X
QE
0
|0
E
0
i with h0
E
0
E
00
|S
QE
0
E
00
(X
QE
0
I
E
00
) |0
E
0
E
00
i. Treating E
0
E
00
as a larger environment E
0
,
which was arbitrary, we see that the maximin value of (54) with arbitrary E
0
can be achieved by unitary
Z
EE
0
and X
QE
0
.
The RHS of the theorem can be manipulated symmetrically with the role of X
QE
0
and Y
EE
0
inter-
changed, eventually leading to (54) exactly. The completes the proof of the theorem.
Using the Fuchs-van de Graaf relation
F
2
+ T
2
≤ 1 ≤ F + T,
we recover Theorem 3 of Ref. [30]:
Corollary 19. For any (noise) channel N, we have
1
4
inf
R
kR ◦ N − idk
2
≤ inf
P
kN
c
− Pk
≤ 2 inf
R
kR ◦ N − idk
1/2
(55)
where P denotes any completely depolarizing channel.
Lemma 20. For any matrix M
A
such that kMk ≤ 1, there exists a unitary V
AB
such that h0
B
|V
AB
|0
B
i =
M
A
where B = C
2
.
23
Proof. Let M = XDY be a singular value decomposition of M with X, Y being unitary. If we had the
lemma proved for the diagonal D, then multiplying X
A
⊗ I
B
and Y
A
⊗ I
B
will prove the lemma in the
general case. Hence, it suffices to prove the lemma for any non-negative diagonal M .
By assumption, the non-negative diagonal elements of M are ≤ 1. The operator V
AB
has four blocks
hi
B
|V
AB
|j
B
i where i, j = 0, 1. Define h0
B
|V
AB
|0
B
i = M, and h1
B
|V
AB
|0
B
i =
√
1 − M
2
. Then the
columns of V
AB
|0
B
i are orthonormal. There exists a basis of the vector space on AB that extends
V
AB
|0
B
i, which can be used to fill the block V
AB
|1
B
i.
B Proof of Theorem 5: Decoupling-Correctability
Lemma 21. Two numbers
µ = sup
ρ
ABCR
B(ρ
ACR
, ρ
A
⊗ ρ
CR
), (56)
δ = inf
ω
A
sup
ρ
ABCR
B(ρ
ACR
, ω
A
⊗ ρ
CR
). (57)
satisfy
1
9
δ
2
≤ µ ≤ 2δ. (58)
Proof. That µ ≤ 2δ follows because B(ρ
A
, ω
A
) ≤ δ by the monotonicity of the Bures distance. For the
other inequality, we will show
ρ
A
− σ
A
1
≤ 2(2 +
√
2)µ (59)
for any code states ρ
ABCR
and σ
ABCR
. This implies that B(ρ
A
, σ
A
) ≤
q
(2 +
√
2)µ, and therefore
δ ≤ sup
ρ
ABCR
B(ρ
ACR
, σ
A
⊗ ρ
CR
) (60)
≤ B(ρ
ACR
, ρ
A
⊗ ρ
CR
) +
q
(2 +
√
2)µ (61)
≤
1 +
q
2 +
√
2
√
µ. (62)
Consider sup
ρ,σ
ρ
A
− σ
A
1
. Since for every ρ
A
there is a code state ρ
ABC
that reduces to ρ
A
, we may
regard the domain of optimization to be the set of mixed code states ρ
ABC
. Since the trace distance is
convex in its both arguments, the supremum occurs at extreme points, which are pure states. So, we only
need to consider the case |ρ
ABC
i =
√
a |σ
ABC
i +
√
1 − a |η
ABC
i where
σ
ABC
η
ABC
= 0 and a ∈ [0, 1].
Define
|ψ
ABCR
i :=
1
√
2
|σ
ABC
0
R
i + |η
ABC
1
R
i
. (63)
Then,
∆ := ψ
AR
− ψ
A
⊗ ψ
R
=
1
2
(σ
A
− η
A
)/2 Tr
BC
|σ
ABC
ihη
ABC
|
| {z }
Y
Tr
BC
|η
ABC
ihσ
ABC
|
| {z }
Y
†
−(σ
A
− η
A
)/2
. (64)
24
Since kXk
1
= sup
U
Re Tr(XU), we see
2
√
2µ ≥ sup
U
Re Tr
∆
U 0
0 −U
(65)
=
1
2
sup
U
Re Tr[(σ
A
− η
A
)U] =
1
2
σ
A
− η
A
1
, (66)
and also
2
√
2µ ≥ sup
U
Re Tr
∆
0 U
U 0
=
1
2
Y + Y
†
1
. (67)
Therefore,
ρ
A
− σ
A
1
=
(a − 1)σ
A
+ (1 − a)η
A
+
p
a(1 − a)(Y + Y
†
)
1
(68)
≤ (1 − a)
σ
A
− η
A
1
+
p
a(1 − a)
Y + Y
†
1
(69)
≤ 4
√
2(1 − a)µ + 4
√
2
p
a(1 − a)µ (70)
≤ 2(2 +
√
2)µ. (71)
C Proof of Theorem 7: Cleaning Lemma and Correctability
Let R be a purifying system for the code space Π.
Lemma 22 (A local error correction map is a local cleaning map.). Let A be a region of the physical
system ABC. Suppose there exists a channel R
AB
B
such that
sup
ρ
ABC
R
AB
B
(ρ
BC
) − ρ
ABC
1
≤ . (72)
Then, for any operator U
ABC
that is not necessarily logical, the pull-back V
BC
= (R
AB
B
)
∗
(U
ABC
) satisfies
V
BC
≤
U
ABC
(73)
Π(U
ABC
− V
BC
)Π
≤ 2
U
ABC
. (74)
In addition, if U
ABC
is a logical unitary, then V
BC
= R
∗
(U
ABC
) satisfies
V
BC
≤ 1 (75)
(U
ABC
− V
BC
)Π
≤ 4
√
(76)
(U
ABC†
− V
BC†
)Π
≤ 4
√
(77)
where Π is the projector onto the code space.
Proof. Since V
BC
= (W
AB
B
)
†
U
ABC
W
AB
B
for some Stinespring isometry W
AB
B
, it follows that
V
BC
≤
U
ABC
. Whenever U
ABC
is hermitian, V
BC
is also hermitian. Since V
BC†
= (R
AB
B
)
∗
(U
ABC†
), (77) will
follow from (76).
25
First, we estimate the norm restricted to the code space assuming U
ABC
is hermitian.
Π(U
ABC
− V
BC
)Π
= sup
ρ
ABC
Tr(ρ
ABC
(U
ABC
− V
BC
))
(78)
= sup
ρ
ABC
Tr(ρ
ABC
U
ABC
− R
AB
B
(ρ
BC
)U
ABC
)
(79)
= sup
ρ
ABC
Tr((ρ
ABC
− R
AB
B
(ρ
BC
))U
ABC
)
(80)
≤ sup
ρ
ABC
ρ
ABC
− R
AB
B
(ρ
BC
)
1
U
ABC
(81)
≤
U
ABC
. (82)
For general U
ABC
, decompose U
ABC
into hermitian and anti-hermitian parts, and use the triangle in-
equality for the operator norm. This proves Eq. (74).
To prove Eq. (76), let |ψi = Π |ψi be any normalized code state. If α =
ΠV
BC
|ψi
2
and β =
(I − Π)V
BC
|ψi
2
, then α ≥ 1−2 by Eq. (74) and the unitarity of U
ABC
. Since
V
BC
≤
U
ABC
= 1,
we see α
2
+ β
2
≤ 1. Hence, β
2
≤ 1 − α
2
≤ 1 − (1 − 2)
2
≤ 4, and
(I − Π)V
BC
Π
≤ 2
√
. (83)
Therefore,
(U
ABC
− V
BC
)Π
≤
(I − Π)(U
ABC
− V
BC
)Π
+
Π(U
ABC
− V
BC
)Π
(84)
≤ 2
√
+ 2 (85)
≤ 4
√
(86)
Lemma 23 (A cleanable region is correctable.). Suppose for any unitary U
AB
that preserves the code
space there exists an operator V
B
supported on B such that
V
B
≤ 1, (87)
(U
AB
− V
B
)Π
≤ , (88)
(U
AB†
− V
B†
)Π
≤ . (89)
Then, for any code state ρ
ABR
with purifying space R
ρ
AR
− ω
A
⊗ ρ
R
1
≤ 5. (90)
Proof. Using the triangle inequality and the fact that kP Qk
1
, kQPk
1
≤ kP k
1
· kQk, we have
U
AB
ρ
ABR
U
AB†
− V
B
ρ
ABR
V
B†
1
≤
U
AB
ρ
ABR
(U
AB†
− V
B†
)
1
(91)
+
(U
AB
− V
B
)ρ
ABR
V
B†
1
(92)
≤ 2, (93)
V
B†
V
B
Π − Π
=
V
B†
ΠV
B
Π − U
AB†
ΠU
AB
Π + V
B†
(I − Π)V
B
Π
(94)
≤
(V
B†
− U
AB†
)ΠV
B
Π + U
AB†
Π(V
B
− U
AB
)Π
(95)
+
V
B†
(I − Π)(V
B
− U
AB
)Π
(96)
≤ 3. (97)
26
Since a partial trace cannot increase the trace distance, we see
ρ
AR
− Tr
B
U
AB
ρ
ABR
U
AB†
1
≤
ρ
AR
− Tr
B
V
B
ρ
ABR
V
B†
1
+ 2 (98)
=
ρ
AR
− Tr
B
V
B†
V
B
Πρ
ABR
1
+ 2 (99)
≤
ρ
AR
− Tr
B
ρ
ABR
1
+ 5 (100)
= 5 (101)
where U
AB
is an arbitrary unitary that preserves the code space. A completely depolarizing channel over
the code space can be written as
Z
dU
AB
U
AB
ρ
ABR
U
AB†
= ρ
R
⊗ Π/ Tr(Π) (102)
where the integral is over the group of all logical unitaries. Using Eq. (101), we see that
Z
dU
AB
h
ρ
AR
− Tr
B
U
AB
ρ
ABR
U
AB†
i
1
≤
Z
dU
AB
ρ
AR
− Tr
B
U
AB
ρ
ABR
U
AB†
1
(103)
≤ 5 . (104)
Let ω
A
= Tr
B
Π/ Tr(Π). Then,
ρ
AR
− ω
A
⊗ ρ
R
1
=
Z
dU
AB
ρ
AR
− ω
A
⊗ ρ
R
1
(105)
≤
Z
dU
AB
Tr
B
(U
AB
ρ
ABR
U
AB†
) − ω
A
⊗ ρ
R
1
+ 5 (106)
= 5. (107)
D Proof of Theorem 4: Disentangling Unitary
Lemma 24. Let Π be a code space on ABC, and R be a purifying space. Let V
B
0
B
00
B
= V ·V
†
denote any
isometry channel, where B
0
is some auxiliary system and B
00
is a copy of AB. Then,
inf
ω
A
sup
ρ
ABCR
B(ρ
ACR
, ω
A
⊗ ρ
CR
) = inf
ω
AB
0
,V
B
0
B
00
B
sup
ρ
ABCR
B(V
B
0
B
00
B
(ρ
ABCR
), ω
AB
0
⊗ ρ
B
00
CR
) (108)
where ρ
B
00
CR
is the same as ρ
ABCR
but supported on B
00
instead of AB.
Proof of 24 as a corollary of the information-disturbance theorem. That LHS ≤ RHS follows at once
because the Bures distance can only decrease by tracing out B
0
B
00
.
For the other direction, we need to find an isometry and a state ω
AB
0
that yields the desired minimax
value. Since B
2
is convex in its arguments, the supremum over ρ
ABCR
always occurs at a pure state, and
thus we can only consider when ρ
ABCR
is pure. The information-disturbance theorem (Thm. 3) provides
a recovery map R
AB
B
to fidelity 1−δ
2
where δ = LHS. Let V = V
ABE
B
be a Stinespring isometry of R
AB
B
.
The fidelity being at least 1 − δ
2
means that
hω
DE
ρ
ABCR
|V
ABE
B
|ρ
DBCR
i
≥ 1 − δ
2
(109)
27
for some pure state ω
DE
where ρ
DBCR
is the same as ρ
ABCR
but supported on DBCR instead of ABCR.
Interchanging the subsystem label D and A, we have
hω
AE
ρ
DBCR
|V
DBE
B
|ρ
ABCR
i
≥ 1 − δ
2
. (110)
Now we set B
0
= E and B
00
= DB to finish the proof.
Conversely, the recovery map with respect to the noise Tr
A
in the information-disturbance theorem
can be constructed using the disentangling isometry V
B
0
B
00
B
. Suppose the initial pure state is ρ
ABCR
. The
noise erases A, and we are confronted with ρ
BCR
. Applying V, we have, to fidelity ≥ 1 −δ
2
, ω
B
0
⊗ρ
B
00
CR
.
Discarding B
0
and mapping B
00
to AB isomorphically, the recovery succeeds with fidelity ≥ 1 − δ
2
.
Direct Proof of 24. That LHS ≤ RHS follows at once because the Bures distance can only decrease by
tracing out B
0
B
00
.
To show δ := LHS ≥ RHS, fix an ω
A
that achieves the LHS in Eq. (108).
inf
ρ
ABCR
F(ρ
ACR
, ω
A
⊗ ρ
CR
) = 1 − δ
2
(111)
Since the fidelity is concave in its arguments, the infimum occurs at a pure state ρ
ABCR
. Introduce
purification auxiliary systems D and EF where EF is a copy of AB. We apply Uhlmann’s theorem with
purifications ω
AD
0
B
of ω
A
and ρ
EF CR
of ρ
CR
. Define S = S
†
to be the swap operator between AB and
EF . Then we have,
1 − δ
2
= inf
pure ρ
ABCR
sup
W
BDEF
Re hω
AD
0
B
ρ
EF CR
|W
BDEF
|ρ
ABCR
0
DEF
i (112)
= inf
pure ρ
ABCR
sup
W
BDEF
Re hω
ED
0
F
ρ
ABCR
|S
ABEF
W
BDEF
|ρ
ABCR
0
DEF
i (113)
= inf
ρ
ABC
sup
W
BDEF
Re Tr
S
ABEF
W
BDEF
ρ
ABC
|0
DEF
ihω
ED
0
F
|
. (114)
In the last expression, the domain of ρ
ABC
is the set of all code states, which is convex. The domain of
W
BDEF
is the set of all unitaries, but can be relaxed to the set of all operators U on BDEF of operator
norm ≤ 1, which is convex, since the supremum occurs at a unitary. The minimax theorem can then be
applied since the objective function is linear in both arguments.
Reversing the manipulation, we have
1 − δ
2
= sup
U
BDEF
inf
pure ρ
ABCR
Re hω
AD
0
B
ρ
EF CR
|U
BDEF
|ρ
ABCR
0
DEF
i. (115)
Here the optimal operator U is not necessarily a unitary. However, the supremum value can be reached
by a unitary because for any operator U with kUk ≤ 1 there is a unitary V such that U
BDEF
=
h0
D
0
|V
BDD
0
EF
|0
D
0
i due to Lemma 20. The latter amounts to a larger choice of the purifying space D
for ω
A
. Hence, for this choice of V , the fidelity between two states on RHS of Eq. (108) is at least 1 −δ
2
.
This is to say that RHS ≤ δ = LHS. Therefore, the claim is proved with V
B
0
B
00
B
= V
BDEF
|0
DEF
i where
B
0
= BD and B
00
= EF .
E Proof of Lemma 17
Proof. Let R
AB
B
be a recovery map for Tr
A
:
sup
ρ
ABCR
B
R
AB
B
(ρ
BCR
), ρ
ABCR
= δ. (116)
28
Let B
i
= A ∩ B
+r
and B
o
= C ∩ B
+r
, so that B
+r
= B
i
BB
o
. Also, let Z = A \ B
+r
= A \ B
i
. We will
show that there exists a recovery channel T = T
ZB
+r
B
+r
for the code UΠU
†
such that
sup
σ
ZB
i
BCR
∈ UΠU
†
⊗R
B
T (σ
B
i
BCR
), σ
ZB
i
BCR
≤ 2 + δ. (117)
Although the domain of R
AB
B
is the set of all states supported on B, we may regard the channel R
AB
B
as
the composition of the complete depolarization E
A
A
on A, followed by a channel D
AB
AB
. That is, R
AB
B
(σ
B
) =
D
AB
AB
◦ E
A
A
(σ
AB
) for any state σ
AB
that partial-traces to σ
B
. We will use this trick in what follows.
We wish to recover from the erasure of the “interior” Z = A \ B
+r
for the code U ΠU
†
. We consider
the following channel S, which is going to be a recovery map,
S(σ
B
i
BCR
) = U ◦ D ◦ U
†
(I
Z
/d
Z
⊗ σ
B
i
BCR
) . (118)
We first calculate the fidelity of the recovery by S. Let σ
ZB
i
BCR
= U(ρ
ABCR
) be an arbitrary code
state in UΠU
†
, possibly entangled with reference system R. The recovery is successful up to error
B
S(σ
B
i
BCR
), σ
ZB
i
BCR
(119)
= B
U
†
◦ S ◦ E
Z
Z
◦ U(ρ
ZB
i
BCR
), ρ
ZB
i
BCR
(120)
= B
DU
†
E
Z
Z
U(ρ
ZB
i
BCR
), ρ
ZB
i
BCR
. (121)
U is locality-preserving, and the channel U
†
E
Z
Z
U can be replaced by a channel E
0
on Z
+r
= A at the cost
of additional error at most . Hence, we can bound the error as
B
S(σ
B
i
BCR
), σ
ZB
i
BCR
≤ + B
D ◦ E
0
(ρ
ABCR
), ρ
ABCR
(122)
= + δ (123)
where the last step is because Tr
A
E
0
(ρ
ABCR
) = ρ
BCR
.
Now we investigate the support of S. By assumption on U , the composition U ◦ D ◦ U
†
can be
approximated by a channel T
0
supported on (AB)
+r
= ABB
o
to an error . Since the domain of S is
restricted to the states on B
i
BCR, we may say that there exists T
ZB
i
BB
o
B
i
BB
o
that recovers the erasure of Z
for the code UΠU
†
to error 2 + δ.
F Continuity of mutual information
The Fannes-Audeanaert inequality [55] reads
|S(ρ) − S(σ)| ≤ H(t) + t log(d − 1) (124)
for any d-dimensional states ρ and σ, where t =
1
2
kρ − σk
1
, and H(t) = −t log t −(1 − t) log(1 −t) is the
binary entropy function.
Alicki and Fannes [56] have proved that when t =
1
2
ρ
AB
− σ
AB
1
<
1
2
,
S(ρ
AB
) − S(ρ
B
) − S(σ
AB
) + S(σ
B
)
≤ 2H(2t) + 8t log d
A
(125)
where d
A
is the dimension of the subsystem A.
29
Assume that subsystems A and B are nontrivial. It follows that the difference of the mutual informa-
tion is bounded as
|I
ρ
(A : B) − I
σ
(A : B)| =
S(ρ
A
) − S(σ
A
) − S(ρ
A|B
) − S(σ
A|B
)
(126)
≤ H(t) + t log(d
A
− 1) + 2H(2t) + 8t log d
A
(127)
≤ 9t log d
A
+ 6t log(1/t) (128)
≤ 9t log(d
A
/t) . (129)
Since the mutual information is symmetric, d
A
can be replaced by min(d
A
, d
B
) ≥ 2.
30
Published in Quantum on 25th April 2017: https://doi.org/10.22331/q-2017-04-25-4