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, 2011 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$ Jun 26, 2011 at 14:57
  • 2
    $\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$ Jul 9, 2012 at 16:43

1 Answer 1


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


Your Answer

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

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