QMA(Quantum Merlin Arthur), is the quantum analog of NP, and QMA(k) is the class with $k$ verifiers. These are important classes when studying Quantum Complexity theory. QMA(k) is QMA with $k$ unentangled provers($k$ Merlins), or BQP verfiers. These classes enable us to formally study the complexity of Entanglement. For instance the class QMA(2) could help us to study the separability of quantum states, and resources required for telling whether these states are separable or far from separable.

A natural question arises - What are the upper bounds for these classes (QMA, QMA(k))- do these classes have nontrivial upper bounds(could they have upper bounds such as PSPACE?


You probably want to check out the complexity zoo for known results. For example, the listing on QMA(2) states:

It was shown in ABD+08 that a conjecture they call the Strong Amplification Conjecture implies that QMA(2) is contained in PSPACE.

It was shown in HM13 that QMA(k) = QMA(2) for k >= 2. However we still do not know if QMA(2) = QMA. The best known upper bound is NEXP.

| improve this answer | |
  • $\begingroup$ I updated the entry on the zoo. Could you requote? $\endgroup$ – Sanketh Menda Apr 22 '18 at 23:36

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.