Characterization of solvable spin models via graph invariants
Adrian Chapman and Steven T. Flammia
Centre for Engineered Quantum Systems, School of Physics, The University of Sydney, Sydney, Australia
May 27, 2020
Exactly solvable models are essential in
physics. For many-body spin-
1
/2 systems, an
important class of such models consists of
those that can be mapped to free fermions
hopping on a graph. We provide a complete
characterization of models which can be solved
this way. Specifically, we reduce the problem
of recognizing such spin models to the graph-
theoretic problem of recognizing line graphs,
which has been solved optimally. A corollary
of our result is a complete set of constant-
sized commutation structures that constitute
the obstructions to a free-fermion solution. We
find that symmetries are tightly constrained
in these models. Pauli symmetries correspond
to either: (i) cycles on the fermion hopping
graph, (ii) the fermion parity operator, or (iii)
logically encoded qubits. Clifford symmetries
within one of these symmetry sectors, with
three exceptions, must be symmetries of the
free-fermion model itself. We demonstrate
how several exact free-fermion solutions from
the literature fit into our formalism and give
an explicit example of a new model previously
unknown to be solvable by free fermions.
1 Introduction
Exactly solvable models provide fundamental insight
into physics without the need for difficult numerical
methods or perturbation theory. In the particular
setting of many-body spin-
1
/2 systems, a remarkable
method for producing exact solutions involves finding
an effective description of the system by noninteract-
ing fermions. This reduces the problem of solving
the n-spin system over its full 2
n
-dimensional Hilbert
space to one of solving a single-particle system hop-
ping on a lattice of O(n) sites. The paradigmatic
example of this method is the exact solution for the
XY model [1], where the Jordan-Wigner transforma-
tion [2] is employed to describe the model in terms
of free fermions propagating in one spatial dimension.
These fermions are resolved as nonlocal Pauli oper-
ators in the spin picture, and the nonlocal nature of
this mapping may suggest that finding generalizations
to this mapping for more complicated spin systems is
a daunting task. Of the many generalizations that
Adrian Chapman: adrian.chapman@sydney.edu.au
have since been proposed [311], a particularly inter-
esting solution to this problem is demonstrated in the
exact solution of a 2-d spin model on a honeycomb
lattice introduced by Kitaev [12]. For this model, the
transformation to free-fermions can be made locality-
preserving over a fixed subspace through the use of
local symmetries.
The dynamics of free-fermion systems are generated
by Gaussian-fermionic Hamiltonians and correspond
to the class of so-called matchgate circuits. This cir-
cuit class coincides with the group of free-fermion
propagators generated by arbitrarily time-dependent
single-particle Hamiltonians [13, 14] and has an ex-
tensive complexity-theoretic characterization. In gen-
eral, matchgate circuits can be efficiently simulated
classically with arbitrary single-qubit product-state
inputs and measurement [15, 16]. However, they be-
come universal for quantum computation with the in-
troduction of non-matchgates such as the SWAP gate
[17, 18], certain measurements and resource inputs
[19, 20], and when acting on nontrivial circuit geome-
tries [21]. Furthermore, these circuits share an inter-
esting connection to the problem of counting the num-
ber of perfect matchings in a graph, which is the con-
text in which they were first developed [2225]. This
problem is known to be very hard computationally
(it is #P-complete [26]), but is efficiently solved for
planar graphs using the so-called Fisher-Kasteleyn-
Temperley algorithm [27, 28].
In this work, we develop a distinct connection be-
tween free-fermion systems and graph theory by using
tools from quantum information science. The cen-
tral object of our formalism is the frustration graph.
This is a network quantifying the anticommutation
structure of terms in the spin Hamiltonian when it is
expanded in the basis of Pauli operators [29]. This
graph has been invoked previously in the setting of
variational quantum eigensolvers [3037], commonly
under the name “anti-compatibility graph". We show
that the problem of recognizing whether a given spin
model admits a free-fermion solution is equivalent to
that of recognizing whether its frustration graph is a
line graph, which can be performed optimally in lin-
ear time [3840]. From the definition of a line graph,
it will be clear that such a condition is necessary, but
we will show that it is also sufficient. When the con-
dition is met, we provide an explicit solution to the
model.
Line graphs have recently emerged as the natural
Accepted in Quantum 2020-05-20, click title to verify. Published under CC-BY 4.0. 1
arXiv:2003.05465v2 [quant-ph] 27 May 2020
structures describing the effective tight-binding mod-
els for superconducting waveguide networks [4143].
In this setting, the line graph corresponds to the phys-
ical hopping graph of photons in the network. We
will see how this scenario is a kind of “inverse prob-
lem" to the one we consider, wherein fermions are
hopping on the root of the line graph. It is clear
from both scenarios that the topological connectivity
structure of many-body systems plays a central role
in their behavior, and it is remarkable that this is al-
ready being observed in experiments. We expect that
further investigation of the graph structure of many-
body Hamiltonians will continue to yield important
insights into their physics.
1.1 Summary of Main Results
Here we give a brief summary of the main results. We
first define the frustration graph of a Hamiltonian,
given in the Pauli basis, as the graph with nonzero
Pauli terms as vertices and an edge between two ver-
tices if their corresponding terms anticommute. A line
graph G of a graph R is the intersection graph of the
edges of R as two-element subsets of the vertices of R.
With these simple definitions, we can informally state
our first main result, which we call our “fundamental
theorem:"
Result 1 (Existence of free-fermion solution; Infor-
mal version of Thm. 1). Given an n-qubit Hamilto-
nian in the Pauli basis for which the frustration graph
G is the line graph of another graph R, then there
exists a free-fermion description of H.
From this description, an exact solution for the
spectrum and eigenstates of H can be constructed.
This theorem illustrates a novel connection between
the physics of quantum many-body systems and graph
theory with some surprising implications. First, it
gives the exact correspondence between the spatial
structure of a spin Hamiltonian and that of its effec-
tive free-fermion description. As we will see through
several examples, this relationship is not guaranteed
to be straightforward. Second, the theorem gives an
exact condition by which a spin model can fail to have
a free-fermion solution, the culprit being the presence
of forbidden anticommutation structures in the frus-
tration graph of H.
Some caveats to Result 1 (that are given precisely
in the formal statement, Theorem 1) involve cases in
which this mapping between Pauli terms in H and
fermion hopping terms is not one-to-one. In particu-
lar, if we are given a Hamiltonian whose frustration
graph is not a line graph, then a free-fermion solu-
tion may still be possible via a non-injective mapping
over a subspace defined by fixing stabilizer degrees of
freedom. Additionally, it is possible for a given spin
Hamiltonian to describe multiple free-fermion models
simultaneously, each generating dynamics over an in-
dependent stabilizer subspace of the full Hilbert space
as for the Kitaev honeycomb model [12]. These sym-
metries are sometimes referred to as gauge degrees of
freedom, though we will reserve this term for freedoms
which cannot affect the physics of the free-fermion
model. Finally, it may be the case that the free-
fermion model contains states which are nonphysical
in the spin-Hamiltonian picture, and so these must be
removed by fixing a symmetry as well. Luckily, all of
these cases manifest as structures in the frustration
graph of H. The first, regarding when a non-injective
free-fermion solution is required, is signified by the
presence of so-called twin vertices, or vertices with
the same neighborhood. We deal with this case in
our first lemma. The next two cases are covered by
our second theorem:
Result 2 (Graphical symmetries; Informal version of
Thm. 2). Given an n-qubit Hamiltonian in the Pauli
basis for which the frustration graph G is the line
graph of another graph R, then Pauli symmetries of
H correspond to either:
(i) Cycles of R;
(ii) A T-join of R, associated to the fermion-parity
operator;
(iii) Logically encoded qubits;
and these symmetries generate an abelian group.
We then prove that we can always fix all of the cy-
cle symmetries by choosing an orientation of the root
graph R. Our results also relate the more general class
of Clifford symmetries to the symmetries of the single-
particle free-fermion Hamiltonian. We show that with
exactly three exceptions, Clifford symmetries of the
spin model, in a subspace defined by fixing the sym-
metries listed above, must also be symmetries of the
single-particle Hamiltonian (see Corollary 1.2 for a
precise statement).
Finally, we illustrate these ideas with several ex-
amples: small systems of up to 3 qubits, the 1-
dimensional anisotropic XY model in a transverse
field and its nearest-neighbor solvable generalization,
the Kitaev honeycomb model, the 3-dimensional frus-
trated hexagonal gauge color code [44], and the
Sierpinski-Hanoi model. To the best of our knowl-
edge, this last model was previously not known to be
solvable.
The remainder of the paper is organized as fol-
lows. In Section 2, we will introduce notation and give
some background on the formalism of free-fermions
and frustration graphs. In Section 3, we will for-
mally state Theorem 1 and some general implications
thereof. In Section 4, we elaborate on the structure of
symmetries which can be present in our class of solv-
able models. In Section 4.1, we will use the theorems
of the previous two sections to outline an explicit so-
lution method. We close by demonstrating how the
examples of free-fermion solutions listed above fit into
this formalism in Section 5.
Accepted in Quantum 2020-05-20, click title to verify. Published under CC-BY 4.0. 2
2 Background
2.1 Frustration Graphs
The models we consider are spin-
1
/2 (qubit) Hamilto-
nians written in the Pauli basis
H =
X
jV
h
j
σ
j
, (1)
where j (a, b), with a, b {0, 1}
×n
labeling an
n-qubit Pauli operator as
σ
j
= i
a·b
n
O
k=1
X
a
k
k
!
n
O
k=1
Z
b
k
k
!
. (2)
The exponent of the phase factor, a · b, is the Eu-
clidean inner product between a and b. This phase
is chosen such that the overall operator is Hermitian,
and such that a
k
= b
k
= 1 means that σ
j
acts on
qubit k by a Pauli-Y operator. We denote the full
n-qubit Pauli group by P, and V P is the set of
Pauli terms in H (i.e. h
j
= 0 for all j / V ). Let the
Pauli subgroup generated by this set be denoted P
H
.
For our purposes, what is important is not the ex-
plicit Pauli description of the Hamiltonian, but rather
the commutation relations between its terms. As
Pauli operators only either commute or anticommute,
a useful quantity is their scalar commutator [[·, ·]],
which we define implicitly as
σ
j
σ
k
= [[σ
j
, σ
k
]]σ
k
σ
j
. (3)
The scalar commutator thus only takes the values ±1.
Additionally, the scalar commutator distributes over
multiplication in each argument, e.g.
[[σ
j
, σ
k
σ
l
]] = [[σ
j
, σ
k
]][[σ
j
, σ
l
]]. (4)
For n-qubit Paulis, the scalar commutator can thus
be read off from the Pauli labels as
[[σ
j
, σ
k
]] = (1)
hj,ki
(5)
Here, hj, ki is the symplectic inner product
hj, ki
a
j
b
j
0
n
I
n
I
n
0
n
a
k
b
k
, (6)
where naturally j (a
j
, b
j
) and k (a
k
, b
k
). 0
n
is the n × n all-zeros matrix, and I
n
is the n × n
identity matrix. Eq. (5) captures the fact that a factor
of 1 is included in the scalar commutator for each
qubit where the operators σ
j
and σ
k
differ and neither
acts trivially. Since the inner product appears as the
exponent of a sign factor, without loss of generality,
we can replace it with the binary symplectic inner
product
hj, ki
2
hj, ki mod 2. (7)
H
P
j∈{x,y,z}
h
j
σ
j
P
j∈{0,x,y,z}
×2
j6=(0,0)
h
j
σ
j
G(H)
' L(R)
R or
Table 1: Example frustration graphs for general Hamiltonians
on small (1- and 2-qubit) systems. (Left column) For general
single-qubit Hamiltonians, the frustration graph is the com-
plete graph on three vertices, K
3
. By the Whitney isomor-
phism theorem [45], K
3
is the only graph which is not the line
graph of a unique graph, but rather is the line graph of both
K
3
and the ‘claw’ graph, K
1,3
. This implies the existence of
two distinct free-fermion solutions of single-qubit Hamilto-
nians. (Right column) For general two-qubit Hamiltonians,
the frustration graph is the line graph of the complete graph
on six vertices K
6
[29, 46]. Colored are the size-five cliques
corresponding to the degree-five vertices of the root graph.
This mapping implies the existence of a free-fermion solution
for general two-qubit Hamiltonians by six fermions, reflecting
the accidental Lie-algebra isomorphism su(4) ' spin(6) (see
Section 5.1).
Through the binary symplectic inner product, the
scalar commutator defines a symmetric binary rela-
tion between terms in the Hamiltonian, to which we
associate the adjacency matrix of a graph. Denote
the frustration graph for a Hamiltonian of the form
in Eq. (1) by G(H) (V, E) with vertex set given by
the Pauli terms appearing in H, and edge set
E {(j, k)|hj, ki
2
= 1} (8)
That is, two Pauli terms correspond to neighbor-
ing vertices in G(H) if and only if they anticom-
mute. Without loss of generality, we can assume
that G(H) is connected, as disconnected components
of this graph correspond to commuting collections of
terms in the Hamiltonian and can thus be indepen-
dently treated. As such, we will further assume that
H has no identity component in the expansion (1)—
rendering it traceless—since this will only contribute
an overall energy shift to the system with no effect on
dynamics.
2.2 Majorana Fermions
A related set of Hermitian operators which only ei-
ther commute or anticommute is that of the Majorana
Accepted in Quantum 2020-05-20, click title to verify. Published under CC-BY 4.0. 3
fermion modes {γ
µ
}
µ
, which satisfy the canonical an-
ticommutation relations
γ
µ
γ
ν
+ γ
ν
γ
µ
= 2δ
µν
I, (9)
and for which γ
µ
= γ
µ
. A familiar way of realizing
these operators in terms of n-qubit Pauli observables
is through the Jordan-Wigner transformation
γ
2j1
=
j1
O
k=1
Z
k
X
j
γ
2j
=
j1
O
k=1
Z
k
Y
j
. (10)
The Pauli operators on the right can easily be veri-
fied to constitute 2n operators satisfying Eq. (9). Of
course, we will explore the full set of generalizations to
this transformation in this work. We seek to identify
those qubit Hamiltonians which can be expressed as
quadratic in the Majorana modes. Such free-fermion
Hamiltonians are written as
e
H = iγ · h · γ
T
2i
X
(j,k)
e
E
h
jk
γ
j
γ
k
(11)
where γ is a row-vector of the Majorana operators,
and h is the single-particle Hamiltonian. Without loss
of generality, h can be taken as a real antisymmetric
matrix, as we can similarly assume
e
H is traceless,
and the canonical anticommutation relations Eq. (9)
guarantee that any symmetric component of h will
not contribute to
e
H.
e
E is the edge-set of the fermion-
hopping graph R (
e
V ,
e
E) on the fermion modes
e
V .
That is, h
jk
= 0 for those pairs (j, k) /
e
E, and the
factor of two in the rightmost expression accounts for
the fact that each edge in
e
E is included only once in
the sum.
As a result of the canonical anticommutation rela-
tions (9), the individual Majorana modes transform
covariantly under the time evolution generated by
e
H
e
i
e
Ht
γ
µ
e
i
e
Ht
=
X
ν
e
V
e
4ht
µν
γ
ν
(12)
since
[γ · h · γ
T
, γ
µ
] = 4(h · γ
T
)
µ
. (13)
Since h is antisymmetric and real, e
4ht
SO(2n, R).
Thus, h can be block-diagonalized via a real orthog-
onal matrix, W SO(2n, R), as
W
T
· h · W =
n
M
j=1
0 λ
j
λ
j
0
(14)
We can represent W as the exponential of a quadratic
Majorana fermion operator as well, by defining
W e
4w
, (15)
e
H is therefore diagonalized as
e
γ·w·γ
T
e
He
γ·w·γ
T
= iγ ·
W
T
· h · W
· γ
T
(16)
= 2i
n
X
j=1
λ
j
γ
2j1
γ
2j
(17)
e
γ·w·γ
T
e
He
γ·w·γ
T
= 2
n
X
j=1
λ
j
Z
j
(18)
Note that the exact diagonalization can be performed
with reference to the quadratics in the Majorana
fermion modes only. To completely solve the system,
it is only necessary to diagonalize h classically, find a
generating matrix w, and diagonalize
e
H using an ex-
ponential of quadratics with regard to some fermion-
ization like Eq. (10). Eigenstates of
e
H can be found
by acting e
γ·w·γ
T
on a computational basis state |xi
for x {0, 1}
×n
. The associated eigenvalue is
E
x
= 2
n
X
j=1
(1)
x
j
λ
j
(19)
Therefore, systems of the form in Eq. (11) may be
considered exactly solvable classically, since their ex-
act diagonalization is reduced to exact diagonalization
on a poly(n)-sized matrix h.
3 Fundamental Theorem
As mentioned previously, we seek to characterize the
full set of Jordan-Wigner-like transformations, gen-
eralizing Eq. (10). To be more precise, we ask for
the conditions under which there exists a mapping
φ : V 7→
e
V
×2
, for some set
e
V (the fermion modes),
effecting
σ
j
7→
φ
1
(j)
γ
φ
2
(j)
, (20)
for φ
1
(j), φ
2
(j)
e
V , and such that
[[σ
j
, σ
k
]] = [[γ
φ
1
(j)
γ
φ
2
(j)
, γ
φ
1
(k)
γ
φ
2
(k)
]] (21)
for all pairs, j and k. Such a mapping induces a term-
by-term free-fermionization of the Hamiltonian (1) to
one of the form (11) such that
G(H) ' G(
e
H). (22)
Again, G(H) is the frustration graph of H.
From the canonical anticommutation relations,
Eq. (9), and the distribution rule Eq. (4), we see that
scalar commutators between quadratic Majorana-
fermion operators are given by
[[γ
µ
γ
ν
, γ
α
γ
β
]] = (1)
|(µ,ν)(α,β)|
(23)
Eqs. (22) and (23) can be restated graph theoretically
as saying that G(H) is the graph whose vertex set is
the edge set of the fermion hopping graph R, and
vertices of G(H) are neighboring if and only if the
associated edges of R share exactly one vertex. Such
a graph is called the line graph of R.
Accepted in Quantum 2020-05-20, click title to verify. Published under CC-BY 4.0. 4
Definition 1 (Line Graphs). The line graph L(R)
(E, F ) of a root graph R (V, E) is the graph whose
vertex set is the edge set of R and whose edge set is
given by
F {(e
1
, e
2
) | e
1
, e
2
E, |e
1
e
2
| = 1} (24)
That is, vertices are neighboring in L(R) if the corre-
sponding edges in R are incident at a vertex.
Notice that if L(R) is connected if and only if R is.
With these definitions in-hand, our first main result
can be stated simply as
Theorem 1 (Existence of free-fermion solution). An
injective map φ as defined in Eq. (20) and Eq. (21)
exists for the Hamiltonian H as defined in Eq. (1) if
and only if there exists a root graph R such that
G(H) ' L(R), (25)
where R is the hopping graph of the free-fermion so-
lution.
Proof. The proof can be found in Section 6.1.
The intuition for this result is that the root graph
R is the graph where the vertices are fermions and
the edges are the bilinears that appear in the Hamil-
tonian H. The result reveals a correspondence be-
tween a characterization of line graphs and a char-
acterization of free-fermion spin models, as not every
graph can be expressed as the line graph of some root.
We must however note that, strictly speaking, the ex-
istence of this mapping alone does not guarantee a
free-fermion solution, since the “Lie-homomorphism"
constraint, Eq. (21), does not fix the sign of the terms
in the free-fermion Hamiltonian. Choosing a sign for
each term is equivalent to orienting the root graph,
since multiplying by a sign is equivalent to making the
exchange φ
1
(j) φ
2
(j) in Eq. (20). Different orien-
tations may not faithfully reproduce the properties of
H, but we will see that such an orientation can al-
ways be chosen. The line graph condition in Eq. (25)
is therefore necessary and sufficient for a free-fermion
solution to exist. Before turning to further implica-
tions of Theorem 1, let us first detail some properties
of line graphs.
Line graphs are closely related to so-called intersec-
tion graphs, originally studied by Erdős [50] and oth-
ers (see, for example, Ref. [51]). An intersection graph
G (V, E) is a graph whose vertex set, V 2
S
, con-
sists of distinct subsets of some set S. Two vertices,
u and v, are neighboring in G if their intersection is
nonempty (|v w| 6= 0). A line graph is a special
case of an intersection graph where every vertex cor-
responds to a subset of size at most two. When we
specify that φ be injective, we are requiring that no
distinct vertices have identical subsets, and our def-
inition of a free-fermion solution Eq. (25) identically
coincides with that of a line graph. Since terms in
H can thus intersect by at most one Majorana mode,
collections of terms containing a given mode are all
neighboring in G(H), so this mode corresponds to a
clique, or complete subgraph, of G(H). This charac-
terization of line graphs was first given by Krausz [52]
and bears stating formally.
Definition 2 (Krausz decomposition of line graphs).
Given a line graph G ' L(R), there exists a partition
of the edges of G into cliques such that every vertex
appears in at most two cliques.
Cliques in G(H) can therefore be identified with the
individual Majorana modes in a free-fermion solution
of H. If a term belongs to only one clique, we can en-
sure our resulting fermion Hamiltonian is quadratic by
taking the second clique for that term to be a clique
of no edges, as we will see in several examples below.
The existence of a Krausz decomposition is utilized
in a linear-time algorithm to recognize line graphs by
Roussopoulos [38], though the earliest such algorithm
for line-graph recognition was given by Lehot [39].
A dynamic solution was later given by Degiorgi and
Simon [40]. These algorithms are optimal and con-
structive, and so can be applied to a given spin model
to provide an exact free-fermion solution.
We next turn to the hereditary property of line
graphs, for which we require the following definition:
Definition 3 (Induced subgraphs). Given a graph
G (V, E), an induced subgraph of G by a subset of
vertices V
0
V , is a graph G[V
0
] (V
0
, E
0
) such that
for any pair of vertices u, v V
0
, (u, v) E
0
if and
only if (u, v) E in G.
An induced subgraph of G can be constructed by re-
moving the subset of vertices V /V
0
from G, together
with all edges incident to any vertex in this subset.
Line graphs are a hereditary class of graphs in the
sense that any induced subgraph of a line graph is also
a line graph. This coincides with our intuition that re-
moving a term from a free-fermion Hamiltonian does
not change its free-fermion solvability. Conversely,
Hamiltonians for which no free-fermion solution exists
are accompanied by “pathological" structures in their
frustration graphs, which obstruct a free-fermion de-
scription no matter how we try to impose one. This is
captured by the forbidden subgraph characterization
of Beineke [47] and later refined by others [48, 49].
Corollary 1.1 (Beineke no-go theorem). A given
spin Hamiltonian H has a free-fermion solution if and
only if its frustration graph G(H) does not contain
any of nine forbidden subgraphs, shown in Table 2,
(a) (d) (e), as an induced subgraph.
These forbidden subgraphs above can be interpreted
as collections of “frustrating" terms. At least one of
the terms must be assigned to a fermion interaction
in every possible assignment from Pauli operators to
Accepted in Quantum 2020-05-20, click title to verify. Published under CC-BY 4.0. 5
With Twins Without twins
Forbidden
Graphs
(a) (d)
Twin-Free,
L(R)
(b)
Root R
(c)
(e)
Table 2: A graph is a line graph if and only if it does not contain any of the nine forbidden graphs in (a), (d), and (e) as
an induced subgraph [47]. Of these nine graphs, the three in (a) contain twin vertices, highlighted. If these three graphs are
induced subgraphs of a frustration graph such that these highlighted vertices are twins in the larger graph, then the twins can
be removed by restricting onto a fixed mutual eigenspace of their products, which correspond to constants of motion of the
Hamiltonian. (b) The twin-free restrictions of the graphs in (a), with all but one highlighted vertex from (a) removed. These
graphs are the line graphs of the graphs in (c). In Ref. [48], it was shown that only five graphs contain the forbidden subgraphs
in (e) and none of those in (a) or (d). Finally, this set was further refined in Ref. [49] to a set of three forbidden subgraphs
for 3-connected line graphs of minimum degree at least seven, though we do not display these graphs here.
fermions. Correspondingly, ignoring these terms by
removing their corresponding vertices from the frus-
tration graph may remove a forbidden subgraph and
cause the Hamiltonian to become solvable. The terms
which we need to remove in this way need not be
unique. In the next section, we discuss one such strat-
egy for removing vertices such that our solution will
remain faithful to the original spin Hamiltonian by
exploiting symmetries.
4 Symmetries
An important class of symmetries involves twin ver-
tices in the frustration graph.
Definition 4 (Twin Vertices). Given a graph G
(V, E), vertices u, v V are twin vertices if, for every
vertex w V , (u, w) E if and only if (v, w) E.
Twin vertices have exactly the same neighborhood,
and are thus never neighbors in a frustration graph,
which contains no self edges due to the fact that every
operator commutes with itself. Sets of twin vertices
are the subject of our first lemma.
Lemma 1 (Twin vertices are constants of motion).
Suppose a pair of terms σ
j
and σ
k
in H correspond
to twin vertices in G(H), then the product σ
j
σ
k
is a
nontrivial Pauli operator commuting with every term
in the Hamiltonian. Distinct such products therefore
commute with each other.
Proof. The statement follows straightforwardly from
the definition of twin vertices: every term in H (in-
cluding σ
j
and σ
k
themselves) either commutes with
both σ
j
and σ
k
or anticommutes with both of these
operators. Terms in H therefore always commute
with the product σ
j
σ
k
. This product is furthermore
a nontrivial Pauli operator, for if σ
j
σ
k
= I, then
j = k, and we would not identify these Paulis with
distinct vertices in G(H). Constants of motion gener-
ated this way must commute with one another, since
they commute with every term in the Hamiltonian
and are themselves products of Hamiltonian terms.
They therefore generate an abelian subgroup of the
symmetry group of the Hamiltonian.
Let the symmetry subgroup generated by products
of twin vertices in this way be denoted S. We can
leverage these symmetries to remove twin vertices
from the frustration graph G(H). To do this, choose
a minimal generating set {σ
s
} of Pauli operators for
S and choose a ±1 eigenspace for each. Let (1)
x
s
be the eigenvalue associated to the generator σ
s
S,
for x
s
{0, 1}. We restrict to the subspace defined
as the mutual +1 eigenspace of the stabilizer group
S
x
= h(1)
x
s
σ
s
i (26)
For a pair of twin vertices corresponding to Hamilto-
nian terms σ
j
and σ
k
, we let
σ
j
σ
k
(1)
d
j,k
Y
sS
j,k
(1)
x
s
σ
s
(27)
where d
j,k
{0, 1} specifies the appropriate sign fac-
tor, and S
j,k
is the subset of generators of S such
Accepted in Quantum 2020-05-20, click title to verify. Published under CC-BY 4.0. 6
that
M
sS
j,k
s = j k (28)
where denotes addition modulo 2 here. In the
stabilizer subspace of S
x
, we can make the substitu-
tion
σ
k
(1)
d
j,k
σ
j
(29)
effectively removing the vertex k from G(H).
Twin vertices capture the cases where a free-fermion
solution for H exists, but is necessarily non-injective.
Indeed, note that we are careful in our statement of
Theorem 1 to specify that our condition Eq. (25) is
necessary and sufficient when φ is injective. If we
instead relax our requirement that vertices of a line
graph correspond to distinct subsets of size two in our
earlier discussion of intersection graphs, then we are
allowing for line graphs of graphs with multiple edges,
or multigraphs. However, our definition of G(
e
H) will
differ from the line graph of a multigraph for pairs of
vertices corresponding to identical edges, which must
be adjacent in the line graph of a multigraph, but will
be nonadjacent in G(
e
H) from Eq. (23). Such vertices
will nevertheless be twin vertices in G(
e
H) due to the
graph-isomorphism constraint, Eq. (22). Therefore,
if no injective mapping φ satisfying Theorem 1 ex-
ists, a many-to-one free-fermion solution exists only
when twin vertices are present. Lemma 1 allows us
to deal with this non-injective case by removing twin
vertices until we obtain the line graph of a simple
graph when possible. The particular way we choose
to perform this removal cannot affect the overall solv-
ability of the model, since the frustration graph with
all twin vertices removed is an induced subgraph of
any frustration graph with only a proper subset of
such vertices removed. A model which is solvable by
free fermions this way is therefore solvable in all of its
symmetry sectors.
Finally, we can see when a non-injective free-
fermion solution may be possible from the forbidden
subgraph characterization, Corollary 1.1. As seen in
Table 2, some of the forbidden subgraphs shown in
(a) themselves contain twin vertices. If these forbid-
den subgraphs are connected to the global frustration
graph such that their twin vertices remain twins in
the larger graph, then they may be removed, possibly
allowing for a solution of the full Hamiltonian by free
fermions. When the twins are removed from the for-
bidden subgraphs, they become line graphs as shown
in Table 2 (b) and (c). An example of a model which
can be solved this way is the Heisenberg-Ising model
introduced in Ref. [1].
We next proceed to identify the remaining Pauli
symmetries for a Hamiltonian satisfying Theorem 1.
For this, we invoke the natural partition of the Pauli
group P into the subgroup P
H
, again defined as that
generated by Hamiltonian terms {σ
j
}
jV
, and the
Pauli operators outside this subgroup, P
P/P
H
.
Note that the latter set does not form a group in gen-
eral, as for example, single-qubit Paulis may be out-
side of P
H
yet may be multiplied to operators in P
H
.
A subgroup of the symmetries of the Hamiltonian is
the center Z(P
H
) of P
H
, the set of n-qubit Pauli oper-
ators in P
H
which commute with every element of P
H
and therefore with every term in the Hamiltonian. To
characterize this group, we need two more definitions.
Definition 5 (Cycle subgroup). A cycle of a graph
G (V, E) is a subset of its edges, Y E, such
that every vertex contains an even number of incident
edges from the subset. If a Pauli Hamiltonian satis-
fies Eq. (25) for some root graph R, we define its cycle
subgroup Z
H
P
H
as the abelian Pauli subgroup gen-
erated by the cycles {Y
i
}
i
of R,
Z
H
=
Π
{j|φ(j)Y
i
}
σ
j
i
. (30)
Since
Y
{j|φ(j)Y
i
}
γ
φ
1
(j)
γ
φ
2
(j)
= ±I (31)
we have, from Eq. (21) and the definition of φ, that
the elements of Z
H
commute with every term in the
Hamiltonian and thus with each other (since they
are products of Hamiltonian terms). That is, Z
H
Z(P
H
). Notice that the definition of the generators
for Z
H
in Eq. (30) may sometimes yield operators
proportional to identity.
A familiar symmetry of free-fermion Hamiltonians
is the parity operator
P i
1
2
|
e
V |(|
e
V |−1)
Y
k
e
V
γ
k
(32)
which commutes with every term in the Hamiltonian
since each term is quadratic in the Majorana modes.
The phase factor is chosen such that P is Hermi-
tian. Here, we define this operator in terms of Pauli
Hamiltonian terms through a combinatorial structure
known as a T-join.
Definition 6 (Parity operator). A T-join of a graph
G (V, E) is a subset of edges, T E, such that
an odd number of edges from T is incident to every
vertex in V . If a Pauli Hamiltonian satisfies Eq. (25)
for some root graph R such that the number of vertices
in R is even, we define the parity operator as
P i
d
Y
jT
σ
j
(33)
where the product is taken over a T-join of R, and
d {0, 1, 2, 3} specifies the phase necessary to agree
with Eq. (32).
Here we have
i
d
Y
jT
φ
1
(j)
γ
φ
2
(j)
= i
1
2
|
e
V |(|
e
V |−1)
Y
µ
e
V
γ
µ
= P , (34)
Accepted in Quantum 2020-05-20, click title to verify. Published under CC-BY 4.0. 7
since every fermion mode will be hit an odd number
of times in the T-join. Unlike with the cycle sub-
group, P is never proportional to the identity in the
fermion description, though it may still be propor-
tional to the identity in the Pauli description (up to
stabilizer equivalences). In this case, only solutions
for the free-fermion Hamiltonian in a fixed-parity sub-
space will be physical. We will see several examples
of this in the next section.
When no T-join exists, we cannot form P as a prod-
uct of Hamiltonian terms. In fact, P Z(P
H
) only
when |
e
V | is even. Now with these definitions in hand,
we are ready to state our second theorem.
Theorem 2 (Symmetries are cycles and parity).
Given a Hamiltonian satisfying Eq. (25) such that the
number of vertices |
e
V | in the root graph is odd, then
we have
Z(P
H
) = Z
H
. (35)
If the number of vertices in the root graph is even,
then we have
Z(P
H
) = hZ
H
, P i . (36)
Proof. The proof can be found in Section 6.2.
The Pauli symmetries of the Hamiltonian outside
of Z(P
H
) may be thought of as “logical" or “gauge"
qubits, and this characterization allows for a simple
accounting of these qubits. Suppose we express a spin
Hamiltonian H on n qubits as a free-fermion Hamil-
tonian on the hopping graph R = (
e
V ,
e
E), and let
|Z(P
H
)| be the number of independent generators of
Z(P
H
). The number of logical qubits n
L
of the model
is given by
n
L
n
h
1
2
(|
e
V | 1) + |Z(P
H
)|
i
|
e
V | odd
n
h
1
2
(|
e
V | 2) + |Z(P
H
)|
i
|
e
V | even
.
(37)
This follows from the fact that the F
2
-rank of the ad-
jacency matrix of G(H) is twice the number of qubits
spanned by the fermionic degrees of freedom in the
model, and also the number of vertices of the root
graph R up to a constant shift.
Finally, we note that there may be additional sym-
metries, such as translation invariance, if the coeffi-
cients h
j
themselves satisfy a symmetry. Our charac-
terization will allow us to say something about this
situation when the associated symmetry transforma-
tion is a Clifford operator—that is, a unitary operator
in the normalizer of the Pauli group—commuting with
the Pauli symmetries in Z(P
H
), such as, e.g., a spa-
tial translation. The following statement follows from
a theorem by Whitney [45] (and extended to infinite
graphs in [53]).
R L(R)
Table 3: The Whitney isomorphism theorem [45] guarantees
that the edge automorphisms exchanging e and e
0
in the
graphs R in the left column, or corresponding vertices in
their line graphs on the right, which cannot be realized by
any vertex automorphism of R, are the only such cases.
Corollary 1.2 (Clifford Symmetries and Whitney
Isomorphism). Let
e
H = iγ · h · γ
T
be a free-fermion
Hamiltonian with single-particle Hamiltonian h in a
fixed symmetry sector of Z(P
H
). Then any uni-
tary Clifford symmetry U such that U
e
HU =
e
H in-
duces a signed permutation symmetry u such that
h = u
T
· h · u, except for when U induces one of
the three edge isomorphisms shown in Table 3.
Proof. This follows from the Whitney isomorphism
theorem: except for the three cases shown in Table 3,
any adjacency-preserving permutation of the vertices
of G(
e
H) is induced by an adjacency-preserving per-
mutation of the vertices of R. A Clifford symmetry U
acts as a signed permutation of the Hamiltonian terms
which preserves
e
H. Suppose the associated unsigned
permutation is not one of the exceptional cases, and
so is induced by a permutation π on the vertices of R.
This gives
e
H = U
e
HU (38)
= i
X
(j,k)
e
E
h
jk
U
γ
j
U
U
γ
k
U
(39)
= i
X
(j,k)
e
E
(1)
x
j
+x
k
h
jk
γ
π(j)
γ
π(k)
(40)
where x
j
{0, 1} designates the sign associated to
the permutation of vertex j
e
V . By unitarity, this
Accepted in Quantum 2020-05-20, click title to verify. Published under CC-BY 4.0. 8
sign must depend on j alone, since U
γ
j
U can only
depend on j. Let u be a single-particle transition
matrix defined as
u
jk
= (1)
x
j
δ
(j)
. (41)
Then we can reinterpret Eq. (40) in the single-particle
picture as
iγ · h · γ
T
= iγ ·
u
T
· h · u
· γ
T
. (42)
By linear independence, Eq. (42) therefore implies
h = u
T
· h · u (43)
and the claim follows.
See section 5.1 for a simple example of an ex-
ceptional Hamiltonian realizing a frustration graph
shown in Table 3. We now complete our characteriza-
tion of free-fermion solutions by choosing an orienta-
tion for every edge in the root graph over a restricted
subspace determined by the constants of motion.
4.1 Orientation and Full Solution
As discussed previously, the Lie-homomorphism con-
dition Eq. (21) does not fully constrain the free-
fermion solution of a given Pauli Hamiltonian. This
is because we are free to choose a direction to each
edge in the root graph by exchanging φ
1
(j) φ
2
(j),
which is equivalent to changing the sign of the term
φ
1
(j)
γ
φ
2
(j)
in
e
H corresponding to σ
j
in H. A re-
lated ambiguity corresponds to the cycle symmetry
subgroup Z
H
: we are free to choose a symmetry sec-
tor over which to solve the Hamiltonian H by choos-
ing a mutual ±1-eigenspace of independent nontrivial
generators of this group. It will turn out that both
ambiguities are resolved simultaneously.
First suppose we have a Hamiltonian H satisfying
Eq. (25) for some root graph R (
e
V ,
e
E). Construct
a spanning tree Υ (
e
V ,
e
E
0
) of R, defined as:
Definition 7 (Spanning Tree). Given a connected
graph G (V, E), a spanning tree Υ (V, E
0
) G is
a connected subgraph of G such that E
0
contains no
cycles.
This can be performed in linear time in |
e
V |. Designate
a particular vertex v
e
V as the root of this tree. Each
vertex u
e
V has a unique path p(u, v)
e
E in Υ to
the root, the path p(v, v) being empty. Choose an
arbitrary direction for each edge in
e
E
0
(we will see
shortly to what extent this choice is important).
Our choice of spanning tree determines a basis of
fundamental cycles for the binary cycle space of R and
thus a generating set of Paulis for the cycle subgroup
Z
H
. To see this, note that for each edge φ(j)
e
E/
e
E
0
,
there is a unique cycle of R given by
Y
j
p[φ
1
(j), v] p[φ
2
(j), v] φ(j). (44)
Let σ
y(j)
be the cycle subgroup generator associated
to Y
j
, defined by
y(j) =
M
{z|φ(z)Y
j
}
z (45)
such that
σ
y(j)
= i
d
Y
{z|φ(z)Y
j
}
σ
z
(46)
where d {0, 1, 2, 3} again designates the appropriate
phase. The set of such Y
j
contains |
e
E||
e
V |+1 cycles
and forms an independent generating set for all the cy-
cles of R under symmetric difference. The correspond-
ing set of σ
y(j)
is therefore an independent generating
set of the cycle subgroup up to signs, since individual
Pauli operators either commute or anticommute and
square to the identity.
In a similar fashion as with twin-vertex symme-
tries, we restrict to a mutual ±1 eigenspace of the
cycle-subgroup generators, designated by a binary
string x {0, 1}
×|
e
E|−|
e
V |+1
over the j such that
φ(j)
e
E/
e
E
0
. That is, we restrict to the mutual +1
eigenspace of the stabilizer group
Z
H,x
(1)
x
j
σ
y(j)
. (47)
If Eq. (45) gives y(j) = 0 for any j, then we take
the corresponding x
j
= 0. We then simply choose the
direction for the edge φ(j) such that
(1)
x
j
i
d
Y
{z|φ(z)Y
j
}
φ
1
(z)
γ
φ
2
(z)
= +I (48)
where d is as defined in Eq. (46). This ensures that the
product of Majorana hopping terms around a funda-
mental cycle Y
j
agrees with the corresponding Pauli
product over the restricted subspace (i.e. up to equiv-
alencies by stabilizers in the group Z
H,x
). By the
Lie-homomorphism constraint Eq. (21), all products
of Majorana hopping terms around a cycle of R there-
fore agree with their corresponding Pauli products
over this subspace, and so the multiplication relations
of the Paulis are respected by their associated fermion
hopping terms up to stabilizer equivalencies. Since we
have exactly as many elements Y
j
in our fundamental
cycle basis as undirected edges φ(j), such an orienta-
tion can always be chosen.
Why are we free then, to choose an arbitrary sign
for each free-fermion term in our original spanning
tree? This choice is actually equivalent to a choice
of signs on the definitions of the individual Majorana
modes themselves and so amounts to a choice of ori-
entation for the coordinate basis in which we write
h. To see this, choose a fiducial orientation for R
satisfying Eq. (48), and suppose our particular free-
fermion solution—not necessarily oriented this way—
corresponds to the mapping
σ
j
7→ i(1)
x
j
γ
φ
1
(j)
γ
φ
2
(j)
(49)
Accepted in Quantum 2020-05-20, click title to verify. Published under CC-BY 4.0. 9
σ
i
1
\σ
j
2
I X Y Z
2-qubit frustration graph L(K
6
)
I P
1
γ
2
γ
3
γ
4
γ
5
γ
6
3
γ
5
2
γ
5
2
γ
3
X
4
γ
6
1
γ
2
1
γ
3
1
γ
5
Y
1
γ
6
2
γ
4
3
γ
4
4
γ
5
Z
1
γ
4
2
γ
6
3
γ
6
5
γ
6
Table 4: (Left) Fermionization of the two-qubit Pauli algebra P
2
= {σ
i
1
σ
j
2
}
(i,j)6=(0,0)
by six fermion modes. The graph
isomorphism G(P
2
) ' L(K
6
) reflects the Lie-algebra isomorphism between su(4) and spin(6). Though the scalar-commutation
relations are reproduced by quadratics in {γ
µ
}
6
µ=1
, the one-sided multiplication relations are only recovered upon projecting onto
the +1 eigenspace of P
1
γ
2
γ
3
γ
4
γ
5
γ
6
on the fermion side of the mapping. (Right) The graph L(K
6
), with vertices labeled
by a particular satisfying Pauli assignment. Edges are colored to identify the six K
5
subgraphs in the Krausz decomposition of
this graph, corresponding to the six fermion modes. Each vertex belongs to exactly two such subgraphs, as must be the case
for a line graph. This graphical correspondence was first observed in Ref. [46] in the language of the Dirac algebra.
for φ(j)
e
E
0
and with x
j
{0, 1} designating the
edge-direction of φ(j) relative to the fiducial orienta-
tion. We have
(1)
x
j
= (1)
r
φ
1
(j)
+r
φ
2
(j)
(50)
where
r
u
=
X
{k|φ(k)p(u,v)}
x
k
. (51)
Since the symmetric difference of p[φ
1
(j), v] and
p[φ
2
(j), v] is the edge φ(j)
e
E
0
, all sign factors on
the right side of Eq. (50) cancel except for (1)
x
j
.
We can then absorb (1)
r
φ
1
(j)
and (1)
r
φ
2
(j)
onto
the definitions of γ
φ
1
(j)
and γ
φ
2
(j)
, respectively. We
furthermore see that imposing Eq. (48) gives an edge-
direction for φ(j)
e
E/
e
E
0
that differs from that of
the fiducial orientation by the associated sign fac-
tor (1)
r
φ
1
(j)
+r
φ
2
(j)
, which remains consistent with
a redefinition of the signs on the individual Majorana
modes. Letting h be the single-particle Hamiltonian
for the fiducial orientation, such a redefinition corre-
sponds to conjugating h by a ±1 diagonal matrix. As
no scalar quantity of h can depend on this choice, this
redefinition corresponds to a gauge freedom.
Proceeding this way, we can solve the effective
Hamiltonian
H
x
H
Y
{j|φ(j)
e
E/
e
E
0
}
I + (1)
x
j
σ
y(j)
2
(52)
sector-by-sector over each stabilizer eigenspace desig-
nated by x. If we also need to remove twin vertices
from G(H) before it is a line graph, we project onto
the mutual +1 eigenspace of the stabilizer group S
x
defined previously in Section 4 as well. Finally, if the
parity operator P is trivial in the Pauli description,
then only a fixed-parity eigenspace in the fermion de-
scription will be physical.
In the next section, we will see how known free-
fermion solutions fit into this characterization and
demonstrate how our method can be used to find new
free-fermion solvable models, for which we give an ex-
ample.
5 Examples
5.1 Small Systems
The frustration graph of single-qubit Paulis X, Y, Z is
K
3
, the complete graph on three vertices. This graph
is the line graph of not one, but two non-isomorphic
graphs: the so-called ‘claw’ graph K
1,3
, and K
3
itself
Accepted in Quantum 2020-05-20, click title to verify. Published under CC-BY 4.0. 10
(see Table 1). By the Whitney isomorphism theorem
[45], K
3
is the only graph which is not the line graph
of a unique graph. This ambiguity results in the exis-
tence of two distinct free-fermion solutions of a single
qubit Hamiltonian, which we will hereafter refer to as
“even" (labeled “0") and “odd" (labeled “1") fermion-
izations
X
0
=
0
γ
1
X
1
=
2
γ
3
Y
0
=
1
γ
2
Y
1
=
0
γ
3
Z
0
=
0
γ
2
Z
1
=
1
γ
3
. (53)
In the even fermionization, no T-join of the root
graph K
3
exists since there are only three fermion
modes {γ
0
, γ
1
, γ
2
}. The orientation of the root graph
is constrained by the identity XY Z = iI. In the
odd fermionization, there are four fermion modes
{γ
0
, γ
1
, γ
2
, γ
3
}, and so a T-join does exist for the root
graph K
1,3
. It is the set of all edges of this graph.
The parity operator is trivial in the Pauli description
however, and so the constraint XY Z = iI is enforced
by restricting to the +1 eigenspace of P γ
0
γ
1
γ
2
γ
3
in the fermion description. We are free to choose the
orientation of the root graph K
1,3
however we like
in this case, since it contains no cycles, though this
choice will affect what we call the physical eigenspace
of P . By virtue of the line-graph construction and our
choice of orientation, both fermionizations respect the
single-qubit Pauli multiplication relations, up to sta-
bilizer equivalencies in some cases.
We have made the choice to label the Paulis in the
two fermionizations in a compatible way, such that
σ
j
0
= P σ
j
1
(54)
This gives
[σ
j
m
, σ
k
m
] = 2
jk`
σ
`
0
. (55)
where m {0, 1} and ε is the Levi-Civita tensor.
Since an even number of parity-operator factors ap-
pear on the left side of Eq. (55), the commutator be-
tween two Paulis in either fermionization is always a
Pauli in the even fermionization. We can addition-
ally write multiplication relations between the two
fermionizations concisely, as
σ
j
p
σ
k
q
= δ
jk
P
pq
+ i(1 δ
jk
)ε
jk`
σ
`
pq
. (56)
Another exceptional situation arises for 2 qubits,
for which the full frustration graph is the line graph
of K
6
, again depicted graphically in Table 1. This
reveals a free-fermion solution for all 2-qubit Hamil-
tonians by six fermion modes, listed explicitly in Ta-
ble 4. We again choose our orientation by picking
a spanning tree of the root graph (for example all
terms containing the mode γ
5
), choosing an arbitrary
orientation on this tree, and choosing the remaining
orientations by enforcing the condition in Eq. (48).
Since K
6
has an even number of vertices, there exists
a T-join for this graph, e.g. the terms {XX, Y Y, ZZ}.
The associated parity operator is trivial however, as
(XX)(Y Y )(ZZ) = I, and so only the +1 eigenspace
of P in the fermion description will be physical. This
solution reflects the exceptional Lie algebra isomor-
phism, su(4) ' spin(6).
Finally, we give an example of a three-qubit Hamil-
tonian with an exceptional symmetry, namely
H = XII + Y II + ZXX + ZZZ (57)
This Hamiltonian has the frustration graph shown in
the top right entry of Table 3, and thus is an excep-
tional case to Corollary 1.2. A symmetry transfor-
mation exchanging e and e
0
for this Hamiltonian is
the Hadamard gate applied to the second and third
qubits, which exchanges the third and fourth terms,
but cannot be realized as any permutation of the in-
dividual Majorana modes in its free-fermion descrip-
tion.
5.2 1-dimensional chains
Shown in Figure 1 is the frustration graph G(H)
for the most general nearest-neighbor Pauli Hamil-
tonian in 1-d (on open boundary conditions) which
is mapped to a free-fermion Hamiltonian under the
Jordan-Wigner transformation,
H =
n1
X
j=1
X
α,β∈{x,y}
µ
j
αβ
σ
α
j
σ
β
j+1
+
n
X
j=1
ν
j
Z
j
. (58)
Cliques are colored according to the Krausz decompo-
sition of this graph, which is easily seen by the free-
fermion description. The fermion hopping graph, R,
is shown below. Note that the cycle symmetry sub-
group Z
H
for this model is trivial, as every product
of Hamiltonian terms along a cycle in R is the iden-
tity. Since the number of vertices in R is even, a
T-join does exist, and the parity operator is in-fact
P = Z
n
. Therefore, we have |Z(P
H
)| = 1.
An example spanning tree for the root graph is
highlighted, taken simply to be the path along edges
(j, j+1) from γ
1
to γ
2n
. Including any additional edge
in this tree will form a cycle. A natural orientation
for this tree is to direct every edge from vertex j +1 to
vertex j. Note that we can recover the Jordan-Wigner
transformation from this graphical description alone.
We first adjoin a single fictitious qubit and a single
coupling term to the Hamiltonian, as
H
0
= µ
0
xx
X
0
X
1
+ H. (59)
Since the remaining qubits only couple to qubit “0"
along the X-direction, all operators in P
H
commute
on this qubit. Furthermore, this new term adds one
vertex to the black clique at the left boundary of the
chain in Fig. 1. It thus extends the spanning tree of
Accepted in Quantum 2020-05-20, click title to verify. Published under CC-BY 4.0. 11
Figure 1: Frustration graph for the general XY model and its root graph, shown below. Cliques are colored to show the
Krausz decomposition, which is the image of the model under the Jordan-Wigner transform. Vertices in the root graph are
correspondingly colored, and a spanning tree is highlighted.
R by one vertex which we label γ
0
due to the fact
that this new term only belongs to one clique (so we
take its additional Majorana mode to be a clique of
size zero). It can be easily verified that products of
Hamiltonian terms from this new vertex to any vertex
along the chosen spanning tree have the form
(
0
γ
2j1
X
0
N
j1
k=1
Z
k
X
j
0
γ
2j
X
0
N
j1
k=1
Z
k
Y
j
(60)
All such operators share γ
0
, so their commutation re-
lations are unchanged by truncating γ
0
. Furthermore,
since all operators in P
H
commute on qubit-0, we may
truncate this qubit as well without changing the com-
mutation relations of the operators above to obtain
the Jordan-Wigner transformation
(
γ
2j1
N
j1
k=1
Z
k
X
j
j odd
γ
2j
N
j1
k=1
Z
k
Y
j
j odd
(61)
In principle, a similar trick would work in general,
but we find it generally simpler to define Majorana
quadratic operators to avoid truncating at a bound-
ary. Our method is especially convenient when con-
sidering the case of periodic boundary conditions on
this model, wherein we add the boundary term
H
boundary
=
X
α,β∈{x,y}
µ
n
αβ
σ
α
1
σ
β
n
(62)
to the Hamiltonian in Eq. (58). With this term
included, the model has a nontrivial cycle symme-
try given by taking the product of fermion bilinears
around the periodic boundary, and this product is also
proportional to the parity operator P = Z
n
in the
spin picture. Adding a boundary term therefore does
not change |Z(P
H
)|, though it does require that we
solve the model over each of the eigenspaces of the
cycle symmetry independently by choosing the sign
of the additional terms in the fermion picture as de-
scribed in Section 4.1. Let the eigenspace of Z
n
be
specified by the eigenvalue (1)
p
. For each associated
free-fermion model solution, we must then restrict to
the +1 eigenspace of the parity operator in the spin
picture
n
Y
j=1
X
j
X
j+1
7→ (i)
n
(1)
p
2n
Y
k=1
γ
k
. (63)
where index addition is taken modulo n. This en-
sures that our free-fermionic solution respects the con-
straint
n
Y
j=1
X
j
X
j+1
= I. (64)
Notice that solving the two free fermion models to-
gether (one for each eigenspace of Z
n
) gives 2
n+1
eigenstates, yet restricting to a fixed-parity sector in
Accepted in Quantum 2020-05-20, click title to verify. Published under CC-BY 4.0. 12
Figure 2: Frustration graph for the Kitaev honeycomb model (left) and its root graph (right). Cliques are colored to show the
Krausz decomposition. Interestingly, this model’s root graph is the same as its interaction graph. A spanning tree of the root
is again highlighted.
each keeps only 2
n
of them, as required. Finally, we
see that this model contains no logical qubits via
n
L
= n
1
2
(2n 2) + 1
= 0 (65)
as we might expect.
5.3 The Kitaev honeycomb model
Next we consider the Kitaev honeycomb model in two
dimensions [12]. This model has the Hamiltonian
H =
X
α∈{x,y,z}
X
αlinks j
J
j
α
σ
α
j
σ
α
j+ ˆα
(66)
where each of the α links correspond to one of the
compass directions of the edges of a honeycomb lat-
tice. Once again, the frustration graph with shaded
cliques according to the Krausz decomposition is
shown in Fig. 2. Interestingly, the root graph of this
model’s frustration graph is again the honeycomb lat-
tice. By going backwards, we can see that indeed, any
free-fermion model with trivalent hopping graph can
be embedded in a 2-body qubit Hamiltonian with the
same interaction graph. This is because we can find a
set of Pauli operators satisfying any frustration graph
whose edges can be partitioned into triangles by as-
signing a different single-qubit Pauli to each of the
vertices of every triangle. A term in the Hamiltonian
is then the tensor product of all of the Pauli opera-
tors from the triangles to which its vertex in G(H)
belongs.
Unlike in the one-dimensional example, the cycle
subgroup of this model, Z
H
, is nontrivial. This sub-
group is generated by the products of Hamiltonian
terms around a hexagonal plaquette of the honeycomb
lattice, denoted W
p
for plaquette p. These cycles are
not independent, however, with constraints between
them depending on the boundary conditions of the
lattice. In particular, if the model is on a torus of
dimension L
x
by L
y
, then the product of all Hamil-
tonian terms is trivial
Y
jV
σ
j
= (1)
L
x
L
y
I (67)
In this case, the cycles of the honeycomb lattice are
not independent, since they similarly multiply to the
identity. There are thus L
x
L
y
1 independent pla-
quettes on the lattice. There are additionally two ho-
motopically nontrivial cycles, which are independent
as well. Notice that the edges of the honeycomb lat-
tice itself form a T-join, and so the above constraint
is also the statement that P is furthermore trivial.
Therefore, we have
|Z(P
H
)| = L
x
L
y
1 + 2 = L
x
L
y
+ 1 (68)
and once again (as first computed in Ref. [54])
n
L
= 2L
x
L
y
1
2
(2L
x
L
y
2) + L
x
L
y
+ 1
= 0.
(69)
This example also illustrates that quite a large num-
ber of symmetries could be present, and in general
this will complicate finding, e.g., the symmetry sector
that contains the ground state.
5.4 Frustrated Hexagonal Gauge 3D Color
Code
The frustrated hexagonal gauge 3d color code is a non-
commuting Hamiltonian whose terms consist of the
stabilizer generators and a subset of the gauge gener-
ators from the gauge color code. The gauge color code
Accepted in Quantum 2020-05-20, click title to verify. Published under CC-BY 4.0. 13
Figure 3: The frustrated hexagonal gauge 3d color code, proposed in Ref. [44]. This model is based on the 3d gauge color
code, whose qubits live on the vertices of the lattice shown. Gauge generators for the 3d gauge color code consist of Pauli-Z
and Pauli-X operators around both the square and hexagonal faces of the lattice. Stabilizers of the 3d gauge color code
consist of Pauli-Z and Pauli-X operators on both the cube and “ball" cells. The frustrated hexagonal gauge 3D color code
is given by taking the stabilizers of the gauge color code together with the hexagonal gauge generators, which commute
with the stabilizers, but not with each other. We see from the colored hexagonal faces above that the frustration graph of
these gauge generators is a set of disconnected path graphs. Every hexagonal plaquette term anticommutes with exactly two
others—the plaquette terms of the other Pauli type intersecting it at exactly one qubit—and commutes with all other terms
in the Hamiltonian.
[5558] has a Hamiltonian that is defined in terms of
a natural set of gauge generators as
H =
X
S,9
J
x
O
jS
X
j
+ J
Z
O
jS
Z
j
+ (boundary terms) (70)
where “" and “9" denote the sets of square and
hexagonal faces on the lattice in Fig. 3, respectively
(see Ref. [59] for a detailed description of this lattice).
Here the qubits live on the vertices of the lattice. Non-
trivial boundary conditions are required to restrict the
logical space of this code to a single qubit. We will
ignore these boundary conditions and consider only
gauge generators in the bulk of the lattice. The sta-
bilizers for this model are given by products of X or
Z around every elementary cell, either a cube or a
“ball".
We consider a model where we partially restore
some of these symmetries. Namely, we will consider
the cube and balls to be “restored” symmetries of
the model, and we will remove the square generators.
This leads to the following gauge Hamiltonian that
sums over only hexagonal faces, balls, and cubes,
H =
X
S9,,
J
X
O
jS
X
j
+ J
Z
O
jS
Z
j
. (71)
The cube and ball terms commute with all of the
hexagon terms, and so constitute symmetries of the
model. Once we fix a sector for these terms, we
Accepted in Quantum 2020-05-20, click title to verify. Published under CC-BY 4.0. 14
Figure 4: The Sierpinski-Hanoi model (left) with its frustration graph, highlighted, and its root graph (right) with a spanning
tree highlighted, for k = 5 and local fields absent. Hamiltonian terms are 3-qubit operators acting on qubits at the vertices
of the Sierpinski sieve graph, highlighted in blue. Cliques of the frustration graph are colored to show the graph’s Krausz
decomposition. Green and orange cells depict generators for the model’s logical Pauli group. At the interior triangular cells of
the lattice are the 3-body generators shown in green. At the interior and exterior edges of the model are 2-body generators
shown in orange. These are obtained from their adjoining Hamiltonian terms by reflecting the action on the intersection of
their supports (so these generators act differently depending on which edge they act on). The frustration graph of this model
is the Hanoi graph H
k1
3
. The vertices of this graph are in correspondence to the states of the towers of Hanoi problem with
three towers and k 1 discs. The root graph of H
k1
3
contains H
k2
3
as a topological minor.
can solve the remaining model by mapping to free-
fermions as follows [44].
In Figure 3, we represent a subsection of the qubit
lattice of this code, where qubits live at the tetravalent
vertices. Because the cube and ball terms commute
with everything, the frustration graph depends only
on the hexagonal faces, several of which are colored
in Figure 3. We see that some of these faces inter-
sect at exactly one vertex, and so the X- and Z-type
gauge generators will anticommute on the associated
qubit. These intersection patterns only occur in 1D
chains along the cardinal axes of the lattice. In par-
ticular, every hexagonal face only overlaps with two
other hexagonal faces along these chains and other-
wise intersects the other faces at an even number of
qubits. The frustration graph of this model thus de-
couples into a set of disconnected paths, which are
line graphs, and in fact they are the frustration graph
of the XY-model [1] and the 1-d Kitaev wire [60]. A
free-fermion mapping therefore exists for this model,
and this demonstrates an example of how one might
construct subsystem codes with a free-fermion solu-
tion to obtain desired spectral properties. In particu-
lar, when |J
x
| 6= |J
z
| the model in Eq. (71) is gapped.
We note that this observation was made previously in
Ref. [44] in the context of quantum error correcting
codes.
5.5 Sierpinski-Hanoi model
Finally, we introduce our own example of a solvable
spin model, which was previously unknown to the
Figure 5: Single-Particle spectrum of the Sierpinski-Hanoi
model for k = 5 with an additional local field term present in
the symmetry sector for which all cycles are +1. Circled are
two critical points where excited bands become degenerate.
best of our knowledge. This model consists of 3-
body XY Z-interaction terms on the shaded cells of
the Sierpinski triangle, all with the same orientation,
as depicted in Fig. 4. Explicitly, the Hamiltonian for
this model is given by
H =
X
(i,j,k)N
X
i
Y
j
Z
k
+ JH
local
(72)
where (i, j, k) is an ordered triple of qubits belong-
ing to a particular shaded cell on the lattice and we
Accepted in Quantum 2020-05-20, click title to verify. Published under CC-BY 4.0. 15
will define additional on-site terms H
local
in Eq. (77).
An instance of the model is parameterized by k, the
fractal recursion depth of the underlying Sierpinski
lattice, where k = 1 is taken to be a single 3-qubit
interaction.
Let us first consider the simplified model where J =
0. Then the frustration graph of this model is the so-
called Hanoi graph H
k1
3
. The vertices of this graph
are labeled by states of the towers of Hanoi problem
with k 1 discs, and two vertices are neighboring if
transitioning between the corresponding states is an
allowed move in the problem. Perhaps surprisingly,
this graph is a line graph, with root and highlighted
spanning tree shown in Fig. 4. Furthermore, the root
graph contains H
k2
3
as a topological minor, obtained
by removing the vertices of degree one and contracting
the vertices of degree two each along one of their two
edges.
This model contains
n =
3
2
(3
k1
+ 1) (73)
physical qubits, and its root graph contains
|
e
V | =
(
2 k = 1
1
2
5 × 3
k2
+ 3
k > 1
(74)
vertices. A T-join for this graph therefore exists only
for even k and k = 1, and the parity operator is never
trivial when a T-join exists. The root graph also con-
tains
|Z
H
| =
k3
X
j=0
3
j
=
(
0 k 2
1
2
3
k2
1
k > 2
(75)
fundamental cycles. None of the generators of the
cycle subgroup are trivial since every qubit is acted
upon by at most two anti-commuting operators. The
number of logical qubits in this model is therefore
n
L
=
(
2 k = 1
1
4
11 × 3
k2
+ 8 + (1)
k
k > 1,
(76)
and so this Hamiltonian encodes logical qubits at a
constant rate of
11
18
in the infinite k limit. Perhaps
unsurprisingly, these logical qubits live on the bound-
aries of the fractal, and we can obtain a set of gen-
erators for the logical Pauli group of this model as
shown in Fig. 4. We can encode logical quantum in-
formation in this model by picking symplectic pairs of
generators from this group, which anticommute with
one another yet commute with the remaining genera-
tors in the group. The remaining such generators can
be used as gauge qubits for the logical qubit we wish
to protect, and the free-fermion Hamiltonian of the
model can be used for error suppression.
We are also free to add an anisotropic local-field
term to a subset of the qubits without breaking solv-
ability
H
local
=
X
iNN
σ
j
i
i
(77)
The sum is taken over all qubits corresponding to
black edges connecting two shaded cells in Fig. 4. j
i
is the third Pauli type from the two Paulis acting on
qubit i by the interaction terms. The effect of these
local-field terms is to couple every black vertex in the
root graph shown in Fig. 4, except for those at the
three corners, to a dedicated fermion mode. We do
not depict these additional modes to avoid cluttering
the figure. These terms also do not affect the symme-
tries of the model, except possibly to add the parity
operator to Z(P
H
) when the number of vertices in the
original graph was odd, as the number of vertices in
the graph with local field terms present will always be
even. The parity operator can then be constructed as
the product of all of the Hamiltonian terms, since the
root graph only has vertices of degrees 1 and 3.
In Fig. 5, we display the single-particle spectrum of
the Sierpinski-Hanoi model as a function of the local
field J for k = 5 in the sector for which all of the
cycle symmetries are in their mutual +1 eigenspace.
We highlight two critical points where excited energy
levels become degenerate to within our numerical pre-
cision. We observe that the locations of these points
are not system-size-independent, but rather asymp-
totically approach J = 0 as the system size is in-
creased. We conjecture that this is connected to the
emergence of scale symmetry, which the model pos-
sesses in the thermodynamic limit, yet not for any
finite size. It would be intriguing if certain physical
features of this symmetry could be realized at the crit-
ical points at finite size, potentially opening the door
to simulating scale-invariant systems on a finite-sized
quantum computer.
6 Proofs of Main Theorems
6.1 Proof of Theorem 1
We restate Theorem 1 for convenience.
Theorem 1, restated (Existence of free-fermion so-
lution). An injective map φ as defined in Eq. (20) and
Eq. (21) exists for the Hamiltonian H as defined in
Eq. (1) if and only if there exists a root graph R such
that
G(H) ' L(R), (78)
where R is the hopping graph of the free-fermion so-
lution.
Proof. If φ exists, define R = (V, E), where E
{(φ
1
(j), φ
2
(j))|φ
1
(j), φ
2
(j) V, j E}. If and only
if |(φ
1
(j), φ
2
(j)) (φ
1
(k), φ
2
(k))| = 1, then the ver-
tices corresponding to j and k are neighboring in G
Accepted in Quantum 2020-05-20, click title to verify. Published under CC-BY 4.0. 16
by Eq. (21). Thus, G(H) ' L(R) and a mapping φ
exists only if R does.
If there exists a graph R (V, E) such that
G ' L(R), take the Krausz decomposition of
G(H). Namely, partition the edges of G(H) as F =
{C
1
, . . . , C
|V |
}, where each C
i
constitutes a clique in
G and such that every vertex in G appears in at
most two C
i
. The cliques in this partitioning cor-
respond to the vertices V of R. For each vertex j,
define φ(j) to be the pair of cliques in which j ap-
pears. Since the cliques partition the edges of G,
then if vertices j and k are neighboring in G, they
must appear in exactly one clique together, and thus
|(φ
1
(j), φ
2
(j)) (φ
1
(k), φ
2
(k))| = 1. Thus, φ satisfies
Eq. (21). Furthermore, φ is injective, since if there
are two vertices j, k G such that φ(j) = φ(k), then
j and k appear in the same two cliques, but since the
Krausz decomposition is a partition of the edges, this
would require that j and k neighbor by two edges.
However, the definition of G guarantees that pairs of
vertices can only neighbor by at most one edge, and
so this is impossible. Therefore φ is injective.
6.2 Proof of Theorem 2
Once again, we restate our theorem for convenience
Theorem 2, restated (Symmetries are cycles and
parity). Given a Hamiltonian satisfying Eq. (78) such
that the number of vertices |
e
V | in the root graph is odd,
then we have
Z(P
H
) = Z
H
. (79)
If the number of vertices in the root graph is even,
then we have
Z(P
H
) = hZ
H
, P i . (80)
Proof. Let G (E, F ) ' L(R) be the connected
line graph of a connected root graph R = (V, E), and
let G have adjacency matrix A. We will need the
following well-known factorization of a line graph ad-
jacency matrix A
A = BB
T
(mod 2) (81)
where B is the edge-vertex incidence matrix of R.
That is, B is a |E| × |V | matrix such that
B
jl
=
(
1 l j
0 otherwise
(82)
for all j E and l V . We can interpret B as
defining the map φ via
φ : σ
j
7→
Y
lV
γ
B
jl
l
(83)
That is, φ
1
(j) and φ
2
(j) are the indices of the nonzero
elements in the row labeled by j in B. This then
defines the adjacency matrix A through the scalar
commutator as
[[
Y
lV
γ
B
jl
l
,
Y
mV
γ
B
kl
m
]] =
Y
l,mV
[[γ
B
jl
l
, γ
B
km
m
]] (84)
=
Y
l,mV
(1)
(1δ
lm
)B
jl
B
km
(85)
[[
Y
lV
γ
B
jl
l
,
Y
mV
γ
B
kl
m
]] = (1)
(BB
T
)
jk
+
(
P
l
B
jl
)(
P
l
B
kl
)
(86)
(1)
A
jk
= (1)
(BB
T
)
jk
(87)
From the third to the fourth line, we replaced the left-
hand side with the definition of A and used the fact
that the rows of B have exactly two nonzero elements.
By the distributive property of the scalar commutator
Eq. (4), we can extend the above equation to products
of Hamiltonian terms
Y
jE
Y
lV
γ
B
jl
l
!
v
j
= ±
Y
lV
γ
(
B
T
·v
)
l
l
, (88)
where v {0, 1}
×|E|
, as
[[
Y
lV
γ
B
jl
l
,
Y
kE
Y
mV
γ
B
km
m
!
v
k
]] = (1)
(
BB
T
·v
)
j
(89)
since linear combinations of rows of B over F
2
will
have even-many ones. Every element of P
H
is a (non-
unique) linear combination of rows of B over F
2
, and
so to characterize the elements of Z(P
H
), it is suffi-
cient to find a spanning set of the kernel of A,
A · v = BB
T
· v = 0 (mod 2) (90)
It is again well-known that the F
2
-kernel of B
T
is the
cycle space of R, and this specifies the cycle subgroup
Z
H
as being contained in Z(P
H
). All that is left
is therefore to find all v such that B
T
· v is in the
kernel of B. Since we have assumed G is connected,
it is easy to see that the only element in this kernel
is 1, the all-ones vector. Thus, v will also be in the
kernel of A if it defines a T-join of G. If |V | is even,
then we can construct a T-join by first pairing the
vertices along paths of G. We can then ensure that
each edge appears at most once in the T-join by taking
the symmetric difference of all paths. If |V | is odd,
then no T-join exists. Indeed, assume that a T-join T
does exist for |V | odd, and let
e
G = (V, T ) G be the
subgraph of G containing exactly the edges from the
T-join. By construction
e
G contains all the vertices of
G and has odd degree for every vertex, though it may
no longer be connected. Let these degrees be {d
j
}
jV
,
then by the handshaking lemma
|V |
X
j=1
d
j
= 2|T |. (91)
Accepted in Quantum 2020-05-20, click title to verify. Published under CC-BY 4.0. 17
However, the left side must be odd since we have as-
sumed the degree of every vertex in
e
G is odd, and
the number of vertices is also odd, and so we have a
contradiction.
7 Discussion
We have seen how the tools of graph theory can be
leveraged to solve a wide class of spin models via map-
ping to free fermions, and given an explicit procedure
for constructing the free-fermion solution when one
exists. A major remaining open question, however,
concerns the characterization of free-fermion solutions
beyond the generator-to-generator mappings we con-
sider here. That is, if G(H) is not a line graph and
no removal of twin vertices will make it so, then it
may still be possible for a free-fermion solution for
H to exist thanks to the continuum of locally equiva-
lent Pauli-bases into which H may be expanded. Our
fundamental theorem does not rule out the possibil-
ity that special such bases may exist. The problem
of finding such bases is equivalent to finding specific
unitary rotations of H for which the G(H) again be-
comes a line graph. These rotations must be outside
of the Clifford group, since the frustration graph is a
Clifford invariant. Their existence may therefore de-
pend on specific algebraic relationships between the
Pauli coefficients h
j
in the Hamiltonian, since the ex-
istence of a free-fermionization is a spectral invari-
ant. We expect such transformations will be hard to
find in general, though perhaps progress can be made
for single-qubit rotations on 2-local Hamiltonians in a
similar vein as in Ref. [61] for stoquasticity. Recently,
a local spin-
1
/2 model with a free-fermion solution
despite no such generator-to-generator solution exist-
ing has been found in Ref. [62]. An investigation of
models which may be fermionized by these more gen-
eral transformations is therefore an interesting subject
of future work.
It is natural to ask whether our results could have
implications for simulating quantum systems and
quantum computation. We expect our characteriza-
tion to shed some light on the inverse problem of find-
ing fermion-to-qubit mappings, such as the Bravyi-
Kitaev superfast encoding [63], Bravyi-Kitaev trans-
form [64], and generalized superfast encoding [65]. It
is possible to achieve further encodings by introduc-
ing ancillary fermion modes, as seen in the Verstraete-
Cirac mapping [7] and the contemporaneous mapping
introduced by Ball [66]. Encodings can be further im-
proved through tailoring to specific symmetries [67],
connectivity structures [68, 69], and through the ap-
plication of Fenwick trees [70]. Recently, a treelike
mapping was shown to achieve optimal average-case
Pauli-weight in Ref [71]. In their “Discussion” sec-
tion, the authors remark that an interesting future
direction for their work would involve introducing an-
cillary qubits to their mapping. We expect our classi-
fication of the symmetries of free-fermion spin models
to help guide this investigation, though further work
is required to fully characterize the logical symmetry
groups which can be realized by these models.
Finally, our characterization highlights the possi-
bility of a “free-fermion rank" for Hamiltonians as an
important measure of classical simulability. Namely,
if there is no free-fermion solution for a given Hamil-
tonian, we can still group terms into collections such
that each collection independently has such a solu-
tion. An interesting natural question for future work
is whether the minimal number of such collections re-
quired can be interpreted as a quantum resource in
an analogous way to the fermionic Gaussian rank [72]
or stabilizer rank [73] for states.
Acknowledgements
We thank Samuel Elman, Ben Macintosh, Ryan
Mann, Nick Menicucci, Andrew Doherty, Stephen
Bartlett, Sam Roberts, Alicia Kollár, Deniz Stiege-
mann, Sayonee Ray, Chris Jackson, Jonathan Gross,
and Nicholas Rubin for valuable discussions through-
out this project. This work was supported by the
Australian Research Council via EQuS project num-
ber CE170100009.
References
[1] E. Lieb, T. Schultz, and D. Mattis, Annals of
Physics 16, 407 (1961).
[2] P. Jordan and E. Wigner, Zeitschrift für Physik
47, 631 (1928).
[3] E. Fradkin, Phys. Rev. Lett. 63, 322 (1989).
[4] Y. R. Wang, Phys. Rev. B 43, 3786 (1991).
[5] L. Huerta and J. Zanelli, Phys. Rev. Lett. 71,
3622 (1993).
[6] C. D. Batista and G. Ortiz, Phys. Rev. Lett. 86,
1082 (2001).
[7] F. Verstraete and J. I. Cirac, Journal of Statis-
tical Mechanics: Theory and Experiment 2005,
P09012 (2005).
[8] Z. Nussinov, G. Ortiz, and E. Cobanera, Phys.
Rev. B 86, 085415 (2012).
[9] Y.-A. Chen, A. Kapustin, and Ð. Radičević, An-
nals of Physics 393, 234 (2018).
[10] S. Backens, A. Shnirman, and Y. Makhlin, Sci-
entific reports 9, 2598 (2019).
[11] N. Tantivasadakarn, arXiv e-prints ,
arXiv:2002.11345 (2020), arXiv:2002.11345
[cond-mat.str-el] .
[12] A. Kitaev, Annals of Physics 321, 2 (2006).
[13] E. Knill, ArXiv e-prints (2001), arXiv:quant-
ph/0108033 .
[14] B. M. Terhal and D. P. DiVincenzo, Phys. Rev.
A 65, 032325 (2002).
Accepted in Quantum 2020-05-20, click title to verify. Published under CC-BY 4.0. 18
[15] M. Van Den Nest, Quantum Info. Comput. 11,
784 (2011).
[16] D. J. Brod, Phys. Rev. A 93, 062332 (2016).
[17] R. Jozsa and A. Miyake, Proc. R. Soc. A 464,
3089 (2008).
[18] D. J. Brod and E. F. Galvão, Phys. Rev. A 84,
022310 (2011).
[19] S. Bravyi, Phys. Rev. A 73, 042313 (2006).
[20] M. Hebenstreit, R. Jozsa, B. Kraus, S. Strelchuk,
and M. Yoganathan, Phys. Rev. Lett. 123,
080503 (2019).
[21] D. J. Brod and A. M. Childs, Quant. Info. Com-
put. 14, 901 (2014).
[22] L. G. Valiant, SIAM Journal on Computing 31,
1229 (2002).
[23] J.-Y. Cai and V. Choudhary, in Proceedings
of the Third International Conference on The-
ory and Applications of Models of Computation,
TAMC’06 (Springer-Verlag, Berlin, Heidelberg,
2006) pp. 248–261.
[24] J. Cai, V. Choudhary, and P. Lu, in Twenty-
Second Annual IEEE Conference on Computa-
tional Complexity (CCC’07) (2007) pp. 305–318.
[25] L. G. Valiant, SIAM Journal on Computing 37,
1565 (2008).
[26] C. H. Papadimitriou, in Encyclopedia of Com-
puter Science (John Wiley and Sons Ltd., Chich-
ester, UK, 1994) pp. 260–265.
[27] P. Kasteleyn, Physica 27, 1209 (1961).
[28] H. N. V. Temperley and M. E. Fisher, Philosoph-
ical Magazine 6, 1061 (1961).
[29] M. Planat and M. Saniga, Quant. Inf. Comput. 8,
127 (2008), arXiv:quant-ph/0701211 [quant-ph] .
[30] A. Jena, S. Genin, and M. Mosca, arXiv e-prints
, arXiv:1907.07859 (2019), arXiv:1907.07859
[quant-ph] .
[31] V. Verteletskyi, T.-C. Yen, and A. F. Izmaylov,
The Journal of Chemical Physics 152, 124114
(2020).
[32] A. Zhao, A. Tranter, W. M. Kirby, S. F.
Ung, A. Miyake, and P. Love, arXiv e-prints
, arXiv:1908.08067 (2019), arXiv:1908.08067
[quant-ph] .
[33] A. F. Izmaylov, T.-C. Yen, R. A. Lang, and
V. Verteletskyi, Journal of Chemical Theory and
Computation 16, 190 (2019).
[34] T.-C. Yen, V. Verteletskyi, and A. F. Izmaylov,
Journal of Chemical Theory and Computation
16, 2400 (2020).
[35] P. Gokhale, O. Angiuli, Y. Ding, K. Gui,
T. Tomesh, M. Suchara, M. Martonosi, and F. T.
Chong, arXiv e-prints , arXiv:1907.13623 (2019),
arXiv:1907.13623 [quant-ph] .
[36] O. Crawford, B. van Straaten, D. Wang,
T. Parks, E. Campbell, and S. Brier-
ley, arXiv e-prints , arXiv:1908.06942 (2019),
arXiv:1908.06942 [quant-ph] .
[37] X. Bonet-Monroig, R. Babbush, and T. E.
O’Brien, arXiv e-prints , arXiv:1908.05628
(2019), arXiv:1908.05628 [quant-ph] .
[38] N. D. Roussopoulos, Information Processing Let-
ters 2, 108 (1973).
[39] P. G. H. Lehot, J. ACM 21, 569 (1974).
[40] D. G. Degiorgi and K. Simon, in Graph-Theoretic
Concepts in Computer Science (Springer Berlin
Heidelberg, Berlin, Heidelberg, 1995) pp. 37–48.
[41] A. J. Kollár, M. Fitzpatrick, and A. A. Houck,
Nature 571, 45 (2019).
[42] A. J. Kollár, M. Fitzpatrick, P. Sarnak, and
A. A. Houck, Communications in Mathematical
Physics , online only (2019).
[43] I. Boettcher, P. Bienias, R. Belyansky, A. J.
Kollár, and A. V. Gorshkov, arXiv e-prints
, arXiv:1910.12318 (2019), arXiv:1910.12318
[quant-ph] .
[44] T. Jochym-O’Connor, S. Roberts, S. Bartlett,
and J. Preskill, Frustrated hexagonal gauge 3d
color code,” (2019), 5th International Conference
on Quantum Error Correction (QEC 2019).
[45] H. Whitney, American Journal of Mathematics
54, 150 (1932).
[46] D. M. Goodmanson, American Journal of Physics
64, 870 (1996).
[47] L. W. Beineke, Journal of Combinatorial Theory
9, 129 (1970).
[48] Ľ. Šoltés, Discrete Mathematics 132, 391 (1994).
[49] Y. Yang, J. Lin, and C. Wang, Discrete Mathe-
matics 252, 287 (2002).
[50] P. Erdős, A. W. Goodman, and L. Pósa, Cana-
dian Journal of Mathematics 18, 106 (1966).
[51] F. Harary, Graph Theory, Addison Wesley series
in mathematics (Addison-Wesley, 1971).
[52] J. Krausz, Matematikai és Fizikai Lapok 50
(1943).
[53] A. Bednarek, Discrete Mathematics 56, 83
(1985).
[54] M. Suchara, S. Bravyi, and B. Terhal, Journal
of Physics A: Mathematical and Theoretical 44,
155301 (2011).
[55] H. Bombín, New Journal of Physics 18, 043038
(2016).
[56] H. Bombín, Phys. Rev. X 5, 031043 (2015).
[57] A. Kubica and M. E. Beverland, Phys. Rev. A
91, 032330 (2015).
[58] H. Bombín, New Journal of Physics 17, 083002
(2015).
[59] B. J. Brown, N. H. Nickerson, and D. E. Browne,
Nature Communications 7, 12302 (2016).
[60] A. Y. Kitaev, Physics-Uspekhi 44, 131 (2001).
[61] J. Klassen and B. M. Terhal, Quantum 3, 139
(2019).
[62] P. Fendley, Journal of Physics A: Mathematical
and Theoretical 52, 335002 (2019).
[63] S. B. Bravyi and A. Y. Kitaev, Ann. Phys. (N.
Y.) 298, 210 (2002).
Accepted in Quantum 2020-05-20, click title to verify. Published under CC-BY 4.0. 19
[64] J. T. Seeley, M. J. Richard, and P. J. Love, The
Journal of Chemical Physics 137, 224109 (2012).
[65] K. Setia, S. Bravyi, A. Mezzacapo, and J. D.
Whitfield, Phys. Rev. Research 1, 033033 (2019).
[66] R. C. Ball, Phys. Rev. Lett. 95, 176407 (2005).
[67] S. Bravyi, J. M. Gambetta, A. Mezzacapo, and
K. Temme, arXiv e-prints , arXiv:1701.08213
(2017), arXiv:1701.08213 [quant-ph] .
[68] M. Steudtner and S. Wehner, New Journal of
Physics 20, 063010 (2018).
[69] Z. Jiang, J. McClean, R. Babbush, and
H. Neven, Phys. Rev. Applied 12, 064041 (2019).
[70] V. Havlíček, M. Troyer, and J. D. Whitfield,
Phys. Rev. A 95, 032332 (2017).
[71] Z. Jiang, A. Kalev, W. Mruczkiewicz, and
H. Neven, arXiv e-prints , arXiv:1910.10746
(2019), arXiv:1910.10746 [quant-ph] .
[72] S. Bravyi and D. Gosset, Communications in
Mathematical Physics 356, 451 (2017).
[73] S. Bravyi, D. Browne, P. Calpin, E. Campbell,
D. Gosset, and M. Howard, Quantum 3, 181
(2019).
Accepted in Quantum 2020-05-20, click title to verify. Published under CC-BY 4.0. 20