Also known as Quantum Merlin Arthur
QMA, as an abbreviation for Quantum Merlin Arthur, refers to a complexity class in computational complexity theory. It is the set of all formal languages that satisfy the following properties:
~7 min read
Article
8 sectionsContents
- Definition
- Problems in QMA
- The local Hamiltonian problem
- Other QMA-complete problems
- Related classes
- Relationship to other classes
- References
- External links
QMA, as an abbreviation for Quantum Merlin Arthur, refers to a complexity class in computational complexity theory. It is the set of all formal languages that satisfy the following properties: If a string is in the language, then there is a polynomial-size quantum proof (representable as a quantum state) that convinces a polynomial-time quantum verifier (running on a quantum computer) of this fact with high probability. If a string is not in the language, every polynomial-size quantum state is rejected by the verifier with high probability.
The relationship between QMA and BQP is analogous to the relationship between the complexity classes NP and P. It is also analogous to the relationship between the probabilistic complexity classes MA and BPP.