Let's say I am given a Hamiltonian $H$, whose ground state is efficiently preparable. We know that $||H|| \leq 1$. Let that ground state be $|\psi_{0}\rangle$, with energy $E_{0}$. We also know that the unitary $U$ such that \begin{equation} U |\psi_{0}\rangle |00\cdots0\rangle = |\psi_{0}\rangle |E_{0}\rangle, \end{equation} is efficiently preparable.

Consider the promise problem. For the yes instances, \begin{equation} E_{0} \geq c, \end{equation} and for the no instances, \begin{equation} E_{0} \leq s, \end{equation} where $c - s \geq \frac{1}{O\big(2^{poly(n)}\big)}$. Would this promise problem be in $BQP$?


1 Answer 1


As you've written it, yes. The implication of what you've written is that $|E_0\rangle$ is prepared exactly. Since it has been done efficiently, we know that you must have used only a number of qubits that's polynomial in $n$. Thus, I can measure those poly($n$) qubits and exactly determine the value of $E_0$. Once I have an exact classical value, it's no problem to compare it to $c$ and $s$, again each expressed using poly($n$) bits.

However, I feel that this problem is not generally a good reflection of what one would have to do in practice. But I'm rather rusty on this sort of thing, and wouldn't want to commit myself further!


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.