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?


2 Answers 2


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.

  • $\begingroup$ Thank you for your reply! Does this also apply to the transverse field Ising Hamiltonian with $H_{init} = \sum_i X_i$ and $H_{final}=\sum_{i,j} a_{i,j}Z_i Z_j +\sum_i a_i Z_i$? $\endgroup$
    – MonteNero
    Commented Jul 13, 2022 at 3:41
  • $\begingroup$ I don’t know enough to say, sorry! You could ask another question though. $\endgroup$ Commented Jul 13, 2022 at 10:47

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.