<p>On the second question: <a href="http://arxiv.org/abs/0905.4755v2" rel="noreferrer">http://arxiv.org/abs/0905.4755v2</a> gives a classical QMA-complete eigenvalue problem related Markov chains.</p>

CC BY-SA 3.0
2011-06-25T19:33:18.583Z
2011-06-25T20:43:51.830Z
2011-06-25T20:43:51.830Z
Martin Schwarz
<p>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?</p>

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

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

CC BY-SA 3.0
2011-06-25T21:48:08.240Z
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.
Kaveh
CC BY-SA 3.0
2011-06-26T14:57:49.423Z
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.
Robin Kothari
CC BY-SA 3.0
2012-07-09T16:43:45.050Z
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...
Niel de Beaudrap
<cc.complexity-theory><quantum-computing>
Why must QMA complete problems be promise problems?
Henry Yuen
# Why must QMA complete problems be promise problems?

(Asked by: username_0 on 2011-06-25)

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?

**Tags:** cc.complexity-theory, quantum-computing

> **Comments:**
> **username_1**: 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.  
> **username_2**: 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.  
> **username_3**: 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...  

---

## 1 answers

### Answer by username_4 on 2011-06-25. Score: 7

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


---

