Under what conditions the minimum eigengap is non-zero?

Question

I would like to know sufficient conditions for a non-zero eigengap of a time-dependent Hamiltonian.

Suppose we have a time-dependent Hamiltonian $H(t)$ defined as follows: $$H(t) = (1-s(t))H_{init} + s(t)H_{final}$$ where $0 \leq s(t) \leq 1$ is monotonically increasing continuous function for $t \in [0,T]$. Suppose that we know and can prepare the ground state $|\psi_0\rangle$ of $H_{init}$. The final goal is to evolve $|\psi_0\rangle$ into the ground state of $H_{final}$. For this to work, the minimum eigengap of $H(t)$ must be non-zero for all $t \in [0,T]$.

I know that the necessary condition for non-zero eigengap is the non-commutativity of $H_{init}$ and $H_{prob}$. However, I don't know if this is a sufficient condition, i.e., the non-commutativity $\implies$ non-zero eigengap?

Answer 1

I think this is formally undecidable.

In detail, Cubitt, Perez-Garcia, and Wolf (arxiv, Nature) reduced the problem of determining the gap of a translationally-invariant Hamiltonian to the problem of determining whether a given set of tiles can be used to tile the plane. Back in the 60's, Berger had shown that such tiling problems reduce to the Halting problem.

Thus to answer your question, it is very unlikely knowable, now or in the future, all necessary and sufficient conditions under which a Hamiltonian has a gap. If we knew such conditions, we could solve the Halting problem, which we can't do, therefore we can't know such conditions.

See this Shtetl-Optimized post. See also this very nice Scientific American remembrance from the authors about their proof discovery process.

The gap of Hamiltonians of a specific class of interest may be decidable. For example, as you indicate, if $H_{init}$ and $H_{prob}$ commute then there is no gap, but in general without any other limitations on the Hamiltonian the problem is likely undecidable.

Additionally as indicated in the answer from @quantum, the setup of the question appears to ask about adiabatic evolution. Even if there was a non-zero gap we might never know, as the runtime of the adiabatic algorithm is polynomial in this gap. I envision that to decide the amount of a gap, promised that there is a gap, of some class of problems to be, if not undecidable, then at least QMA-hard.

Answer 2

There are none known to us at this time.

Also, the min gap may become exponentially small with increasing problem size, requiring exponentially slow annealing. To no avail in solving the problem.