# Random translation-invariant Hamiltonians and their spectral gaps

Ian Jauslin  Department of Mathematics, Rutgers University, Piscataway, NJ
08854, USA  Marius Lemm  Department of Mathematics, University of Tübingen,
72076 Tübingen, Germany

(August 21, 2022)

###### Abstract

We consider random translation-invariant frustration-free quantum spin
Hamiltonians on ${\mathbb{Z}}^{D}$ in which the nearest-neighbor interaction
in every direction is randomly sampled and then distributed across the
lattice. Our main result is that, under a small rank constraint, the
Hamiltonians are automatically frustration-free and they are gapped with a
positive probability. This extends previous results on 1D spin chains to all
dimensions. The argument additionally controls the local gap. As an
application, we obtain a 2D area law for a cut-dependent ground state via
recent AGSP methods of Anshu-Arad-Gosset.

##  1 Introduction

In quantum many-body physics, the existence of a spectral gap above the ground
state has massive consequences for ground state correlation and entanglement
properties [1, 2, 3, 4]. The closing of a spectral gap is also intimately
connected to the occurrence of topological quantum phase transitions, since
the modern definition of a quantum phases relies on the existence of a path of
gapped Hamiltonians through Hastings’ notion of quasi-adiabatic evolution [5,
6, 7]. The stability of spectral gaps under various “local” perturbations of
the Hamiltonian is an active research area [8, 9, 10, 11, 12], and to make use
of these stability results it is of course beneficial to have a wide net of
gapped Hamiltonians available for further stability analysis. Generally,
questions concerning spectral gaps are at the heart of many of the most
challenging open problems in physics. Two examples are Haldane’s conjecture
that the antiferromagnetic Heisenberg chain is gapped for integer spin values
[13, 14]. and the Yang-Mills mass gap, a millennium problem. For additional
background about the relevance of spectral gaps, see [15, 7].

Given the fact that the existence of a spectral gap has strong physical
implications, there has been significant interest in identifying mathematical
techniques for deriving a spectral gap rigorously. It has been found that with
very few exceptions, only special frustration-free Hamiltonians are amenable
to a rigorous analysis of the spectral gap. We recall that frustration-free
Hamiltonians play a central role in quantum many-body theory, for example for
classification of topological phases of quantum matter and for quantum error
correcting codes. For a highly incomplete list of examples, we mention that
the toric code and Levin–Wen models are paradigms of topological quantum
computation [16, 17], AKLT ground states [18] are universal resource states
for measurement-based quantum computation [19, 20, 21, 22], Motzkin
Hamiltonians provided the first examples with volume-entanglement [23, 24],
and product vacua with boundary states (PVBS) [25, 26, 27] provided hands-on
models for topological quantum phase transitions. Frustration-free
Hamiltonians also arise generally as the parent Hamiltonians of matrix product
states (MPS) or projected entangled pair states (PEPS) and are thus central to
the study of tensor network states. The main reason for their usefulness is
that they are among the few many-body Hamiltonians that can be rigorously
analyzed.

The seminal work of Affleck-Kennedy-Lieb-Tasaki [18] derived the spectral gap
for their eponymous (frustration-free) AKLT chain. This has led to a large
number of follow-up works which also focus on special frustration-free
Hamiltonians which can be analyzed by one of the standard methods, the
martingale method [25, 26, 27, 28] or finite-size criteria [29, 30, 31, 32,
33, 34], or their combination, [35, 36].

While the study of these specific frustration-free Hamiltonians leads to
numerous insights, it leaves open the physically very relevant question
whether generic frustration-free Hamiltonians are gapped or not. Part of the
motivation for asking this question is that random Hamiltonians are considered
key models for quantum chaos. As a consequence, a new avenue of research [37,
38, 39] has recently emerged which asks the question whether gaps are common
or uncommon.

It is worth pointing out that there exist heuristic physical arguments both
for and against the commonality of gaps: On the one hand, as reviewed above,
gaps place extremely strong constraints on ground states which suggests they
are rare in some sense. On the other hand, the closing of the gap is
associated with a quantum phase transition, which suggests that most systems
should be gapped (i.e., not at the brink of a quantum phase transition). To
further highlight that this is a subtle problem, we recall that Movassagh [39]
proved that spatially disordered Hamiltonians are generically gapless in any
dimension. Movassagh’s argument fundamentally relied on the decoupling of rare
local regions from the bulk of the system and thus fundamentally on the non-
translation-invariance of the Hamiltonians. A natural follow-up question was
then what happens in the translation-invariant setting where this mechanism is
absent. Concretely, we would like to address the following question:

Does a typical translation-invariant frustration-free local Hamiltonian have a
spectral gap?

Here the word “typical” refers to an underlying probability measure on the
space of translation-invariant, nearest-neighbor Hamiltonians which is made
precise in Subsection 2.1 below. The main model parameters are

$\displaystyle D=$ $\displaystyle\textnormal{spatial lattice dimension},$
$\displaystyle d=$ $\displaystyle\textnormal{local qudit dimension},$
$\displaystyle r=$ $\displaystyle\textnormal{ rank of interaction}.$

The Hamiltonians are normalized to have local ground state energy zero and so
the rank $r$ equals $d^{2}-\textnormal{local ground state dimension}$. We will
be interested in models of sufficiently small rank $r$, or equivalently, of
sufficiently large local ground space dimension. The point is that choosing a
sufficiently small $r$ is a way to ensure frustration-freeness which is well-
known for line graphs [40].

Indeed, this makes intuitive sense: A small rank is the same as a large local
ground space dimension. This makes it easier for the local ground states to
overlap sufficiently to obtain a global ground state which does not frustrate
any local interaction. As a consequence, the well-known examples frustration-
free Hamiltonians have only moderate rank $r$ compared to the maximal allowed
rank $d^{2}$ for nearest-neighbor interactions. For example, the AKLT chain
has $r=5$ and $d^{2}=9$, Motzkin Hamiltonians have $r=3$ and $d^{2}=9$, and
product vacua with boundary states (PVBS) have $r=(d-1)(d+2)/2$. This
heuristic beckons the question whether small $r$ is sufficient to ensure
frustration-freeness by a general argument. Here, we will give a general,
rigorous proof that the resulting Hamiltonians are always frustration-free if
$r$ is sufficiently small. See Lemma 2.4 for the precise mathematical
statement. This relies on a QSAT criterion from [41] and the rigorous Kotecky-
Preiss criterion for the convergence of the cluster expansion from classical
statistical mechanics [42].

Regarding the experimental realizability of the small rank constraint, we
first recall that a standard setup to realize quantum spin systems are cold
quantum gases, e.g., constrained by optical lattices. A common way to increase
single-bond ground state degeneracy (i.e., to lower the interaction rank) is
to coarse-grain the Heisenberg antiferromagnetic two-spin interaction by
introducing the higher-order coupling $(\vec{S}_{x}\cdot\vec{S}_{y})^{2}$ to
obtain a spectral projector as is done, e.g., in the AKLT Hamiltonian.
Orbital-dependent Hubbard models are expected to display these higher-order
couplings and hence e.g. the AKLT Hamiltonian experimentally [43]. While it
can be challenging to realize small interaction ranks in the laboratory, this
challenge is shared among almost all frustration-free Hamiltonians. In
summary, progress on the ongoing program of realizing frustration-free
Hamiltonians in the laboratory will likely translate to the Hamiltonians
considered here. A particular advantage of the construction we provide is that
it is flexible about the underlying graph structure and can thus be readily
adapted to pertinent experimental constraints.

With Lemma 2.4 at hand, we have produced a natural model of translation-
invariant frustration-free nearest-neighbor Hamiltonians. The next step is to
analyze the typical spectral gap. Our main result says that these random
Hamiltonians are gapped with positive probability independent of system size
(Theorem 2.2). Together with [39], which treated the spatially disordered
case, this proves rigorously that gaps are strictly more common in the
presence of translation-invariance.

As reviewed below, our first result is the first that applies to graphs of
dimension $>1$. Previous works [37, 38] in the frustration-free setting were
restricted to quantum spin chains, i.e., line graphs.

Our result paves the way to a broader understanding of the gaps of
frustration-free Hamiltonians and their ground state properties. Given that
these ground states and their gaps are central tools for the modern definition
of quantum phases, understanding their landscape is of clear theoretical
relevance. In addition, gaps have significant practical implications for the
lifetimes of quantum states, e.g., for quantum memory or measurement-based
quantum computation. For example, AKLT ground states on various graphs are
universal resource states for measurement-based quantum computation [19, 20,
21, 22] which are known to be protected by a gap since recently [29, 31, 33,
34]. Our result raises the possibility of widely expanding the class of gap-
protected universal resource states for MBQC by analyzing the ground states of
the gapped Hamiltonians we identify here. We would like to mention that the
method we use to prove the main result Theorem 2.2 not only yields positive
probability of the spectral gap, it also identifies the types of local
interactions that produce a gap. This is important for potentially realizing
the Hamiltonians we find here physically. The details can be found in Remark
2.3 (i).

An advantage of our method (finite-size criteria) is that it also gives a
system size-independent lower bound on the local gap. The local gap has
recently received attention because it is needed to obtain the 2D area law in
the recent breakthrough of Anshu-Arad-Gosset [44]. The problem in general is
that the local gap can in principle be much smaller than the global gap. Here,
we are able to prove that this does not happen by deriving a lower bound on
the local gap of our random Hamiltonians. Consequently, we are able to provide
for the first time a broad class of examples of 2D Hamiltonians satisfying the
area law. See Subsection 2.5 for the details.

##  2 Model an main results

###  2.1 The random Hamiltonians

We consider a nearest-neighbor Hamiltonian acting on a system of qudits,
described by local Hilbert spaces ${\mathbb{C}}^{d}$, which are placed on a
$D$-dimensional discrete box ${\Lambda}_{L}=((-L,L]\cap{\mathbb{Z}})^{D}$ of
side length $2L$. The total Hilbert space is
$\bigotimes_{x\in{\Lambda}_{L}}{\mathbb{C}}^{d}$ and the Hamiltonian is given
by

$H_{{\Lambda}_{L}}=\sum_{x\in{\Lambda}_{L}}\sum_{j=1}^{D}P^{j}_{x,x+e_{j}}$
(2.1)

with periodic or open boundary conditions. We say that the Hamiltonian is
translation-invariant if all the local interactions pointing in the same
direction act identically. Formally, this means we have

$\displaystyle
P^{j}_{x,x+e_{j}}=P^{j}\otimes\mathrm{Id}_{{\Lambda}_{L}\setminus\\{x,x+e_{j}\\}},$
$\displaystyle\textnormal{for all }x\in{\Lambda}_{L}\textnormal{ and all
}j=1,\ldots,D$

with fixed prototypes
$P^{1},\ldots,P^{D}:{\mathbb{C}}^{d}\otimes{\mathbb{C}}^{d}\to{\mathbb{C}}^{d}\otimes{\mathbb{C}}^{d}$,
one for every direction; see Figure 1. Note that we do not assume isotropy of
the local interaction, i.e., the prototypes $P^{1},\ldots,P^{D}$ may differ
for different directions. We assume that the local interaction is an
orthogonal projection of rank $r$.

Figure 1: The Hamiltonian (2.1) on the square lattice: $P^{1}$ acts in the
$e_{1}$-direction and $P^{2}$ acts in the $e_{2}$-direction.

To turn these $H_{{\Lambda}_{L}}$’s into a family of random translation-
invariant Hamiltonians, we only need to sample the prototypes for local
interactions $P^{1},\ldots,P^{D}$ from a suitable probability distribution.
For simplicity, we assume henceforth that the random projections
$P^{1},\ldots,P^{D}$ are independent and identically distributed and each
$P^{j}$ is the projection onto the first $r$ columns of a Haar-random
orthogonal matrix. The use of Haar measure is natural; indeed, it is
equivalent to selecting the $r$ spanning vectors uniformly from the unit
sphere, with different vectors chosen independently modulo the orthogonality
constraint. Many other choices are possible and easily implementable, cf.
Remark 2.3 (ii) below.

######  Remark 2.1 (Possible extensions).

We close the presentation with a brief discussion of the assumptions on the
underlying probability measure. Recall that we took the distribution of the
random projections $P^{1},\ldots,P^{D}$ to be i.i.d. with each $P^{j}$ given
as projection onto the first $r$ columns of a Haar-random orthogonal matrix.
While independence is helpful, some correlation between different directions
can be accommodated, but the proof does not apply to the isotropic case
$P^{1}=\ldots=P^{D}$. There is a lot of freedom in choosing the underlying
probability measure of each $P^{j}$, as long as the small-rank assumption is
verified. More precisely, the choice of probability measure only enters in the
proof of [38, Lemma 7] which is used to obtain (4.8) below. This lemma was
proved in [38] for Haar measure but the proof extends verbatim to any
probability measure such that basis vectors are independent modulo
orthonormality and the induced probability measure for an individual basis
vector assigns positive probability to each spherical cap. For interactions of
full rank, one can instead use a perturbative result by Yarotsky [45] to
obtain a gap with positive probability.

###  2.2 Previous results

So far, the literature on the spectral gap problem for random translation-
invariant Hamiltonians has been restricted to quantum spin chains, meaning
that $D=1$, so the graph is a line ${\Lambda}_{L}=\\{1,2,\ldots,L\\}$. We
denote the 1D Hamiltonian by

$H_{L}^{\mathrm{1D}}\equiv H_{{\Lambda}_{L}}=\sum_{x=1}^{L}P_{x,x+1}$

where we chose periodic boundary conditions, identifying $L+1\equiv 1$. The
following is known in 1D.

  * •

For local dimension $d=2$ and rank $r=1$, Bravyi-Gosset [37] proved that, with
probability $1$, the quantum spin chain Hamiltonian $H_{L}^{\mathrm{1D}}$ is
gapped.

  * •

For arbitrary local dimension $d$ and rank $r\leq d-1$, [38] proved that the
quantum spin chain Hamiltonian $H_{L}^{\mathrm{1D}}$ is gapped with positive
probability.

We recall that we say that the family of $H_{L}^{\mathrm{1D}}$’s is gapped (or
$H_{L}^{\mathrm{1D}}$ is gapped for short) if there exists a universal
constant $c>0$ such that for all $L$, the spectral gap above the ground state
satisfies ${\gamma}(H_{L}^{\mathrm{1D}})\geq c>0$. We remark that [37] analyze
the $d=2$ and $r=1$ case in additional detail; they obtain a complete
description of the spectral gap phase diagram in terms of the one-dimensional
subspace in ${\mathbb{C}}^{4}$ that one projects on.

###  2.3 Main result

The main result of this work breaks the dimensional barrier and extends the
previous results of [37, 38] from one-dimensional line graphs to arbitrary
graphs for the first time. Similarly to those work, we need to assume that the
rank $r$ is sufficiently small compared to the local qudit dimension $d$.

######  Theorem 2.2 (Main result).

Assume that

$r\leq\min\left\\{\frac{\lfloor\frac{d^{2}}{4}\rfloor}{D},\frac{e^{-1}}{4D-1}d^{2}\right\\}.$
(2.2)

Then, $H_{{\Lambda}_{L}}$ is gapped with probability bounded below by $p>0$.

More precisely, the result says that there exists $c>0$ and a positive
probability $p>0$ such that

$\mathbb{P}({\gamma}(H_{{\Lambda}_{L}})\geq c)\geq p>0.$ (2.3)

Importantly, the constants $c>0$ and $p>0$ depend only on the order-$1$ system
parameters $D,d$ and $r$ and not on the system size $L$. Similarly, it is an
important feature of condition (2.2) that it only depends only on these
order-$1$ system parameters and again $L$ is not involved. (For example,
taking rank $r=1$ and spatial dimension $D=2$, condition (2.2) holds whenever
the local qudit dimension $d\geq 4$.) The fact that these quantities are
independent of $L$ is crucial for a meaningful derivation of a spectral gap in
the thermodynamic limit $L\to\infty$.

In words, our result can be summarized as the following answer to (a more
precise version of) the question formulated in the introduction:

A random translation-invariant Hamiltonians with local interaction of small
rank has a positive probability of being gapped.

We recall that the small-rank assumption should be understood as ensuring
frsutration-freeness. The precise statement is in Lemma 2.4.

A few remarks about Theorem 2.2 are in order.

######  Remark 2.3.

  1. (i)

As in [38], the proof is based on the verification of a finite-size criterion
with positive probability. The argument is constructive: it provides explicit
choices of local projections $P$ for which the Hamiltonian is gapped.
Concretely, the interaction $P$ is obtained by taking the local projections to
be onto the span of $r$ of the vectors

$w_{ij}=|i\otimes j\rangle,\qquad\textnormal{for $i\leq d$ odd and $j\leq d$
even}.$

and then perturbing these vectors on the unit sphere of
$\mathbb{C}^{d}\otimes\mathbb{C}^{d}$ within a sufficiently small spherical
cap. Further details can be found in Subsection 4.2. The fact that any
sufficiently small perturbation inside the spherical cap yields a gap is
practically relevant, as it ensures that the implementation is stable against
perturbations of the local interaction which may be present in experiments.

  2. (ii)

It is possible to make the constants $c$ and $p$ in (2.3) explicit.

  3. (iii)

The proof generalizes to other graphs, e.g., the honeycomb lattice, as
explained in Section 5.

Let us also compare our result to undecidability results on the spectral gap
problem [46, 47]. Specifically, the work [47] constructs a 2D Hamiltonian
whose spectral gap problem is equivalent to the halting problem for Turing
machines and therefore algorithmically and logically undecidable. The relevant
Hamiltonians require very special choices of local interactions which form a
zero-measure set for almost any choice of probability measure on interactions.
In view of this, it is very likely that the spectral gap problem is
generically decidable. Hence, the question whether the spectral gap problem is
decidable is somewhat orthogonal to the question about the typical value of
the gap that we consider here.

Despite these a priori different perspective, we believe that the usefulness
of small rank that we leverage here may shed further light on the
undecidability question. The point is that the special examples constructed in
[47] require large rank. Our work then raises the question whether the small
rank assumption can be leveraged even further to address decidability of the
gap for sufficiently small rank interactions. Note that this is what Bravy-
Gosset obtained in 1D, where there is a similar undecidability result [46].

###  2.4 Small rank implies frustration-freeness

A key step in the proof is to show that Assumption (2.2) on the parameters
ensures that $H_{{\Lambda}_{L}}$ is frustration-free (i.e.,
$\inf\mathrm{spec}\,H_{{\Lambda}_{L}}=\\{0\\}$). This is non-trivial because
it leverages information about the local model parameters $r$ and $d$ to
derive the global property of frustration-freeness.

The result holds for general graphs of bounded degree and may be of
independent interest. Given a graph $G=(K,E)$, let

$H_{G}=\sum_{e\in E}P_{e}$

be a nearest-neighbor Hamiltonian with all local interactions $P_{e}$ of rank
$r$. We still denote the local qudit dimension by $d$.

######  Lemma 2.4.

Let $G$ be a graph with degree bounded by ${\delta}$. Assume that

$r\leq\frac{e^{-1}}{2{\delta}-1}d^{2}.$ (2.4)

Then $H_{G}$ is frustration-free.

An intuitive explanation for this result is again that small interaction rank
corresponds to large local ground state space, which leaves more “room” in the
Hilbert space for the system to find a global ground state that is also a
local ground state everywhere (i.e., that is frustration-free).

This important lemma rests on verifying the statistical mechanics style QSAT
criterion from [41] (recalled as Theorem 3.3 below) through bounds on the
partition function of a classical hard-core dimer system that we derive from
the cluster expansion method (Kotecký-Preiss criterion [42]).

###  2.5 Bounds on the local gap and application to the area law

In fact, our method lower bounds the local gap. We recall that the local gap
plays a key role in the recent breakthrough of Anshu, Arad, and Gosset [44]
who proved that non-degenerate ground states of locally gapped frustration-
free 2D Hamiltonians satisfy an area law. This is a 2D analog of a famous 1D
result by Hastings [2]. Here we will use a variant that is adapted to highly
degenerate ground spaces [48]; see also [49].

Generalizing the definition of local gap from [44, Eq. (41)] to arbitrary
graphs, we obtain the following.

######  Definition 2.5 (Local gap).

Let $G$ be a graph. The local gap is given by

${\gamma}_{\mathrm{loc},G}=\min_{S\subset G}{\gamma}(H_{S}).$ (2.5)

The new area law criterion from [44] requires a lower bound on
${\gamma}_{\mathrm{loc},G}$ at least when $S$ varies over rectangle in
${\mathbb{Z}}^{2}$. Consequently, lower bounds of the local gap have become of
significant interest. Note the trivial bound

${\gamma}_{\mathrm{loc},G}\leq{\gamma}_{G},$ (2.6)

so a lower bound on the local gap is more difficult to derive than a lower
bound on the usual, global gap. Fortunately, our argument can be strengthened
to give a lower bound on the local gap.

######  Theorem 2.6 (Local gap version of main result).

Under the assumptions of Theorem 2.2, there exist $c>0$ and a positive
probability $p>0$ such that

$\mathbb{P}({\gamma}_{\mathrm{loc},{\Lambda}_{L}}\geq c)\geq p>0.$

The only difference compared to Theorem 2.2 is the replacement of
${\gamma}_{{\Lambda}_{L}}$ by ${\gamma}_{\mathrm{loc},{\Lambda}_{L}}$. Our
technique to control the local gap will be discussed in Subsection 2.6.

######  Remark 2.7.

While it is generally expected that the gap decreases with system size, which
would suggest a reverse inequality to (2.6), this heuristic can likely fail
for certain subsystems due to boundary effects of finite systems. It is an
interesting open problem to derive any kind of converse to (2.6), even
restricting to the local gap over rectangles that enters in [44].

Recalling the area-law criterion from [44] and considering Lemma 2.4 and
Theorem 2.6, we see that only the non-degenerateness of the ground space can
fail for our models. In fact, one can use Theorem 3.3 to see that the ground
space is exponentially degenerate in system size for certain parameter values.
While methods exist for extending the result of [44] to degenerate ground
spaces [49], they come with an additional contribution to the entanglement
entropy of $\log\dim(\textnormal{ground space})$ which becomes volume-like,
and thus uninformative, for exponential ground space degeneracy.

Instead, we rely on a modified version of the area law that is obtainable by
combining the methods from [44] and [1]. In terms of techniques, these works
rely on the approximate ground state projector (AGSP) that is well-suited for
frustration-free Hamiltonians.

We now state this novel variant criterion [48]. Let the graph
$G=([-L,L]\cap{\mathbb{Z}})^{2}$ be a box in ${\mathbb{Z}}^{2}$. We split the
Hilbert space into left and right halves in the natural way

$\mathcal{H}=\mathcal{H}_{\mathrm{left}}\otimes\mathcal{H}_{\mathrm{right}}.$

Given a ground state $\psi$ of $H_{G}$, we let

$\rho_{\psi}^{\mathrm{left}}=\mathrm{Tr}_{\mathcal{H}_{\mathrm{right}}}|\psi\rangle\langle\psi|$

equal the partial trace over the right half. The entanglement entropy of the
left and right halves is then given by

$S(\rho_{\psi}^{\mathrm{left}})=-\mathrm{Tr}\rho_{\psi}^{\mathrm{left}}\log\rho_{\psi}^{\mathrm{left}}.$
(2.7)

The following result holds deterministically for any Hamiltonian of the form
(2.1).

######  Theorem 2.8 (Area law criterion, [44, 48]).

Let $D=2$. Suppose that $H_{{\Lambda}_{L}}$ is frustration-free and there
exists $c>0$ independent of $L$ such that ${\gamma}_{\mathrm{loc},G}\geq c>0$.

Then, there exists a ground state $\psi$ of $H_{G}$ that satisfies an area law
for the entanglement entropy, i.e.,

$S(\rho_{\psi}^{\mathrm{left}})\leq CL^{1+(\log L)^{-1/5}}$ (2.8)

As pointed out to us by [48], this follows directly from the validity of the
AGSP condition, cf. [44, 1].

######  Remark 2.9.

The logarithmic correction in (2.8) does not play any important role. The
result can be generalized if desired, e.g., to any cut and to rectangular
(i.e., non-square) domains. Moreover, only a lower bound on the local gap over
rectangles and L-shaped regions is needed as in [44].

Our main results then imply that the random translation-invariant Hamiltonians
are among the small number of non-trivial examples of 2D Hamiltonians that
provably have ground states satisfying an area law.

######  Corollary 2.10 (Area law).

Let $D=2$ and assume that (2.2) holds.

Then, with a positive probability $p>0$ that is independent of $L$,
$H_{{\Lambda}_{L}}$ has a ground state satisfying the area law (2.8).

In closing, we remark that this result does not rely on PEPS techniques and,
indeed, it does not identify the ground state satisfying the area law as a
PEPS state.

###  2.6 Finite-size criteria automatically control local gaps

In this short section, we would like to emphasize a methodological point. The
local gap bound from Theorem 2.6 rests on the observation that the standard
Knabe finite-size criterion for the gap [50] can be easily extended to also
lower bound the local gap, which as reviewed above has recently emerged as an
important quantity in quantum information theory. This shows that there is an
efficient method available for lower bounding the local gap—finite-size
criteria.

Let $j,k=1,\ldots,D$. We introduce the local $3$-site Hamiltonians

$\displaystyle H_{j}=$ $\displaystyle P^{j}_{-e_{j},0}+P^{j}_{0,e_{j}},$ (2.9)
$\displaystyle H^{++}_{jk}=$ $\displaystyle P^{j}_{0,e_{j}}+P^{k}_{0,e_{k}},$
$\displaystyle H^{-+}_{jk}=$ $\displaystyle P^{j}_{-e_{j},0}+P^{k}_{0,e_{k}},$
$\displaystyle H^{--}_{jk}=$ $\displaystyle
P^{j}_{-e_{j},0}+P^{k}_{-e_{k},0}.$

These local Hamiltonians cover all the possibilities by which adjacent edges
can interact. We denote their common minimal spectral gap by

${\gamma}_{3}=\min_{j,k=1,\ldots,D}\min\left\\{{\gamma}(H_{j}),{\gamma}(H^{++}_{jk}),{\gamma}(H^{-+}_{jk}),{\gamma}(H^{--}_{jk})\right\\}.$
(2.10)

######  Proposition 2.11 (Finite-size criterion for the local gap in any
dimension).

Let $H_{{\Lambda}_{L}}$ be frustration-free. Then

${\gamma}_{\mathrm{loc},{\Lambda}_{L}}\geq(4D-2)\left({\gamma}_{3}-\frac{4D-3}{4D-2}\right)$
(2.11)

The proof is a generalization of the one from [50]. It is included in the
appendix for the convenience of the reader. The number $\frac{4D-3}{4D-2}$ is
commonly called the gap threshold. We refer to [51, 52, 53, 15, 54] for other
improvements and generalizations of Knabe’s finite-size criterion, especially
for hypercubic lattices.

###  2.7 The one-dimensional case

Upon revisiting the construction in the one-dimensional spin chain setting
[38], we observe here that by tweaking the construction in [38], the range of
ranks can be improved up to a natural limit. The 1D random Hamiltonian is of
the simple form

$H_{L}=\sum_{x=1}^{L-1}P_{x,x+1},$

where we chose open boundary conditions for definiteness. (The same proof
applies verbatim to periodic boundary conditions.)

######  Theorem 2.12 (Improved 1D result).

Let $r\leq\max\\{\tfrac{d^{2}}{4},d-1\\}$. Then $H_{L}$ is gapped with
positive probability.

This strictly extends the main result of [38] whenever $\tfrac{d^{2}}{4}\geq
d$, i.e., whenever $d\geq 4$. The assumption
$r\leq\max\\{\tfrac{d^{2}}{4},d-1\\}$ is precisely what guarantees
frustration-freeness [40] and so the range of ranks covered by Theorem 2.12 is
a natural limit point of existing methods, as these all require frustration-
freeness.

The restriction to $r\leq d-1$ in the previous work [38] arose due to a
technical issue that we resolve here. See Appendix A for the details.

##  3 Frustration-freeness

In this section, we prove Lemma 2.4 using the QSAT criterion Theorem 3.3 from
[41]. These results hold on general graphs.

The criterion concerns the classical partition function of the nearest-
neighbor exlusion on the interaction graph associated to $H_{G}$. We take some
care to formulate the criterion directly in a way that is suitable for our
purposes:

  * •

We define the partition function with the notation of [42]. This is convenient
for implementing the cluster expansion method to bound the partition function
afterwards.

  * •

We focus on edge graphs which are the interaction graphs of nearest-neighbor
interactions such as our $P_{x,x+e_{j}}$.

######  Definition 3.1 (Partition function of nearest-neighbor exclusion).

Consider a graph $\mathcal{G}=(\mathcal{K},\mathcal{E})$. Given two vertices
$\gamma_{1},\gamma_{2}\in\mathcal{K}$, we write $\gamma_{1}\iota\gamma_{2}$
(read: $\gamma_{1}$ is joined to $\gamma_{2}$) or equivalently
$(\gamma_{1},\gamma_{2})\in\iota$ if $\gamma_{1}$ and $\gamma_{2}$ are either
equal or connected by an edge. Let $\mathcal{D}_{0}(\mathcal{G})$ be the set
of admissible subsets $\partial\subset\mathcal{K}$, i.e., for every
$\gamma_{1},\gamma_{2}\in\partial$, $(\gamma_{1},\gamma_{2})\not\in\iota$. Let
$\mathcal{B}(G)$ denote the set of subsets $\partial\subset K$ that are
connected, in the sense that any partition $S_{1},S_{2}\subset\partial$ with
$S_{1}\cup S_{2}=\partial$ is such that there exists $\gamma_{1}\in S_{1}$ and
$\gamma_{2}\in S_{2}$ such that $\gamma_{1}\iota\gamma_{2}$. The grand-
canonical partition function of the nearest-neighbor exclusion on
$\mathcal{G}$ at fugacity $z\in\mathbb{C}$ is

$\mathcal{Z}(\mathcal{G};z)=\sum_{\partial\in\mathcal{D}_{0}(\mathcal{G})}z^{|\partial|},$
(3.1)

where $|\partial|$ is the cardinality of $\partial$.

We will consider the nearest-neighbor exclusion not on the original graph $G$,
but on its edge graph $G^{\prime}$ defined as follows.

######  Definition 3.2 (Edge graph).

Given a graph $G=(K,E)$ we define the edge graph $G^{\prime}$. The set of
vertices of $G^{\prime}$ is the set $E$ of edges of $G$. For every pair
$e,e^{\prime}\in E$, $G^{\prime}$ has an edge between $e$ and $e^{\prime}$ if
and only if $e$ and $e^{\prime}$ share a vertex in $G$ (that is, $e\cap
e^{\prime}\neq\emptyset$).

The QSAT criterion reads as follows.

######  Theorem 3.3 (QSAT criterion [41]).

Let $G$ be a graph. Let $p=\frac{r}{d^{2}}$ and suppose that

$\mathcal{Z}(G^{\prime};-p^{\prime})>0,\qquad p^{\prime}\in[0,p].$ (3.2)

Then

$\dim\ker H_{G}\geq\mathcal{Z}(G^{\prime};-p)d^{|G|}>0.$ (3.3)

This can be considered a quantum analog of Shearer’s theorem. We recall that
the lower bound $\dim\ker H_{G}>0$ implies that $H_{G}$ is frustration-free.

The main work of this section is then to verify condition (3.2) of Theorem 3.3
in order to derive Lemma 2.4. We achieve this via the cluster expansion
method, specifically the Kotecký-Preiss criterion.

###  3.1 Cluster expansion bound

Before we state the Kotecký-Preiss criterion, a bibliographical comment is in
order. The cluster expansion is used in this paper for a nearest-neighbor
exclusion model on a graph. In this simple setting, the cluster expansion
should really be called a Mayer expansion, whose introduction dates back to
[55, 56]. We will need an estimate for the error of the Mayer expansion, and
such estimates can be found in the literature as far back as the early 1960’s
[57, 58]. Here, we have opted for the more general Kotecký-Preiss formulation
[42], as it is directly applicable to discrete systems (graphs), whereas many
of the older references are stated in the continuum (despite the fact that
their proofs are easily generalizable to graphs).

We consider a graph $\mathcal{G}=(\mathcal{K},\mathcal{E})$ of bounded degree.
We denote the maximal degree of $\mathcal{G}$ by $\Delta-1$. We let
$\mathcal{Z}(\mathcal{G};z)$ be as in Definition 3.1.

######  Theorem 3.4 (Kotecký-Preiss criterion [42]).

If there exists $a\geqslant 0$ such that, for all $\gamma\in\mathcal{K}$,

$\sum_{\gamma^{\prime}:\ \gamma^{\prime}\iota\gamma}e^{a}|z|\leqslant a$ (3.4)

then $\mathcal{Z}(\mathcal{G};z)\neq 0$, and there exists a function
$\Phi^{T}:\mathcal{B}(\mathcal{G})\to\mathbb{C}$ such that

$\log\mathcal{Z}(\mathcal{G};z)=\sum_{C\in\mathcal{B}(\mathcal{G})}\Phi^{T}(C)$
(3.5)

furthermore,

$\sum_{C\in\mathcal{B}(\mathcal{G}):\ C\iota\gamma}|\Phi^{T}(C)|\leqslant a$
(3.6)

where $C\iota\gamma$ means that $\gamma^{\prime}\iota\gamma$ for all
$\gamma^{\prime}\in C$.

The following conclusion of this theorem is tailored to our purposes.

######  Corollary 3.5.

For $0\leqslant p^{\prime}\leqslant\frac{e^{-1}}{\Delta}$, we have

$\mathcal{Z}(\mathcal{G};-p^{\prime})\geqslant e^{-|K|e^{1}\Delta
p^{\prime}}.$ (3.7)

###### Proof of Corollary 3.5.

We introduce the specific free energy

$f_{\mathcal{G}}(z)=\frac{1}{|\mathcal{K}|}\log\mathcal{Z}(\mathcal{G};z),$
(3.8)

with $|\mathcal{K}|$ the cardinality of $\mathcal{K}$. We claim that if

$|z|\leqslant\frac{e^{-1}}{\Delta}$ (3.9)

then

$|f_{\mathcal{G}}(z)|\leqslant e^{1}\Delta|z|$ (3.10)

Suppose that (3.9) holds. We aim to apply Theorem 3.4. The condition (3.4) is

$|z|\leqslant\frac{ae^{-a}}{\Delta}.$ (3.11)

In order to choose $a$ as small as possible, we choose it to saturate the
inequality

$ae^{-a}=\Delta|z|.$ (3.12)

Indeed, since $a\mapsto ae^{-a}$ is an increasing function for $a\leqslant 1$,
condition (3.12) has a solution if and only if (3.9) holds.

Furthermore, (3.5) implies that

$|\log\mathcal{Z}(\mathcal{G};z)|\leqslant\sum_{\gamma\in\mathcal{K}}\sum_{C\in\mathcal{B}(\mathcal{G}):\
C\iota\gamma}|\Phi^{T}(C)|$ (3.13)

and so, by (3.6),

$|f_{\mathcal{G}}(z)|\leqslant a\leqslant e^{1}\Delta|z|.$ (3.14)

This proves (3.10) and hence (3.7). ∎

###  3.2 Proof of frustration-freeness

###### Proof of Lemma 2.4.

We aim to apply Theorem 3.3 and are thus led to consider
$\mathcal{Z}(G^{\prime},p^{\prime})$. Elementary considerations show that the
edge graph satisfies the maximal degree bound

$\Delta-1\leq 2({\delta}-1).$

Assumption (2.2) ensures that

$p=\frac{r}{d^{2}}\leq\frac{e^{-1}}{2{\delta}-1}\leq\frac{e^{-1}}{\Delta}.$

Hence, by Corollary 3.5 with $\mathcal{G}=G^{\prime}$, we have for all
$p^{\prime}\in[0,p]$ the estimate

$\mathcal{Z}(G^{\prime};-p)\geq e^{-|E|e\Delta p}>0,$

where we used that the vertex set of the edge graph $G^{\prime}$ is equal to
the edge set $E$ of the original graph $G$.

Hence, we can apply Theorem 3.3 to conclude that

$\dim\ker H_{G}\geq\mathcal{Z}(G^{\prime};-p)d^{|G|}>0$

and so $H_{G}$ is frustration-free. ∎

##  4 Bounds on the spectral gap

###  4.1 Proof of finite-size criterion for the local gap

###### Proof of Proposition 2.11.

Let $S\subset{\Lambda}_{L}$ be an arbitrary subgraph. Without loss of
generality, $S$ is connected. (Indeed, if $S$ is the disjoint union of $S_{1}$
and $S_{2}$, then
${\gamma}(H_{S})=\min\\{{\gamma}(H_{S_{1}}),{\gamma}(H_{S_{2}})\\}$.) The
following is an extension of Knabe’s argument [50] to any dimension without
assuming isotropy. The underlying observation is that by restricting on the
right-hand side of Proposition (2.11) to $3$-vertex subgraphs, we can control
the gap of any subgraph $S\subset{\Lambda}_{L}$.

By the spectral theorem and frustration-freeness, the claim is equivalent to
the operator inequality

$H_{S}^{2}\geq(4D-2)\left({\gamma}_{3}-\frac{4D-3}{4D-2}\right)H_{S}.$ (4.1)

Since the $P^{j}_{x,x+e_{j}}$ are projections, we have

$H_{S}^{2}=H_{S}+Q_{S}+R_{S}$

where $Q_{S}$ contains the terms of the form
$\\{P^{j}_{x,x+e_{j}},P^{k}_{y,y+e_{k}}\\}$ so that the edges
$\\{x,x+e_{j}\\}$ and $\\{y,y+e_{j}\\}$ share exactly one vertex and $R_{S}$
contains the terms $\\{P_{x,x+e_{j}},P_{y,y+e_{k}}\\}$ so that the edges
$\\{x,x+e_{j}\\}$ and $\\{y,y+e_{j}\\}$ do not share any vertex. Note that
$R_{S}$ is positive definite by commutativity. Hence,

$H_{S}^{2}\geq H_{S}+Q_{S}.$ (4.2)

We define the auxiliary operator

$\displaystyle\mathcal{A}_{S}=$ $\displaystyle\sum_{x\in
S}\sum_{j=1}^{D}(H_{j,x})^{2}$ $\displaystyle+\sum_{x\in
S}\left(\sum_{j,k=1}^{D}\left(\left(H^{++}_{jk,x}\right)^{2}+\left(H^{-+}_{jk,x}\right)^{2}+\left(H^{--}_{jk,x}\right)^{2}\right)\right)$

where the subindex $x$ denotes a shift by $x$ compared to (2.9), e.g.,
$H^{-+}_{jk,x}=P^{j}_{x-e_{j},x}+P^{k}_{x,x+e_{k}}$, etc.

Let ${\delta}_{x}\leq 2D$ denote the degree of vertex $x\in S$ within the
subgraph induced by $S$. On the one hand, we can expand the square and
interchange the order of summation to find

$\mathcal{A}_{S}=\sum_{x\in
S}\sum_{j=1}^{D}({\delta}_{x}+{\delta}_{x+e_{j}}-2)P^{j}_{x,x+e_{j}}+Q_{S}.$

On the other hand, by translation-invariance, frustration-freeness, and the
spectral theorem, we have the operator inequality

$\displaystyle\mathcal{A}_{S}\geq$ $\displaystyle{\gamma}_{3}\sum_{x\in
S}\left(\sum_{j=1}^{D}H_{j,x}+\sum_{j,k=1}^{D}\left(H^{++}_{jk,x}+H^{-+}_{jk,x}+H^{--}_{jk,x}\right)\right)$
$\displaystyle=$ $\displaystyle{\gamma}_{3}\sum_{x\in
S}\sum_{j=1}^{D}({\delta}_{x}+{\delta}_{x+e_{j}}-2)P^{j}_{x,x+e_{j}}$

Combining these, we obtain

$\displaystyle Q_{S}\geq$ $\displaystyle\left({\gamma}_{3}-1\right)\sum_{x\in
S}\sum_{j=1}^{D}({\delta}_{x}+{\delta}_{x+e_{j}}-2)P^{j}_{x,x+e_{j}}$
$\displaystyle\geq$ $\displaystyle(4D-2)\left({\gamma}_{3}-1\right)H_{S},$

where the second step uses ${\gamma}_{3}\leq 1$ and $1\leq{\delta}_{x}\leq
2D$. We now use (4.2) to conclude (4.1). ∎

###  4.2 Proof of the main result

In this section, we prove the main result, Theorem 2.2. Some details are
parallel to [38] and will be skipped. An important difference here compared to
[38] is the choice of “good” vectors $w_{ij}$ in (4.5); see also Appendix A.

###### Proof of Theorem 2.2.

By applying Lemma 2.4 with $G={\Lambda}_{L}$, so ${\delta}=2D$ and using
(2.2),we obtain that $H_{{\Lambda}_{L}}$ is frustration-free. Hence we can
apply Proposition 2.11 by which it suffices to show

${\gamma}_{3}>\frac{4D-3}{4D-2}.$ (4.3)

We can lower bound ${\gamma}_{3}$ by using the anticommutator bound from Lemma
6.3(ii) in [59]. Recall (2.9) and introduce the set of pairs of projections
appearing in it, i.e.,

$\displaystyle\mathcal{P}=$
$\displaystyle\left\\{\\{P^{j}_{-e_{j},0},P^{j}_{0,e_{j}}\\},\\{P^{j}_{0,e_{j}},P^{k}_{0,e_{k}}\\},\right.$
$\displaystyle\;\left.\\{P^{j}_{-e_{j},0},P^{k}_{0,e_{k}}\\},\\{P^{j}_{-e_{j},0},P^{k}_{-e_{k},0}\\}\right\\}_{j,k=1,\ldots,D}$

Inspecting the proof of Theorem 5 in [38], we obtain the gap bound

${\gamma}_{3}\geq 1-\max_{\\{P,Q\\}\in\mathcal{P}}\|PQ-P\wedge Q\|$

where $P\wedge Q$ is the orthogonal projection onto the subspace
$\mathrm{ran}\,P\cap\mathrm{ran}\,Q$.

Hence, the claim (4.3) reduces to

$\max_{\\{P,Q\\}\in\mathcal{P}}\|PQ-P\wedge Q\|<\frac{1}{4D-2}.$ (4.4)

To prove (4.4), we proceed via an auxiliary family of “good” projectors
$\tilde{P}^{1},\ldots,\tilde{P}^{D}$. (This generalizes an idea of [38],
though, the choice of good projectors is quite different here.) First, we set

$w_{ij}=|i\otimes j\rangle,\qquad\textnormal{for $i\leq d$ odd and $j\leq d$
even}.$ (4.5)

Note that the total number of these vectors is $\frac{d^{2}}{4}$ if $d$ is
even and $\frac{d^{2}-1}{4}$ if $d$ is odd. Equivalently, the total number of
these vectors is $\tilde{d}:=\lfloor\frac{d^{2}}{4}\rfloor$. Let
$\\{v_{1},\ldots,v_{\tilde{d}}\\}$ be an enumeration of the set
$\\{w_{i,j}\\}$. Now we define the rank-$r$ good projectors

$\tilde{P}^{j}=\sum_{i=(j-1)r+1}^{jr}P_{v_{i}},\qquad j=1,\ldots,D,$ (4.6)

where $P_{v_{i}}$ projects onto $v_{i}$. Note that defining $\tilde{P}^{D}$
uses our assumption in (2.2) that
$Dr\leq\tilde{d}=\lfloor\frac{d^{2}}{4}\rfloor$.

It is then elementary to check from (4.5) the key property that

$\tilde{P}\tilde{Q}=\tilde{P}\wedge\tilde{Q}=0$ (4.7)

for all pairs $\\{\tilde{P},\tilde{Q}\\}$ belonging to the set

$\displaystyle\tilde{\mathcal{P}}=$
$\displaystyle\left\\{\\{\tilde{P}^{j}_{-e_{j},0},\tilde{P}^{j}_{0,e_{j}}\\},\\{\tilde{P}^{j}_{0,e_{j}},\tilde{P}^{k}_{0,e_{k}}\\},\right.$
$\displaystyle\;\left.\\{\tilde{P}^{j}_{-e_{j},0},\tilde{P}^{k}_{0,e_{k}}\\},\\{\tilde{P}^{j}_{-e_{j},0},\tilde{P}^{k}_{-e_{k},0}\\}\right\\}_{j,k=1,\ldots,D}$

Indeed, this is obvious for $j\neq k$ because the ranges of $\tilde{P}$ and
$\tilde{Q}$ are orthogonal, while for
$\\{\tilde{P},\tilde{Q}\\}=\\{\tilde{P}^{j}_{-e_{j},0},\tilde{P}^{j}_{0,e_{j}}\\}$
this relies on the parity structure in (4.5) and the fact that even indices
are paired with odd ones at the center site $0$.

Now we proceed with a perturbative argument. Specifically, we apply Lemma 7 in
[38], which follows from some geometrical estimates for spherical caps, to the
particular collection of vectors $\\{v_{1},\ldots,v_{\tilde{d}}\\}$. This
yields, for any ${\varepsilon}>0$, vectors
$\\{\phi_{1},\ldots,\phi_{\tilde{d}}\\}$ such that

$\mathbb{P}\left(\sup_{1\leq
i\leq\tilde{d}}\|v_{i}-\phi_{i}\|<{\varepsilon}\right)\geq p_{\varepsilon}>0.$
(4.8)

From now on, we assume that, for some ${\varepsilon}>0$ to be determined, we
have taken $\\{\phi_{1},\ldots,\phi_{\tilde{d}}\\}$ such that this event
occurs, i.e., $\|v_{i}-\phi_{i}\|<{\varepsilon}$ holds for all $1\leq
i\leq\tilde{d}$.

We recall a classical theorem of von Neumann [60] which says that for any pair
of projections $P,Q$,

$P\wedge Q=s-\lim_{n\to\infty}(PQ)^{n},$

and consequently $\|P\wedge Q\|\leq\liminf_{n\to\infty}\|PQ\|^{n}$, leading us
to

$\|PQ-P\wedge Q\|\leq\|PQ\|+\liminf_{n\to\infty}\|PQ\|^{n}.$ (4.9)

Given $\\{P,Q\\}\in\mathcal{P}$, we let $\\{\tilde{P},\tilde{Q}\\}$ be the
corresponding pair in $\mathcal{P}$. Then we estimate
$\|PQ\|=\|PQ-\tilde{P}\tilde{Q}\|$ by using $\|v_{i}-\phi_{i}\|<{\varepsilon}$
and following the same steps as in [38] to conclude that

$\|PQ\|\leq 4r{\varepsilon}.$ (4.10)

For ${\varepsilon}<\frac{1}{4r}$, we obtain
$\liminf_{n\to\infty}\|PQ\|^{n}=0$. Finally, we choose ${\varepsilon}>0$ small
enough such that $4r{\varepsilon}<\frac{1}{4D-2}$. Then (4.9) implies (4.4)
and hence Theorem 2.2. ∎

##  5 Extension to other directed graphs

In this short section, we explain how the proof method can be generalized to
other directed graphs. After some general remarks, we focus for definiteness
on the specific example of the honeycomb lattice which is commonplace in
applications; see, e.g., [31, 34].

###  5.1 General discussion

Recall Definition (2.1) of the Hamiltonian and observe the following two
features: (i) the Hamiltonian is defined on oriented edges (the orientation
matters because $P^{j}_{x,x+e_{j}}\neq P^{j}_{x+e_{j},x}$) and (ii) the
symmetry structure of the Euclidean lattice enters because it allows to set
interactions on collinear edges equal. Point (ii) is no longer available for a
general directed graph which does not necessarily have obvious “partner”
directions such as the collinear ones in the Euclidean case, though, other
lattice graphs come with their own symmetries.

At any rate, also without symmetries, we can define a random Hamiltonian on a
general $k$-regular directed graph by independently sampling the prototypical
$k$ local interactions $P^{1},\ldots,P^{k}$ at any vertex at random. That is,
all local interactions are sampled independently, which is different from the
construction in the Euclidean case. Once a random translation-invariant
Hamiltonian is defined in this way, the argument can be adapted. This is
possible because we are able to ensure frustration-freeness for general graphs
via Lemma 2.4 thanks to the cluster expansion. It is notationally slightly
cumbersome to formulate an explicit construction of the random translation-
invariant Hamiltonian on general $k$-regular directed graphs after the local
interaction prototypes $P^{1},\ldots,P^{k}$ have been sampled. Hence, we find
it most instructive to consider an explicit example and so we focus on the
honeycomb lattice in the following.

###  5.2 The honeycomb lattice

Let $\mathbb{H}_{L}=(K,E)$ denote the honeycomb lattice wrapped on an $L\times
L$ torus. We place a qudit ${\mathbb{C}}^{d}$ at each site of
$\mathbb{H}_{L}$, so we consider the Hilbert space
$\bigotimes_{x\in\mathbb{H}_{L}}{\mathbb{C}}^{d}$. Fix any orientation of the
edges. Let $r\geq 1$. As before, let
$P^{1},P^{2},P^{3}:{\mathbb{C}}^{d}\otimes{\mathbb{C}}^{d}\to{\mathbb{C}}^{d}\otimes{\mathbb{C}}^{d}$
denote three i.i.d. random rank $r$ projections with the distribution of each
$P^{j}$ given as the projection onto the first $r$ columns of a Haar-random
orthogonal matrix. The random translation-invariant Hamiltonian on the
honeycomb lattice is given by

$H_{\mathbb{H}_{L}}=\sum_{\vec{e}\in E}P^{t(\vec{e})}_{\vec{e}}$

Here, for any directed edge $\vec{e}=(x,y)$, we set
$P^{j}_{\vec{e}}=P_{x,y}\otimes\mathrm{Id}_{\mathbb{H}_{L}\setminus\\{x,y\\}}$
and we introduced the type $t(\vec{e})$,

$t(\vec{e})=\begin{cases}1,\qquad\mathrm{span}\\{y-x\\}\textnormal{ parallel
to $(1,0)$-axis},\\\ 2,\qquad\mathrm{span}\\{y-x\\}\textnormal{ at angle
$\frac{\pi}{3}$ to $(1,0)$-axis},\\\
3,\qquad\mathrm{span}\\{y-x\\}\textnormal{ at angle $\frac{2\pi}{3}$ to
$(1,0)$-axis}.\end{cases}$

######  Theorem 5.1 (Honeycomb lattice).

Assume that

$r\leq\min\left\\{\frac{\lfloor\frac{d^{2}}{4}\rfloor}{3},\frac{e^{-1}}{5}d^{2}\right\\}$

Then, there exist $c>0$ and a positive probability $p>0$ such that

$\mathbb{P}({\gamma}_{\mathrm{loc},{\Lambda}_{L}}\geq c)\geq p>0.$

###### Proof.

Since $r\leq\frac{e^{-1}}{5}d^{2}$, we can apply Lemma 2.4 to conclude that
$\mathbb{H}_{L}$ is frustration-free. The proof of the finite-size criterion
in Proposition 2.11 generalizes straightforwardly to any frustration-free
Hamiltonian on a bounded degree graph; in that case, ${\gamma}_{3}$ is the
minimal gap that occurs when restricting the corresponding Hamiltonian to $3$
connected sites. Using $r\leq\frac{\lfloor\frac{d^{2}}{4}\rfloor}{3}$, the
good projections $\tilde{P}^{1},\tilde{P}^{2},\tilde{P}^{3}$ can be defined
exactly as in (4.6) in terms of the same good vectors (4.5). The same argument
as before implies (4.7). Then we use [38, Lemma 7] as the basis of the
perturbative argument. The details are analogous to the Euclidean lattice case
and are hence ommitted. ∎

## Acknowledgments

We are grateful to Anurag Anshu and Zeph Landau for kindly informing us of
their observation [48] that the main result of [44] extends to degenerate
ground spaces in the form of Theorem 2.8. We acknowledge support by Open
Access Publishing Fund of University of Tübingen.

## References

  * [1] Itai Arad, Zeph Landau, Umesh Vazirani, and Thomas Vidick.  “Rigorous RG algorithms and area laws for low energy eigenstates in 1D”.  Communications in Mathematical Physics 356, 65–105 (2017).
  * [2] Matthew B Hastings.  “An area law for one-dimensional quantum systems”.  Journal of statistical mechanics: theory and experiment 2007, P08024 (2007).
  * [3] Matthew B Hastings and Tohru Koma.  “Spectral gap and exponential decay of correlations”.  Communications in mathematical physics 265, 781–804 (2006).
  * [4] Bruno Nachtergaele and Robert Sims.  “Lieb-Robinson bounds and the exponential clustering theorem”.  Communications in mathematical physics 265, 119–130 (2006).
  * [5] Sven Bachmann, Spyridon Michalakis, Bruno Nachtergaele, and Robert Sims.  “Automorphic equivalence within gapped phases of quantum lattice systems”.  Communications in Mathematical Physics 309, 835–871 (2012).
  * [6] Matthew B Hastings.  “Lieb-Schultz-Mattis in higher dimensions”.  Physical review b 69, 104431 (2004).
  * [7] Bruno Nachtergaele, Robert Sims, and Amanda Young.  “Quasi-locality bounds for quantum lattice systems. I. Lieb-Robinson bounds, quasi-local maps, and spectral flow automorphisms”.  Journal of Mathematical Physics 60, 061101 (2019).
  * [8] Sergey Bravyi, Matthew B Hastings, and Spyridon Michalakis.  “Topological quantum order: stability under local perturbations”.  Journal of mathematical physics 51, 093512 (2010).
  * [9] Simone Del Vecchio, Jürg Fröhlich, Alessandro Pizzo, and Stefano Rossi.  “Lie–schwinger block-diagonalization and gapped quantum chains with unbounded interactions”.  Communications in Mathematical Physics 381, 1115–1152 (2021).
  * [10] Wojciech De Roeck and Manfred Salmhofer.  “Persistence of exponential decay and spectral gaps for interacting fermions”.  Communications in Mathematical Physics 365, 773–796 (2019).
  * [11] Spyridon Michalakis and Justyna P Zwolak.  “Stability of frustration-free Hamiltonians”.  Communications in Mathematical Physics 322, 277–302 (2013).
  * [12] Bruno Nachtergaele, Robert Sims, and Amanda Young.  “Stability of the bulk gap for frustration-free topologically ordered quantum lattice systems” (2021).
  * [13] F Duncan M Haldane.  “Continuum dynamics of the 1-D Heisenberg antiferromagnet: Identification with the $O(3)$ nonlinear sigma model”.  Physics letters a 93, 464–468 (1983).
  * [14] F Duncan M Haldane.  “Nonlinear field theory of large-spin Heisenberg antiferromagnets: semiclassically quantized solitons of the one-dimensional easy-axis Néel state”.  Physical review letters 50, 1153 (1983).
  * [15] Marius Lemm and Evgeny Mozgunov.  “Spectral gaps of frustration-free spin systems with boundary”.  Journal of Mathematical Physics 60, 051901 (2019).
  * [16] Alexei Kitaev.  “Anyons in an exactly solved model and beyond”.  Annals of Physics 321, 2–111 (2006).
  * [17] Michael A Levin and Xiao-Gang Wen.  “String-net condensation: A physical mechanism for topological phases”.  Physical Review B 71, 045110 (2005).
  * [18] Ian Affleck, Tom Kennedy, Elliott H Lieb, and Hal Tasaki.  “Valence bond ground states in isotropic quantum antiferromagnets”.  Communications in Mathematical Physics 115, 477–528 (1988).
  * [19] Akimasa Miyake.  “Quantum computational capability of a 2D valence bond solid phase”.  Annals of Physics 326, 1656–1671 (2011).
  * [20] Frank Verstraete and J Ignacio Cirac.  “Valence-bond states for quantum computation”.  Physical Review A 70, 060302 (2004).
  * [21] Tzu-Chieh Wei, Ian Affleck, and Robert Raussendorf.  “Affleck-Kennedy-Lieb-Tasaki state on a honeycomb lattice is a universal quantum computational resource”.  Physical review letters 106, 070501 (2011).
  * [22] Tzu-Chieh Wei, Poya Haghnegahdar, and Robert Raussendorf.  “Hybrid valence-bond states for universal quantum computation”.  Physical Review A 90, 042333 (2014).
  * [23] Ramis Movassagh and Peter W Shor.  “Supercritical entanglement in local systems: Counterexample to the area law for quantum matter”.  Proceedings of the National Academy of Sciences 113, 13278–13282 (2016).
  * [24] Zhao Zhang, Amr Ahmadain, and Israel Klich.  “Novel quantum phase transition from bounded to extensive entanglement”.  Proceedings of the National Academy of Sciences 114, 5142–5146 (2017).
  * [25] Sven Bachmann and Bruno Nachtergaele.  “Product vacua with boundary states and the classification of gapped phases”.  Communications in Mathematical Physics 329, 509–544 (2014).
  * [26] Sven Bachmann, Eman Hamza, Bruno Nachtergaele, and Amanda Young.  “Product Vacua and Boundary State Models in $d$ Dimensions”.  Journal of Statistical Physics 160, 636–658 (2015).
  * [27] Michael Bishop, Bruno Nachtergaele, and Amanda Young.  “Spectral gap and edge excitations of d-dimensional PVBS models on half-spaces”.  Journal of Statistical Physics 162, 1485–1521 (2016).
  * [28] Bruno Nachtergaele.  “The spectral gap for some spin chains with discrete symmetry breaking”.  Communications in mathematical physics 175, 565–606 (1996).
  * [29] Houssam Abdul-Rahman, Marius Lemm, Angelo Lucia, Bruno Nachtergaele, and Amanda Young.  “A class of two-dimensional AKLT models with a gap”.  Analytic Trends in Mathematical Physics 741, 1–21 (2020).
  * [30] Marius Lemm and Bruno Nachtergaele.  “Gapped PVBS models for all species numbers and dimensions”.  Reviews in Mathematical Physics 31, 1950028 (2019).
  * [31] Marius Lemm, Anders W Sandvik, and Ling Wang.  “Existence of a spectral gap in the Affleck-Kennedy-Lieb-Tasaki model on the hexagonal lattice”.  Physical review letters 124, 177204 (2020).
  * [32] Marius Lemm, Anders W Sandvik, and Sibin Yang.  “The AKLT model on a hexagonal chain is gapped”.  Journal of Statistical Physics 177, 1077–1088 (2019).
  * [33] Nicholas Pomata and Tzu-Chieh Wei.  “AKLT models on decorated square lattices are gapped”.  Physical Review B 100, 094429 (2019).
  * [34] Nicholas Pomata and Tzu-Chieh Wei.  “Demonstrating the Affleck-Kennedy-Lieb-Tasaki spectral gap on 2d degree-3 lattices”.  Physical review letters 124, 177203 (2020).
  * [35] Bruno Nachtergaele, Simone Warzel, and Amanda Young.  “Spectral Gaps and Incompressibility in a $\nu=1/3$ Fractional Quantum Hall System”.  Communications in Mathematical Physics 383, 1093–1149 (2021).
  * [36] Simone Warzel and Amanda Young.  “A bulk spectral gap in the presence of edge states for a truncated pseudopotential”.  In Annales Henri Poincaré.  Pages 1–46.  Springer (2022).
  * [37] Sergey Bravyi and David Gosset.  “Gapped and gapless phases of frustration-free spin-$1/2$ chains”.  Journal of Mathematical Physics 56, 061902 (2015).
  * [38] Marius Lemm.  “Gaplessness is not generic for translation-invariant spin chains”.  Physical Review B 100, 035113 (2019).
  * [39] Ramis Movassagh.  “Generic local Hamiltonians are gapless”.  Physical review letters 119, 220504 (2017).
  * [40] Ramis Movassagh, Edward Farhi, Jeffrey Goldstone, Daniel Nagaj, Tobias J Osborne, and Peter W Shor.  “Unfrustrated qudit chains and their ground states”.  Physical Review A 82, 012318 (2010).
  * [41] Or Sattath, Siddhardh C Morampudi, Chris R Laumann, and Roderich Moessner.  “When a local Hamiltonian must be frustration-free”.  Proceedings of the National Academy of Sciences 113, 6433–6437 (2016).
  * [42] Roman Koteckỳ and David Preiss.  “Cluster expansion for abstract polymer models”.  Communications in Mathematical Physics 103, 491–498 (1986).
  * [43] Maciej Koch-Janusz, DI Khomskii, and Eran Sela.  “Affleck-Kennedy-Lieb-Tasaki State on a Honeycomb Lattice from $t_{2g}$ Orbitals”.  Physical Review Letters 114, 247204 (2015).
  * [44] Anurag Anshu, Itai Arad, and David Gosset.  “An area law for 2D frustration-free spin systems”.  In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing.  Pages 12–18.  (2022).
  * [45] DA Yarotsky.  “Uniqueness of the ground state in weak perturbations of non-interacting gapped quantum lattice systems”.  Journal of statistical physics 118, 119–144 (2005).
  * [46] Johannes Bausch, Toby S Cubitt, Angelo Lucia, and David Perez-Garcia.  “Undecidability of the spectral gap in one dimension”.  Physical Review X 10, 031038 (2020).
  * [47] Toby S Cubitt, David Perez-Garcia, and Wolf Michael M.  “Undecidability of the spectral gap”.  Nature 528, 207–211 (2015).
  * [48] Anurag Anshu and Zeph Landau.  personal communication.
  * [49] Nilin Abrahamsen.  “Sharp implications of AGSPs for degenerate ground spaces” (2020).
  * [50] Stefan Knabe.  “Energy gaps and elementary excitations for certain VBS-quantum antiferromagnets”.  Journal of statistical physics 52, 627–638 (1988).
  * [51] Anurag Anshu.  “Improved local spectral gap thresholds for lattices of finite size”.  Physical Review B 101, 165104 (2020).
  * [52] David Gosset and Evgeny Mozgunov.  “Local gap threshold for frustration-free spin systems”.  Journal of Mathematical Physics 57, 091901 (2016).
  * [53] Marius Lemm.  “Finite-size criteria for spectral gaps in D-dimensional quantum spin systems”.  Analytic trends in mathematical physics 741, 121 (2020).
  * [54] Marius Lemm and David Xiang.  “Quantitatively improved finite-size criteria for spectral gaps”.  Journal of Physics A: Mathematical and Theoretical 55, 295203 (2022).
  * [55] Joseph E Mayer.  “The statistical mechanics of condensing systems. I”.  The Journal of Chemical Physics 5, 67–73 (1937).
  * [56] HD Ursell.  “The evaluation of Gibbs’ phase-integral for imperfect gases”.  In Mathematical Proceedings of the Cambridge Philosophical Society.  Volume 23, pages 685–697.  Cambridge University Press (1927).
  * [57] J Groeneveld.  “Two theorems on classical many-particle systems”.  Phys. Letters3 (1962).
  * [58] David Ruelle.  “Statistical mechanics: Rigorous results”.  World Scientific. (1999).
  * [59] Mark Fannes, Bruno Nachtergaele, and Reinhard F Werner.  “Finitely correlated states on quantum spin chains”.  Communications in mathematical physics 144, 443–490 (1992).
  * [60] J Von Neumann.  “Functional Operators, Vol. II. The Geometry of Orthogonal Spaces (this is a reprint of mimeographed lecture notes first distributed in 1933) Annals of Math”.  Studies Nr. 22 Princeton Univ. Press (1950).

##  Appendix A Improvement of the main result in [38]

###### Proof of Theorem 2.12.

Let $r\leq\max\\{\tfrac{d^{2}}{4},d-1\\}$. Without loss of generality, we
assume that $r=\lfloor\tfrac{d^{2}}{4}\rfloor\geq d$. We take for granted the
entire analysis in [38] and only mention where the critical change occurs. We
replace the vectors

$v_{i}=|1\otimes(i+1)\rangle,\qquad\textnormal{for }1\leq i\leq r$

(of which there exist at most $d-1$, hence the restriction), by the family

$w_{ij}=|i\otimes j\rangle,\qquad\textnormal{for $i\leq d$ odd and $j\leq d$
even}.$

The key property of these vectors is that thanks to the parity structure we
have

$\tilde{P}_{1,2}\tilde{P}_{2,3}=0,\qquad\textnormal{where
}\tilde{P}=\sum_{\begin{subarray}{c}i\leq d\textnormal{ odd}\\\ j\leq
d\textnormal{ even}\end{subarray}}w_{i,j}.$

By orthogonality, the rank of $\tilde{P}$ is given by

$\mathrm{rank}\,\tilde{P}=\begin{cases}\frac{d^{2}}{4},\qquad&\textnormal{ if
$d$ is even},\\\ \frac{d^{2}-1}{4},\qquad&\textnormal{ if $d$ is
odd}.\end{cases}$

or equivalently $\mathrm{rank}\,\tilde{P}=\lfloor\frac{d^{2}}{4}\rfloor$ which
equals $r$ by assumption.

The rest of the argument goes exactly as in [38] mutatis mutandis. We omit the
details. ∎