Generating FaultTolerant Cluster States from Crystal Structures
Abstract
Measurementbased quantum computing (MBQC) is a promising alternative to traditional circuitbased quantum computing predicated on the construction and measurement of cluster states. Recent work has demonstrated that MBQC provides a more general framework for faulttolerance that extends beyond foliated quantum errorcorrecting codes. We systematically expand on that paradigm, and use combinatorial tiling theory to study and construct new examples of faulttolerant cluster states derived from crystal structures. Included among these is a robust selfdual cluster state requiring only degree connectivity. We benchmark several of these cluster states in the presence of circuitlevel noise, and find a variety of promising candidates whose performance depends on the specifics of the noise model. By eschewing the distinction between data and ancilla, this malleable framework lays a foundation for the development of creative and competitive faulttolerance schemes beyond conventional errorcorrecting codes.
I Introduction
Faulttolerant quantum computation is possible, provided that error processes are sufficiently weak and uncorrelated Aliferis et al. (2006); Knill et al. (1996); Aharonov and BenOr (1997); Terhal and Burkard (2005); Aliferis and Terhal (2007). However, quantum systems are inherently delicate, and so it is important maximize the robustness of a faulttolerance strategy relative to the specific noise patterns a quantum processor experiences Knill (2005); Dennis et al. (2002); Raussendorf and Harrington (2007); Wang et al. (2003); Ohno et al. (2004); Wang et al. (2010); Fowler et al. (2009, 2012); Suchara et al. (2015a); Wang et al. (2011); Stephens et al. (2013).
Typically, faulttolerance schemes are founded on constructing and maintaining a quantum errorcorrecting code Shor (1996, 1995); Calderbank and Shor (1996); Steane (1996, 1997); Gottesman (1997) on which abstracted logical circuits can be implemented with high fidelity. However, there is an alternative to circuitbased quantum computation (CBQC) that is built on the adaptive measurement of highlyentangled resource states Raussendorf et al. (2003); Briegel et al. (2009). This alternative has been appropriately named measurementbased quantum computation (MBQC), and has blossomed within the framework of faulttolerance Raussendorf and Harrington (2007); Raussendorf et al. (2007, 2006, 2005).
Most proposals for faulttolerant MBQC are based on a topological approach, whereby quantum circuits are woven into resource states via adaptive measurement choices Raussendorf et al. (2007, 2006). The ambient space on which this topological pattern occurs is commonly referred to as the D cluster state vacuum, and represents the errorresilient stitching that protects the computation. The essential property of this state is that it can both propagate highly nonlocal correlations, which carry the logical information being manipulated, while supporting local correlations, which act as consistency checks to catch errors. This permits the sharing of longrange entanglement in the presence of noise, which is essential for any faulttolerance scheme Raussendorf et al. (2005).
Early on, a fundamental connection was observed between D cluster states and surface codes Raussendorf and Harrington (2007), which was later extended to CSS codes Bolt et al. (2016, 2018) and eventually all stabilizer codes Brown and Roberts (2018). This connection has been termed foliation, which according to its name, maps a stabilizer code to a cluster state representing the evolution of that code in time. In particular, each data qubit of the code is replaced by a timelike D cluster state, so that the foliated code maintains the errorcorrection properties of the base code in a naturally phenomenological error model.
Recently, pioneering work by Nickerson and Bombín studied cluster states that cannot be realized as the foliation of any quantum code Nickerson and Bombín (2018). The central insight is that faulttolerant cluster states need not behave as timelike errorcorrecting codes to maintain their essential property: the coexistence of longrange logical correlations with local consistency checks. At the circuit level, this manifests as constantly measuring and reinitializing all of the qubits, so that each plays a role in both propagating logical information and catching errors. This stands in contrast to a quantum errorcorrecting code, in which the logical information is held statically in data qubits that remain unmeasured until the end of the computation, while only the ancilla qubits search for errors. Relaxing this division of labor opens up a new design space to explore, and Nickerson and Bombín (2018) employed a splitting technique reminiscent of techniques in network theory Nguyen et al. (1994); Parhami and Kwai (2001) to construct new cluster states that were resilient to both dephasing and erasure noise.
In this work, we use tools from combinatorial tiling theory Dress (1987) to study and construct a broad range of robust faulttolerant cluster states. The central idea is to use a discrete analogue of orbifold covers to turn the geometric problem described in Nickerson and Bombín (2018) into an algebraic problem on groups DelgadoFriedrichs (2001). Although we focus on cluster states that are built from periodic crystal structures, we also discuss how these techniques can apply more generally. To illustrate the power of this algebraic approach, we construct a selfdual faulttolerant cluster state that is optimally local, requiring only a regular underlying graph state. See Figure 1 for a highlevel description of the main idea.
In addition, we benchmark these cluster states in the presence of circuitlevel noise with varying relative parameters. We do so using a minimumweight perfect matching decoder, which is less efficient than the unionfind decoder Delfosse and Nickerson (2017) utilized in Nickerson and Bombín (2018), but which exhibits higher performance and relates to the zerotemperature phase transition of associated statistical mechanical models with quenched disorder Wang et al. (2003); Chubb and Flammia (2018). We find a variety of competitive cluster states whose robustness depends on the specifics of the noise parameters.
The paper is organized as follows. In Section II, we discuss the general formulation of faulttolerant cluster states in terms of chain complexes, and introduce their relevant circuitlevel noise models. In Section III, we review the foundations of combinatorial tiling theory, and use it to identify interesting faulttolerant cluster states based on crystal structures. In Section IV, we provide numerics on examples drawn from an extensive classification of selfdual tilings to both benchmark promising candidates, and to probe the effects of circuitlevel noise. Finally, we discuss avenues for future development in Section V.
Ii FaultTolerant Cluster States
ii.1 CSS codes as chain complexes
To understand faulttolerant cluster states, it is instructive to first review quantum CSS codes. In particular, there is a wellestablished interpretation of CSS codes as chain complexes Bombin and MartinDelgado (2007); Kitaev (2003); Freedman et al. (2002). Throughout, we implicitly work with coefficients in , reflecting the use of qubits.
Definition 1.
A chain complex is a sequence of vector spaces and linear maps between them called boundaries:
satisfying . Every such complex has an associated cochain complex comprised of vector spaces and linear maps between them called coboundaries:
satisfying We sometimes refer to as the dual of , and we call the length of the chain complex.
One important characteristic of a chain complex relevant to the associated quantum code is its homology. This measures the failure of each sequence of boundary maps to be exact.
Definition 2.
The homology groups of the chain complex are the quotient spaces . The cohomology groups of the chain complex are the quotient spaces . Representatives of elements in these quotient spaces are referred to as cycles and cocycles, respectively.
It turns out that chain complexes and their homology provide a natural language for describing and building CSS codes.
Definition 3.
An CSS code can be identified with a length chain complex :
where and .
In particular, we have the following correspondence:
The boundary condition ensures the commutativity of the  and type stabilizers. By construction, the class of type (type) logical operator representatives can be identified with nontrivial cycles (cocycles) in ().
Logical qubits can be identified with pairs of  and type logical operators , and so it should be the case that . Furthermore, these logical operators should satisfy canonical anticommutativity relations . This correspondence manifests as a structure theorem on chain complexes Hatcher (2000).
Theorem 4 (Universal Coefficient Theorem).
There is a welldefined isomorphism
given by .
Thus, for any nontrivial cycle representing a logical type operator, there is a nontrivial cocycle representing a logical type operator that intersects with odd parity when identified with its dual in . Furthermore, this element will intersect any equivalence class of cycles with even parity. Consequently, the factorization of the logical subspace into logical qubit subsystems is captured by the structure of the chain complex.
This perspective has been extremely profitable in several ways, including the construction of codes with improved parameters Kitaev (2003); Freedman et al. (2002); Bravyi and Hastings (2014); Hastings (2016); Londe and Leverrier (2017); Audoux and Couvreur (2015), the study of singleshot errorcorrection Campbell (2019); Bombín (2015), and the design of faulttolerant gates JochymO’Connor (2019); Krishna and Poulin (2019). We detail two foundational examples of this correspondence in Figure 2.
In the language of chain complexes, errorcorrection in the code capacity model can be rephrased as the following problem:
(1) 
Colloquially, this reads: given  and type syndromes, determine corrections that, taken together with the errors, apply the logical identity. For many error models, this problem can be treated independently in each coordinate without significant loss in performance Bombin et al. (2012); Dennis et al. (2002). In the presence of depolarizing noise, it is then optimal to choose code families for which these two problems are symmetric, as the threshold will be determined by the worse of the two. These include families like the toric and color codes, while asymmetric families like Shor’s code Shor (1995) will be bottlenecked by one type of error Li et al. (2019).
The chain complex formulation of errorcorrection can be extended to phenomenological noise as well. In particular, recent work has studied redundant syndromes checks in the context of length chain complexes in order to characterize singleshot errorcorrection Campbell (2019); Bombín (2015). It is then apt that faulttolerant cluster states, which eschew the distinction between data and ancilla, meet in the middle between length and length chain complexes.
ii.2 Faulttolerant cluster states as chain complexes
Having described CSS codes in the chain complex framework, we turn to describing faulttolerant cluster states. Despite their similarities, faulttolerant cluster states afford an extra degree of freedom that is useful in the construction of robust quantum processes Nickerson and Bombín (2018). As with most measurementbased schemes, our faulttolerant cluster states will be built from a particular class of stabilizer states associated to graphs.
Definition 5.
For a graph , the associated graph state is the unique state stabilized by the set of operators
Informally, cluster states refer to particular families of graph states that are used as a resource for MBQC.
Defining a complete faulttolerant MBQC scheme involves several considerations, including details describing the implementation of a universal gate set. For existing proposals, this information requires the specification of additional structures, such as input/output surfaces and their relation to defects Raussendorf et al. (2007); Brown and Roberts (2018).
In this work, we focus on the errorresilience of the vacuum. Consequently, we consider a distilled problem: the preservation of longrange correlations in the presence of errors. As was noted in Nickerson and Bombín (2018), the faulttolerance schemes we discuss can be readily adapted to universal faulttolerant MBQC using the topological techniques in Raussendorf et al. (2007). However, this simplified perspective allows for a concise description of errorresilient vacuums.
Definition 6.
A faulttolerant cluster state can be identified with a length chain complex :
The underlying graph state is given by the bipartite graph with biadjacency matrix . We refer to qubits indexed by as dual, and qubits indexed by as primal.
We emphasize that the underlying graph state is entirely determined by the map , which encodes a single bipartite graph; the maps and serve to distinguish the correlations used for errorcorrection.
There is an intrinsic asymmetry in cluster states, indicated by the presence of type symmetries and absence of type symmetries, introduced by the asymmetric definition of a graph state. This asymmetry also manifests in the construction and processing of a faulttolerant cluster state. Following the prescription in Raussendorf et al. (2007), for a cluster state on qubits with underlying graph state , this proceeds in three steps.

Prepare .

For each , apply CZ in some specified order.

Measure each qubit in the basis.
In particular, we have the following correspondence:
For any indexing dual qubits, there is a corresponding symmetry of the form
where the are supported on dual qubits and the are supported on primal qubits. The reverse relation holds for in the cochain complex. Thus, when we identify () with dual (primal) symmetries, we mean symmetries whose restriction to dual (primal) qubits is of type.
Just as the structure of a length chain complex can be interpreted naturally in terms of the properties of a CSS code, so too can the structure of a length chain complex be interpreted naturally in terms of the properties of a faulttolerant cluster state.^{1}^{1}1Note that primal logical symmetries and dual logical symmetries correspond, respectively, to dual correlation surfaces and primal correlation surfaces as described in Raussendorf et al. (2007). For a geometrically defined cluster state, a primal (dual) logical symmetry can be visualized as a closed surface in the dual (primal) lattice.
Chain Complex  Faulttolerant Cluster State 

Dual stabilizers are accessible via measurements.  
Indexes equivalence classes of dual logical symmetries.  
Primal errors equivalent to dual errors are undetectable.  
Indexes equivalence classes of primal logical errors.  
Primal stabilizers are accessible via measurements.  
Indexes equivalence classes of primal logical symmetries.  
Dual errors equivalent to primal errors are undetectable.  
Indexes equivalence classes of dual logical errors. 
Equivalence classes of dual (primal) logical symmetries are defined up to dual (primal) stabilizer equivalence, while equivalence classes of undetectable dual (primal) errors are defined up to primal (dual) error equivalence. Such errors are trivial, as they commute with our measurements. Theorem 4 ensures that there are canonical isomorphisms
so that for every logical symmetry, there is a corresponding undetectable error that negates it.
One subtlety is that, without specifying input/output surfaces, there is no explicit correspondence between primal and dual symmetries emulating a logical qubit Raussendorf et al. (2005); Brown and Roberts (2018). This correspondence is explicit for foliated codes, as measuring the bulk of the lattice generates an encoded longrange Bell pair between these surfaces Bolt et al. (2016). We focus on faulttolerant cluster states realized by periodic cellulations of space, for which the notions of input/output surfaces, defects, and topologically protected gates can be introduced directly Raussendorf et al. (2007); Nickerson and Bombín (2018). However, faulttolerant cluster states need not be geometrically defined, as the chain complex structure need not stem from the cellulation of a manifold. Any foliation of a nonhomological code is an example of such a state, and faulttolerant cluster states can be more general still.
Having established the parallels between length chain complexes and faulttolerant cluster states, errorcorrection in the faulttolerant MBQC model can be rephrased as the following problem:
(2) 
Once again, this can be read colloquially as: given primal and dual syndromes, determine primal and dual corrections that, taken together with the errors, preserve the primal and dual logical symmetries. Mirroring CSS codes, this problem can be treated independently in each coordinate, and so it is often optimal to choose a faulttolerant cluster state for which these two problems are symmetric. In particular, both primal and dual symmetries are required to perform universal faulttolerant computation Raussendorf et al. (2007).
Although the problems of errorcorrection in CSS codes and errorcorrection in faulttolerant cluster states appear similar, comparing problems (1) and (2), there are key differences between them (see Figure 3). There is a mapping between these two problems that associates to any stabilizer code a faulttolerant cluster state called the foliation of that code. The key insight made in Nickerson and Bombín (2018) is that this mapping is too restrictive; there is an extra degree of freedom in problem (2) that can be exploited to construct more robust faulttolerant protocols. To highlight this difference, we review foliation in the case of CSS codes, which has also been extended to all stabilizer codes Brown and Roberts (2018).
ii.3 Foliated quantum codes
Foliated quantum codes are not codes persay, but rather faulttolerant cluster states that are closely related to codes. In particular, foliation is a map that takes any CSS (or more generally stabilizer) code and constructs a corresponding faulttolerant cluster state that emulates that code evolving in time for some number of time steps Bolt et al. (2016). The most famous example is the D cluster state on a cubic lattice, which can be seen as a foliated D surface code.
Given a CSS code presented as a length chain complex
and a number of timesteps , its timestep foliation is the following faulttolerant cluster state, presented as a length chain complex:
Let denote the identity on , and for , let denote the map that applies from to and is zero everywhere else. Then the corresponding boundary maps are
This chain complex is welldefined, and that the corresponding faulttolerant cluster state inherits the properties of the underlying CSS code Bolt et al. (2016). It is easiest to visualize a foliated code by replacing each code qubit with a timelike D cluster state, with ancilla and ancilla interacting with the cluster state in alternating timesteps Brown and Roberts (2018). This picture recovers the D cluster state as a foliated surface code, emphasized in Figure 4. We include the timestep foliated code, along with its associated chain complexes, as another leading example in Figure 5.
Foliated quantum codes are closely related to their corresponding CSS codes in a phenomenological model; indeed the spacetime decoding processes for each can be nearly identical Dennis et al. (2002); Raussendorf and Harrington (2007). Foliated codes also yield a prescription for building faulttolerant cluster states: a priori, building length chain complexes with desirable properties like high distance, high encoding rate, or locality can be a difficult task. Generally, foliation allows one to port existing constructions of quantum errorcorrecting codes to the MBQC framework, making it a powerful tool.
However, it is also restrictive. There are chain complexes corresponding to faulttolerant cluster states that cannot be realized as the foliation of any quantum code Nickerson and Bombín (2018). The broadened framework of length chain complexes permits a wide variety of robust cluster states that often outperform their foliated cousins. In some sense, this generalizes the notion of quantum errorcorrection in a phenomenological error model. Mirroring the construction of the toric code, one good prescription for building sparse chain complexes corresponding to robust cluster states is by cellulating manifolds. However, before building cluster states from cellulations, it will be helpful to first interpret the effects of different types of noise on such states. In what follows, we describe a circuitlevel error model and identify which cluster states should be robust to which parameter regimes of noise.
ii.4 Circuitbased error model and its effects
We consider a simple circuitlevel Pauli error model that captures the correlated errors that may occur due to gate failures. Decoding will be performed independently on primal and dual qubits, and so we describe errors that manifest as type on primal qubits; errors on dual qubits can be treated analogously. We consider three types of errors.

Measurement errors occur with probability . This can also account for preparation errors.

type errors occur on the dual qubit support of a CZ gate with probability after the gate.

type errors occur on the primal qubit support of a CZ gate with probability after the gate.
Although errors commute with our measurements, errors occurring on dual qubits during the construction of the cluster state will result in correlated errors on primal qubits.
For faulttolerant cluster states constructed as cellulations, we build the underlying graph state facebyface. In each face, the CZ gates are applied in consecutive order about the face so that the resulting correlated errors are stringlike.^{2}^{2}2There is a subtlety here: the errorcorrection performance may depend on this ordering, and optimal orderings for primal and dual qubits may not be compatible. An augmented skeleton of the cellulation will then serve as the decoder graph, see Figure 6.
There are three broad design principles discussed in Nickerson and Bombín (2018) relevant to the construction of faulttolerant cluster states built as cellulations of manifolds:

Low average vertex degree: heuristically, lower degree vertices yield more information about the surrounding errors, resulting in more robust errorcorrection. In the limiting case, the repetition code in a code capacity model can be thought of as having a degree decoder graph. This is particularly important when dominates, as measurement errors are indifferent to the construction cost of the cluster state. Consequently, choosing the most robust errorcorrection is optimal.

Few edges in each face: a face with many edges may result in longrange correlated errors. This is particularly important when dominates, as errors on dual qubits cause such errors.

Few faces incident to each edge: to first order in , the effective error rate each qubit experiences is given by the number of CZ gates it participates in. This is determined by the number of faces its corresponding edge belongs to, and so is particularly important when dominates.
As correlated errors on twoqubit gates tend to commute with the gates themselves Aliferis et al. (2009); Aliferis and Preskill (2008); Trout et al. (2018), we generally expect with varying; however, we consider a variety of noise models. Additionally, for selfdual complexes, principles () and () become identical. A final heuristic worth following is increasing the symmetry of the underlying graph states, as homogeneous structures tend to perform better. Broadly, we expect that given different relative error strengths, different faulttolerant cluster states appropriately balancing robust errorcorrection with locality become viable.
Iii Combinatorial tiling theory
Building quantum codes from manifolds has been enormously profitable, resulting in some of the best known local codes Freedman et al. (2002); Kitaev (2003); Hastings (2016); Londe and Leverrier (2017); Breuckmann et al. (2017); Breuckmann and Terhal (2016); Conrad et al. (2018). However, we do not focus on the topological properties of a faulttolerant cluster state, but rather the way in which its vacuum is stitched together. Correspondingly, the objects of interest are no longer manifolds but rather certain orbifolds,^{3}^{3}3A space locally modeled on Euclidean space modulo a linear finite group action, which may not be free. and in particular, their underlying simplicial structures. These admissible triangulations are encoded into dressed graphs known as extended Schläfli symbols, and their study is broadly known as combinatorial tiling theory Dress (1985, 1987); Dress and Huson (1987); Grünbaum and Shephard (1987); Huson (1993); Balke and Huson (1996); DelgadoFriedrichs et al. (2003a); DelgadoFriedrichs (2001); DelgadoFriedrichs et al. (1999); DelgadoFriedrichs and Huson (1997); Thurston et al. (1997); Hyde et al. (2006). Put simply for our purposes, it is the algebraic study of ways to periodically tile space.
Following Nickerson and Bombín (2018), we focus on building faulttolerant cluster states from such tilings, forming a length chain complex in the usual way. The underlying graph state is constructed by placing qubits on faces and edges, with graph state edges determined by . The skeleton of the tiling will determine the robustness of primal errorcorrection, with a decoder graph that is an augmented version of the skeleton. The same holds for dual qubits in the dual tiling, and so we focus on selfdual complexes to realize symmetric thresholds.
iii.1 Constructing tilings
We next review the foundations of combinatorial tiling theory, following the prescription of DelgadoFriedrichs (2001) towards the construction and recognition of tilings.
Definition 1.
A tiling is a regular CWcomplex^{4}^{4}4Closurefinite, weak topology. realizing a simply connected dimensional manifold. Its symmetry group is the group of all automorphisms that respect the induced CWfiltration.
Informally, a tiling is a partition of space, and it determines a group of symmetries that respect the partition. There is a notion of equivalence between tilings that depends on both their topological structure and their symmetry group.
Definition 2.
Two tilings with respective symmetry group are equivariantly equivalent if there exists a homeomorphism respecting the filtration that induces an isomorphism given by .
To study tilings, it is useful to break them down into elemental combinatorial objects called flags.
Definition 3.
A flag is an increasing sequence of cells with and where each belongs to the skeleton, but not the skeleton.
Let denote the set of all flags. A central insight of Dress (1985) is to study two relevant group actions on . The first is induced by , as each automorphism respects the filtration. The second is by the free Coxeter group.
Definition 4.
The free Coxeter group generated by reflections is the group
For each flag and each index , there is a unique flag satisfying for all and . This yields a welldefined action given by . Furthermore, the actions of and commute, and so the action descends to an action on the set of flag orbits Specifying the free Coxeter group action, in terms of its generators and relations, on each flag orbit carries all relevant information about a tiling. The objects representing this information are known as extended Schläfli symbols (or Delaney symbols, see Blatov et al. (2010)).
Definition 5.
A dimensional extended Schläfli symbol is a set equipped with a transitive action along with, for each and for all , positive natural numbers satisfying

,

,

for any .
The symbol is further called regular if for all .
We will generally refer to these as symbols , leaving implicit the extra information carried by the set. There is also a notion of maps between symbols called coverings, analogous to covering maps between orbifolds.
Definition 6.
A covering of a dimensional symbol by another dimensional symbol is an equivariant map satisfying for all . The covering is an isomorphism if is bijective.
We will often be concerned with selfdual cluster states, as our thresholds will be limited by errorcorrection on the worse of the two lattices. Fortunately, the corresponding notion of duality on symbols is quite simple.
Definition 7.
The dual of a dimensional extended Schläfli symbol is the symbol obtained by interchanging and . A symbol is called selfdual if it is isomorphic to its dual.
For a dimensional tiling with symmetry group , we can associate a dimensional symbol in the following way.

Let with corresponding transitive action inherited from .

For each flag orbit , for any flag , and for any , let denote the order of the action about , namely . This is independent of the choice of representative .
Note that for a tiling, the th cell of depends only on the  and cells of . Consequently, any symbol associated to a tiling must be regular, as the corresponding , must commute. Extended Schläfli symbols provide a sharp invariant for characterizing equivariant equivalence classes of tilings.
Theorem 8 (Dress (1985)).
Two tilings are equivariantly equivalent if and only if their associated extended Schläfli symbols are isomorphic.
Symbols are often presented as dressed graphs DelgadoFriedrichs (2001). The vertex set is given by , with each vertex labeled by its corresponding . For regular symbols associated to tilings, the order of the necessarily commuting reflections is typically omitted, so that each vertex is only labeled by . The edge set is determined by the action, with each edge labeled by the corresponding reflection generator. For tilings, these can be visualized by barycentrically subdividing the tiling into simplices representing flags, with the action represented by reflections about facets; see Figure 7.
Just as we can create a symbol from a tiling, so too can we construct the underlying space Top of an orbifold encoded by a symbol . This is done by associating to each a simplex with facets, and then identifying the th facets of two simplices if the corresponding elements of are exchanged by .^{5}^{5}5The information specifying the singular locus of the orbifold is lost in this mapping. Coverings can also be realized as continuous maps that identify simplices.
To summarize, we can map from tilings to symbols, and from symbols to topological spaces, where the equivariant equivalence class of a tiling is determined by its associated symbol.^{6}^{6}6The composition of these maps need not recover the tiling, but rather encodes an orbifold covered by the tiling. We would like to construct tilings from symbols directly in order to turn the former geometric problem into a (dressed) graph problem. To do so, we must determine which symbols can be used to realize tilings of Euclidean space. For this, we can use a covering space theory of symbols inherited from the covering space theory of orbifolds DelgadoFriedrichs (2001); Thurston et al. (1997). This will further transform the problem on dressed graphs into an algebraic problem on their associated fundamental groups.
Definition 9.
Let be an extended Schläfli symbol with basepoint . Up to isomorphism, there is a unique symbol with basepoint and a covering with such that for any other covering and any , there is a unique through which factors: with Thurston et al. (1997). We call the universal cover of .
Furthermore, an explicit presentation for the universal cover of can be constructed according to the prescription in DelgadoFriedrichs (2001). Namely, fix a basepoint and identify with cosets in of the normal subgroup
where the action is inherited from the group, and define As , this defines a valid cover with covering map , where the information about is passed to through the group action in the exponent of . In fact, opposite to the universal cover of , there also exists a final (or minimal) cover . Up to basepoints, this is defined as the unique symbol with covering such that, for any other covering , there is a unique through which factors:
Given the universal cover of a symbol , we can define the fundamental group of as the group of deck transformations in the usual way.
Definition 10.
Let be an extended Schläfli symbol with basepoint , and let be its universal cover with covering map . Then the fundamental group of is given by the subgroup of automorphisms of annihilated by ,
Following the construction of the universal cover, the fundamental group can be constructed explicitly as with a finite presentation Balke and Valverde (1996). We then have the usual correspondence between subgroups and covers of , given by and pictured below.
On the left, we have a sequence of inclusions of groups, and on the right, a corresponding sequence of coverings of symbols. From top to bottom, the sizes of the objects on the left increase, while the sizes of the objects on the right decrease. We can regard moving up the diagram as unfurling the symmetries of a symbol; the final cover has a maximal group of symmetries and the universal cover is a complete unfurling of those symmetries.^{7}^{7}7In particular, the symbols we associated to tiling were actually their final covers, corresponding to a realization of space by a minimal set of simplices, but expanded by a maximal set of symmetries.
For now, we are interested in determining which symbols correspond to (unfurled) periodic tilings of Euclidean space. Such an should be covered by with deck transformations realizing Euclidean isometries, up to homeomorphism. As symbols also carry the underlying orbifold structure, we also insist that the cover carry a trivial orbifold structure free of local group actions. Correspondingly, the universal cover must satisfy
for all .^{8}^{8}8This property, called semigood in DelgadoFriedrichs (2001), is not necessary for the construction of the chain complex; we only care about the underlying manifold structure. However, it is helpful in not doublecounting symbols that may correspond to the same underlying tiling. Symbols satisfying these two properties are called flat, and it suffices to test flatness on any symbol covered by .
Theorem 11 (DelgadoFriedrichs (2001)).
If and are dimensional symbols with covering , then is flat if and only if is flat.
By design, we are looking for infinite universal covers. Fortunately, for finite symbols corresponding to compact orbifolds, any flat symbol must use an infinite translational symmetry group of finite index to fill Bieberbach (1911, 1912). Thus, one can enumerate over finite index subgroups of until identifying one isomorphic to , and then construct the corresponding finite cover. If the symbol is free of local group actions, then one can check algorithmically whether its simplicial topological realization is homeomorphic to a torus Hemion (1992). If so, then the symbol encodes a tiling by unfurling these final translational symmetries. For a complete description of how to perform this check efficiently, see DelgadoFriedrichs (2001).
In summary, in order to construct a faulttolerant cluster state with desirable properties like selfduality and locality, one begins by constructing valid symbols with those desired properties. There are several necessary conditions one can impose to narrow this search, such as demanding regularity and positive curvature on tiles, as they themselves must be spherical. Then, one can follow the above prescription to construct the associated fundamental group explicitly, and search for a subgroup of spanning translational symmetries. If found, the corresponding finite cover encodes a tiling realizing to the desired cluster state, which can be built from translations of the unit cell represented by this symbol.
It is worth noting that, instead of building faulttolerant cluster states based on tilings of space, we could instead try and build CSS codes based on tilings of space. In the D setting, the Euler characteristic provides a simple invariant for detecting the zerocurvature of a flat D symbol , which must satisfy . However, this limits the average degree of a selfdual tiling to , which also determines the locality of the code, and so the toric code is essentially optimal with symmetric noise. The central insight in Nickerson and Bombín (2018) is that this limitation is relaxed in D (where the Euler characteristic is zero) due to the increased length of the chain complex. However, faulttolerant cluster states still incur a tradeoff between the graph state degree and decoder graph degree in a selfdual lattice, as we will see shortly.
iii.2 Generating selfdual faulttolerant cluster states with local underlying graph states
iii.2.1 An optimally local faulttolerant cluster state
Before detailing a large class of selfdual faulttolerant cluster states, presented in terms of their corresponding symbols, we begin with a single fullyrealized and optimally local example. Broadly, we’ve discussed two design principles from Nickerson and Bombín (2018) for building a robust faulttolerant cluster state: low average degree of the underlying skeleton, contributing to robust errorcorrection, and underlying graphstate locality, contributing to a low effective errorrate and minimal correlated errors.
Mirroring the D case, these two parameters experience a tradeoff. For example, any spanning surface in a D tiling must itself obey the zerocurvature of a D tiling. As described in Section II.4, we expect the performance of faulttolerant cluster states to vary based on the relative strength of different noise sources. In Figures 8 and 9, we depict four highly symmetric selfdual faulttolerant cluster states spanning this tradeoff, including one of the new optimally local (regular) graph states found by our search. In particular, the underlying graph state requires only degree connectivity.
The cubic, diamond, and triamond Nickerson and Bombín (2018) lattices are carried by special selfdual tilings. Up to a maximal group of symmetries, they only have one type of volume, face, edge, and vertex, although only the cubic tiling has a single type of flag. It has been conjectured that, among a subclass of tilings called natural, these are the only selfdual tilings with this property DelgadoFriedrichs et al. (2003a).^{9}^{9}9However, natural tilings play no special role for our purposes, and (nonselfdual) nonnatural tilings with only one type of volume, face, edge, and vertex have been constructed DelgadoFriedrichs et al. (2003b). However, the degree selfdual faulttolerant cluster state described in Figure 8 is also highly symmetric: both the graph state and the decoder graph are regular. In fact, up to a maximal group of symmetries, it has only two types of volumes, faces, edges, and vertices.^{10}^{10}10This can be determined by removing one of the reflection generators, and then counting distinct isomorphism classes of the connected components of the new dimensional symbol. Although the decoder graph is relatively dense, the graph state locality can make it robust to particular noise processes.
iii.2.2 Families of degree3, 4, and 5 selfdual faulttolerant cluster states
Next, we describe how simple heuristics, combined with the prescription in Section III.1, can yield a wealth of robust selfdual faulttolerant cluster state candidates. Although one should ideally choose a cluster state that is optimal for a particular noise model, we focus on only , , and regular graph state families for simplicity. Very broadly, we would expect local families to perform better in the presence of stronger correlated errors, and denser families to perform better in the presence of stronger independent errors. In particular, this search yielded the aforementioned optimally local example, among many others.
Writing down valid, regular, selfdual symbols corresponding to regular graph states can be tricky given the many conditions they must satisfy. However, here is one prescription for doing so.

For a desired , choose any or .

Form a matrix of nodes defining the vertex set of .

Indexing the nodes from in the bottomleft corner to in the topright corner, insert the following edges.

For every , connect and with an edge if is even, or with an edge if is odd.

For every , connect and with an edge if is even, or with an edge if is odd.

If is odd, complete the symbol with selfloops along the boundary. If , complete the symbol with periodic boundaries. If is even, complete the symbol with either selfloops along the boundary or with periodic boundaries.


Define for all .

For every orbit lying either below or intersecting the diagonal, and for all in the orbit, choose if the orbit size is greater than one, else choose . This limitation is imposed by the crystallographic restrictions on rotational symmetries.

Define the remaining .
One example with appears in Figure 8. These are valid regular symbols, as for , each orbit forms a cycle of length or . The underlying graph state is an biregular graph, and so this algorithm, if it succeeds, yields an regular graph state. By construction, the symbol is selfdual, with reflection about inducing the duality isomorphism. From this definition, and its associated action are fixed. The only free parameters are the , which lie in restricted sets, forming potential configurations.^{11}^{11}11Small changes to this prescription, like mixed boundary conditions or exchanging and also yield valid symbols. We make specific choices to limit our search.
Gavrog is an opensource software built explicitly for analyzing tilings DelgadoFriedrichs ; DelgadoFriedrichs and O’Keeffe (2003); DelgadoFriedrichs (2003); DelgadoFriedrichs and O’Keeffe (2005); DelgadoFriedrichs (2005). Using its internal methods (and more generally GAP GAP ), which apply an optimized version of the construction in Section III.1, we search over these symbols to identify selfdual faulttolerant cluster states with regular underlying graph states. Among the candidates we searched over, the vast majority generated by , we found unique symbols realizing selfdual cluster states. The search results are summarized in Table 1, which are complete for all but . Rendering these can be difficult, depending on the complexity of the symmetry group. However, to fully translate from algebraic representations to concrete tilings, we graph the two examples described by in Figure 12.
(n,k)  Periodic?  (Candidates)  (Cluster States)  Example vectors  

N/A  
No  
Yes  
N/A  ^{12}^{12}12The cubic tiling.  
Yes  
No  
Yes  
No  ^{13}^{13}13With and , this realizes the doubleedge cubic cluster state in Nickerson and Bombín (2018).  
Yes 


N/A  
No  …  
Yes 

In summary, we can search for faulttolerant cluster states with desired properties by defining a heuristic on graphs representing symbols that satisfy those properties. Then, one can convert this to a computational problem on groups, and identify candidates whose geometric realization gives the desired cluster state. Finally, one can construct this cluster state from its graphical representation, and study robustness of the resulting state.
Although we stop at degree, we could continue this search to higher degree graph states. However, at higher degrees, one might also look for more symmetric tilings using other heuristics. Alternatively, one could search for low degree decoder graphs, rather than low degree graph states, although this constraint is not as straightforward to impose on a symbol.^{14}^{14}14For smaller symbols, one can determine vertex degrees by solving systems of equations involving the Euler characteristic. The maximum of the symbol also provides a simple lowerbound on the minimum degree.
Iv Benchmarking crystalline cluster states
Crystals are of fundamental importance in chemistry, and so there are an abundance of crystals carried by selfdual tilings already in the literature. In addition to building faulttolerant cluster states from symbols, we can search over existing databases for promising candidates. One example is the RCSR database, which has indexed selfdual tilings O’Keeffe et al. (2008). Each lattice is labeled with a threeletter identifier, which we adopt to refer to each tiling.
In Nickerson and Bombín (2018), the cubic (pcu), diamond (dia), doubleedged cubic, and triamond (srs) lattices were benchmarked with a unionfind decoder Delfosse and Nickerson (2017) in weighted phenomenological and weighted erasure error models. Although the unionfind decoder is highly efficient, it is often suboptimal when compared with the less efficient minimumweight perfect matching (MWPM) decoder Edmonds (2009); Kolmogorov (2009). In this section, we extend this analysis in three ways. First, we benchmark additional examples from the aforementioned set of selfdual faulttolerant cluster states, along with the one constructed in Section III.2. Second, we perform these simulations in a circuitlevel noise model that captures the tradeoff between robust errorcorrection and cluster state preparation. Our simulations span four different relative parameter regimes in order to better characterize the effects of this tradeoff. Finally, we use the highperformance MWPM decoder to obtain a closer estimate of the maximum thresholds achievable using this approach.
In fact, we can say more using a wellestablished connection between thresholds for quantum errorcorrection and statistical mechanical models. For each of these crystal lattices with cell complex , we can associate a lattice gauge theory with quenched disorder mirroring the randomplaquette gauge model on the cubic lattice Dennis et al. (2002); Wang et al. (2003); Ohno et al. (2004). The corresponding Hamiltonian is given by assigning spins to edges and defining
where is a quenched random variable and the local symmetry is obtained by flipping the spins on all edges incident to a vertex. The optimal phenomenological threshold for each lattice then corresponds to a phase transition of its corresponding model along the Nishimori line Dennis et al. (2002); Nishimori (1986); Kubica et al. (2018); Chubb and Flammia (2018).
The MWPM decoder selects, for each syndrome, an error class with the most likely individual error. While this is generally suboptimal, it can be viewed from the statistical mechanics perspective as the decoder that chooses a recovery string minimizing the free energy at zero temperature. Correspondingly, up to rescaling, our dephasing thresholds can be interpreted as zero temperature phase transitions for lattice gauge theories with disorder defined on a variety of crystal lattices, whose behavior may be of independent interest. The circuitlevel thresholds can also be interpreted similarly according to extensions of this model to correlated errors Chubb and Flammia (2018).
To simulate our noise model on a particular lattice, we first embed the lattice on a torus of linearsize . We choose a translationinvariant ordering of CZ gates in each face, and then form an augmented skeleton with edges corresponding to error gate failures on the primal qubit support and error gate failures on the dual qubit support. For this initial comparative benchmarking, we make this choice arbitrarily. On the one hand, this gate ordering is likely suboptimal. On the other, we do not benchmark the dual lattice, for which the gate ordering may be worse. The effects of this choice will grow with , and we leave further optimization to future work Andreta de Castro et al. (2019).
For each edge , let () be the number of type (type) gate failures that could excite . Then the probability of exciting edge with a type gate failure is given by
and the probability of exciting that edge due to an type gate failure is given analogously. The total probability of exciting an edge is then given by
In each trial, we excite edges according to and form the resulting syndrome. To choose a recovery string, we run MWPM Edmonds (2009); Kolmogorov (2009); L’Eculier (1999); L’Eculier et al. (2002) with edges weighted according to Wang et al. (2011). We declare failure if we have introduced a homologically nontrivial cycle after recovery. For each data point we ran trials, adding up to approximately computational hours in total, and observed good agreement with previous benchmarks Wang et al. (2003); Barrett and Stace (2010).
It is important to note that this a severe error model in which every error is damaging. The corresponding noise strength in a dephasing or depolarizing gate model should be rescaled by or , respectively. After rescaling, the threshold approaches analogous circuitlevel thresholds for the surface code Fowler et al. (2012); Suchara et al. (2015b); Raussendorf and Harrington (2007); Barrett and Stace (2010).
We simulate seven different lattices, referring to them by their threeletter RCSR identifiers.^{15}^{15}15We omit the doubleedge cubic lattice, which can be viewed as a concatenation of the D cluster state with a phaseflip repetition code, and was studied in Stephens et al. (2013); Rudolph (2017); Nickerson and Bombín (2018). We denote the degree cluster state by bst for bipyramidstar with triangular faces, and because it is best with respect to locality. Our simulation sizes span through , depending on the lattice. Although we do observe some finite size effects, it is important to note that several of the lattices have many vertices in their fundamental cell, so that their distance is much greater than . The additional three lattices were chosen from the RCSR database to validate our hypotheses on the effects of noise; we expect there are many more robust candidates. Renderings of these new lattices, along with a short summary of the selfdual tilings available in the database, are given in Appendix A. In addition, we run four noise models in which and are weighted differently. The resulting threshold estimates are summarized in Table 2, and the raw data is available in Appendix B.
bst  pcu  cdq  hms  dia  ctn  srs  

(UnionFind Nickerson and Bombín (2018))  N/A  N/A  N/A  N/A  
Supporting the discussion in Section II.4, the performance of each cluster state generally reflects the tradeoff between the degree of the graph state and of the decoder graph with respect to the relative strength of errors and errors. One can see the peak performer moving from right to left as correlated errors become more prevalent, and so we would expect the degree cluster state to be a top performer in an entirely correlated error model. However, as cluster states are constructed entirely from CZ gates, we believe that the noise regime in which dominates but and remain significant warrants the most interest Aliferis and Preskill (2008); Aliferis et al. (2009); Stephens et al. (2013). Indeed, this reflects the growing effort to take advantage of biased models Tuckett et al. (2018a, b, 2019); Xu et al. (2018); Puri et al. (2019); Li et al. (2019); Webster et al. (2015); Brooks and Preskill (2013). However, even when noise is symmetric, there are several candidates competitive with the surface code, and it appears that some lattices are generally more robust than others.
Unsurprisingly, the MWPM decoder performs better than the unionfind decoder. While this improvement is noticeable across all three compared lattices, the difference in performance only ranges from . Mirroring the results in Delfosse and Nickerson (2017) on the cubic lattice, we interpret this as positive evidence that the unionfind decoder may be a promising alternative to MWPM, given its essentially lineartime efficiency. However, it could be the case that this performance gap increases in the presence of correlated errors, for which the matching decoder can be tailored.
One outlier for symmetric and biased noise is the degree cluster state. Although the trend suggests that it may be a topperformer in a fully type error model, for more realistic models its thresholds are lower. Generally, achieving faulttolerance with degree connectivity or local interactions comes with difficult assumptions, or reductions in threshold. However, the sacrifice is often worth the cost, as locality is more valuable than it might appear at the level of gate errors Chamberland et al. (2019); Bravyi et al. (2013). Consequently, we believe that the performance of the degree cluster state, whose threshold is only a factor of away from the topperforming surface code, is very encouraging.
V Conclusions
Although there are many similarities between them, faulttolerant MBQC has certain freedoms that CBQC with errorcorrecting codes lacks. We can take advantage of these freedoms to build more robust faulttolerance protocols beyond those based on errorcorrecting codes. At the circuit level, this freedom manifests as passing logical information between qubits which are regularly measured and reinitialized, without a distinction between data and ancilla. This stands in stark contrast to the more restrictive CBCQ faulttolerance model, where logical information is held statically within the code qubits until a final measurement.
Using combinatorial tiling theory, we gave a prescription for building faulttolerant cluster states. Different types of errors have different effects, and one must balance locality of both the decoder graph and the graph state according to different relative error strengths and architectural considerations. We also expect many of these cluster states to be particularly resilient to measurement errors, as their relative error strength does not scale with the construction cost of the underlying graph state. Finally, we analyzed several examples of faulttolerant cluster states in a variety of noise models emulating circuitlevel errors, and benchmarked them with the highperforming MWPM decoder. These results draw closer to optimal thresholds for topological MBQC, and relate to statistical mechanical models defined on different crystal structures.
There are several immediate extensions worth exploring. It would be interesting to consider more varied noise models; for example, we expect local graph state constructions to perform well in the presence of correlated noise. Additionally, this framework is naturally robust to leakage, as no qubit is longlived. In comparison, thresholds of quantum errorcorrecting codes require additional teleportation gadgets which lower thresholds Suchara et al. (2015b). Further understanding these cluster states’ resilience to hybridized loss and Pauli models would also be of interest Nickerson and Bombín (2018); Varnava et al. (2007). While we have tested only a few examples to take a snapshot of their performance, a more thorough investigation of promising tilings and their robustness is warranted Andreta de Castro et al. (2019).
There are also several broader avenues worth exploring. Following Nickerson and Bombín (2018), we have restricted ourselves to geometrically defined cluster states. While this immediately extends to a universal faulttolerance scheme, it is not required by the underlying homological problem of preserving distinguished primal and dual symmetries. It would be interesting to study nonfoliated codes that are not geometrically defined, although it may be difficult to build abstract sparse chain complexes with the desired properties.
To this end, in the prescription for building faulttolerant cluster states from simplicial structures on orbifolds, we discarded those whose symmetries were not compatible with a Euclidean metric. However, for computational devices with alltoall connectivity, there is no need to restrict ourselves to periodic tilings of Euclidean space. Candidates with a subgroup in their fundamental group are particularly interesting, as this subgroup serves the role of growing the cluster state in the Euclidean case. One could additionally look at generalized notions of periodicity which have less restrictive symmetries.
Finally, there is no fundamental barrier to extending this approach to build faulttolerant cluster states from tilings of higher dimensional spaces. For example, a faulttolerant cluster state built from a D cubic lattice will inherit stringlike excitations as a foliation of the D toric code. This comes with a number of favorable properties, including high phenomenological thresholds and local decoders, stemming from the D toric code’s thermodynamic stability Duivenvoorden et al. (2018); Breuckmann et al. (2016); Kubica and Preskill (2019). However, it also requires higher degree graph states due to the D toric code’s weight stabilizers, which are damaging at the circuitlevel Duivenvoorden et al. (2018). Analogous to dimension, could we use a similar prescription in higher dimensions to construct lowdegree faulttolerant cluster states that exhibit stringlike excitations? We could also take the opposite approach, and try minimizing the degree of the decoder graph by constructing a higherdimensional analogue of the triamond lattice, similar to the hypercubic and hyperdiamond lattices. Understanding this tradeoff in higher dimensions, which allows for richer symmetry, would be of significant interest.
Vi Acknowledgments
The authors are indebted to Olaf DelgadoFriedrichs for various personal communications about tilings and his opensource software package, Gavrog. They are also grateful to Austin Daniel, Akimasa Miyake, and Naomi Nickerson for helpful comments. They thank Dripto Debroy, Shilin Huang, and Muyuan Li for their assistance in running numerical simulations. The computational resources for simulations were provided by the Duke Computing Cluster. This research was supported in part by the NSF STAQ project (1717523), the ODNI/IARPA LogiQ program through ARO grant (W911NF1610082), ARO MURI (W911NF1610349 and W911NF1810218), and EPiQC – an NSF Expedition in Computing (1730104).
References
 Aliferis et al. (2006) P. Aliferis, D. Gottesman, and J. Preskill, Quantum Information & Computation 6, 97 (2006).
 Knill et al. (1996) E. Knill, R. Laflamme, and W. Zurek, arXiv preprint quantph/9610011 (1996).
 Aharonov and BenOr (1997) D. Aharonov and M. BenOr, in Proceedings of the Twentyninth Annual ACM Symposium on Theory of Computing (ACM, 1997) pp. 176–188.
 Terhal and Burkard (2005) B. M. Terhal and G. Burkard, Physical Review A 71, 012336 (2005).
 Aliferis and Terhal (2007) P. Aliferis and B. M. Terhal, Quantum Information & Computation 7, 139 (2007).
 Knill (2005) E. Knill, Nature 434, 39 (2005).
 Dennis et al. (2002) E. Dennis, A. Kitaev, A. Landahl, and J. Preskill, Journal of Mathematical Physics 43, 4452 (2002).
 Raussendorf and Harrington (2007) R. Raussendorf and J. Harrington, Physical Review Letters 98, 190504 (2007).
 Wang et al. (2003) C. Wang, J. Harrington, and J. Preskill, Annals of Physics 303, 31 (2003).
 Ohno et al. (2004) T. Ohno, G. Arakawa, I. Ichinose, and T. Matsui, Nuclear Physics B 697, 462 (2004).
 Wang et al. (2010) D. Wang, A. Fowler, A. Stephens, and L. Hollenberg, Quantum Information & Computation 10, 456 (2010).
 Fowler et al. (2009) A. G. Fowler, A. M. Stephens, and P. Groszkowski, Physical Review A 80, 052312 (2009).
 Fowler et al. (2012) A. G. Fowler, A. C. Whiteside, and L. C. Hollenberg, Physical Review Letters 108, 180501 (2012).
 Suchara et al. (2015a) M. Suchara, A. W. Cross, and J. M. Gambetta, Quantum Information & Computation 15, 997 (2015a).
 Wang et al. (2011) D. S. Wang, A. G. Fowler, and L. C. Hollenberg, Physical Review A 83, 020302 (2011).
 Stephens et al. (2013) A. M. Stephens, W. J. Munro, and K. Nemoto, Physical Review A 88, 060301 (2013).
 Shor (1996) P. W. Shor, in Foundations of Computer Science, 1996. Proceedings., 37th Annual Symposium on (IEEE, 1996) pp. 56–65.
 Shor (1995) P. W. Shor, Physical Review A 52, R2493 (1995).
 Calderbank and Shor (1996) A. R. Calderbank and P. W. Shor, Physical Review A 54, 1098 (1996).
 Steane (1996) A. M. Steane, Physical Review Letters 77, 793 (1996).
 Steane (1997) A. M. Steane, Physical Review Letters 78, 2252 (1997).
 Gottesman (1997) D. Gottesman, arXiv preprint quantph/9705052 (1997).
 Raussendorf et al. (2003) R. Raussendorf, D. E. Browne, and H. J. Briegel, Physical Review A 68, 022312 (2003).
 Briegel et al. (2009) H. J. Briegel, D. E. Browne, W. Dür, R. Raussendorf, and M. Van den Nest, Nature Physics 5, 19 (2009).
 Raussendorf et al. (2007) R. Raussendorf, J. Harrington, and K. Goyal, New Journal of Physics 9, 199 (2007).
 Raussendorf et al. (2006) R. Raussendorf, J. Harrington, and K. Goyal, Annals of Physics 321, 2242 (2006).
 Raussendorf et al. (2005) R. Raussendorf, S. Bravyi, and J. Harrington, Physical Review A 71, 062313 (2005).
 Bolt et al. (2016) A. Bolt, G. DuclosCianci, D. Poulin, and T. Stace, Physical Review Letters 117, 070501 (2016).
 Bolt et al. (2018) A. Bolt, D. Poulin, and T. Stace, Physical Review A 98, 062302 (2018).
 Brown and Roberts (2018) B. Brown and S. Roberts, arXiv preprint arXiv:1811.11780 (2018).
 Nickerson and Bombín (2018) N. Nickerson and H. Bombín, arXiv preprint arXiv:1810.09621 (2018).
 Nguyen et al. (1994) J. Nguyen, J. Pezaris, G. Pratt, and S. Ward, in International Workshop on Parallel Computer Routing and Communication (Springer, 1994) pp. 101–115.
 Parhami and Kwai (2001) B. Parhami and D.M. Kwai, IEEE Transactions on Parallel and Distributed Systems 12, 74 (2001).
 Dress (1987) A. W. Dress, Advances in Mathematics 63, 196 (1987).
 DelgadoFriedrichs (2001) O. DelgadoFriedrichs, Discrete & Computational Geometry 26, 549 (2001).
 Delfosse and Nickerson (2017) N. Delfosse and N. H. Nickerson, arXiv preprint arXiv:1709.06218 (2017).
 Chubb and Flammia (2018) C. T. Chubb and S. T. Flammia, arXiv preprint arXiv:1809.10704 (2018).
 Bombin and MartinDelgado (2007) H. Bombin and M. A. MartinDelgado, Journal of Mathematical Physics 48, 052105 (2007).
 Kitaev (2003) A. Y. Kitaev, Annals of Physics 303, 2 (2003).
 Freedman et al. (2002) M. H. Freedman, D. A. Meyer, and F. Luo, in Mathematics of Quantum Computation (CRC Press, 2002) pp. 287–320.
 Hatcher (2000) A. Hatcher, Algebraic Topology (Cambridge Univ. Press, Cambridge, 2000).
 Bravyi and Hastings (2014) S. Bravyi and M. B. Hastings, in Proceedings of the FortySixth Annual ACM Symposium on Theory of Computing (ACM, 2014) pp. 273–282.
 Hastings (2016) M. B. Hastings, arXiv preprint arXiv:1608.05089 (2016).
 Londe and Leverrier (2017) V. Londe and A. Leverrier, arXiv preprint arXiv:1712.08578 (2017).
 Audoux and Couvreur (2015) B. Audoux and A. Couvreur, arXiv preprint arXiv:1512.07081 (2015).
 Campbell (2019) E. Campbell, Quantum Science and Technology 4, 025006 (2019).
 Bombín (2015) H. Bombín, Physical Review X 5, 031043 (2015).
 JochymO’Connor (2019) T. JochymO’Connor, Quantum 3, Art (2019).
 Krishna and Poulin (2019) A. Krishna and D. Poulin, arXiv preprint arXiv:1909.07424 (2019).
 Bombin et al. (2012) H. Bombin, R. S. Andrist, M. Ohzeki, H. G. Katzgraber, and M. A. MartínDelgado, Physical Review X 2, 021004 (2012).
 Li et al. (2019) M. Li, D. Miller, M. Newman, Y. Wu, and K. R. Brown, Physical Review X 9, 021041 (2019).
 Daniel et al. (2019) A. K. Daniel, R. N. Alexander, and A. Miyake, arXiv preprint arXiv:1907.13279 (2019).
 Aliferis et al. (2009) P. Aliferis, F. Brito, D. P. DiVincenzo, J. Preskill, M. Steffen, and B. M. Terhal, New Journal of Physics 11, 013061 (2009).
 Aliferis and Preskill (2008) P. Aliferis and J. Preskill, Physical Review A 78, 052331 (2008).
 Trout et al. (2018) C. J. Trout, M. Li, M. Gutiérrez, Y. Wu, S.T. Wang, L. Duan, and K. R. Brown, New Journal of Physics 20, 043038 (2018).
 Breuckmann et al. (2017) N. P. Breuckmann, C. Vuillot, E. Campbell, A. Krishna, and B. M. Terhal, Quantum Science and Technology 2, 035007 (2017).
 Breuckmann and Terhal (2016) N. P. Breuckmann and B. M. Terhal, IEEE transactions on Information Theory 62, 3731 (2016).
 Conrad et al. (2018) J. Conrad, C. Chamberland, N. P. Breuckmann, and B. M. Terhal, Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences 376, 20170323 (2018).
 Dress (1985) A. W. Dress, in Algebraic Topology Göttingen 1984 (Springer, 1985) pp. 56–72.
 Dress and Huson (1987) A. W. Dress and D. Huson, Geometriae Dedicata 24, 295 (1987).
 Grünbaum and Shephard (1987) B. Grünbaum and G. C. Shephard, Tilings and Patterns (Freeman, 1987).
 Huson (1993) D. H. Huson, Geometriae Dedicata 47, 269 (1993).
 Balke and Huson (1996) L. Balke and D. H. Huson, Geometriae Dedicata 60, 89 (1996).
 DelgadoFriedrichs et al. (2003a) O. DelgadoFriedrichs, M. O’Keeffe, and O. M. Yaghi, Acta Crystallographica Section A 59, 22 (2003a).
 DelgadoFriedrichs et al. (1999) O. DelgadoFriedrichs, A. W. Dress, D. H. Huson, J. Klinowski, and A. L. Mackay, Nature 400, 644 (1999).
 DelgadoFriedrichs and Huson (1997) O. DelgadoFriedrichs and D. Huson, Periodica Mathematica Hungarica 34, 29 (1997).
 Thurston et al. (1997) W. P. Thurston, S. Kerckhoff, W. Floyd, and J. W. Milnor, The Geometry and Topology of ThreeManifolds (Unpublished, 1997).
 Hyde et al. (2006) S. Hyde, O. DelgadoFriedrichs, S. Ramsden, and V. Robins, Solid State Sciences 8, 740 (2006).
 Blatov et al. (2010) V. Blatov, M. O’Keeffe, and D. Proserpio, CrystEngComm 12, 44 (2010).
 Balke and Valverde (1996) L. Balke and A. Valverde, Contributions to Algebra and Geometry 37, 17 (1996).
 Bieberbach (1911) L. Bieberbach, Mathematische Annalen 70, 297 (1911).
 Bieberbach (1912) L. Bieberbach, Mathematische Annalen 72, 400 (1912).
 Hemion (1992) G. Hemion, The Classification of Knots and 3Dimensional Spaces (Oxford University Press, 1992).
 DelgadoFriedrichs et al. (2003b) O. DelgadoFriedrichs, M. O’Keeffe, and O. M. Yaghi, Acta Crystallographica Section A 59, 515 (2003b).
 (75) O. DelgadoFriedrichs, “Gavrog,” https://github.com/odf/gavrog.
 Brown et al. (2019) N. C. Brown, M. Newman, and K. R. Brown, New Journal of Physics 21, 073055 (2019).
 Chamberland et al. (2019) C. Chamberland, G. Zhu, T. J. Yoder, J. B. Hertzberg, and A. W. Cross, arXiv preprint arXiv:1907.09528 (2019).
 Momma and Izumi (2011) K. Momma and F. Izumi, Journal of Applied Crystallography 44, 1272 (2011).
 DelgadoFriedrichs and O’Keeffe (2003) O. DelgadoFriedrichs and M. O’Keeffe, Acta Crystallographica Section A: Foundations of Crystallography 59, 351 (2003).
 DelgadoFriedrichs (2003) O. DelgadoFriedrichs, in International Symposium on Graph Drawing (Springer, 2003) pp. 178–189.
 DelgadoFriedrichs and O’Keeffe (2005) O. DelgadoFriedrichs and M. O’Keeffe, Journal of Solid State Chemistry 178, 2480 (2005).
 DelgadoFriedrichs (2005) O. DelgadoFriedrichs, Discrete & Computational Geometry 33, 67 (2005).
 (83) GAP, GAP – Groups, Algorithms, and Programming, Version 4.10.2, The GAP Group (2019).
 (84) “Tinkercad,” http://www.tinkercad.com.
 O’Keeffe et al. (2008) M. O’Keeffe, M. A. Peskov, S. J. Ramsden, and O. M. Yaghi, Accounts of Chemical Research 41, 1782 (2008).
 Edmonds (2009) J. Edmonds, in Classic Papers in Combinatorics (Springer, 2009) pp. 361–379.
 Kolmogorov (2009) V. Kolmogorov, Mathematical Programming Computation 1, 43 (2009).
 Nishimori (1986) H. Nishimori, Journal of the Physical Society of Japan 55, 3305 (1986).
 Kubica et al. (2018) A. Kubica, M. E. Beverland, F. Brandão, J. Preskill, and K. M. Svore, Physical Review Letters 120, 180501 (2018).
 Andreta de Castro et al. (2019) L. Andreta de Castro, M. Newman, and K. R. Brown, (2019), In preparation.
 L’Eculier (1999) P. L’Eculier, Operations Research 47, 159 (1999).
 L’Eculier et al. (2002) P. L’Eculier, R. Simard, E. J. Chen, and W. D. Kelton, Operations Research 50, 1073 (2002).
 Barrett and Stace (2010) S. D. Barrett and T. M. Stace, Physical Review Letters 105, 200502 (2010).
 Suchara et al. (2015b) M. Suchara, A. W. Cross, and J. M. Gambetta, in Information Theory (ISIT), 2015 IEEE International Symposium on (IEEE, 2015) pp. 1119–1123.
 Rudolph (2017) T. Rudolph, APL Photonics 2, 030901 (2017).
 Tuckett et al. (2018a) D. K. Tuckett, S. D. Bartlett, and S. T. Flammia, Physical Review Letters 120, 050505 (2018a).
 Tuckett et al. (2018b) D. K. Tuckett, C. T. Chubb, S. Bravyi, S. D. Bartlett, and S. T. Flammia, arXiv preprint arXiv:1812.08186 (2018b).
 Tuckett et al. (2019) D. K. Tuckett, S. D. Bartlett, S. T. Flammia, and B. J. Brown, arXiv preprint arXiv:1907.02554 (2019).
 Xu et al. (2018) X. Xu, Q. Zhao, X. Yuan, and S. C. Benjamin, arXiv preprint arXiv:1812.01505 (2018).
 Puri et al. (2019) S. Puri, L. StJean, J. A. Gross, A. Grimm, N. Frattini, P. S. Iyer, A. Krishna, S. Touzard, L. Jiang, A. Blais, et al., arXiv preprint arXiv:1905.00450 (2019).
 Webster et al. (2015) P. Webster, S. D. Bartlett, and D. Poulin, Physical Review A 92, 062309 (2015).
 Brooks and Preskill (2013) P. Brooks and J. Preskill, Physical Review A 87, 032310 (2013).
 Bravyi et al. (2013) S. Bravyi, G. DuclosCianci, D. Poulin, and M. Suchara, Quantum Information & Computation 13, 963 (2013).
 Varnava et al. (2007) M. Varnava, D. E. Browne, and T. Rudolph, New Journal of Physics 9, 203 (2007).
 Duivenvoorden et al. (2018) K. Duivenvoorden, N. P. Breuckmann, and B. M. Terhal, IEEE Transactions on Information Theory 65, 2545 (2018).
 Breuckmann et al. (2016) N. P. Breuckmann, K. Duivenvoorden, D. Michels, and B. M. Terhal, arXiv preprint arXiv:1609.00510 (2016).
 Kubica and Preskill (2019) A. Kubica and J. Preskill, Phys. Rev. Lett. 123, 020501 (2019).
Appendix A Selfdual tilings from the RCSR database
Here, we include renderings of the tilings used in our benchmarking simulations. For completeness, we also include a summary of selfdual tilings appearing in the RCSR database. This information can be found at http://rcsr.anu.edu.au/.
bbr  cbs  cdq  cds  ctn  dia  est  ete  fsf  ftw  gsi  hms  hst  
Avg. Decoder Graph Degree  4  6  5  4  3.43  4  5  3.33  5  6  4  4  3.33 
Avg. Graph State Degree  7.5  4  4.8  7  8  6  5.375  10.33  5  4  7.5  6  10.6 
lcy  mab  mcf  mco  mgc  pcu  pte  pyr  qtz  rtw  sda  smt  srs  
Avg. Decoder Graph Degree  6  6  4  3.33  8  6  4.33  4  6  4.66  6  6  3 
Avg. Graph State Degree  5  5.33  6  8  4  4  5.14  6  4.66  5.42  4.33  4.66  10 
sto  svn  swl  sxd  tfa  tfc  ths  tph  ttv  unj  vck  vtx  bst  
Avg. Decoder Graph Degree  3.33  7  7  6  3.33  3.33  3  6.86  4.29  4  7  5.33  12 
Avg. Graph State Degree  8.8  4.29  3.86  4.33  8  8.8  10.66  4  4.8  6.5  3.71  4.5  3 