Logical operator tradeoff for local quantum codes

Show preview

Hide preview

Logical operator tradeoff for local quantum codes
Jeongwan Haah and John Preskill Institute for Quantum Information and Matter, California Institute of Technology, Pasadena, California 91125, USA
(Dated: 2 July 2012)
We study the structure of logical operators in local D-dimensional quantum codes, considering both subsystem codes with geometrically local gauge generators and codes defined by geometrically local commuting projectors. We show that if the code distance is d, then any logical operator can be supported on a set of specified geometry containing d˜ qubits, where d˜d1/(D−1) = O(n) and n is the code length. Our results place limitations on partially self-correcting quantum memories, in which at least some logical operators are protected by energy barriers that grow with system size. We also show that for any two-dimensional local commuting projector code there is a nontrivial logical “string” operator supported on a narrow strip, where the operator is only slightly entangling across any cut through the strip.
PACS numbers: 03.67.Pp, 03.67.Lx
I. INTRODUCTION
Geometrically local quantum codes provide intriguing models of quantum many-body physics, and also have potential applications to fault-tolerant quantum compu- tation in systems with short-range interactions. There has been impressive recent progress in understanding the properties of such codes. Bravyi, Poulin, and Terhal [1] showed that for codes defined by geometrically local com- muting projectors in D dimensions, the code length n, distance d and number of encoded qubits k are related by
kd2/(D−1) = O(n).
Bravyi and Terhal [2] showed that
d = O(n(D−1)/D)
for subsystem codes with geometrically local gauge gen- erators, and Bravyi [3] showed that
kd = O(n)
for two-dimensional subsystem codes with geometrically local gauge generators.
Bravyi and Terhal [2], and Kay and Colbeck [4], also showed that no two-dimensional local stabilizer code can be a self-correcting quantum memory — if we regard the code as a system governed by a local Hamiltonian, the energy barrier protecting against logical errors is a con- stant independent of system size. A self-correcting mem- ory based on a geometrically local stabilizer code is pos- sible in four dimensions [5, 6], where the storage time increases sharply as the system size grows. In three di- mensions there are codes such that the energy barrier in- creases logarithmically with system size [7, 8], but where the storage time is bounded above by a constant inde- pendent of system size [9].
We address a related but somewhat different question. To illustrate the question, consider the three-dimensional toric code [10], on a cubic lattice with linear size L. This
code provides different degrees of protection against dif- ferent types of errors. For example, we can arrange for the logical bit flip acting on the code space to have weight L (i.e., to be supported on a set of L qubits), while the logical phase flip has weight L2. In that case, the en- ergy barrier protecting against logical phase errors grows linearly with L, though the energy barrier protecting against bit flips is only a constant. We might say this system is partially self correcting, meaning it has very ro- bust physical protection against phase errors, but weaker protection against bit flips.
We find limitations on partial self correction in two- dimensional local subsystem codes with local stabilizer generators; in particular the logical phase flip must have weight O(L) if the logical bit flip has weight Ω(L). More generally, we study how the code distance d constrains the weight of logical operators, for both local commut- ing projector codes and subsystem codes, finding that d limits not just the weight of the lowest-weight logical op- erator but also the higher-weight logical operators. Let us say that two logical operators are equivalent if they act in the same way on the protected system. Our re- sult, which applies to both local subsystem codes and to local commuting projector codes in D ≥ 2 dimensions, says that for any logical operator there is an equivalent logical operator with weight d˜ such that
d˜d1/(D−1) = O(LD) (1)
where L is the linear size of the lattice. We call this result the tradeoff theorem for logical operators, since, e.g., increasing the weight of the lowest-weight logical operator reduces the upper bound on the weight of other logical operators. One immediate consequence is that, since d ≤ d˜,
d = O(LD−1),
a result previously known for local subsystem codes but not for local commuting projector codes with D ≥ 3. For D = 2 the tradeoff becomes dd˜ = O(L2), and hence d = O(L).
ar X
iv :1
01 1.
35 29
v3 [
qu an
t-p h]
3 Ju
l 2 01
2

2 We also show that for any two-dimensional local commuting projector code there is a nontrivial logical “string” operator supported on a narrow strip (or on a narrow slab in higher dimensions), where the operator is only slightly entangling across any cut through the strip. However, we have not settled the question whether two- dimensional local commuting projector codes can be self correcting.
We review the theory of stabilizer codes and subsys- tem codes in Sec. II. In Sec. III we prove a “Clean- ing Lemma” for subsystem codes previously stated by Bravyi [3]; our proof uses tools developed by Yoshida and Chuang [11], and may be of independent interest. We prove the tradeoff theorem for local subsystem codes in Sec. IV and for local commuting projector codes in Sec. V. In Sec. VI we show that any two-dimensional commuting projector code admits a nontrivial logical “string” operator supported on a narrow strip. In Sec. VII we explain why partial self-correction is impossible for two-dimensional local stabilizer codes with distance d = Ω(L). In Sec. VIII we show that the logical string operator in a two-dimensional local commuting projector code can be chosen to be slightly entangling across any cut through the string. Sec. IX contains our conclusions.
II. BACKGROUND: STABILIZER AND SUBSYSTEM CODES
A stabilizer code [12, 13] embeds k protected qubits in the Hilbert space of n physical qubits. The code has a stabilizer group S, an abelian subgroup with n − k independent generators of the n-qubit Pauli group P , and the code is the simultaneous eigenspace with eigenvalue 1 of all elements of S.
It is convenient to abelianize P by ignoring the phase in the product of two Pauli operators, thus obtaining a 2n- dimensional vector space over the binary field, which we also denote by P . The vector space P is equipped with a symplectic form, such that two vectors are orthogonal if and only if the corresponding Pauli operators commute. If G is a subgroup of P , we use the symbol G to denote both the subgroup and the corresponding subspace of P .
Viewed as a vector space, S is (n−k)-dimensional. We denote by S⊥ the vector space orthogonal to S, which has dimension 2n − (n − k) = n + k. It can be decomposed as a direct sum of S and a 2k dimensional vector space corresponding to the logical Pauli group, which acts non- trivially on the k protected qubits. We define the weight of a Pauli operator as the number of qubits on which the operator acts nontrivially, and the distance d of the sta- bilizer code is the minimum weight of a nontrivial logical operator (one contained in S⊥ but not in S).
A subsystem code [14, 15] can be viewed as a stabilizer code with k+g encoded qubits, but where only k of these qubits are used to store protected quantum information. The stabilizer group S together with Pauli operators act- ing on the g unused qubits generate the code’s gauge
group G. Equivalently, we may say that the subsystem code is defined by its gauge group G ≤ P , and that the code’s stabilizer group S = G∩G⊥ is the subgroup of G that commutes with all elements of G.
Logical operations in the subsystem code preserve the 2k-dimensional Hilbert space spanned by the k protected qubits. We distinguish between bare logical operators, which act trivially on the gauge qubits, and dressed log- ical operators, which may act nontrivially on the gauge qubits as well as the protected qubits. Thus, nontrivial bare logical operators are in G⊥ but not in G, while non- trivial dressed logical operators are in S⊥ but not in G. The code distance d is the minimum weight of a nontriv- ial dressed logical operator.
A bare logical operator x ∈ G⊥ acts trivially on the protected qubits as well as the gauge qubits if and only if x ∈ G⊥ ∩ G = S; hence we may regard G⊥/S as the group of bare logical operators. A dressed logical opera- tor x ∈ S⊥ acts trivially on the protected qubits (but perhaps nontrivially on the gauge qubits) if and only if x ∈ G; hence we may regard S⊥/G as the group of dressed logical operators, where we regard two dressed logical operators as equivalent if they act the same way on the protected qubits. We denote by [G] the dimen- sion of the vector space G (the number of independent generators of the corresponding group); by counting the number of independent bare logical operators, we find that the number k of protected qubits satisfies
2k = [G⊥/S] = [G⊥]− [S] = [P ]− [G]− [S] = 2n− [G]− [S].
Similarly, by counting the number of independent dressed logical operators, we find
2k = [S⊥/G] = [S⊥]− [G] = [P ]− [S]− [G] = 2n− [S]− [G].
A stabilizer code is the special case of a subsystem code in which G = S, and in that case, k = n− [S].
We will also consider stabilizer codes and subsystem codes of the CSS type [16, 17], where each generator of the gauge group, and each logical operator, may be cho- sen to be either of the X-type or the Z-type. We use PX
(PZ) to denote the group of X-type (Z-type) Pauli op- erators, GX (GZ) to denote the X-type (Z-type) gauge group, and SX (SZ) to denote the X-type (Z-type) sta- bilizer group. We use (GX)⊥ to denote the subgroup of PZ that commutes with GX , etc. Then the group of bare Z-type logical operators is (GX)⊥/SZ and the group of bare X-type logical operators is (GZ)⊥/SX . Therefore the number k of protected qubits is
k = [(GX)⊥/SZ ] = n− [GX ]− [SZ ], k = [(GZ)⊥/SX ] = n− [GZ ]− [SX ].
We wish to study stabilizer codes in which the sta- bilizer generators are geometrically local and subsystem codes in which the gauge generators are geometrically

3 local. To be concrete, we may imagine that the qubits reside at the vertices of a D-dimensional hypercubic lat- tice (with either open or periodic boundary conditions), and that each generator acts nontrivially only inside a hypercube (containing wD vertices) with linear size w. In fact our results can be easily extended to codes with geometrically local generators defined on any graph em- bedded in D-dimensional space. Note that for a sub- system code the stabilizer generators might be nonlocal even if the gauge generators are local. Some of our re- sults also apply to a larger class of local codes that in- cludes local stabilizer codes. For this class, which we call local commuting projector codes, the code space is the simultaneous eigenspace with eigenvalue one of a set of mutually commuting geometrically local projection op- erators, where the projectors do not necessarily project onto eigenspaces of Pauli operators. A local stabilizer code, but not a local subsystem code, is a special case of a local commuting projector code.
III. CLEANING LEMMA FOR SUBSYSTEM CODES
The Cleaning Lemma for subsystem codes relates the number of independent bare logical operators supported on a set of qubits M to the number of independent dressed logical operators supported on the complemen- tary set M c. The concept of the Cleaning Lemma was introduced in [2], then generalized in [11] and [3]. Here we use ideas from [11] to prove a version stated in [3]. (See also [18].) As in the Sec. II, we will regard a sub- group of the Pauli group as a vector space, allowing us to obtain the Cleaning Lemma from straightforward di- mension counting.
We use PA to denote the subgroup of the Pauli group P supported on a set A of qubits; likewise for any subgroup G of the Pauli group GA = G ∩ PA, is the subgroup of G supported on A. We denote by ΠA : P → PA the restriction map that maps a Pauli operator to its restriction supported on the set A, and we use |A| to denote the number of qubits contained in A; thus [PA] = 2|A|.
If we divide n qubits into two complementary sets A and B, then a subgroup G of P can be decomposed into GA, GB , and a “remainder,” as follows:
Lemma 1. (Decomposition of Pauli subgroups) Suppose that A and B are complementary sets of qubits. Then for any subgroup G of the Pauli group,
G = GA ⊕GB ⊕G′
for some G′, where
[(G⊥)A] = 2|A| − [GA]− [G′], [(G⊥)B ] = 2|B| − [GB ]− [G′]
Proof. If V is a vector space and W is a subspace of V , then there is a vector space V ′ such that V = W ⊕ V ′;
we may choose V ′ to be the span of the basis vectors that extend a basis for W to a basis for V . Since GA and GB are disjoint, i.e., GA ∩GB = {0}, GA ⊕GB is a subspace of G, and thus there exists an auxiliary vector space G′ ≤ G such that
G = GA ⊕GB ⊕G′.
The choice of G′ is not canonical, but we need only its existence. Since the restriction map ΠA obviously anni- hilates GB , we may regard it as a map from GA ⊕ G′ onto ΠAG. In fact this map is injective. Note that if ΠAx = 0 for some x ∈ GA⊕G′. then since P = PA⊕PB it must be that x ∈ GB . But because the sum is direct, i.e. GB ∩ (GA ⊕G′) = {0}, it follows that x = 0, which proves injectivity. Hence ΠA : GA ⊕ G′ → ΠAG is an isomorphism. Now, we may calculate (G⊥)A by solving a system of linear equations. Noting that x ∈ PA is con- tained in G⊥ if and only if x commutes with the restric- tion to A of each element of G, we see that the number of independent linear constraints is [ΠAG] = [GA] + [G
′]; hence [(G⊥)A] = [PA]− [GA]− [G′] = 2|A| − [GA]− [G′]. Likewise, ΠB : GB ⊕ G′ → ΠBG is also an isomor- phism, and hence [(G⊥)B ] = [PB ] − [GB ] − [G′] = 2|B| − [GB ]− [G′].
Now we are ready to state and prove the Cleaning Lemma. For a subsystem code, let gbare(M) be the num- ber of independent non-trivial bare logical operators sup- ported on M , and let g(M) be the number of indepen- dent non-trivial dressed logical operators supported on M , i.e.,
gbare(M) = [G ⊥ ∩ PM/SM ] = [(G⊥)M/SM ],
g(M) = [S⊥ ∩ PM/GM ] = [(S⊥)M/GM ].
Likewise, for a CSS subsystem code, let gXbare(M) be the number of independent non-trivial bare X-type logical operators supported on M , and let gX(M) be the num- ber of independent non-trivial dressed X-type logical op- erators supported on M , i.e.,
gXbare(M) = [(G Z)⊥ ∩ PXM/SXM ],
gX(M) = [(SZ)⊥ ∩ PXM/GXM ],
and similarly for the Z-type logical operators.
Lemma 2. (Cleaning Lemma for subsystem codes) For any subsystem code, we have
gbare(M) + g(M c) = 2k, (2)
where M is any set of qubits and M c is its complement. Moreover, for a CSS subsystem code
gXbare(M) + g Z(M c) = k = gZbare(M) + g
X(M c). (3)

4 Proof. We use Lemma 1 to prove the Cleaning Lemma by a direct calculation:
gbare(M) = [(G ⊥)M/SM ]
= 2|M | − [GM ]− [G′]− [SM ], and
g(M c) = [(S⊥)Mc/GMc ] = 2|M c| − [SMc ]− [S′]− [GMc ].
Summing, we find
gbare(M) + g(Mc) = 2|M |+ 2|Mc| − ([GM ] + [GMc ] + [G′]) − ([SM ] + [SMc ] + [S′])
and invoking Lemma 1 once again,
gbare(M) + g(Mc) = 2n− [G]− [S] = 2k, which proves the claim for general subsystem codes. For the CSS case, we apply the analogue of Lemma 1 to the X-type and Z-type Pauli operators, finding
gZbare(M) = [(G X)⊥ ∩ PZM/SZM ]
= |M | − [GXM ]− [(GX)′]− [SZM ] and also
gX(M c) = [(SZ)⊥ ∩ PXMc/GXMc ] = |M c| − [SZMc ]− [(SZ)′]− [GXMc ].
Summing and using Lemma 1 we have
gZbare(M) + g X(M c) = n− [GX ]− [SZ ] = k;
a similar calculation yields
gXbare(M) + g Z(M c) = n− [GZ ]− [SX ] = k,
proving the claim for CSS subsystem codes.
Of course, for a stabilizer code there is no distinction between bare and dressed logical operators; the state- ment of the Cleaning Lemma becomes
g(M) + g(M c) = 2k
for general stabilizer codes, and
gX(M) + gZ(M c) = k
for CSS stabilizer codes. To understand how the Cleaning Lemma gets its name,
note that it implies that if no bare logical operator can be supported on the set M then all dressed logical op- erators can be supported on its complement M c. That is, any of the code’s dressed logical Pauli operators can be “cleaned up” by applying elements of the gauge group
G. The cleaned operator acts the same way on the pro- tected qubits as the original operator (though it might act differently on the gauge qubits), and acts trivially on M .
We say that a region M is correctable if erasure of the qubits in M is a correctable error. For a subsystem code, it follows that no nontrivial dressed logical operators are supported on M if M is correctable; hence g(M) = 0 and thus gbare(M) = 0. The Cleaning Lemma then asserts that all dressed logical operators can be supported on M c. Let us say that two dressed logical operators x and y are equivalent if x = yz and z is an element of the gauge group G, so that x and y act the same way on the protected qubits. We have obtained:
Lemma 3. (Cleaning Lemma for dressed logical opera- tors) For any subsystem code, if M is a correctable region and x is a dressed logical operator, then there is a dressed logical operator y supported on M c that is equivalent to x.
IV. OPERATOR TRADEOFF FOR LOCAL SUBSYSTEM CODES
In this section we consider local subsystem codes with qubits residing at the sites of a D-dimensional hypercu- bic lattice Λ. The code has interaction range w, meaning that the generators of the gauge group G can be chosen so that each generator has support on a hypercube con- taining wD sites.
Definition 1. Given a set of gauge generators for a sub- system code, and a set of qubits M , let M ′ denote the support of all the gauge generators that act nontrivially on M . The external boundary of M is ∂+M = M
′ ∩M c, where M c is the complement of M , and the internal boundary of M is ∂−M = (M c)
′ ∩ M . The boundary of M is ∂M = ∂+M ∪ ∂−M , and the interior of M is M◦ = M \ ∂−M .
Recall that a region (i.e., set of qubits) M is said to be correctable if no nontrivial dressed logical operation is supported on M , in which case erasure of M can be corrected. Since the code distance d is defined as the minimum weight of a dressed logical operator, M is cer- tainly correctable if |M | < d. But in fact much larger regions are also correctable, as follows from this lemma:
Lemma 4. (Expansion Lemma for local subsystem codes) For a local subsystem code, if M and A are both correctable, where A contains ∂M , then M ∪ A is cor- rectable.
Proof. Given a subsystem code C with gauge group G, we may define a subsystem code CMc on M c with gauge group ΠMcG, where ΠMc maps a Pauli operator to its restriction supported on M c. We note that a Pauli op- erator x supported on M c is a bare logical operator for C if and only if x is a bare logical operator for CMc ; that

5 is, x commutes with all elements of G if and only if it commutes with all elements of the restriction of G to M c.
Furthermore, if x is a dressed logical operator for CMc supported on ∂+M , then x can be extended to a dressed logical operator x¯ for C supported on ∂M . Indeed, sup- pose x = yz, where y is a bare logical operator for CMc (and hence also a bare logical operator for C supported on M c), while z is an element of the gauge group ΠMcG of CMc . Then z can be written as a product z =
∏ i gi of
generators of ΠMcG, each of which can be expressed as gi = ΠMc g¯i, where g¯i is a generator of G supported on M c∪∂−M . Thus x¯ = y
∏ i g¯i is a dressed logical operator
for C supported on ∂M . It follows that if ∂M is correctable for the code C (i.e,
code C has no nontrivial dressed logical operators sup- ported on ∂M), then ∂+M is correctable for the code CMc (CMc has no nontrivial dressed logical operators sup- ported on ∂+M). By similar logic, if A is correctable for C and contains ∂M , then A ∩M c is correctable for CMc .
Suppose now that the code C has k encoded qubits and that M is correctable, i.e. g(C)(M) = 0. There- fore, applying Lemma 2 to the code C, g(C)bare(M c) = 2k. Suppose further that the set A containing ∂M is cor- rectable for C, implying that A ∩M c is correctable for CMc , i.e. g(CMc )(A ∩M c) = 0. Then applying Lemma 2 to the code CMc , we conclude that g(CMc )bare (M c \A) = 2k. Since each bare logical operator for CMc , supported on M c \ A, is also a bare logical operator for C, supported on M c \ A, we can now apply Lemma 2 once again to the code C, using the partition into M c \ A and M ∪ A, finding g(C)(M ∪A) = 0. Thus M ∪A is correctable.
If the interaction range is w, and M is a correctable hypercube with linear size l − 2(w − 1), then we may choose A ⊇ ∂M so that M ∪A is a hypercube with linear size l and M\A is a hypercube with linear size l−4(w−1). Then A contains
|A| = lD − [l − 4(w − 1)]D ≤ 4(w − 1)DlD−1
qubits, and A is surely correctable provided |A| < d, where d is the code distance. Suppose that d > 1, so a single site is correctable. Applying Lemma 4 repeatedly, we can build up larger and larger correctable hypercubes, with linear size 1+2(w−1), 1+4(w−1), 1+6(w−1), . . . . This process continues as long as |A| < d. We conclude: Lemma 5. (Holographic Principle for local subsystem codes) For a D-dimensional local subsystem code with interaction range w > 1 and distance d > 1, a hypercube with linear size l is correctable if
4(w − 1)DlD−1 < d. (4)
Thus (roughly speaking) for the hypercube to be cor- rectable it suffices for its [2(w − 1)]-thickened boundary, rather than its volume, to be smaller than the code dis- tance. Bravyi [3] calls this property “the holographic
FIG. 1: (Color online) Lattice covering used in the proof of Theorem 1, shown in two dimensions. Each gray square is l × l and the white gap between squares has width w − 1. The solid blue curve represents the support of a nontrivial logical operator; because the square Mi is correctable, this square can be “cleaned” — we can find an equivalent logical operator supported on Mci , the complement of Mi. When all squares are cleaned, the logical operator is supported on the narrow strips between the squares.
principle for error correction,” because the absence of in- formation encoded at the boundary of a region ensures that no information is encoded in the “bulk.” For local stabilizer codes, the criterion for correctability is slightly weaker than for local subsystem codes, as we discuss in Appendix A.
Now we are ready to prove our first tradeoff theorem.
Theorem 1. (Tradeoff Theorem for local subsystem codes) For a local subsystem code in D ≥ 2 dimensions with interaction range w > 1 and distance d� w, defined on a hypercubic lattice with linear size L, every dressed logical operator is equivalent to an operator with weight d˜ satisfying
d˜d1/(D−1) < cLD, (5)
where c is a constant depending on w and D.
Proof. As shown in Fig. 1, we fill the lattice with hyper- cubes, separated by distance w−1, such that each hyper- cube has linear size l satisfying eq.(4). (By “distance” we mean the number of sites in between — e.g. we say that adjacent sites are “distance zero” apart.) Thus no gauge generator acts nontrivially on more than one hypercube, and each hypercube is correctable by Lemma 5. Consider any nontrivial dressed logical operator x, and label the hypercubes {M1,M2,M3, . . . }. By Lemma 3 there exists a gauge operator yi that “cleans” the logical operator in the hypercube Mi, i.e., such that xyi acts trivially in Mi. Furthermore, since no gauge generator acts nontrivially on more than one hypercube, we can choose yi so that it acts trivially in all other hypercubes. Taking the product of all the yi’s we construct a gauge operator that cleans all hypercubes simultaneously; thus x˜ = x
∏ i yi is equiv-
alent to x and supported on the complement of the union of hypercubes M = ∪iMi. Therefore, the weight d˜ of x˜ is upper bounded by |M c|.

6 The lattice is covered by hypercubes of linear size l + (w − 1), each centered about one of the Mi’s. There are LD/ [l + (w − 1)]D such hypercubes in this union, each containing no more than [l + (w − 1)]D − lD ≤ (w − 1)D [l + (w − 1)]D−1 elements of M c. Thus
d˜ ≤ |M c| ≤ (w − 1)D [l + (w − 1)]D−1 L D
[l + (w − 1)]D
= (w − 1)D l + (w − 1)L
D.
We optimize this upper bound on d˜ by choosing l to be the largest integer such that a hypercube with linear size l is known to be correctable, i.e., satisfying
l <
( d
4(w − 1)D )1/(D−1)
,
thus obtaining eq.(5). Note that eq.(5) is trivial if d is a
constant independent of L, since the weight d˜ cannot be larger than LD.
V. OPERATOR TRADEOFF FOR LOCAL COMMUTING PROJECTOR CODES
In this section we consider a local commuting projector code, defined as the simultaneous eigenspace with eigen- value one of a set of commuting projectors. As in Sec. IV we assume that the qubits reside on a hypercubic lattice Λ and that each projector acts trivially outside a hyper- cube of linear size w, where w is the interaction range. By a logical operator we mean any transformation that preserves the code space, and we say that two logical op- erators are equivalent if they have the same action on the code space. The weight of a logical operator is the number of qubits on which it acts nontrivially. We say that a set of qubits M is correctable if erasure of M can be reversed by a trace-preserving completely positive re- covery map. The distance d of the code is the minimum size of a noncorrectable set of qubits.
Bravyi, Poulin, and Terhal [1] proved some useful prop- erties of these codes. To state their results, we use the definition
Definition 2. Given a set of commuting projectors defining a code, and a set of qubits M , let M ′ denote the support of all the projectors that act nontrivially on M . The external boundary of M is ∂+M = M
′ ∩M c, where M c is the complement of M , and the internal boundary of M is ∂−M = (M c)
′ ∩ M . The boundary of M is ∂M = ∂+M ∪ ∂−M , and the interior of M is M◦ = M \ ∂−M . Lemma 6. (Disentangling Lemma [1]) Consider a local commuting projector code and suppose that M and ∂+M are both correctable regions. Then there exists a unitary
operator U∂M acting only on the boundary ∂M such that, for any pure code vector |ψ〉,
U∂M |ψ〉 = |φM 〉 ⊗ |ψ′Mc〉. (6)
Here |φM 〉, supported on M , does not depend on the code vector |ψ〉, while |ψ′Mc〉, supported on M c, does depend on |ψ〉. The Disentangling Lemma says that, if M and ∂+M are both correctable, then the entanglement of code vectors across the cut between M and M c is localized in ∂M and can be removed by a unitary transformation acting on only ∂M . Furthermore, in the resulting product state, no information distinguishing one code vector from an- other is available in M . This Lemma has a simple but important corollary:
Lemma 7. (Expansion Lemma for local commuting pro- jector codes [1]) For a local commuting projector code, if M and A are both correctable, where A contains ∂M , then M ∪A is correctable. Proof. By eq.(6), if A is erased the resulting state on M \ A is independent of the code vector |ψ〉; all the in- formation needed to reconstruct |ψ〉 resides in M c \ A. Therefore, we can erase M \ A as well without compro- mising our ability to reconstruct |ψ〉; that is, M ∪ A is correctable.
Definition 2 and Lemma 7 for commuting projector codes are parallel to Definition 1 and Lemma 4 for subsys- tem codes. Arguing as in the proof of Lemma 5, we see that one consequence is a holographic principle for these codes:
Lemma 8. (Holographic Principle for local commuting projector codes) For a D-dimensional local commuting projector code with interaction range w > 1 and distance d > 1, a hypercube with linear size l is correctable if
4(w − 1)DlD−1 < d. (7)
We will need an analog of the Cleaning Lemma to an- alyze the logical operator tradeoff for local commuting projector codes; it can be derived from the Disentangling Lemma.
Lemma 9. (Cleaning Lemma for local commuting pro- jector codes) Consider a local commuting projector code, and suppose that M and ∂+M are both correctable. For any logical operator W there exists an equivalent logical operator V supported on the complement of the interior M◦ of M . If W is an isometry, then V can be chosen to be unitary.
Proof. Let us name the regions:
A =M◦ = M \ ∂−M, B =∂−M, C =∂+M, D =(ABC)
c.

7 Let {|αi〉} be an orthonormal basis for the code space. By Lemma 6, there exists a unitary transformation UBC , and vectors |φ〉AB , {|α′i〉CD} such that
|αi〉 = UBC |φ〉AB ⊗ |α′i〉CD, where the normalized vector |φ〉AB does not depend on i and the vectors {|α′i〉CD} are normalized and mutu- ally orthogonal. Because W is a logical operator, |βi〉 ≡ W |αi〉 is also a code vector, and therefore
|βi〉 = UBC |φ〉AB ⊗ |β′i〉CD where {|β′i〉CD} is another set of vectors; if W is an isometry then these vectors, too, are normalized and mutually orthogonal. Define a transformation V ′ by |β′i〉CD = V ′|α′i〉CD, and choose an arbitrary extension so that V ′ becomes an operator on CD. If W is an isom- etry, then this extension V ′CD can be chosen to be unitary. We now have
W |αi〉 = |βi〉 = UBC(IAB ⊗ V ′CD)|φ〉AB ⊗ |α′i〉CD = UBC(IAB ⊗ V ′CD)U†BC |αi〉
for all i. Defining
V(M◦)c = UBC(IAB ⊗ V ′CD)U†BC , we observe that V(M◦)c acts trivially on A = M
◦ and has the same action on code vectors as W , completing the proof.
To prove the tradeoff theorem we will need a further lemma establishing that a union of correctable sets is correctable under suitable conditions. Recall that we say a set of qubits M is correctable if and only if erasure of M can be corrected. Equivalently, M is correctable if and only if, for any operator O supported on M ,
ΠOΠ = cOΠ (8) where Π denotes the projector onto the code space and cO is a constant (possibly zero) depending on O [19]. Lemma 10. (The union of separated correctable regions is correctable) For a local commuting projector code, sup- pose that M and N are correctable regions such that no projector acts nontrivially on both M and N . Then M ∪N is also correctable. A weaker version of this lemma was proved in [1].
Proof. Let S be the set of local commuting projectors that define the code. We denote by S ′N the set of projec- tors in S that act nontrivially on N . Define
ΠN ′ = ∏
Πa∈S′N Πa,
ΠcN ′ = ∏
Πa∈S\S′N Πa,
and note that the projector onto the code space is
Π = ∏
Πa∈S Πa = ΠN ′Π
c N ′ .
Also note that the support of ΠN ′ does not intersect M and the support of ΠcN ′ does not intersect N . Let O be an arbitrary operator supported on M ∪N ; we will show that O satisfies eq.(8). Since M and N are disjoint, O has a Schmidt decomposition
O = ∑ α
OαM ⊗OαN
where each OαM is supported on M and each OαN is sup- ported on N . Since ΠN ′ commutes with OαM and ΠcN ′ commutes with OαN ,
ΠOΠ = ∑ α
Π(ΠN ′)OαMOαN (ΠcN ′)Π
= ∑ α
ΠOαM (ΠN ′)(ΠcN ′)OαNΠ
= ∑ α
(ΠOαMΠ) (ΠOαNΠ)
= ∑ α
cOαM cOαNΠ
= cOΠ
where in the fourth equality we used the correctability of M andN . ThusO obeys eq.(8), andM∪N is correctable.
Now we are ready to state and prove our second trade- off theorem.
Theorem 2. (Tradeoff Theorem for local commuting projector codes) For a local commuting projector code in D ≥ 2 dimensions with interaction range w > 1 and dis- tance d � w, defined on a hypercubic lattice with linear size L, every logical operator is equivalent to an operator with weight d˜ satisfying
d˜d1/(D−1) < cLD, (9)
where c is a constant depending on w and D.
Proof. The proof is similar to the proof of Theorem 1. We fill the lattice with hypercubes, separated by dis- tance w − 1, where each hypercube Mi has linear size l sufficiently small so that Mi and ∂+Mi are both cor- rectable. Applying Lemma 10 repeatedly, we conclude that the union M of all Mi is correctable, and the union ∂+M of all ∂+Mi is correctable.
For any logical operator, Lemma 9 now ensures the ex- istence of an equivalent logical operator supported out- side the interior M◦ of M , and hence the weight d˜ of this equivalent logical operator is bounded above by |(M◦)c|. The lattice is covered by hypercubes with linear size l+ (w−1), each centered about one of the Mi, and there

8 are LD/ [l + (w − 1)]D such hypercubes, each containing no more than
[l + (w − 1)]D − [l − 2(w − 1)]D
≤ 3(w − 1)D [l + (w − 1)]D−1
elements of (M◦)c; therefore,
d˜ ≤ |(M◦)c|
≤ 3(w − 1)D [l + (w − 1)]D−1 L D
[l + (w − 1)]D
= 3(w − 1)D l + (w − 1)L
D.
To ensure that Mi and ∂+Mi are correctable, it suffices that |∂Mi| < d, where d is the code distance, or
|∂Mi| ≤ [l + 2(w − 1)]D − [l − 2(w − 1)]D
≤ 4(w − 1)D [l + 2(w − 1)]D−1 < d. We choose the largest such integer value of l, obtaining eq.(9).
VI. “STRING” OPERATORS FOR LOCAL COMMUTING PROJECTOR CODES
Because the code distance d is defined as the size of the smallest noncorrectable set, and because a set supporting a nontrivial logical operator is noncorrectable, we have d ≤ d˜ and hence Theorem 2 implies
d = O(LD−1).
In fact we can make a stronger statement, specifying the geometry of a region that supports a nontrivial log- ical operator with weight O(LD−1). On the hypercube {1, 2, 3, . . . L}D, we refer to the set {i, i + 1, . . . , i + r − 1} × {1, 2, 3, . . . , L}D−1 as a slab of width r. Let us say that a code is nontrivial if the code space dimension is greater than one. Then:
Lemma 11. (Existence of a noncorrectable thin slab) For a nontrivial local commuting projector code in D ≥ 1 dimensions with interaction range w > 1, there is a noncorrectable slab of width 3(w − 1). Proof. Suppose, contrary to the claim, that any slab of width 3(w − 1) is correctable. Choose a correctable slab M of width 3(w − 1). The boundary ∂M of M is con- tained in two slabs ML and MR, each of width 2(w− 1). Hence ML and MR are both correctable, and since M has width 3(w− 1), ML and MR are separated by w− 1. Therefore, no local projector acts on both ML and MR, and by Lemma 10, ML ∪MR ⊇ ∂M is correctable. Then Lemma 7 implies that the slab M ∪ML ∪MR of width 5(w − 1) is correctable. Repeating the argument, we see that if a slab M of width r is correctable, so is the slab of width r + 2(w − 1) containing M .
If the system obeys open boundary conditions, then by induction the entire lattice is correctable. If the lattice is periodic, we may consider two thick correctable slabs M1,M2 such thatM1∪M2 is the entire lattice and ∂M1 ⊆ M2; in that case Lemma 7 implies that the entire lattice M1 ∪ M2 is correctable. For either type of boundary condition, then, there are no nontrivial logical operators at all. But we assumed that the code is nontrivial, and therefore reach a contradiction.
It follows from Lemma 11 that the distance d of a local commuting projector code satisfies
d ≤ 3(w − 1)LD−1. It was previously known that d ≤ wLD−1 for a local sta- bilizer code [2, 4] and d ≤ 3wLD−1 for a local subsystem code [2].
Now we may wonder about the geometry of a set that supports a nontrivial logical operator. For a subsystem code, there is a nontrivial logical operator supported by any noncorrectable set, but this statement is not true for general codes (see Appendix B). We say that an operator O is a logical operator if it preserves the code space, and that it is a nontrivial logical operator if it preserves the code space and its restriction to the code space is not proportional to the identity. From the definition of correctability, then, M is not correctable if it supports a nontrivial logical operator. But for some codes the converse is false. IfM is not correctable, then an operator O exists that fails to satisfy eq.(8); however O might not preserve the code space.
But for a local commuting projector code, a correctable set can be extended to a slightly larger set that does support a nontrivial logical operator. Suppose the code is the simultaneous eigenspace with eigenvalue one of a set of commuting projectors S = {Πa}. For any set of qubits M , we define M ′ as the support of all the projectors that act nontrivially on M . Then if M is noncorrectable a nontrivial unitary logical operator is supported on M ′.
Lemma 12. (Support for nontrivial logical operator) For a commuting projector code, if the set M is not cor- rectable, then there is a nontrivial unitary logical operator supported on M ′ that commutes with every projector in S. Proof. Let Π =
∏ Πa∈S Πa be the projector onto the code
space. We claim that there exists a Pauli operator PM supported on M such that ΠPΠ is not proportional to Π. Indeed, if M is not correctable, then there exists an operator OM supported on M such that ΠOMΠ 6∝ Π. Expanding OM =
∑ i ciP
(i) M as a linear combination of
Pauli operators, we see that at least one Pauli operator
P (j) M must satisfy ΠP
(j) M Π 6∝ Π.
We denote by S ′M the set of projectors in S that act nontrivially on M , and define
ΠM ′ = ∏
Πa∈S′M Πa.

9 We claim that
H = ΠM ′PMΠM ′ , is a nontrivial Hermitian logical operator supported on M ′.
To see that H is a logical operator, note that if Πa ∈ S ′M , then ΠaΠM ′ = ΠM ′ = ΠM ′Πa, because Π2a = Πa; hence
ΠaH = H = HΠa, i.e., Πa commutes with H. If Πa 6∈ S ′M , then Πa is sup- ported in the complement M c of M ; hence it commutes trivially with PM , and therefore also with H. Since H commutes with each projector in S, it certainly com- mutes with Π and hence preserves the code space. Fur- thermore, because
ΠHΠ = ΠPMΠ, H acts on the code space in the same way as ΠPMΠ, and therefore must be nontrivial.
Thus U = exp (−iλH) preserves the code space and is unitary for any real λ. Since H, restricted to the code space, has at least two distinct eigenvalues, the same is true of U for a generic choice of λ; i.e., U is a nontrivial unitary logical operator.
Lemmas 11 and 12 now imply:
Theorem 3. (A logical operator is supported on one thin slab) For a nontrivial local commuting projector code in D ≥ 1 dimensions, with interaction range w > 1, there is a nontrivial unitary logical operator (commuting with all projectors) supported on a slab of width 5(w − 1). Note that, though the proof of Theorem 3 establishes the existence of a logical operator supported on a slab of constant width, it provides no algorithm for constructing the operator.
In D = 2 dimensions, the slab becomes a strip of con- stant width stretching across the L× L code block, and the logical operator supported on the strip may be called a “string” operator. It was previously known that for D = 2 a string operator can be supported on a strip of width w in a local stabilizer code [2, 4], and of width 3w in a local subsystem code [2].
VII. TWO-DIMENSIONAL LOCAL STABILIZER CODES ARE NOT PARTIALLY SELF
CORRECTING
Theorems 1 and 2 constrain the weight of logical op- erators, but the proofs tell us more — they specify the geometry of a region that supports a logical operator. This geometry has further implications for the physical robustness of quantum memories.
Consider a subsystem code whose stabilizer group S has a set of geometrically local generators {Sa}, where
the qubits reside at the sites of a D-dimensional hyper- cubic lattice with linear size L. The generating set {Sa} might be overcomplete, but we assume that the number of generators acting nontrivially on each qubit is a con- stant independent of L. The local Hamiltonian
H = − ∑ a
1
2 (Sa − I) , (10)
has a 2k+g-fold degenerate ground state with energy E = 0, where k is the number of protected qubits and g is the number of gauge qubits of the subsystem code — each ground state is a simultaneous eigenstate with eigenvalue one of all elements of {Sa}. If a quantum memory gov- erned by this Hamiltonian is subjected to thermal noise, how well protected is the 2k-dimensional code space?
If |ψ〉 is a zero-energy eigenstate of H and x ∈ P , then x|ψ〉 is an eigenstate of H with eigenvalue E(x), where E(x) is the number of elements of {Sa} that anticommute with x. Thermal fluctuations may excite the memory, but excitations with energy cost E are suppressed by the Boltzmann factor e−E/τ where τ is the temperature (and Boltzmann’s constant kB has been set to one). Following [2], we suppose that the environment applies a sequence of weight-one Pauli operators to the system, so that the error history after t steps can be described as a walk on the Pauli group, starting at the identity:
{xi ∈ P, i = 0, 1, 2, 3, . . . t},
where x0 = I, and xi+1x −1 i has weight one. Let P(z)
denote the set of all such walks, with any number of steps, that start at I and terminate at z ∈ P . We define
∆(z) ≡ min γ∈P(z)
max x∈γ E(x),
the minimum energy barrier that must be surmounted by any walk that reaches Pauli operator z. Thus such walks occur with a probability per unit time suppressed by the Boltzmann factor e−∆(z)/τ . We also define
∆min ≡ min x∈S⊥\G
∆(x),
∆max ≡ max x∈S⊥
min y∈G
∆(xy).
Here ∆min is the lowest energy barrier protecting any nontrivial dressed logical operator (representing a non- trivial coset of S⊥/G), and ∆max is the highest such en- ergy barrier.
We say that a quantum memory is self correcting if ∆min grows faster than logarithmically with L. In that case all nontrivial logical operators are suppressed by a Boltzmann factor whose reciprocal grows super- polynomially with L. We say that the quantum mem- ory is partially self correcting if ∆max grows faster than logarithmically with L. In that case at least one logical operator is protected by an energy barrier that increases with system size. Though the Pauli walk may not be a

10
particularly accurate description of noise in realistic sys- tems, it allows us to define the notion of barrier height precisely, and to state the criteria for self correction and partial self correction simply. Furthermore, we expect the Boltzmann factor e−∆/τ suppressing the Pauli walk to provide a reasonable (though crude) estimate of the logical error rate for more realistic noise models, assum- ing that the system attains thermal equilibrium.
Bravyi and Terhal [2], and Kay and Colbeck [4], showed that no two-dimensional local subsystem code with local stabilizer generators can be self correcting. On the other hand, partially self-correcting quantum memo- ries are certainly possible in two dimensions — the Ising model, regarded as a quantum repetition code, is an ex- ample. In the Ising model, the logical bit flip operator flips every qubit, hence d˜ = L2. In the Pauli walk that reaches the logical bit flip and traverses the lowest bar- rier, a domain wall of length Ω(L) sweeps across the sys- tem; hence ∆max = Ω(L). Theorem 1 shows that this
high value of d˜ for the logical bit flip is possible only because the code distance d is O(1), and hence a logi- cal phase flip can be realized by an operator of constant weight.
But suppose that, as in the toric code [20], a logical phase flip can occur only if a thermally activated local- ized quasiparticle propagates across the system. Thus d˜ = Ω(L) for the logical phase flip. Can the logical bit flip still be protected by a high barrier? Arguing as in [2], and invoking Theorem 1, we see that under this condi- tion robust protection against bit flips cannot be achieved using a local subsystem code with local stabilizer gener- ators.
Theorem 4. (Limitation on partial self correction in local subsystem codes) For a two-dimensional local sub- system code, with qubits residing at sites of an L × L square lattice, suppose that {Sa} is a (possibly overcom- plete) set of geometrically local stabilizer generators, where the number of generators acting on each qubit is an L-independent constant. Consider a quantum mem- ory governed by the Hamiltonian eq.(10). If the code dis- tance is d = Ω(L), then the memory is not partially self correcting — i.e., ∆max = O(1). More generally, if the code distance is d = Ω(Lα) in D spatial dimensions, then ∆max = O(L
β), where β = D − 1− α/(D − 1). Proof. Let w be the interaction range of the gauge gener- ators of the subsystem code and let wS be the interaction range of the stabilizer generators.
For any dressed logical operator x supported on this set, we may build a Pauli walk that starts at I and ends at x by first building the horizontal strings column by column and then building the vertical strings row by row. At each stage of this walk, any “excited” local stabilizer Sa such that Sa = −1 acts only on qubits in a wS × wS square that contains qubits either at the boundary of the walk or in the intersection of a horizontal and vertical string. The number of such qubits is O(1) and the total number of stabilizer generators acting on these
qubits is O(1). Therefore, the energy cost of the partially completed walk, and hence ∆max, are O(1).
In D spatial dimensions, the proof of Theorem 1 shows that the support of any dressed logical opera- tor can be reduced to a network of overlapping (D−1)- dimensional slabs, where each slab has constant width and slabs with the same orientation are separated by dis- tance l such that lD−1 = Ω(d); hence l = Ω(Lα/(D−1)) if d = Ω(Lα). For any dressed logical operator sup- ported on this set of slabs, we may build a Pauli walk that sweeps across the system, such that at each stage of the walk the excited stabilizer generators are con- fined to a (D−1)-dimensional “surface.” This surface may be oriented such that it cuts across each slab on a (D−2)-dimensional surface with weight O(LD−2). There are O(L/l) such intersections; therefore during the walk the total number of excited stabilizer generators (and hence the energy cost) is O((L/l)LD−2) = O(Lβ), where β = D − 1− α/(D − 1).
We needed to assume that each Sa is geometrically lo- cal to ensure that eq.(10) is a geometrically local Hamil- tonian. For any local subsystem code with geometrically local gauge generators, whether or not the stabilizer gen- erators are also geometrically local, the Hamiltonian [14]
H = − ∑ a
1
2 λa (Ga − I)
is geometrically local, where now {Ga} is the set of gauge generators. However, because the gauge generators are not mutually commuting, the energetics of a Pauli walk is not easy to study in this model, which is beyond the scope of Theorem 4.
VIII. ARE THERE SELF-CORRECTING LOCAL COMMUTING PROJECTOR CODES IN TWO
DIMENSIONS?
For a two-dimensional local commuting projector code, the simultaneous eigenspace with eigenvalue one of the projectors {Πa}, the code space is the degenerate ground state with energy E = 0 of the Hamiltonian
H = − ∑ a
1
2 (Πa − I) . (11)
If only a constant number of projectors act on each qubit, then an operator supported on a set M can increase the energy by at most c|M |, where c is a constant. Since Theorem 3 establishes the existence of a nontrivial logi- cal operator supported on a narrow strip, one might an- ticipate that, by arguing as in the proof of Theorem 4, we can show that this system is not self correcting or partially self correcting.
We may envision a sequence of operations interpolat- ing between the identity and a nontrivial logical opera- tor, where each operation in the sequence could plausibly

11
evolve from the previous operation due to the action of a thermal bath. In the strip M of constant width that supports a nontrivial logical operator O, we can divide the qubits into two subsets A and B = M \ A, imagin- ing that the interface between A and B gradually creeps along the strip.
Now, however, we encounter an important distinction between stabilizer codes and more general commuting projector codes. For a stabilizer code, the nontrivial log- ical operator supported in M can be chosen to be a Pauli operator, and hence the product of an operator supported in A and an operator supported in B. For a commut- ing projector code, a logical operator supported in M may actually be entangling across the A-B cut. Are we assured that this entangling operation can be built up gradually due to the effects of local noise?
We have not been able to settle this question. We can say that in any two-dimensional local commuting projec- tor code there exists a nontrivial logical operator that is only slightly entangling across any cut through the strip. This property, however, might not suffice to guarantee that the logical operator can be constructed as a prod- uct of physical operations, where each operation acts on a constant number of system qubits near the A-B cut and also on a constant number of ancillary qubits in the “environment.”
To define the notion of “slightly entangling” for an operator O supported on AB, we perform a Schmidt de- composition
O = ∑ α
√ λα OαA ⊗OαB ;
here {λα} is a set of nonnegative real numbers, while {OαA} is a set of operators supported on A and {OαB} is a set of operators supported on B, with the normalization conditions
tr ( Oα†A OβA
) = 2|A| δαβ ,
tr ( Oα†B OβB
) = 2|B| δαβ .
The number of nonzero terms in the Schmidt decompo- sition is the Schmidt rank of O, and we say that O is slightly entangling if its Schmidt rank is a constant inde- pendent of system size.
As we know from Theorem 3, for a two-dimensional local commuting projector code on an L×L lattice, there is a nontrivial logical operator supported on a vertical strip M with dimensions r×L, where r is a constant. M can be regarded as the disjoint union of an r×h rectangle A covering the bottom of M and an r× (L−h) rectangle B covering the top of M . We can prove
Lemma 13. (Existence of slightly entangling logical op- erators) For a nontrivial two-dimensional local commut- ing projector code, there is a nontrivial Hermitian log- ical operator H supported on a strip of constant width M ′ such that, for any division of M ′ into constant-width
rectangles A and B, H is slightly entangling across the A-B cut.
Proof. We know from Lemmas 11 and 12 that there is a noncorrectable constant-width strip M and a Pauli op- erator PM supported on M such that
H = ΠM ′PMΠM ′ ,
is a nontrivial Hermitian logical operator supported on M ′; here ΠM ′ =
∏ Πa∈S′M Πa and S
′ M is the set of projec-
tors that act nontrivially on M . The Pauli operator PM is a product operator, with Schmidt number one across the A-B cut. Among the local projectors occurring in the product ΠM ′ , those fully supported on either A or B have no effect on the Schmidt number of ΠM ′PMΠM ′ , and only a constant number of the projectors act nontriv- ially on both A and B. Since each such Πa is supported on a constant number of qubits, the action of Πa increases the Schmidt number by a constant. Thus H has constant Schmidt number, i.e. is slightly entangling.
We may relax the notion of slightly entangling, regard- ing an operator O as slightly entangling if it may be well approximated by an operator with constant Schmidt rank. In this sense the unitary logical operator U = exp(iλH) is also slightly entangling. We may expand the exponential as a power series where each term has a Schmidt rank independent of system size; furthermore, the power series expansion truncated at constant order approximates the exponential function very well with re- spect to the operator norm.
Now we might hope to construct a slightly entangling logical operator O, supported on a constant-width verti- cal strip, by gradually building its support one horizon- tal row of qubits at a time. However, Lamata et al. [21] showed that, if O is entangling, then it cannot be ob- tained as a product of unitary operators where each of these operators acts on just a few rows of system qubits and on a shared ancillary system.
An alternative procedure for gradually building a nontrivial logical error has been proposed by Landon- Cardinal and Poulin [22]. They envision a walk along the strip such that, in each step of the walk, first a con- stant size set of qubits depolarizes, and then the code projectors acting on that set are applied. If the projec- tion fails to accept the state, the step can be repeated until the projection succeeds.
This procedure could fail if at some stage the pro- jection succeeds with zero probability. But Landon- Cardinal and Poulin [22] have shown that their procedure eventually generates a nontrivial logical error (and hence that the code is not self correcting) for any local commut- ing projector code obeying a “local topological order” cri- terion [23]. Whether self-correcting two-dimensional lo- cal commuting projector codes are possible remains open, though, because topologically ordered codes that violate local topological order have not been ruled out.

12
IX. CONCLUSION
The quantum accuracy threshold theorem [19] shows that quantum information can be reliably stored and pro- cessed by a noisy physical system if the noise is not too strong. But can quantum information be protected “pas- sively” in a macroscopic physical system governed by a static local Hamiltonian, at a sufficiently low nonzero temperature? This question [5, 14], aside from its far- reaching potential implications for future quantum tech- nologies, is also a fundamental issue in quantum many- body physics. Hamiltonians derived from local quantum codes, whose properties are relatively easy to discern, can provide us with valuable insights.
A two-dimensional ferromagnet can be a self-correcting classical memory, but a Hamiltonian based on a two- dimensional local subsystem code with local stabilizer generators cannot be a self-correcting quantum memory [2, 4]. We have shown that for two-dimensional local sub- system code with local stabilizer generators on an L×L square lattice, robust classical protection is impossible if the code distance is d = Ω(L), as expected for a topolog- ically ordered two-dimensional system. More generally, we have studied how the code distance d limits the size of the support of arbitrary nontrivial logical operators, in both local subsystem codes and local commuting pro- jector codes. In view of the upper bound d = O(LD−1) on the code distance, we may write d = Θ(L(D−1)(1−δ)) where 0 ≤ δ ≤ 1, and thus our upper bound eq.(1) on the weight of logical operators becomes
d˜ = O(LD−1+δ).
In particular, in three dimensions, d = Ω(L) implies d˜ = O(L5/2). We have also shown that any two-dimensional local commuting projector code admits a nontrivial logi- cal string operator which is only slightly entangling across any cut through the string.
Our arguments modestly extend the findings of [1–4], and use similar ideas. In passing, we also proved a Clean- ing Lemma for subsystem codes based on ideas from [11], proved a Cleaning Lemma for local commuting projector codes. Our methods might find further applications in fu- ture studies of quantum memories based on local codes.
Acknowledgments
We are grateful to Salman Beigi, Alexei Kitaev, Robert Ko¨nig, Olivier Landon-Cardinal, and Norbert Schuch for helpful discussions, and we especially thank David Poulin for useful comments on the manuscript. This re- search was supported in part by NSF under Grant No. PHY-0803371, by DOE under Grant No. DE-FG03-92- ER40701, by NSA/ARO under Grant No. W911NF-09- 1-0442, and by the Korea Foundation for Advanced Stud- ies. The Institute for Quantum Information and Matter (IQIM) is an NSF Physics Frontiers Center with support from the Gordon and Betty Moore Foundation.
Appendix A: Holographic lemma for local stabilizer codes
We say that a local stabilizer code has interaction range w if each stabilizer generator has support on a hypercube containing wD sites. For this case, we can improve the criterion for correctability of a hypercube, found for local subsystem codes in Lemma 5.
Lemma 14. (Expansion Lemma for local stabilizer codes) For a local stabilizer code, suppose that ∂+M , A, and M \ A are all correctable, where ∂−M ⊆ A ⊆ M . Then M is also correctable.
Proof. Suppose, contrary to the claim, that there is a nontrivial logical operator x supported on M . Then, be- cause A is correctable, Lemma 3 implies that there is a stabilizer generator y such that xy acts trivially on A. Furthermore, y can be expressed as a product of local sta- bilizer generators, each supported on M ′ = M ∪ ∂+M . Thus xy is a product of two factors, one supported on M \ A and the other supported on ∂+M . Because ∂−M ⊆ A, no local stabilizer generator acts nontrivially on both M\A and ∂+M ; therefore, each factor commutes with all stabilizer generators and hence is a logical oper- ator. Because M \A and ∂+M are both correctable, each factor is a trivial logical operator and therefore xy is also trivial. It follows that x is trivial, a contradiction.
Now, if the interaction range is w and M is a hyper- cube with linear size l, we choose A so that M \ A is a hypercube with linear size l − 2(w − 1), and we notice that ∂+M is contained in a hypercube with linear size l+ 2(w− 1). Thus both M \A and ∂+M are correctable provided that
|∂+M | ≤ [l + 2(w − 1)]D − lD ≤ 2(w − 1)D [l + 2(w − 1)]D−1 < d.
Reasoning as in the proof of Lemma 5, we conclude that:
Lemma 15. (Holographic Principle for local stabilizer codes) For a D-dimensional local stabilizer code with in- teraction range w > 1 and distance d > 1, a hypercube with linear size l is correctable if
2(w − 1)D [l + 2(w − 1)]D−1 < d. (A1) To ensure that the hypercube M is correctable, it suf- fices for its (w − 1)-thickened boundary, rather than its [2(w − 1)]-thickened boundary, to be smaller than the code distance.
Appendix B: A noncorrectable set that supports no nontrivial logical operator
Here we give a simple example illustrating that for some quantum codes a noncorrectable set need not sup- port a nontrivial logical operator. For n = 2 qubits, con- sider the three-dimensional code space spanned by the

13
orthogonal vectors
|φ〉 = 1√ 2
(|00〉+ |11〉) , |ψ〉 = |01〉, |χ〉 = |10〉;
this is the eigenspace with eigenvalue 1 of the projector
Π = |φ〉〈φ|+ |ψ〉〈ψ|+ |χ〉〈χ|. If the first qubit is mapped to |0〉, then |φ〉 is no longer perfectly distinguishable from |ψ〉 or |χ〉; hence erasure of this qubit is not correctable. (Similarly, the second qubit is also a noncorrectable set.)
Is there a logical operator supported on the first qubit? Suppose that
L =
( a b c d
)
is an operator acting on the first qubit. Then L⊗ I|ψ〉 = a|01〉+c|11〉 is a code vector only if c = 0, and L⊗I|χ〉 = b|00〉+ d|10〉 is a code vector only if b = 0. Furthermore, if b = c = 0, then L ⊗ I|φ〉 = (a|00〉+ d|11〉) /√2 is a code vector only if a = d. Thus L is a multiple of the identity, a trivial operator.
[1] 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.
[2] S. Bravyi and B. Terhal, No-go theorem for two- dimensional self-correcting quantum memory based on stabilizer codes, New J. Phys. 11, 043029 (2009), arXiv:0810.1983.
[3] S. Bravyi, Subsystem codes with spatially local genera- tors, arXiv:1008.1029 (2010).
[4] A. Kay and R. Colbeck, Quantum self-correcting stabi- lizer codes, arXiv:0810.3557 (2008).
[5] E. Dennis, A. Kitaev, A. Landahl, and J. Preskill, Topo- logical quantum memory, J. Math. Phys. 43, 4452-4505 (2002), arXiv:quant-ph/0110143.
[6] R. Alicki, M. Horodecki, P. Horodecki, and R. Horodecki, On thermal stability of topological qubit in Ki- taev’s 4D model, Open Syst. Inf. Dyn. 17, 1 (2010), arXiv:0811.0033.
[7] J. Haah, Local stabilizer codes in three dimensions with- out string logical operators, Phys. Rev. A 83, 042330 (2011), arXiv:1101.1962.
[8] S. Bravyi and J. Haah, On the energy landscape of 3D spin Hamiltonians with topological order, Phys. Rev. Lett. 107, 150504 (2011), arXiv:1105.4159.
[9] S. Bravyi and J. Haah, Analytic and numerical demon- stration of quantum self-correction in the 3D Cubic Code, arXiv:1112.3252 (2011).
[10] C. Castelnovo and C. Chamon, Topological order in a 3D toric code at finite temperature, Phys. Rev. B 78, 155120 (2008), arXiv:0804.3591.
[11] B. Yoshida and I. L. Chuang, Framework for classifying logical operators in stabilizer codes, Phys. Rev. A 81, 052302 (2010), arXiv:1002.0085.
[12] A. R. Calderbank, E. M. Rains, P. W. Shor, and N. J. A. Sloane, Quantum error correction and orthogonal geom-
etry, Phys. Rev. Lett 78, 405-408 (1997), arXiv:quant- ph/9605005.
[13] D. Gottesman, Class of quantum error-correcting codes saturating the quantum Hamming bound, Phys. Rev. A 54, 1862–1868 (1996), arXiv:quant-ph/9604038.
[14] D. Bacon, Operator quantum error-correcting subsys- tems for self-correcting quantum memories, Phys. Rev. A 73, 012340 (2006), arXiv:/quant-ph/0506023.
[15] D. Poulin, Stabilizer formalism for operator quantum error correction, Phys. Rev. Lett 95, 230504 (2005), arXiv:quant-ph/0508131.
[16] A. R. Calderbank and P. W. Shor, Good quantum error-correcting codes exist, Phys. Rev. A 54, 1098–1105 (1996), arXiv:quant-ph/9512032.
[17] A. Steane, Multiple particle interference and quantum error correction, Proc. Roy. Soc. Lond. A A452, 2551– 2577 (1996), arXiv:quant-ph/9601029.
[18] M. Wilde and D. Fattel, Nonlocal quantum information in bipartite quantum error correction, Quant. Inf. Proc. 9, 591-610 (2010), arXiv:0912.2150.
[19] D. Gottesman, An introduction to quantum error correction and fault-tolerant quantum computation, arXiv:0904.2557 (2009), and references therein.
[20] A. Yu. Kitaev, Fault-tolerant quantum computation by anyons, Ann. Phys. 303, 2-30 (2003), arXiv:quant- ph/9707021.
[21] L. Lamata, J. Leo´n, D. Pe´rez-Garcia, D. Salgado, and E. Solano, Sequential implementation of global quan- tum operations, Phys. Rev. Lett. 101, 180506 (2008), arXiv:0711.3652.
[22] O. Landon-Cardinal and D. Poulin, unpublished (2012). [23] S. Bravyi and M. B. Hastings, A short proof of sta-
bility of topological order under local perturbations, arXiv:1001.4363 (2010).