Clase QMA

En la teoría de la complejidad , QMA (del inglés Quantum Merlin Arthur ) es el análogo cuántico de NP en la teoría clásica de la complejidad y el análogo de MA en la probabilística. Está relacionado con BQP de la misma manera que NP está relacionado con P , o MA está relacionado con BPP .

De manera informal, se trata de un conjunto de lenguajes para los que existe una prueba cuántica polinomial, aceptada por un algoritmo cuántico polinomial en el tiempo con alta probabilidad.

Definición

Un lenguaje L pertenece si existe un algoritmo cuántico V polinomio en el tiempo y un polinomio p(x) tal que: [1] [2] ${\mbox{QMA}}(c,s)$

${\ estilo de visualización \ para todos x \ en L}$ , hay un estado cuántico tal que la probabilidad de que V tome más de . $|\psi\ángulo$ ${\ estilo de visualización (| x \ ángulo, | \ psi \ ángulo)}$ $C$
$\forall x\notin L$ , para cualquier estado cuántico , la probabilidad de que V tome menos de . $|\psi\ángulo$ ${\ estilo de visualización (| x \ ángulo, | \ psi \ ángulo)}$ $s$

donde es el estado cuántico con p(x) qubits. $|\psi\ángulo$

Definamos una clase como una clase igual a . De hecho, las constantes no son importantes y la clase no cambiará si las constantes arbitrarias son mayores que . También para cualquier polinomio y , es cierto ${\mbox{QMA))$ ${\mbox{QMA}}({2}/{3},1/3)$ $C$ $s$ $C$ $s$ ${\ estilo de visualización q (n)}$ ${\ estilo de visualización r (n)}$

{\mbox{QMA}}\left({\frac {2}{3}},{\frac {1}{3}}\right)={\mbox{QMA}}\left({\ fracción {1}{2}}+{\frac {1}{q(n)}},{\frac {1}{2}}-{\frac {1}{q(n)))\right) ={\mbox{QMA}}(1-2^{-r(n)},2^{-r(n)})

Clases relacionadas

${\mbox{QCMA))$ (o [2] ) el nombre se lee como Merlin Arthur clásico cuántico (o Merlin Quantum Arthur), es un análogo de QMA, pero la prueba (enviada por Merlin) debe ser una cadena regular. No se sabe si QMA y QCMA son lo mismo. ${\mbox{MQA))$

${\mbox{QIP}}(k)$ es una clase de lenguajes reconocidos por protocolos interactivos cuánticos con tiempo polinómico y k rondas, es una generalización de QMA en la que se permite transmitir no un mensaje, sino k. De la definición se deduce que QMA coincide con QIP(1). Se sabe que QIP(2) está contenido en PSPACE. [3]

${\mbox{QIP}}$ es una clase de lenguajes de QIP(k), donde k puede ser polinomial en el número de qubits. Se sabe que QIP(3) = QIP. [4] También se sabe que QIP = IP. [5]

${\mbox{QMA}}_{1}$ es una clase de lenguajes aceptados por los protocolos cuánticos Merlin Arthur con una integridad ideal.

Relaciones con otras clases

Se sabe sobre QMA que

{\mbox{P}}\subseteq {\mbox{NP}}\subseteq {\mbox{MA}}\subseteq {\mbox{QCMA}}\subseteq {\mbox{QMA}}\subseteq {\ mbox{PP}}\subseteq {\mbox{PSPACE}}

La primera incrustación se deriva de la definición de NP. Las siguientes dos inclusiones son correctas porque los verificadores son cada vez más fuertes. La afirmación de que QMA está contenida en PP ha sido probada por Alexei Kitaev y John Watrus. PP también está contenido en PSPACE .

No se sabe cuáles de estas inclusiones son estrictas.

Notas

↑ Dorit Aharonov & Tomer Naveh (2002), Quantum NP - A Survey, arΧiv : quant-ph/0210077v1 [quant-ph].
↑ 1 2 John Watrous (2008), Complejidad computacional cuántica, arΧiv : 0804.3401v1 [quant-ph].
↑ Jain, Rahul; Upadhyay, Sarvagya; Watros, John Las pruebas interactivas cuánticas de dos mensajes están en PSPACE // FOCS '09: Actas del 50º Simposio Anual IEEE de 2009 sobre Fundamentos de Ciencias de la Computación . - IEEE Computer Society , 2009. - P. 534-543. — ISBN 978-0-7695-3850-1 .
↑ Watrous, JohnPSPACE tiene sistemas de prueba interactivos cuánticos de ronda constante // Ciencias de la computación teórica : diario. - Essex, Reino Unido: Elsevier Science Publishers Ltd., 2003. - Vol. 292 , núm. 3 . - pág. 575-588 . — ISSN 0304-3975 . - doi : 10.1016/S0304-3975(01)00375-9 .
↑ Jain, Rahul; Ji, Zhengfeng; Upadhyay, Sarvagya; Watros, John QIP = PSPACE // STOC '10: Actas del 42º simposio ACM sobre Teoría de la computación . - ACM, 2010. - Pág. 573-582. — ISBN 978-1-4503-0050-6 .

Literatura

"Algoritmos para computación cuántica: logaritmos discretos y factorización" PW Shor, AT&T Bell Labs. doi:10.1109/SFCS.1994.365700

Enlaces

A. Kh. Shen, M. N. Vyaly, Curso de conferencias "Computación clásica y cuántica". Lección 8: Definición de computación cuántica. Ejemplos // Intuit.ru, 15/03/2007

Clases de complejidad de algoritmos
Considerado ligero	DLOGTIME CA 0 ACC 0 TC0 [ es L SL RL Países Bajos CAROLINA DEL NORTE SC CC PAGS P-completa ZPP PR BPP BQP EQP APX
Se supone que es difícil	UP notario público NP completo co-NP co-NP-completo AM MA QMA PH ⊕P PÁGINAS #PAGS #P- IP ESPACIO P PSPACE-completo
Considerado difícil	EXPTIME NEXPTIME EXPESPACIO 2-EXPTIM PRIMARIA R PR RE RE-completar Co-RE Co-RE-completo TODOS

informatica cuantica

Conceptos generales

comunicaciones cuánticas

canal cuántico
- red cuántica
criptografía cuántica
- Distribución de clave cuántica
Teletransportación de energía cuántica
teletransportación cuántica
Codificación cuántica ultradensa
LOCC
destilación cuántica

Algoritmos cuánticos

simulador cuántico
Algoritmo Deutsch-Yozhi
Algoritmo de Bernstein-Wazirani
algoritmo de Grover
Transformada cuántica de Fourier
Algoritmo de Shor
el problema de simon
Algoritmo de estimación de fase cuántica
Algoritmo de computación cuántica
recocido cuántico
Enfriamiento algorítmico
Algoritmo cuántico para resolver un sistema de ecuaciones lineales
ganancia de amplitud

Teoría de la complejidad cuántica

Modelos de computación cuántica

circuito cuántico
- puerta cuántica
Computadora cuántica unilateral
- grupo
Computación cuántica adiabática
Computadora cuántica topológica

Prevención de decoherencia

Corrección de errores cuánticos
Códigos de estabilización
Formalismo de estabilización
Código convolucional cuántico

Implementaciones físicas

óptica cuántica	Electrodinámica cuántica de cavitación Electrodinámica cuántica de contorno Computación cuántica basada en óptica lineal Protocolo KLM Muestreo bosónico
átomos superfríos	Computadora cuántica de iones absorbidos rejilla óptica
basado en la espalda	Computadora cuántica basada en resonancia magnética nuclear La computadora cuántica de Kane Computadora cuántica perdida - DiVincenzo centro NV
Computadoras cuánticas superconductoras	qubit de carga qubit de transmisión qubit de fase Transmón