Questions tagged [qma]
QMA stands for the complexity class Quantum Merlin Arthur.
6
questions
1
vote
1
answer
144
views
Is QMA known to contain Co-NP?
Is QMA known to contain Co-NP? If not, would Co-NP being contained in QMA have any implications for other complexity classes. (e.g. Causing the polynomial heirachy to collapse.)
- 177
3
votes
3
answers
165
views
The complexity of LH with constant gap
Kitaev's quantum equivalent of the Cook-Levin Theorem, provides a polynomial time classical reduction from a QMA verification circuit to a sum $H$ of local hamiltonians, such that the least eigenvalue ...
- 91
1
vote
0
answers
138
views
Two definitions of $QMA$
In this question, I am trying to understand the equivalence between the following two definitions of the complexity class QMA.
In Quantum Computational Complexity, John Watrous defines the class QMA ...
- 997
4
votes
2
answers
349
views
Simulation of every physical quantum system on quantum computer
Let me quote from the section 9.3 of Classical and Quantum Computation by Kitaev, Shen and Vyalyi.
With high confidence, we may claim that every physical quantum system
can be efficiently ...
- 997
12
votes
2
answers
705
views
What is the Relationship between QMA and AM?
I read in S. P. Jordan, D. Gosset, P. J. Love's "$QMA$-complete problems for stoquastic Hamiltonians and Markov matrices" that it is unlikely that $QMA \subseteq AM$.
I was surprised about this ...
- 1,558
9
votes
2
answers
652
views
Understanding QMA
This question comes out of an answer Joe Fitzsimons gave to a different question. Most natural complexity classes have a one-line "intuitive description" that helps characterize core problems in that ...
- 31.7k