I'd like to know if there's anything that can be said about whether and when we can efficiently prepare a state corresponding to the second-lowest eigenvalue of a given Hamiltonian, or in any other way learn what this energy is?

For example, in the case of a Hamiltonian of a doubly-stochastic Markov chain $H$ acting on a space $\Omega$ of known dimension $N$ that is promised to be ergodic, and wherein we have oracle access to adjacent nodes, we can prepare arbitrary states $\vert b\rangle$ and perform quantum phase estimation to thereon, to do an eigenvalue sampling on the probability distribution supported on the spectrum of $H$.

My intuition, which I don't know how to formalize, is that given two vertices $i$ and $j$ that are far from each other in the state space $\Omega$ of the Markov chain, the spectral decomposition of a superposition such as: $$\vert\psi\rangle=\frac{1}{\sqrt{2}}(\vert i\rangle-\vert j\rangle)$$ likely has a large component corresponding to this second-lowest eigenstate.

Thus eigenvalue sampling may well lead to such a second-lowest energy eigenstate.

  • 1
    $\begingroup$ I know nothing about the specific case you're talking about. In the general case, however, I imagine it would be relatively straightforward to modify existing proofs of the QMA-hardness of finding the ground state energy so that the ground state is known but the first excited state is QMA-hard to find. $\endgroup$ – DaftWullie Apr 30 at 6:37
  • $\begingroup$ Thanks! If $H$ is sign-problem free, then the Perron-Frobenius theorem puts a lot of constraints on the ground state, but the Perron-Frobenius theorem might say nothing, or very little, about the first excited state/spectral gap. $\endgroup$ – Mark S Apr 30 at 12:54
  • 1
    $\begingroup$ arxiv.org/abs/1312.4758 discusses the complexity of spectral gap and related question. -- On a different note, it should be easy to build a Hamiltonian whose ground state is trivial (e.g. all zeros) but whose 1st excited state can be the ground state of any other Hamiltonian, i.e. QMA hard. $\endgroup$ – Norbert Schuch May 1 at 10:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.