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.
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.
The quantum adiabatic theorem ensures that a slowly changing system, initially prepared in its ground state, will evolve to its final ground state with arbitrary precision. As a first result this thesis extends the original theorem to projection operators keeping the statement valid for Hamiltonians with degenerate ground spaces. Yet the main focus of this work lies in studying the efficiency of quantum circuit simulations by adabatic quantum computation. The standard Hamiltonian construction by Kitaev is based on a path graph reflecting the
L computation steps and influencing the scaling of the necessary evolution time by its spectral gap of
O(L21). Aspiring to an improved running time we generalize Kitaev's Hamiltonian to so-called standard graph Hamiltonians based on graph families with a different spectral gap. In this generalized construction the first two time derivatives of the Hamiltonian and the fraction of initial vertices appear as additional parameters of running time. In a first step the time derivatives can be proven to be constant. Expansion results from spectral graph theory however impose a trade-off between the spectral gap and the fraction of initial vertices as well as the fraction of final vertices which corresponds to the probability for obtaining the correct computational output. Graphs with spectral gap
O(Lk1),
k<2, turn out to contradict very likely, graphs with
k<1 even for sure at least one of the efficiency criterias for running time, output probability or Hamiltonian implementation. The above results may also be obstacles for a possible quantum PCP-theorem in complexity theory claiming the local Hamiltonian problem with constant gap to be QMA-complete since the very same Kitaev Hamiltonian is constructed in the QMA-hardness proof for the Local Hamiltonian problem.
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.