I'm reading Watrous's excellent survey paper on paper on quantum complexity theory. In it he states that it would be surprising if a QMA -complete problem were found to have a vacuous promise (I.e. Be a language). Why is this so?

Does it have to do with the fact that the k-local Hamiltonian problem is a promise problem?

Also, this leads me to a related question: are there QMA-complete problems that aren't inherently "quantum" in nature?

  • 3
    $\begingroup$ I guess that would be an interesting thing because QMA is defined as a semantic class, such a complete problem would give a syntactic characterization. Check the related questions about syntactic/semantic complexity classes on cstheory/Mathoverflow. $\endgroup$ – Kaveh Jun 25 '11 at 21:48
  • 3
    $\begingroup$ Moreover, this phenomenon is not specific to QMA in particular. Other semantically defined classes like MA are BPP are also not known to have complete languages. $\endgroup$ – Robin Kothari Jun 26 '11 at 14:57
  • 1
    $\begingroup$ I wonder what the necessary and sufficient conditions are in practice for a problem to be "not quantum". I suppose that any problem which invokes a completely positive map (e.g. is a given CP map invertible, or far from invertible?) or tensor product structure (e.g. does a positive semidefinite operator, given in a k-local presentation, have eigenvalues less than delta, or are they all substantially greater than delta?) would be examples of suspiciously quantum problems, whether or not they are presented in terms of quantum channels/evolution or the state space of an aggregate system... $\endgroup$ – Niel de Beaudrap Jul 9 '12 at 16:43

On the second question: http://arxiv.org/abs/0905.4755v2 gives a classical QMA-complete eigenvalue problem related Markov chains.

| cite | improve this answer | |

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.