# A graph-based formalism for surface codes and twists

Rahul Sarkar111Institute for Computational & Mathematical Engineering,
Stanford University, Stanford, CA, USA<EMAIL_ADDRESS>and Theodore J.
Yoder222IBM T.J. Watson Research Center, Yorktown Heights, NY, USA.
<EMAIL_ADDRESS>
###### Abstract

Twist defects in surface codes can be used to encode more logical qubits,
improve the code rate, and implement logical gates. In this work we provide a
rigorous formalism for constructing surface codes with twists generalizing the
well-defined homological formalism introduced by Kitaev for describing CSS
surface codes. In particular, we associate a surface code to _any_ graph $G$
embedded on _any_ 2D-manifold, in such a way that (1) qubits are associated to
the vertices of the graph, (2) stabilizers are associated to faces, (3) twist
defects are associated to odd-degree vertices. In this way, we are able to
reproduce the variety of surface codes, with and without twists, in the
literature and produce some new examples. We also calculate and bound various
code properties such as the rate and distance in terms of topological graph
properties such as genus, systole, and face-width.

###### Contents

  1. 1 Introduction
  2. 2 Preliminaries
    1. 2.1 Graph embeddings
    2. 2.2 Oriented rotation systems
    3. 2.3 General rotation systems
    4. 2.4 Dual graph and checkerboardability
    5. 2.5 Homology of graph embeddings
    6. 2.6 Covering maps and contractible loops
  3. 3 Majorana and qubit surface codes from rotation systems
    1. 3.1 Majorana operators and codes
    2. 3.2 Majorana surface codes defined on embedded graphs
    3. 3.3 From Majorana surface codes to qubit surface codes
    4. 3.4 Relation to homological surface codes
  4. 4 Locating logical operators
    1. 4.1 Checkerboardability with defects
    2. 4.2 Characterizing logical operators as cycles in the decoding graph
    3. 4.3 Doubled graphs
    4. 4.4 Face-width as a lower-bound on code distance
    5. 4.5 Logical operators from trails in the original graph
  5. 5 Code examples
    1. 5.1 Square lattice toric codes
    2. 5.2 Rotated toric codes
    3. 5.3 New hyperbolic codes
    4. 5.4 Two more ways to generalize the triangle code
  6. 6 Open problems
  7. A Graph embeddings from oriented rotation systems
  8. B Paulis with arbitrary commutation patterns and CALs
    1. B.1 Basic definitions
    2. B.2 Constructing a list of Paulis given desired commutation relations
    3. B.3 Properties of cyclically anticommuting lists of Paulis
  9. C Equivalence of Majorana and qubit surface codes
  10. D A more general family of cyclic qubit stabilizer codes
    1. D.1 A four parameter cyclic code family
    2. D.2 A two parameter cyclic code family
  11. E Embedding of the medial graph
  12. F Using GAP to find normal subgroups

##  1 Introduction

Since their introduction [1], surface codes have been an essential tool in the
quantum engineer’s fight against noise, combining a high threshold with
relatively simple 2-dimensional qubit connectivity. These codes also exemplify
a surprising connection between quantum error-correction and topology. In
effect, one associates a CSS quantum code to a graph embedded on a
2-dimensional manifold by assigning qubits to edges and stabilizers to
vertices and faces of the graph. The homology of the surface guarantees that
the stabilizers commute and that non-trivial logical operators correspond to
homologically non-trivial cycles in the graph or its dual.

However, the simple 2-dimensional connectivity comes with a drawback. Like all
2-dimensional stabilizer codes, surface codes are limited by the Bravyi-
Poulin-Terhal bound [2], which says that a code family that uses $N$ qubits to
encode $K$ qubits with distance $D$ must satisfy $KD^{2}\leq cN$ for some
constant $c$. For instance, the rotated surface code [3] achieves $c=1$ in the
plane, while the square-lattice toric code [1] achieves $c=1$ on the torus.

Motivated in part by improving the constant $c$, twist defects have been
introduced to surface codes [4, 5]. Fundamentally, twist defects are local
regions where Pauli errors can create (or destroy) unpaired excitations of
both types, $X$ and $Z$, say, whereas elsewhere in the code the parities of
these excitations are conserved. However, twist defects appear in several
quantitatively different forms. For example, sometimes weight-five stabilizers
are involved [4, 5], sometimes only weight-four as in the usual surface code
[6], and sometimes twists are embodied by a combination of weight-two and
weight-six stabilizers [7]. Qualitatively, these defects behave the same, with
$M$ defects adding $(M-2)/2$ logical qubits to the code and with non-trivial
logical operators forming paths between pairs of defects.

Clever placement and implementation of twist defects can lead to savings in
qubit count by producing codes with $N=cKD^{2}$ for relatively small constant
$c$. For instance, in the plane, $c=3/4$ [6] and $c=1/2$ [8] have been
achieved for surface codes, and $c=3/8$ for color codes [8]. However, there is
not a rigorous formalism for constructing surface codes with twists comparable
to the well-defined homological formalism introduced by Kitaev for describing
CSS surface codes [1]. Such a formalism would be helpful for looking for
better surface codes with perhaps even smaller constants $c$.

Our main goal in this work is to introduce such a formalism, capable of
describing surface codes with and without twist defects in a unified manner.
Again we associate a code to an embedded graph, but find it most natural to do
this in a different way than the homological formalism described above.
Instead of placing qubits on edges, we place them on vertices. Only faces of
the graph support stabilizers in our description, and odd-degree vertices act
as the twist defects. Placing qubits on vertices is not a substantially new
idea (for instance, appearing for the degree-4 case in [3]), but we go beyond
prior works in applying the construction to arbitrary embedded graphs,
yielding new codes with improved parameters.

Let us briefly summarize the main results of each section. Section 2
rigorously defines embedded graphs and related notation used throughout the
paper. Our description of choice for an embedded graph is via a rotation
system. Effectively, this is a combinatoric description of the embedded graph,
which abstracts away unnecessary details about how exactly the graph is drawn
on the surface. What remains is just the adjacency of the graph components
(e.g. vertices, edges, and faces). The rotation system description is very
similar to the formalisms used for hyperbolic codes in, for example, [9, 10]
but slightly more general as it applies to non-regular graphs. Although the
rotation system description may be overkill for individual codes, for which a
picture may suffice, we believe that creating a more comprehensive theory of
surface codes deserves such a precise framework. Having the rotation system
description is also convenient for computer-assisted searches for codes, as we
do for hyperbolic manifolds in Section 5.3. We identify a key property of
embedded graphs called checkerboardability, which means one can two-color
faces of the graph such that adjacent faces are differently colored.

In Section 3, we give our surface code construction. We actually provide two
equivalent descriptions, one using Majoranas to encode qubits and one using
qubits to encode qubits. The Majorana description is similar to that used to
describe surface codes in [11, 12, 13]. We place two Majoranas on each edge
and a single Majorana at each odd-degree vertex. Stabilizers, products of
Majoranas, are associated to faces and vertices of the graph. Identifying
qubit subspaces at the vertices turns the Majorana code into a qubit surface
code with qubits on the vertices, as we described above. A significant result
in this section is the computation of the number of encoded qubits in Theorem
3.3. This depends on the genus of the surface, its orientability, the number
of odd-degree vertices, and the checkerboardability of the surface. Finally,
we note that, when the graph is checkerboardable, Kitaev’s homological
construction, applied to a different but related graph, can be used to
describe the same code.

Our focus in Section 4 is on finding logical operators and bounding the code
distance. A key idea here is to derive a “decoding” graph from the original
embedded graph. Vertices in the decoding graph represent stabilizers, edges
represent Pauli errors, and cycles represent logical operators. In principle,
one can perform perfect matching in the decoding graph to recover from errors,
though for non-checkerboardable codes this may not succeed in achieving the
code distance. Like Kitaev’s homological construction, we wish to associate
homologically non-trivial cycles to non-trivial logical operators. This is
easily done in the checkerboardable case of our construction. However, in the
non-checkerboardable case, the decoding graph might not embed in the same
manifold as the original graph. In this case, we instead find a way to embed
the decoding graph in a manifold of potentially higher genus in such a way
that this correspondence of homological and logical non-triviality is
maintained. Bounds on the code distance follow in terms of lengths of cycles
in the decoding graph.

Finally, Section 5, we provide several code families that serve as examples of
our construction. The first family, square-lattice codes on the torus [11],
serves as a familiar introduction. The second family rotates the square-
lattice on the torus to get codes like those in [14]. Included in this case is
a family of cyclic codes that contains the famous 5-qubit quantum code as a
member. The third family consists of hyperbolic codes defined using regular
tilings of high genus surfaces. Because we are using our qubit-on-vertices
definition of surface codes, this leads to new codes, different from those in,
for instance [15, 16]. In these first examples, we take pains to calculate the
code distances formally. A final section of examples consists of a planar code
family generalizing the triangle code [6] and an embedding of stellated codes
[8] on higher genus surfaces. In these cases, we do not formally prove the
code distances but provide conjectures. We believe that stellated codes on
higher genus surfaces provide the smallest known constant $c$, approaching
$1/4$, for codes with stabilizers that are mostly weight four and vanishingly
many stabilizers of weight five.

##  2 Preliminaries

In this section, we first provide an introduction to the combinatorial
description of graph embeddings (also called maps) on closed surfaces. We
refer to this description as a rotation system, following terminology in [17,
18, 19]. We recall that a closed surface is a 2-dimensional, compact, and
connected topological manifold without boundary (see [20, 21] for an
introduction to topological manifolds), and henceforth we simply say a
manifold to mean a closed surface (unless specified otherwise). All manifolds
admit a unique smooth structure up to diffeomorphisms [22], and by the closed
surface classification theorem [23, 20, 24], each manifold is homeomorphic to
a space of one of three types — (a) Type I: $\mathbb{S}^{2}$, (b) Type II: a
connected sum of one or more copies of $\mathbb{T}^{2}$, (c) Type III: a
connected sum of one or more copies of $\mathbb{RP}^{2}$. This greatly
simplifies the picture when we physically think of “drawing” a graph on a
manifold, more formally captured using the concept of graph embeddings. A
rotation system is simply a combinatorial description of any such graph
emdedding. To garner the most intuition, we believe that rotation systems are
most clearly presented in two parts, by first defining them for the case of
embeddings in orientable manifolds (Type I and II), and then generalizing them
to include embeddings in non-orientable manifolds (Type III). To a large
extent, the content of this section follows [17, 25, 26]. Graph theoretic
terminology appearing in this section is borrowed from [27, 28]. We also
introduce the concept of graph checkerboardability in this section, and
briefly discuss the notion of $\mathbb{F}_{2}$-homology of a graph embedding.

###  2.1 Graph embeddings

Let us first cover graphs and their embeddings. A graph $G(V,E)$ is a
collection of vertices $V$ and edges $E$. We will mostly deal with finite
graphs, i.e. $1\leq|V|<\infty$, and $1\leq|E|<\infty$, and explicitly state
when this assumption is violated. The entry in a vertex-edge adjacency matrix
$a_{ve}$ indicates whether a vertex $v$ and an edge $e$ are adjacent
($a_{ve}=1$) or not ($a_{ve}=0$), where $a\in\mathbb{F}^{|V|\times|E|}$. An
edge adjacent to a single vertex is a loop. If an edge is not a loop, then it
is adjacent to exactly two vertices. The degree of a vertex $v$ is denoted
$\text{deg}(v)$, and it is the number of edges adjacent to it, with loops
counted with multiplicity two. We assume in this section that $G$ is a
connected graph.

A graph embedding requires that we actually draw the graph on a manifold
$\mathcal{M}$. There may be multiple ways to do this even for a single graph
and a fixed manifold. Generally, this drawing procedure is described by a
graph embedding map $\Gamma:V\cup E\rightarrow\mathcal{M}$ that assigns unique
points in $\mathcal{M}$ to each $v\in V$, and arcs in $\mathcal{M}$ to each
$e\in E$. If $e\in E$ is not a loop adjacent to distinct vertices $v_{1}$ and
$v_{2}$, then the arc assigned to it must be the image of a homeomorphism
$\gamma:[0,1]\rightarrow\mathcal{M}$, with endpoints $\gamma(0)=\Gamma(v_{1})$
and $\gamma(1)=\Gamma(v_{2})$. If $e$ is a loop adjacent to a vertex $v$, then
the arc assigned to it is the image of a homeomorphism
$\gamma:\mathbb{S}^{1}\rightarrow\mathcal{M}$, with both endpoints given by
$\gamma(0)=\Gamma(v)$ (here $\mathbb{S}^{1}$ is parameterized in polar
coordinates). Moreover, two arcs may not intersect except possibly at their
endpoints.

The set $\mathcal{F}=\mathcal{M}\setminus\Gamma(E)$ is a collection of regions
called the faces of the embedding, and two points $p,q\in\mathcal{F}$ belong
to the same face if and only if there exists a continuous map
$\gamma^{\prime}:[0,1]\rightarrow\mathcal{F}$ such that
$\gamma^{\prime}(0)=p$, and $\gamma^{\prime}(1)=q$. We say that an embedding
of $G$ is a 2-cell embedding if and only if every face is homeomorphic to the
open disc $\mathcal{B}(0,1)=\\{(x,y)\in\mathbb{R}^{2}:x^{2}+y^{2}<1\\}$. If
the closure of every face is homeomorphic to the closed disc
$\overline{\mathcal{B}(0,1)}$, and the set difference of the closure of the
face and the face itself is homeomorphic to the circle $\mathbb{S}^{1}$, we
say that it is a closed 2-cell embedding or a strong embedding. Every
connected graph admits a 2-cell embedding in some orientable manifold (see
Theorem A.16. in [19]), and also in some non-orientable manifold (see Theorem
3.4.3 in [28]). One can see a graph (a square lattice) embedded in the torus
in Fig. 1(a).

###  2.2 Oriented rotation systems

The goal in this subsection is to establish an equivalence between graphs
embedded in orientable manifolds and a combinatorial object called an oriented
rotation system. It is easier to see this equivalence in one direction — start
with an embedded graph in an orientable manifold and develop the oriented
rotation system description. This direction we sketch here. A more formal
argument and the other direction are covered in Appendix A.

The description of a graph embedding in the previous section requires a
variety of homeomorphisms whose exact details, topologically speaking, do not
matter. The oriented rotation system description dispenses with those details
by breaking the embedded graph down into half-edges, two for every edge, and
describing vertices, edges, and faces of the graph embedding as sets of these
half-edges. The precise definition is as follows.

######  Definition 2.1.

An oriented rotation system is a triple $R_{O}=(H_{O},\nu,\epsilon)$, where
$H_{O}$ is a finite set of half-edges (sometimes called darts), and two
permutations $\nu:H_{O}\rightarrow H_{O}$ and $\epsilon:H_{O}\rightarrow
H_{O}$ satisfying the additional properties

  1. (i)

$\epsilon$ is a fixed-point-free involution, meaning $\epsilon^{2}=\text{Id}$,
and $\epsilon h\neq h$ for all $h\in H_{O}$.

  2. (ii)

The free group $\langle\nu,\epsilon\rangle$ generated by $\nu$ and $\epsilon$,
acts transitively on $H_{O}$. This means that for all $h,h^{\prime}\in H_{O}$,
one can find $\kappa\in\langle\nu,\epsilon\rangle$ such that $\kappa
h=h^{\prime}$.

We now define the three sets

$\begin{split}V&=\\{v\subseteq H_{O}:v\text{ is an orbit of the free group
}\langle\nu\rangle\\},\\\ E&=\\{e\subseteq H_{O}:e\text{ is an orbit of the
free group }\langle\epsilon\rangle\\},\\\ F&=\\{f\subseteq H_{O}:f\text{ is an
orbit of the free group }\langle\nu\epsilon\rangle\\}.\end{split}$ (1)

We call elements of these sets the vertices, edges, and faces of the oriented
rotation system, respectively. So, condition (i) ensures edges are sets of
exactly two half-edges, and thus $|H_{O}|$ is even, while condition (ii)
ensures the graph is connected.

Thus given an embedded graph $G(V,E)$ in an oriented manifold $\mathcal{M}$,
to get the oriented rotation system $(H_{O},\nu,\epsilon)$ corresponding to
it, we first create a set of half-edges $H_{O}$ with each edge in $E$
contributing two half-edges. Let $e\in E$ with corresponding half-edges
$h_{e},h^{\prime}_{e}\in H_{O}$. The permutation $\epsilon$ is defined so that
$\epsilon h_{e}=h^{\prime}_{e}$, and $\epsilon h^{\prime}_{e}=h_{e}$ for every
$e\in E$, and note that property (i) of Definition 2.1 is satisfied. If $e$ is
adjacent to vertices $v,v^{\prime}\in V$ ($v=v^{\prime}$ if $e$ is a loop), we
assign $h_{e}$ and $h^{\prime}_{e}$ to $v$ and $v^{\prime}$ respectively. Thus
each vertex $v$ gets assigned exactly $\text{deg}(v)$ half-edges, and
conversely each half-edge in $H_{O}$ is assigned to exactly one vertex in $V$.
This partitions $H_{O}$ into disjoint subsets indexed by the vertices. Now
choose a smoothly varying outward normal on $\mathcal{M}$, which is possible
since it is orientable, fix a vertex $v\in V$, and let $(H_{O})_{v}$ be the
half-edges assigned to it. We can enumerate the edges adjacent to $v$ in
counterclockwise order with respect to the outward normal, where an edge
appears twice successively in this enumeration if it is a loop. Then replacing
each edge in this ordering by the corresponding half-edge that it contributes
to $v$, gives a counterclockwise ordering of $(H_{O})_{v}$. The permutation
$\nu$ for $(H_{O})_{v}$ is defined to be the cyclic permutation given by this
counterclockwise ordering, and repeating this at every vertex completely
specifies $\nu$. It follows easily that property (ii) of Definition 2.1 is
satisfied if $G$ is connected. This completes the construction of the oriented
rotation system $(H_{O},\nu,\epsilon)$. See Fig. 1(a) for an example. However,
the description we just provided fails to capture graph embeddings in non-
orientable manifolds, because in that case we cannot choose a smoothly varying
outward normal.

Figure 1: (a) A graph embedded onto the torus and its oriented rotation
system. An orbit of $\langle\nu\rangle$, an orbit of $\langle\epsilon\rangle$,
and two orbits of $\langle\nu\epsilon\rangle$ are shown. These correspond to
an edge, a vertex, and two faces of the graph embedding. (b) We show a graph
embedded on the projective plane. A general rotation system is defined by a
set of flags (gray triangles) and three permutations: $\lambda$ swaps flags
along the same side of an edge, $\rho$ swaps them within a face adjacent to a
vertex, and $\tau$ swaps them across an edge.

###  2.3 General rotation systems

The rotation system description can be generalized to cover non-orientable
manifolds as well. To do so, we must effectively introduce an orientation to
half-edges. Thus, instead of half-edges, we use a set of flags $H$. Fig. 1(b)
makes it clear how flags can be visualized in the embedding, with two flags
per half-edge, one on either “side”. The formal definition of a general
rotation system is as follows.

######  Definition 2.2.

A general rotation system is a quadruple $R=(H,\lambda,\rho,\tau)$, where $H$
is a finite set of flags, and $\lambda,\rho,\tau$ are permutations on $H$
satisfying the properties

  1. (i)

$\lambda,\rho$, and $\tau$ are fixed-point-free involutions.

  2. (ii)

$\lambda\tau=\tau\lambda$, or equivalently, $\lambda\tau$ is an involution.

  3. (iii)

the monodromy group $M(R)=\langle\lambda,\rho,\tau\rangle$ acts transitively
on $H$.

The involutions $\lambda,\rho,\tau$ permute flags as shown in Fig. 1(b). We
define vertices, edges, and faces as orbits of $\langle\rho,\tau\rangle$,
$\langle\lambda,\tau\rangle$, and $\langle\rho,\lambda\rangle$ respectively.
From properties (i) and (ii) of Definition 2.2, orbits of
$\langle\lambda,\tau\rangle$ have the form $\\{h,\lambda h,\tau h,\lambda\tau
h:h\in H\\}$, i.e. are exactly of size four, and so $|H|\equiv 0\pmod{4}$.
Moreover, one deduces from property (i) that the orbits of
$\langle\rho,\lambda\rangle$ and $\langle\rho,\tau\rangle$ have even sizes,
with the canonical form of an orbit of size $2n+2$ given by $\\{h,\lambda
h,\rho\lambda h,\lambda\rho\lambda h,\dots,(\lambda\rho)^{n}\lambda h:h\in
H\\}$, and $\\{h,\tau h,\rho\tau h,\tau\rho\tau h,\dots(\tau\rho)^{n}\tau
h:h\in H\\}$ respectively. The sets of vertices, edges, and faces, which we
denote $V$, $E$, and $F$ respectively, define a graph embedding and satisfy
Euler’s formula

$\chi=|V|-|E|+|F|,$ (2)

where $\chi$ is the Euler characteristic of the manifold, i.e. if $g$ is the
manifold’s genus (orientable or non-orientable), then $\chi=2-2g$ if the
manifold is orientable, and $\chi=2-g$ if it is non-orientable. Note that
property (iii) ensures that $G$ is a connected graph. We will write $G(V,E,F)$
to denote such an embedded graph, as compared to $G(V,E)$ which only denotes
the graph without the embedding.

The orbits of the free group $\langle\tau\rangle$ are exactly the half-edges,
and additionally we define _sectors_ as the orbits of the free group
$\langle\rho\rangle$. As $\tau$ and $\rho$ are fixed-point-free involutions,
these orbits are just two flags each. We denote a half-edge as
$[h]_{\tau}=\\{h,\tau h\\}$, and a sector as $[h]_{\rho}=\\{h,\rho h\\}$.

Definition 2.2 generalizes Definition 2.1. Suppose we have an oriented
rotation system $R_{O}=(H_{O},\nu,\epsilon)$. There is a corresponding general
rotation system $R=(H,\lambda,\rho,\tau)$ where $H=H_{O}\times\\{1,-1\\}$ and
for $(h,i)\in H$,

$\lambda(h,i)=(\epsilon
h,-i),\quad\rho(h,i)=(\nu^{i}x,-i),\quad\tau(h,i)=(h,-i).$ (3)

This definition ensures that the general rotation system represents the same
embedded graph as the given oriented rotation system.

A general rotation system $(H,\lambda,\rho,\tau)$ describes a graph embedded
in an orientable manifold if and only if $H$ can be partitioned into two sets
$H_{\pm 1}$ such that $\lambda$, $\rho$, and $\tau$ each map elements of
either set to elements of the other set. Otherwise, the graph is embedded in a
non-orientable manifold. If the manifold is orientable, there are at least two
oriented rotation systems describing the same graph embedding, on the same set
of half-edges. Take $H_{O}=H/\tau$ and let $[h]_{\tau}=\\{h,\tau h\\}\in
H_{O}$ be a generic half-edge. Define $\nu[h]_{\tau}=[\rho\tau h]_{\tau}$,
$\nu^{\prime}[h]_{\tau}=[\tau\rho h]_{\tau}$, and
$\epsilon[h]_{\tau}=[\lambda\tau h]_{\tau}$. Then, both $(H_{O},\nu,\epsilon)$
and $(H_{O},\nu^{\prime},\epsilon)$ are oriented rotation systems for the same
embedded graph.

Adjacency is an important concept for graphs and their components. Using the
general rotation system description, flags are the primitives, and we say a
flag is adjacent to a vertex, edge, or face $x\in V\cup E\cup F$, if it is
contained in $x$. We define adjacency matrices in terms of flags. The vertex-
flag adjacency matrix $A\in\mathbb{F}_{2}^{|V|\times|H|}$ has $A_{vh}=1$ if
and only if $h\in v$. Similarly define an edge-flag adjacency matrix
$B\in\mathbb{F}_{2}^{|E|\times|H|}$, and a face-flag adjacency matrix
$C\in\mathbb{F}_{2}^{|F|\times|H|}$. Although flags are primitives, we can
also define adjacency of the more typical graph components. For example, we
say that a vertex $v\in V$ and an edge $e\in E$ are adjacent if $v\cap
e\neq\emptyset$, and $a_{ve}=1$ if and only if $v$ and $e$ are adjacent.
Likewise, adjacency of edges and faces, and of vertices and faces can be
defined by non-trivial intersection. Note that each edge in an embedded graph
is adjacent to at least one and at most two faces. The degree of a vertex $v$
is half the number of flags it is adjacent to, $\text{deg}(v)=|v|/2$, and this
definition coincides with the one in Subsection 2.1. We also say that two
vertices (resp. two faces) are adjacent, if there exists an edge adjacent to
both vertices (resp. both faces).

###  2.4 Dual graph and checkerboardability

If an embedded graph $G(V,E,F)$ is described by the general rotation system
$(H,\lambda,\rho,\tau)$, then the embedded dual graph
$\overline{G}(\overline{V},\overline{E},\overline{F})$ of $G$ is defined by
the general rotation system $(H,\tau,\rho,\lambda)$, i.e. by simply exchanging
the permutations $\lambda$ and $\tau$. This implies that $\overline{G}$ has a
vertex (resp. face) for every face (resp. vertex) of $G$, while
$|E|=|\overline{E}|$, and we conclude that the Euler characteristic of $G$ and
$\overline{G}$ are the same. Note also that the graph $\overline{G}$ is
connected (by properties of a general rotation system). Moreover
$\overline{G}$ defines an embedding in an orientable manifold if and only if
$G$ does too — thus the graphs $G$ and $\overline{G}$ are embedded in the same
manifold. The edges of $\overline{G}$ have a natural interpretation: for every
edge $e\in E$ adjacent to faces $f,f^{\prime}\in F$, not necessarily distinct,
there is an edge $\overline{e}\in\overline{E}$ between the vertices of
$\overline{G}$ corresponding to $f$ and $f^{\prime}$ (in particular if
$f=f^{\prime}$ then $\overline{e}$ is a loop). The dual of the graph
$\overline{G}$ is isomorphic to the graph $G$. There are several more
modifications of a graph $G$ that we use in the paper. In Table 1, we list
these and the sections where they are defined.

Name | Original | Dual | Medial | Decoding | Doubled | Face-vertex
---|---|---|---|---|---|---
Notation | $G$ | $\overline{G}$ | $\widetilde{G}$ | $G_{\text{dec}}$ | $G^{2}$ | $G_{\text{fv}}$
Section | 2.1 | 2.4 | 3.4 | 4.2 | 4.3 | 4.4
Table 1: Embedded graph $G$ and the derived graphs used in this paper.

Before proceeding any further, given a graph embedding $G(V,E,F)$, we define
the face-edge adjacency matrix
$\Phi=\frac{1}{2}CB^{\top}\in\mathbb{F}_{2}^{|F|\times|E|}$ (with this matrix
multiplication performed over the integers, then reduced modulo two), which
captures the adjacency of the faces and edges of $G$. It is worth pointing out
the structure of the matrix $\Phi$. First note that each column of $B^{\top}$
contains exactly four non-zeros, as each edge $e\in E$ is a set of four flags.
Now there are two cases: (i) the two sides of $e$ belong to distinct faces
$f,f^{\prime}\in F$, and (ii) $e$ is surrounded by a single face on both
sides, i.e. $e$ is a subset of that face. In the former case,
$\Phi_{fe}=\Phi_{f^{\prime}e}=1$ are the only non-zero entries of the column
of $\Phi$ corresponding to $e$, while in the latter case $\Phi_{fe}=0$ for all
$f\in F$.

We now discuss an important property of embedded graphs from the perspective
of quantum codes, called checkerboardability.

######  Definition 2.3.

A graph embedding $G$ is checkerboardable if the dual graph $\overline{G}$ is
bipartite.

An equivalent, and a more intuitive way of stating this definition is the
following lemma.

######  Lemma 2.1.

A graph embedding $G(V,E,F)$ described by a general rotation system
$(H,\lambda,\rho,\tau)$, is checkerboardable if and only if the faces of $G$
can be two-colored, such that for every flag $h\in H$, $h$ and $\tau h$ are
differently colored.

  * Proof.

One direction of this equivalence is clear. Suppose $\overline{G}$ is
bipartite, and we color the two disjoint vertex sets of $\overline{G}$,
corresponding to the bipartition differently. Using the correspondence between
the faces of $G$ and vertices of $\overline{G}$, we get a two-coloring of $F$,
and hence of the flags $H$. Now pick any flag $h\in H$, and let $h\in e\in E$.
Then $h,\tau h$ must belong to distinct faces $f,f^{\prime}\in F$
respectively, otherwise if $e$ is adjacent to a single face then
$\overline{G}$ will contain a loop (as mentioned above), and hence cannot be
bipartite. Since $f$ and $f^{\prime}$ are both adjacent to $e$, they must be
differently colored. For the converse, suppose we are given a two-coloring of
$F$ (which now induces a coloring of the vertices of $\overline{G}$) such that
$h$, and $\tau h$ are differently colored for all $h\in H$. Consider
$\overline{G}(\overline{V},\overline{E})$, and partition the vertices as
$\overline{V}=\overline{V}_{w}\sqcup\overline{V}_{b}$, where each disjoint
partition contains all vertices of $\overline{G}$ of a single color. Assume
that $\overline{G}$ is not bipartite with this bipartition. If $\overline{G}$
has a loop then there exists $e\in E$ adjacent to a single face. If
$\overline{G}$ has no loop, then either $\overline{V}_{w}$ or
$\overline{V}_{b}$ is not an independent set; so there exist distinct faces
$f,f^{\prime}\in F$ of the same color, adjacent to an edge $e\in E$. In both
cases, all four flags of $e$ have the same color which is a contradiction.
Thus $\overline{G}$ is bipartite. ∎

There are numerous other equivalent statements of checkerboardability. We give
two more below that we find useful. Note that the only permutation out of
$\lambda$, $\rho$, $\tau$ that moves flags across edges of the graph is
$\tau$. Therefore using Lemma 2.1, we have the following:

######  Lemma 2.2.

A graph embedding $G(V,E,F)$ described by the general rotation system
$R=(H,\lambda,\rho,\tau)$, is checkerboardable if and only if we can partition
$H$ into two disjoint sets $H_{w}$ and $H_{b}$ such that (i) $\lambda$ and
$\rho$ map both sets to themselves, and (ii) $\tau$ maps elements of either
set to the other set.

  * Proof.

Suppose first that $G$ is checkerboardable. Then there is a two-coloring of
the faces of $F$ such that for every $h\in H$, $h$ and $\tau h$ are
differently colored. Defining $H_{w}$ and $H_{b}$ to be the sets of flags of
each color then shows that these sets have the required properties (i) and
(ii), proving the only if direction. Now assume that $H$ can be partitioned
into disjoint sets $H_{w}$ and $H_{b}$ satisfying the two properties. If $f\in
F$, by property (i) all flags of $f$ must belong to either $H_{w}$ or $H_{b}$.
Let us color all flags of $H_{w}$ and $H_{b}$ black and white respectively,
which induces a two-coloring of all the faces of $G$. Property (ii) now
implies that for every $h\in H$, $h$ and $\tau h$ are differently colored,
proving that $G$ is checkerboardable. ∎

In this paper we adopt the notation that $\vec{1}$ and $\vec{0}$ are the row
vectors of all 1s and all 0s respectively. The arguments above show that in a
checkerboard coloring, each edge is adjacent to exactly one face of each color
(white and black, say). Thus, checkerboardability implies the existence of a
vector $x\in\mathbb{F}_{2}^{|F|}$ (e.g. $x_{f}=1$ if and only if face $f$ is
colored white) such that $x\Phi=\vec{1}$. In fact we also have that
$(\vec{1}-x)\Phi=\vec{1}$, and these are the only two vectors with this
property. This is summarized in the following lemma.

######  Lemma 2.3.

Let $G(V,E,F)$ be a graph embedding described by the general rotation system
$(H,\lambda,\rho,\tau)$, and let $\Phi$ be its face-edge adjacency matrix.
Then

  1. (a)

$G$ is checkerboardable if there exists $x\in\mathbb{F}_{2}^{|F|}$ such that
$x\Phi=\vec{1}$.

  2. (b)

If $G$ is checkerboardable then the set
$\\{x\in\mathbb{F}_{2}^{|F|}:x\Phi=\vec{1}\\}$ has exactly two distinct
elements $x$ and $x^{\prime}$ (different from $\vec{0}$ and $\vec{1}$), which
satisfy $x+x^{\prime}=\vec{1}$. Thus the partitioning of the flags into the
two disjoint sets as described in Lemma 2.2 is unique.

  * Proof.

    1. (a)

Suppose there exists $x$ such that $x\Phi=\vec{1}$, and define $F_{b}=\\{f\in
F:x_{f}=1\\}$, and $F_{w}=F\setminus F_{b}$. Color the faces in $F_{b}$ and
$F_{w}$ differently. Assume for contradiction that $h\in H$ is a flag such
that $h$ and $\tau h$ have the same color, and let $h\in e\in E$. Since $h$
and $\lambda h$ belong to the same face, this implies that all four flags of
$e$ have the same color. But this implies $\Phi_{fe}=0$ for all $f\in F$ (by
properties of $\Phi$ discussed above), and so $(x\Phi)_{e}=\vec{0}$, which is
a contradiction.

    2. (b)

Assume $G$ is checkerboardable, which also implies that every column of $\Phi$
has exactly two non-zeros (or equivalently each edge $e\in E$ is adjacent to
two distinct faces), and so $\vec{1}\Phi=\vec{0}$. We already know from the
discussion in the paragraph before this lemma that there exists
$y\in\mathbb{F}_{2}^{|F|}$ such that $y\Phi=\vec{1}$. Thus we also conclude
that $(\vec{1}-y)\Phi=\vec{1}$. Now suppose there is a vector
$x\in\mathbb{F}_{2}^{|F|}$ such that $x\Phi=\vec{1}$, and define a disjoint
partition $F=F_{w}\sqcup F_{b}$ of the faces of $G$, as in the proof of (a).
This induces a disjoint vertex partition
$\overline{V}=\overline{V}_{w}\sqcup\overline{V}_{b}$ of the dual graph
$\overline{G}(\overline{V},\overline{E})$. Then combining the arguments of the
proof of (a), and the proof of the converse part of Lemma 2.1 shows that
$\overline{G}$ is bipartite. Since, $\overline{G}$ is connected, the
bipartition is unique, and so $x$ is equal to either $y$ or $\vec{1}-y$. This
proves the first part, and the second part follows from it easily.

∎

A consequence of Lemma 2.3(b) is that the checkerboard coloring of a
checkerboardable graph is essentially unique up to a permutation of the
colors. One easy way a graph can fail to be checkerboardable is if it contains
an odd-degree vertex $v$. Then, $(\rho\tau)^{\text{deg}(v)}$ would map $h\in
v$ to itself, but also because $\tau$ is applied an odd number of times, it
would map $h$ from one set, say $H_{w}$, to the other $H_{b}$ (where $H_{w}$
and $H_{b}$ are as in Lemma 2.2), a contradiction. If $g=0$ (the graph is
planar, i.e. embedded on the 2-sphere $\mathbb{S}^{2}$), we also have have the
well known converse: a planar graph embedding is checkerboardable if all
vertices have even degree.

###  2.5 Homology of graph embeddings

One topological invariant that is important for this paper (and for other
quantum codes such as homological codes) is that of $\mathbb{F}_{2}$-homology.
We introduce this concept briefly here, and refer the reader to [29] for a
more comprehensive treatment of homology. To do this in the context of
embedded graphs, we will first introduce some graph theoretic terminology.
Recall first that a trail $t$ in a graph is a sequence of vertices and edges,

$t=(v_{0},e_{1},v_{1},e_{2},\dots,v_{\ell-1},e_{\ell},v_{\ell}),$ (4)

where edge $e_{i}$ is adjacent to vertices $v_{i-1}$ and $v_{i}$, and each
edge is distinct. Trails can be open (if $v_{0}\neq v_{\ell}$) or closed (if
$v_{0}=v_{\ell}$). Open trails have endpoints $v_{0}$ and $v_{\ell}$. Closed
trails are also called cycles. Including the vertices in the specification of
a trail is standard but superfluous — a trail $t$ can be represented by a
vector $t\in\mathbb{F}_{2}^{|E|}$ such that $t_{i}=1$ if and only if the
$i^{\text{th}}$ edge of the graph is in the trail. A _path_ is a trail without
repeated vertices, except the first and last if it is a closed trail. The set
of trails generates a group $\mathcal{T}(G)$ with the group operation the
symmetric difference of the trails or, equivalently, the addition modulo two
of the vectors $y\in\mathbb{F}_{2}^{|E|}$ representing the trails. Because
each edge is a trail, $\mathcal{T}(G)$ is isomorphic to the vector space
$\mathbb{F}_{2}^{|E|}$, and a generating set of $\mathcal{T}(G)$ (or
equivalently a basis for $\mathbb{F}_{2}^{|E|}$) can be constructed to consist
only of paths.

Now let $G(V,E,F)$ be an embedded graph on a manifold, either orientable or
non-orientable. Two subgroups of $\mathcal{T}(G)$ are particularly important
in the definition of $\mathbb{F}_{2}$-homology: the subgroup $\mathcal{Z}(G)$
of all the cycles of $G$, and the subgroup $\mathcal{B}(G)$ generated by the
cycles of $G$ that are boundaries of faces of the embedded graph. Formally

$\begin{split}\mathcal{Z}(G)&=\left\langle c:c\text{ is a cycle of
}G\right\rangle,\\\ \mathcal{B}(G)&=\left\langle c:c\text{ is a cycle of
}G,\;\exists f\in F\text{ such that }\forall\;\text{edges }e\in
c,\;\Phi_{fe}=1\right\rangle.\end{split}$ (5)

We call cycles in $\mathcal{B}(G)$ homologically trivial and cycles in
$\mathcal{Z}(G)$ but not in $\mathcal{B}(G)$ homologically non-trival. The
homological systole of the graph, $\mathrm{hsys}\left({G}\right)$, is the
length of the shortest homologically non-trivial cycle. The first homology
group over $\mathbb{F}_{2}$ is the quotient group (or equivalently as the
quotient vector space)

$H_{1}(G,\mathbb{F}_{2})=\frac{\mathcal{Z}(G)}{\mathcal{B}(G)}.$ (6)

It turns out that for two different graphs $G,G^{\prime}$ embedded in the same
manifold $\mathcal{M}$, $H_{1}(G,\mathbb{F}_{2})\cong
H_{1}(G^{\prime},\mathbb{F}_{2})$. Thus in the rest of the paper, we will
simply write $H_{1}(\mathcal{M})$ for any given graph embedding $G(V,E,F)$ in
$\mathcal{M}$.

###  2.6 Covering maps and contractible loops

A cycle drawn on a manifold $\mathcal{M}$ is contractible if it can be
continuously deformed to a point and non-contractible otherwise. Homological
non-triviality implies non-contractibility [30]. However, the converse is not
true – consider for instance a cycle winding twice around a torus, which is
non-contractible but homologically trivial. Similar to the homological case,
we let $\mathrm{sys}\left({G}\right)$ denote the length of the shortest non-
contractible cycle in a graph $G$ embedded on $\mathcal{M}$ and note
$\mathrm{hsys}\left({G}\right)\geq\mathrm{sys}\left({G}\right)$. A manifold is
simply-connected if all cycles are contractible.

We say a connected manifold $\mathcal{M}^{\prime}$ is a cover of $\mathcal{M}$
if there is a map $\pi:\mathcal{M}^{\prime}\rightarrow\mathcal{M}$ such that
each open disk $U\subseteq\mathcal{M}$ has a pre-image $\pi^{-1}(U)$ that is a
union of disjoint open disks, each mapped homeomorphically onto $U$ by $\pi$
[31]. We say $\pi$ is a covering map. An $l$-fold cover is one in which
$\pi^{-1}(U)$ is a union of $l$ open disks for all $U$. It is also acceptable
to call a 2-fold cover a double cover, a 3-fold cover a triple cover, etc.

A universal cover $\mathcal{U}$ of a manifold $\mathcal{M}$ is a cover that
covers all other covers of $\mathcal{M}$. Equivalently, the universal cover of
$\mathcal{M}$ is the unique simply-connected cover of $\mathcal{M}$ (see for
instance Chapter III.4 of [31]). Compact manifolds are universally covered by
either the sphere (if $\mathcal{M}$ is the sphere or projective plane) or the
plane (otherwise).

A curve drawn in $\mathcal{M}^{\prime}$ can be projected down to $\mathcal{M}$
by applying $\pi$. Conversely, a curve $\gamma:[0,1]\rightarrow\mathcal{M}$
can be _lifted_ to $\mathcal{M}^{\prime}$. Roughly one constructs a lift by
applying $\pi^{-1}$ to $\gamma$. However, since $\pi^{-1}$ is one-to-many,
more precisely a lift of $\gamma$ is defined to be any compact, continuous
curve in $\mathcal{M}^{\prime}$ that maps to $\gamma$ when applying $\pi$.

An interesting connection presents itself between contractibility and the
universal cover. A cycle in $\mathcal{M}$ is contractible if and only if its
lift into the universal cover $\mathcal{U}$ is also a cycle. Non-contractible
curves, on the other hand, lift to curves with two distinct endpoints [30].

##  3 Majorana and qubit surface codes from rotation systems

In this section, we define our framework for constructing qubit surface codes
from rotation systems. Majorana surface codes appear as a useful intermediary
in the construction. So, building on the last section’s introduction to
rotation systems, the logical progression of this section is roughly

$\begin{array}[]{ccccc}\text{Rotation system \textbackslash graph
embedding}&\longrightarrow&\text{Majorana surface
code}&\longrightarrow&\text{Qubit surface code}\\\
\text{(Section\leavevmode\nobreak\ \ref{sec:rotation-
systems})}&&\text{(Section\leavevmode\nobreak\
\ref{subsec:maj_codes_on_graphs})}&&\text{(Section\leavevmode\nobreak\
\ref{subsec:qub_surface_codes})}\end{array}.$ (7)

Before diving into surface codes, Section 3.1 gives a quick introduction to
Majorana fermions and Majorana fermion codes in general. Afterward, in Section
3.4, we show how our framework for qubit surface codes generalizes the
standard homological definition [1], in which qubits are placed on edges,
while vertices and faces support stabilizers. We assume some familiarity of
the reader with the Pauli group, and Appendix B contains a brief recap.

###  3.1 Majorana operators and codes

The Majorana operators $\\{\gamma_{0},\gamma_{1},\dots,\gamma_{m-1}\\}$, for
$m$ even, are linear Hermitian operators acting on the fermionic Fock space
$\mathcal{H}_{m/2}=\\{|{\vec{b}}\rangle:\vec{b}\in\mathbb{F}_{2}^{m/2}\\}$, or
equivalently the $m/2$-qubit complex Hilbert space, satisfying

$\displaystyle\gamma_{i}^{2}=I,\quad\gamma_{i}\gamma_{j}=-\gamma_{j}\gamma_{i},\quad\forall\;0\leq
i<j\leq m-1.$ (8)

Eq. (8) ensures that each $\gamma_{i}$ is distinct and different from $I$. The
total number of Majorana operators is even because two Majoranas correspond to
each fermion in the system. We define a group $\mathcal{J}_{m}$ consisting of
finite products of the Majorana operators $\gamma_{i}$, and phase factor
$i=\sqrt{-1}$. By Eq. (8), this group is finite with size
$|\mathcal{J}_{m}|=2^{m+2}$. Elements of $\mathcal{J}_{m}$ either commute or
anticommute. We indicate an element of $\mathcal{J}_{m}$ uniquely by
$\eta\gamma_{a}$ where $\eta\in\\{\pm 1,\pm i\\}$, $a\in\mathbb{F}_{2}^{m}$,
and $\gamma_{a}=\prod_{i:a_{i}=1}\gamma_{i}$ (this product is ordered so that
the $\gamma_{i}$ with smaller indices are on the left, and the empty product
is defined to be equal to $I$), and the uniqueness of this representation
follows from Eq. (8). We define the support of $\eta\gamma_{a}$ to be the set
$\mathrm{supp}\left({\eta\gamma_{a}}\right):=\\{i:a_{i}=1\\}$, and its weight
$|\eta\gamma_{a}|:=|\mathrm{supp}\left({\eta\gamma_{a}}\right)|=|a|$, where
$|a|$ is the Hamming weight of $a$. The commutation of the elements of
$\mathcal{J}_{m}$ is now easily expressed as

$\gamma_{a}\gamma_{b}=(-1)^{|a||b|+a\cdot
b}\gamma_{b}\gamma_{a}=(-1)^{\xi(a,b)}\gamma_{a+b},\;\;\xi(a,b)=\sum_{i:b_{i}=1}|\\{j>i:a_{j}=1\\}|,$
(9)

where it is understood the operations “$\cdot$” and “$+$” are performed over
$\mathbb{F}_{2}$ (the quantity $|a||b|$ is computed over integers and reduced
modulo 2). These vectors are assumed to have context-appropriate length.

Particular choices of Majorana operators can be made by associating them with
appropriately chosen Pauli operators on $m/2$ qubits. This can be done in a
variety of ways. A particularly famous example is the Jordan-Wigner
transformation, which makes the association

$\displaystyle\text{JW}(\gamma_{2k})=X_{k}\prod_{i=0}^{k-1}Z_{i},\quad\text{JW}(\gamma_{2k+1})=Y_{k}\prod_{i=0}^{k-1}Z_{i},$
(10)

for all $0\leq k\leq m/2-1$, where $X_{i},Y_{i},Z_{i}$ are the Paulis acting
on qubit $i$. One can check that the Paulis associated with the Majoranas obey
Eq. (8).

Majorana fermion codes (see e.g. [32, 33]) are created by specifying a
subgroup $\mathcal{S}\leq\mathcal{J}_{m}$ to be a stabilizer. The
corresponding codespace is defined as usual to be the $+1$-eigenspace of all
stabilizers, a subspace of $\mathcal{H}_{m/2}$. We require the stabilizer be
chosen so that

  1. (i)

$\mathcal{S}$ does not contain $-I$.

  2. (ii)

Each $\gamma\in\mathcal{S}$ has even weight.

The first condition arises because we wish the codespace to be non-empty, and
the second condition is imposed because we want the stabilizer operators to be
physical, preserving fermion parity in the system. In fact, the first
condition also implies that $\mathcal{S}$ is Abelian and that all elements of
$\mathcal{S}$ are Hermitian. We note this fact and a few others in the
following lemma.

######  Lemma 3.1.

Let $\mathcal{S}$ be a subgroup of $\mathcal{J}_{m}$, and let
$\mathcal{I}\subseteq\mathcal{J}_{m}$ be non-empty, such that elements of
$\mathcal{I}$ commute and are Hermitian. Then $\langle\mathcal{I}\rangle$ is
Abelian and Hermitian, and moreover the following holds:

  1. (a)

There exists a set $\mathcal{I}^{\prime}$ formed by multiplying each element
of $\mathcal{I}$ by either $1$ or $-1$, such that
$-I\not\in\langle\mathcal{I}^{\prime}\rangle$.

  2. (b)

If $-I\not\in\mathcal{S}$, then $\mathcal{S}$ is Abelian and Hermitian.
Conversely, if $\mathcal{S}$ is Abelian and Hermitian, then either
$-I\not\in\mathcal{S}$, or $\mathcal{S}=\langle\mathcal{S}^{\prime},-I\rangle$
for some subgroup $\mathcal{S}^{\prime}$ of $\mathcal{S}$ with
$-I\not\in\mathcal{S}^{\prime}$.

  * Proof.

In this proof $\eta,\eta^{\prime},\eta^{\prime\prime}\in\\{\pm 1,\pm i\\}$,
and $a,a^{\prime},b\in\mathbb{F}_{2}^{m}$. We also note some useful facts for
this proof which follow easily from Eqs. (8,9): if $x\in\mathcal{J}_{m}$ then
(i) $x^{-1}=x^{{\dagger}}$, (ii) $x$ is either Hermitian or skew-Hermitian,
and (iii) $x^{2}\in\\{I,-I\\}$, with $x^{2}=I$ if and only if $x=x^{\dagger}$.
Also note that for any non-empty $\mathcal{J}\subseteq\mathcal{J}_{m}$ whose
elements commute and are Hermitian, if $x\in\mathcal{J}$, then by (i) and
(iii) $x=x^{\dagger}=x^{-1}$, so all elements in $\langle\mathcal{J}\rangle$
are products of elements of $\mathcal{J}$. That $\langle\mathcal{I}\rangle$ is
Abelian is clear since any element of $\langle\mathcal{I}\rangle$ is a product
of the elements in $\mathcal{I}$. To see that $\langle\mathcal{I}\rangle$ is
Hermitian, note that if $\langle\mathcal{I}\rangle\ni
x=\prod_{y\in\mathcal{I}^{\prime}}y$ for some
$\mathcal{I}^{\prime}\subseteq\mathcal{I}$, then
$x^{2}=\prod_{y\in\mathcal{I}^{\prime}}y^{2}=I$, and we conclude using (iii).

    1. (a)

Let $|\mathcal{I}|=k\geq 1$. We prove the result by induction on
$|\mathcal{I}|$. If $\mathcal{I}=\\{x\\}$ we choose
$\mathcal{I}^{\prime}=\\{x\\}$ if $x\neq-I$, else
$\mathcal{I}^{\prime}=\\{I\\}$, proving the base case. Now suppose the result
is true for all $\mathcal{I}$ such that $1\leq|\mathcal{I}|\leq r<k$. If
$|\mathcal{I}|=r+1$, pick any $x\in\mathcal{I}$ and let
$\mathcal{I}_{1}=\mathcal{I}\setminus\\{x\\}$. By the inductive hypothesis,
there exists $\mathcal{I}^{\prime}_{1}$ formed by multiplying every element of
$\mathcal{I}_{1}$ by either $1$ or $-1$, such that
$-I\not\in\langle\mathcal{I}^{\prime}_{1}\rangle$. If
$x\in\langle\mathcal{I}^{\prime}_{1}\rangle$ (resp.
$-x\in\langle\mathcal{I}^{\prime}_{1}\rangle$), choose
$\mathcal{I}^{\prime}=\mathcal{I}^{\prime}_{1}\cup\\{x\\}$ (resp.
$\mathcal{I}^{\prime}=\mathcal{I}^{\prime}_{1}\cup\\{-x\\}$) and we are done.
If $x,-x\not\in\langle\mathcal{I}^{\prime}_{1}\rangle$, choose
$\mathcal{I}^{\prime}=\mathcal{I}^{\prime}_{1}\cup\\{x\\}$. Now for
contradiction, assume $-I\in\langle\mathcal{I}^{\prime}\rangle$, so we have
$-I=zx$ for some $z\in\langle\mathcal{I}^{\prime}_{1}\rangle$, using
properties of $\mathcal{I}$ (commuting and Hermitian) and (iii). Letting
$z=\eta\gamma_{a}$, and $x=\eta^{\prime}\gamma_{a^{\prime}}$ then gives
$-I=\eta\eta^{\prime}(-1)^{\xi(a,a^{\prime})}\gamma_{a+a^{\prime}}$ using Eq.
(9), and so $a=a^{\prime}$. Combining with $z^{2}=x^{2}=I$ now gives
$\eta=-\eta^{\prime}$, or equivalently $z=-x$ which is a contradiction.

    2. (b)

First suppose $-I\not\in\mathcal{S}$. Note that if $x\in\mathcal{S}$ is not
Hermitian, then $\mathcal{S}\ni x^{2}=-I$ by (iii). Now suppose $\mathcal{S}$
is non-Abelian. Then there exists
$\eta\gamma_{a},\;\eta^{\prime}\gamma_{a^{\prime}}\in\mathcal{S}$, such that
$\gamma_{a}\gamma_{a^{\prime}}=-\gamma_{a^{\prime}}\gamma_{a}$. But this
implies that $\pm\eta^{\prime\prime}\gamma_{b}\in\mathcal{S}$, where
$\eta^{\prime\prime}\gamma_{b}=\eta\eta^{\prime}\gamma_{a}\gamma_{a^{\prime}}$,
and so both $\pm(\eta^{\prime\prime})^{2}\gamma_{b}^{2}\in\mathcal{S}$. But
one of these must be $-I$, as $\gamma_{b}^{2}=\pm I$, giving a contradiction.
For the converse assume that $-I\in\mathcal{S}$ for Hermitian and Abelian
$\mathcal{S}$. Consider the cosets of $\langle-I\rangle$ in $\mathcal{S}$, and
let $\mathcal{I}$ be the set formed by picking exactly one element from each
coset. By (a), then there exists $\mathcal{I}^{\prime}$ such that
$-I\not\in\langle\mathcal{I}^{\prime}\rangle$, and
$\mathcal{S}=\langle\langle\mathcal{I}^{\prime}\rangle,-I\rangle$.

∎

Because of Pauli representations of Majoranas like Eq. (10), it is clear that
a Majorana fermion code on $m$ Majoranas corresponds to a stabilizer code on
$m/2$ qubits. Applying the Jordan-Wigner transformation, Eq. (10), to
$\mathcal{S}$ converts it to an Abelian group of Pauli operators on $m/2$
qubits, which has size upper bounded by $2^{m/2}$. Therefore,
$|\mathcal{S}|\leq 2^{m/2}$. Thus, if $\mathcal{S}$ is generated by $m/2-k$
independent operators, then the code encodes $k$ qubits (or $2k$ Majoranas).
The centralizer $\mathcal{C}(\mathcal{S})$ of $\mathcal{S}$ is the subset of
$\mathcal{J}_{m}$ that commutes with all elements of $\mathcal{S}$. The
distance $d$ of the Majorana code is the minimum weight of an element of
$\mathcal{C}(\mathcal{S})$ that is not (up to factors of $i$) in
$\mathcal{S}$, i.e.
$d=\min\\{|\gamma|:\gamma\in\mathcal{C}(\mathcal{S})\setminus\langle\\{iI\\}\cup\mathcal{S}\rangle\\}$.

Consider, for example, a simple Majorana code, generated by just one
stabilizer:

$\mathcal{S}_{\text{even}}=\langle
i^{m/2}\gamma_{0}\gamma_{1}\dots\gamma_{m-1}\rangle.$ (11)

The phase $i^{m/2}$ guarantees this stabilizer squares to $I$ and not $-I$.
This code encodes $k=(m/2-1)$ qubits into $m$ Majoranas with distance $2$,
because the centralizer consists of all $\gamma_{a}$ with even weight. The
code $\mathcal{S}_{\text{even}}$ will play an important role in our converting
Majorana codes defined on graphs to qubit stabilizer codes defined on graphs.

###  3.2 Majorana surface codes defined on embedded graphs

Given an embedded graph $G$ given by a rotation system $R$, we define a
Majorana stabilizer code $\mathcal{S}(R)$ (or equivalently $\mathcal{S}(G)$)
by placing Majorana operators on each half-edge and each odd-degree vertex,
and associating stabilizers to each vertex and face of the embedded graph. The
formal definition is as follows.

######  Definition 3.1.

Given a rotation system $R=(H,\lambda,\rho,\tau)$ and the associated embedded
graph $G=(V,E,F)$ with $M$ odd-degree vertices, associate a single Majorana
$\gamma_{[h]_{\tau}}$ to each half-edge $[h]_{\tau}=\\{h,\tau h\\}\in H/\tau$
and a single Majorana $\bar{\gamma}_{v}$ to each odd-degree vertex in $v\in
V$. Now to every vertex $v\in V$, associate a vertex stabilizer $S_{v}$ by

$S_{v}=\bigg{\\{}\begin{array}[]{ll}i^{\text{deg}(v)/2}\left(\prod_{[h]_{\tau}\subseteq
v}\gamma_{[h]_{\tau}}\right),&\text{deg}(v)\text{ is even}\\\
i^{(\text{deg}(v)+1)/2}\left(\prod_{[h]_{\tau}\subseteq
v}\gamma_{[h]_{\tau}}\right)\bar{\gamma}_{v},&\text{deg}(v)\text{ is
odd}\end{array}$ (12)

and to every face $f\in F$, a face stabilizer $S_{f}$ by

$S_{f}=i^{|\\{h\in f:\tau h\not\in f\\}|/2}\prod_{\\{h\in f:\tau h\not\in
f\\}}\gamma_{[h]_{\tau}}.$ (13)

The order of Majoranas in these products is important. To clarify this, we
give each Majorana a unique label from $\\{0,1,\dots,m-1\\}$ satisfying
certain rules, where $m=2|E|+M$, and then the products are sorted by ascending
order in these labels. When $G$ is not checkerboardable, the labeling can be
arbitrary as long as it ensures that any two Majoranas on the same edge, e.g.
$\gamma_{[h]_{\tau}}$ and $\gamma_{[\lambda h]_{\tau}}$, have successive
labels. When $G$ is checkerboardable, the labeling should additionally ensure
that for all $0\leq j\leq m/2-1$, the Majoranas corresponding to labels $2j+1$
and $2j+2$ (evaluating the labels modulo $m$) belong to half-edges which are
subsets of the same vertex. We denote the group generated by all $S_{v}$ and
$S_{f}$ as $\mathcal{S}(R)$ (or equivalently $\mathcal{S}(G)$). The Majorana
code associated with $R$ (or $G$) has the stabilizer group $\mathcal{S}(R)$.

We note a few easy consequences of this definition. First, notice that the
total number of Majoranas is even since $M$ is, which is true because
$2|E|=\sum_{v\in V}\text{deg}(v)$. Second, notice that the vertex and the face
stabilizers have even weight, are Hermitian (since they square to $I$), and
commute. The commutation follows from Eq. (9) since supports of $S_{v}$ and
$S_{v^{\prime}}$ do not overlap for distinct $v,v^{\prime}\in V$, supports of
$S_{f}$ and $S_{f^{\prime}}$ for distinct $f,f^{\prime}\in F$ overlap if and
only if they share adjacent edges and therefore share an even number of
Majoranas, and supports of $S_{v}$ and $S_{f}$ for $v\in V$ and $f\in F$
overlap only if $v$ and $f$ are both adjacent to one or more sectors in which
case they share an even number of Majoranas (note that this holds even if $v$
and $f$ are both adjacent to any edge $e$ such that $e$ is not adjacent to any
other face).

It turns out that the Majorana labeling scheme used in Definition 3.1 ensures
that the stabilizer group $\mathcal{S}(R)$ has the property
$-I\not\in\mathcal{S}(R)$, which is formally proved below in Lemma 3.2(g), and
since each stabilizer has even weight, so does every element of
$\mathcal{S}(R)$; thus $\mathcal{S}(R)$ satisfies the two properties of a
Majorana fermion code. If a different Majorana labeling was used, or if the
products in Eqs. (12) and (13) were ordered differently then it is not
necessarily true that the first property holds, but in that case by Lemma
3.1(a) one can multiply the stabilizers by either $1$ or $-1$ and get a new
set of stabilizers for which the property would still be true. By Lemma
3.1(b), $\mathcal{S}(R)$ is Abelian and Hermitian. Two examples of Majorana
surface code stabilizers are shown in Fig. 2.

We note briefly that a labeling scheme satisfying the demands of Definition
3.1 exists in the checkerboardable case (the non-checkerboardable case is
trivial). If $G$ is checkerboardable it has no odd-degree vertices, so there
exists an Euler cycle $(e_{0},e_{1},\dots,e_{|E|-1})$ that uses all the edges
in $E$. Majoranas can be labeled in the order they are encountered by
following this cycle.

Figure 2: (a) An example section of a Majorana surface code. Majorana
operators are placed on each half-edge (blue circles) and at each odd-degree
vertex (green circles). The stabilizer associated to an even-degree vertex is
the product of Majoranas around that vertex. The stabilizer associated to an
odd-degree vertex is the product of Majoranas around that vertex and the
Majorana located at that vertex. Gray lines cordon off the Majoronas involved
in these stabilizers. The stabilizer associated to the pentagonal face is the
product of the ten blue Majoranas on edges around that face. (b) A Majorana
surface code of reference [34]. In our framework, it arises from a graph
triangulating the torus. Here opposite sides of the hexagon are identified
(directionally, as indicated by arrows) along with Majoranas on those edges. A
total of 72 Majoranas survive this identification. All stabilizers associated
to both vertices and faces are the product of six Majoranas.

The next lemma is useful to understand the dependence between the stabilizers
of the Majorana surface code.

######  Lemma 3.2.

The stabilizers of the Majorana surface code for the embedded graph $G(V,E,F)$
satisfy

  1. (a)

There is no non-empty subset $V^{\prime}\subseteq V$ such that $\prod_{v\in
V^{\prime}}S_{v}=\pm I$.

  2. (b)

There is no non-empty, proper subset $V^{\prime}\subset V$ and no subset
$F^{\prime}\subseteq F$ such that $\prod_{v\in V^{\prime}}S_{v}=\pm\prod_{f\in
F^{\prime}}S_{f}$. If there is any odd-degree vertex, then the statement holds
for all non-empty subsets $V^{\prime}\subseteq V$.

  3. (c)

If $\prod_{v\in V}S_{v}=\prod_{f\in F^{\prime}}S_{f}$ for some subset
$F^{\prime}\subseteq F$, then $G$ is checkerboardable. If $G$ is
checkerboardable then $\prod_{v\in V}S_{v}=\prod_{f\in
F^{\prime}}S_{f}=\prod_{f\in F\setminus F^{\prime}}S_{f}$ for a non-empty
proper subset $F^{\prime}\subset F$, which is determined uniquely up to taking
complements.

  4. (d)

There is no non-empty, proper subset $F^{\prime}\subset F$ such that
$\prod_{f\in F^{\prime}}S_{f}=\pm I$.

  5. (e)

$\prod_{f\in F}S_{f}=I$.

  6. (f)

$|F|=1$ if and only if there is $f\in F$ such that $S_{f}=I$.

  7. (g)

$-I\not\in\mathcal{S}(G)$.

  * Proof.

We start with an observation that is needed for proofs of (c) and (g). For any
subset $F^{\prime}\subseteq F$ and any Majorana associated to a half-edge
$\gamma_{[h]_{\tau}}$, the product $\prod_{f\in F^{\prime}}S_{f}$ either
contains both $\gamma_{[h]_{\tau}}$ and $\gamma_{[\lambda h]_{\tau}}$, or
neither of them. Thus the Majoranas appearing in the product $\prod_{f\in
F^{\prime}}S_{f}$ can be grouped in pairs labeled by edges, which allows us to
identify the product with a vector $y\in\mathbb{F}_{2}^{|E|}$, with $y_{e}=1$
for $e=\\{h,\lambda h,\tau h,\lambda\tau h\\}\in E$, if and only if both
$\gamma_{[h]_{\tau}}$ and $\gamma_{[\lambda h]_{\tau}}$ appear in the product.
It follows that $y=x\Phi$, where we recall that
$\Phi\in\mathbb{F}_{2}^{|F|\times|E|}$ is the face-edge adjacency matrix of
the graph embedding, and $x\in\mathbb{F}_{2}^{|F|}$ satisfying $x_{f}=1$ if
and only if $f\in F^{\prime}$. We now return to the proof.

    1. (a)

This follows because all the vertex stabilizers are independent from each
other, as they have disjoint supports.

    2. (b)

First assume that $V^{\prime}\subset V$ is a non-empty proper subset. We find
an edge $e\in E$ with one endpoint in $V^{\prime}$ and one in $V\setminus
V^{\prime}$ (we use connectivity of $G$ here), and notice that since face
stabilizers either include or exclude both Majoranas on an edge together,
there is no way to take a product of face stabilizers to include only one
Majorana out of the two on edge $e$. This proves the first part. Now assume
that there is at least one odd-degree vertex $v$, and suppose $\prod_{v\in
V^{\prime}}S_{v}=\prod_{f\in F^{\prime}}S_{f}$ for some non-empty subset
$V^{\prime}\subseteq V$ and some subset $F^{\prime}\subseteq F$. Then by the
first part, $V^{\prime}=V$, so the Majorana $\bar{\gamma}_{v}$ is present in
the product $\prod_{v\in V^{\prime}}S_{v}$, which is a contradiction since no
face stabilizer contains $\bar{\gamma}_{v}$.

    3. (c)

Suppose $\prod_{v\in V}S_{v}=\prod_{f\in F^{\prime}}S_{f}$ for some subset
$F^{\prime}\subseteq F$. This cannot happen if there is any odd-degree vertex,
as the product $\prod_{f\in F^{\prime}}S_{f}$ cannot contain any Majorana
associated to an odd-degree vertex. On the other hand, $\prod_{v\in V}S_{v}$
contains every Majorana associated to a half-edge, and so we can identify
$\prod_{f\in F^{\prime}}S_{f}$ with $\vec{1}\in\mathbb{F}_{2}^{|E|}$. Thus we
have $x\Phi=\vec{1}$ where $x\in\mathbb{F}_{2}^{|F|}$ satisfying $x_{f}=1$ if
and only if $f\in F^{\prime}$, so by Lemma 2.3(a) we conclude that $G$ is
checkerboardable. Now suppose that $G$ is checkerboardable. So $G$ has no odd-
degree vertices, and by Lemma 2.3(b) there exist exactly two distinct vectors
$x,x^{\prime}\in\mathbb{F}_{2}^{|F|}$ (different from $\vec{0}$ and $\vec{1}$)
such that $x\Phi=x^{\prime}\Phi=\vec{1}$, and $x+x^{\prime}=\vec{1}$. Taking
$F^{\prime}=\\{f\in F:x_{f}=1\\}$ we obtain a non-empty proper subset for
which these properties imply $\prod_{v\in V}S_{v}=\eta\prod_{f\in
F^{\prime}}S_{f}=\eta^{\prime}\prod_{f\in F\setminus F^{\prime}}S_{f}$ where
$\eta,\eta^{\prime}\in\\{\pm 1,\pm i\\}$. Now $\eta,\eta^{\prime}\neq\pm i$ as
$\mathcal{S}(G)$ is Hermitian by Lemma 3.1, so it remains to show that
$\eta,\eta^{\prime}\neq-1$. We defer this remaining part to the proof of (g).

    4. (d)

This is similar to (b), but for the dual graph embedding $\overline{G}$. Find
a face $f^{\prime}\in F^{\prime}$ that shares an adjacent edge $e\in E$ with a
face $f\not\in F^{\prime}$ (this uses connectivity of the dual graph), and
notice that the Majoranas on edge $e$ appear just once in the product, which
can therefore not be identity.

    5. (e)

Note that each Majorana $\gamma_{[h]_{\tau}}$ is included in either two face
stabilizers (if $h$ and $\tau h$ are in different faces) or none (if $h$ and
$\tau h$ are in the same face). Moreover, Majoranas associated to odd-degree
vertices are not included in any face stabilizer. Also note that for any flag
$h\in H$, $i\gamma_{[h]_{\tau}}\gamma_{[\lambda h]_{\tau}}$ commutes with all
Majoranas different from $\gamma_{[h]_{\tau}}$ and $\gamma_{[\lambda
h]_{\tau}}$, and squares to $I$. Using these facts, a straightforward
calculation shows that $\prod_{f\in F}S_{f}=I$.

    6. (f)

This follows directly from (d) and (e).

    7. (g)

Suppose this is false. Then $-I=\prod_{v\in V}S_{v}\prod_{f\in
F^{\prime}}S_{f}$ for some non-empty proper subset $F^{\prime}\subset F$, as
all other cases are ruled out by (a), (b), (d), (e), or equivalently
$\prod_{v\in V}S_{v}=-\prod_{f\in F^{\prime}}S_{f}$. By the same
identification argument used in (c), we conclude that $G$ is checkerboardable.
We will now show that in fact $\prod_{v\in V}S_{v}=\prod_{f\in
F^{\prime}}S_{f}$, which will complete the proof. Note that this also finishes
the remaining part of the proof of (c), because if either $\eta=-1$ or
$\eta^{\prime}=-1$, then $-I\in\mathcal{S}(G)$.

Since $G$ is checkerboardable, it has no odd-degree vertices, and each edge in
$E$ is adjacent to exactly one face in $F^{\prime}$. Thus let us identify the
Majoranas by their labels: so define $\gamma_{j}:=\gamma_{[h]_{\tau}}$ if
$\gamma_{[h]_{\tau}}$ has label $j$. Let $\tilde{v}\in V$ be the vertex that
contains the Majoranas $\gamma_{0}$ and $\gamma_{2|E|-1}$ in its vertex
stabilizer. Then for each $v\in V\setminus\tilde{v}$, one has
$S_{v}=\prod_{j\in I_{v}}(i\gamma_{2j+1}\gamma_{2j+2})$, and
$S_{\tilde{v}}=(i\gamma_{0})\left(\prod_{j\in
I_{\tilde{v}}}i\gamma_{2j+1}\gamma_{2j+2}\right)\gamma_{2|E|-1}$, where for
every $v\in V$, $I_{v}\subseteq\\{0,\dots,|E|-2\\}$ contains those integers
$j$ such that $\gamma_{2j+1}$ is associated to a half-edge that is a subset of
$v$. Noticing that $(i\gamma_{2j+1}\gamma_{2j+2})$ commutes with all Majoranas
different from $\gamma_{2j+1}$ and $\gamma_{2j+2}$, we immediately get
$\prod_{v\in V}S_{v}=i^{|E|}\gamma_{0}\gamma_{1}\dots\gamma_{2|E|-1}$.
Similarly, each face stabilizer can be written as $S_{f}=\prod_{j\in
I_{f}}i\gamma_{2j}\gamma_{2j+1}$ where $I_{f}\subseteq\\{0,\dots,|E|-1\\}$
contains those integers $j$ for which $\gamma_{2j}$ belongs to an edge
adjacent to $f$. It follows that $\prod_{f\in
F^{\prime}}S_{f}=i^{|E|}\gamma_{0}\gamma_{1}\dots\gamma_{2|E|-1}$, completing
the proof.

∎

A consequence of Lemma 3.2(g) is that since $\mathcal{S}(R)$ is Abelian and
Hermitian, it implies that a non-empty subset of the stabilizers is dependent
if and only if the product of its elements is $I$. Let us determine the number
of qubits encoded by this Majorana code. There are $|V|+|F|$ stabilizers as
defined. However, not all these stabilizers are independent. If the total
number of independent stabilizers is $|V|+|F|-\alpha$ for a non-negative
integer $\alpha$, then the number of encoded qubits is

$K=(2|E|+M)/2-\left(|V|+|F|-\alpha\right)=M/2-\chi+\alpha,$ (14)

using Eq. (2). The remaining work is in determining $\alpha$ by counting
dependencies in the stabilizers, which can be done easily using Lemma 3.2.

######  Theorem 3.3.

A Majorana surface code encodes

$K=\left\\{\begin{array}[]{ll}2g&,\text{ orientable}\\\ g&,\text{ non-
orientable}\end{array}\right\\}+\left\\{\begin{array}[]{ll}0&,\text{
checkerboardable}\\\ (M-2)/2&,\text{ not
checkerboardable}\end{array}\right\\}$ (15)

qubits, where conditions in brackets are properties of the rotation system
$(H,\lambda,\rho,\tau)$, or equivalently the graph embedding, defining the
code.

  * Proof.

We will argue that (i) $\alpha\in\\{1,2\\}$, and (ii) $\alpha=2$ if and only
if the graph is checkerboardable. Once we have done so and because a
checkerboardable graph does not contain any odd degree vertices, we can use
Eq. (14) to complete the proof.

To prove (i), let $\mathcal{I}=\\{S_{v}:v\in V\\}\cup\\{S_{f}:f\in F\\}$ be
the set of stabilizers, so $\langle\mathcal{I}\rangle=\mathcal{S}(R)$. By
Lemma 3.2(e), one can always remove a single face stabilizer $S_{f}$ so that
$\langle\mathcal{I}\setminus S_{f}\rangle=\mathcal{S}(R)$, which implies
$\alpha\geq 1$. If $\mathcal{I}\setminus S_{f}$ is not independent, by Lemma
3.2(a,b,d) it must be that $\prod_{v\in V}S_{v}=\prod_{f\in F^{\prime}}S_{f}$
for some non-empty subset $F^{\prime}\subseteq F\setminus f$. If this happens
then we remove a vertex stabilizer $S_{v}$ arbitrarily after which Lemma
3.2(b) guarantees that the set $\mathcal{I}\setminus\\{S_{f},S_{v}\\}$ is
independent. Thus $\alpha\leq 2$. To prove (ii), by the preceding arguments
$\alpha=2$ if and only if $\prod_{v\in V}S_{v}=\prod_{f\in F^{\prime}}S_{f}$
for some non-empty proper subset $F^{\prime}\subset F$, and the latter is true
if and only if the graph is checkerboardable by Lemma 3.2(c). ∎

We also point out that if the graph defining the Majorana surface code has
vertices with degree one or degree two, then there are vertex stabilizers
$S_{v}$ that are the product of just two modes. These two modes and the
stabilizer that is their product can be removed from the code without
affecting the number of encoded qubits or code distance. What may be affected
is the degree of protection arising from superselection rules [32], e.g.
Kitaev’s 1D chain [35] has many such weight-two stabilizers. Nevertheless, our
main goal is to convert these Majorana surface codes to qubit codes where
superselection is not a relevant protection. Thus, we assume from now on that
our graphs have no vertices of degree less than three.

###  3.3 From Majorana surface codes to qubit surface codes

In this subsection we replace Majorana operators with Paulis to make qubit
surface codes from the Majorana surface codes of the previous section. The
main idea is to recognize that at each even (resp. odd) degree vertex $v$,
because of the vertex stabilizer $S_{v}$, there is a copy of the code
$\mathcal{S}_{\text{even}}$, Eq. (11), defined on $\text{deg}(v)$ (resp.
$\text{deg}(v)+1$) distinct Majorana modes and encoding $(\text{deg}(v)-2)/2$
(resp. $(\text{deg}(v)-1)/2$) qubits. Therefore, to define the qubit code
given an embedded graph $G=(V,E,F)$, the first step is to place this many
qubits at each vertex. We already assumed the graph has vertices of degree at
least three, so there is at least one qubit at each vertex.

Now, consider a single vertex $v$. By definition, Paulis that act only on the
qubits at $v$ can be associated to logical operators of the code
$\mathcal{S}_{\text{even}}$ located at $v$. We are most interested in the
Paulis associated to the sector operators
$q_{[h]_{\rho}}=i\gamma_{[h]_{\tau}}\gamma_{[\rho h]_{\tau}}$ for each flag
$h\in v$. That is, $q_{[h]_{\rho}}$ is the product of the two Majoranas on
half-edges adjacent to the sector. We are interested particularly in
$q_{[h]_{\rho}}$ because the face stabilizers of the Majorana code can be
alternatively written as the product of these sector operators,

$S_{f}=\pm\prod_{[h]_{\rho}\subseteq f}q_{[h]_{\rho}}.$ (16)

Therefore, choosing Paulis $q_{[h]_{\rho}}$ will also give $S_{f}$ in terms of
Paulis.

Let us list the sector operators $\\{q_{[h]_{\rho}},q_{[\tau\rho
h]_{\rho}},\dots,q_{[(\tau\rho)^{\text{deg}(v)-1}h]_{\rho}}\\}$ starting from
some arbitrary $h\in v$. Notice that these operators have very specific
commutation rules, with adjacent (and the first and last elements also
considered adjacent) elements anticommuting with one another, and all other
pairs commuting. This leads us to study the following lists of Paulis.

######  Definition 3.2.

A cyclically anticommuting list (CAL) acting on $n$ qubits is a list of
$n$-qubit Paulis $\\{p_{0},p_{1},\dots,p_{\ell-1}\\}$, in which for distinct
$i$ and $j$, $p_{i}$ and $p_{j}$ anticommute if and only if $i=j\pm
1\mod\ell$. A CAL of length $\ell\geq 1$ is called extremal if there does not
exist a CAL of the same length acting on fewer qubits.

Clearly, the list of sector operators $\\{q_{[h]_{\rho}},q_{[\tau\rho
h]_{\rho}},\dots,q_{[(\tau\rho)^{\text{deg}(v)-1}h]_{\rho}}\\}$ is a CAL of
length $\text{deg}(v)$ acting on $(\text{deg}(v)-2)/2$ qubits if $v$ has even
degree or acting on $(\text{deg}(v)-1)/2$ qubits if $v$ has odd degree. Let us
establish existence of CALs with a construction.

######  Theorem 3.4.

A CAL of length $\ell\geq 3$ acting on $n$ qubits in which the Paulis have
weight at most two exists if and only if

$n\geq\bigg{\\{}\begin{array}[]{ll}(\ell-2)/2,&\ell\text{ even},\\\
(\ell-1)/2,&\ell\text{ odd}.\end{array}$ (17)

  * Proof.

We construct extremal CALs with length $\ell$ acting on $n$ qubits saturating
the lower bound in Eq. (17). To get non-extremal CALs, more qubits can always
be added by acting on them with identity, or just Pauli $Z$, for instance, so
long as the commutation relations are unaffected. We note that extremal CALs
of length three and four, acting on a single qubit, are $\\{X,Y,Z\\}$ and
$\\{X,Z,X,Z\\}$. To construct extremal CALs of longer length, we define a
composition operation $\circ$ that takes a CAL of length $\ell$ (even) and a
CAL of length $\ell^{\prime}$ (either even or odd) to a CAL of length
$\ell+\ell^{\prime}-2$:

$\\{p_{0},\dots,p_{\ell-1}\\}\circ\\{p^{\prime}_{0},\dots,p^{\prime}_{\ell^{\prime}-1}\\}:=\\{p_{0},\dots,p_{\ell/2-2},p_{\ell/2-1}p^{\prime}_{0},p^{\prime}_{1},p^{\prime}_{2},\dots,p^{\prime}_{\ell^{\prime}-2},p^{\prime}_{\ell^{\prime}-1}p_{\ell/2},p_{\ell/2+1}\dots
p_{\ell-1}\\},$ (18)

where the $p_{j}$s and $p^{\prime}_{j}$s represent Paulis that act on $n$ and
$n^{\prime}$ qubits, respectively. Thus the CAL on the right acts on
$n+n^{\prime}$ qubits. Repeated application of this composition suffices to
make CALs of any length out of the length three and four CALs given above.
Composition preserves extremality — if $n$ and $n^{\prime}$ are minimal qubit
counts for CALs of lengths $\ell$ and $\ell^{\prime}$, then

$n+n^{\prime}=\bigg{\\{}\begin{array}[]{ll}(\ell+\ell^{\prime}-4)/2,&\ell^{\prime}\text{
even},\\\ (\ell+\ell^{\prime}-3)/2,&\ell^{\prime}\text{ odd}\end{array}$ (19)

is the minimum number of qubits needed for a length $\ell+\ell^{\prime}-2$
CAL. A graphical depiction of this composition operation is shown in Fig. 3.
It should be clear that the construction results in CALs consisting of Paulis
of weight just one or two.

Figure 3: One way to create a CAL of length $\ell$ is to compose CALs of
lengths three or four together. In (a), we compose three CALs with length four
(right) to make a CAL with length eight (left) acting on three qubits (red
circles). In (b), we use a similar composition of two length-four CALs and one
length-three CAL to make a length-seven CAL. In terms of surface codes defined
on graphs, this composition operation means that we can always decompose
higher degree vertices into vertices with degrees just three or four. Still,
we generally will include higher degree vertices in our drawings to highlight
symmetries when possible.

There are no CALs of length $\ell$ acting on fewer qubits than in Eq. (17).
Suppose, by way of contradiction, that a CAL
$\\{p_{0},p_{1},\dots,p_{\ell-1}\\}$ acting on $n$ qubits has length
$\ell>2n+2$. Then, there is a set of Paulis

$\left\\{a_{j}=\prod_{k=0}^{j}p_{k}:j\in\\{0,1,\dots,\ell-2\\}\right\\}$ (20)

with size $>2n+1$ in which all Paulis anticommute with one another. However,
this contradicts known results on the maximum size of such anticommuting sets
[36]. ∎

CALs can be thoroughly studied in their own right. The interested reader can
find much more discussion of CALs in Appendix B. For instance, we show some
structural properties of extremal CALs, such as the following lemmas which we
find useful (see Corollary B.10 and Corollary B.11).

######  Lemma 3.5.

If $\\{p_{0},p_{1},\dots,p_{\ell-1}\\}$ is an extremal CAL of length $\ell\geq
3$ acting on $n$ qubits, then taking products of the $p_{i}$ generates the
entire $n$-qubit Pauli group (up to global phases).

######  Lemma 3.6.

Suppose $\\{p_{0},p_{1},\dots,p_{\ell-1}\\}$ is an extremal CAL of length
$\ell\geq 3$. Then $\prod_{j=0}^{\ell-1}p_{j}\propto I$ and, if $\ell$ is
even, $\prod_{j=0}^{\ell/2-1}p_{2j}\propto I$ and
$\prod_{j=0}^{\ell/2-1}p_{2j+1}\propto I$. Moreover, these are the only
products that are proportional to identity.

These lemmas lead to the following simple corollary.

######  Corollary 3.7.

Let $\mathcal{C}=\\{p_{0},p_{1},\dots,p_{\ell-1}\\}$ be an extremal CAL of
length $\ell\geq 3$ acting on $n$ qubits. For any Pauli $q$ acting on $n$
qubits, define the (row) vector $C_{q}\in\mathbb{F}_{2}^{\ell}$ whose
$j^{\text{th}}$ element is $1$ if and only if $q$ and $p_{j}$ anticommute. If
$\ell$ is odd define
$M^{\top}=\left(\begin{smallmatrix}1&1&\dots&1&1\end{smallmatrix}\right)\in\mathbb{F}_{2}^{1\times\ell}$
and if $\ell$ is even $M^{\top}=\left(\begin{smallmatrix}1&1&\dots&1&1\\\
1&0&\dots&1&0\end{smallmatrix}\right)\in\mathbb{F}_{2}^{2\times\ell}$. Then
$C_{q}M=\vec{0}$. Moreover, if $x\in\mathbb{F}_{2}^{\ell}$ satisfies
$xM=\vec{0}$, then there exists a (unique, up to phase) Pauli $q$ such that
$x=C_{q}$. Finally, $C_{q}=\vec{0}$ if and only if $q\propto I$.

  * Proof.

Lemma 3.6 implies that the last one (two) Paulis of a CAL are not independent
from the others if $\ell$ is odd (even) and that these are the only
dependencies. These dependencies result in $C_{q}M=0$. Lemma 3.5 implies that
the first $\ell-1$ ($\ell-2$) independent Paulis of the CAL generate the
entire $n$-qubit Pauli group. Therefore, we are guaranteed the existence of a
(unique, up to phase) Pauli $q$ satisfying the commutation relations expressed
by the first $\ell-1$ ($\ell-2$) bits of $x$ and, since $xM=\vec{0}$, the
final one (two) bits of $x$ must be consistent with those commutations.
Finally, $C_{q}=\vec{0}$ implies $q$ commutes with the entire Pauli group,
which is possible if and only if $q\propto I$. ∎

With CALs forming the basis for the logical space of the Majorana code
$\mathcal{S}_{\text{even}}$ we can complete our construction of qubit surface
codes.

######  Definition 3.3.

Suppose we have an embedded graph $G$ described by some rotation system
$R=(H,\lambda,\rho,\tau)$ and the vertices of $G$ are at least degree three.
At vertex $v$, place $N_{v}=\lceil(\text{deg}(v)-2)/2\rceil$ qubits, and
associate a Hermitian Pauli $q_{[h]_{\rho}}$ to each sector $[h]_{\rho}$
around that vertex. These Paulis $\\{q_{[h]_{\rho}},q_{[\tau\rho
h]_{\rho}},\dots,q_{[(\tau\rho)^{\text{deg}(v)-1}h]_{\rho}}\\}$ should form an
extremal CAL of length $\text{deg}(v)$ acting on the $N_{v}$ qubits at $v$. To
every face $f$ of the graph we associate a stabilizer, the product of all
Paulis associated to sectors $[h]_{\rho}\subseteq f$.

By the discussion starting this subsection, this definition ensures the
codespaces of the Majorana code associated to $G$ (Definition 3.1) and the
qubit surface code associated to $G$ (Definition 3.3) are the same, both
encoding $K$ qubits from Theorem 3.3, leading to the following corollary,
which is formally proved in Appendix C.

######  Corollary 3.8.

A qubit surface code encodes

$K=\left\\{\begin{array}[]{ll}2g&,\text{ orientable}\\\ g&,\text{ non-
orientable}\end{array}\right\\}+\left\\{\begin{array}[]{ll}0&,\text{
checkerboardable}\\\ (M-2)/2&,\text{ not
checkerboardable}\end{array}\right\\}$ (21)

qubits, where conditions in brackets are properties of the rotation system
$(H,\lambda,\rho,\tau)$, or equivalently the graph embedding, defining the
code.

Fig. 4, the qubit versions of the Majorana codes from Fig. 2, should help in
understanding the correspondence of Majorana and qubit surface codes. Further
examples of qubit surface codes fitting our definition and appearing in prior
literature are shown in Fig. 5.

Notice that while a Majorana surface code has stabilizers associated to both
vertices and faces, a qubit surface code only has stabilizers associated to
faces. This is because we introduced just the right number of qubits at each
vertex to automatically enforce the vertex stabilizers of the Majorana surface
code. Alternatively, we introduced just enough physical qubits to span the
codespaces of the Majorana codes $\mathcal{S}_{\text{even}}$ that exist at
each vertex. This fact can also be illustrated with a simple qubit count –
with one qubit for every two Majoranas (e.g. using the Jordan-Wigner
transformation, Eq. (10)) we would have $(2|E|+M)/2=|E|+M/2$ qubits (recall
$M$ is the number of odd-degree vertices), but instead we have used

$N=\sum_{v\in V}N_{v}=M/2+\sum_{v\in
V}\left(\text{deg}(v)-2\right)/2=|E|-|V|+M/2$ (22)

qubits. Each of the $|V|$ “missing” qubits is a degree of freedom eliminated
by enforcing a stabilizer $S_{v}$.

For stabilizer code with stabilizer group $\mathcal{S}$, the _logical
operators_ are the elements of the centralizer $\mathcal{C}(\mathcal{S})$,
i.e. the group of all Pauli operators that commute with all elements of
$\mathcal{S}$. The centralizer includes the stabilizer group itself, and so we
refer to elements of $\mathcal{S}$ as trivial logical operators as they apply
the logical identity to encoded qubits. The code distance $D$ of a stabilizer
code is the minimum weight of an element of
$\mathcal{C}(\mathcal{S})\setminus\langle\\{iI\\}\cup\mathcal{S}\rangle$. We
use the notation $\llbracket N,K,D\rrbracket$ to concisely present the code
parameters of a stabilizer code.

Figure 4: Qubit versions of the Majorana codes in Fig. 2. Place a single qubit
on vertices with degrees three or four and a pair of qubits on vertices with
degrees five or six. Around each vertex write a cyclically anticommuting list
of Paulis (acting on qubits at that vertex). Each face represents a stabilizer
defined as the product of all Paulis written within that face. Note that (b)
depicts a toric code with $X^{\otimes 4}$ and $Z^{\otimes 4}$ stabilizers but
on a lattice different from Kitaev’s square lattice [1]. In this case, the
code is $\llbracket 24,2,4\rrbracket$. The number of encoded qubits is clear
by Corollary 3.8 as this graph embedding is checkerboardable.  Figure 5: (a)
The triangular surface code [6], (b) the rotated surface code [3] and (c) a
stellated surface code [8] with even greater symmetry. Each code fits in our
framework – in this case, by Definition 3.3 applied to these planar graphs. In
(b), we show explicitly the assignment of CALs that gives the familiar rotated
surface code. Notice that the outer face also gets assigned a stabilizer.
Because of Lemma 3.2(e), the product of stabilizers on all non-outer faces is
proportional to the stabilizer on the outer face.

To further demonstrate Definition 3.3, in Fig. 6 we show a family of
topological codes that includes the well-known $\llbracket 5,1,3\rrbracket$
code as its smallest member. Also included as a subset are the cyclic codes
given in Example 11 and Figure 3 of [37]. The general construction gives
cyclic codes defined on the torus. Consider the typical fundamental square for
the torus, i.e. a unit square with opposite sides identified, and draw the
lines $y=bx/a$ and $y=-ax/b$, where we assume $b>a\geq 1$ are integers and
$\text{gcd}(a,b)=1$. These two lines intersect at $N=a^{2}+b^{2}$ points
within the fundamental square, including the single point at
$(0,0)=(0,1)=(1,0)=(1,1)$. Interpret these intersections as vertices of a
4-regular graph with edges the line segments between them. With correct choice
of CALs, so that each face stabilizer has two $X$s and two $Z$s (see Fig. 6
for the convention we use), and with qubits labeled in a sequence along the
line $y=bx/a$ (moving outwards from the origin in the direction of increasing
$x$), the surface code defined by this graph and Definition 3.3 is cyclic — an
overcomplete generating set of the stabilizer group consists of $Z\otimes
X\otimes I^{\otimes s}\otimes X\otimes Z\otimes I^{N-s-4}$ and its cyclic
permutations, where $s=\lceil Nt/b\rceil-2$ and $t$ is the minimal positive
integer such that $(ta+1)/b$ is an integer.333The extended Euclidean algorithm
on $(a,b)$ can be used to determine $t$. A Bézout pair $(x,y)$ of $(a,b)$ is a
pair of integers such that $xa+yb=\text{gcd}(a,b)$. In particular,
$(x,y)=(-t,(ta+1)/b)$ is the unique Bézout pair of $(a,b)$ in which $-b\leq
x\leq 0$. We have the following parameters for these codes.

Figure 6: (a) The smallest error-correcting quantum code, the $\llbracket
5,1,3\rrbracket$ code, is a surface code defined by an embedding of the
5-vertex complete graph $K_{5}$ in the torus. There are different embeddings
of $K_{5}$ in the torus, but no other gives a 5-qubit code with distance more
than two. Parts (b-f) show members of the cyclic toric code family with more
qubits. See Theorem 3.9 and the paragraph above it for the code definition and
parameters. A demonstrative CAL is written around one vertex in each graph.
The codes are cyclic when this same CAL is orientated similarly around each
vertex.

######  Theorem 3.9.

The cyclic toric code with integer parameters $a$ and $b$, where without loss
of generality $\text{gcd}(a,b)=1$ and $b>a\geq 1$, is a $\llbracket
N=a^{2}+b^{2},K,D\rrbracket$ code, with

  1. 1.

If $N$ is odd, $K=1$ and $D=a+b$,

  2. 2.

If $N$ is even, $K=2$ and $D=b$.

The odd and even cases differ in the number of encoded qubits because of
checkerboardability (the latter case being checkerboardable and the former
not). Note that a consequence of the theorem is that the code distance $D$ is
always odd. The codes in Example 11 and Figure 3 of [37] are cyclic toric
codes with $a=b-1$.

We delay the proof of this theorem, in particular the code distances, until
Section 5.2, after we have developed sufficient tools in Section 4. We point
out that in two situations, the cyclic toric codes achieve
$N=\frac{1}{2}KD^{2}+O(D)$ – when $a=b-1=(D-1)/2$ and when $b=D$ is odd with
$a=1$. Moreover, $1/2$ is the best constant achievable for the cyclic toric
codes.

To conclude this section, we point out a corollary on the structure of qubit
surface codes that follows from the proof of Theorem 3.4, and in particular
the vertex decomposition demonstrated in Fig. 3. We use this corollary later
to justify considering only graphs of low degree.

######  Corollary 3.10.

For any graph $G$, there is a choice of CALs such that the surface code
associated with $G$ is the same as the code associated with another graph
$G^{\prime}$ that only has vertices with degrees three and four.

###  3.4 Relation to homological surface codes

Finally, we want to point out the relation of Definition 3.3 with the well-
known homological construction of surface codes [1, 38, 39]. In the
homological construction, a single qubit is placed on each edge of a graph
embedding $G=(V,E,F)$. Stabilizers correspond to each vertex $v\in V$ and face
$f\in F$:

$S^{\prime}_{v}=\prod_{e\in v}X_{e},\quad S^{\prime}_{f}=\prod_{e\in f}Z_{e},$
(23)

where $e\in v$ and $e\in f$ are shorthand for saying edge $e$ is adjacent to
the vertex $v$ or face $f$, and of course $X_{e}$, $Z_{e}$ are Paulis on the
qubit on that edge.

The _medial graph_ $\widetilde{G}$ of an embedded graph $G=(V,E,F)$ has a
vertex for each edge of $G$ and connects them with edges such that vertices
and faces of $G$ form faces of $\widetilde{G}$. See some examples in Fig. 7.
It should be clear that the homological surface code defined on graph $G$ is
exactly the same code as our surface code, Definition 3.3, defined on the
medial graph $\widetilde{G}$. Thus, Definition 3.3 includes all homological
codes.

We can formally define the medial graph using rotation systems.

######  Definition 3.4.

The _medial rotation system_
$\widetilde{R}=(\widetilde{H},\widetilde{\lambda},\widetilde{\rho},\widetilde{\tau})$
of a rotation system $R=(H,\lambda,\rho,\tau)$ is defined by setting
$\widetilde{H}=H\times\\{1,-1\\}$ and for $(h,j)\in\widetilde{H}$ letting
$\widetilde{\tau}(h,j)=(h,-j)$, $\widetilde{\lambda}(h,j)=(\rho(h),j)$, and

$\widetilde{\rho}(h,j)=\bigg{\\{}\begin{array}[]{ll}(\lambda(h),j),&\text{if
}j=-1\\\ (\tau(h),j),&\text{if }j=1\end{array}.$ (24)

Some facts about medial graphs become apparent (we prove these in Appendix E).
First, the medial graph embeds into the same manifold as the original graph.
Second, medial graphs are also always 4-valent (every vertex is degree four).
Third, medial graphs are always checkerboardable – e.g. a natural way to color
faces in $\widetilde{G}$ is to color black faces that correspond to vertices
of $G$ and color white faces corresponding to faces of $G$. In fact, an
embedded graph is the medial graph of another embedded graph if and only if it
is 4-valent and checkerboardable. As a result, there are codes resulting from
Definition 3.3 that cannot be described as homological codes.

The reader may also refer to [3] where checkerboardable, 4-valent graphs (i.e.
medial graphs) are used to define homological surface codes directly and to
[40] where this connection between homological codes and medial graphs is also
pointed out.

Figure 7: Graphs (gray edges with small, black vertices) on the torus (a) and
projective plane, (b) and (c), are drawn with their medial graphs (black edges
and large, red vertices). In (a), we get a $\llbracket 8,2,2\rrbracket$ toric
code. In (b), we get Shor’s $\llbracket 9,1,3\rrbracket$ code [41] with the
gray graph coming from [39]. In (c), we show another $\llbracket
9,1,3\rrbracket$ code from [39].

Of course, forays have already been made beyond the strict homological surface
code construction. We have already seen some examples in the forms of the
triangular, rotated, and stellated codes, Fig. 5. Our goal however is a more
rigorous framework that generalizes these specific instances.

One way in which the homological surface code construction can be rigorously
generalized to produce more general planar codes is described by Freedman and
Meyer [39]. Let us describe this construction using the language of medial
graphs. Start with a homological surface code defined on an improper embedding
of a graph in orientable surface of genus $g$. By an improper embedding, we
mean one face is not an open disk but instead a $g$-punctured disk, e.g. if
$g=1$ the $g$-punctured face is a cylinder. Now, form the medial graph of this
improperly embedded graph444We defined the medial graph of an embedded graph.
In this case, the graph is not properly embedded. When we construct the medial
graph here, we do so by drawing proper, disk-like faces around each vertex..
The medial graph will also be improperly embedded, but it is still 4-valent
and checkerboardable. Because of the redundancy in stabilizers (see proof of
Theorem 3.3), we can delete, i.e. remove from the stabilizer group, any single
black as well any single white face without changing the code. Thus, delete
the face that is $g$-punctured (say it is colored white), a black face sharing
an adjacent edge, and any edges shared between them. The result is a planar
graph with some degree-3 vertices (because of the deletion of edges). Examples
producing the rotated surface code and the Bravyi-Kitaev planar code [38] are
shown in Fig. 8.

Figure 8: Improper embeddings of graphs (gray), and their medial graphs
(black), on the torus. In both pictures, the face (of the medial graph
embedding) intersecting the top and bottom frames is not an open disk but
instead a cylinder. Deleting this face, the face intersecting the left and
right frames, and their shared adjacent edges (highlighted) results in
familiar planar codes. In (a) we find the $\llbracket 9,1,3\rrbracket$ rotated
surface code and in (b) Bravyi and Kitaev’s planar code [38], in this instance
$\llbracket 18,1,3\rrbracket$.

Notably, this improper embedding procedure does not produce non-
checkerboardable graph embeddings in surface of larger genus $g>0$, so it does
not produce the cyclic toric codes in Fig. 6(a,c,d,f) for instance. We have
also not found a way to produce stellated codes with odd symmetry, e.g. parts
(a) and (c) of Fig. 5, using the improper embedding technique, the apparent
obstacle being the presence of an odd degree vertex in the center of the
planar graph, i.e. not adjacent to the outer face. This appears an obstacle
because the outer face and the odd degree vertices are effectively created by
deleting faces and their shared adjacent edges from the improper embedding,
with the result being that any odd degree vertices are adjacent to the outer
face. Hence, we find this construction involving improper embeddings and face
deletions to be more complicated than our construction while also producing
fewer codes.

##  4 Locating logical operators

In this section, we discuss the structure of logical operators in the
generalized surface codes of Definition 3.3. One of our main findings is that
logical operators are exactly the homologically non-trivial cycles in a
related graph, called the decoding graph. This is probably not a huge surprise
to someone familiar with homological codes, but there are some technical
hurdles to overcome in proving it in our generalized setting, including the
fact that the decoding graph for non-checkerboardable codes is not generally
embeddable in the same manifold $\mathcal{M}$ as the original graph. Without a
graph embedding, there is no notion of homology, so finding an appropriate
embedding of the decoding graph is essential to the proof.

In Section 4.1 we generalize checkerboardability to include “defects”, useful
in the subsequent sections. In Section 4.2 we define the decoding graph, show
that cycles in the decoding graph correspond to logical operators of the code
(both trivial and non-trivial), and prove it embeds in $\mathcal{M}$ in the
checkerboardable case. In Section 4.3, we define a (generally higher-genus)
manifold in which we can embed the decoding graph, and prove that homological
non-triviality in this new manifold equates with logical non-triviality.
Finally, in Section 4.5, we discuss how some logical operators (including all
trivial ones) can be represented by paths in the original graph.

###  4.1 Checkerboardability with defects

In Definition 2.3 we defined what it means for a graph embedding to be
checkerboardable. In this section, we generalize this notion to include
defects. Informally put, a defect is a set of edges that can be deleted from
the graph embedding to make it checkerboardable. Defects have a few uses in
finding or identifying logical operators in surface codes which are covered in
the subsequent subsections.

To define checkerboardability with defects more rigorously, we use the matrix
$\Phi\in\mathbb{F}_{2}^{|F|\times|E|}$ from Section 2.4, which encodes the
edges belonging to each face of the embedding.

######  Definition 4.1.

We say a graph embedding $G=(V,E,F)$ is checkerboardable with defect
$\delta\in\mathbb{F}_{2}^{|E|}$ if there is a vector
$x\in\mathbb{F}_{2}^{|F|}$ such that $x\Phi=\vec{1}+\delta$.

Clearly, being checkerboardable according to Definition 2.3 is equivalent to
being checkerboardable with the trivial defect $\delta=\vec{0}$. The analogous
lemma to Lemma 2.2 is as follows.

######  Lemma 4.1.

$G$, described by rotation system $R=(H,\lambda,\rho,\tau)$, is
checkerboardable with a defect if and only if we can partition $H$ into two
sets $H_{w}$ and $H_{b}$ such that $\lambda$ and $\rho$ map both sets to
themselves, while $\tau$ maps elements of either set to the other set,
_except_ when those flags are part of an edge in the defect.

A given embedded graph does not have a unique defect. However, different
choices of defect are related by the addition of rows of $\Phi$. That is, by
simple application of the definition, the following is true.

######  Lemma 4.2.

Suppose a graph embedding $G=(V,E,F)$ is checkerboardable with defect
$\delta_{1}$. Then, $G$ is checkerboardable with defect $\delta_{2}$ as well
if and only if there exists $x$ such that $x\Phi=\delta_{1}+\delta_{2}$.

Moreover, it is an interesting fact that a defect cannot be just any subset of
edges. In fact, a defect must be a sum of certain _trails_ in the graph.
Recall that $\mathcal{T}(G)\cong\mathbb{F}_{2}^{|E|}$ is the group of all
trails in the graph. A subgroup of $\mathcal{T}(G)$ is generated by just the
closed trails and trails whose endpoints are odd-degree vertices. We call this
subgroup $\mathcal{T}_{0}(G)$.

######  Lemma 4.3.

Suppose the graph embedding $G=(V,E,F)$ is checkerboardable with defect
$\delta\in\mathbb{F}_{2}^{|E|}$. Then, $\delta\in\mathcal{T}_{0}(G)$. Let
$a_{v}=\sum_{e\ni v}\delta_{e}$ evaluated over $\mathbb{F}_{2}$ indicate the
parity of the number of edges that are adjacent to $v\in V$ and in the defect.
Then, $a_{v}=1$ if and only if $\deg(v)$ is odd.

  * Proof.

The way that $\delta$ can fail to be in $\mathcal{T}_{0}(G)$ is if $a_{v}=1$
for some even-degree vertex $v$. However, if this were the case, it would
imply that $G$ is not checkerboardable with defect $\delta$ because it fails
to be so locally around vertex $v$. We would need to two-color faces around
$v$ such that faces on opposite sides of an edge $e\ni v$ are different colors
if $\delta_{e}=0$ and the same color if $\delta_{e}=1$. This is impossible for
an even-degree vertex with $a_{v}=1$. This shows
$\delta\in\mathcal{T}_{0}(G)$. The remaining claim, that $a_{v}=1$ for odd-
degree vertices $v$ follows from a similar argument of colorability in the
local neighborhood of $v$. ∎

Finally, we point out that for any graph embedding $G$ it is efficient
(polynomial time in graph size) to perform two related tasks: (1) determine
some $\delta\in\mathbb{F}_{2}^{|E|}$ such that $G$ is checkerboardable with
defect $\delta$ and (2) given a candidate $\delta\in\mathbb{F}_{2}^{|E|}$
determine whether $G$ is checkerboardable with defect $\delta$. We present an
algorithm in Algorithm 1 that can perform both tasks via a greedy strategy.
The inputs are, first, a representation of the faces in the graph embedding
(to be concrete, we use the binary vectors $\phi_{i}\in\mathbb{F}_{2}^{|E|}$,
$i=1,2\dots,|F|$, that are the rows of $\Phi$) and, second, a candidate defect
$\delta$. The outputs are a list of faces colored black, a list of those
colored white, and a defect. The algorithm starts by arbitrarily coloring one
face and continues by coloring faces that neighbor colored faces appropriately
(the same color if they neighbor across a defect edge and differently
otherwise). If ever a face cannot be colored either color without
contradiction, edges are added or removed from the defect to make it work.

It is clear this algorithm solves task (1). To solve (2), we note the
algorithm guarantees that the output defect $\gamma$ is the same as the input
$\delta$ if and only if $\delta$ is a defect. This solves (2). In the course
of the algorithm, each edge is considered at most once in the while loop, the
body of which takes $O(\max_{i}|\phi_{i}|)$ time using appropriate data
structures,555In particular, one needs adjacency oracles that take a part of
the graph embedding (e.g. a face) and return other adjacent parts (e.g. the
adjacent edges). These oracles or similar are standard in the field of
computational graph theory – for instance, the “doubly-connected edge list”
data structure used in [42]. leading to a total time complexity of just
$O(|E|\max_{i}|\phi_{i}|)$ for both tasks (1) and (2).

Algorithm 1 Returns checkerboard colors for each face and a list of edges in
the defect

1:procedure
Checkerboard($\\{\phi_{1},\phi_{2},\dots,\phi_{|F|}\\}\in\left(\mathbb{F}_{2}^{|E|}\right)^{|F|}$,
$\delta\in\mathbb{F}_{2}^{|E|}$)

2: Set $B\leftarrow\\{1\\}$, $W\leftarrow\emptyset$ # Sets of faces colored
black and white

3: Set $\gamma\leftarrow\delta$ # This is a record of the defect edges (vector
in $\mathbb{F}_{2}^{|E|}$)

4: Set $b\leftarrow\phi_{1}$ # This is a list of “boundary” edges of the faces
already colored (vector in $\mathbb{F}_{2}^{|E|}$)

5: For any edge $e$ that is internal to a face (same face on both sides), set
$\gamma_{e}\leftarrow 1$.

6: While $b$ is not $\vec{0}$:

7: Let $e$ be the first edge such that $b_{e}=1$

8: If $e$ is adjacent to a face $f\not\in B\cup W$ and a face $g\in B\cup W$:

9: If $g\in W$ and $\gamma_{e}=0$, append $f$ to $B$.

10: If $g\in B$ and $\gamma_{e}=1$, append $f$ to $B$.

11: If $f\not\in B$, append $f$ to $W$.

12: Set $b_{e^{\prime}}=1$ for any $e^{\prime}$ that borders both $f$ and a
face $f^{\prime}\not\in B\cup W$.

13: else:

14: If the two faces adjacent to $e$ are both in $B$ or both in $W$, set
$\gamma_{e}\leftarrow 1$. Else, set $\gamma_{e}\leftarrow 0$.

15: Set $b_{e}=0$

16: Return $B,W,\gamma$

###  4.2 Characterizing logical operators as cycles in the decoding graph

Recall that $\mathcal{C}(\mathcal{S})$ is the group of logical operators of
the stabilizer code with stabilizer $\mathcal{S}$. We characterize
$\mathcal{C}(\mathcal{S})$ for our surface codes as the cycles in a related
graph, referred to here as the decoding graph.

######  Definition 4.2.

Given an embedded graph $G=(V,E,F)$, an associated decoding graph
$G_{\text{dec}}$ is a (unembedded) graph with vertices $V_{\text{dec}}$ of
three types: (1) a vertex $u_{f}$ associated to each face of $G$, (2) a vertex
$w^{(0)}_{v}$ associated to each odd-degree vertex of $G$, and (3) two
vertices $w^{(1)}_{v}$ and $w^{(-1)}_{v}$ associated to each even-degree
vertex of $G$. For each sector $[h]_{\rho}$ of $G$, there is an edge
$e_{[h]_{\rho}}$ in $G_{\text{dec}}$. Choose $v\in V$ and $f\in F$ such that
$h\in v$ and $h\in f$. If $v$ is odd-degree, $e_{[h]_{\rho}}$ connects
vertices $w^{(0)}_{v}$ and $u_{f}$. If $v$ is even-degree, $e_{[h]_{\rho}}$
connects vertices $u_{f}$ to $w^{(j)}_{v}$ where $j$ is such that the edges
associated to the adjacent sectors, i.e. $e_{[\tau h]_{\rho}}$ and
$e_{[\tau\rho h]_{\rho}}$, are incident to $w^{(-j)}_{v}$. All decoding graphs
of $G$ are equivalent up to relabeling vertices $w^{(1)}_{v}$ and
$w^{(-1)}_{v}$, so we just speak of _the_ decoding graph of $G$.

In Fig. 9, we draw the decoding graph locally around vertices of small degree.
Our definition is slightly different from the decoding graphs commonly used
decode surface codes (e.g. [43]) in that we introduce vertices at the vertices
of $G$ as well as the faces. One reason we do this is so we can make precise
statements about embedding the decoding graph or its connected components into
various manifolds. A consequence of this decision however is that the decoding
graph’s systole is doubled. The reader knowledgeable in topological quantum
error correction should not be concerned by the appearance of a factor of
$1/2$ when we calculate the code distance in terms of this systole.

Consider now the problem of relating cycles in $G_{\text{dec}}$ to elements of
$\mathcal{C}(\mathcal{S})$. Notice that the decoding graph is bipartite, with
vertices associated to faces of $G$ (type 1 in the Definition) on one side and
vertices associated to vertices of $G$ (types 2 and 3) on the other.
Therefore, any cycle in $G_{\text{dec}}$ is even-length and can be broken into
paths of consecutive edges $(e_{[h]_{\rho}},e_{[k]_{\rho}})$, where $h,k$ are
flags in the same vertex $v$ but not in the same sector. We let
$\mathcal{T}_{2}(G_{\text{dec}})\leq\mathcal{T}(G_{\text{dec}})$ denote the
group of two-edge paths of $G_{\text{dec}}$.

Define a map
$\sigma:\mathcal{T}_{2}(G_{\text{dec}})\rightarrow\mathcal{C}(\mathcal{S})$
that translates each two-edge path $(e_{[h]_{\rho}},e_{[k]_{\rho}})$ to a
Pauli acting on qubits at the vertex $v$. This Pauli is chosen to anti-commute
with only two elements, $q_{[h]_{\rho}}$ and $q_{[k]_{\rho}}$, of the CAL
associated with $v$ that defines the surface code on $G$ (see Definition 3.3).
This Pauli exists and is unique (up to phase) by Corollary 3.7.

Now we state some consequences of Corollary 3.7 for $\sigma$. First, if we
ignore phases on the Paulis, $\sigma$ is actually surjective – every Pauli up
to phase is represented by some collection of two-edge paths in
$G_{\text{dec}}$ – and, second, $\sigma$ is a homomorphism – for all
$t_{1},t_{2}\in\mathcal{T}_{2}(G_{\text{dec}})$, we have
$\sigma(t_{1}+t_{2})=\sigma(t_{1})\sigma(t_{2})$. Finally, $\sigma(t)\propto
I$ if and only if $t$ is the empty set.

Figure 9: The decoding graph (red/blue) pictured locally around vertices of
degrees 3 through 6. In odd-degree cases, all vertices in the surrounding
faces connect to the central vertex. In the even-degree cases, there are two
distinct central vertices, red and blue (not shown), and faces connect to
these alternatively.

By surjectivity of $\sigma$, if we have a logical operator
$l\in\mathcal{C}(\mathcal{S})$, then it can be represented by a set of edges
$E_{l}\subseteq E_{\text{dec}}$ in the decoding graph. Because the logical
operator must commute with all stabilizers $S_{f}$, the number of edges from
$E_{l}$ incident to any vertex $u_{f}$ of the decoding graph (i.e. a face in
the original graph) must be even. Therefore, $E_{l}$ is a sum of cycles in the
decoding graph. The converse is also clearly true – any cycle $c$ in the
decoding graph maps to a logical operator
$\sigma(c)\in\mathcal{C}(\mathcal{S})$. Thus, we have a characterization of
the logical operators of our codes.

######  Theorem 4.4.

Let $G=(V,E,F)$ be an embedded graph. Cycles in the decoding graph of $G$
(Defintion 4.2) represent all logical operators of the qubit surface code
corresponding to $G$ (Definition 3.3) via the map $\sigma$.

Figure 10: Example cycles in a decoding graph. The original graph has black
edges, and stitched edges are part of a (particular choice of) defect. Faces
are checkerboardable with this defect (the outer face should be colored black
but is not shown). The entire decoding graph is not shown, but cycles labeled
(a), (b), (c), (d), (e), and (f) illustrate some of it. Cycles (a), (b), (c)
in green represent trivial logical operators (i.e. stabilizers), while cycles
(d) and (e) in red and cycle (f) in blue represent non-trivial logical
operators. We know they are non-trivial because (d) and (e) anticommute with
(f). Cycles (a), (e), and (f) connect to the vertex in the outer face (not
shown) via their dangling edges.

See Fig. 10 for some examples of cycles in a decoding graph and their
correspondence with logical operators.

In checkerboardable codes, we can say even more about locating nontrivial
logical operators by relating them to the homology of the surface. For this to
work, we must embed the decoding graph of the checkerboardable code into the
same surface.

######  Lemma 4.5.

Suppose $G$ is a checkerboardable graph embedded in a 2-manifold
$\mathcal{M}$. Then the decoding graph $G_{\text{dec}}$ consists of exactly
two connected components, each of which can be embedded in the manifold
$\mathcal{M}$.

  * Proof.

Suppose $G$ is described by the rotation system $(H,\lambda,\rho,\tau)$ and,
because it is checkerboardable, there is a partition $H=H_{w}\sqcup H_{b}$ as
in Lemma 2.2. Of course, each vertex of $G$ is necessarily even-degree. It
should be clear from Fig. 9 that the decoding graph $G_{\text{dec}}$ has two
connected components, one corresponding to faces that are subsets of $H_{w}$
and another corresponding to faces that are subsets of $H_{b}$.

Let $G_{\text{dec},w}$ and $G_{\text{dec},b}$ be the connected components of
$G_{\text{dec}}$. These are described by rotation systems
$R_{\text{dec},w}=(H_{w}\times\\{\pm
1\\},\lambda_{\text{dec}},\rho_{\text{dec}},\tau_{\text{dec}})$ and
$R_{\text{dec},b}=(H_{b}\times\\{\pm
1\\},\lambda_{\text{dec}},\rho_{\text{dec}},\tau_{\text{dec}})$, where

$\displaystyle\lambda_{\text{dec}}(h,j)$ $\displaystyle=(h,-j),$ (25)
$\displaystyle\rho_{\text{dec}}(h,j)$
$\displaystyle=\bigg{\\{}\begin{array}[]{ll}(\tau\rho\tau(h),j),&j=-1\\\
(\lambda(h),j),&j=1\end{array},$ (28) $\displaystyle\tau_{\text{dec}}(h,j)$
$\displaystyle=(\rho(h),j).$ (29)

This provides an explicit embedding of the components of $G_{\text{dec}}$.

We do still need to show that they are indeed embedded in the manifold
$\mathcal{M}$ and not some other one. Suppose $G$ has sets of vertices, edges,
faces $V$, $E$, $F=F_{w}\sqcup F_{b}$ (with this partition due to
checkerboardability) and $G_{\text{dec},w}$ has sets $V_{\text{dec}}$,
$E_{\text{dec}}$, and $F_{\text{dec}}$. One can check from the rotation
system, Eqs. (25-29), that $|V_{\text{dec}}|=|F_{w}|+|V|$,
$|E_{\text{dec}}|=\frac{1}{2}\sum_{v\in V}\text{deg}(v)=|E|$, and
$|F_{\text{dec}}|=|F_{b}|$. This implies the Euler characteristics of $R$ and
$R_{\text{dec},w}$ are the same.

We also need to show that $R_{\text{dec},w}$ is orientable if and only if $R$
is. Note $R$ being orientable means one can partition $H$ into two sets
$H_{\pm 1}$ such that $\lambda$, $\rho$, $\tau$ applied to an element of one
set maps it to an element of the other set. Define $H^{\prime}_{\pm
1}\subseteq H^{\prime}:=H_{w}\times\\{\pm 1\\}$ such that $(h,j)\in
H_{\text{dec},k}$ if and only if $h\in H_{jk}$. These sets clearly partition
$H^{\prime}$ and $\lambda_{\text{dec}}$, $\rho_{\text{dec}}$, and
$\tau_{\text{dec}}$ all map either set to the other. So $R_{\text{dec}}$ is
orientable. The other direction – if $R_{\text{dec}}$ is orientable, then $R$
is – follows a very similar argument that we leave for the reader. ∎

Here we comment on the case where a checkerboardable graph $G$ has only
degree-4 vertices. In this case, the decoding graph has degree-2 vertices
associated to the vertices of $G$. Suppose we remove these vertices, joining
the edges incident to them into one edge. It is not hard to see that this
vertex removal makes the connected components of $G_{\text{dec}}$ into graphs
$Q$ and $\overline{Q}$ (duals of one another) where the medial graph
$\widetilde{Q}$ is equal to $G$. Therefore, in this checkerboardable and
4-valent case, the operation of building the decoding graph essentially
inverts the operation of building the medial graph. Then $Q$ is a graph that
defines a homological code (see Section 3.4) equivalent to the code we have
defined on $G$.

With the decoding graph embedded, we can relate homological and logical
nontriviality in the checkerboardable case.

######  Theorem 4.6.

For checkerboardable graph $G$, a cycle $c$ in $G_{\text{dec}}$ is
homologically nontrivial if and only if $\sigma(c)$ is a nontrivial logical
operator of the surface code associated with $G$.

  * Proof.

The key fact to use is that a Pauli $p$ is a stabilizer generator associated
to a face in $G$ if and only if $p\propto\sigma(c)$ for some facial cycle $c$
in $G_{\text{dec}}$. In Fig. 11, we show this correspondence explicitly. We
use this fact to complete the proof.

Figure 11: Picturing the correspondence between a face $f$ of checkerboardable
graph $G$ (thick, black edges) and a face $f^{\prime}$ of a connected
component of its decoding graph $G_{\text{dec}}$ (blue edges). Notation comes
from the proof of Lemma 4.5. Flags of $G$ and $G_{\text{dec}}$ are outlined by
thin lines. Flags of $G$ making up $f$ include $h$, $\rho h$, $\lambda\rho h$,
and $\rho\lambda\rho h$. These each relate to two flags in the corresponding
face $f^{\prime}$. For instance, $h\in f$ becomes $(\tau h,\pm 1)\in
f^{\prime}$. If $f$ is colored black in $G$, then $f^{\prime}$ is a face of
$G_{\text{dec},w}$.

Let $c$ be a homologically trivial cycle in $G_{\text{dec}}$. We need to show
$\sigma(c)$ is a stabilizer. Since $G_{\text{dec}}$ has two connected
components, $c=c_{w}+c_{b}$ where $c_{w}$ is a cycle in $G_{\text{dec},w}$ and
$c_{b}$ a cycle in $G_{\text{dec},b}$. Since
$\sigma(c)=\sigma(c_{w})\sigma(c_{b})$, we just show $\sigma(c_{w})$ is a
stabilizer with an analogous argument for $\sigma(c_{b})$. Since $c_{w}$ is
homologically trivial it is a sum of facial cycles
$c_{w}=c_{1}+c_{2}+\dots+c_{l}$ and
$\sigma(c_{w})=\sigma(c_{1})\sigma(c_{2})\dots\sigma(c_{l})$. By the fact in
the previous paragraph, $\sigma(c)$ is indeed a stabilizer.

Likewise, if Pauli $p$ is a stabilizer, then it is the product of stabilizer
generators associated to faces of $G$, or $p=p_{1}p_{2}\dots p_{l}$. By fact
(1), there are facial cycles $c_{1},c_{2},\dots,c_{l}$ in $G_{\text{dec}}$
such that $\sigma(c_{j})=p_{j}$ and therefore a homologically trivial cycle
$c=c_{1}+c_{2}+\dots+c_{l}$ so that $\sigma(c)=p$. ∎

In a slight abuse of notation, we let
$\mathrm{hsys}\left({G_{\text{dec}}}\right)$ be the smaller of the homological
systoles of the two connected components of $G_{\text{dec}}$ embedded as in
Lemma 4.5.

######  Corollary 4.7.

Suppose $G$ is a checkerboardable, embedded graph and $D$ is the code distance
of the surface code defined by $G$. Then,
$\frac{1}{2}\mathrm{hsys}\left({G_{\text{dec}}}\right)\leq D$ and if $G$ is
4-valent, $\frac{1}{2}\mathrm{hsys}\left({G_{\text{dec}}}\right)=D$.

  * Proof.

For the proof of the bound, note that any non-trivial logical operator with
weight $D$ is represented by a homologically non-trivial cycle $c$ confined to
a single connected component of the decoding graph $G_{\text{dec}}$. Suppose
$c$ visits $n\leq D$ vertices of $G_{\text{dec}}$ that are associated to
vertices of $G$. There is a homologically non-trivial sub-cycle of $c$, call
it $c^{\prime}$, that visits each of the $n$ vertices at most once and so has
at most $2n$ edges. Since $\mathrm{hsys}\left({G_{\text{dec}}}\right)$ lower
bounds the length of $c^{\prime}$,
$\mathrm{hsys}\left({G_{\text{dec}}}\right)\leq 2n\leq 2D$.

Now suppose $G$ is 4-valent. The shortest homologically non-trivial cycle $c$
in $G_{\text{dec}}$ is confined to just one connected component. By 4-valency,
there is only one qubit at each vertex and each two-edge sub-path in $c$ is
mapped to single-qubit Pauli by $\sigma$. Since $c$ has length
$\mathrm{hsys}\left({G_{\text{dec}}}\right)$, the weight of the non-trivial
logical Pauli it represents is at most
$\frac{1}{2}\mathrm{hsys}\left({G_{\text{dec}}}\right)$, which therefore is an
upper bound on $D$. ∎

The equality statement in this corollary does not hold for graphs with higher
degree vertices because, in that case, two-edge paths in the decoding graph
may represent Paulis of weight greater than one. However, if one uses the CAL
construction in Theorem 3.4 to assign Paulis to sectors, one can effectively
decompose these higher-degree vertices into degree-4 vertices (see Corollary
3.10) and apply Corollary 4.7 to the resulting 4-valent graph.

###  4.3 Doubled graphs

Our goal in this section is to find some manifold to embed $G_{\text{dec}}$
into when the original graph $G$ is not checkerboardable. In general, this is
a manifold with genus larger than the original surface. In particular, for any
non-checkerboardable graph $G$ embedded on a manifold $\mathcal{M}$, we show
that there is a checkerboardable graph $G^{2}$, referred to as a _doubled_
graph, embedded on manifold $\mathcal{M}^{2}$ such that $G_{\text{dec}}$ is
isomorphic to any one of the two connected components of $G^{2}_{\text{dec}}$.
A similar doubled construction is given by Barkeshli and Freedman [44] in the
context of topological phases.

Figure 12: A doubled graph for the rotated surface code of Fig. 5(b) is
embedded in the torus (six-sided blue border). Figure 13: A doubled graph for
the triangle code of Fig. 5(a) is embedded in the torus (six-sided blue
border).

Informally, the doubled manifold $\mathcal{M}^{2}$ is created by taking two
copies of $\mathcal{M}$, cutting along the edges of a defect of the embedded
graph $G$, and gluing the two copies together. This gluing is done in such a
way that in crossing from one copy of $\mathcal{M}$ to the other, a path ends
up at the same place in the destination manifold as it would have in the
original manifold if it were still intact. This means, for instance, that a
defect trail between two odd degree vertices is cut open into a disk and glued
with its corresponding disk on the other copy. In contrast, cycles in the
defect that are homologically non-trivial result in the handles or cross-caps
of the surface being cut apart before they are glued with their copies. We
provide a formal construction of the doubled graph in terms of rotation
systems and a construction of the doubled manifold subsequently. We comment
that the doubled graph $G^{2}$ depends on the choice of defect, but the
topology of $\mathcal{M}^{2}$ does not.

######  Definition 4.3.

The doubled rotation system
$R^{2}=(H^{\prime},\lambda^{\prime},\rho^{\prime},\tau^{\prime})$ of a
rotation system $R=(H,\lambda,\rho,\tau)$ with defect $\delta$ is defined by
setting $H^{\prime}=H\times\\{1,-1\\}$ and for $(h,j)\in H^{\prime}$ letting
$\lambda^{\prime}(h,j)=(\lambda(h),j)$, $\rho^{\prime}(h,j)=(\rho(h),j)$, and

$\tau^{\prime}(h,j)=\bigg{\\{}\begin{array}[]{ll}(\tau(h),-j),&\exists
e\in\delta\text{ s.t.\leavevmode\nobreak\ }h\in e\\\
(\tau(h),j),&\text{otherwise}\end{array}.$ (30)

One can study orbits of $\langle\lambda^{\prime},\rho^{\prime}\rangle$ to
relate faces of $G^{2}$ with faces of $G$. Since neither $\lambda^{\prime}$
nor $\rho^{\prime}$ acting on $(h,j)\in H^{\prime}$ flips the sign of $j$,
there are two faces in $G^{2}$ for every face of $G$, one made up of flags
with $j=1$ and one with flags $j=-1$. It turns out we can also checkerboard
$G^{2}$ such that these two faces are oppositely colored.

######  Lemma 4.8.

For any embedded graph $G$, the doubled graph $G^{2}$ is checkerboardable.

  * Proof.

Let $\delta$ be the defect used to define $G^{2}$ from $G$, and let
$R=(H,\lambda,\rho,\tau)$ be the rotation system of $G$. As $G$ is
checkerboardable with defect $\delta$, there is a partition of $H=H_{w}\sqcup
H_{b}$, where $\lambda$ and $\rho$ map either set to itself and $\tau$ maps an
element $h$ from either set to the other _except_ when $h$ is in an edge
belonging to the defect (Lemma 4.1).

Now we can partition $H^{\prime}=H\times\\{1,-1\\}$, the set of flags for the
doubled rotation system
$R^{2}=(H^{\prime},\lambda^{\prime},\rho^{\prime},\tau^{\prime})$, into two
sets

$\displaystyle H^{\prime}_{w}$ $\displaystyle=\\{(h,j):h\in H_{w},j=1\text{ or
}h\in H_{b},j=-1\\},$ (31) $\displaystyle H^{\prime}_{b}$
$\displaystyle=\\{(h,j):h\in H_{b},j=1\text{ or }h\in H_{w},j=-1\\}.$ (32)

One can check that $\lambda^{\prime}$ and $\rho^{\prime}$ map either set to
itself and $\tau^{\prime}$ maps between the sets. Thus, $G^{2}$ is
checkerboardable. ∎

Just as there are two faces in $G^{2}$ for every face in $G$, it follows from
Definition 4.3 that $G^{2}$ has two edges for every edge of $G$, two
degree-$\text{deg}(v)$ vertices for every even-degree vertex $v$ of $G$, and
one degree-$2\text{deg}(v)$ vertex for every odd-degree vertex $v$ of $G$.
This counting allows us to establish the genus of $G^{2}$.

######  Theorem 4.9.

Let $G$ be a non-checkerboardable graph containing $M$ odd-degree vertices.

  1. 1.

If $G$ embeds into a genus $g$, orientable manifold, then $G^{2}$ embeds into
a genus $2g+(M-2)/2$, orientable manifold.

  2. 2.

Suppose $G$ embeds into a genus $g$, non-orientable manifold.

    1. (a)

If $G^{2}$ embeds into an orientable manifold, its genus is $g+(M-2)/2$.

    2. (b)

If $G^{2}$ embeds into a non-orientable manifold, its genus is
$2\left(g+(M-2)/2\right)$.

  * Proof.

Part of this theorem that is implicit is that if $G$ is orientable, then
$G^{2}$ is orientable. Represent $G$ and $G^{2}$ with rotation systems as in
Definition 4.3. Then, $G$ being orientable means there is a partition of
$H=H_{+1}\sqcup H_{-1}$ such that $\lambda$, $\rho$, and $\tau$ all map
elements of either set $H_{\pm 1}$ to elements of the other. Clearly,
$H^{\prime}=H^{\prime}_{+1}\sqcup H^{\prime}_{-1}$ can also be partitioned so
that $(h,j)\in H^{\prime}_{k}$ if and only if $h\in H_{k}$. As required for
orientability, $\lambda^{\prime}$, $\rho^{\prime}$, and $\tau^{\prime}$ all
map elements of either set $H^{\prime}_{\pm 1}$ to elements of the other.

The genus of $G^{2}$ can be obtained by counting. As discussed previously, the
doubled graph has $|F^{\prime}|=2|F|$ faces, $|E^{\prime}|=2|E|$ edges, and
$|V^{\prime}|=2|V|-M$ vertices where $|F|$, $|E|$, and $|V|$ are the face,
edge, and vertex counts of $G$. The conclusions follow. ∎

Because $G^{2}$ is checkerboardable, its decoding graph $G^{2}_{\text{dec}}$
has two connected components, each embedding in the same manifold as $G^{2}$.

######  Theorem 4.10.

Either connected component of $G^{2}_{\text{dec}}$ is isomorphic to
$G_{\text{dec}}$. Moreover, homologically non-trivial cycles in
$G^{2}_{\text{dec}}$ correspond to non-trivial logical operators of the
surface code associated to $G$. If that code has distance $D$, then
$\frac{1}{4}\mathrm{hsys}\left({G^{2}_{\text{dec}}}\right)\leq
D\leq\frac{1}{2}\mathrm{hsys}\left({G^{2}_{\text{dec}}}\right)$.

  * Proof.

We describe the isomorphism by describing how vertices of $G_{\text{dec}}$ and
$G^{2}_{\text{dec},w}$ (one of the two connected components of
$G^{2}_{\text{dec}}$) are mapped to each other. There are three maps that
should be composed in the right way, the map from $G$ to $G_{\text{dec}}$, the
map from $G$ to $G^{2}$, and the map from $G^{2}$ to $G^{2}_{\text{dec},w}$.

First, note $G^{2}_{\text{dec},w}$ has a single vertex for each white face of
$G^{2}$ (which is checkerboardable). Also, $G^{2}_{\text{dec},w}$ has a single
vertex for each vertex of $G^{2}$. Next, recall $G_{\text{dec}}$ has a vertex
for each face of $G$, two vertices for each even-degree vertex of $G$, and one
vertex for each odd-degree vertex of $G$. Finally, $G^{2}$ has two
(differently colored) faces for each face of $G$, two vertices for each even-
degree vertex of $G$, and one vertex for each odd-degree vertex of $G$. With
the vertices of $G_{\text{dec}}$ and $G^{2}_{\text{dec},w}$ associated to one
another by the implied map, vertex-adjacency is also preserved, showing the
isomorphism.

We argued in Lemma 4.8 that every face of $G$ corresponds to two oppositely
colored faces of $G^{2}$. Since $G^{2}_{\text{dec},w}$ has faces corresponding
to black faces of $G^{2}$, these actually represent all the faces of $G$.
Therefore, a cycle in $G^{2}_{\text{dec},w}$ is homologically non-trivial if
and only if it is a non-trivial logical operator of the code. The upper bound
on the code distance follows immediately.

The lower bound is a result of two vertices in $G^{2}$ representing each even-
degree vertex of $G$. If a homologically non-trivial cycle in
$G^{2}_{\text{dec},w}$ crosses both of these vertices, it may represent only
one qubit of support in the corresponding logical operator. Thus, we have an
additional factor of $1/2$ compared to the upper bound. ∎

With the theory above, we have seen how the doubled manifold effectively
describes the homology of nontrivial logical operators in a higher genus
surface. One consequence for surface codes is that for every non-
checkerboardable code defined by graph $G$ with parameters $\llbracket
N,K,D\rrbracket$, there is a checkerboardable code defined by graph $G^{2}$
with parameters $\llbracket 2N,2K,D^{\prime}\rrbracket$ where $D^{\prime}\geq
D$. The checkerboardable code has the same rate and at least as good a code
distance, but with potentially higher weight stabilizers and larger genus.
Thus, non-checkerboardable codes can offer improvements over checkerboardable
codes given that stabilizer weight and genus are relevant parameters for
practical implementations.

###  4.4 Face-width as a lower-bound on code distance

The _face-width_ $\text{fw}(G)$ of an embedded graph $G$ (with genus $g>0$) is
the minimum number of times any non-contractible cycle drawn on the manifold
intersects the graph [30]. This can also be defined as the length of the
shortest non-contractible cycle in a related graph, the face-vertex graph
$G_{\text{fv}}$.

######  Definition 4.4.

The face-vertex graph $G_{\text{fv}}$ of an embedded graph $G$ is an embedded
graph possessing a vertex $w_{v}$ for each vertex $v$ of $G$ and a vertex
$u_{f}$ for each face $f$ of $G$. An edge is drawn between $w_{v}$ and $u_{f}$
if and only if $v$ and $f$ are adjacent in $G$. To specify the embedding, if
$G$ has rotation system $(H,\lambda,\rho,\tau)$, the face-vertex graph has
rotation system
$(H_{\text{fv}},\lambda_{\text{fv}},\rho_{\text{fv}},\tau_{\text{fv}})$, where
$H_{\text{fv}}=H\times\\{1,-1\\}$ and

$\displaystyle\lambda_{\text{fv}}(h,j)=(h,-j),\quad\quad\rho_{\text{fv}}(h,j)=\bigg{\\{}\begin{array}[]{ll}(\tau(h),j),&j=-1\\\
(\lambda(h),j),&j=1\end{array},\quad\quad\tau_{\text{fv}}(h,j)=(\rho(h),j).$
(35)

We point out some easily-proved facts about the face-vertex graph. First, it
is bipartite since vertices of type $w_{v}$ are only ever connected to
vertices of type $u_{f}$. Second, the face-vertex graph is the dual of the
medial graph (Definition 3.4), $\overline{\widetilde{G}}=G_{\text{fv}}$.
Third, the face-vertex graph is embedded in the same manifold as $G$. Fourth,
if we recall that a graph $G$ and its dual $\overline{G}$ have isomorphic
medial graphs, we also find that $G$ and $\overline{G}$ have isomorphic face-
vertex graphs. Finally, the face-vertex graph is the decoding graph (see Def.
4.2) with the vertices $w^{(\pm 1)}_{v}$ merged at each even-degree vertex
$v$.

Because $G_{\text{fv}}$ is bipartite,
$\mathrm{sys}\left({G_{\text{fv}}}\right)$ is even. Any cycle drawn on the
manifold is homeomorphic to a cycle in the face-vertex graph. Hence, it is
easy to see that
$\text{fw}(G)=\frac{1}{2}\mathrm{sys}\left({G_{\text{fv}}}\right)$. This is
the most convenient definition of face-width for our purposes.

The rest of this subsection is devoted to proving the following.

######  Theorem 4.11.

Suppose $G$ is an embedded graph with only even-degree vertices and genus
$g>0$. Let $D$ be the code distance of the surface code associated to $G$.
Then $\text{fw}(G)\leq D$.

To prove this theorem, we need a simple lemma, which we prove separately.

######  Lemma 4.12.

Suppose $G$ is a non-checkerboardable graph with only even-degree vertices
embedded in manifold $\mathcal{M}$ with genus $g>0$. Then the doubled graph
$G^{2}$ is embedded in a manifold $\mathcal{M}^{2}$ that is a double cover of
$\mathcal{M}$.

  * Proof.

To create the manifold $\mathcal{M}^{2}$ from the rotation system description
in Def. 4.3 (whose notation we import here), we glue the flags together
according to $\lambda^{\prime}$, $\rho^{\prime}$, $\tau^{\prime}$. Suppose we
map flags in $H^{\prime}=H\times\\{1,-1\\}$ to flags in $H$, i.e. $\Pi(h,j)=h$
for $h\in H$ and $j=\pm 1$. This map extends to a map
$\pi:\mathcal{M}^{2}\rightarrow\mathcal{M}$ by simply mapping points in the
flag $(h,j)$ to points in flag $h$ in homeomorphic fashion, i.e. if both
$(h,j)$ and $h$ are viewed as identically-sized triangular patches of surface
with boundaries associated to the $\lambda$, $\rho$, and $\tau$ involutions,
then map the former to latter point-by-point. Note that
$\Pi\circ\lambda^{\prime}=\lambda\circ\Pi$,
$\Pi\circ\rho^{\prime}=\rho\circ\Pi$, and
$\Pi\circ\tau^{\prime}=\tau\circ\Pi$. This establishes that if two flags are
glued together in $\mathcal{M}^{2}$, their images are glued together in
$\mathcal{M}$.

We should check that for all open disks $U$, $\pi^{-1}(U)$ is the union of two
open disks, thus proving it is a double cover. This is clearly true for open
disks contained entirely within a single flag $h$. We also look at open disks
that straddle two flags (across a flag’s edge) and open disks that straddle
more than two flags (because they contain a flag’s corner).

Suppose an open disk straddles two flags $h,\lambda h\in H$. Applying
$\Pi^{-1}$ to this pair of flags, we get either $(h,1)$ and
$\lambda^{\prime}(h,1)=(\lambda h,1)$ or $(h,-1)$ and
$\lambda^{\prime}(h,-1)=(\lambda h,-1)$. Thus, $\pi^{-1}$ gives two open
disks, each straddling one of these pairs of flags in $\mathcal{M}^{2}$.

The same argument holds for flags $h,\rho h$. Slightly more interesting is the
case of flags $h,\tau h$. In this case, if the edge of the graph $G$
containing $h$ is in the defect, $\Pi^{-1}$ gives either $(h,1)$ and $(\tau
h,-1)$ or $(h,-1)$ and $(\tau h,1)$. If the edge is not in the defect, then
the result is $(h,1)$ and $(\tau h,1)$ or $(h,-1)$ and $(\tau h,-1)$.

Finally, corners of the flags correspond to vertices, edges, and faces of the
graphs. An open disk at the corner $\\{h,\rho h,\lambda h,\rho\lambda h\\}$, a
face of the graph, is the most straightforward case since no defect is
involved. Here $\Pi^{-1}$ maps the face of $G$ to two faces of $G^{2}$, namely
$\\{(h,1),(\rho h,1),(\lambda h,1),(\rho\lambda h,1)\\}$ and $\\{(h,-1),(\rho
h,-1),(\lambda h,-1),(\rho\lambda h,-1)\\}$. Likewise, it is not hard to see
that an edge (containing $h$) in $G$ maps to two edges (the one containing
$(h,1)$ and the one containing $(h,-1)$) in $G^{2}$, whether or not that edge
is part of the defect. For the case of a vertex $v$ in $G$, one must recall
the fact that an even number of edges incident to $v$ are part of the defect,
Lemma 4.3. This is the only place where we are using that $G$ has only even-
degree vertices. Suppose $h\in v$. The vertices in $G^{2}$ that map to $v$
under $\Pi$ are the one containing $(h,1)$ and the one containing $(h,-1)$,
and these are distinct because of the aforementioned fact. ∎

  * Proof of Theorem 4.11.

If $G$ is checkerboardable, then notice that
$\text{fw}(G)=\frac{1}{2}\text{sys}(G_{\text{fv}})\leq\frac{1}{2}\text{sys}(G_{\text{dec}})\leq\frac{1}{2}\text{hsys}(G_{\text{dec}})=D$,
with the final equality following from Corollary 4.7.

Thus, we are left with the non-checkerboardable case. Lemma 4.12 says the
doubled manifold $\mathcal{M}^{2}$ is a double cover of the manifold
$\mathcal{M}$ on which $G$ is embedded. This means that the universal cover of
$\mathcal{M}$ (which is the plane $\mathcal{U}=\mathbb{R}^{2}$) is also the
universal cover of $\mathcal{M}^{2}$. This implies the existence of three
covering maps, the projections
$\pi_{21}:\mathcal{M}^{2}\rightarrow\mathcal{M}$,
$\pi_{U2}:\mathcal{U}\rightarrow\mathcal{M}^{2}$, and
$\pi_{U1}:\mathcal{U}\rightarrow\mathcal{M}$ such that
$\pi_{U1}=\pi_{21}\pi_{U2}$.

Now, choose a logical operator represented by some homologically non-trivial
cycle $c_{2}$ (in the decoding graph $G^{2}_{\text{dec}}$) drawn on
$\mathcal{M}^{2}$. Any lift $\pi_{U2}^{-1}(c_{2})$ is necessarily a non-closed
curve in $\mathcal{U}$. We also see that $c_{1}=\pi_{21}(c_{2})$, which is