11
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 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$
    – Robin Kothari
    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$
    – Niel de Beaudrap
    Jul 9, 2012 at 16:43

1 Answer 1

Reset to default
6
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

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

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