QMA

This article is about the complexity class. For the coaxial RF connector, see QMA and QN connector.

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:

  1. 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.
  2. 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.

QAM is a related complexity class, in which fictional agents Arthur and Merlin carry out the sequence: Arthur generates a random string, Merlin answers with a quantum certificate and Arthur verifies it as a BQP machine.

This article is issued from Wikipedia. The text is available under Creative Commons Attribution-Share Alike 4.0 unless otherwise noted. Additional terms may apply for the media files.