Hispanopedia Wiki
Articulo de referencia

QMA

QMA , abreviatura de Quantum Merlin Arthur, se refiere a una clase de complejidad en la teoría de la complejidad computacional . Es el conjunto de todos los lenguajes formales q...

Hispanopedia WikiContenido en espanolLectura gratuita

QMA , abreviatura de Quantum Merlin Arthur, se refiere a una clase de complejidad en la teoría de la complejidad computacional . Es el conjunto de todos los lenguajes formales que satisfacen las siguientes propiedades:

  1. Si una cadena pertenece al lenguaje, entonces existe una prueba cuántica de tamaño polinomial (representable como un estado cuántico ) que convence a un verificador cuántico de tiempo polinomial (que se ejecuta en una computadora cuántica ) de este hecho con alta probabilidad.
  2. Si una cadena no pertenece al lenguaje, el verificador rechaza con alta probabilidad cualquier estado cuántico de tamaño polinomial.

La relación entre QMA y BQP es análoga a la relación entre las clases de complejidad NP y P. También es análoga a la relación entre las clases de complejidad probabilística MA y BPP .

QAM es una clase de complejidad relacionada, en la que los agentes ficticios Arthur y Merlin llevan a cabo la siguiente secuencia: Arthur genera una cadena aleatoria, Merlin responde con un certificado cuántico y Arthur lo verifica como una máquina BQP.

Definición

Un lenguaje L está enQMETROA(do,s){\displaystyle {\mathsf {QMA}}(c,s)}si existe un verificador cuántico de tiempo polinomial V y un polinomial ⁠pag(incógnita){\displaystyle p(x)}de tal manera que: [ 1 ] [ 2 ] [ 3 ]

  • ∀incógnita∈L{\displaystyle \forall x\in L}, existe un estado cuántico|ψ⟩{\displaystyle |\psi \rangle }de tal manera que la probabilidad de que V acepte la entrada(|incógnita⟩,|ψ⟩){\displaystyle (|x\rangle ,|\psi \rangle )}es mayor que c .
  • ∀incógnita∉L{\displaystyle \forall x\notin L}y para todos los estados cuánticos|ψ⟩{\displaystyle |\psi \rangle }con como máximopag(|incógnita|){\displaystyle p(|x|)}cúbits , la probabilidad de que V acepte la entrada(|incógnita⟩,|ψ⟩){\displaystyle (|x\rangle ,|\psi \rangle )}es menor que s .

La clase de complejidadQMETROA{\displaystyle {\mathsf {QMA}}}se define como igual aQMETROA(2/3,1/3){\displaystyle {\mathsf {QMA}}({2}/{3},1/3)}Sin embargo, las constantes no son demasiado importantes ya que la clase permanece sin cambios si c y s se establecen como cualquier constante tal que c sea mayor que s . Además, para cualquier polinomioq(norte){\displaystyle q(n)}yr(norte){\displaystyle r(n)}, tenemos

QMETROA(23,13)=QMETROA(12+1q(norte),12−1q(norte))=QMETROA(1−2−r(norte),2−r(norte)){\displaystyle {\mathsf {QMA}}\left({\frac {2}{3}},{\frac {1}{3}}\right)={\mathsf {QMA}}\left({\frac {1}{2}}+{\frac {1}{q(n)}},{\frac {1}{2}}-{\frac {1}{q(n)}}\right)={\mathsf {QMA}}(1-2^{-r(n)},2^{-r(n)})}.

Problemas en QMA

Dado que QMA incluye muchas clases interesantes, como P, BQP y NP, todos los problemas de estas clases también pertenecen a QMA. Sin embargo, existen problemas que pertenecen a QMA pero que no se sabe que estén en NP o BQP. Algunos ejemplos conocidos de estos problemas se analizan a continuación.

Se dice que un problema es QMA-difícil, análogo a NP-difícil , si todo problema en QMA se puede reducir a él. Se dice que un problema es QMA- completo si es QMA-difícil y pertenece a QMA.

El problema hamiltoniano local

Un hamiltoniano k -local (mecánica cuántica)H{\displaystyle H}es una matriz hermitiana que actúa sobre n cúbits y que puede representarse como la suma demetro{\displaystyle m}Términos hamiltonianos que actúan sobre como máximok{\displaystyle k}cúbits cada uno.

H=∑i=1metroHi{\displaystyle H=\sum _{i=1}^{m}H_{i}}

El problema general del hamiltoniano k -local es, dado un hamiltoniano k -localH{\displaystyle H}para encontrar el valor propio más pequeñoλ{\displaystyle \lambda }deH{\displaystyle H}. [ 4 ]λ{\displaystyle \lambda }También se la denomina energía del estado fundamental del hamiltoniano.

La versión de decisión del problema del hamiltoniano k -local es un tipo de problema de promesa y se define como, dado un hamiltoniano k -local yα,β{\displaystyle \alpha,\beta}dóndeα>β{\displaystyle \alpha >\beta }para decidir si existe un autoestado cuántico|ψ⟩{\displaystyle |\psi \rangle }deH{\displaystyle H}con valor propio asociadoλ{\displaystyle \lambda }, de tal manera queλ≤β{\displaystyle \lambda \leq \beta }o siλ≥α{\displaystyle \lambda \geq \alpha }.

El problema del hamiltoniano local es el análogo cuántico de MAX-SAT . El problema del hamiltoniano k -local es QMA-completo para k ≥ 2. [ 5 ]

El problema del hamiltoniano 2-local restringido a actuar sobre una cuadrícula bidimensional de cúbits , también es QMA-completo. [ 6 ] Se ha demostrado que el problema del hamiltoniano k -local sigue siendo QMA-difícil incluso para hamiltonianos que representan una línea unidimensional de partículas con interacciones de vecinos más cercanos con 12 estados por partícula. [ 7 ] Si el sistema es invariante traslacionalmente, su problema del hamiltoniano local se vuelve QMA EXP- completo (como la entrada del problema está codificada en el tamaño del sistema, el verificador ahora tiene un tiempo de ejecución exponencial mientras mantiene la misma brecha de promesa). [ 8 ] [ 9 ]

Se conocen resultados de dureza QMA para modelos de red simples de cúbits como el hamiltoniano ZX [ 10 ].HZincógnita=∑ihiZi+∑iΔiincógnitai+∑i<jJijZiZj+∑i<jKijincógnitaiincógnitaj{\displaystyle H_{ZX}=\sum _{i}h_{i}Z_{i}+\sum _{i}\Delta _{i}X_{i}+\sum _{i<j}J^{ij}Z_{i}Z_{j}+\sum _{i<j}K^{ij}X_{i}X_{j}} dóndeZ,incógnita{\displaystyle Z,X}representan las matrices de Pauliσz,σincógnita{\displaystyle \sigma _{z},\sigma _{x}}Estos modelos son aplicables a la computación cuántica adiabática universal .

Los problemas de hamiltonianos k -locales son análogos a los problemas clásicos de satisfacción de restricciones . [ 11 ] La siguiente tabla ilustra los dispositivos análogos entre los CSP clásicos y los hamiltonianos.

Otros problemas completos de QMA

Puede encontrar una lista de problemas QMA-completos conocidos en https://arxiv.org/abs/1212.6312 .

QCMA (o MQA [ 2 ] ), que significa Quantum Classical Merlin Arthur (o Merlin Quantum Arthur), es similar a QMA, pero la demostración debe ser una cadena clásica. Se desconoce si QMA es igual a QCMA, aunque QCMA está claramente incluido en QMA.

QIP(k) , que significa Tiempo Polinomial Interactivo Cuántico (k mensajes), es una generalización de QMA donde Merlín y Arturo pueden interactuar durante k rondas. QMA es QIP(1). Se sabe que QIP(2) está en PSPACE. [ 12 ]

QIP es QIP(k) donde k puede ser polinomial en el número de cúbits. Se sabe que QIP(3) = QIP. [ 13 ] También se sabe que QIP = IP = PSPACE . [ 14 ]

Relación con otras clases

QMA se relaciona con otras clases de complejidad conocidas mediante las siguientes relaciones:

PAG⊆nortePAG⊆METROA⊆QdoMETROA⊆QMETROA⊆PAGPAG⊆PAGSPAGAdomi{\displaystyle {\mathsf {P}}\subseteq {\mathsf {NP}}\subseteq {\mathsf {MA}}\subseteq {\mathsf {QCMA}}\subseteq {\mathsf {QMA}}\subseteq {\mathsf {PP}}\subseteq {\mathsf {PSPACE}}}

La primera inclusión se deriva de la definición de NP . Las siguientes dos inclusiones se derivan del hecho de que el verificador se hace más poderoso en cada caso. QCMA está contenido en QMA ya que el verificador puede obligar al probador a enviar una prueba clásica midiendo las pruebas tan pronto como se reciben. Alexei Kitaev y John Watrous demostraron que QMA está contenido en PP . También se demuestra fácilmente que PP está en PSPACE .

Se desconoce si alguna de estas inclusiones es incondicionalmente estricta, ya que ni siquiera se sabe si P está estrictamente contenido en PSPACE o si P = PSPACE. Sin embargo, los límites superiores actualmente mejor conocidos para QMA son [ 15 ] [ 16 ].

QMETROA⊆A0PAGPAG{\displaystyle {\mathsf {QMA}}\subseteq {\mathsf {A_{0}PP}}}yQMETROA⊆PAGQMETROA[logramo]{\displaystyle {\mathsf {QMA}}\subseteq {\mathsf {P^{QMA[log]}}}},

donde ambosA0PAGPAG{\displaystyle {\mathsf {A_{0}PP}}}yPAGQMETROA[logramo]{\displaystyle {\mathsf {P^{QMA[log]}}}}están contenidos enPAGPAG{\displaystyle {\mathsf {PP}}}Es improbable queQMETROA{\displaystyle {\mathsf {QMA}}}igualPAGQMETROA[logramo]{\displaystyle {\mathsf {P^{QMA[log]}}}}, ya que esto implicaríaQMETROA=doo{\displaystyle {\mathsf {QMA}}={\mathsf {co}}}-QMETROA{\displaystyle {\mathsf {QMA}}}Se desconoce si PAGQMETROA[logramo]⊆A0PAGPAG{\displaystyle {\mathsf {P^{QMA[log]}}}\subseteq {\mathsf {A_{0}PP}}}o viceversa.

Referencias

  1. ↑ Aharonov, Dorit ; Naveh, Tomer (2002). "Quantum NP – A Survey". arXiv : quant-ph/0210077v1 .
  2. 1 2 Watrous, John (2009). "Complejidad computacional cuántica". En Meyers, Robert A. (ed.). Enciclopedia de la complejidad y la ciencia de sistemas . págs. 7174–7201 . arXiv : 0804.3401 . doi : 10.1007/978-0-387-30440-3_428 . ISBN  978-0-387-75888-6. S2CID 1380135 . 
  3. ↑ Gharibian, Sevag; Huang, Yichen; Landau, Zeph; Shin, Seung Woo (2015). "Complejidad hamiltoniana cuántica". Fundamentos y tendencias en informática teórica . 10 (3): 159– 282. arXiv : 1401.3916 . doi : 10.1561/0400000066 . S2CID 47494978 . 
  4. ↑ O'Donnel, Ryan. "Conferencia 24: QMA: Quantum Merlin Arthur" (PDF) . Consultado el 18 de abril de 2021 .
  5. ↑ Kempe, Julia ; Kitaev, Alexei ; Regev, Oded (2006). "La complejidad del problema hamiltoniano local". SIAM Journal on Computing . 35 (5): 1070–1097 . arXiv : quant-ph/0406180v2 . doi : 10.1137/S0097539704445226 ..
  6. ↑ Oliveira, Roberto; Terhal, Barbara M. (2008). "La complejidad de los sistemas de espín cuántico en una red cuadrada bidimensional". Quantum Information and Computation . 8 (10): 900– 924. arXiv : quant-ph/0504050 . Bibcode : 2005quant.ph..4050O . doi : 10.26421/QIC8.10-2 . S2CID 3262293 . 
  7. ↑ Aharonov, Dorit ; Gottesman, Daniel ; Irani, Sandy; Kempe, Julia (2009). "El poder de los sistemas cuánticos en una línea". Communications in Mathematical Physics . 287 (1): 41– 65. arXiv : 0705.4077 . Bibcode : 2009CMaPh.287...41A . doi : 10.1007/s00220-008-0710-3 . S2CID 1916001 . 
  8. ↑ Aharonov, Dorit; Gottesman, Daniel; Irani, Sandy; Kempe, Julia (1 de abril de 2009). "El poder de los sistemas cuánticos en una línea". Communications in Mathematical Physics . 287 (1): 41– 65. arXiv : 0705.4077 . Bibcode : 2009CMaPh.287...41A . CiteSeerX 10.1.1.320.7377 . doi : 10.1007/s00220-008-0710-3 . S2CID 1916001 .  
  9. ↑ Bausch, Johannes; Cubitt, Toby; Ozols, Maris (noviembre de 2017). "La complejidad de las cadenas de espín invariantes traslacionalmente con baja dimensión local" . Annales Henri Poincaré . 18 (11): 3449– 3513. arXiv : 1605.01718 . Bibcode : 2017AnHP...18.3449B . doi : 10.1007/s00023-017-0609-7 .
  10. ↑ Biamonte, Jacob; Love, Peter (2008). "Hamiltonianos realizables para computadoras cuánticas adiabáticas universales". Physical Review A . 78 (1) 012352. arXiv : 0704.1287 . Bibcode : 2008PhRvA..78a2352B . doi : 10.1103/PhysRevA.78.012352 . S2CID 9859204 . .
  11. ↑ Yuen, Henry. "La complejidad del entrelazamiento" (PDF) . henryyuen.net . Archivado del original (PDF) el 28 de febrero de 2025. Consultado el 20 de abril de 2021 .
  12. ↑ Jain, Rahul; Upadhyay, Sarvagya; Watrous, John (2009). "Las pruebas interactivas cuánticas de dos mensajes están en PSPACE". Actas del 50.º Simposio Anual del IEEE sobre Fundamentos de la Informática (FOCS '09) . IEEE Computer Society. págs. 534–543 . arXiv : 0905.1300 . doi : 10.1109/FOCS.2009.30 . ISBN  978-0-7695-3850-1. S2CID 6869749 . 
  13. ↑ Watrous, John (2003). "PSPACE tiene sistemas de prueba interactivos cuánticos de ronda constante" . Theoretical Computer Science . 292 (3): 575– 588. doi : 10.1016/S0304-3975(01)00375-9 .
  14. ^ Jainista, Rahul; Ji, Zhengfeng; Upadhyay, Sarvagya; Watrous, John (2011). "QIP = ESPACIO" . Revista de la ACM . 58 (6): A30. doi : 10.1145/2049697.2049704 . S2CID 265099379 . 
  15. ↑ Vyalyi, Mikhail N. (2003). "QMA = PP implica que PP contiene PH" . Coloquio electrónico sobre complejidad computacional .
  16. ↑ Gharibian, Sevag; Yirka, Justin (2019). "La complejidad de simular mediciones locales en sistemas cuánticos" . Quantum . 3 189. arXiv : 1606.05626 . Bibcode : 2019Quant...3..189G . doi : 10.22331/q-2019-09-30-189 .
  • Aaronson, Scott. "PHYS771 Lección 13: ¿Qué tan grandes son los estados cuánticos?" .
  • Gharibian, Sevag. "Conferencia 5: Quantum Merlin Arthur (QMA) y reducción de errores fuertes" (PDF) . Archivado del original (PDF) el 4 de noviembre de 2019. Consultado el 28 de febrero de 2020 .
  • Zoológico de la complejidad : QMA