# How is a promise gap related to a spectral gap?

In linear algebra one often concerns oneself with the spectral gap of a given matrix, which may be defined as the difference between the smallest and second-smallest eigenvalue (or, depending on convention and context, between the largest and second-largest eigenvalue). In computational complexity one often concerns oneself with a promise gap of a given problem, which may be loosely defined as a difference of some variable between accepting and rejecting inputs.

The different meanings of "gap" appear to overlap in certain problems of quantum computing. For example a promise gap is used in the $$\mathsf{QMA}$$-complete problem of determining the ground energy of a Hamiltonian - e.g. a promise that the ground energy of the given Hamiltonian is either less than a first value or greater than a second value, but we are also concerned with the spectral gap of the considered Hamiltonian, which may affect the general dynamics of the Hamiltonian.

I'd like to know whether there is any relation between the two different meanings of "gap". For example:

In certain formulations of $$\mathsf{QMA}$$-complete or $$\mathsf{BQP}$$-complete problems, can the spectral gap be smaller than the promised gap? What would be the implications of the promise gap being larger than the spectral gap?

In general the larger the promise gap the easier the problem may be; similarly the larger the spectral gap the easier the problem may be.

To be concrete, take a problem in $$\mathrm{QMA}_1$$, that is, where a "yes" instance has a perfectly accepting verifier, and put it into the Kitaev QMA construction. In a "yes" instance, the resulting Hamiltonian will have ground state energy 0 and a 1/poly(N) spectral gap, and in the latter case, the Hamiltonian will have a 1/poly(N) ground state energy, and the spectrum can be pretty much anything, in particular, the spectral gap of the "no" Hamiltonian can be exponentially small, or even less.
• In a "yes" instance of Kitaev's construction could the second-smallest eigenvalue be in the promise gap? I.E. the smallest eigenvalue is $\lt a$, say $a-\epsilon$, but with the second smallest $\gt a$, say $a+\epsilon$, but still $\le b$? Mar 20, 2021 at 18:11