A fault-tolerant quantum circuit will require error correction at regular intervals to avoid the build up of errors [6,8,62,64,78]. The error correcting code used is assessed using various figures-of-merit. Of these, the two most fundamental are the code dimension k and the distance d. The code dimension k is the number of qubits that can be encoded in the code. The distance d measures the number of single-qubit errors required to irreparably corrupt encoded information. The choice of code also affects how encoded information can be processed in a quantum circuit. We want to design a code in a way that protects encoded information from unavoidable interactions with the environment which might corrupt the code; yet at the same time, we want the code to be amenable to interactions that facilitate computation. Understanding the optimal tradeoff between these three figures-of-merit is a fundamental question in quantum error correction [10,36,44,63,77]. In this paper, we study these tradeoffs in the context of quantum lowdensity parity-check (LDPC) codes.
A quantum LDPC code is characterized by how syndrome information is gathered. Unlike the classical setting, we cannot directly read quantum codewords. The state of a register of n qubits could be in some delicate superposition which measurements can upset. The only information we can use for diagnosis is the syndrome, itself just a binary string. Each bit of the syndrome is obtained by measuring a set of qubits in a manner prescribed by the error correcting code. These specific measurements are designed to preserve the encoded information and are called stabilizer measurements. Each bit of the syndrome is obtained by measuring the corresponding stabilizer generator. Together, the stabilizer generators generate a stabilizer group, a set of measurements that does not destroy encoded quantum information. In a quantum LDPC code, we need only measure a constant number of qubits for each bit of the syndrome. Furthermore, each qubit only affects the value of at most a constant number of syndrome bits. This property is expected to simplify the process of obtaining the syndrome which, in addition to the code dimension and distance, is also a criterion for picking a quantum error correcting code. Indeed, quantum LDPC codes may have benefits for constructing scalable fault-tolerant quantum circuits [39,46,66]. In sharp contrast to the classical setting, it is unknown whether good quantum LDPC codes exist i.e. whether quantum LDPC code families exist where k and d scale linearly with n.
For ease of implementation, we may wish to construct quantum LDPC codes that are spatially local in 2 dimensions. A local quantum code refers to a code family embedded in R D in which the qubits involved in a particular syndrome bit are contained in a ball of diameter w, where w is some constant, independent of the size of the code. Unfortunately, locality is a fundamental problem in the design of quantum error correcting codes. Bravyi and Terhal [21] proved that any local code in R D obeys d = O(n 1-1/D ). This bounds the distance of a D-dimensional local code away from n. Subsequently, Bravyi, Poulin and Terhal [22] proved that any local code in R D obeys kd 2/(D-1) = O(n). In particular, 2dimensional codes are very restricted: their distance d can scale at best as Θ( √ n), implying that the code dimension is constant. The famous surface code (and the closely related color code and variants) saturates this bound up to constant factors [15,16,19,61].
Constructive approaches that eschew locality to build quantum LDPC codes still face difficulties. There exist codes that achieve a code dimension scaling linearly in the block size but with limited distance [18,41,49,65,68,70,86,88]. It proved to be very challenging to achieve a distance scaling better much better than Θ( √ n) [41]. In the latter half of 2020, a series of works heralded one breakthrough after another [23,37,51,56,57]. The current record is held by a construction due to Panteleev and Kalachev, who demonstrated the existence of codes with code dimension k = Θ(log(n)) and distance scaling as Θ(n/ log(n)) [75].
In contrast to these constructive approaches, we present Bravyi-Poulin-Terhal-like bounds applicable to general LDPC codes that are not constrained to be local. Such a top-down approach to bound the properties of quantum LDPC codes might serve to answer why finding constructive approaches has been difficult.
In addition to these concerns, we need ways to process encoded information fault tolerantly.
This means that if a subroutine within a circuit fails, it only corrupts the limited set of qubits it acts on. We do not want errors in one location to spread to errors in another, thereby overwhelming the error correcting code. Transversal gates are one way to implement a fault-tolerant gate [73]. In its simplest form, transversal gates refer to gates acting independently on each physical qubit in the code. Note that this is trivial in the classical setting: to implement the logical NOT on a 3-bit repetition code, we need just flip each bit of the code. However, this is considerably more difficult in the quantum setting as the set of transformations even on just a single qubit corresponds to SU (2), a dense group. Bravyi and Koenig [20] proved that transversal gates on D-dimensional local quantum error correcting codes are limited. Specifically, transversal gates on 2-dimensional local codes can at best implement transformations of a finite group of transformations referred to as the Clifford group. This finite group of transformations is insufficient to implement all gates required to run interesting algorithms and can even be simulated efficiently on a classical computer [1]. Subsequently, Pastawski and Yoshida showed that there is a relation between the distance of D-dimensional local codes and the gates they support [76]. To state their result in a non-technical way, they proved that implementing transformations outside the finite group would come at the cost of the distance of the code. Recent work by Burton and Browne [27] extends this result and has shown that a specific class of finite rate quantum LDPC codes (that are not constrained by locality) has a structure where transversal gates can still only implement Clifford transformations on encoded information. This suggests that locality itself might not be the constraint that limits transversal gates.
As previously mentioned it is known that locality is a strong limitation to the protection of quantum information. The purpose of the present work is to show that connectivity, in a well defined sense, imposes similar restrictions on quantum codes. To illustrate the difference, consider a code on n qubits that is embedded in a a tree lattice. We require that we are limited to local in-teractions: if two qubits are involved in the same measurement, then they necessarily are neighbors in the lattice.
We can then make two seemingly conflicting observations. First, a tree lattice is highly non-local as it cannot be embedded in any D-dimensional space, hence it is not restricted by the Bravyi, Terhal and Poulin bounds. On the other hand, a tree lattice is poorly connected: if we remove the root vertex, then large chunks of the code can no longer communicate. Intuitively this should restrict the properties of the code, and we show that this is indeed the case.
This example is meant to underline the difference between locality and connectivity. Any notion of locality has to refers to a particular space -Euclidean, hyperbolic, etc. -while connectivity is meant to only refer to the inner structure of the code. The main metric of connectivity we will use here is the separator
The separator sep(G) of a graph G is a subset of vertices of minimal size which, if removed, would split G into two small subgraphs that are disconnected from each other [83]. Colloquially, if every subgraph H of G has a small separator, then G is poorly connected: in some sense the graph is shallow. This notion has recently received some interest in the field of geometric group theory under the name of separation profile [14,53,54,67], which we write s G . The function s G bounds the size of the separator not only for the graph G, but also for all of its subgraphs.
For our results it will be crucial we require that the connectivity be low everywhere, which is more appropriately captured by s G than by the size of a single separator. This is especially important when G is, for example, made of several disconnected but dense graphs. In this case, we would have sep(G) = ∅, but this hardly captures the geometry of the entire graph.
Example: Consider the √ n× √ n grid graph. This graph has a separator of size √ n: we just have to remove a single column of vertices from the middle to cleave the graph in two. In fact, any planar graph is poorly connected; the famous Lipton-Tarjan Theorem states that any planar graph with n vertices has a separator of size O( √ n) [69].
Finally, we note that the separator allows us to bound the dimension, and the performance of transversal gates in a code. We detail these results in sections 3.1, 3.2 and 3.3. These results build on the idea of partitioning the qubits into subsets that do not contain a logical operator.
As shown in [20][21][22], the size and number of such subsets can provide a lot of information about the tradeoff between k and d, as well as the ability of transversal gates to induce logical transformations. We use the separation profile to construct such partitions by recursively separating the code into smaller parts.
We have not yet discussed to what degree these bounds are practical. Can they easily be applied to a given class of codes?foot_1 Fortunately, numerous separator theorems are known [33,43,58,60,67,69]. These theorems, for a given class of graphs, guarantee upper bounds on their separators. With these tools, we can address an open question of [24], where it is asked whether bounds on the parameters of local codes in non-Euclidean lattices can be obtained. In section 4, we answer this question in the affirmative by proving bounds on local codes in D-dimensional hyperbolic space H D . These bounds follow naturally from a recent result by Kisfaludi-Bak [60] who showed that graphs locally embedded in D-dimensional hyperbolic space H D have bounded separators.
In comparison with the known bounds for local codes in D-dimensional Euclidean space, the bounds we obtain for H D are more restrictive on the distance but offer the same tradeoff between k and d. Indeed we find kd 2/(D-1) = O(n) for a local code in H D , the same as for R D as shown by Bravyi, Poulin & Terhal. If we find codes to saturate the bounds in D-dimensional Euclidean space, we would conclude that H D does not seem advantageous. We note, however, that these bounds do not apply to hyperbolic manifolds, which have been used to prove the existence of constant rate codes with polynomial distance [26,49,50,70].
Similarly, we use a result of Dujmović, Eppstein and Wood [33] to prove bounds on codes locally embedded on a surface of genus g, thus extending a result of Delfosse [29] to arbitrary LDPC codes.
Our main results are presented in Section 3. The first of these results, Theorem 16, states that the distance is bounded by s G . Secondly, Theorem 23 shows that a small separation profile implies a stark tradeoff between k and d. Similarly, a small separation profile implies a limited ability to perform transversal gates as shown in Theorem 27. We note that Theorems 23 and 27 are not limited to LDPC codes.
The rest of the paper proves these results and explores their consequences. In Section 2, we establish background required to state our result. We define quantum stabilizer codes in Section 2.1, some important properties and their representations in terms of graphs. In Section 2.2, we define the notions of separability and the closely related notion of treewidth. These are metrics of connectivity in terms of which our main theorems are stated. In Section 3 we formally state and prove our main results. First Section 3.1 focuses on Theorem 16 on the distance. Then Section 3.2 focuses on Theorem 23 on the code dimension. Lastly, Section 3.3 focuses on Theorem 27 on transversal gates.
2 Background and Notation
In our paper, we focus on stabilizer codes on n qubits. A qubit is associated with the complex Euclidean space C 2 and n qubits with (C The Clifford hierarchy is a generalization of the Clifford group and plays an important role in the theory of quantum error correction [47]. Theth level of the Clifford hierarchy, denoted K ( ) , is defined recursively. The 1st level of the Clifford hierarchy, denoted K (1) , is the Pauli group. For ≥ 2, the hierarchy is defined as
It can be seen from this definition that K (2) is the Clifford group.
Let W be a unitary gate and let W denote the encoded version of W . In other words, if E S : C ⊗k → C ⊗n is the encoding operation for the quantum error correcting code defined by the stabilizer group S, then W E S (|φ ) = E S (W |φ ).
We say that W can be implemented in a transversal manner if W = W 1 ⊗ ... ⊗ W n for some singlequbit gates {W i } i .
We recall some definitions from [21]. Let V =
[n] index the qubits and Q(V ), the n-qubit space associated with C 2 ⊗n . For any subset U ⊆ V , let Q(U ) ⊆ Q(V ) denote the |U |-qubit space with the corresponding indices. For ease of notation, we shall use U to also refer to Q(U ) where no confusion may arise. Let U = [n] \ U be the complement of U . For any Pauli operator L we write its support supp(L) ⊂ V the set of qubits on which L acts nontrivially. Central to everything that follows is the notion of correctability of sets of qubits. As a consequence, correctable regions turn out to have a rather interesting property. If the support of a logical operator L intersects a correctable region U , then it can be cleaned out of U . This is illustrated in fig. 1. Intuitively we expect that subsets of qubits that are sufficiently far away from one another can be corrected independently. Definition 3 (Boundary). Let C(Ω) be a stabilizer code and U ⊂ V . We define the outer and inner boundaries respectively as follows:
1. Outer boundary: ∂ + U is the set of all qubits corresponding to v ∈ U such that there exists at least one stabilizer generator S and u ∈ U satisfying v, u ∈ supp(S).
Proof. Let U i be one cluster of the decoupled set and L U i the restriction of L on U i . L U i has to commute with any generators whose overlap with L is only contained within U i . Due to the decoupling condition, this is the case for all generators having support on U i . Since L U i commutes with all generators having support on U i , we conclude L U i ∈ L. However, every U i is correctable, therefore L U i = I U i , i.e. they act as identity on the qubits U i .
any logical operator L whose support intersects with U can be cleaned to T ∪ W , and we let L denote the cleaned operator. This implies that L = L T ⊗ L W . Note that no check acts on both T and W as ∂ + T ⊆ U which means that L T , by itself, is a bonafide logical operator. Since T is correctable, we have L T = I. Therefore T ∪ U is correctable.
In addition to the algebraic view presented above, quantum codes can also be represented graphically. We shall use the following object, called a connectivity graph representation. This representation depends on the generators of a code, not on the code itself.
Definition 7 (Connectivity graph). Let C(Ω) be a stabilizer code. Then the connectivity graph G(Ω) = (V, E) associated with Ω is defined so that:
1. V = [n], i.e. each vertex is associated with a qubit, and 2. (u, v) ∈ E if and only if there exists a generator S ∈ Ω such that u, v ∈ supp(S).
For the sake of readability, we will refrain from referring to Ω explicitly. When we refer to a connectivity graph G of a code C, it is to be understood that there exist a generating set Ω such that C = C(Ω) and G = G(Ω).
Remarks: We first remark that this representation is not a function of the code, as different generating sets can yield the same code but different graphs. Further the mapping from Ω to G is not injective: different codes might yield the same connectivity graph, if the right generating sets are chosen. This stands in contrast with the Tanner graph, another common graphical representation of LDPC codes. However, despite this lack of uniqueness, the connectivity graph suffices to obtain the desired bounds on the distance and code dimension. Note that this representation dispenses with Pauli labels between the stabilizers and qubits and no longer carries information concerning the commutation relations. Taking this information into account could be important in restricting the types of graphs that emerge; we do not do so here. This representation was also used for different purposes, see for example [66] or [46].
The following observations will be useful. Consider two disjoint subsets U 1 , U 2 ⊂ V . If there is no edge between U 1 and U 2 then they are decoupled. Equivalently, the distance on the connectivity graph between these two sets is at least two. In other words, ∂ + U 1 is the neighborhood of U 1 in the connectivity graph.
If the quantum code family is LDPC, then the connectivity graph has bounded degree. Suppose C = {C n } is a code family with qubit degree upper bounded by δ V and stabilizer degree bounded by δ C . Then each vertex in the connectivity graph is connected to at most δ V (δ C -1) other qubits. We expect the degree to be less than this because the stabilizer generators can overlap, and likely will, to obey commutation relations.
As an example, consider a portion of the surface code as shown in fig. 3 below. The surface code is a code defined on the 2-dimensional square grid. The qubits are identified with the edges of the lattice, the X stabilizers with the vertices and the Z stabilizers with the faces. An X (Z) stabilizer acts on a qubit if the vertex (face) corresponding to the stabilizer is adjacent to the edge corresponding to the qubit. The corresponding connectivity graph has vertices on all edges of the grid in addition to diagonal connections.
In this section, we start by formally introducing the notion of a separator and other related metrics. We then introduce a closely related metric, the treewidth. This additional metric is introduced for a technical reason, as it will be the ba-sis for the proof of Theorem 16. Fortunately, the separation profile and the treewidth are closely related, as shown by Lemma 12: this will allow us to restate our bound on the distance from Lemma 15 in terms of the separators.
The separator might not be uniquely defined, as multiple sets could have the same size and still split the graph in two disjoint subgraphs. However, this multiplicity does not affect our results, as it will suffice to prove the existence of one such small set. It will be useful to note that for any α, we have
as any set of such size naturally induces two sets, A = ∅, and
Consider the graph made of the disjoint union
where G 1 and G 2 are densely connected. The separator of G alone would only provide superficial information about its connectivity. To make a more consistent statement about the connectivity of a graph, we introduce a notion of separability that also relies on subgraphs.
To a set of graphs G = {G n } n , we associate a set of α-separation profiles {s α n } n where s α n is the separation profile of G n .
-see Lemma 32 -our results do not rely on a specific value of α, hence we will often write the separation profile s G or s n to mean s α G or s α n . As an example of separation profile, consider a grid graph as shown in fig. 3. This graph is poorly connected; we can partition the vertices into two sets by removing a thin strip from the middle. In other words, an L × L grid with For general graphs, there exist polynomial-time algorithms to approximate their separator up to constant factors [74].
For many classes of graphs [33,43,58,60,67,69,72] the separation profile of a graph is upper bounded by a polynomial up to constant factors, which is particularly amenable to recursive separation -see Lemma 33 -which will be essential to the formulation of our results. However the separation profile does not always assume a polynomial form, so to capture these cases, it will be helpful to consider the quantity c(r) such that s G (r) = r c(r) . This motivates the following definition. itself is comprised of n 1-α such disconnected expander graphs as shown. Each subgraph H i has size n α , and so G has n vertices in total. Suppose it was known that d = O(n α ). If we consider small enough subgraphs i.e. of size lesser than n α , then there exist subgraphs with large separators. However, if we let r = n α , the largest separator corresponds to any subgraph H i and therefore c max = 1.
For the sake of readability, we will simply write k ≡ k(n) and d ≡ d(n). By the definition above, there exists a subgraph H ⊆ G n such that d ≤ |H| ≤ n and |sep(H)| = |H| cmax . We also note that for all d ≤ r ≤ n, we have that s n (r) ≤ r cmax (n) . Further one can note that since
We now define the tree decomposition and then the treewidth. The tree decomposition of a graph G is a tree whose nodes are clusters of vertices of G. The width of the tree is the minimum size of its nodes and is yet another way to measure the connectivity of a graph.
where {i : i ∈ I} is a family of subsets Q(i) ⊆ V and T = (I, E) is a tree. The sets I and E refer to the nodes and edges of the tree T respectively. Furthermore, the pair Q, T must obey the following properties:
for every edge {v, w} ∈ E there exists i ∈ I with {v, w} ⊆ Q(i),
3. for every i, j, k ∈ I the following holds: if j lies on the path from i to k in T , then
The width of the tree decomposition ({Q(i
The treewidth tw(G) of G is the minimum width of a tree decomposition of G.
To avoid confusion between the graphs G and T , we shall henceforth refer to the vertices v ∈ V of G and the nodes i ∈ I of T . The tree decomposition of a graph is not unique; for instance, a trivial decomposition of a graph G is to make one giant node N containing all the vertices of G. The treewidth, however, is the minimum width across all decompositions and is therefore well defined. The notation Q(i) is meant to be suggestive as it will soon refer to the qubits in that node.
Example: We consider some examples to illustrate this idea. The first example is the tree decomposition of a tree as shown in fig. 5. In it is a binary tree of depth 2 and the corresponding tree decomposition. The vertices of the graph are gray and the nodes of the tree are green. It is simple to check Property 1. Notice that every node of the tree decomposition contains a single edge from the tree trivially satisfying Property 2. Finally, Property 3 is simple to verify: only two adjacent nodes ever share qubits. Since the size of each node is 2, the treewidth is 1.
As a second example, consider the surface code again as shown in fig. 6 on the left along with its tree decomposition on the right. The graph on the left indicates via green boxes how vertices are partitioned to form the nodes of the tree. Recall the structure of the connectivity graph of the surface code as shown in fig. 3. We choose the nodes of the tree by selecting vertices of the connectivity graph diagonally as shown. Again, it is straightforward to verify that this tree decomposition satisfies the definition. First, the diagonals contain every vertex and thus satisfy Property 1. It is also straightforward to verify that every edge is contained in at least one node, satisfying Property 2. Finally, since two successive nodes overlap on one diagonal array of vertices, the decomposition satisfies Property 3. The treewidth of this graph is obtained from the largest node of the tree which corresponds to the node cd. The treewidth is therefore 11.
In practice, there is a lot of interest in efficient algorithms to compute the treewidth of arbitrary graphs [31]. It can be noted that since the treewidth and the size of the separator of a graph are within a constant of each other -see Lemma 12 -the algorithm of [74] can be used to obtain polynomial time approximation of the treewidth.
As promised earlier, the separation profile and the treewidth are closely related.
For any graph G = (V, E) on n vertices with separation profile s G , then s G (n) = Θ(tw(G)).
Proof. First, it was noted in [17] that for a graph G on n vertices, s
Another commonly used notion of connectivity is that of expansion, which has already found applications in analyzing the structure of quantum codes [38]. Further expander graphs are an essential tool in classical error correction [80,87]. It is then natural to ask how the treewidth, the separability, and our results in general, relate to the expansion of a graph.
The vertex expansion of a graph is generally defined through its Cheeger constant. for some c, c > 0 if either of these two conditions is fulfilled
Proof. Case 1 is Proposition 2 in [48]. Case 2, is readily obtained from Case 1 by the fact that
3 Main results
We now state and prove the first main result: the distance of a code family is bounded by the treewidth of the connectivity graph. Proof. Consider a tree decomposition T of G such that the width of the tree T is the treewidth of G. For the sake of contradiction, assume d > δ(tw(G) + 1).
Suppose the tree T is non-trivial and has depth D ≥ 1 (and the root at depth 0). Let p ∈ I be some node at depth D -1. Let the leaves {j 1 , ..., j t } ⊂ I be the children of p.
The purpose of A is to be a correctable anchor whose boundary will be provably small. This will allow us to grow A to a larger, but still correctable, region.
First, it follows from lemma 5 that A is itself correctable. This is because once the boundaries are removed, A is a union of decoupled sets as per definition 4. 2
Next, we turn to ∂ + A. Consider any pair of qubits u, u such that u ∈ A, u ∈ ∂ + A. By construction, there must be some leaf j i such that u ∈ Q(j i ) and since u ∈ ∂ + A, either:
Including the case of Q(ji) and Q(j k ) sharing a qubits q. In that case, Q(ji) \ ∂+Q(j k ) ∪ Q(j k ) \ ∂+Q(ji) can be decomposed as the union of three decoupled sets: something in Q(ji) not connected to anything in Q(j k ), q, and something in Q(j k ) not connected to anything in Q(ji). The Cleaning lemma still applies.
Q(p 3 ) 2. u ∈ Q(j i ) but u ∈ ∂ + Q(j j ) for some j.
We conclude that ∂ + A ⊂ ∪ i ∂ + Q(j i ).
be the extended parent. The purpose of P ext will be to bound the size of ∂ + Q(j i ) and extend our anchor. By the definition of the treewidth, |Q(p)| ≤ tw(n) + 1. Furthermore, since the degree of the qubits in the connectivity graph is at most δ, it follows that
by assumption, both Q(p) and ∂ + Q(p) are correctable. It follows from Lemma 6 that P ext is correctable.
For every leaf j i and every u ∈ ∂ -Q(j i ), u shares an edge with the exterior of Q(j i ). Therefore there exists another node j such that u ∈ Q(j) by Property 2 of Definition 11. By Property 3 of Definition 11, it follows that u ∈ Q(p). We conclude that
We now have the necessary ingredients to extend the anchor. Since A and P ext are correctable with
. This too follows from Lemma 6. This shows that the qubits in p together with its children together are correctable. We can combine these nodes to form one larger leaf. Notice that after combining the p and its children into one node, the resulting tree is still a valid tree decomposition of the connectivity graph G. Save for the new amalgamated node, the size of the rest of the nodes of the tree is still upper bounded by tw(G) + 1.
The proof now proceeds by repeating this process until the entire tree is contracted to one node. First, we can contract the children of all nodes at depth D -1 to reduce the depth of the entire tree to D -1. It follows that this tree is also a valid tree decomposition, with all the leaves corresponding to correctable sets as proved above. This process can be iterated until the entire tree becomes one giant node which itself must be correctable. If the tree decomposition has several disjoint components, each of these components is a tree with bounded treewidth. Each can be proved to be correctable, and then since disjoint, their union is also correctable. This implies the whole code is correctable, a contradiction if the code is to encode at least one logical qubit.
From
3 To verify that the inclusion holds, it is sufficient to verify that ∪iQ(ji) ⊂ A ∪ Pext. Since A = ∪iQ(ji) \ ∪i∂+Q(ji) it suffices to show that ∪i∂+Q(ji) ⊂ Pext, which is the conclusion of the previous paragraph
The first bound is from Lemma 15, the second is from Lemma 12.
There are many classes of graphs for which the value of c is known [33,43,58,60,67,69], and it can be estimated for arbitrary families in polynomial time [74].
A useful property of separation profiles and treewidth is that both metrics are somewhat robust to the addition of edges in a graph. This then leads to the following corollary.
Proof. Any separator S of the graph G can be augmented to be a separator of the graph G by removing the vertices involved in the edges E aug . Since there are at most 2|E aug | of these vertices, then s G (r) ≤ s G (r) + 2|E aug | and the result follows.
A straightfoward consequence is that if a code has a poor connectivity, it takes a significant number of edges to overcome the associated poor distance. For example a planar LDPC has distance d = O(n 1/2 ), and to improve it to any d = Ω(n 1/2+ ) with > 0 one needs to add at least Ω(n 1/2+ ) edges.
This theorem then leads to the following conclusion-unless the graph is very connected, the distance cannot grow linearly.
Conversely, any family C = {C n } with linear distance [75] implies the existence of an expander family of graphs {G n }, G n ⊂ G n by Lemma 14.
In this section, we mirror the strategy of [22] to bound the dimension of a code with poor connectivity. Before diving into the formal proofs, we outline the proof.
For a given quantum code C on a set V of qubits, it can be shown that if a subset of qubits A ⊂ V is correctable, then C satisfies k ≤ |V \ A|. Then, one can always pick A such that |A| = d -1 < d, and obtain k ≤ n -d + 1. This is just a weaker version of the Singleton bound [45]. This bound does not rely on the connectivity of the code and tells us very little about the asymptotic behavior of quantum codes.
In order to improve this bound, we will make use of the connectivity graph G = (V, E). Consider a set S ⊂ V , such that S is a separator of G and therefore induces a tripartition
Another perspective is that removing S from the graph G induces two disjoint graphs
Then, by Lemma 5, if A 1 and A 2 are correctable, since there are no edges between A 1 and A 2 , then
which gives us a connectivity-dependent bound: if a graph has small separators, then the bound on k can be expected to be restrictive. This strategy can be extended to the case where A 1 and A 2 are not correctable. It suffices to "take" new separators in G A 1 and G A 2 , until every induced subgraph is correctable -which can be guaranteed when every subgraph is of size d -1. We then have k ≤ sum over the separators |S| We now proceed to make this statement formal. We begin by restating the following result as a lemma and provide an alternate proof without the use of von Neumann entropies. The tradeoff is that our proof only works in the case of stabilizer codes, whereas the original statement applies to all quantum codes. Lemma 19 (Bravyi-Poulin-Terhal [22], Eq. 14).
Consider the tripartition Q = A B C where A and B are correctable. We infer from eq. 3 that
The last inequality follows because removing columns from a matrix can at best reduce its rank. Similarly, we obtain
Adding eq. 4 and eq. Proof. Let W ⊂ V , then we define cost(W) as the size of the smallest set J W ⊂ W such that K ≡ W \ J W is a union of disjoint subsets of size strictly less than d. J W might not be uniquely defined, but as we are only interest in its size, there is no loss of generality.
Now consider a separator S W of the subgraph induced by W . This separator provides us with a partition
It is then easy to verify that cost(W
is a union of disjoint subsets, all of which are of size strictly less than d. This then gives cost(W
Further, by the definition of the separation profile, we have cost(W
This upper bound on cost(W ) is not very tractable and cannot be unraveled in a practical way. To solve this issue, we define T (r) ≡ max W ⊆V,|W |≤r cost(W ), and we have
It is then possible to verify -see Lemma 33 -that one has T (r) ≤ S d (r), where S d (r) is defined as in Definition 20.
We can then take
We can summarize the general idea of our results as follows. Note that to find large A, B, given an easily separable graph, we can recursively separate it to obtain small correctable regions, which will be A. Then G \ A can be recursively separated anew, yielding B. See Figure 8. Proof. From Lemma 21, we can recursively separate the connectivity graph to find A such that Ideally, one could then simply plug in s α G in Definition 20, and obtain a closed form for the formula with Lemma 33 in Appendix B. However, the separation profile may not always be a polynomial. In these instances, we can generalize this result with the following theorem.
Further, if we have c max (n) ≤ c 0 for a constant c 0 ∈ (0, 1), then
Proof. By definition, we have s n (r) ≤ r cmax (n) . Applying Lemma 22 with Lemma 33 gives the desired result.
This theorem tells us that a code with high k, d has to have a very dense subgraph. Indeed, as we have k ∈ Õ(n/d 1-cmax(n) ), then for k ∼ n, and d → ∞, we need c max (n) close to 1. Equivalently, for a code to achieve constant rate and growing distance, it needs to contain a dense subgraph. Furthermore, this subgraph has to have density at least d.
In many cases, the family of connectivity graphs can be verified to satisfy s n (r) ∈ O(r c ), with c < 1, this is notably the case for many classes of local graphs [83], as they exhibit a rather limited structure [85]. In that case the following corollary will be useful.
Proof. The proof follows from applying Lemma 22 with Lemma 33.
As previously mentioned, there are many classes of graphs for which the value of c is known [33,43,58,60,67,69], and it can be estimated for arbitrary families in polynomial time [74].. Although this result allows us to formulate a bound in purely graph-theoretic terms, we cannot rederive the Bravyi-Poulin-Terhal bound. Indeed, they make use of the Expansion Lemma to obtain regions V • of size d 2 , instead of d. This optimization cannot be carried out here as we do not have a guarantee on the boundary of the regions V • we create. In other words, we make no assumptions on the structure of the subgraph that we obtain from the separator. As a consequence, our bound applies to all codes and not just LDPC codes. As we will see when dealing with D-dimensional hyperbolic codes, some spaces induce small separators and large boundaries so we do not expect the Expansion Lemma to always yield a tighter bound. These are highly nonlocal codes and may be able to bypass the restrictions on purely local codes. These spaces might be expected to yield a poor distance and better tradeoffs. Without being able to pin down the structure of the subgraph induced by the separator, we cannot derive tighter bounds on the rate-distance tradeoff.
In this section, we prove that transversal gates on quantum LDPC codes can only implement a limited set of transformations on the encoded information. We begin with by recalling a result from [20] that we will build on.
Let C be a code such that its set of qubits can be partitioned as Q = ∪ i=R+1 i=1 Λ i , where each Λ i is correctable. The transversal gates on this code are limited to the R-th level K (R) of the Clifford hierarchy.
We are then in position to prove the following result.
Let C be a code on n qubits and G = G(C) be an associated connectivity graph. Let S d be the function defined in Definition 20, and let us denote S d composed R times with itself as
Then the tranversal gates on this code are limited to the R-th level of the Clifford hierarchy K (R) for the smallest R satisfying
Proof. We proceed iteratively. The recursive separation of Lemma 21 acting on G yields partitions A 1 and A 1 , where A 1 is correctable, and
and not the entire graph G). We repeat this process R times until A R is correctable.
In doing so we get R+1 correctable regions which is achieved when
Theorem 27. Let C = {C n } be an n, k, d code family and G = {G n } be an associated connectivity graph, and {s n } n the associated separation profiles. Suppose that s n (r) = O(r c ) for c ∈ (0, 1), and d = Θ(n α ) for α ∈ (0, 1).
Then transversal gates on C belong to
Proof. Since s n (r) = O(r c ), we known from Appendix B that S d (n) ≤ σd c-1 n for some constant σ > 0, for sufficiently large n. The condition from Lemma 26 can be satisfied if
Equivalently, taking the logarithm base n, we get
Rearranging terms, we get
.
As we assume that d ≥ σ n α for sufficiently large n, it is sufficient to satisfy
Remarks: In the case of D-dimensional quantum codes, it can be compared to the results of Pastawski and Yoshida [76]. From [72,83,84]
While the bound from Pastawski and Yoshida, can be re-expressed to read
There are instances where our bound may yield slightly better results; we thank Sam Cree for pointing this out. For example, consider D = 3 and α = 0.6 < 1 -1/D = 2/3. Our bound implies that transversal gates must lie in the Clifford group, whereas the Pastawski-Yoshida bound implies that transversal gates are only contained in the third level of the Clifford hierarchy. Of course, it is unclear whether such a code can be constructed.
We cannot reproduce the Pastawski-Yoshida bound for the same reason that we cannot reproduce the Bravyi-Poulin-Terhal bound: in [20], the separation of the D-dimensional lattice is better than the separation into multiple sectors we have based on S d .
Indeed the interest of the results presented here lies within more exotic spaces and constructions where the lattice-based approach of the numerous no-go theorems in R D breaks down.
We also mention a general limitation on obtaining practical codes. Let C be a family of quantum LDPC codes with s n separation profiles. Suppose s n (r) ∝ r c and that we can achieve d = Θ(n c ). This implies that we can at best implement gates in K (R) , where R = 1/c . In particular, if c > 1/2, we are limited to Clifford gates. This implies that there is a tradeoff between the distance and our ability to perform transversal gates even without the restriction of locality.
It is also interesting to note that it is shown in Burton and Brown [27] that all hypergraph product codes are limited to the Clifford hierarchy, regardless of their separation profile. It raises the question of whether these codes offer the best trade-off between connectivity and versatility of transversal gates.
Several constructions of quantum codes are naturally expressed through hyperbolic geometry [25,29,41]. We use our results to study limitations of codes embeddable in H D and on hyperbolic surfaces. We demonstrate that D-dimensional hyperbolic codes have distance upper bounded by O(n (D-2)/(D-1) ), reminiscent of Euclidean codes in (D -1)-dimensions. Interestingly, the tradeoff between the code dimension and distance is the same as that for local codes in R D . Our results follow from recent work by Kisfaludi-Bak [60] who proved that certain classes of hyperbolic graphs have bounded separators.
We begin by comparing our work with previous results to provide some intuition on what follows.
Recall that the Bravyi-Terhal and Bravyi-Poulin-Terhal results are statements on the geometry of R D . A ball of area A in the Euclidean plane can be split into two equally-sized half balls by a line segment of length √ A. As a consequence, one expects a graph nicely embedded in such a ball to have a separator of size O( √ A). Similarly, a ball of area A in 2-dimensional hyperbolic space has a diameter of size O(log(A)) in the limit of large balls. We therefore expect the hyperbolic plane to perform poorly in terms of distance.
Similarly, this geometric consideration can be used to justify why the hyperbolic space might be particularly well suited to our technique. As previously noted after Corollary 24, Theorem 23 does not allow us to rederive the Bravyi-Poulin-Terhal bound; we cannot guarantee that the re-gions we create through the recursive separation have small boundaries. However, we do not expect this to be relevant in hyperbolic space since, due to the isoperimetric inequality, the boundary of a region is proportional to its volume in the limit of large volumes.
To formalize this correspondence between geometry and graphs, we need a precise definition of what it means for a graph to be nicely embedded in such a space. We expect the density of vertices not to diverge, and two vertices linked by an edge should not be too far apart. This leads to definition 28.
Let (M, d) denote a metric space M equipped with a metric d :
A recent result by Kisfaludi-Bak [60] demonstrates that (ρ, w)-local graphs embedded in H D have small separators. We begin by repeating Theorem 2 from [60] as it applies to this class of graphs -see Section E for details. 1) ).
From our previous results, we can then prove the following theorem. We can see from this result that the distance of the D-dimensional hyperbolic codes for D ≥ 3 obeys the same upper bound as (D -1)dimensional Euclidean local codes.
Note that these results do not apply to hyperbolic manifolds of the form H D /Γ as quotienting by Γ can change the size of the separator completely. A straightforward consequence is that a graph on a 2-torus does not necessarily have a O(log(n)) separator. Fortunately, in the case of hyperbolic surfaces, we can still bound the separator as a function of the genus. We turn next to these codes.
The class of 2D topological codes has generated a wealth of literature and is among the most likely candidates for physical implementation in the near future. One could attribute this popularity to their relative ease of implementation and tractable properties. Unfortunately, due to a result by Delfosse, these codes are known to be strongly limited and are constrained by kd 2 = O(log(k) 2 n) [29]. Here we generalize this bound for local codes on an arbitrary surface of genus g, denoted Σ g , and we prove that for fixed g, d = O( √ n), which is saturated by the surface code.
Topological graph theory provides a very natural bridge between graphs embeddable on a surface and their separability [7,32,42,59]. We employ a result due to Dujmović, Eppstein and Wood [33] which states that graphs embedded in Σ g with planarity p have bounded separators. A graph is said to be p-planar if it can be drawn with at most p crossings on each edge. [33] proved that any graph that can be embedded in Σ g that is p-planar has a separator of size O( (g + 1)(p + 1)n).
Observe that all ρ-local graphs that can be embedded on Σ g must be t-planar for some constant t. This is because:
1. Every edge (a, b) can be contained within a ball B of radius w.
2. For any edge (c, d) crossing (a, b), c and d must be at a distance less than w to some point p in the ball, which is at a distance at most w from a and b.
3. Since the number of points at a distance less than 2w is bounded by ρ, there can be at most ρ crossings Together, these observations imply that any ρlocal graph on Σ g is t-planar for some constant t. This implies the following result. We can also use this result to think about implementations of good quantum codes. We might wish to implement codes such that there are as few edge crossings as possible. If we consider implementing codes on a flat surface, then we would need a significant number of edges overlapping. Indeed the number of edges crossing would have to scale as n. This, in turn, would mean that the code is no longer (ρ, w)-local.
In this paper, we have shown that there is an intimate relation between quantum codes and the graphs on which they are defined. Given a code, we can obtain the connectivity graph from which we can infer properties of the associated quantum codes. We have three main results. First, we found that the distance of the quantum LDPC code is bounded by the size of the separator of the associated connectivity graph. Second, we found that the code dimension of a code is bounded as a function of the size of the separator via a recurrence relation. Third, we found that transversal gates can only implement a limited set of transformations depending on the connectivity of the graph. Together, the first two results state that we have good quantum LDPC codes only when the connectivity graph contains an expander.
We explored the properties of codes embedded in D-dimensional hyperbolic space. In particular we found that a local code in D-dimensional hyperbolic space obeys d = O(n (D-2)/(D-1) ) and that for closed 2-manifolds with genus g, local codes obey d = O( √ gn).
These results raise many interesting questions.
1. Non-sparse graphs can often be well approximated by sparser graphs [3,9,13,28]. This naturally leads to the following question: can the bound on the distance from the treewidth be made independent from the maximum degree of the connectivity graph?
2. Low-connectivity codes have poor performance, but do all codes with poor connectivity have low-dimensional local embeddings? [2,4,5,71,79] Note that a strict locality requirement would be hard to satisfy: consider a connectivity graph that has the form of a δ-regular tree, then this graph cannot be embedded locally, as a ball in the tree can grow much quicker than a ball in R D for any constant D.
3. High connectivity is necessary for good quantum codes. Can it be proven to be a sufficient condition given some minimal extra assumptions? Can we distinguish sufficient and insufficient connectivity through another graph metric? For example some families of expander graphs have bounded book thickness [34], but this metric is not bounded for sparse graphs [12].
4. The connectivity graph representation relies on selecting a particular basis for our generators, but there exist more algebraic representation of a graph [81]. Can the results we present here be generalized to be basis independent, for example using spectral partitioning? [82] 5. The recursive separation method we use is rather naive. Is it possible to formulate a better one? [11,40,52] We add that we use the same techniques as reference [22] to also prove bounds on the code dimension of classical codes based on the graph separator in Appendix C. We would like to highlight that in contrast to local codes, there are many basic open questions concerning quantum LDPC codes. For a broad discussion on the subject, we point the interested reader to a review by Breuckmann and Eberhardt [24].
This paper is dedicated to the memory of David Poulin, a role model as a researcher and a mentor. David inspired and encouraged us to explore fundamental questions in quantum error correction while simultaneously studying consequences for real-world implementations. His presence will be missed.
We then only have to show that s
. We note that if, after removing a αseparator, A, B do not satisfy |A|, |B| ≤ 2 3 n, then they both can be separated again t + 1 times such that α t = 1 3 . At this point the vertices have been partitioned into V = i=l i=1 C i j=m j=1 D j , where the C i induce mutually disjoint subgraphs with |C i | ≤ n/3, and the D j are a set of α-separators. Note that there are at most m ≤ u= t+1 u=1 2 u = O(2 t ) such D j . We will want to show that ∪ j D j is a 2 3 -separator. We can now group the C i in order to form a partition A, B such that |A|, |B| ≤ 2n/3. Consider
B Closed-form expression for recurrence relation Lemma 33. Consider the function S d defined by the recurrence relation
If c is upper bounded by a constant, then
In order to prove the base case, we will consider
As the base case is verified, we can then verify the expression holds for r > d .
The induction step is then satisfied if and only if
r +(1-αr) c -1 for any possible value of α r . From here one we thus take g(c) ≡
We have thus showed that
). In the case where c might depend on n, we remind the reader that c ≤ 1 + log n (1 -α), which gives
Secondly, we verify using Mathematica [55] that
Equivalently, for any > 0, there exist n 0 such that for all n ≥ n 0 we have
In [22], the authors also derive a bound on the parameters of classical codes using the following lemma.
Lemma 34 (Bravyi, Poulin, Terhal)
The Bravyi-Poulin-Terhal bound [22] applies to a much larger class of codes than just stabilizer codes. Mirroring their result, we consider a class of codes defined by a set {Π a } a of commuting projectors where each projector Π a acts on some constant number of qubits, and every qubit can affect at most a constant number of projectors. We refer to such a code as a lowdensity commuting projector code. A stabilizer code is the special case where each projector can be expressed as Π a = 1 2 (1 + S a ) for some stabilizer generators {S a } a . However, in general, a commuting-projector code need not have this specific structure. The codespace C is the space C = {|ψ : Π a |ψ = |ψ ∀a}. In this section, we prove that our main results extend to this general class of codes.
At the outset, this may seem difficult as the workhorse behind our results was the Cleaning Lemma. However, there exist analogues of the Union and Expansion Lemmas. For proofs, we refer the reader to Lemma 2 and Corollary 1 respectively of the paper by Bravyi, Poulin and Terhal [22].
Before stating the lemmas, we note that the idea of a boundary, either exterior ∂ + or interior ∂ - carries over quite naturally. Let V be the set of qubits defining a code and U ⊆ V be some subset of qubits. The external boundary ∂ + U of U is the set of qubits v ∈ U such that there exists a projector acting on v and some u ∈ U . The internal boundary ∂ -U is the exterior boundary of U . The boundary ∂U is the union ∂ + U ∪ ∂ -U . We say that two regions U 1 and U 2 are decoupled if there exist no projectors Π a that are supported jointly on the two regions. The definition of the connectivity graph extends naturally: two qubits are connected by an edge if they are both in the support of a projector Π. Therefore, two regions U 1 and U 2 are decoupled if there exist no edges between them in the connectivity graph.
Lemma 36 (Generalized Union Lemma). Let U 1 , U 2 be any correctable regions such that U 1 and U 2 are decoupled. Suppose that ∂ + U 1 is also correctable, then U 1 ∪ U 2 is correctable.
Observe the qualitative difference in this case from that of stabilizer codes: we also require that ∂ + U 1 be correctable for the union to be correctable. This difference will manifest in the bounds on code properties by making the bounds weaker in the case of commuting projector codes.
Let U be a correctable set of qubits. Consider any region B ⊆ V and C ⊆ U , such that ∂U ⊆ BC and BC is correctable. Then U ∪C is correctable.
We are now ready to prove a bound on the distance.
Theorem 38. Let C be a low-density commuting projector code on n qubits. Let G = G(C) be the corresponding connectivity graph with bounded degree δ. If G has treewidth tw(G), then d ≤ 8δ 2 tw(G).
Proof. For the sake of contradiction, assume d > 8δ 2 tw(G).
Consider a set of leaves {j 1 , ..., j t } sharing the same parent node p, and define A i = Q(j i ) \ ∪ k ∂ + Q(j k ), and A = ∪ i A i . Each A i is then what remains of Q(j i ) after we remove the qubits connected to another leaf.
As noted before in the proof of Theorem 15, for any A i , we have ∂ + A i ⊆ ∪ i ∂ + Q(j i ) ⊆ P ext , and we remind the reader that We will now want to prove that A ∪ P ext is correctable using the Generalized Expansion Lemma 37.
We can then repeat the argument as in Theorem 15 and prove the entire code is correctable: a contradiction if the code is to encode at least one logical qubit
We now turn to the case of the bound k. Proof. We remind the reader that Lemma 19 also holds for non stabilizer codes [22]. However due to the restriction from Lemma 36 that ∂ + M 1 has to be correctable, we will have to adapt our use of the recursive separation: instead of creating regions of size d, we will stop at d/δ. From 21, we can find A such that A is the union of disjoint subsets {V • } of size less than d/δ, and |A| ≤ S d/δ (n). For every
By applying the same argument as in Lemma 22, we find k ≤ S d/δ • S d/δ (n).
In this section, we wish to clarify when we can apply Kisfaludi-Bak's results. Their statement is not in terms of (ρ, w)-local graphs, but instead in terms of a certain class called noisy uniform ball graphs (NUBG). This class is defined as follows.
Definition 40 (Noisy uniform ball graphs (NUBG)). Let (M, d) be a metric space. Let σ > 0 and ν ≥ 1 be fixed constants. A graph G = (V, E) ∈ NUBG H D (σ, ν) if there is a function η : V → M such that for all pairs v, w ∈ V , we have 1. d(η(v), η(w)) < 2σ =⇒ (v, w) ∈ E. Definition 40 requires all vertices close enough to another vertex to be connected. Note that a (ρ, w)-local graph G can be extended to a (w/2, 2)-NUBG graph by adding edges between any two vertices that are a distance w/2 away, written G w/2 = (V w/2 , E w/2 ). The vertex set V w/2 = V and the edges in the modified graph G w/2 obey the condition
Since the density ρ is constant, this modification adds at most a constant number of edges. Note then that a separator S for the NUBG graph G w/2 is also a separator for G.
For completeness, we repeat the definition of Theorem 2 from [60] using the language of NUBG graphs as in the original paper.
Accepted in Quantum 2022-04-16, click title to verify. Published under CC-BY 4.0.
The separator itself is hard to compute. Surprisingly, there exist polynomial-time algorithms to approximate the separator of an arbitrary graph up to constant factors[74].