I will preface this by saying that I am a physicist, so I suspect that there are some basic misunderstandings about computer science terminology here which I hope can be clarified.

A typical definition of a promise problem $L$ is a pair of subsets $L=L_1\cup L_0$ such that $L_0,L_1\subseteq \{0,1\}^*$ and $L_0\cap L_1 = \emptyset$. I have some questions about how growth conditions are enforced within the definitions of promise problems.

Consider a problem like $k$-local Hamiltonian. The input to such a problem is a string of the form $z = (H,a,b)$, where $H$ is (some encoding of) a $k$-local Hamiltonian on $n$-qubits, and where $a,b$ are the promise gap parameters, i.e., the Hamiltonian comes with the promise that its eigenvalues are either below $a$ or above $b$, and the problem is to decide whether the smallest eigenvalue $\lambda(H)$ satisfies $\lambda(H) \le a$ or $\lambda(H)\ge b$.

For a well-defined problem, we also need to impose a growth condition on $a,b$ such that $b-a \ge 1/\mathrm{poly}(n)$. My question is how do you actually define a promise problem $L = \{(H,a,b)\}$ whose members satisfy a condition like $b-a \ge 1/\mathrm{poly}(n)$?

As an example of my confusion, consider some fixed element $z \in L$ with $z=(H,a,b)$. For any $b>a$, there will always exist some polynomial $p$ such that $b-a > 1/p(n)$, so the condition $b-a\ge 1/\mathrm{poly}(n)$ seems vacuous or unenforceable to me. Alternatively, we could define the problem $L$ with a fixed polynomial $p_0$ in mind and consider only strings $(H,a,b)$ where $b-a>1/p_0(n)$. This seems contrary to the intentions of the problem however, and it seems important (in the standard proofs of QMA-completeness, for example) that the gap can be arbitrarily polynomially small.

So my basic question is: How do I properly define the promise problem associated with something like the $k$-local Hamiltonian problem where the parameters $a,b$ are meant to satisfy a non-trivial growth condition.

  • $\begingroup$ It's just a computer-science thing I guess. Most of the time I think of $a$ and $b$ as constant, but they could of course depend on $n$. For example you could have $a=f(n)$ and $b=g(n)$. The growth condition would be that $g(n)-f(n)$ is at least inverse polynomial in $n$ (and not, say, inverse exponential in $n$). This keeps the gap large enough, regardless of $n$. You don't want to close the gap for $n=1,000,000$ qubits. $\endgroup$
    – Mark S
    Aug 26 at 16:59
  • $\begingroup$ @MarkS That seems close to my proposal in the question with $L$ defined relative to some fixed polynomial $p_0$. The thing that confuses me about that is whether such a problem with some fixed polynomial gap size is really general enough to be QMA-complete. A standard reduction of some QMA problem to $k$-local Hamiltonian gives you something like $b-a \approx 1/Q(n)$ where $Q(n)$ is the size of the verification circuit. It seems in this case that it's actually important that $b-a$ can be arbitrarily polynomially small. $\endgroup$
    – EuYu
    Aug 26 at 17:16
  • $\begingroup$ Well, it still has to be in QMA (e.g., polynomially verifiable with a quantum circuit). You can't make the gap so small that you need many many qubits of precision in your quantum phase estimation circuit to verify the gap. I think. $\endgroup$
    – Mark S
    Aug 26 at 17:53
  • $\begingroup$ @MarkS I understand that. My point is that if a problem $P$ has verification times $Q(n)$, then the reduction from $P$ to $k$-LH will have a promise gap on the order of $1/Q(n)$. So it seems like you cannot simply take $a=f(n)$ and $b=g(n)$ for fixed $f$ and $g$. $\endgroup$
    – EuYu
    Aug 26 at 18:55


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.