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.
We study quantum chains whose Hamiltonians are perturbations by bounded interactions of short range of a Hamiltonian that does not couple the degrees of freedom located at different sites of the chain and has a strictly positive energy gap above its ground-state energy. We prove that, for small values of a coupling constant, the spectral gap of the perturbed Hamiltonian above its ground-state energy is bounded from below by a positive constant uniformly in the length of the chain. In our proof we use a novel method based on local Lie-Schwinger conjugations of the Hamiltonians associated with connected subsets of the chain.
Abstract This work clarifies a fundamental relationship between spectral gap and ground state properties, where the spectral gap means the energy difference between the ground state and the first excited state. In short-range interacting systems, the well-known exponential clustering theorem has been derived for the ground states: the bipartite correlations decay exponentially beyond a finite localization length, which is smaller than the inverse of the spectral gap. However, in more general systems including long-range interacting systems, the problem of how to characterize universal ground state structures by reference to the spectral gap is an ongoing challenge. Recently, for such systems, another fundamental constraint dubbed local reversibility has been proved for arbitrarily gapped ground states; as a consequence, it also results in the exponential concentration of the probability distribution of macroscopic observables. In this paper, we extend this kind of asymptotic behavior to more general setups.
The quantum analogue of a constraint satisfaction problem is a sum of local Hamiltonians - each local Hamiltonian specifies a local constraint whose violation contributes to the energy of the given quantum state. Formalizing the intuitive connection between the ground (minimal) energy of the Hamiltonian and the minimum number of violated constraints is problematic, since the number of constraints being violated is not well defined when the terms in the Hamiltonian do not commute. The detectability lemma proved in this paper provides precisely such a quantitative connection. We apply the lemma to derive a quantum analogue of a basic primitive in classical complexity: amplification of probabilities by random walks on expander graphs. It holds under the restriction that the interaction graph of the local Hamiltonian is an expander. Our proofs are based on a novel structure imposed on the Hilbert space that we call the
XY decomposition, which enables a reduction from the quantum non-commuting case to the commuting case (where many classical arguments go through). The results may have several interesting implications. First, proving a quantum analogue to the PCP theorem is one of the most important challenges in quantum complexity theory. Our quantum gap amplification lemma may be viewed as the quantum analogue of the first of the three main steps in Dinur's PCP proof. Quantum gap amplification may also be related to spectral gap amplification, and in particular, to fault tolerance of adiabatic computation. Finally, the detectability lemma, and the
XY decomposition provide a handle on the structure of local Hamiltonians and their ground states.
We establish an exponentially decaying upper bound on the average energy that can be extracted in quantum energy teleportation (QET) protocols executed on finite-range {gapped} lattice systems possessing a unique ground state. Under mild regularity assumptions on the Hamiltonian and uniform operator-norm bounds on the local measurement operators, there exist positive constants
C and
μ (determined by the spectral gap, interaction range and local operator norms) such that for any local measurement performed in a region
A and any outcome-dependent local unitaries implemented in a disjoint region
B separated by distance
d=dist(A,B) one has
∣EA−EB∣≤Ce−μd. The bound is nonperturbative, explicit up to model-dependent constants, and follows from the variational characterization of the ground state combined with exponential clustering implied by the spectral gap. We emphasize that the constants deteriorate as the gap closes (equivalently, as the correlation length diverges), so the estimate is intended for the gapped regime.