## Abstract

It is believed that not all quantum systems can be simulated efficiently using classical computational resources. This notion is supported by the fact that it is not known how to express the partition function in a sign-free manner in quantum Monte Carlo (QMC) simulations for a large number of important problems. The answer to the question—whether there is a fundamental obstruction to such a sign-free representation in generic quantum systems—remains unclear. Focusing on systems with bosonic degrees of freedom, we show that quantized gravitational responses appear as obstructions to local sign-free QMC. In condensed matter physics settings, these responses, such as thermal Hall conductance, are associated with fractional quantum Hall effects. We show that similar arguments also hold in the case of spontaneously broken time-reversal (TR) symmetry such as in the chiral phase of a perturbed quantum Kagome antiferromagnet. The connection between quantized gravitational responses and the sign problem is also manifested in certain vertex models, where TR symmetry is preserved.

## INTRODUCTION

There is a common understanding related to computational complexity classes, that quantum mechanics is vastly superior to classical mechanics. Indeed, all problems that can be solved efficiently on a classical computer can be solved just as efficiently on a quantum computer, while the opposite is believed not to hold. From a condensed matter theory perspective, natural computational problems arise in the studies of models of interacting quantum many-body systems. Notably, some of these systems with purely bosonic degrees of freedom can be used as hardware for universal quantum computations (*1*, *2*); therefore, simulating them classically in polynomial time is likely to be impossible. Despite decades of efforts, efficient classical simulators are not known for many physically relevant bosonic models. Among those are the antiferromagnetic Heisenberg model on a Kagome lattice and most, but not all (*3*, *4*), bosonic fractional quantum Hall effects (FQHEs). This state of affairs might be due to a lack of one’s analytical ingenuity. However, one cannot exclude the possibility that some inherent physical property creates an obstruction to efficient classical simulations of many-body quantum systems.

Establishing an obstruction to a classical simulation is a rather ill-defined task. A related, yet more concrete, goal is to find an obstruction to an efficient quantum Monte Carlo (QMC), which is one of the chief numerical workhorses in the field. In the QMC, one considers the Euclidean (or thermal) partition function of a quantum system in *d* dimensions as a statistical mechanical (SM) model in *d* + 1 dimensions with the extra dimension being imaginary time (*5*). If this can be carried out such that the resulting SM model has Boltzmann weights that are local and non-negative, then efficient QMC sampling is possible (*6*).

Although QMC offers essentially numerically exact solutions for a wide variety of many-body quantum problems, in the case of aforementioned systems, the Boltzmann weights seem to be unavoidably negative or complex. Notably, signs and phases in the Euclidean partition function can sometimes be a matter of representation. Having a “sign problem” thus means that no local transformation that removes the signs and phases is possible. Notably, the definition of a sign problem must involve the notion of locality [see also the study of Hastings (*7*)]. By performing a nonlocal transformation on the physical degrees of freedom, one can always diagonalize the Hamiltonian and obtain a classical partition function. However, such a transformation requires computational resources that scale exponentially with the system size. Therefore, for a meaningful definition of the sign problem, one has to add an additional requirement, that is, that the degrees of freedom σ, that enter the Boltzmann weights must be expressed as local combinations of the physical ones or, more precisely, that σ are given by finite depth local quantum circuits acting on the physical degrees of freedom. For the sake of clarity in this work, we do not address the possibility of nonlocal approaches to QMC, such as determinant QMC or cluster algorithms (*8*–*10*).

In a recent study (*7*), Hastings showed that for Hamiltonians consisting of commuting projectors, in the double semion phase, the partition function has a sign problem. To the best of our knowledge, this was the first time that the existence of a sign problem was established rigorously rather than by an accumulation of failed attempts to solve it. Although not proven, it is likely that the sign problem in this model is a property of the double semion phase (or, more precisely, its *S*-matrix), which holds regardless of the requirement of having commuting projectors. Another interesting insight comes from a recent work by Iazzi *et al*. (*11*), who argued that the sign problem in auxiliary-field determinant QMC arises from Aharonov-Bohm–like phases and thus has a topological origin. Here, building on some of these insights, we show that in bosonic systems with quantized gravitational responses, the sign problem cannot be cured by local transformations of degrees of freedom. We note that we study bosonic systems here, as opposed to fermions, to highlight the fact that the sign problem, which we discuss here, is not related to the trivial fermionic exchange.

Considering the FQHE, a hint to which of its properties is in tension with a sign-free QMC comes from recent studies of bosonic symmetry-protected topological states (SPTs) (*3*, *4*, *12*, *13*). The latter found that certain SPTs related to bilayer bosonic integer quantum Hall effects (characterized by a nonzero Hall conductance) allow one for a sign-free QMC implemented via a local change of basis (*12*). Because both the FQHE and these SPTs show quantized bulk electromagnetic responses (that is, the Hall conductance) (*14*), it is difficult to draw an electromagnetic distinction between them. However, a distinction between these phases does exist and is highlighted by the responses to temperature gradients or via quantized gravitational responses (*14*). Namely, unlike these SPTs, most FQHEs show a nonzero quantized thermal Hall conductance.

Another canonical example of a sign problem arises in the studies of quantum Kagome lattice antiferromagnets (K-AFMs). Some of these models have close connections to the physics of FQHE. For example, it was recently found that the ground state of the perturbed K-AFM model (*15*, *16*) lies in proximity of the Kalmeyer-Laughlin state (*17*, *18*), which is known to have nontrivial gravitational responses.

Turning to a different set of models (critical vertex models representing unitary minimal conformal field theories), gravitational responses yet again appear to be indicative of a sign problem. Although unitary minimal models have a sign-free formulation, no such formulations are known for their vertex counterparts with larger operator content (*19*). The low-energy theories of these vertex models contain a term that attaches electric charge to the curvature (*20*, *21*), reminiscent of the Wen-Zee term in the FQHE (*22*), whose coefficient is proportional to the thermal Hall conductance.

## RESULTS

Here, we expose a direct link between gravitational responses and the sign problem in QMC. In particular, we show that no local sign-free QMC formulation is possible for phases that have a nonvanishing quantized thermal Hall conductance and a gapped bulk. These results suggest a link between quantum gravitational effects and quantum complexity theory.

Before delving into detailed proofs, let us sketch the main idea behind them, which relies on anomalies. Anomalies are a peculiar effect in which a symmetry that is present at a classical field theory level becomes violated at the quantum field theory level. Both the Hall conductance and the thermal Hall conductance could be understood in terms of anomalies—a charge and gravitational anomaly, respectively (*14*). In general, when coupling anomalous theories to static gauge fields, one finds that fluxes of the gauge field induce quantized complex phase factors in the partition function (*14*). In many cases, these complex phases are a direct reflection of the aforementioned violation of the symmetry. In our context, it is useful to view these complex phases as Berry phases occurring at the level of the partition function rather than at the level of wave functions. Similarly, the gradual introduction of static gauge fluxes should be viewed as a certain periodic cycle in a parameter space.

It may seem then that any anomaly is in conflict with a sign-free partition function where complex phases are, by definition, disallowed. However, this is evidently not the case because there are various counterexamples (*3*, *4*, *12*, *13*). The subtlety is that for an anomaly in symmetry, these complex phases may not come from the pristine theory but rather from the addition of the static gauge flux itself. Here, gravitational anomalies stand out: The analogs of gauge fluxes in gravity are torsion and curvature (*23*), and these can always be introduced to a classical partition function, via lattice defects, without generating signs or complex phases (see Fig. 1). Thus, the anomalous complex phases in the partition function induced by a flux insertion are, in the case of gravitational anomalies, in sharp contradiction with a sign-free partition function.

Let us now make our setting more precise. In general, an Euclidean partition function of a *d*-dimensional quantum problem can be written as a *d* + 1–dimensional partition function of a corresponding classical problem on a periodic *d* + 1–dimensional lattice with degrees of freedom σ attached to the sites of the lattice. We will call a partition function classical if it is given by a product of Boltzmann weights, being real non-negative functions of σ. These weights must be local and are functions of σ, which involve a finite number of nearby sites. Further, it is useful to assume that a discrete translational invariance holds with some finite, lattice vector.

We start with an observation that a classical partition function on the plane can be transported to the torus, or to a twisted torus, because, for both, the lattice appears locally everywhere as a plane (see Fig. 1). Further, the partition function can be used to construct a non-negative transfer operator, T, along the periodic (imaginary time) direction such that the partition function is given by T raised to a suitable power. We shall always pick the transfer-matrix direction along the imaginary time axis.

### Fractional quantum Hall effect

Let us assume that a classical 2 + 1–dimensional Euclidean partition function exists for the bosonic FQHE (for example, at ν = 1/2) on a plane or a torus. If this is the case, the partition function can be transported to the following geometry: a time-space three-dimensional (3D) bulk on a lattice, open boundary conditions in the *y* direction, periodic boundary conditions with period *L* and β in the *x* direction, and the imaginary time in the *z* direction (we assume a large β, that is, larger than any other parameter). We further introduce a twist in the boundary conditions such that (*x* + φ*L*, *y*, *z*) ≡ (*x*, *y*, *z* + β). Following Nakai *et al*. (*14*), the resulting partition function on the left/right edge transforms under an insertion of a modular/torsional transformation (φ → φ + α) in the *xz* plane as *Z*_{l,r}[φ + α] = *e*^{±iπα/12}*Z*_{l,r}[φ]. The total partition function being the product of the contributions from the left and right edges has canceling phase factors. The equation above is understood as a global gravitational anomaly occurring within each edge (*14*, *24*). This is analogous to the case of the *U*(1) charge anomaly (*14*, *25*), where the charge, despite being conserved on each edge separately, is redistributed between two edges after a flux insertion.

The tension between a sign-free partition function and the above phase factor is sharpened by the following observations. First, we recall that if the partition function can be made positive for φ = 0 (regular torus), then it can also be made positive for φ ≠ 0 (twisted torus), and in particular, the transfer operator remains real and non-negative everywhere (see Fig. 1). This implies that one cannot have a sign-free partition function describing a single edge. Still, in the full partition function, this tension is obscured by the canceling phase factors arising from both edges. However, as shown below, in the presence of a gapped bulk, we can unambiguously separate the low-energy contributions from the left/right edges.

Let us outline two ways of formally achieving this left/right separation. The first, which makes a direct connection with the gravitational anomaly, requires augmenting the twist such that it acts only on a single edge. Here, one has to give special attention to the unwinding of the twist in the bulk and make sure that it does not induce any opposite quantized phase factors, as turns out to be the case. For details, the reader is referred to Materials and Methods. An alternative way is to use the fact that these gravitational anomalies are always associated with chiral boundary excitations (*24*). It is thus sufficient to prove that a sign-free formulation is in conflict with having only chiral excitations on a particular edge. Because this proof is particularly simple, we include it here.

Consider a transfer operator T for an FQHE Hamiltonian on a lattice and assume that T is real and non-negative. Note also that the lattice translation operator *e*^{iaP} (where *P* is the lattice momentum operator) is always element-wise non-negative and particularly invariant under complex conjugation. Because inserting *e*^{iaP} into the partition function generates torsion in the geometry, its non-negativity is a reflection of the aforementioned observation that torsional defects do not induce signs in the partition function. In addition, note that if a sublattice structure is present, then we interpret *a* and *P* accordingly. We proceed by establishing the conflict between the realness of T and *e*^{iaP} and having chiral edge states.

Because T commutes with *e*^{iaP}, we can classify eigenstates of the transfer operator using momentum eigenvalues. Because both matrices are real, the eigenvalues, momenta, and eigenstates must come in complex-conjugate pairs , . Notably, only when *k*_{n} = 0, is it possible for the state to be its own complex conjugate. The non-negativity of T, together with the known fact that FQHE ground states on a cylinder are unique (nondegenerate), implies that the largest eigenvalue λ_{0} is positive and therefore gives real minimum ground-state energy ε_{0}. The non-negativity of the ground state wave functions (via Perron-Frobenius) and that of the operator *e*^{iaP} further implies that .

Next, we discuss excited states and their identification in the eigenvalues of the transfer operator. On general grounds, one expects the highest weight states λ_{n} of T to be in one-to-one correspondence with the low-energy spectrum of the Hamiltonian (*26*, *27*) based on ε_{n} = −ε^{−1}Re[ln(λ_{n})], where ε denotes a lattice spacing in the time direction. Because we are mainly interested in the simulation of quantum Hamiltonians, transfer matrices would appear as *e*^{−εH} or, more generally, , where *H* = ∑_{i}*H*_{i}, and ε is small enough to ensure that the low-energy physics is faithfully reproduced. More formally, we thus limit ourselves to the possibility of solving a sign problem by performing a local similarity transformation *S* so that the transfer matrix has the form . It is clear in this representation that the low-energy spectra of *H* and of T coincide up to terms of the order *O*(ε^{2}).

The chiral nature of bosonic FQHE, such as ν = 1/2, implies the existence of two lowest momentum-carrying excitations (*28*) residing on different edges, which we denote by |ε_{q}, *e*^{iqa}, *l*〉, |ε_{n}, *e*^{−iqa}, *r*〉. These are characterized by the eigenvalues of *e*^{iaP}, that is, *e*^{+iqa} on, say, the left edge and *e*^{−iqa} on the right edge, with *q* = 2π/*L*, and corresponding energies ε_{± q} = ε_{0} + *O*(1/*L*). Let us be precise on how these edge labels are assigned. Given a collective excitation characterized by an eigenvector |*a*〉 of the transfer matrix, we compare the density matrix associated with the excitation |*a*〉 on the left or right half of the cylinder ρ_{l}*o*_{l/r}[|*a*〉] with the reduced density matrix of the ground state ρ_{l/r}[|*gs*〉] on the same regions. If, for example, ρ_{l}[|*a*〉] = ρ_{l}[|*gs*〉] (up to factors , where *l*_{B} is the magnetic length), we say that the excitation |*a*〉 is localized on the right edge. Notably, ρ_{l/r}[|*a*〉*] = ρ_{l/r}[|*a*〉]*, and because |*gs*〉 = |*gs*〉*, we find that ρ_{l/r}[|*gs*〉] is real. We find that complex conjugation of the eigenstate of the low-energy collective excitation associated with one edge cannot be transformed into an excitation on the opposite edge.

Finally, we note that given an excitation |ε_{q}, *e*^{iqa}, *l*〉, an orthogonal state with a complex conjugate momentum *e*^{−iqa} must appear on the same edge. However, given the chiral nature of edge excitations, we know that there is no such state in the spectrum, and we thus arrived at the desired contradiction, which completes our proof.

In the above proof, we showed that element-wise non-negative transfer operator and translation operator forbid the existence of a spatially isolated chiral channel. Because a sign-free local formulation of the partition function implies that these two operators are non-negative and because gravitational anomalies imply the occurrence of such a chiral channel on an edge, a clear contradiction is established between gravitational anomalies and a sign-free local formulation. Notably, no particular property of the FQHE has been used apart from the presence of chiral edge states (or, equivalently, a gravitational anomaly) and a bulk gap. Thus, this proof generalizes to all FQHEs, which do not have counterpropagating modes on their edges.

### Kagome antiferromagnet

Having considered FQHE states, which are induced by an external magnetic field, we turn to discuss cases where FQHE-like states can appear as a result of spontaneous symmetry breaking. We will discuss a possibility of such a situation in the case of frustrated Heisenberg models, such as the Kagome quantum antiferromagnets. Whereas the presence of time-reversal symmetry may imply the lack of a sign problem for fermions (*29*, *30*), the latter bosonic models are known for having one. Frustration may give rise to exotic spin-liquid states at low temperatures including chiral spin liquids (*15*, *16*). One of the candidates for these states is described by the Kalmeyer-Laughlin wave function (*18*). The latter is in the same universality class as the bosonic ν = 1/2 FQHE. There is numerical evidence that a perturbed Kagome quantum antiferromagnet (K-AFM′) in the presence of next-nearest-neighbor and next-next-nearest-neighbor Ising interactions (*17*) is described by the Kalmeyer-Laughlin phase.

Let us discuss a spontaneous TR symmetry-breaking scenario on the example of the K-AFM′ model. A standard prescription for observing a broken symmetry is to couple the system to an infinitesimal ordering field. However, we want to avoid adding such operators here because they can introduce sign problems. Therefore, we use Anderson’s tower of states picture as an alternative indicator of symmetry breaking. Now, because the model cannot, strictly speaking, break the time-reversal symmetry, its low-lying spectrum cannot be chiral. Each of the two symmetry-broken lowest-energy states (|*gs*〉 and ) supports either chiral or antichiral excitations on a particular edge. Consequently, an excited state produced by complex conjugating a chiral edge excitation (belonging to one of the symmetry-broken states) does appear in the spectrum on the same edge (cf. with the FQHE case) but must be associated with the other symmetry-broken state. Thus, the argument presented above for FQHE does not straightforwardly apply.

Let us first consider the case where |*gs*〉 is proportional to on the computational basis. We claim that this cannot occur if T is non-negative, regardless of any chiral or topological physics. To give an intuitive example, consider a simple 1D Ising ferromagnet. On the *S*_{z} basis, T is non-negative. However, the two ground states are not connected by complex conjugation. On the other hand, on the *S*_{y} basis, the states are connected by *K* but at the price of having negative entries in T. We defer the proof for a more general case to Materials and Methods.

In the complementary case of |*gs*〉 being orthogonal to , these two states and the edge excitations on top of them will be distinct in the bulk. Consequently, complex conjugating a chiral excitation above |*gs*〉 will lead to antichiral excitations different from those above and the previous arguments for the FQHE hold.

### Vertex models

Finally, we address the sign problem appearing in certain vertex models. Let us consider the six-vertex model formulation of 2 + 0*D* minimal conformal field theories (*31*). The six-vertex model can be thought of as a dense loop model, for example, by splitting every vertex into two loop configurations. It is known that for positive integer loop fugacities *n*, one can write a local partition function with positive Boltzmann weights (*31*). However, in the general case, one has to resort to complex Boltzmann weights.

The Ising critical point can be described by an SM model; therefore, it does not have a sign problem. Notwithstanding, to the best of our knowledge, no local sign-free reformulation is known for its loop model counterpart, for which . To clarify this, we note that although the equality between the Ising model and the vertex model holds at the level of partition functions, their operator content is different, and the equality of their partition functions is a result of miraculous cancellation of a large number of contributions in the vertex model case [see the study of Foda and Nienhuis (*19*)].

Similarly, the field theories governing the two models are distinct. The Ising model is described by a scalar field *m*, whereas the vertex model is described by a compact boson φ coupled to Gaussian curvature (*20*). Thus, a curvature defect, or a disclination on a lattice (*21*), binds an electric charge in the vertex model, but no similar effect is expected for the Ising model. Hence, in this very different setting, a sign problem is accompanied by a gravitational response. It is worth mentioning that (i) local operators in the vertex model are vortices in φ (the magnetic charges)—therefore, disclinations, by binding electric charges, couple to them via Aharonov-Bohm fluxes—and (ii) disclinations can be added without introducing signs into partition functions (see Fig. 1).

## DISCUSSION

In summary, we suggested that nontrivial gravitational/geometrical responses can be identified with obstructions to sign-free local QMC simulations. First, we pointed out that geometrical perturbations are unique in this context because they can always be added to a classical partition function without introducing complex phases or signs. Then, we established that having a global gravitational anomaly on an edge of a gapped system, as is the case for most fractional quantum Hall phases, implies a sign problem. The same argument extends to frustrated quantum magnets that support a chiral spin liquid phase, although here, some additional microscopic assumptions are currently required. Last, we pointed out that sign problems in critical 2D oriented loop models are also associated with a coupling of charge to curvature. Curiously, tensor network–based numerical approaches, for which the sign problem is irrelevant by construction, also struggle with simulating FQHE states (in the thermodynamic limit). This raises an intriguing connection between gravity and computational complexity via sign problems (*6*).

## MATERIALS AND METHODS

### Exposing the gravitational anomaly using one-sided twists

Here, we show how to introduce a modular twist on a single fractional quantum Hall edge in a way that does not induce any complex phase factors when applied to a sign-free partition function. In the presence of a perturbative gravitational anomaly, we show that such a twist must nonetheless induce phase factors in the partition function.

Let us begin pedagogically and consider how the gravitational anomaly arises in its simplest setting—that of the fermionic integer QHE. Here, we consider a single-particle lattice Hamiltonian such that μ is within the band gap and all bands below the gap have a Chern number equal to 1. When placed on a cylinder, the system will show chiral and antichiral edge states on the opposite edges. Focusing on, say, the right edge, and taking a very long cylinder, one can distinguish the states associated with the left and right edges. Let us denote by |*k*, *r*〉 the first-quantized wave functions of the states on the right edge and introduce a cutoff operator(1)where *k*_{μ} is the momentum corresponding to the state with energy μ, and is given by for |*x*| < Λ, where , and zero for larger |*x*|. Next, we write a projected single-particle Hamiltonian on the right edge as(2)

Similarly, we introduce a projected momentum operator(3)

The operator is defined by *ia*^{−1}log (*T*), where *T* is the translation operator along one unit cell and *a* is the lattice spacing. Specifically, we consider a local basis |*x*, *α*〉, where *x* denotes a site and α denotes unit-cell index, and construct as(4)where *k* is chosen to be in the first Brillouin zone, and |*k*, α〉 ∝ ∑_{x}*e*^{ikx}|*x*, α〉.

Using the projected single-particle Hamiltonian and momentum operator, we construct the corresponding many-body Hamiltonian and the many-body momentum operator . Now, let us consider the many-body partition function with a twist in the boundary conditions(5)where realizes the twist.

In the limit of a very large β, the partition function will be dominated by the ground-state contribution(6)

Taking *k*_{μ} = 0 for simplicity and assuming a spectrum , we find by summing over occupied states that(7)where *k*_{n} = 2π*n*/*L*. Now, we can evaluate *P*_{0} using the Euler-Maclaurin formula to write the sum over momentum as an integral, which yields(8)

We thus find that *P*_{0} contains a diverging energy density, which can be understood as the energy density of an infinite edge plus a finite-size Casimir-like correction. The contribution from the gravitational anomaly is contained in the second term. To filter out this contribution, we can compare two systems with sizes *L* and 2*L*, which yields(9)so that(10)

Now, we consider the above procedure for an operator in the representation where all the matrix elements are real, so that its eigenvalue subspaces can all be chosen to have real eigenvectors. As a result, is a real operator. Notice further that is purely imaginary because(11)and for every *k* in the summand, there is a −*k*. Consequently, is purely imaginary in the local basis (or, equivalently, is real and positive). Equation 10 thus consists of only real numbers on the left-hand side, which is in contradiction with the right-hand side.

Next, let us turn to the interacting case. To this end, we need to express the effective momentum operator on the right edge, *P*_{r}, without appealing to a single-particle basis. We suggest the following obvious solution: We consider a cylinder of large circumference *L* such that a rotation in a finite angle φ_{0} is equivalent to a translation by many (*L*φ/2π) unit cells. We then define to be the operator that rotates the system by φ_{0} up to, say, 10 correlation lengths away from the right edge and then gradually rotates until, at a distance of, say, 20 correlation lengths away from the right edge, it stops rotating the remainder of the cylinder. We refer to this as twisted rotation. Notably, the twisted-rotation operator thus defined is strictly positive.

The quantity of interest is then , which should contain the same *e*^{iφ/12} Casimir term as before. Because it rotates the right edge and not the left edge, we expect the edge contribution to yield the same contribution as before. One may worry though that an extra bulk contribution would appear, which would cancel the right edge’s contribution. This, however, should not be the case because Casimir effects are 1/*L* effects, and these should not occur in a gapped system such as the bulk of an FQHE. This can be verified explicitly using a continuum version of for the integer quantum Hall effect on a cylinder in the Landau gauge. It is then easy to show that , defined using twisted rotation, has essentially the same algebraic properties as the previous one-sided rotation, defined using spectral projections.

### “Complex conjugation symmetry” in statistical mechanics

A transfer matrix T of any SM model, being non-negative, has a global anti-unitary symmetry, which is defined by a complex conjugation operator *K*. It is a natural question to ask whether this symmetry can be broken spontaneously (see definitions below). We conjecture that this is impossible in any physical setting. Specifically, we prove this conjecture in two relevant cases: (i) the model is inversion symmetric along some direction such that T becomes a symmetric matrix, or (ii) there is a degeneracy of the eigenvalues of the transfer matrix for broken symmetry ground states. We also discuss a complementary scenario where neither (i) nor (ii) holds.

Let us start by making a precise definition of what we mean by saying that complex conjugation symmetry is spontaneously broken: (i) The transfer matrices T(*L*), where *L* is the system size, have two dominant eigenvalues λ, λ′, which are *O*(*e*^{−L}) apart in the logarithms of their magnitudes, and are separated from all other states by a distance δ(*L*), which scales as δ(*L*) ~ *L*^{−a}, where *a* ≥ 0; . (ii) Any linear superposition of |λ〉, |λ′〉, which is invariant under *K* in the computational basis σ, is a Schrodinger cat state (cat state). By this, we mean that it is an equal-weight superposition of two distinct many-body states (physical states) or, more precisely, states that have nonzero matrix elements only for operators acting of *O*(*N*) sites for a system of size *N*. (iii) The physical states |ψ_{1}〉, |ψ_{2}〉 map to each other under the action of *K*. (iv) The physical states are distinguishable by having finite, and different, expectation values for some local Hermitian operator *O*_{y}, which obeys *KO*_{y}*K* = −*O*_{y} in the thermodynamic limit.

First, we consider the simplest scenario where the absolute values of λ, λ′ are equal (|λ| = |λ′|). Then, by the Perron-Frobenius theorem, this implies that |λ〉 and |λ′〉 may be chosen positive on the computational basis |σ〉 on which T is non-negative. We next show that having two non-negative ground states contradicts the above symmetry-breaking assumptions. By these assumptions, we can write(12)where *a* and *b* are two complex numbers equal in magnitude and φ is an arbitrary phase. Note that both physical states and the λ states are assumed to be normalized. Now, using (ii), we have(13)(14)and from (iii) and (iv), we find that the right-hand side is nonzero. Next, let us split the computational basis σ = (η, μ) into the set of degrees of freedom on which *O*_{y} acts as an identity (η) and the set μ on which it acts nontrivially. We then find that(15)where we used the non-negativity of |λ〉, |λ′〉 on the σ basis in the last line. Let us denote the operator appearing on the last line as . Notably, it is invariant under complex conjugation. Using assumptions (ii) and (iii) and the invariance under complex conjugation, we find that(16)

Grouping the last three equations together, we find that(17)

Thus, the *K* symmetry-breaking assumptions are incompatible with having two non-negative ground states.

Next, we consider the case when |λ′| < |λ|, where |λ〉 is still non-negative, but now, |λ′〉 is only guaranteed to be real. Because |λ′| and |λ| become exponentially close, it is natural to expect some notion of continuity in the sense that almost degenerate dominant eigenvectors should also be almost non-negative. If so, the previous proof can be repeated.

Let us establish this almost non-negative behavior for the case where T is symmetric and, therefore, also Hermitian. To this end, split the real state |λ′〉 into two non-negative states with distinct supports—those with non-negative coefficients |+〉 and those with negative coefficients |−〉 such that |λ′〉 = |+〉 − |−〉. Note that the states |+〉, |−〉 are not yet assumed to be normalized. Consider next the state ||λ′|〉 = |+〉 + |−〉 and expand it in the eigenvectors of T(18)

Because of the non-negative nature of T, ||T||λ′|〉|| ≥ ||T|λ′〉||. This, the exponential degeneracy of |λ| and |λ|′, and the δ(*L*) gap to other states imply that is exponentially small in system size. We thus find that(19)(20)

Because |λ′〉 is normalized, at least one of these vectors has a norm order of 1, and let us assume without losing generality that this is the vector |+〉. Now, depending on the remaining vector, there are two possible scenarios: (i) 〈−|−〉 > *e*^{−L} and (ii) 〈−|−〉 < *e*^{−L}. In case (i), the joint weights are still exponentially larger than the weights of remaining terms. Consequently, |−〉 can be chosen as the second basis vector for the ground-state subspace of T. Because |−〉 and |+〉 are, by definition, non-negative and orthogonal, one can repeat the previous argument about the expectation value of with these two states.

In case (ii), we use the orthogonality of |λ〉 and |λ′〉 to obtain 〈λ|+〉 = 〈λ|−〉, and using , we finally obtain 〈λ|+〉 < *e*^{−L/2}. We thus take |λ〉 and |+〉 to be the two dominant vectors. Notably, they are both non-negative and *K*-invariant and are, up to the exponential correction spanning the ground-state manifold, allowing us to apply the previous argument.

The essential place we have used T = T^{T} above is when we took the overlap 〈λ|λ′〉. For a positive and symmetric T, 〈λ| = [|λ〉]^{T} on σ; however, in general, it is some dual vector whose amplitudes, while still strictly positive, may not be identical to those of |λ〉.

To determine what changes in the case of nonsymmetric T, let us consider a vector |ν〉 with components , where 〈λ| now refers to the dual of |λ〉. The entries of vector |*ν*〉 are all equal to 1 in the symmetric case. Consider now a diagonal matrix whose diagonal is given by ν_{σ}. Next, perform the similarity transformation(21)

If T is strictly positive, then so is T′; and they have the same spectrum. What was gained is that the left and right dominant eigenvectors and are now given by and its transpose. To the extent that can be viewed as a local similarity transformation, the previous proof can now be repeated. However, we cannot refute the possibility that is some nonlocal transformation that can, in principle, transform a Schrodinger cat state into a physical state, rendering the previous arguments void.

This is an open-access article distributed under the terms of the Creative Commons Attribution-NonCommercial license, which permits use, distribution, and reproduction in any medium, so long as the resultant use is **not** for commercial advantage and provided the original work is properly cited.

## REFERENCES AND NOTES

**Acknowledgments:**We thank J. T. Chalker and A. Lukas (Oxford) for helpful discussions. We also thank A. Läuchli and S. Gazit for useful suggestions and comments on the manuscript.

**Funding:**Z.R. was supported by the European Union’s Horizon 2020 research and innovation program under Marie Skłodowska-Curie grant agreement no. 657111. D.L.K. was supported by the Engineering and Physical Sciences Research Council (grant no. EP/M007928/1).

**Author contributions:**Z.R. and D.L.K. contributed substantially to all aspects of this work.

**Competing interests:**The authors declare that they have no competing interests.

**Data availability:**All data needed to evaluate the conclusions in the paper are present in the paper. Additional data related to this paper may be requested from the authors.

- Copyright © 2017 The Authors, some rights reserved; exclusive licensee American Association for the Advancement of Science. No claim to original U.S. Government Works. Distributed under a Creative Commons Attribution NonCommercial License 4.0 (CC BY-NC).