# Definition of promise problems with growth conditions

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.

• 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. Aug 26 at 16:59
• @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.
– EuYu
Aug 26 at 17:16
• 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. Aug 26 at 17:53
• @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$.
– EuYu
Aug 26 at 18:55