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. Speciﬁcally, 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
ﬁnd 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. Cliﬀord 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 ﬁt 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 diﬃcult numerical
methods or perturbation theory. In the particular
setting of many-body spin-
1
/2 systems, a remarkable
method for producing exact solutions involves ﬁnding
an eﬀective 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 ﬁnding generalizations
to this mapping for more complicated spin systems is
a daunting task. Of the many generalizations that
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 ﬁxed 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 eﬃciently 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 ﬁrst developed [2225]. This
problem is known to be very hard computationally
(it is #P-complete [26]), but is eﬃciently 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 deﬁnition of a line graph,
it will be clear that such a condition is necessary, but
we will show that it is also suﬃcient. 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 eﬀective 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
ﬁrst deﬁne 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 deﬁnitions, we can informally state
our ﬁrst 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 eﬀec-
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 deﬁned by ﬁxing 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
which cannot aﬀect 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 ﬁxing a symmetry as well. Luckily, all of
these cases manifest as structures in the frustration
graph of H. The ﬁrst, regarding when a non-injective
free-fermion solution is required, is signiﬁed by the
presence of so-called twin vertices, or vertices with
the same neighborhood. We deal with this case in
our ﬁrst 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 ﬁx all of the cy-
cle symmetries by choosing an orientation of the root
graph R. Our results also relate the more general class
of Cliﬀord symmetries to the symmetries of the single-
particle free-fermion Hamiltonian. We show that with
exactly three exceptions, Cliﬀord symmetries of the
spin model, in a subspace deﬁned by ﬁxing 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
ﬁeld 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 ﬁt 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 deﬁne 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 oﬀ 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
diﬀer 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-ﬁve cliques
corresponding to the degree-ﬁve vertices of the root graph.
This mapping implies the existence of a free-fermion solution
for general two-qubit Hamiltonians by six fermions, reﬂecting
the accidental Lie-algebra isomorphism su(4) ' spin(6) (see
Section 5.1).
Through the binary symplectic inner product, the
scalar commutator deﬁnes 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 eﬀect 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-
ﬁed 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 deﬁning
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, ﬁnd 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),
eﬀecting
σ
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
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
Deﬁnition 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 deﬁnitions in-hand, our ﬁrst main result
can be stated simply as
Theorem 1 (Existence of free-fermion solution). An
injective map φ as deﬁned in Eq. (20) and Eq. (21)
exists for the Hamiltonian H as deﬁned 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 ﬁx 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). Diﬀerent 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 suﬃcient for a free-fermion
solution to exist. Before turning to further implica-
tions of Theorem 1, let us ﬁrst 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 ﬁrst given by Krausz [52]
and bears stating formally.
Deﬁnition 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 identiﬁed 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 deﬁnition:
Deﬁnition 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 reﬁned 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 ﬁxed 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 ﬁve graphs contain the forbidden subgraphs
in (e) and none of those in (a) or (d). Finally, this set was further reﬁned 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.
Deﬁnition 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 ﬁrst 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 deﬁnition 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 deﬁned
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} speciﬁes 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)
eﬀectively 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 suﬃcient 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 deﬁnition of G(
e
H) will
diﬀer 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
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 aﬀect 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 deﬁned 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 deﬁnitions.
Deﬁnition 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-
ﬁes Eq. (25) for some root graph R, we deﬁne 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 deﬁnition 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 deﬁnition 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 deﬁne this operator in terms of Pauli
Hamiltonian terms through a combinatorial structure
known as a T-join.
Deﬁnition 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 satisﬁes Eq. (25)
for some root graph R such that the number of vertices
in R is even, we deﬁne 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} speciﬁes 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 ﬁxed-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 deﬁnitions 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
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 coeﬃ-
cients h
j
themselves satisfy a symmetry. Our charac-
situation when the associated symmetry transforma-
tion is a Cliﬀord 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 inﬁnite
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 (Cliﬀord Symmetries and Whitney
Isomorphism). Let
e
H = iγ · h · γ
T
be a free-fermion
Hamiltonian with single-particle Hamiltonian h in a
ﬁxed symmetry sector of Z(P
H
). Then any uni-
tary Cliﬀord 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 Cliﬀord 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 deﬁned 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, deﬁned as:
Deﬁnition 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
, deﬁned 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 diﬀerence. 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 deﬁned 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
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 deﬁnitions 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 ﬁducial 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
) reﬂects 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 ﬁrst 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 ﬁducial 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 diﬀerence 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 deﬁnitions 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 diﬀers from that of
the ﬁducial orientation by the associated sign fac-
tor (1)
r
φ
1
(j)
+r
φ
2
(j)
, which remains consistent with
a redeﬁnition of the signs on the individual Majorana
modes. Letting h be the single-particle Hamiltonian
for the ﬁducial orientation, such a redeﬁnition corre-
sponds to conjugating h by a ±1 diagonal matrix. As
no scalar quantity of h can depend on this choice, this
redeﬁnition corresponds to a gauge freedom.
Proceeding this way, we can solve the eﬀective
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
deﬁned previously in Section 4 as well. Finally, if the
parity operator P is trivial in the Pauli description,
then only a ﬁxed-parity eigenspace in the fermion de-
scription will be physical.
In the next section, we will see how known free-
fermion solutions ﬁt into this characterization and
demonstrate how our method can be used to ﬁnd 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 aﬀect what we call the physical eigenspace
of P . By virtue of the line-graph construction and our
choice of