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

## Definição

Uma linguagem L está na classe ${\mbox{QMA}}(c,s)$ se existe um computador quântico V que verifica em tempo polinomial e um polinômio P, tal que:
* $\forall x\in L$, existe um estado quântico $|\psi \rangle$ de tal forma que a probabilidade de V aceitar a entrada $(|x\rangle ,|\psi \rangle )$ é maior que $c$.
* $\forall x\notin L$, para todo estado quântico $|\psi \rangle$, a probabilidade de V aceitar a entrada $(|x\rangle ,|\psi \rangle )$ é menor que $s$.
onde $|\psi \rangle$ varia com todos os estados quânticos com a maioria dos p(x).
A classe de complexidade ${\mbox{QMA}}$ é definida como ${\mbox{QMA}}({2}/{3},1/3)$. No entanto, as constantes não são tão importantes pois a classe permanece a mesma se $c$ e $s$ forem estabelecidas como quaisquer constantes tais que $c$ seja maior que $s$. Adicionalmente, para quaisquer polinômios $q(n)$ e $r(n)$, temos
    ${\mbox{QMA}}\left({\frac {2}{3}},{\frac {1}{3}}\right)={\mbox{QMA}}\left({\frac {1}{2}}+{\frac {1}{q(n)}},{\frac {1}{2}}-{\frac {1}{q(n)}}\right)={\mbox{QMA}}(1-2^{-r(n)},2^{-r(n)})$.

## Problemas em QMA

Um problema é chamado QMA-duro, análogo a NP-hard, se todos os problemas em QMA pode ser reduzida a ele. Um problema é dito ser QMA-completa é QMA-dura e QMA.

### O problema Hamiltoniano local

O problema hamiltoniano local é o análogo a MAX-sat. É uma matriz Hermitiana com estados quânticos, assim é $2^{n}\times 2^{n}$ para um sistema de entrada n. Um Hamiltoniano k-local é um Hamiltoniano que pode ser escrito como a soma de Hermitianas, cada uma não-trivial, em no máximo tamanho K (em vez de todo o tamanho n).
O problema hamiltoniano k-local, que é um problema promessa, é definida como se segue: A entrada é um hamiltoniano k-local de tamanho n, que é a soma de diversas matrizes hermitianas que de tamanho k. A entrada também contém dois números $a<b\in [0,1]$, such that ${\frac {1}{b-a}}=O(n^{c})$ para alguma constante c. O problema consiste em determinar se o valor deste hamiltoniano é inferior a ou maior do que b, promessa de que uma delas é o caso.
O Hamiltoniano K-Local é QMA-completo para k≥ 2.
Os resultados de QMA-duro são conhecidos até mesmo para modelos lattice simplistas e fisicamente realistas, como $H=\sum _{i}h_{i}Z_{i}+\sum _{i<j}J^{ij}Z_{i}Z_{i}+\sum _{i<j}K^{ij}X_{i}X_{i}$ onde $Z,X$ representa a Pauli matrices $\sigma _{z},\sigma _{x}$. Tais modelos são aplicáveis a computação quântica adiabática universal.
As Hamiltonianas para o problema QMA-completo pode também ser restringido a uma matriz bidimensional ou uma linha de partículas quânticas com 12 Membros por partícula.

### Outros problemas QMA-completo

Uma lista de problemas QMA-completo conhecidos pode ser encontradas em http://arxiv.org/abs/1212.6312.

## Classes relacionadas

QCMA (ou MQA), de Quantum Classical Merlin Arthur (ou Merlin Quantum Arthur), é semelhante a QMA, mas a prova tem de ser uma cadeia clássica. Não se sabe se QMA é igual a QCMA, embora QCMA é claramente contido em QMA.
QIP(k), que está para Quantum Interativo de tempo polinomial (k mensagens), é uma generalização de QMA onde Merlin e Arthur podem interagir para k rodadas. QMA é QIP (1). QIP (2) é conhecido por ser em PSPACE.
QIP é QIP(k) onde k é permitido ser polinomial. Sabe-se que QIP (3) = QIP. É também conhecido que QIP = IP = PSPACE.

## Relacionamento com outras classes

QMAestá relacionada com outras classes de complexidade, seguindo a seguinte relação:
    ${\mbox{P}}\subseteq {\mbox{NP}}\subseteq {\mbox{MA}}\subseteq {\mbox{QCMA}}\subseteq {\mbox{QMA}}\subseteq {\mbox{PP}}\subseteq {\mbox{PSPACE}}$
A primeira inclusão decorre da definição de NP. As próximas duas inclusões seguem a partir do fato de que o verificador está sendo feito mais poderoso em cada caso. QCMA está contido em QMA pois o verificador pode forçar o provador a enviar uma prova clássica por provas de medição assim que eles são recebidos. O fato de que QMA está contido em PP foi mostrado por Alexei Kitaev e John Watrous. PP também é facilmente demonstrado estar contida em PSPACE.
Não se sabe se alguma destas inclusões é também igualdade. Não é sequer sabido se P está estritamente contida em PSPACE ou P = PSPACE.