Mostrar código-fonte de QMA

'''QMA''', na [[Complexidade computacional|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 (complexidade)|NP]] se relaciona com [[P (complexidade)|P]], ou MA se relaciona com [[BPP]].

Informalmente, é um conjunto de [[Problema de decisão|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 <math>\mbox{QMA}(c,s)</math> se existe um computador quântico V que verifica em tempo polinomial e um [[Função polinomial|polinômio]] P, tal que: <ref>{{Citar arXiv|eprint = quant-ph/0210077v1|primeiro1 = Dorit|último1 = Aharonov|autorlink1 = Dorit Aharonov|primeiro2 = Tomer|último2 = Naveh|título= Quantum NP – A Survey|ano= 2002}}</ref><ref name="JW">{{citar livro|arxiv = 0804.3401|primeiro = John|último = Watrous|autorlink = John Watrous (computer scientist)|capítulo= Quantum Computational Complexity|ano= 2009|título= Encyclopedia of Complexity and Systems Science|páginas= 7174–7201|doi = 10.1007/978-0-387-30440-3_428|editor-nome = Robert A.|editor-sobrenome = Meyers}}</ref>
* <math>\forall x \in L</math>, existe um estado quântico  <math>|\psi\rangle</math> de tal forma que a probabilidade de V aceitar a entrada <math>(|x\rangle, |\psi\rangle)</math> é maior que <math>c</math>.
* <math>\forall x \notin L</math>, para todo estado quântico <math>|\psi\rangle</math>, a probabilidade de V aceitar a entrada <math>(|x\rangle, |\psi\rangle)</math> é menor que <math>s</math>.
onde <math>|\psi\rangle</math> varia com todos os estados quânticos com a maioria dos p(x).

A classe de complexidade <math>\mbox{QMA}</math> é definida como <math>\mbox{QMA}({2}/{3},1/3)</math>. No entanto, as constantes não são tão importantes pois a classe permanece a mesma se <math>c</math> e <math>s</math> forem estabelecidas como quaisquer constantes tais que <math>c</math> seja maior que <math>s</math>. Adicionalmente, para quaisquer polinômios <math>q(n)</math> e <math>r(n)</math>, temos
: <math>\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)})</math>.

== Problemas em QMA ==
<div>Uma vez que muitas classes interessantes estão contidas em QMA, tais como P, BQP e NP, todos os problemas dessas classes também estão em QMA. No entanto, existem problemas que estão em QMA, mas não se sabe se estão em NP ou BQP. Alguns desses problemas bem conhecidos são discutidos abaixo.<br>
</div>

Um problema é chamado QMA-duro, análogo a [[NP-difícil|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|matriz Hermitiana]] com estados quânticos, assim é  <math>2^n \times 2^n</math>  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  <math>a< b \in [0,1]</math>, such that <math>\frac{1}{b-a}=O(n^c)</math> 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.<div><br>
<div><br>
<div> <br>
</div></div></div>

O Hamiltoniano K-Local é QMA-completo para k≥ 2.<ref>{{citar periódico|último1 = Kempe|primeiro1 = Julia|último2 = Kitaev|primeiro2 = Alexei|autorlink2 = Alexei Kitaev|último3 = Regev|primeiro3 = Oded|autorlink3 = Oded Regev|título= The complexity of the local Hamiltonian problem|ano= 2006|periódico= [[SIAM Journal on Computing]]|volume = 35|número= 5|páginas= 1070–1097|arxiv = quant-ph/0406180v2|doi = 10.1137/S0097539704445226}}</ref>

Os resultados de QMA-duro são conhecidos até mesmo para modelos lattice simplistas e fisicamente realistas, como <ref>{{citar periódico|último1 = Biamonte|primeiro1 = Jacob|último2 = Love|primeiro2 = Peter|título= Realizable Hamiltonians for universal adiabatic quantum computers|periódico= [[Physical Review A]]|ano= 2008|volume = 78|número= 1|páginas= 012352|arxiv = 0704.1287|doi = 10.1103/PhysRevA.78.012352}}</ref>
<math>
H = \sum_{i}h_i Z_i + \sum_{i<j}J^{ij}Z_iZ_i + \sum_{i<j}K^{ij}X_iX_i
</math>
onde <math>Z, X</math> representa a [[Matrizes de Pauli|Pauli matrices]] <math>\sigma_z, \sigma_x</math>. 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 <ref>{{citar periódico|último = Oliveira|primeiro = Roberto|primeiro2 = Barbara M.|último2 = Terhal|título= The complexity of quantum spin systems on a two-dimensional square lattice|volume = 8|páginas= 900–924|periódico= Quantum Information and Computation|ano= 2008|número= 10|arxiv = quant-ph/0504050}}</ref> ou uma linha de partículas quânticas com 12 Membros por partícula.<ref>{{citar periódico|doi = 10.1007/s00220-008-0710-3|volume = 287|número= 1|páginas= 41–65|último = Aharonov|primeiro = Dorit|autorlink1 = Dorit Aharonov|primeiro2 = Daniel|último2 = Gottesman|autorlink2 = Daniel Gottesman|primeiro3 = Sandy|último3 = Irani|primeiro4 = Julia|último4 = Kempe|título= The power of quantum systems on a line|periódico= [[Communications in Mathematical Physics]]|ano= 2009}}</ref>

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

== Classes relacionadas ==
'''QCMA '''(ou '''MQA'''<ref name="JW">{{citar livro|arxiv = 0804.3401|primeiro = John|último = Watrous|autorlink = John Watrous (computer scientist)|capítulo= Quantum Computational Complexity|ano= 2009|título= Encyclopedia of Complexity and Systems Science|páginas= 7174–7201|doi = 10.1007/978-0-387-30440-3_428|editor-nome = Robert A.|editor-sobrenome = Meyers}}</ref>), 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.<ref>{{citar livro|último1 = Jain|primeiro1 = Rahul|último2 = Upadhyay|primeiro2 = Sarvagya|último3 = Watrous|primeiro3 = John|autorlink3 = John Watrous (computer scientist)|título= [[Symposium on Foundations of Computer Science|Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS '09)]]|publicado= IEEE Computer Society|isbn = 978-0-7695-3850-1|ano= 2009|capítulo= Two-message quantum interactive proofs are in PSPACE|doi = 10.1109/FOCS.2009.30|páginas= 534–543}}</ref>

'''QIP''' é QIP(k) onde k é permitido ser polinomial. Sabe-se que QIP (3) = QIP.<ref>{{citar periódico|último1 = Watrous|primeiro1 = John|autorlink1 = John Watrous (computer scientist)|título= PSPACE has constant-round quantum interactive proof systems|ano= 2003|periódico= [[Theoretical Computer Science (journal)| Theoretical Computer Science]]|volume = 292|número= 3|páginas= 575–588|doi = 10.1016/S0304-3975(01)00375-9}}</ref> É também conhecido que QIP = [[IP-Complexidade|IP]] = [[PSPACE]].<ref>{{citar periódico|último1 = Jain|primeiro1 = Rahul|último2 = Ji|primeiro2 = Zhengfeng|último3 = Upadhyay|primeiro3 = Sarvagya|último4 = Watrous|primeiro4 = John|autorlink4 = John Watrous (computer scientist)|periódico= [[Journal of the ACM]]|ano= 2011|título= QIP = PSPACE|volume = 58|número= 6|página= A30|doi = 10.1145/2049697.2049704}}</ref>

== Relacionamento com outras classes ==
QMAestá relacionada com outras [[Classe de complexidade|classes de complexidade]], seguindo a seguinte relação:
: <math>\mbox{P} \subseteq \mbox{NP} \subseteq \mbox{MA} \subseteq \mbox{QCMA} \subseteq \mbox{QMA}\subseteq \mbox{PP} \subseteq \mbox{PSPACE}</math>
A primeira inclusão decorre da definição de [[NP (complexidade)|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 (complexidade)|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.

{{Referências}}

== Ligações externas ==
* {{citar web|url = http://www.scottaaronson.com/democritus/lec13.html|título= PHYS771 Lecture 13: How Big are Quantum States?|último = Aaronson|primeiro = Scott}}
* ''Complexity Zoo'': [https://complexityzoo.uwaterloo.ca/Complexity_Zoo:Q#qma QMA]

{{Classes de complexidade}}
[[Categoria:Classes de complexidade]]
[[Categoria:Teoria da complexidade computacional]]