Cheeger inequalities bound the spectral gap
γ of a space by isoperimetric properties of that space and vice versa. In this paper, I derive Cheeger-type inequalities for nonpositive matrices (aka stoquastic Hamiltonians), real matrices, and Hermitian matrices. For matrices written
H=L+W, where
L is either a combinatorial or normalized graph Laplacian, I show that: (1) when
W is diagonal and
L has maximum degree
dmax, $2h \geq γ\geq \sqrt{h^2 + d_{\max}^2}-d_\max$; (2) when
W is real, we can often route negative-weighted edges along positive-weighted edges such that the Cheeger constant of the resulting graph obeys an inequality similar to that above; and (3) when
W is Hermitian, the weighted Cheeger constant obeys
2h≥γ here
h is the weighted Cheeger constant of
H. This constant reduces bounds on
γ to information contained in the underlying graph and the Hamiltonian's ground-state. If efficiently computable, the constant opens up a very clear path towards adaptive quantum adiabatic algorithms, those that adjust the adiabatic path based on spectral structure. I sketch a bashful adiabatic algorithm that aborts the adiabatic process early, uses the resulting state to approximate the weighted Cheeger constant, and restarts the process using the updated information. Should this approach work, it would provide more rigorous foundations for adiabatic quantum computing without \textit{a priori} knowledge of the spectral gap.
Determining spectral gaps in the thermodynamic limit is a central challenge in quantum many-body physics. When a fixed boundary condition is imposed, this problem is undecidable: no algorithm, even with unlimited resources, can decide for every Hamiltonian whether it is gapped. Yet the thermodynamic limit is meant to capture the intrinsic properties of very large systems, which should not depend on how their boundaries are chosen. We therefore consider the bulk spectral gap, which concerns only the intrinsic excitations of the infinite system, and ask what can and cannot be computed about it. First, we give a general algorithm producing a hierarchy of certified upper bounds on the bulk gap, arbitrarily tight at the cost of more computation. Second, we prove that the spectral gap problem remains undecidable in the bulk, already for translationally invariant nearest-neighbour chains of fixed local dimension. Hence no general algorithm produces convergent lower bounds, and no convergent upper-bounding algorithm, ours included, admits a computable convergence rate. The bulk spectral gap is thus certifiable from above but uncomputable from below; more precisely, the bulk-gaplessness promise problem is RE-complete, exactly as hard as the halting problem. The same construction shows that no general algorithm can decide whether a given product state is a ground state, and that convergent bounds on ground-state expectation values admit no computable convergence rate in general. Finally, we obtain the first nontrivial certified upper bounds on the bulk gap of the spin-1/2 kagome Heisenberg antiferromagnet.
We prove that generic quantum local Hamiltonians are gapless. In fact, we prove that there is a continuous density of states above the ground state. The Hamiltonian can be on a lattice in any spatial dimension or on a graph with a bounded maximum vertex degree. The type of interactions allowed for include translational invariance in a disorder (i.e., probabilistic) sense with some assumptions on the local distributions. Examples include many-body localization and random spin models. We calculate the scaling of the gap with the system's size when the local terms are distributed according to a Gaussian β orthogonal random matrix ensemble. As a corollary, there exist finite size partitions with respect to which the ground state is arbitrarily close to a product state. When the local eigenvalue distribution is discrete, in addition to the lack of an energy gap in the limit, we prove that the ground state has finite size degeneracies. The proofs are simple and constructive. This work excludes the important class of truly translationally invariant Hamiltonians where the local terms are all equal.
Abstract Energy gap, the difference between the energy of the ground-state of a given Hamiltonian and the energy of its first excited state, is a parameter of a critical importance in analysis of phase transitions and adiabatic quantum computation. We present a concrete technique to determine an upper bound for the energy gap of a Hamiltonian H 0 based on properties of the set of expectation values of H 0 and an additional auxiliary Hamiltonian V . This formalism can be applied to obtain an effective criterion of gaplessness, which we illustrate with a concrete example of the XY model —a physical system with vanishing energy gap.
We consider a family of translation-invariant quantum spin chains with nearest-neighbor interactions and derive necessary and sufficient conditions for these systems to be gapped in the thermodynamic limit. More precisely, let ψ be an arbitrary two-qubit state. We consider a chain of n qubits with open boundary conditions and Hamiltonian Hn(ψ) which is defined as the sum of rank-1 projectors onto ψ applied to consecutive pairs of qubits. We show that the spectral gap of Hn(ψ) is upper bounded by 1/(n − 1) if the eigenvalues of a certain 2 × 2 matrix simply related to ψ have equal non-zero absolute value. Otherwise, the spectral gap is lower bounded by a positive constant independent of n (depending only on ψ). A key ingredient in the proof is a new operator inequality for the ground space projector which expresses a monotonicity under the partial trace. This monotonicity property appears to be very general and might be interesting in its own right. As an extension of our main result, we obtain a complete classification of gapped and gapless phases of frustration-free translation-invariant spin-1/2 chains with nearest-neighbor interactions.
We consider a family of translation-invariant quantum spin chains with nearest-neighbor interactions and derive necessary and sufficient conditions for these systems to be gapped in the thermodynamic limit. More precisely, let
ψ be an arbitrary two-qubit state. We consider a chain of
n qubits with open boundary conditions and Hamiltonian
Hn(ψ) which is defined as the sum of rank-1 projectors onto
ψ applied to consecutive pairs of qubits. We show that the spectral gap of
Hn(ψ) is upper bounded by
1/(n−1) if the eigenvalues of a certain two-by-two matrix simply related to
ψ have equal non-zero absolute value. Otherwise, the spectral gap is lower bounded by a positive constant independent of
n (depending only on
ψ). A key ingredient in the proof is a new operator inequality for the ground space projector which expresses a monotonicity under the partial trace. This monotonicity property appears to be very general and might be interesting in its own right. As an extension of our main result, we obtain a complete classification of gapped and gapless phases of frustration-free translation-invariant spin-1/2 chains with nearest-neighbor interactions.