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 ${\displaystyle {\mbox{QMA}}(c,s)}$ se existe um computador quântico V que verifica em tempo polinomial e um polinômio P, tal que: [1][2]

• ${\displaystyle \forall x\in L}$, existe um estado quântico  ${\displaystyle |\psi \rangle }$ de tal forma que a probabilidade de V aceitar a entrada ${\displaystyle (|x\rangle ,|\psi \rangle )}$ é maior que ${\displaystyle c}$.
• ${\displaystyle \forall x\notin L}$, para todo estado quântico ${\displaystyle |\psi \rangle }$, a probabilidade de V aceitar a entrada ${\displaystyle (|x\rangle ,|\psi \rangle )}$ é menor que ${\displaystyle s}$.

onde ${\displaystyle |\psi \rangle }$ varia com todos os estados quânticos com a maioria dos p(x).

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

${\displaystyle {\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

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.

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 é  ${\displaystyle 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  ${\displaystyle a<b\in [0,1]}$, such that ${\displaystyle {\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.[3]

Os resultados de QMA-duro são conhecidos até mesmo para modelos lattice simplistas e fisicamente realistas, como [4] ${\displaystyle 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 ${\displaystyle Z,X}$ representa a Pauli matrices ${\displaystyle \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 [5] ou uma linha de partículas quânticas com 12 Membros por partícula.[6]

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[2]), 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.[7]

QIP é QIP(k) onde k é permitido ser polinomial. Sabe-se que QIP (3) = QIP.[8] É também conhecido que QIP = IP = PSPACE.[9]

Relacionamento com outras classes

QMAestá relacionada com outras classes de complexidade, seguindo a seguinte relação:

${\displaystyle {\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.

Referências

1. Aharonov, Dorit; Naveh, Tomer (2002). «Quantum NP – A Survey». arXiv:quant-ph/0210077v1 
2. Watrous, John (2009). «Quantum Computational Complexity». In: Meyers, Robert A. Encyclopedia of Complexity and Systems Science. [S.l.: s.n.] pp. 7174–7201. arXiv:0804.3401. doi:10.1007/978-0-387-30440-3_428 
3. Kempe, Julia; Kitaev, Alexei; Regev, Oded (2006). «The complexity of the local Hamiltonian problem». SIAM Journal on Computing. 35 (5): 1070–1097. arXiv:quant-ph/0406180v2. doi:10.1137/S0097539704445226 
4. Biamonte, Jacob; Love, Peter (2008). «Realizable Hamiltonians for universal adiabatic quantum computers». Physical Review A. 78 (1). 012352 páginas. arXiv:0704.1287. doi:10.1103/PhysRevA.78.012352 
5. Oliveira, Roberto; Terhal, Barbara M. (2008). «The complexity of quantum spin systems on a two-dimensional square lattice». Quantum Information and Computation. 8 (10): 900–924. arXiv:quant-ph/0504050 
6. Aharonov, Dorit; Gottesman, Daniel; Irani, Sandy; Kempe, Julia (2009). «The power of quantum systems on a line». Communications in Mathematical Physics. 287 (1): 41–65. doi:10.1007/s00220-008-0710-3 
7. Jain, Rahul; Upadhyay, Sarvagya; Watrous, John (2009). «Two-message quantum interactive proofs are in PSPACE». Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS '09). [S.l.]: IEEE Computer Society. pp. 534–543. ISBN 978-0-7695-3850-1. doi:10.1109/FOCS.2009.30 
8. Watrous, John (2003). «PSPACE has constant-round quantum interactive proof systems». Theoretical Computer Science. 292 (3): 575–588. doi:10.1016/S0304-3975(01)00375-9 
9. Jain, Rahul; Ji, Zhengfeng; Upadhyay, Sarvagya; Watrous, John (2011). «QIP = PSPACE». Journal of the ACM. 58 (6): A30. doi:10.1145/2049697.2049704 

Ligações externas

• Aaronson, Scott. «PHYS771 Lecture 13: How Big are Quantum States?» 
• Complexity Zoo: QMA