QMA

QMA, na teoria da complexidade, que vem de Quantum Merlin Arthur, é uma classe de complexidade análoga à classe NP ou à classe de complexidade probabilística MA. QMA está relacionada a BQP da mesma forma que NP se relaciona com P, ou MA se relaciona com BPP. Informalmente, é um conjunto de problemas de decisão para os quais quando uma resposta é "sim", ele usa espaço da ordem de um polinomial em computador quântico que tem um verificador de ordem probabilística. Por outro lado, se a resposta for "não", cada máquina quântica de espaço polinomial é rejeita por um verificador de alta probabilidade.. Mais precisamente, as provas têm de ser verificáveis em tempo polinomial em um computador quântico, de tal forma que se a resposta for "sim", de fato, o verificador aceita uma prova correta com probabilidade superior a 2/3, e se a resposta for não, então não existe nenhuma prova de que o convence a aceitar o verificador com probabilidade maior do que 1/3. É comum as constantes de 2/3 e 1/3 serem alteradas. Alterando 2/3 para qualquer constante estritamente entre 1/2 e 1, e alterando a constante 1/3 para valores estritamente entre 0 e 1/2 , não se altere a classe QMA. QAM é uma classe de complexidade relacionada, na qual os personagens fictícios Arthur e Merlin realizam a seguinte seqüência: Arthur gera uma cadeia aleatória, Merlin responde com um certificado quântico e Arthur o verifica como uma máquina BQP.