How is a promise gap related to a spectral gap?

Question

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.

Answer 1

The spectral gap is pretty much independent of the promise gap.

(First off, my feeling is that "promise gap" is a little bit misleading, though formally correct: What it really refers to, in essence, is the accuracy you are aiming for in determining the energy of the Hamiltonian. One way is to guarantee that the problem does not have a ground state energy inside the "promise gap", but you can equivalently just as much allow your algorithm to fail for instances which have an energy inside the gap. But I will consider the "promise" version in the following.)

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.

Whether this can be done for QMA problems as well seems to be linked to the problem whether proofs can be made unique -- see https://arxiv.org/abs/0810.4840, which also discusses aspects related to the spectral gap.