Optimal Locality and Parameter Tradeoffs for Subsystem Codes

Dai, Samuel; Li, Ray; Tang, Eugene

doi:10.4230/LIPIcs.TQC.2025.4

Optimal Locality and Parameter Tradeoffs for Subsystem Codes

Samuel Dai

Department of Physics, Northeastern University, Boston, MA, USA Ray Li

Math & CS Department, Santa Clara University, CA, USA Eugene Tang

Departments of Math and Physics, Northeastern University, Boston, MA, USA

Abstract

We study the tradeoffs between the locality and parameters of subsystem codes. We prove lower bounds on both the number and lengths of interactions in any $D$ -dimensional embedding of a subsystem code. Specifically, we show that any embedding of a subsystem code with parameters $[[n,k,d]]$ into $\mathbb{R}^{D}$ must have at least $M^{*}$ interactions of length at least $\ell^{*}$ , where

M^{*}=\Omega(\max(k,d)),\quad\text{and}\quad\ell^{*}=\Omega\bigg(\max\bigg(% \frac{d}{n^{\frac{D-1}{D}}},\bigg(\frac{kd^{\frac{1}{D-1}}}{n}\bigg)^{\frac{D-% 1}{D}}\bigg)\bigg).

We also give tradeoffs between the locality and parameters of commuting projector codes in $D$ -dimensions, generalizing a result of Dai and Li [8]. We provide explicit constructions of embedded codes that show our bounds are optimal in both the interaction count and interaction length.

Keywords and phrases:

Quantum Error Correcting Code, Locality, Subsystem Code, Commuting Projector Code

Funding:

Ray Li: Supported by NSF grant CCF-2347371.

Copyright and License:

2012 ACM Subject Classification:

Hardware

\rightarrow

Quantum error correction and fault tolerance ; Theory of computation

\rightarrow

Error-correcting codes

Related Version:

Full Version: https://arxiv.org/pdf/2503.22651 [9]

Acknowledgements:

We thank Andy Liu, Shouzhen Gu, Zhiyang He for helpful feedback on our manuscript.

DOI:

10.4230/LIPIcs.TQC.2025.4

Event:

20th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2025)

Editor:

Bill Fefferman

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Quantum computing necessitates the manipulation of fragile states of information. The most promising way towards large-scale fault-tolerant quantum computing involve the extensive use of quantum error-correcting codes (QECCs). Physical implementations of quantum computing hardware naturally favor architectures which are local in $2$ or $3$ spatial dimensions – architectures where the qubits are embedded in 2 or 3 dimensions, and interactions occur only between qubits that are spatially nearby. On the other hand, it has long been known that the constraint of spatial locality places severe limitations on the parameters of QECCs. For example, the Bravyi-Terhal [7] and Bravyi-Poulin-Terhal (BPT) [6] bounds state that a commuting projector code whose constraints are local in $D$ -dimensions necessarily have code parameters satisfying, respectively,

\displaystyle d=O(n^{\frac{D-1}{D}}),\qquad\text{and}\qquad kd^{\frac{2}{D-1}}% =O(n).

(1)

These bounds suggest that there are tradeoffs between better code performance and the cost of non-local implementation. Consequently, the locality of a QECC becomes another key factor to consider when choosing a code for applications.

What is the quantitative tradeoff between locality and code quality? This problem was initially investigated by Baspin and Krishna [3], who asked, for a quantum low-density parity-check (qLDPC) code in $D$ -dimensions, how many “long-range” interactions must there be, and how long must those interactions be? Baspin and Krishna gave bounds for $D$ -dimensional codes which are nearly optimal in certain parameter settings. For $2$ -dimensional codes, Dai and Li [8] improved the bounds to be tight across all parameter regimes and also gave matching constructions that saturate the upper bounds (see also Hong, et al. [11], who considered the special case $k=1,d=\sqrt{n}$ for 2-dimensional codes). Dai and Li showed that an $[[n,k,d]]$ quantum code embedded in $2$ spatial dimensions must have $\Omega(M^{*})$ interactions of length $\Omega(\ell^{*})$ , where

\displaystyle M^{*}=\max(k,d),\qquad\text{and}\qquad\ell^{*}=\max(\frac{d}{% \sqrt{n}},\sqrt[4]{\frac{kd^{2}}{n}}).

(2)

Both the interaction count $M^{*}$ and interaction length $\ell^{*}$ are tight in strong ways.

In this paper, we study the locality versus parameter tradeoffs for quantum subsystem codes. Bravyi [5] showed that the BPT bound could be violated by the use of local subsystem codes, providing $2$ D-local subsystem codes with parameters $k,d=\Theta(\sqrt{n})$ . Subsystem codes are nevertheless constrained by locality. Bravyi [5] showed that a $[[n,k,d]]$ subsystem code whose gauge generators are local in a $D$ -dimensional lattice embedding satisfies

d=O(n^{\frac{D-1}{D}}),\qquad\text{and}\qquad kd^{\frac{1}{D-1}}=O(n).

(3)

While previous work has made it clear that outperforming local quantum codes requires copious amounts of long-ranged interactions, it is not a priori clear whether the same requirements hold for subsystem codes. Is it possible that small violations of locality in the gauge generators suffice to define subsystem codes parametrically better than those allowed by Bravyi’s bound? More concretely:

Question 1.

How much non-locality is required for a subsystem code to exceed Bravyi’s bound?

We address Question 1 by demonstrating that subsystem codes, like their commuting projector counterparts, require an extensive number of long-ranged interactions to surpass Bravyi’s bound. We also provide constructions of subsystem codes that show our lower bounds are tight in strong ways. Additionally, we also generalize the results of Dai and Li [8] from $2$ -dimensions to $D$ -dimensions. Our work establishes optimal bounds on interaction lengths and counts for embeddings of both commuting projector codes and subsystem codes in any number of dimensions.

1.1 Main Result

We study subsystem codes whose gauge generators are not necessarily local. Our main result is a lower bound on the number and length of interactions in any $D$ -dimensional embedding of a $[[n,k,d]]$ subsystem code. Formally, a $D$ -dimensional embedding is a mapping of the code’s $n$ physical qubits into $\mathbb{R}^{D}$ , such that any two qubits are at distance at least 1.

Theorem 2 (Main Result for Subsystem Codes).

For any $D\geq 2$ , there exist constants $c_{0}=c_{0}(D)>0$ and $c_{1}=c_{1}(D)>0$ such that the following is true: Any $D$ -dimensional embedding of a nontrivial¹¹1Nontrivial here simply means that $k>0$ . $[[n,k,d]]$ subsystem code with $kd^{\frac{1}{D-1}}\geq c_{1}n$ or $d\geq c_{1}n^{\frac{D-1}{D}}$ must have at least $M^{*}$ interactions of length $\ell^{*}$ , where

M^{*}=c_{0}\cdot\max(k,d),\qquad\text{and}\qquad\ell^{*}=c_{0}\cdot\max\bigg(% \frac{d}{n^{\frac{D-1}{D}}},\bigg(\frac{kd^{\frac{1}{D-1}}}{n}\bigg)^{\frac{D-% 1}{D}}\bigg).

(4)

Prior to this work, no such bounds of this form were known for subsystem codes aside from Bravyi’s original bound. While such bounds were known for commuting projector codes, our bound shows that a locality versus parameter trade-off also holds for subsystem codes. Our result also generalizes Bravyi’s bound [5], not only in that we (optimally) address the number and length of long-range interactions, but also in that we handle more general embeddings. Bravyi’s bound [5] considers only embeddings onto a $n^{1/D}\times\cdots\times n^{1/D}$ lattice, but our bound applies to arbitrary embeddings, even those not constrained to a $O(n^{1/D})\times\cdots\times O(n^{1/D})$ box (see Section 3 for further discussion).

Like for stabilizer codes, subsystem codes beyond the “local regime” – above the BPT bound for stabilizer codes, or above the Bravyi bound for subsystem codes – need copious amounts of non-locality. In particular, the number of required long-range interactions $\Omega(\max(k,d))$ is the same for both subsystem and stabilizer codes. Additionally, for codes with a large number $k$ of logical qubits, the required length of the long range interactions is similar. For example, a $2$ -dimensionally embedded asymptotically good subsystem code (with $k,d=\Omega(n)$ ) needs $M^{*}=\Omega(n)$ interactions of length $\ell^{*}=\Omega(\sqrt{n})$ – the worst possible case – just as for stabilizer codes. Our results show that, compared to stabilizer codes, subsystem codes do not offer substantial improvements in locality outside of the “local regime,” though they can offer some quantitative improvements in the interaction length.

We also provide matching constructions that show $M^{*}$ and $\ell^{*}$ are optimal in strong ways (see Figure 2). An asymptotically good qLDPC code [14, 12] has $O(M^{*})=O(\max(k,d))$ interactions of any length (see Theorem 1.3 of [8]). Since a stabilizer code can also be trivially regarded as a subsystem code, this shows that our bounds are tight in terms of interaction count. For optimality in the interaction length, we exhibit subsystem codes embedded in $D$ -dimensions where all interactions are of length at most $O(\ell^{*})$ (Theorem 21).

Figure 1: The (asymptotically) optimal interaction count and length for subsystem codes in 2D: A

[[n,k,d]]

subsystem code need at least

\Omega(M^{*})

interactions of length

\Omega(\ell^{*})

, where

M^{*}

is plotted on the left and

\ell^{*}

is plotted on the right. Above, we plot the contours of

k

vs.

d

tradeoffs for various values of the Interaction Count or Interaction Length. Everywhere, big-

O

is suppressed for clarity.

Figure 2: Schematic diagram illustrating the optimality of our lower bounds for all

n, k, d

: A point

(M,L)

represents that there is a code with

O(M)

interactions of length

\omega(L)

. Blue shaded region is achievable, red lined region is unachievable. Our lower bound shows that

(M,\ell)

with

M\leq o(M^{*})

and

\ell\leq o\left(\ell^{*}\right)

is impossible, where

M^{*}

and

\ell^{*}

are the optimal interaction count and length, respectively, given by Theorem 2. There is a construction (good qLDPC code) with

O(M^{*})

interactions of any length, and another construction (concatenated local code, Theorem 21) with zero interactions of length

\omega\left(\ell^{*}\right)

.

1.2 Generalizing [8] to $𝑫$ -dimensions

We also show that the bounds in [8] can be generalized to $D$ -dimensional embeddings and to commuting projector codes.

Theorem 3 (Generalization of [8] to $D$ -dimensions).

For any $D\geq 2$ , there exist constants $c_{0}=c_{0}(D)>0$ and $c_{1}=c_{1}(D)>0$ such that the following is true: Any $D$ -dimensional embedding of a nontrivial $[[n,k,d]]$ commuting projector code with $kd^{\frac{2}{D-1}}\geq c_{1}n$ or $d\geq c_{1}n^{\frac{D-1}{D}}$ must have at least $M^{*}$ interactions of length $\ell^{*}$ , where

M^{*}=c_{0}\cdot\max(k,d),\qquad\text{and}\qquad\ell^{*}=c_{0}\cdot\max\bigg(% \frac{d}{n^{\frac{D-1}{D}}},\bigg(\frac{kd^{\frac{2}{D-1}}}{n}\bigg)^{\frac{D-% 1}{2D}}\bigg).

(5)

We now compare our works to prior works. First, we note that, when setting $D=2$ , our bound matches the bounds in [8] up to the implied constant. For $D>2$ dimensions, the only prior bounds we are aware of are due to Baspin and Krishna [3]. Theirs match our bounds up to polylog factors when $d\geq\sqrt{kn}$ and when $k=\Theta(n)$ , and we improve their bounds in the remaining parameter regimes. We also generalize their results; our results hold for all commuting projector codes, whereas theirs hold only for qLDPC codes.

Similar to Theorem 2 and [8], our $M^{*}$ and $L^{*}$ in Theorem 3 are optimal up to constant factors. Any asymptotically good qLDPC code [14, 12] is a commuting projector code with at most $O(M^{*})=O(\max(k,d))$ interactions of any length. Further, we exhibit stabilizer codes embedded in $D$ dimensions, all of whose interactions are of length at most $O(\ell^{*})$ ; see Theorem 23.

1.3 Organization of the Paper

We divide the proof of Theorem 2 into two parts:

Theorem 4 (Main Result – Part 1).

For all $D\geq 2$ , there exist constants $c_{0}=c_{0}(D)>0$ and $c_{1}=c_{1}(D)>0$ such that the following is true: Any $D$ -dimensional embedding of a nontrivial $[[n,k,d]]$ subsystem or commuting projector code with $d\geq c_{1}n^{\frac{D-1}{D}}$ must have at least $c_{0}d$ interactions of length at least $c_{0}\frac{d}{n^{\frac{D-1}{D}}}$ .

Theorem 5 (Main Result – Part 2).

For all $D\geq 2$ , there exist constants $c_{0}=c_{0}(D)>0$ and $c_{1}=c_{1}(D)>0$ such that the following is true: Any $D$ -dimensional embedding of a $[[n,k,d]]$ subsystem code with $kd^{\frac{1}{D-1}}\geq c_{1}n$ must have at least $c_{0}k$ interactions of length at least $c_{0}(\frac{kd^{\frac{1}{D-1}}}{n})^{\frac{D-1}{D}}$ .

Theorem 4 implies Theorem 2 in the regime where $d\geq k$ , and Theorem 5 implies Theorem 2 in the regime when $d\leq k$ . Note that Theorem 4 also implies Theorem 3 when $d\geq\sqrt{kn}$ . The remaining case of Theorem 3 is when $d\leq\sqrt{kn}$ , which we prove in Theorem 6.

Theorem 6 (Generalization of [8] when $d\leq\sqrt{kn}$ ).

For all $D\geq 2$ , there exist constants $c_{0}=c_{0}(D)>0$ and $c_{1}=c_{1}(D)>0$ such that the following is true: Any $D$ -dimensional embedding of a $[[n,k,d]]$ commuting projector code with $kd^{\frac{2}{D-1}}\geq c_{1}n$ must have at least $c_{0}k$ interactions of length $c_{0}(\frac{kd^{\frac{2}{D-1}}}{n})^{\frac{D-1}{2D}}$ .

2 Preliminaries

Notation and Definitions

We use standard Landau notation $O(\cdot),\Omega(\cdot),\Theta(\cdot),o(\cdot),\omega(\cdot)$ . We also use the notations $\tilde{O}(\cdot),\ \tilde{\Omega}(\cdot)$ , which are variants of $O(\cdot)$ and $\Omega(\cdot)$ , respectively, that ignore logarithmic factors. For example, $f(n)=\tilde{O}(h(n))$ means that there exists an integer $k$ such that $f(n)=O(h(n)\log^{k}n)$ . For a set $S$ , we write $S^{\leq D}\stackrel{{\scriptstyle\rm def}}{{=}}S\cup S^{2}\cup\cdots\cup S^{D}$ .

In $\mathbb{R}^{D}$ , distance refers to Euclidean ( $\ell_{2}$ ) distance unless otherwise specified. We sometimes also use the $\ell_{\infty}$ -distance of two points $(x,y),(x^{\prime},y^{\prime})\in\mathbb{R}^{D}$ , which is $\max(|x-x^{\prime}|,|y-y^{\prime}|)$ . A grid tiling is a division of $\mathbb{R}^{d}$ given by axis aligned hyperplanes equally spaced at a fixed distance $w$ . Throughout, a box is always a set of the form $[a_{1},b_{1}]\times\cdots\times[a_{D},b_{D}]$ . In particular, boxes contain their boundary and are axis-parallel. A cube is a box all of whose side lengths are equal: $b_{1}-a_{1}=b_{2}-a_{2}=\cdots=b_{D}-a_{D}$ .

An embedded set in $\mathbb{R}^{D}$ is a finite set $Q\subset\mathbb{R}^{D}$ with pairwise ( $\ell_{2}$ ) distance at least 1. A function $f:\mathbb{R}^{D}\to\mathbb{N}$ is finitely supported if $f(x)\neq 0$ for finitely many $x\in\mathbb{R}^{D}$ . For a finitely supported function $f:\mathbb{R}^{D}\to\mathbb{N}$ and a region $R\subset\mathbb{R}^{D}$ , define, by abuse of notation, $f(R)=\sum_{i\in R;f(i)\neq 0}f(i)$ . We will be primarily concerned with the finitely supported function given by Definition 8.

2.1 Quantum codes

We associate the pure states of a qubit with unit vectors in $\mathbb{C}^{2}$ and pure $n$ -qubit states with unit vectors in $(\mathbb{C}^{2})^{\otimes n}$ . Let $\mathcal{P}$ denote the (single-qubit) Pauli group, which consists of the Pauli matrices $\mathsf{I},\mathsf{X},\mathsf{Y},\mathsf{Z}$ , and their scalar multiples by $\{\pm 1,\pm i\}$ . The $n$ -qubit Pauli group is $\mathcal{P}_{n}=\mathcal{P}^{\otimes n}$ . Given $P\in\mathcal{P}_{n}$ , its weight $|P|$ is the number of tensor components not equal to $\mathsf{I}$ .

A quantum error-correcting code $\mathcal{C}$ is a subspace of $(\mathbb{C}^{2})^{\otimes n}$ . The parameter $n$ is called the (block) length of the code. We define the dimension $k$ of the code to be $k=\log_{2}(\dim\cal C)$ .

Stabilizer Codes

A stabilizer group $\mathcal{S}$ is an abelian subgroup of the $n$ -qubit Pauli group $\mathcal{P}_{n}$ that does not contain $-\mathsf{I}$ . A stabilizer code $\mathcal{Q}=\mathcal{Q}(\mathcal{S})\subseteq(\mathbb{C}^{2})^{\otimes n}$ is defined to be the subspace of states left invariant under the action of the stabilizer group $\mathcal{S}$ , i.e. $\mathcal{Q}=\{\ket{\psi}:\;\mathsf{S}\ket{\psi}=\ket{\psi},\;\forall\mathsf{S}% \in\mathcal{S}\}$ . Being an abelian group, we can describe $\mathcal{S}$ by $n-k$ independent generators $\{\mathsf{S}_{1},...,\mathsf{S}_{n-k}\}$ , where $k$ is the dimension of the code. The distance $d$ is the minimum weight of an error $E\in\mathcal{P}_{n}$ that maps a codeword in $\mathcal{Q}$ to another codeword. A quantum code $\mathcal{Q}$ with distance $d$ can correct up to $d-1$ qubit erasures.

Subsystem Codes

A subsystem code is a choice of decomposition of a stabilizer code $\mathcal{C}$ into a tensor product $\mathcal{C}=\mathcal{A}\otimes\mathcal{B}$ , where $\mathcal{A}\cong(\mathbb{C}^{2})^{\otimes k}$ and $\mathcal{B}\cong(\mathbb{C}^{2})^{\otimes g}$ are the logical and gauge parts of $\cal C$ , respectively. The dimension $k$ of a subsystem code is defined as the number of qubits encoded in its logical subsystem $\mathcal{A}$ . One can view a subsystem code as a stabilizer code that can encode $k+g$ logical qubits, but only $k$ of the logical qubits are actually used to protect information.

We can define a subsystem code by starting with a stabilizer code $\mathcal{S}$ given by $n-k-g$ independent stabilizer generators, with $k+g$ logical qubits associated with $k+g$ pairs of logical operators $\bar{X}_{1},\bar{Z}_{1},\dots,\bar{X}_{k+g},\bar{Z}_{k+g}$ . The first $k$ logical qubits are used to encode information, and the last $g$ logical qubits are called gauge qubits. The gauge group of the subsystem is the group $\mathcal{G}=\langle\mathcal{S},\bar{X}_{k+1},\bar{Z}_{k+1},\dots,\bar{X}_{k+g}% ,\bar{Z}_{k+g}\rangle$ . Given the gauge group $\mathcal{G}$ , the code’s stabilizer group $\mathcal{S}$ can be recovered as the center of $\cal G$ , so a subsystem code is uniquely defined by its gauge group. Any stabilizer code can be equivalently regarded as a subsystem code whose gauge group is abelian, so stabilizer codes form a subset of subsystem codes.

For subsystem codes, we make a distinction between bare logical operations, which act trivially on the gauge qubits, and dressed logical operators, which may not. Formally, (non-trivial) bare logical operators are elements of $\mathsf{C}(\mathcal{G})\setminus\mathcal{G}$ , where $\mathsf{C}(\mathcal{G})$ denotes the centralizer of $\mathcal{G}$ , and (non-trivial) dressed logical operators are elements of $\mathsf{C}(\mathcal{S})\setminus\mathcal{G}$ . Note that for stabilizer codes there is no distinction. The distance $d$ of a subsystem code is defined as the minimum weight of a non-trivial dressed logical operator, i.e., $d=\min_{P\in\mathsf{C}(\mathcal{G})\setminus\mathcal{G}}|P|$ . We will sometime denote a subsystem code $\mathcal{C}$ with $n$ physical qubits, $k$ logical qubits, distance $d$ , and $g$ gauge qubits by $\mathcal{C}=[[n,k,d,g]]$ .

Commuting Projector Codes

A commuting projector code $\mathcal{C}\subseteq(\mathbb{C})^{\otimes n}$ is a subspace defined by a set of pairwise commuting projections $\{\Pi_{1},\dots,\Pi_{m}\}$ . The code $\mathcal{C}$ is the subspace of states left invariant by all projections $\Pi_{i}$ . Every stabilizer code is also a commuting projector code where the defining projections are of Pauli type, i.e., $\Pi_{i}=(\mathsf{I}+P_{i})/2$ , for some Pauli operator $P_{i}\in\mathcal{P}_{n}$ . For the purposes of establishing our locality bounds, the only properties we need of commuting projector codes is the fact that all the properties of correctable sets for stabilizer codes, i.e., those listed in Lemma 11, continue to hold without modification for commuting projector codes [10]. Finally, we note that while stabilizer codes can be considered a subset of both subsystem and commuting projector codes, there is no direct relation between subsystem and commuting projector codes themselves.

Quantum codes in $𝑫$ dimensions

Given a finite set $S$ , an embedding of $S$ into $\mathbb{R}^{D}$ is a map $\iota:S\rightarrow\mathbb{R}^{D}$ such that $\|\iota(s_{i})-\iota(s_{j})\|\geq 1$ for all distinct $s_{i},s_{j}\in S$ . The image $\iota(S)$ is then said to be an embedded set. Throughout, the embedding map will usually be implicit. We identify the qubits $Q$ of a quantum code with a $D$ -dimensional embedded set, which we continue to call $Q\subset\mathbb{R}^{D}$ by abuse of notation. By further abuse of notation, we refer to $Q\subset\mathbb{R}^{D}$ as the embedding of the qubits $Q$ . When the set of qubits $Q$ is understood, given a subset $V\subset Q$ , we write $\overline{V}\stackrel{{\scriptstyle\rm def}}{{=}}Q\setminus V$ to denote the complement of $V$ in $Q$ .

Definition 7 (Interactions).

Given an embedding $Q\subset\mathbb{R}^{D}$ of a quantum code $C$ , either a commuting projector code or a subsystem code, interactions of the code are defined with respect to a specific set of generators for that code. In the case that $C$ is a commuting projector code with defining projections $\{\Pi_{1},\cdots,\Pi_{m}\}$ , we say that a pair of qubits $q,p\in Q$ define an interaction if $p$ and $q$ are both in the support of some projection $\Pi_{i}$ . Similarly, if $C$ is a subsystem code with a set of generators $\{G_{1},\cdots,G_{m}\}$ for its gauge group, we say that $p,q\in Q$ define an interaction if $p$ and $q$ are both in the support of some gauge generator $G_{i}$ . In both cases, the length of an interaction $(p,q)$ is defined to be the $\ell_{2}$ distance between $p$ and $q$ .

Interactions are always defined with respect to a particular set of generators (either projector or gauge), but throughout we assume that the generator set is fixed (but otherwise arbitrary), and thus the set of interactions is fixed as well. Note that for subsystem codes, interactions are always defined with respect to gauge generators and not stabilizer generators. In particular, since each stabilizer generator is generally a product of multiple gauge generators, it is possible for a subsystem code to have local gauge generators, but non-local stabilizer generators. Indeed, it is only in such cases that a separation in the locality bounds for stabilizer and subsystem codes is possible.

In the proofs of our results, we typically consider a fixed interaction length $\ell$ . We then refer to an interaction as bad if the length is at least $\ell$ and as good if the length is less than $\ell$ . Intuitively, good interactions are easier to deal with for our proof; they are effectively local, and can be treated in a similar to how local interactions are treated in the original proofs of the BPT and Bravyi bounds. To control the number of bad interactions, we introduce the following function that counts the number of bad interactions that a particular qubit participates in:

Definition 8 (Interaction counter).

Given a quantum code with a $D$ -dimensional embedding $Q\subset\mathbb{R}^{D}$ , let $f_{\geq\ell}:\mathbb{R}^{D}\to\mathbb{N}$ denote the interaction counting function, where $f_{\geq\ell}(q)$ for $q\in Q$ equals the number of interactions of length at least $\ell$ that qubit $q$ participates in, and $f_{\geq\ell}(\cdot)=0$ outside of $Q$ .

Correctable sets

Like in previous works [2, 3, 1, 8], we analyze the limitations of quantum codes using correctable sets. Intuitively, a subset $U\subset Q$ of qubits is correctable if the code can correct the erasure of the qubits in $U$ . We state the definition of a correctable set for completeness, though we only interface with the definition indirectly using Lemmas 11, 12, and 13.

Definition 9 (Correctable set).

Let $U\subset Q$ be a subset of qubits in a quantum code, and let $\overline{U}=Q\backslash U$ . Let $\mathcal{D}[\overline{U}]$ and $\mathcal{D}[Q]$ denote the space of density operators associated with the sets of qubits $\overline{U}$ and $Q$ respectively. The set $U$ is correctable if there exists a recovery channel $\mathcal{R}:\mathcal{D}[\overline{U}]\to\mathcal{D}[Q]$ such that for any code state $\rho$ , we have $\mathcal{R}(\textnormal{Tr}_{U}(\rho))=\rho$ .

For an embedded set of qubits $Q\subset\mathbb{R}^{D}$ , we will say that a region $R\subset\mathbb{R}^{D}$ is correctable if the subset of all qubits contained in $R$ is a correctable subset. As an abuse of terminology, we will often refer to subsets of qubits as regions. For stabilizer and commuting projector codes, a region being correctable is equivalent to having no non-trivial logical operators supported on that region. For subsystem codes, a region $U\subset Q$ is correctable if and only if no non-trivial dressed logical operators are supported on $U$ . Note that $U$ being correctable also implies that no non-trivial bare logical operators are supported on $U$ , but the converse does not necessarily hold. This motivates the following definition.

Definition 10 (Dressed-Cleanable).

If there are no non-trivial bare logical operators supported on a region $U\subset Q$ , then we say that $U$ is dressed-cleanable [15].

We use the following notions in Lemma 11 to reason about correctable sets in subsystem codes and commuting projector codes. In a quantum code with qubits $Q$ , say sets $U_{1},\dots,U_{\ell}\subset Q$ are decoupled if there are no interactions between two distinct $U_{i}$ ’s. For a set $U\subset Q$ , let $\partial U=\partial_{+}U\cup\partial_{-}U$ be the boundary of $U$ , where $\partial_{+}U$ denotes the outer boundary of $U$ , the set of qubits outside $U$ that have an interaction with $U$ , and $\partial_{-}U=\partial_{+}\overline{U}$ is the inner boundary of $U$ .

Lemma 11 ([7, 10, 15]).

Let $Q$ be the qubits of a $[[n,k,d]]$ commuting projector or subsystem code $\mathcal{C}$ .

1.

Subset Closure: Let $U\subset Q$ be a correctable set. Then any subset $W\subset U$ is correctable.
2.

Distance Property: Let $U\subset Q$ with $|U|<d$ . Then $U$ is correctable.
3.

Union Lemma: Let $U_{1},\dots,U_{\ell}$ be decoupled, and let each $U_{i}$ be correctable. If $\mathcal{C}$ is a subsystem code, then $\bigcup_{i=1}^{\ell}U_{i}$ is dressed-cleanable. If $\mathcal{C}$ is a commuting projector code, then $\bigcup_{i=1}^{\ell}U_{i}$ is correctable.
4.

Expansion Lemma: Let $U,T\subset Q$ be correctable sets such that $T\supset\partial U$ . Then $T\cup U$ is correctable.

A key point in Lemma 11 is that the union lemma differs for commuting projector and subsystem codes. For subsystem codes, the union of decoupled and correctable sets is not necessarily correctable – only dressed-cleanable [15]. In general, being dressed-cleanable is weaker than being correctable. One of the major problems with generalizing Theorem 3 from commuting projector codes to subsystem codes is that the union lemma for subsystem codes only allows the conclusion that the union of correctable sets is dressed-cleanable. This version of the union lemma is too weak to adapt the original proof of Theorem 3 to subsystem codes. Instead, we take an alternative approach in proving Theorem 4 which is based solely on the expansion lemma.

The usefulness of reasoning about correctable sets is that the sizes of the correctable sets in a quantum code directly give bounds on the parameters:

Lemma 12 ( $A B$ Lemma – Implicit in [5], Section VIII).

Suppose that the qubits $Q$ of a $[[n,k,d]]$ subsystem code can be partitioned as $Q=A\sqcup B$ . If $A$ is dressed-cleanable, then $k\leq\left|B\right|.$

Lemma 13 ( $A B C$ Lemma [6]).

Suppose that the qubits $Q$ of a $[[n,k,d]]$ commuting projector code can be partitioned as $Q=A\sqcup B\sqcup C$ . If $A$ and $B$ are correctable, then $k\leq\left|C\right|$ .

2.2 Geometric Lemmas

In this section, we give two lemmas about $D$ -dimensional embeddings of sets. The first, Lemma 14, allows us to generalize our results from lattice embeddings to arbitrary embeddings.

Lemma 14 (Point Density).

Let $R\subseteq\mathbb{R}^{D}$ be a box with side lengths $L_{1}\geq\cdots\geq L_{D}$ . Suppose $Q\subseteq\mathbb{R}^{D}$ is an embedded set. Then

\displaystyle|R\cap Q|\leq\frac{2^{D}}{\mathrm{vol}(B_{D})}\prod_{i=1}^{D}(1+L% _{i})

(6)

where $B_{D}$ is the unit ball in $\mathbb{R}^{D}$ .

We refer the reader to [9] for the proof.

The second lemma, Lemma 15, utilizes the probabilistic method to generate a grid tiling that allows us to maintain a convenient distribution of the qubits and bad interactions in our embeddings (see Figure 3).

Lemma 15 (Tiling Lemma).

Let $X,Y\subseteq\mathbb{R}^{D}$ be two multi-sets. Let $w$ and $\ell$ be positive integers with $w\geq 4\ell$ . There exists a tiling of $\mathbb{R}^{D}$ using hypercubes of side length $w$ such that:

1.

at most a $(4\ell D/w)^{2}$ fraction of points in $X$ are within $\ell^{\infty}$ -distance $2\ell$ of a codimension- $2$ face of some hypercube,
2.

at most a $8\ell D/w$ fraction of points in $Y$ are within $\ell^{\infty}$ -distance $2\ell$ of a codimension- $1$ face of any hypercube.

We refer the reader to [9] for the proof.

Figure 3: Tiling Lemma: for fixed sets of points

X

and

Y

and a random width-

w

grid tiling, we expect a

O(\ell^{2}/w^{2})

fraction of

X

to be within a

O(\ell)

of a grid codimension-2 face, and a

O(\ell/w)

fraction of

Y

to be within

O(\ell)

of a codimension-1 face.

3 Proof of Theorem 4

We now prove Theorem 4, which covers the $d\geq k$ case of Theorem 2, our lower bound for subsystem codes. This also covers the $d\geq\sqrt{kn}$ case of Theorem 3, our generalization of [8] to $D$ -dimensions.

Theorem (Theorem 4, restated).

For all $D\geq 2$ , there exist constants $c_{0}=c_{0}(D)>0$ and $c_{1}=c_{1}(D)>0$ such that the following is true: Any $D$ -dimensional embedding of a nontrivial $[[n,k,d]]$ subsystem or commuting projector code with $d\geq c_{1}n^{\frac{D-1}{D}}$ must have at least $c_{0}d$ interactions of length at least $c_{0}\frac{d}{n^{\frac{D-1}{D}}}$ .

As mentioned after the statement of Lemma 11, the Union Lemma for subsystem codes is substantially weaker than the corresponding result for commuting projector codes. Without the ability to conclude that the union of correctable sets remains correctable, we cannot directly generalize the techniques previously employed in the proofs of the generalized BPT bound, which required alternating applications of the expansion and union lemmas [2, 8]. This poses a challenge for subsystem codes since we only obtain a dressed-cleanable set after the union lemma, and there is no straightforward way to continue with the expansion lemma, which requires correctable sets.

In view of these challenges, we take an alternative approach to the proof of Theorem 4 by repeatedly – and exclusively – applying the expansion lemma to a carefully crafted subset of qubits in order to grow our correctable region. To do this, we grow our correctable region by sweeping across our set of qubits $Q\subseteq\mathbb{R}^{D}$ one dimension at a time, changing directions and moving into a new dimension whenever the expansion process in unable to continue in the previous dimensions. The brunt of the proof is showing that this process never gets stuck, and that we are eventually able to grow our correctable set without obstruction to encompass the entire set of qubits $Q$ . In this way, we are able to bypass the usage of the union lemma altogether.

We point out that the usual way of doing this expansion [7, 6, 8] – starting with a $d^{1/D}\times\cdots\times d^{1/D}$ box and repeatedly adding the boundary – does not work for general $D$ -dimensional embeddings. For general embeddings, the qubits may not be constrained to an $O(n^{1/D})\times\cdots\times O(n^{1/D})$ box, so, at some step, the uncontrolled expansion boundaries could contain more than $d$ qubits, in which case we cannot apply the expansion lemma. For example, consider qubits embedded in 2-dimensions in a $n^{2/3}\times n^{2/3}$ square, with $\Omega(n)$ qubits distributed within $n^{1/3}$ of the box’s boundary, and the remainder randomly distributed in the square. If we expand a rectangle from anywhere inside the square, applications of the expansion lemma fail when we approach the boundary. The easiest $D$ -dimensional embeddings to realize are ones on a lattice structure contained in a $O(n^{1/D})\times\cdots\times O(n^{1/D})$ box; our general statement shows that more creative embeddings like the one above cannot save on locality.

The general expansion process is quite involved in $D$ -dimensions. We refer the reader to Appendix A for an extended exposition of the $2$ -dimensional case as an illustration of the basic idea of the proof, as well as the full proof in $D-$ dimensions.

4 Proof of Theorem 5

We now prove Theorem 5, which covers the $k\geq d$ case of Theorem 2, our lower bound for subsystem codes.

Theorem (Theorem 5, restated).

For all $D\geq 2$ , there exist constants $c_{0}=c_{0}(D)>0$ and $c_{1}=c_{1}(D)>0$ such that the following is true: Any $D$ -dimensional embedding of a $[[n,k,d]]$ subsystem code with $kd^{\frac{1}{D-1}}\geq c_{1}n$ must have at least $c_{0}k$ interactions of length at least $c_{0}(\frac{kd^{\frac{1}{D-1}}}{n})^{\frac{D-1}{D}}$ .

First, we state two lemmas that help us find large correctable sets in a $D$ -dimensional embedding of a quantum code. The first is a generalization of the “holographic principle” for error correction in [5], which shows that the area, rather than the volume, governs the size of correctable sets. Recall that $f_{\geq\ell}(V)$ counts the number of interactions involving qubits in $V$ with length at least $\ell$ (see Definition 8).

Lemma 16 (Holographic Principle).

Suppose we have a $[[n,k,d]]$ quantum code (either commuting projector or subsystem) with an embedding $Q\subset\mathbb{R}^{D}$ , and suppose $\ell\leq\frac{1}{8\sqrt{D}}d^{1/D}$ . Let $V\subset Q$ be the subset of qubits contained in a box with sides of length at most

\displaystyle w_{0}\stackrel{{\scriptstyle\rm def}}{{=}}\left(\frac{% \operatorname*{vol}(B_{D})}{2\cdot 4^{D+1}D}\cdot\frac{d}{\ell}\right)^{\frac{% 1}{D-1}}.

(7)

If $f_{\geq\ell}(V)\leq d/10$ , then $V$ is correctable.

We refer the reader to [9] for the formal proof.

If we divide $\mathbb{R}^{D}$ into cubes using Lemma 15, most cubes will be “good” in that they contain $\ll d$ long-ranged interactions (see footnote $5$ of [8]). Lemma 16 then says that all the good cubes are correctable. How do we handle the cubes with large numbers of bad qubits? In [8], the solution was to further subdivide the bad cubes into sufficiently small rectangles, most of which then contains a sufficiently small number of bad qubits. The same strategy works in $D$ -dimensions:

Lemma 17 (Subdivision).

Let $w,\ell$ and $d_{1}$ be positive real numbers. Let $f:\mathbb{R}^{D}\to\mathbb{N}$ be a finitely supported function. Let $R$ be a $h\times w^{D-1}$ box, with $h\geq 5\ell$ and $f(R)\geq d_{1}$ . Then there exists a division of $R$ by hyperplanes orthogonal to $x_{1}$ into boxes $R_{1},\dots,R_{m}$ such that:

1.

Each box has dimensions $h_{i}\times w^{D-1}$ , with $h_{i}\geq 5\ell$ .
2.

Each $R_{i}$ satisfies either (i) $f(R_{i})\leq d_{1}$ or (ii) has $h_{i}\leq 10\ell$ .
3.

The number of boxes $m$ is at most $\frac{2f(R)}{d_{1}}$ .

We refer the reader to [9] for the formal proof.

Finally, we collect a few inequalities that we will frequently use in the proof of Theorems 5 and 6.

Lemma 18.

Let

\displaystyle w_{0}=\left(\frac{\operatorname*{vol}(B_{D})}{2\cdot 4^{D+1}D}% \cdot\frac{d}{\ell}\right)^{\frac{1}{D-1}},\qquad\text{and}\qquad c=\frac{% \operatorname*{vol}(B_{D})^{\frac{1}{D}}}{400\alpha D}

(8)

for some $\alpha\geq 1$ . Suppose that $\ell$ satisfies $\ell\leq cd^{\frac{1}{D}}$ . Then we have

1.

$\displaystyle\frac{2^{D}}{\operatorname*{vol}(B_{D})}(2w_{0})^{D-1}\ell=\frac{% d}{16D},$
2.

$\displaystyle w_{0}\geq 100\alpha D\ell,$
3.

$\displaystyle w_{0}\geq\frac{1}{90\sqrt{D}}\left(\frac{d}{\ell}\right)^{\frac{% 1}{D-1}}.$

We are now ready to prove Theorem 5.

Proof of Theorem 5.

We give a proof by contradiction, where we first assume that we have an embedding of a subsystem code with $k$ logical qubits that has few long interactions, and then show that the code’s dimension must actually be less than $k$ . With hindsight, choose $c_{0}=\frac{\operatorname*{vol}(B_{D})^{\frac{1}{D}}}{400D}$ . Note that we have $c_{0}\leq 1/(200D)\leq 1/400$ for $D\geq 2$ . Choose $c_{1}=(1/c_{0})^{\frac{D}{D-1}}$ . Suppose we have a $[[n,k,d]]$ subsystem code with a $D$ -dimensional embedding $Q\subset\mathbb{R}^{D}$ satisfying $kd^{\frac{1}{D-1}}\geq c_{1}n$ . Let

\displaystyle\ell=c_{0}\left(\frac{kd^{\frac{1}{D-1}}}{n}\right)^{\frac{D-1}{D% }},

(9)

and note that we have $1\leq\ell\leq c_{0}d^{\frac{1}{D}}<\frac{1}{8\sqrt{D}}d^{\frac{1}{D}}$ , where the first upper bound follows from $k\leq n$ , and the lower bound from $kd^{\frac{1}{D-1}}\geq c_{1}n$ .

Now assume for the sake of contradiction that the embedding $Q\subset\mathbb{R}^{D}$ has at most $c_{0}k$ interactions of length $\geq\ell$ . Call an interaction long if its length is at least $\ell$ and short otherwise. Call a qubit $v\in Q$ bad if it participates in a long interaction and good otherwise. Then the function $f_{\geq\ell}(v)$ counts the number of long interactions that the qubit $v$ participates in. By assumption, there are at most $c_{0}k$ long interactions, so the total number of bad qubits is at most $\sum_{v\in Q}f_{\geq\ell}(v)\leq 2c_{0}k$ . Now we construct a division of $\mathbb{R}^{D}$ into $\mathcal{A}\sqcup\mathcal{B}$ that outlines the partition of the qubits $Q=A\sqcup B$ . Let

\displaystyle w_{0}=\left(\frac{\operatorname*{vol}(B_{D})}{2\cdot 4^{D+1}D}% \cdot\frac{d}{\ell}\right)^{\frac{1}{D-1}}

(10)

as in Lemma 16. It follows from Lemma 18(2) that $w_{0}\geq 100D\ell$ . Apply Lemma 15 with $Y=Q$ (and with $X$ arbitrary). This produces a tiling of $\mathbb{R}^{D}$ into cubes $\{S_{m}\}_{m\in\mathbb{Z}^{D}}$ of side length $w_{0}$ , where at most $\frac{8D\ell}{w_{0}}n$ qubits of $Q$ are within $\ell_{\infty}$ distance $2\ell$ of some codimension-1 face of some cube. We call a cube $S_{m}$ good if $f_{\geq\ell}(S_{m})<d/10$ and bad otherwise. Now apply Lemma 17, with $d_{1}=d/10$ , to decompose each bad cube $S_{m}$ into boxes $R_{m,1},\cdots,R_{m,n_{m}}$ . All boxes obtained in this way will also be called bad. This process results in a division of $\mathbb{R}^{D}$ into good cubes and bad boxes. It follows from Lemma 17 (item 3) that the total number of bad boxes is no more than

\displaystyle\sum_{m:S_{m}\text{bad}}\frac{2f_{\geq\ell}(S_{m})}{d/10}\leq\sum% _{m}\frac{2f_{\geq\ell}(S_{m})}{d/10}\leq\frac{20}{d}\sum_{m}f_{\geq\ell}(S_{m% })\leq\frac{40}{d}c_{0}k<\frac{k}{10d}.

(11)

Now we define the division $\mathcal{A}\sqcup\mathcal{B}$ as follows:

$\blacksquare$

$\mathcal{B}$ is the set of all points within $\ell_{\infty}$ distance $2\ell$ of some codimension-1 face of either a good cube $S_{m}$ or a bad box $R_{m,i}$ .
$\blacksquare$

$\mathcal{A}$ is the set of points not in $\mathcal{B}$ .

Note that we can perturb the tiling slightly in order to ensure that no qubits lie on the boundary of any subregion of $\mathcal{A}$ or $\mathcal{B}$ .

Having constructed the division, we will now construct a corresponding partition of qubits $Q=A\sqcup B$ such that $A$ is dressed-cleanable and $\left|B\right|<k$ . This will give us our desired contradiction from Lemma 12. We define the partition $Q=A\sqcup B$ as follows:

$\blacksquare$

$A$ is the set of all good qubits in region $\mathcal{A}$ .
$\blacksquare$

$B$ is the set of all remaining qubits. These are either good qubits in region $\mathcal{B}$ or bad qubits.

It remains to check that $A$ is dressed-cleanable and that $\left|B\right|<k$ . We refer the reader to [9] for the formal proof. $\hfill\blacktriangleleft$

5 Proof of Theorem 6

Figure 4: The division of the plane into regions

\mathcal{A}

(lined blue),

\mathcal{B}

(red and pink crosshatch), and

\mathcal{C}

(solid yellow) for the proof of Theorem 6. The region

\mathcal{B}^{\prime}

(pink crosshatch) is also indicated in the figure on the right. These regions inform our qubit division

Q=A\sqcup B\sqcup C

. We use this division in different ways for the cases

k\geq d

and

d\geq k

. When

k\geq d

(left), we ignore

\mathcal{B}^{\prime}

, and also subdivide any bad squares into bad rectangles. When

d\geq k

(right), there are no bad squares, but we need to explicitly consider the region

\mathcal{B}^{\prime}

.

We now prove Theorem 6, which, together with Theorem 4, yields Theorem 3, our generalization of the main result of [8] to case of $D$ -dimensional embeddings.

Theorem (Theorem 6, restated).

For all $D\geq 2$ , there exist constants $c_{0}=c_{0}(D)>0$ and $c_{1}=c_{1}(D)>0$ such that the following is true: Any $D$ -dimensional embedding of a $[[n,k,d]]$ commuting projector code with $kd^{\frac{2}{D-1}}\geq c_{1}n$ must have at least $c_{0}k$ interactions of length $c_{0}(\frac{kd^{\frac{2}{D-1}}}{n})^{\frac{D-1}{2D}}$ .

Proof.

For $d\geq\sqrt{kn}$ , the result follows from Theorem 4, so it suffices to consider the case where $d\leq\sqrt{kn}$ . With hindsight, choose $c_{0}=\frac{\operatorname*{vol}(B_{D})^{\frac{1}{D}}}{800D^{2}}$ , and let $c_{1}=(1/c_{0})^{\frac{2D}{D-1}}$ . Note that $c_{0}\leq 1/(400D^{2})\leq 1/400$ . Suppose we have a $[[n,k,d]]$ commuting projector code with a $D$ -dimensional embedding $Q\subset\mathbb{R}^{D}$ satisfying $kd^{\frac{2}{D-1}}\geq c_{1}n$ . Let

\displaystyle\ell=c_{0}\left(\frac{kd^{\frac{2}{D-1}}}{n}\right)^{\frac{D-1}{2% D}}.

(12)

Note that we have $1\leq\ell\leq c_{0}d^{\frac{1}{D}}\leq\frac{1}{8\sqrt{D}}d^{\frac{1}{D}}$ , where the lower bound follows from $kd^{\frac{2}{D-1}}\geq c_{1}n$ and the first upper bound from the $k\leq n$ .

Now assume for the sake of contradiction that the embedding $Q\subset\mathbb{R}^{D}$ has at most $c_{0}\max(k,d)$ interactions of length $\geq\ell$ . Call an interaction long if its length is at least $\ell$ and short otherwise. Call a qubit $v\in Q$ bad if it participates in a long interaction and good otherwise. The function $f_{\geq\ell}(v)$ counts the number of long interactions that the qubit $v$ participates in. By assumption, the total number of long interactions is at most $c_{0}\max(k,d)$ , so the total number of bad qubits is at most $\sum_{v\in Q}f_{\geq\ell}(v)\leq 2c_{0}\max(k,d)$ . We will construct a division of $\mathbb{R}^{D}$ into subsets $\mathcal{A}\sqcup\mathcal{B}\sqcup\mathcal{C}$ that will inform the partition of the qubits $Q=A\sqcup B\sqcup C$ . Let

\displaystyle w_{0}=\left(\frac{\operatorname*{vol}(B_{D})}{2\cdot 4^{D+1}D}% \frac{d}{\ell}\right)^{\frac{1}{D-1}},

(13)

as in Lemma 16. Note that it follows from Lemma 18 that $w_{0}\geq 200D^{2}\ell$ and $w_{0}\geq\frac{1}{90\sqrt{D}}(d/\ell)^{\frac{1}{D-1}}$ .

Apply Lemma 15 with $X=Q$ and with $Y$ as the multiset where each qubit $v$ appears with multiplicity $f_{\geq\ell}(v)$ . This gives a partition of $\mathbb{R}^{D}$ into a set of cubes $\{S_{m}\}_{m\in\mathbb{Z}^{D}}$ of side length $w_{0}$ . By construction, at most $\frac{16D^{2}\ell^{2}}{w_{0}^{2}}n$ qubits of $Q$ are within $\ell_{\infty}$ distance $2\ell$ of a codimension-2 face of some cube, and at most $\frac{8D\ell}{w_{0}}\cdot 2c_{0}\max(k,d)$ bad interactions involve a qubit within $\ell_{\infty}$ distance $2\ell$ of a codimension-1 face of some cube. We call a cube $S_{m}$ good if $f_{\geq\ell}(S_{m})<d/10$ and bad otherwise. Now apply Lemma 17 to decompose each bad cube into boxes $R_{m,1},\cdots,R_{m,n_{m}}$ . All boxes obtained by subdividing a bad cube will also be called bad. This process results in a division of $\mathbb{R}^{D}$ into good cubes and bad boxes. By Lemma 17 (item 3), the total number of bad boxes is no more than

\displaystyle\sum_{m:S_{m}\text{bad}}\frac{2f_{\geq\ell}(S_{m})}{d/10}\leq\sum% _{m}\frac{2f_{\geq\ell}(S_{m})}{d/10}\leq\frac{20}{d}\sum_{m}f_{\geq\ell}(S_{m% })\leq\frac{40}{d}c_{0}\max(k,d)<\frac{\max(k,d)}{10d}.

(14)

Now we define the division $\mathcal{A}\sqcup\mathcal{B}\sqcup\mathcal{C}$ as follows:

$\blacksquare$

$\mathcal{C}$ is the set of all points within $\ell_{\infty}$ distance $2\ell$ of some codimension-2 face of a good cube $S_{m}$ or a bad box $R_{m,i}$ .
$\blacksquare$

$\mathcal{B}$ is the set of all points not already in $\mathcal{C}$ and within $\ell_{\infty}$ distance $\ell$ of some codimension-1 face of a good cube $S_{m}$ or bad box $R_{m,i}$ .
$\blacksquare$

$\mathcal{B}^{\prime}\subset\mathcal{B}$ is the set of all points not already in $\mathcal{C}$ and within $\ell_{\infty}$ distance $2\ell$ of some codimension-1 face of a good cube $S_{m}$ .
$\blacksquare$

$\mathcal{A}$ is the set of points not in $\mathcal{B}$ or $\mathcal{C}$ .

Note that we can perturb the tiling slightly in order to ensure that no qubits lie on the boundary of any subregion of $\mathcal{A}$ , $\mathcal{B}$ , $\mathcal{B^{\prime}}$ , or $\mathcal{C}$ .

Having defined the division of $\mathbb{R}^{D}$ , we will now construct our partition of qubits $Q=A\sqcup B\sqcup C$ . A sketch of the high-level ideas are as follows: We aim to define our qubit partition with the goal of having $A, B$ be correctable, and $\left|C\right|<k$ . This will lead to the desired contradiction using Lemma 13. There are two cases to consider, depending on whether $k\geq d$ or $k\leq d$ . When $k\geq d$ , we have $2c_{0}k\ll k$ bad qubits, which can then be directly placed in $C$ without affecting the requirement that $|C|<k$ . When $k\leq d$ , we have $2c_{0}d\ll d$ bad qubits, and the set of all bad qubits is itself correctable. Our chosen division of $\mathbb{R}^{D}$ implies that very few bad qubits can interact with the qubits in $\mathcal{B}$ , so the union lemma suggests that we can add almost all of the bad qubits to $\mathcal{B}$ while preserving its correctability. We now continue with our proof, divided into the two cases $k\geq d$ and $k\leq d$ .

Case 1: $k\geq d$ .

We define the partition of qubits $Q=A\sqcup B\sqcup C$ as follows:

$\blacksquare$

$C$ is the set of qubits in region $\mathcal{C}$ , along with all bad qubits.
$\blacksquare$

$B$ is the set of all good qubits in region $\mathcal{B}$
$\blacksquare$

$A$ is the set of all good qubits in region $\mathcal{A}$ .

It’s clear that this is indeed a partition of $Q$ . It remains to show that $A, B$ are correctable, and that $|C|<k$ . This gives us a contradiction with the fact that $A$ and $B$ are correctable through Lemma 13. We refer the reader to [9] for the formal proof.

Case 2: $d\geq k$ .

From equation (13), the total number of bad boxes is at most $\max(k,d)/(10d)=1/10$ , which is less than $1$ . It follows that there are no bad boxes in this case, only good cubes. We define the partition of qubits $Q=A\sqcup B\sqcup C$ in this case as follows:

$\blacksquare$

$C$ consists of the set of qubits in region $\mathcal{C}$ , together with all qubits participating in a long interaction with a qubit in $\mathcal{B}^{\prime}$ (including the bad qubits in $\mathcal{B}^{\prime})$ .
$\blacksquare$

$B$ is the set of good qubits in region $\mathcal{B}$ , together with the bad qubits not in $C$ .
$\blacksquare$

$A$ is the set of good qubits in region $\mathcal{A}$ .

It’s clear that this is a partition of the qubits in $Q$ . It remains to check that $A, B$ are correctable and $\left|C\right|<k$ . This gives us our desired contradiction using Lemma 13. We refer the reader to [9] for the formal proof.

We have obtained a contradiction in both the $d\leq k$ and $d\geq k$ cases, and this completes the proof of the theorem. $\hfill\blacktriangleleft$

6 Construction for Upper Bounds

The bounds derived in Theorems 2 and 3 are tight in both the interaction count $M^{*}$ and the interaction length $\ell^{*}$ . Tightness is shown by constructing explicit examples of embedded codes which saturate the interaction count or length. For the interaction count, it suffices to consider an asymptotically good quantum low-density parity-check (qLDPC) code [14, 12], which has $O(M^{*})=O(\max(k,d))$ interactions of any length. Since a stabilizer code can also be regarded as a subsystem code with zero gauge qubits, this shows that both Theorem 2 and 3 are tight in terms of interaction count. This is covered by Theorem 1.3 of [8].

We now describe constructions that show the interaction length is optimal in Theorem 2 and Theorem 3. In both cases, we construct a code that saturates the bound for interaction length by concatenating an asymptotically good qLDPC code with a geometrically local code which saturates the Bravyi and BPT bounds, respectively.

6.1 Subsystem codes

We start by showing the interaction length for subsystem codes (Theorem 2) is optimal. We will define a concatenated subsystem code composed of an asymptotically good qLDPC code, together with a subsystem code which is geometrically local in $D$ -dimensions and saturates the Bravyi bound. For the local subsystem code, we employ the “wire code” construction of Baspin and Williamson [4].

Theorem 19 (Wire code [4]).

For all $D\geq 2$ , there exists an $\varepsilon>0$ such that, for all positive integers $n$ there exists a subsystsem code with parameters $[[n,\geq\varepsilon n^{\frac{D-1}{D}},\geq\varepsilon n^{\frac{D-1}{D}}]]$ that has a set of gauge generators that are $O(1)$ -local in a $D$ -dimensional embedding.

The concatenation procedure for subsystem codes is formally identical to the process for stabilizer codes. Namely, if $\mathcal{C}_{1}=[[n_{1},k_{1}]]$ and $\mathcal{C}_{2}=[[n_{2},k_{2}]]$ are subsystem codes, then their concatenation $\mathcal{C}_{2}\circ\mathcal{C}_{1}$ is defined using $n_{2}$ blocks of the inner code $\mathcal{S}_{1}$ and $k_{1}$ copies of the outer code $\mathcal{C}_{2}$ . Let $q_{ij}$ be the $i$ th logical qubit of the $j$ th $\mathcal{S}_{1}$ block. Then the concatenated code is defined by replacing the $j$ th physical qubit of the $i$ th $\mathcal{C}_{2}$ block with $q_{ij}$ .

Lemma 20 (Concatenated Subsystem Codes).

Let $\mathcal{C}_{1}=[[n_{1},k_{1},d_{1},g_{1}]]$ and $\mathcal{C}_{2}=[[n_{2},k_{2},d_{2},g_{2}]]$ be two subsystem codes. Then there exists a subsystem code $\mathcal{C}=\mathcal{C}_{2}\circ\mathcal{C}_{1}=[[n_{1}n_{2},k_{1}k_{2},d\geq d% _{1}d_{2},k_{1}g_{2}+n_{2}g_{1}]]$ , called the concatenation of $\mathcal{C}_{2}$ and $\mathcal{C}_{1}$

Theorems 19 and 20 together give the desired construction. We state the result below and refer the reader to [9] for the formal proof.

Theorem 21 (Optimality of Interaction Length for Subsystem Codes).

For all $D\geq 2$ , there exists a constant $c_{1}=c_{1}(D)>0$ such that the following holds: for all $n,k,d>0$ with $k,d\leq n$ satisfying $kd^{\frac{1}{D-1}}\geq c_{1}n$ or $d\geq c_{1}n^{\frac{D-1}{D}}$ , there exists an $[[n,\geq k,\geq d]]$ subsystem code with a $D$ -dimensional embedding containing no interactions of length at least

\displaystyle\ell=\max\bigg(\frac{d}{n^{\frac{D-1}{D}}},\bigg(\frac{kd^{\frac{% 1}{D-1}}}{n}\bigg)^{\frac{D-1}{D}}\bigg).

(15)

6.2 Commuting Projector Codes

We now show the interaction length in Theorem 3 is optimal. The construction is very similar to the one used in Theorem 1.3 of [8], except generalized to $D$ -dimensions. In 2D, the surface code offers a simple and natural candidate for a geometrically local code that saturates the BPT bound. In higher dimensions, we instead use the family of “subdivided codes” constructed by Lin, Wills and Hsieh [13].

Theorem 22 (Subdivided code [13]).

For all $D\geq 2$ , there exists an $\varepsilon>0$ such that, for all positive integers $n$ there exists a stabilizer code with parameters $[[n,\geq\varepsilon n^{\frac{D-2}{D}},\geq\varepsilon n^{\frac{D-1}{D}}]]$ that has a set of stabilizer generators that are $O(1)$ -local in a $D$ -dimensional embedding.

The optimality of the interaction length follows by concatenating a good qLDPC code with the subdivided code. We refer the reader to [9] for the formal proof.

Theorem 23 (Optimality of Interaction Length for Stabilizer Codes).

For all $D\geq 2$ , there exists a constant $c_{1}=c_{1}(D)>0$ such that the following holds: for all $n,k,d>0$ with $k,d\leq n$ satisfying either $kd^{\frac{2}{D-1}}\geq c_{1}\cdot n$ or $d\geq c_{1}\cdot n^{\frac{D-1}{D}}$ , there exists a $[[n,\geq k,\geq d]]$ quantum stabilizer code with a $D$ -dimensional embedding containing no interactions of length at least

\displaystyle\ell=\max\bigg(\frac{d}{n^{\frac{D-1}{D}}},\bigg(\frac{kd^{\frac{% 2}{D-1}}}{n}\bigg)^{\frac{D-1}{2D}}\bigg).

(16)

References

[1] Nouédyn Baspin, Venkatesan Guruswami, Anirudh Krishna, and Ray Li. Improved rate-distance trade-offs for quantum codes with restricted connectivity. Quantum Science and Technology, 10(1):015021, 2024.
[2] Nouédyn Baspin and Anirudh Krishna. Connectivity constrains quantum codes. Quantum, 6:711, 2022.
[3] Nouédyn Baspin and Anirudh Krishna. Quantifying nonlocality: How outperforming local quantum codes is expensive. Physical Review Letters, 129(5):050505, 2022.
[4] Nouédyn Baspin and Dominic Williamson. Wire codes. arXiv preprint arXiv:2410.10194, 2024.
[5] Sergey Bravyi. Subsystem codes with spatially local generators. Physical Review A, 83(1), January 2011. doi:10.1103/physreva.83.012320.
[6] Sergey Bravyi, David Poulin, and Barbara Terhal. Tradeoffs for reliable quantum information storage in 2D systems. Physical Review Letters, 104(5):050503, 2010. doi:10.1103/PhysRevLett.104.050503.
[7] Sergey Bravyi and Barbara Terhal. A no-go theorem for a two-dimensional self-correcting quantum memory based on stabilizer codes. New Journal of Physics, 11(4):043029, 2009. doi:10.1088/1367-2630/11/4/043029.
[8] Samuel Dai and Ray Li. Locality vs quantum codes. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, pages 677–688, 2025.
[9] Samuel Dai, Ray Li, and Eugene Tang. Optimal locality and parameter tradeoffs for subsystem codes. arXiv preprint arXiv:2503.22651, 2025.
[10] Jeongwan Haah and John Preskill. Logical-operator tradeoff for local quantum codes. Physical Review A, 86(3), September 2012. doi:10.1103/physreva.86.032308.
[11] Yifan Hong, Matteo Marinelli, Adam M Kaufman, and Andrew Lucas. Long-range-enhanced surface codes. Physical Review A, 110(2):022607, 2024.
[12] Anthony Leverrier and Gilles Zémor. Quantum tanner codes. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 872–883. IEEE, 2022.
[13] Xingjian Li, Ting-Chun Lin, and Min-Hsiu Hsieh. Transform arbitrary good quantum ldpc codes into good geometrically local codes in any dimension. arXiv preprint arXiv:2408.01769, 2024.
[14] Pavel Panteleev and Gleb Kalachev. Asymptotically good quantum and locally testable classical ldpc codes. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 375–388, 2022.
[15] Fernando Pastawski and Beni Yoshida. Fault-tolerant logical gates in quantum error-correcting codes. Physical Review A, 91(1), January 2015. doi:10.1103/physreva.91.012305.

Appendix A Proof of Theorem 4

In this appendix, we first give a detailed sketch of the proof of Theorem 4 for the case of $2$ -dimensional embeddings. This is meant as a simplified illustration of the proof idea in the general $D$ -dimensional case, which may be difficult to visualize. We then give the full proof in $D$ -dimensions.

A.1 Detailed Sketch of Theorem 4 in $2$ -dimensions

Let $Q$ be a $2$ -dimensional embedding of a subsystem code $\mathcal{C}=[[n,k,d]]$ satisfying $d\geq 32\sqrt{n}$ . Without loss of generality, we may assume that all of our qubits are contained in the interior of a large square $[\ell,A-\ell]\times[\ell,A-\ell]$ , for some integer $A\in\mathbb{N}$ . We remove a border of width $\ell$ so that we do not have to worry about edge cases later in our proof. Suppose for the sake of contradiction that there exists at most $d/4$ interactions of length at least $\ell=\frac{d}{32\sqrt{n}}$ . Note that our choice of code parameters ensures that we have $1\leq\ell\leq\sqrt{n}/32$ . We will call any qubit participating in a length $\geq\ell$ interaction a bad qubit. Let $B$ be the set of all bad qubits. Then by assumption, $|B|\leq d/2$ . Given any region $R\subset\mathbb{R}^{2}$ , we will say that $R$ is correctable if and only if $Q\cap R$ is correctable.

The basic idea of the proof is as follows. We wish to show that, given our assumption on the number of long interactions, a small correctable region can be iteratively grown without bound using the expansion lemma. Eventually the correctable region will encompass the entire set of qubits $Q$ , which is a contradiction with our initial assumption that the code is non-trivial. We do this by first expanding along the $x_{1}$ -direction, and then switching to the $x_{2}$ -direction whenever we are unable to continue in the $x_{1}$ -direction. The details for the two cases are given below.

A.1.1 Expansion in the $x_{1}$ -direction

Let us imagine starting with a region of the form of a vertical strip $V[a_{1}]=[0,a_{1}]\times\mathbb{R}$ , for some $a_{1}>0$ . If $a_{1}<\ell$ , then $V[a_{1}]$ contains no qubits by assumption, so it is vacuously correctable. Now, given an existing correctable region of the form $V[a_{1}]$ , we wish to apply the expansion lemma to obtain a larger correctable set of the form $V[a_{1}+\ell]$ . This will be possible provided that the number of qubits in the boundary of $V[a_{1}]$ is sufficiently small so that the boundary set itself is correctable. We will formalize this requirement by saying that a number $a_{1}\in\mathbb{R}$ is “good” if the density of qubits around the line $x=a_{1}$ is low. Formally, $a_{1}\in\mathbb{R}$ is a good $x_{1}$ -coordinate if the set $[a_{i}-\ell,a_{1}+\ell]\times\mathbb{R}$ contains at most $\ell\sqrt{n}$ qubits, and bad otherwise.

The boundary of $V[a_{1}]$ consists of all qubits within a distance $\ell$ of the line $x=a_{1}$ , together with a subset of the bad qubits. Therefore the boundary is a subset of $B\cup[a_{1}-\ell,a_{1}+\ell]\times\mathbb{R}$ . If $a_{1}$ is good, then by definition this subset contains at most

\displaystyle d/2+\ell\sqrt{n}=d/2+d/32<d

(17)

qubits, and is hence correctable. It follows by expansion and subset closure that if $V[a_{1}]$ is correctable and $a_{1}$ is good, then $V[a_{1}+\ell]\subset V[a_{1}]\cup\partial V[a_{1}]$ is also correctable. This gives us an easy way to grow the sets $V[a_{1}]$ . However, this process cannot continue indefinitely, since there is no guarantee at each step that the new coordinate $a_{1}+\ell$ is good. When $a_{1}+\ell$ is a bad coordinate, our expansion process gets stuck. To get unstuck, we will fill in the stretch around the bad coordinate $a_{1}+\ell$ by expanding in the $x_{2}$ -direction. After this gap containing bad $x_{1}$ -coordinates has been filled, we can continue expanding in the $x_{1}$ -direction until we reach our next obstacle.

A.1.2 Stuck in the $x_{1}$ -direction, expand along the $x_{2}$ -direction

Now we formalize the process of expanding in the $x_{2}$ direction. Given a bad coordinate $a_{1}$ , we will define $\textsf{Next}(a_{1})$ to be the “next available” good coordinate. More precisely, we define

\displaystyle\textsf{Next}(a_{1})=\inf G_{>a_{1}}+\gamma,

(18)

where $G_{>a_{1}}$ is the set of all good coordinates larger than $a_{1}$ , and $\gamma>0$ is a sufficiently small value so that we actually have $\textsf{Next}(a_{1})\in G_{>a_{1}}$ .²²2The small constant $\gamma$ is necessary since the set of good coordinates is an open set, and as such does not contain its own infimum. A bit of thought reveals that it is sufficient to take $\gamma$ smaller than the minimum element of $\bigcup_{q\neq q^{\prime}}\{|q_{1}-q_{1}^{\prime}|,||q_{1}-q_{1}^{\prime}|-2% \ell|\}$ , where $q_{1},q_{1}^{\prime}$ denote the $x_{1}$ -coordinates of qubits $q,q^{\prime}\in Q$ . Given a set $V[a_{1}]$ where $a_{1}$ is good but $a_{1}+\ell$ is bad, let us define $V[a_{1},a_{2}]$ to be

\displaystyle V[a_{1},a_{2}]=V[a_{1}]\cup([a_{1},\textsf{Next}(a_{1}+\ell)]% \times[0,a_{2}])=([0,a_{1}]\times\mathbb{R})\cup([a_{1},\textsf{Next}(a_{1}+% \ell)]\times[0,a_{2}]).

(19)

We will call sets $V[a_{1},a_{2}]$ defined this way legal sets. Our goal is to show that given a correctable legal set $V[a_{1},a_{2}]$ , we can always apply expansion in the $x_{2}$ -direction to obtain a new correctable legal set $V[a_{1},a_{2}+\ell]$ .

The key observation now is that the additional block $[a_{1},\textsf{Next}(a_{1}+\ell)]\times[0,a_{2}]$ in $V[a_{1},a_{2}]$ must be thin in the $x_{1}$ -direction. Indeed, the entire interval $[a_{1}+\ell,\textsf{Next}(a_{1}+\ell)-\gamma]$ consists of bad coordinates. Any strip of width $2\ell$ centered around a bad coordinate contains at least $\ell\sqrt{n}$ qubits, and since we only have a total of $n$ qubits, the set $[a_{1}+\ell,\textsf{Next}(a_{1}+\ell)-\gamma]\times\mathbb{R}$ can fit at most $\lfloor{\sqrt{n}/\ell}\rfloor$ such strips inside. It follows that we have

\displaystyle\textsf{Next}(a_{1}+\ell)-\gamma-a_{1}-\ell<2\ell\left\lfloor% \frac{\sqrt{n}}{\ell}\right\rfloor+2\ell,

(20)

which implies

\displaystyle\textsf{Next}(a_{1}+\ell)-a_{1}<2\sqrt{n}+4\ell.

(21)

Now, consider the boundary of a correctable legal set $V[a_{1},a_{2}]$ . This will be a subset of

$\displaystyle B$	$\displaystyle\cup\underbrace{[a_{1}-\ell,a_{1}+\ell]\times\mathbb{R}}_{S_{1}}$
	$\displaystyle\cup\underbrace{[\textsf{Next}(a_{1}+\ell)-\ell,\textsf{Next}(a_{% 1}+\ell)+\ell]\times\mathbb{R}}_{S_{2}}$
	$\displaystyle\cup\underbrace{[a_{1},\textsf{Next}(a_{1}+\ell)]\times[a_{2}-% \ell,a_{2}+\ell]}_{S_{3}}.$	(22)

Since $a_{1}$ and $\textsf{Next}(a_{1}+\ell)$ are good coordinates, we have

\displaystyle|Q\cap S_{1}|+|Q\cap S_{2}|\leq 2\ell\sqrt{n}

(23)

by assumption. By Lemma 14, the number of qubits in the subset $S_{3}$ is bounded above by

\displaystyle|Q\cap S_{3}|\leq\frac{4}{\pi}(2\ell+1)(2\sqrt{n}+4\ell+1)\leq 9% \ell\sqrt{n}.

(24)

Therefore the boundary of $V[a_{1},a_{2}]$ contains at most

\displaystyle|B|+|Q\cap S_{1}|+|Q\cap S_{2}|+|Q\cap S_{3}|\leq\frac{d}{2}+11% \ell\sqrt{n}=\frac{27}{32}d<d

(25)

qubits, and is hence correctable. It follows by expansion and subset closure that if $V[a_{1},a_{2}]$ is a correctable legal set, then $V[a_{1},a_{2}+\ell]$ is again a correctable legal set. We can therefore continue expanding in the $x_{2}$ -direction until we reach $V[a_{1},A]=V[\textsf{Next}(a_{1}+\ell)]$ . This is a vertical strip with a good boundary coordinate $\textsf{Next}(a_{1}+\ell)$ . We can therefore return to the previous case and proceed to expand along the $x_{1}$ -direction again. This process can now continue indefinitely, alternating between the $x_{1}$ and $x_{2}$ -directions whenever we get stuck again. In this way, starting from an initial correctable set, say the vacuously correctable region $V[\ell/2]$ , we can iteratively grow our correctable region without bound to encompass the entire set of qubits $Q$ . Thus we arrive at our desired contradiction.

Figure 5: Sketch of the expansion process in 2 dimensions. The blue region is

V[a_{1}]

and the pink region is

[a_{1},\textsf{Next}(a_{1}+\ell)]\times[0,a_{2}]

. The crosshatched region (labeled

F

in the proof of Theorem 4) contains the boundary of

V[a_{1},a_{2}]

.

A.2 Proof of Theorem 4 in $𝑫$ -dimensions

For notational convenience, we grow the correctable region from low coordinates to high coordinates for this proof. For a set $S$ , we write $S^{\leq D}=S\cup S^{2}\cup\cdots\cup S^{D}$ .

Proof.

With hindsight, set $c_{1}=2(6^{D}D/\operatorname*{vol}(B_{D}))^{D/(D-1)}$ . Suppose $n, k, d$ are code parameters with $d\geq c_{1}n^{\frac{D-1}{D}}$ . With hindsight, choose

\displaystyle\ell=\frac{\operatorname*{vol}(B_{D})}{6^{D}Dn^{(D-1)/D}}d,

(26)

so that $1<\ell<\frac{n^{1/D}}{4^{D}D}$ . Let $Q$ be a $D$ -dimensional embedding of a $[[n,k,d]]$ subsystem code $\mathcal{C}$ with $d\geq k$ , and suppose there are at most $d/4$ interactions of length at least $\ell$ .

Let $B$ denote the set of qubits participating in long range interactions, so that $|B|\leq d/2$ . Without loss of generality, we may assume all the qubits are in the box $[\ell,A-\ell]^{D}$ for some large integer $A$ . Choose a sufficiently small constant $\gamma>0$ . With hindsight, $\gamma$ less than the minimum nonzero element of $\bigcup_{i\in[D],q\neq q^{\prime}}\{|q_{i}-q_{i}^{\prime}|,||q_{i}-q_{i}^{% \prime}|-2\ell|\}$ suffices.

For $i=1,\dots,D-1$ , call real number $x_{i}\in\mathbb{R}$ $i$ -good if $\mathbb{R}^{i-1}\times[x_{i}-\ell,x_{i}+\ell]\times\mathbb{R}^{D-i}$ has at most $\ell n^{(D-1)/D}$ qubits and $i$ -bad otherwise. By convention, we will consider every real number to be $i$ -good when $i=D$ . An $i$ -bad number represents an $i$ -th-coordinate-value where we would “get stuck” and need to start expanding in a different direction.

For $i=1,\dots,D-1$ and an $i$ -bad real number $x$ , let $\textsf{Next}_{i}(x)$ be the maximum value such that all values in the interval $[x,\textsf{Next}_{i}(x)-\gamma]$ are $i$ -bad ( $\textsf{Next}_{i}(x)$ is undefined if $x$ is $i$ -good). Note, as $\gamma$ is sufficiently small, that $\textsf{Next}_{i}(x)$ is always $i$ -good when it is defined.

For $a_{1},\dots,a_{i}\in\mathbb{R}$ , with $i\leq D$ , let

$\displaystyle V[a_{1},\dots,a_{i}]$	$\displaystyle=[0,a_{1}]\times\mathbb{R}^{D-1}$
	$\displaystyle\ \quad\cup[a_{1},\textsf{Next}_{1}(a_{1}+\ell)]\times[0,a_{2}]% \times\mathbb{R}^{D-2}$
	$\displaystyle\ \quad\cup[a_{1},\textsf{Next}_{1}(a_{1}+\ell)]\times[a_{2},% \textsf{Next}_{2}(a_{2}+\ell)]\times[0,a_{3}]\times\mathbb{R}^{D-3}$
	$\displaystyle\ \quad\qquad\qquad\qquad\qquad\vdots\qquad\qquad\vdots\qquad\qquad\vdots$
	$\displaystyle\ \quad\cup[a_{1},\textsf{Next}_{1}(a_{1}+\ell)]\times\cdots% \times[a_{i-1},\textsf{Next}_{i-1}(a_{i-1}+\ell)]\times[0,a_{i}]\times\mathbb{% R}^{D-i}.$	(27)

Call such a set $V[a_{1},a_{2},\dots,a_{i}]$ legal if (i) $a_{j}$ is $j$ -good for all $j\in\{1,\dots,i\}$ and (ii) $a_{j}+\ell$ is $j$ -bad for $j\in\{1,\dots,i-1\}$ . We grow a large correctable set of the above form using the following four properties:

1.

(If possible, expand in $i$ th dimension): If $i\leq D$ , the set $V[a_{1},\dots,a_{i}]$ is correctable and legal, and $V[a_{1},\dots,a_{i-1},a_{i}+\ell]$ is legal, then $V[a_{1},\dots,a_{i-1},a_{i}+\ell]$ is correctable.

We apply the expansion lemma. Note that the boundary is a subset of

$\displaystyle F$	$\displaystyle\stackrel{{\scriptstyle\rm def}}{{=}}B$
	$\displaystyle\cup\left([a_{1}-\ell,a_{1}+\ell]\times\mathbb{R}^{D-1}\right)$
	$\displaystyle\cup\left([\textsf{Next}_{1}(a_{1}+\ell)-\ell,\textsf{Next}_{1}(a% _{1}+\ell)+\ell]\times\mathbb{R}^{D-1}\right)$
	$\displaystyle\qquad\qquad\vdots\qquad\qquad\vdots\qquad\qquad\vdots$
	$\displaystyle\cup\left(\mathbb{R}^{i-2}\times[a_{i-1}-\ell,a_{i-1}+\ell]\times% \mathbb{R}^{D-i+1}\right)$
	$\displaystyle\cup\left(\mathbb{R}^{i-2}\times[\textsf{Next}_{i-1}(a_{i-1}+\ell% )-\ell,\textsf{Next}_{i-1}(a_{i-1}+\ell)+\ell]\times\mathbb{R}^{D-i+1}\right)$
	$\displaystyle\cup\left(\mathbb{R}^{i-1}\times[a_{i}-\ell,a_{i}+\ell]\times% \mathbb{R}^{D-i}\right).$	(28)

Since $V[a_{1},\dots,a_{i}]$ is legal, the values $a_{j}$ and $\textsf{Next}(a_{j}+\ell)$ are $j$ -good for $j\in\{1,\dots,i\}$ and $j\in\{1,\dots,i-1\}$ , respectively. By definition of $i$ -good, each set in the above union, other than $B$ , has at most $\ell n^{(D-1)/D}$ qubits. Thus, $F$ has at most $d/2+(2D-1)\ell n^{1/D}<d$ qubits, so $F$ is correctable. It follows that $V[a_{1},\dots,a_{i}]\cup F$ is correctable, and by Subset Closure, $V[a_{1},\dots,a_{i-1},a_{i}+\ell]$ is correctable.

2.

(Stuck in $i$ -th dimension, start in $(i+1)$ -th-dimension): If $V[a_{1},a_{2},\dots,a_{i}]$ is correctable and legal, and $V[a_{1},\dots,a_{i-1},a_{i}+\ell]$ is not legal, then $V[a_{1},\dots,a_{i},0]$ is correctable and legal.

The set $V[a_{1},\dots,a_{i},0]$ is correctable by definition as $V[a_{1},\dots,a_{i},0]=V[a_{1},\dots,a_{i}]$ . It is legal also by definition, as we assume $a_{i}$ is $i$ -good but $a_{i}+\ell$ is $i$ -bad, and 0 is trivially $(i+1)$ -good.

3.

(Expand in $D$ -th dimension): If $V[a_{1},a_{2},\dots,a_{D}]$ is correctable and legal, then $V[a_{1},\dots,a_{D-1},a_{D}+\ell]$ is correctable and legal.

It is legal as every real number is $D$ -good by definition. For correctable, we again use the expansion lemma. Following part 1, the boundary is a subset of

$\displaystyle F$	$\displaystyle\stackrel{{\scriptstyle\rm def}}{{=}}B$
	$\displaystyle\cup\left([a_{1}-\ell,a_{1}+\ell]\times\mathbb{R}^{D-1}\right)$
	$\displaystyle\cup\left([\textsf{Next}_{1}(a_{1}+\ell)-\ell,\textsf{Next}_{1}(a% _{1}+\ell)+\ell]\times\mathbb{R}^{D-1}\right)$
	$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\vdots\qquad\qquad% \vdots\qquad\qquad\vdots$
	$\displaystyle\cup\left(\mathbb{R}^{D-2}\times[a_{D-1}-\ell,a_{D-1}+\ell]\times% \mathbb{R}\right)$
	$\displaystyle\cup\left(\mathbb{R}^{D-2}\times[\textsf{Next}_{D-1}(a_{D-1}+\ell% )-\ell,\textsf{Next}_{D-1}(a_{D-1}+\ell)+\ell]\times\mathbb{R}\right)$
	$\displaystyle\cup[a_{1},\textsf{Next}_{1}(a_{1}+\ell)]\times\cdots\times[a_{D-% 1},\textsf{Next}_{D-1}(a_{D-1}+\ell)]\times[a_{D}-\ell,a_{D}+\ell].$	(29)

As in part 1, we have $|B|\leq d/2$ , and all but the last set in the union above has size at most $\ell n^{(D-1)/D}$ . We now bound the size of the last set in $F$ . Since $[a_{j}+\ell,\textsf{Next}_{j}(a_{j}+\ell)-\gamma]$ is $j$ -bad for all $j$ , a counting argument yields

\displaystyle\textsf{Next}_{j}(a_{j}+\ell)-(a_{j}+\ell)\leq 2n^{1/D}+2\ell.

(30)

To see this, pack strips of width $2\ell$ in the $j$ th dimension into $\mathbb{R}^{j-1}\times[a_{j}+\ell,\textsf{Next}_{j}(a_{j}+\ell)]\times\mathbb{% R}^{D-j}$ . Each strip has at least $\ell n^{1/D}$ qubits by definition of being $j$ -bad. There are at most $n$ qubits, so there are at most $n/(\ell n^{(D-1)/D})$ packed strips, so the total width satisfies

\displaystyle\textsf{Next}_{j}(a_{j}+\ell)-(a_{j}+\ell)\leq\frac{2\ell n}{\ell n% ^{(D-1)/D}}+2\ell=2n^{1/D}+2\ell.

(31)

We conclude $\textsf{Next}_{j}(a_{j}+\ell)-a_{j}\leq 2n^{1/D}+3\ell$ . Hence, the last box has at most

\displaystyle(2n^{1/D}+3\ell+1)^{D-1}(2\ell+1)<\frac{6^{D}}{\operatorname*{vol% }(B_{D})}\ell n^{(D-1)/D}

(32)

qubits inside by Lemma 14. The total boundary thus has at most

\displaystyle\frac{d}{2}+(2D-2)\ell n^{(D-1)/D}+\frac{6^{D}}{\operatorname*{% vol}(B_{D})}\ell n^{(D-1)/D}<d

(33)

qubits. It follows that $F$ is correctable, so $V[a_{1},\dots,a_{D}]\cup F$ is correctable, and by Subset Closure, $V[a_{1},\dots,a_{D-1},a_{D}+\ell]$ is correctable.

4.

(Finish $(i+1)$ -th-dimension, get unstuck in $i$ -th dimension): If $V[a_{1},\dots,a_{i+1}]$ is correctable and legal, and $A-\ell\leq a_{i+1}<A$ , then $V[a_{1},\dots,a_{i-1},\textsf{Next}_{i}(a_{i}+\ell)]$ is correctable.

The set is correctable because $V[a_{1},\dots,a_{i-1},\textsf{Next}_{i}(a_{i}+\ell)]$ equals $V[a_{1},\dots,a_{i},\infty]$ , which equals $V[a_{1},\dots,a_{i+1}]$ . It is legal because $\textsf{Next}_{i}(a_{i})$ is not $j$ -bad by definition of $\textsf{Next}_{i}$ .

We can repeatedly apply these properties to get that the set of all qubits is correctable by induction. Here are the details. Let $\vec{t}_{1},\vec{t}_{2},\dots,$ be the enumeration of the $A_{\text{tot}}=(A+1)+(A+1)^{2}+\cdots+(A+1)^{D}$ tuples in $\{0,1,2,\dots,A\}^{\leq D}$ , in lexicographical order. Define the lexicographical index of a region $V[a_{1},\dots,a_{i}]$ as the largest $\alpha$ such that $t_{\alpha}$ is lexicographically less than or equal to $(a_{1},\dots,a_{i})\in\mathbb{R}^{\leq D}$ . We prove by induction that, for all $r\leq A_{\text{tot}}$ , there exists a correctable and legal set with lexicographical index at least $r$ . For the base case, $V[0]=\emptyset$ is clearly correctable and legal. For the induction step, suppose we have a correctable and legal set $V[a_{1},\dots,a_{i}]$ with lexicographical index $r$ . The above items shows that we can find a region with strictly larger lexicographical index: If $a_{i}\geq A$ , either $i=1$ , in which case we are done, or $i\geq 2$ and we apply item 4 – the lexicographical index increases because $\textsf{Next}_{i}(a_{i}+\ell)-a_{i}\geq\ell\geq 1$ . Otherwise, if $i=D$ , we apply item 3. Otherwise, if $V[a_{1},\dots,a_{i}+\ell]$ is legal, we apply item 1, and if not, we apply item 2. This completes the induction.

Since the entire set of qubits $Q$ is correctable, an application of the AB Lemma (12) with $A=Q$ and $B=\emptyset$ implies that $k=0$ . This contradicts our assumption that the code is nontrivial. $\hfill\blacktriangleleft$

[bib.bib1] [1] Nouédyn Baspin, Venkatesan Guruswami, Anirudh Krishna, and Ray Li. Improved rate-distance trade-offs for quantum codes with restricted connectivity. Quantum Science and Technology, 10(1):015021, 2024.

[bib.bib2] [2] Nouédyn Baspin and Anirudh Krishna. Connectivity constrains quantum codes. Quantum, 6:711, 2022.

[bib.bib3] [3] Nouédyn Baspin and Anirudh Krishna. Quantifying nonlocality: How outperforming local quantum codes is expensive. Physical Review Letters, 129(5):050505, 2022.

[bib.bib4] [4] Nouédyn Baspin and Dominic Williamson. Wire codes. arXiv preprint arXiv:2410.10194, 2024.

[bib.bib5] [5] Sergey Bravyi. Subsystem codes with spatially local generators. Physical Review A, 83(1), January 2011. doi:10.1103/physreva.83.012320.

[bib.bib6] [6] Sergey Bravyi, David Poulin, and Barbara Terhal. Tradeoffs for reliable quantum information storage in 2D systems. Physical Review Letters, 104(5):050503, 2010. doi:10.1103/PhysRevLett.104.050503.

[bib.bib7] [7] Sergey Bravyi and Barbara Terhal. A no-go theorem for a two-dimensional self-correcting quantum memory based on stabilizer codes. New Journal of Physics, 11(4):043029, 2009. doi:10.1088/1367-2630/11/4/043029.

[bib.bib8] [8] Samuel Dai and Ray Li. Locality vs quantum codes. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, pages 677–688, 2025.

[bib.bib9] [9] Samuel Dai, Ray Li, and Eugene Tang. Optimal locality and parameter tradeoffs for subsystem codes. arXiv preprint arXiv:2503.22651, 2025.

[bib.bib10] [10] Jeongwan Haah and John Preskill. Logical-operator tradeoff for local quantum codes. Physical Review A, 86(3), September 2012. doi:10.1103/physreva.86.032308.

[bib.bib11] [11] Yifan Hong, Matteo Marinelli, Adam M Kaufman, and Andrew Lucas. Long-range-enhanced surface codes. Physical Review A, 110(2):022607, 2024.

[bib.bib12] [12] Anthony Leverrier and Gilles Zémor. Quantum tanner codes. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 872–883. IEEE, 2022.

[bib.bib13] [13] Xingjian Li, Ting-Chun Lin, and Min-Hsiu Hsieh. Transform arbitrary good quantum ldpc codes into good geometrically local codes in any dimension. arXiv preprint arXiv:2408.01769, 2024.

[bib.bib14] [14] Pavel Panteleev and Gleb Kalachev. Asymptotically good quantum and locally testable classical ldpc codes. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 375–388, 2022.

[bib.bib15] [15] Fernando Pastawski and Beni Yoshida. Fault-tolerant logical gates in quantum error-correcting codes. Physical Review A, 91(1), January 2015. doi:10.1103/physreva.91.012305.

Optimal Locality and Parameter Tradeoffs for Subsystem Codes

Abstract

Keywords and phrases:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Acknowledgements:

DOI:

Event:

Editor:

Series and Publisher:

1 Introduction

Question 1.

1.1 Main Result

Theorem 2 (Main Result for Subsystem Codes).

1.2 Generalizing [8] to 𝑫-dimensions

Theorem 3 (Generalization of [8] to D-dimensions).

1.3 Organization of the Paper

Theorem 4 (Main Result – Part 1).

Theorem 5 (Main Result – Part 2).

Theorem 6 (Generalization of [8] when d≤k⁢n).

2 Preliminaries

Notation and Definitions

2.1 Quantum codes

Stabilizer Codes

Subsystem Codes

Commuting Projector Codes

Quantum codes in 𝑫 dimensions

Definition 7 (Interactions).

Definition 8 (Interaction counter).

Correctable sets

Definition 9 (Correctable set).

Definition 10 (Dressed-Cleanable).

Lemma 11 ([7, 10, 15]).

Lemma 12 (A⁢B Lemma – Implicit in [5], Section VIII).

Lemma 13 (A⁢B⁢C Lemma [6]).

2.2 Geometric Lemmas

Lemma 14 (Point Density).

Lemma 15 (Tiling Lemma).

3 Proof of Theorem 4

Theorem (Theorem 4, restated).

4 Proof of Theorem 5

Theorem (Theorem 5, restated).

Lemma 16 (Holographic Principle).

Lemma 17 (Subdivision).

Lemma 18.

Proof of Theorem 5.

5 Proof of Theorem 6

Theorem (Theorem 6, restated).

Proof.

Case 1: 𝒌≥𝒅.

Case 2: 𝒅≥𝒌.

6 Construction for Upper Bounds

6.1 Subsystem codes

Theorem 19 (Wire code [4]).

Lemma 20 (Concatenated Subsystem Codes).

Theorem 21 (Optimality of Interaction Length for Subsystem Codes).

6.2 Commuting Projector Codes

Theorem 22 (Subdivided code [13]).

Theorem 23 (Optimality of Interaction Length for Stabilizer Codes).

References

Appendix A Proof of Theorem 4

A.1 Detailed Sketch of Theorem 4 in 𝟐-dimensions

A.1.1 Expansion in the 𝒙𝟏-direction

A.1.2 Stuck in the 𝒙𝟏-direction, expand along the 𝒙𝟐-direction

A.2 Proof of Theorem 4 in 𝑫-dimensions

Proof.

1.2 Generalizing [8] to $𝑫$ -dimensions

Theorem 3 (Generalization of [8] to $D$ -dimensions).

Theorem 6 (Generalization of [8] when $d\leq\sqrt{kn}$ ).

Quantum codes in $𝑫$ dimensions

Lemma 12 ( $A B$ Lemma – Implicit in [5], Section VIII).

Lemma 13 ( $A B C$ Lemma [6]).

Case 1: $k\geq d$ .

Case 2: $d\geq k$ .

A.1 Detailed Sketch of Theorem 4 in $2$ -dimensions

A.1.1 Expansion in the $x_{1}$ -direction

A.1.2 Stuck in the $x_{1}$ -direction, expand along the $x_{2}$ -direction

A.2 Proof of Theorem 4 in $𝑫$ -dimensions