QMA

EN Texte en anglais Pas encore d'article dans ta langue : extrait en anglais.

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