Research Article

When a local Hamiltonian must be frustration-free

Or Sattath, Siddhardh C. Morampudi, Chris R. Laumann, and Roderich Moessner
PNAS June 7, 2016 113 (23) 6433-6437; first published May 19, 2016; https://doi.org/10.1073/pnas.1519833113

  1. Edited by Peter W. Shor, Massachusetts Institute of Technology, Cambridge, MA, and approved April 1, 2016 (received for review October 7, 2015)

Significance

Quantum computers promise computational power qualitatively superior to that achievable classically. This power will not be unlimited: Beyond much-touted applications, such as breaking encryption schemes, entire classes of problems are known to be intractable even for quantum computers. This work addresses a question of great practical relevance: In between these two extremes of certain (in)tractability, how can one efficiently diagnose the nature and properties of a given problem instance? To achieve this, we adopt a strategy of transferring insights from statistical physics and classical computing into the quantum realm. This provides a new perspective on the complexity of quantum problems and allows us to analyze a canonical class of quantum optimization problems in unprecedented explicit detail.

Abstract

A broad range of quantum optimization problems can be phrased as the question of whether a specific system has a ground state at zero energy, i.e., whether its Hamiltonian is frustration-free. Frustration-free Hamiltonians, in turn, play a central role for constructing and understanding new phases of matter in quantum many-body physics. Unfortunately, determining whether this is the case is known to be a complexity-theoretically intractable problem. This makes it highly desirable to search for efficient heuristics and algorithms to, at least, partially answer this question. Here we prove a general criterion—a sufficient condition—under which a local Hamiltonian is guaranteed to be frustration-free by lifting Shearer’s theorem from classical probability theory to the quantum world. Remarkably, evaluating this condition proceeds via a fully classical analysis of a hardcore lattice gas at negative fugacity on the Hamiltonian’s interaction graph, which, as a statistical mechanics problem, is of interest in its own right. We concretely apply this criterion to local Hamiltonians on various regular lattices, while bringing to bear the tools of spin glass physics that permit us to obtain new bounds on the satisfiable to unsatisfiable transition in random quantum satisfiability. We are then led to natural conjectures for when such bounds will be tight, as well as to a novel notion of universality for these computer science problems. Besides providing concrete algorithms leading to detailed and quantitative insights, this work underscores the power of marrying classical statistical mechanics with quantum computation and complexity theory.

An overwhelming majority of systems of physical interest can be described via local Hamiltonians:H=∑i=1M Πi.[1]Here, the “k-local” operator Πi acts on a k-tuple of the microscopic degrees of freedom, best thought of as qudits for the computer scientists among our readers or spins for the physicists. The M operators define an interaction (hyper)graph G, displayed in Fig. 1.

Fig. 1.
Fig. 1.

(Left) The interaction graph of a k=3-local Hamiltonian. The degrees of freedom, qudits, are denoted by circles; the squares, which indicate the operators Πi appearing in H, are joined to the qudits on which they act. In the hardcore lattice gas mapping, each square may be occupied by a particle covering also the adjacent circles (shaded blobs), on which it must not overlap with another particle. (Right) A k=6 interaction graph forming a triangular lattice of the operators Πi. The corresponding hardcore lattice gas corresponds to the hard hexagon model, which is exactly solvable.

A surprisingly diverse and important class of such model Hamiltonians is defined by the additional property of being “frustration-free”: The ground state |ψ〉 of H is a simultaneous ground state of each and every Πi. This class comprises both commuting Hamiltonians—for which [Πi,Πj]=0 ∀i,j—such as the toric code, general quantum error correcting codes, and Levin–Wen models (1⇓–3), and noncommuting ones, such as the Affleck-Kennedy-Lieb-Tasaki (AKLT) and Rokhsar–Kivelson models (4⇓–6). Their particular usefulness is also related to the fact that many of these examples can be viewed as “local parent Hamiltonians” for generalized matrix product states (7). In general, frustration-free conditions provide analytic control of ground state properties in otherwise largely inaccessible quantum problems.

Determining whether a given Hamiltonian H is frustration-free is well known in quantum complexity theory as the quantum satisfiability (QSAT) problem. QSAT is widely believed to be intractable, in the sense that no general purpose classical or quantum algorithm can efficiently determine whether a given Hamiltonian is frustration-free (“satisfiable”). The technical statement is that QSAT is complete for the Quantum Merlin Arthur complexity class (QMA1-complete) (8), even when restricted to qubits and k=3 (9) or when the interaction is between neighboring qudits on a line (10).

Fortunately, such hardness results apply only in the worst case. For instance, in contrast to the hardness result, it is immediately obvious that a fully disconnected interaction graph G can be analyzed efficiently by considering each term Πi individually.

The central result reported here is a sufficient combinatorial criterion for a local Hamiltonian H to be frustration-free. In fact, we provide a lower bound for the dimension of the satisfying subspace. This amounts to a generalization of Shearer’s theorem (11) from classical probability theory to the quantum world.

We first formulate the result in Theorem 1, followed by an intuitive explanation of its content, with a technical proof relegated to SI Appendix. We then turn to applying Theorem 1, for which we enlist the results available on statistical mechanics of hardcore objects with negative fugacity on the interaction graph to deduce statements regarding QSAT, producing new bounds on the satisfiability threshold for a large class of 1D, 2D, and 3D interaction graphs. With the help of the cavity method, we are able to conjecture improved lower bounds for the satisfiability of QSAT on regular and Erdős–Rényi random graphs, canonical models for quantum constraint optimization problems. These statement hold just as well for classical satisfiability—but for some of these classical models better bounds are known (12, 13).

We close with an outlook, including a discussion of the role of a universality that emerges in our analysis, as well as conjectures on when our results are exact or tight.

Theorem 1.

Given a local projector Hamiltonian H as in Eq. 1 with interaction graph G and relative projector rank p=R(Im Πi) for all i, thenR(ker H)≥Z(G,−p)>0if Z(G,−p′)>0 for all 0≤p′≤p.

Without loss of generality, we have taken the terms Πi to be projectors so that the satisfiability condition reduces to the presence of a zero-energy ground state. (This may always be done by shifting and deforming the eigenvalues of the local Hamiltonian terms without influencing the frustration-free ground state space.)

Here, the relative dimension of a subspace X of the full Hilbert space ℋ is simply R(X)=dimX/dimℋ, and, Z(G,λ) is the partition function for a hardcore lattice gas of fat particles living on the (hyper)edges of the interaction graph at fugacity λ (Fig. 1). More precisely,Z(G,λ)=∑{ni}λ∑ni∏i↔j(1−ninj),[2]where i↔j runs over all projectors that share qudits and the sum runs over occupations ni=0,1 of the lattice gas.

Intuition

Let us first consider the case of classical projectors, Πi, diagonal in the standard computational basis, where we can provide a simple pictorial representation of the content of the Shearer bound. The operator ∏i(1−Πi) projects onto the zero-energy space of the Hamiltonian. If it is nonzero, the Hamiltonian is frustration-free. Moreover, its expectation value in the maximally mixed (infinite temperature) state gives the relative dimension of the zero-energy space,R(ker H)=∏i=1M(1−Πi)¯.[3]If all of the projectors act on different qudits, then this expectation value simply factorsR(ker H)=∏i=1M(1−Πi)¯=(1−p)M,where p=Πi¯ is the relative dimension of Πi. This is nonzero as long as p<pc=1.

Now suppose that some of the projectors share qudits; we call such pairs of projectors dependent, as they introduce dependence into the expectation value in Eq. 3. When can we, nevertheless, guarantee that R(kerH) remains positive? The essence of the Shearer bound is captured by the Venn diagram in Fig. 2, where each bubble represents the fraction of configuration space “knocked out” by a projector, with overlapping bubbles representing configurations multiply penalized by the corresponding projectors.

Fig. 2.
Fig. 2.

Shearer bound for dependent projectors. Projectors are independent if they do not share any qudit (Top Left), and there will always exist configurations violating any combination of such projectors simultaneously. In the Venn diagram (Top Right), this is represented by the mutual intersections of the shaded circles, each of which denotes the fraction of configuration space penalized by the projector it is labeled with. By contrast, for dependent projectors (Bottom Left), such an overlap is not guaranteed. A lower bound for the relative dimension of the satisfying space can be obtained by assuming the projectors Πi and Πl do not share any violating configurations with the projector Πj with which they share a qudit (Bottom Right).

The area covered by the bubbles is largest if they do not overlap, corresponding to a large number of violating configurations; we thus expect a lower bound on R(kerH) when they are fully disjoint. To calculate this lower bound, we expand the product in Eq. 3 and introduce a collection of occupation variables ni=0,1 that indicate the presence of Πi in each term of the expansion,R(ker H)=∑{ni}(−1)∑niΠ1n1⋯ΠMnM¯.[4]If two dependent projectors, Πi and Πj, are thus occupied, then that term is zero when their bubbles are made disjoint. Otherwise, it is given by p∑ni. Thus,R(ker H)≥∑{ni}(−p)∑ni∏i↔j(1−ninj)=Z(G,−p),[5]where i↔j runs over projectors that share qudits.

We have derived inequality [5] under the assumption that it is possible to make the dependent bubbles disjoint. If p is small enough, this is always the case; in the Venn diagram, the bubbles can be made disjoint without covering more area than the total space contains. Shearer (11, 14) showed that the above intuitive lower bound is correct for classical projectors as long as p≤pc, where pc is the first zero of Z(G,−p). This is the classical analog of our quantum generalization, Theorem 1.

The classical sketch above makes little sense for noncommuting quantum projectors. In the language of probability, this reflects the failure of the inclusion–exclusion principle (Eq. 4) for the relative dimension of vector spaces. Nonetheless, the result holds; the proof—our fundamental technical advance—is provided in SI Appendix, Proof of Theorem 1.

Statistical Mechanical Transcription

A remarkable aspect of Theorem 1 is that it maps the quantum satisfiability problem onto the classical statistical mechanical problem of determining the position of the first negative fugacity zero λc(G) of the partition function Z(G,λ). In general, evaluating Z is computationally hard, but for many infinite graphs it may nonetheless be accomplished in a satisfactory manner using statistical mechanical tools. [Technically, computing Z is #P-hard almost everywhere (15).] In the thermodynamic limit (number of qudits N→∞), the first zero λc(G) can be identified with a well-known critical point λc(G∞) of the hardcore lattice gas referred to as the hardcore singularity. The critical fugacity λc(G∞) upper bounds the λc of any finite subgraph by monotonicity (11). Thus, Theorem 1 implies that all subgraphs of G∞ are frustration-free as long as the relative rank of the projectors satisfies p<−λc(G∞).

The hardcore singularity has been studied extensively in the statistical mechanical literature (16⇓⇓⇓⇓⇓⇓⇓⇓–25) and its location is known for many infinite lattices. Table 1 summarizes some of these critical values and indicates their translation into QSAT interaction graphs. In addition, there exist rigorous bounds on λc that may be efficiently calculated on any sufficiently simple lattice (16). The singularity exhibits universal features just like standard phase transitions. In particular, the free energy density f(λ)=(1/N)log Z(λ) near the critical point λc has universal exponents (21, 22) due to its connection with the so-called Yang-Lee edge singularity (24⇓⇓⇓–28). Technically, this means that the leading nonanalytic part of the free energy f∼(λ−λc)ϕD near λc, where ϕD is a noninteger critical exponent that depends only on the spatial dimension D of the lattice (21, 22, 24). It is known analytically that ϕ1=1/2, ϕ2=5/6 (20, 29, 30), and ϕD=3/2 for D above the upper critical dimension DC=6 (24).

View this table:
Table 1.

Summary of the critical threshold for various infinite interaction graphs

The critical exponents control the lower bounds on the dimension of the ground space of Hamiltonians close to the critical threshold. Indeed, by Theorem 1, R(ker H)≥enf(λ)∝ean(λ−λc)ϕD+O(λ−λc) for λ>λc, so the critical exponents show up directly—and perhaps somewhat unexpectedly—as anomalous growth laws in D=1,2 (SI Appendix, Improved Bounds Using the Critical Exponents). In the following, observation of the expected exponent in the random k-QSAT ensemble helps confirm the validity of the nonrigorous cavity analysis.

Examples

As a first application of Theorem 1, we calculate the critical threshold λc for several infinite graphs. We do this using the cavity method, a well-known technique for studying statistical (31) and quantum (32⇓–34) models on infinite graphs that are locally tree-like. On trees and chains, the results are rigorously exact whereas on infinite random graphs they are less rigorous, but often just as exact.

The heart of the cavity method is to introduce an auxiliary system of messages that propagate in both directions between the hyperedges and the nodes of the interaction graph G. For the model given by Eq. 2, the derivation is straightforward and quite intuitive at positive fugacity where the cavity messages correspond to marginal distributions for the gas particles (SI Appendix, The Cavity Derivations). The resulting equations continue smoothly to the negative fugacity regime. Adopting the convention that indexes i,j,… label hyperedges and a,b,… label sites, the belief propagation (BP) equations (for a recent pedagogical treatment, see ref. 35, chap. 14) areqa→i=λλ+1+∑jϵ∂a\ilj→a1−lj→ali→a=λλ+Πbϵ∂i\a(λqb→i−λ),where li→a and qa→i give the probability that hyperedge i is occupied in the absence of the connection to a and in the absence of everything except a, respectively. We note that a special case of these equations has been used previously to study the number of dimer coverings of random graphs (k=2, positive fugacity) (36).

Given a solution of the BP equations, the cavity estimate of the free energy F=log Z of the system is given by a sum of the free energies associated to the addition of individual elements of the interaction graph; i.e.,F=∑a Fa+∑i Fi−∑(ai) Fai,[6]where Fa, Fi, and Fai correspond to the change in free energy due to the addition of sites a, hyperedges i, and the links ai between them, respectively. The full expressions may be found in SI Appendix, The Cavity Derivations.

The Chain

On the infinite chain, the BP equations can be solved by uniform messages qa→i=q, li→a=l. After some algebra and taking the root of the BP equations corresponding to q(λ=0)=0, one finds l=q=1+(1−1+4λ)/2λ. This expression suggests that λc=−1/4 as q becomes complex for λ<λc. Indeed, it is easy to check that the free energy density f=F/N (Eq. 6) has the expansion near λc:f=−log⁡2+2(λ−λc)1/2−2(λ−λc)+⋯.The free energy goes complex for λ<λc, which reflects the accumulation of partition function zeros and indicates the failure of the lower bound.

The free energy density is precisely −log⁡2 at the critical point. For qudits of local dimension q, this provides a lower bound on the dimension of the ground space dim(ker H)=qNR(ker H)≥(q/2)N. In fact, careful application of Theorem 1 for finite chains agrees with the exact result dim(ker H)=(q/2)N(N+1) for open chains derived using matrix-product techniques (37, 38). It is interesting to note that the entropy per site is zero for qubits at criticality, but has a finite value for larger q.

Regular Trees

The BP equations on infinite regular trees with site degree t and hyperedge degree k can be solved under the ansatz that all messages are the same. For algebraic details, see SI Appendix, The Cavity Derivations. The resulting critical threshold isλc=−1t−1(k−1)k−1kk.[7]For k=2-local trees, this agrees with previous results obtained by matrix product states on trees (39). As far as we are aware, Eq. 7 provides a strictly better lower bound on satisfiability of infinite regular trees than any previous literature. The corresponding expansion of the free energy density isf=f0(t,k)+A(t,k)(λ−λc)+B(t,k)(λ−λc)3/2+⋯.[8]We thus recover the expected nonanalyticity (ϕ=3/2) in the free energy density for the infinite-dimensional hardcore singularity (24).

Random k-QSAT

We now apply Theorem 1 to random k-QSAT. Random satisfiability has been a workhorse for the study of typical case complexity and heuristic algorithms. By tuning the density α=M/N of Erdős–Rényi-type random interaction graphs, a cornucopia of phases and phase transitions in the structure of the satisfying space has been discovered. In the quantum case, three phases for random k-QSAT on qubits and rank-1 projectors are believed to be (i) at low density, a product state satisfiable phase (PRODSAT); (ii) at intermediate densities for k sufficiently large, a satisfiable phase in which all ground states are entangled (ENTSAT); and (iii) at high density, an unsatisfiable (UNSAT) phase. The arguably most interesting of these phases, ENTSAT, has been shown to exist using the quantum Lovász local lemma (QLLL) (40) for k≥13. The application of Theorem 1 to the Erdős–Rényi (ER) ensemble is not straightforward, as the interaction graphs exhibit an unbounded degree distribution, so that a strict application of Shearer’s theorem provides no useful information. However, as explained in SI Appendix, Local Degree Fluctuations for Random k-QSAT, such local degree fluctuations do not appear to be the source of unsatisfiability in k-QSAT for qubits.

Neglecting this local rare-region effect, we calculate the self-consistent solutions to the disorder-averaged cavity equations, using standard methods (population dynamics) (35). For λ>λc, this numerical technique converges to a population of messages that represents the distribution of q and l in the infinite random graph and from which we can directly estimate the disorder-averaged free energy f and occupation number density 〈n〉=∂f/∂(log⁡λ). The latter is particularly useful, because as λ→λc, we expect 〈n〉 to exhibit a square-root singularity by universality; i.e., 〈n〉∼(λ−λc)1/2. Observing this singularity allows us to estimate λc accurately and confirms the validity of the numerical approach. By fitting these singularities, we extract a new and improved (lower) but nonrigorous threshold for the existence of an ENTSAT phase, k≥7 (Fig. 3).

Fig. 3.
Fig. 3.

Our current understanding of the phase diagram of the random k-QSAT. For small α, the instances are PRODSAT, with the transition out of PRODSAT approaching αP→1 from below as k grows (45). For large α, the instances are guaranteed to be UNSAT, with the best known upper bound (46) for the satisfiability transition at αSu=0.573⋅2k at k≥4. In between, there may be an ENTSAT phase if αS>αP. The best previous lower bound for the satisfiability transition, αSl, was given by the quantum Lovász local lemma (QLLL, up triangles) (40) and is roughly exponential at large k. This work obtains a better lower bound through the Shearer criterion (squares), lowering the threshold for the existence of an ENTSAT phase from k=13 to k=7.

Conclusion and Open Questions

By extending the classical Shearer theorem to quantum mechanical systems, we have provided a new statistical mechanical criterion for determining whether a local Hamiltonian is frustration-free. We have applied this criterion to a large class of regular and random Hamiltonians. These instances cover many of the geometries that have been studied in quantum complexity and as parent Hamiltonians for wavefunction-based many-body physics. In the context of random satisfiability problems, we have provided a set of new lower bounds on the existence of the ENTSAT phase. In particular, these bounds suggest that the ENTSAT phase is eminently more reachable in simulations than previously established.

Theorem 1 depends on the dimension p of the projectors Πi relative to the Hilbert space dimension and not the absolute local dimension q of the qudits. At small q (e.g., qubits), there are many Hamiltonians where R(ker H) is strictly larger than the bound of Theorem 1 (compare the discussion of random k-QSAT). Nonetheless, for large q we conjecture that Theorem 1 becomes tight. This is in sharp contrast to the classical case where the length-4 cycle (periodic chain) already provides a counterexample to the analogous statement (41). However, it is easy to show numerically that this counterexample breaks down for quantum projectors.

If, indeed, Theorem 1 is tight, there are several striking consequences. The geometrization theorem (37) states that R(ker H) is minimized by almost all choices of the Πi s. Coupled with tightness, the lattice gas partition function Z then provides a complete characterization of quantum satisfiability for almost all Hamiltonians with large enough qudits. It also directly lifts the universality of the lattice gas critical exponents to the counting of the ground state entropy of almost all quantum Hamiltonians in the frustration-free regime. In this sense, the conjecture amounts to an even larger scope of transferring insights from classical statistical mechanics into the quantum complexity domain.

Although Theorem 1 can guarantee the existence of zero energy states, it does not construct them. This is in contrast to classical SAT and commuting QSAT, where efficient constructive classical (under Lovász’s and Shearer’s assumptions) and quantum algorithms (under Lovász’s assumption) are known (41⇓⇓–44).

Analogously constructing the wavefunctions corresponding to the solutions of the noncommuting quantum problem would represent a milestone for quantum complexity theory.

SI Appendix

Proof of Theorem 1

Definition 1:

For a subspace X⊂V, let R(X)=dim(X)/dim(V). We say that X is mutually R independent of the subspaces Y1,…,Yn⊂V if ∀S⊂[n], R(X∩i∈SYi)=R(X)R(∩i∈SYi).

Definition 2:

The subspaces X1,…,Xn have R-dependency graph G=([n],E) if Xi is mutually R independent of {Xj}j∈[n]∖Γ+(i), where Γ(i)≡{j|(i,j)∈E}, Γ+(i)≡Γ(i)∪{i}.

An independent set (also known as a stable set) of a graph G is a set of nonadjacent vertices. Indep(G) is the family of all of the independent sets in G. The independent set polynomial isI(G,x)=∑S∈Indep(G)x|S|.We use the shorthand I(G)=I(G,−p) whenever p is clear from the context.

Lemma 1 (14).

Fix (G,p). The following properties are equivalent:

  • i) For every 0≤p′≤p, I(G,−p′)>0.

  • ii) For every induced subgraph F of G, I(F,−p)>0.

If this is the case, we say that (G,p) has Shearer’s property.

Theorem 2.

Let X1,…,Xn subspaces of V with dependency graph G, such that ∀i∈[n], R(Xi)≥1−p. If (G,p) has Shearer’s property, then R(∩i∈[n]Xi)≥I(G,p)>0.

For comparison, the following is the classical analog by Shearer (11).

Theorem 3.

Let B1,…,Bn be events with dependency graph G, such that ∀i∈[n] Pr(Bi)≥1−p. If (G,p) has Shearer’s property, then Pr(∩i∈[n]Bi)≥I(G,p)>0.

Proof of Theorem 2:

We first introduce some notations. For S⊂[n], we use the shorthand XS=∩i∈SXi, where XØ=V. The subgraph induced by U⊂V(G) is denoted G[U].

Lemma 2.

For any S⊂T⊂[n],R(XS)I(G[S])≤R(XT)I(G[T]).Lemma 2 completes the proof of Theorem 3, using S=Ø and T=[n]: R(X[n])I(G)≥R(XØ)I(G[Ø])=1.

We prove Lemma 2 by induction on the size of S and assume that T=S∪{i}. Let A=S∖Γ(i). By partitioning the independent sets in T to ones that contain i and the ones that do not, we haveI(G[T])=I(G[S])−pI(G[A]).[S1]We get a lower bound similar to the previous equation:R(XT)=R(XΓ(i)∩Xi∩XA)≥R(XΓ(i)∩XA)+R(Xi∩XA)−R(XA)=R(XS)+R(Xi)R(XA)−R(XA)≥R(XS)−pR(XA).[S2]

The first inequality follows from Fact 4, the second equality follows from the fact that Xi is R independent of {Xj}j∈A, and the last inequality follows from the assumption R(Xi)≥1−p.

Fact 4.

R(X∩Y∩Z)≥R(X∩Z)+R(Y∩Z)−R(Z).Fact 4 follows from the following property by assigning A=X∩Z,B=Y∩Z,dim(A∩B)=dim(A)+dim(B)−dim(A+B)for any two subspaces A,B⊂V, where A+B={a+b|a∈A,b∈B}.

To complete the proof of Lemma 2,R(XT)I(G[T])−R(XS)I(G[S])≥R(XS)−pR(XA)I(G[S])−pI(G[A])−R(XS)I(G[S])=p(I(G[A])R(XS)−R(XA)I(G[S]))I(G[S])(I(G[S])−pI(G[A]))=pI(G[A])I(G[S])−pI(G[A])(R(XS)I(G[S])−R(XI)I(G[A]))=pI(G[A])I(G[T])(R(XS)I(G[S])−R(XI)I(G[A]))≥0,where we used Eqs. S1 and S2 in the first inequality, Eq. S1 in the third equality, and the second definition of Shearer’s property (Lemma 1) and the induction hypothesis in the last inequality.

□

Proof of Theorem 1:

This is an application of Theorem 2. For a QSAT instance Π1,…,Πm, with interaction graph F we define Xi=ker(Πi), and G has m vertices and an edge between i and j if Πi and Πj act on a shared qudit. G is indeed an R-dependency graph for X1,…,Xm: This follows from the property dim(A⊗B)=dim(A)dim(B) (40).

To complete the proof we observe that I(G,−p)=Z(F,−p) [in graph theoretic terminology, this is equivalent to the statement that for any hypergraph F, IL(F)(x)=MF(x), where L(F) is the line graph of F and MF(x) is the matching polynomial of F (47)].

□

The Cavity Derivations

The cavity method is a collection of techniques for calculating the properties of statistical mechanical models defined on locally tree-like lattices, i.e., on graphs without short loops. Here, we apply it to evaluating the free energy F=log Z of the hardcore gas of particles living on the hyperedges i of the interaction graph G, as defined by Eq. 2.

We introduce a pair of cavity distributions (“messages” or “beliefs”), pi→a(ni) and pa→i(ni), for each link between a hyperedge i and node a. These represent the marginal distribution of the occupation variable ni in the absence of its link to site a and in the absence of its link to sites other than a, respectively. On a graph with no loops, these distributions are simply the normalized partial sums of Z when evaluated from the leaves inward toward the link between a and i.

Assuming that the cavity distributions coming into a given node or edge are independent (as they are on graphs with no loops), the 2Mk cavity messages satisfy the local relations,pa→i′(ni)=∑{nj},jϵ∂a\i[I(∑kϵ∂ank≤1)]λni∏jϵ∂a\ipj→a(nj)pi→a′(ni)=λni∏bϵ∂i\a(pb→i(ni)λni),where p′ denotes an unnormalized distribution. Properly normalized, each cavity distribution can be parameterized by one real number, which we take to be the probability of occupation (recall that ni∈{0,1}),qa→i=pa→i(1)li→a=pi→a(1).Using this parameterization leads directly to the BP equations in the main text.

On graphs without loops, the BP equations admit a single global solution for the cavity messages qa→i and li→a, which corresponds to an exact evaluation of Z. From this solution, one obtains the total free energy Eq. 6 as a sum of local contributions due to the free energy of each hyperedge Fi, site Fa, and link Fai. These free energies are functions of the messages coming into the relevant piece of the interaction graph. Explicitly,Fa=log[∑{nj},jϵ∂a∏jpj→a(nj)]=log[∏jϵ∂a(1−lj→a)+∑jϵ∂alj→a∏kϵ∂a\j(1−lk→a)]Fi=log[∑niλni∏bϵ∂ipb→i(ni)λni]=log[∏bϵ∂i(1−qb→i)+λ∏bϵ∂iqb→iλ]Fai=log[∑ni1λnipi→a(ni)pa→i(ni)]=log[(1−li→a)(1−qa→i)+li→aqa→iλ].This evaluation of the free energy is exact for finite trees. For infinite graphs with loops of divergent girth, it often produces asymptotically exact results.

Thus, the main task in evaluating the free energy (and corresponding Z) for a given infinite graph is to obtain solutions of the infinite set of BP equations for the cavity messages.

Solving the Cavity Equations: Regular Graphs.

For infinite t-regular k-local trees/regular random graphs, the BP equations admit a solution with uniform messages qa→i=q and li→a=l. After a small amount of algebra, the self-consistent equations can be reduced to finding the roots ofxk−xk−1−λ(t−1)=0,[S3]wherex=1+(t−1)(1l−1−1)=λ(q−1−1).The discriminant of Eq. S3 is [with z=λ(t−1)]Embedded Image

where in the second step we observed that only three terms in the determinant are nonzero. The discriminant has a simple zero at zc=−((k−1)k−1/kk), in agreement with Eq. 7. The zeros of the discriminant indicate values of z where two roots of the BP equations merge so that there is a nonanalyticity in the resulting free energy.

At zc, the root of interest has multiplicity 2 and can thus be easily found by looking for a root shared with the derivative of Eq. S3. Thus,xc=k−1k,which can be verified by direct evaluation. Geometrically, we expect x to evolve as a square root of deviations in z from criticality. To leading nonvanishing order in δz=z−zc and δx=x−xc, Eq. S3 can be solved,δz=12(δx)2[(k−1k)k−3(k−1)].[S4]From the critical values for zc and xc, and the behavior near criticality Eq. S4, it is a straightforward if algebraically tedious process to evaluate the free energy density given in Eq. 8.

Solving the Cavity Equations: Random Graphs.

In infinite Erdős–Rényi random graphs, the local geometry fluctuates from site to site and, accordingly, the local BP equations vary. We do not expect to find a solution with uniform messages; rather, the distribution of cavity messages Pq[⋅] and Pl[⋅] should be stable under the iteration of the BP equations. This leads to self-consistent equations for the distributions Pq[⋅] and Pl[⋅], which we solve by numerical population dynamics.

Local Degree Fluctuations for Random k-QSAT

In an Erdős–Rényi random graph, the degree z of each site follows a Poisson distribution; i.e.,Pr(degree=z)=e−kα(kα)zz!.This means that there is a small but finite density of large degree sites at any α. These large degree sites pose a problem for the Shearer bound: The partition function of the finite “star” of hyperedges surrounding a site of degree z is Z=1+zλ. This has its first negative fugacity zero at λc=−1/z. Given the unbounded fluctuations in z, monotonicity implies that λc=0 for the infinite graph.

However, we believe that it is not these fluctuations that in fact lead to the instance becoming UNSAT for the case of qubits. This can already be seen classically: One can explicitly verify that a star that by Shearer should be UNSAT will, in fact, always be SAT; this happens because the constraints imposed by different projectors on the central spin can never be disjoint as the worst-case Shearer bounds assume.

This carries over to the quantum case. Indeed, here it has been shown (46) that stars not only are satisfiable, but also have entropic ground spaces dimker H=2(2k−1−1)z(z/(2k−2)+1). This is backed up by the rigorous work of ref. 40, which found a lower bound on the satisfiability threshold by gluing together product states on high-degree regions of the Erdős–Rényi graph with states guaranteed by the QLLL on the low-degree regions.

Our numerics, in turn, also implicitly neglect the large degree fluctuations because the density of sites with z>2k is very small (10−14 at k=5 to 10−370 at k=9) for α≈αc of the observed bulk transition. By contrast, for k<5, the large degree fluctuations are not as rare and thus the population dynamics fail to converge.

For k≥5, the population dynamics converge up to some λc(α) and, moreover, we clearly observe the square-root singularity in 〈n〉 referenced to this λc. This suggests that we are detecting a bulk transition in the lattice gas, from which we determine αc by solving λc(α)=1/2k (Fig. 3).

Improved Bounds Using the Critical Exponents

We can rewrite R(kerH)≥exp(nf)=peffn, where peff=exp(f). In the large n limit, there exists a (nonanalytic) power series expansion of f(λ) near λc. We learn a few interesting facts from the existence of this power series expansion (and, in particular, that f does not diverge at the critical point). First, peff≠0 at the critical point. Second, f is known to have nonanalytic terms that depend only on the lattice dimension. For example, for all 1D lattices (chains, ladders, etc.), the expansion close to the transition point is f(λ)=a0+a1/2(λ−λc)1/2+O(λ−λc), and for 2D lattices, f(λ)=b0+b5/6(λ−λc)5/6+O(λ−λc).

To conclude, near the critical point, the leading power of the nonanalytic part of f depends only on the dimension of the lattice involved and not on the specific details of the lattice. As a result, the dimension of the satisfying subspace grows faster than one would expect for 1D and 2D lattices.

Acknowledgments

We thank Dorit Aharonov, David Gosset, Antonello Scardicchio, Shivaji Sondhi, Mario Szegedy, and Umesh Vazirani for valuable discussions. This work was supported by the ARO Grant W922NF-09-1-0440, NSF Grants CCF-0905626 and PHY-1520535, the DFG Grant SFB 1143, ERC Grant 030-8301, and a Sloan Research Fellowship.

Footnotes

  • ↵1To whom correspondence should be addressed. Email: siddhardh{at}gmail.com.

  • Author contributions: O.S., S.C.M., C.R.L., and R.M. designed research, performed research, contributed new reagents/analytic tools, analyzed data, and wrote the paper.

  • The authors declare no conflict of interest.

  • This article is a PNAS Direct Submission.

  • This article contains supporting information online at www.pnas.org/lookup/suppl/doi:10.1073/pnas.1519833113/-/DCSupplemental.

View Abstract
Back to top
Article Alerts
Email Article
Citation Tools
Request Permissions
When a local Hamiltonian must be frustration-free
Or Sattath, Siddhardh C. Morampudi, Chris R. Laumann, Roderich Moessner
Proceedings of the National Academy of Sciences Jun 2016, 113 (23) 6433-6437; DOI: 10.1073/pnas.1519833113
Digg logo Reddit logo Twitter logo Facebook logo Google logo Mendeley logo
Proceedings of the National Academy of Sciences: 113 (23)
Table of Contents

Submit

Article Classifications

Jump to section

You May Also be Interested in

Large piece of gold
News Feature: Tracing gold's cosmic origins
Astronomers thought they’d finally figured out where gold and other heavy elements in the universe came from. In light of recent results, they’re not so sure.
Image credit: Science Source/Tom McHugh.

Similar Articles