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$ Aug 26, 2022 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, 2022 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$ Aug 26, 2022 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, 2022 at 18:55


Your Answer

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

Browse other questions tagged or ask your own question.