# If we can prepare a ground state efficiently, when can we prepare the second-lowest energy eigenstate?

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.

• 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. – DaftWullie Apr 30 at 6:37
• 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. – Mark S Apr 30 at 12:54
• 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. – Norbert Schuch May 1 at 10:13