1
$\begingroup$

Let's denote $kLP_{c}$ the promise problem where the input, given in an explicit encoding with finite number of bits, is a set $\{p_{1},p_{2},\ldots p_{m}\}$ of k-local projectors over a n-qbits register such that the least eigenvalue $\varepsilon_{\min}$ of $\sum_{i=1}^{m}p_{i}$ is either $\varepsilon_{\min}\leq\varepsilon\tag{y}\label{eq:LHy-1}$ where $\varepsilon$ is a parameter given in input, or $\varepsilon_{\min}(n)\geq\varepsilon+n^{-c}\tag{n}\label{eq:LHn-1}$ and the answer is yes (no) in the \ref{eq:LHy-1} (\ref{eq:LHn-1}) case.

That is, the $k$LH promise problem with hamiltonians that are projectors. Is this restriction known/studied? A circuit->projectors mapping of the type used to prove QMA1-hardness of QSAT should work in mapping to kLP the generic QMA problem. Or one could maybe reduce a kLH instance to an equivalent instance of kLP. However, how would the energy gap behave?

$\endgroup$
2
$\begingroup$

The standard Kitaev construction yields a Hamiltonian where the individual terms are projectors (up to energy shift & rescaling), each of which constrains the system to a subspace. Thus, the problem is QMA-hard.

$\endgroup$
9
  • $\begingroup$ It seems to me that this doesn't (immediately) work for the 2-local reduction link $\endgroup$ – J.Ask Mar 24 at 10:59
  • 1
    $\begingroup$ @J.Ask Sure, but I have also never talked about that. My answer stands: The problem you are asking about is QMA-hard. And please don't edit your question afterwards to invalidate existing answers! If you have a new question, ask a new question! $\endgroup$ – Norbert Schuch Mar 24 at 12:35
  • $\begingroup$ My edit didn't invalid your answer. I just liked to know if the problem is known/studied also for lower localities than 5. Doesn't seem necessary to open a new question for each k. But if you prefere restate this explicitely for Kitaev's construction and I accept your answer. But I'd like to know about k=2 $\endgroup$ – J.Ask Mar 24 at 12:49
  • 1
    $\begingroup$ @J.Ask It renders my answer incomplete. Regarding k<5, IIRC there is a frustration-free k=3 construction, so this can also be done with projectors. For k=2, one has to see if the perturbation gadgets can be constructed with projectors as well. I would suspect yes, but I am not 100% sure. (Also, note that any Hamiltonian can be written as a sum of projectors if you allow several terms to act on the same spins, a perspective of which, if I recall correctly, you are a strong proponent. (Maybe you have to be more precise in stating your question ;p ) $\endgroup$ – Norbert Schuch Mar 24 at 12:56
  • 1
    $\begingroup$ Might still work, you can approximate any rational. Question is only how good the approximation has to be to not break the normalization of the Hamiltonian vs. gap. $\endgroup$ – Norbert Schuch Mar 24 at 17:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.