BQP

En teoría de la complejidad computacional, BQP (tiempo polinomial cuántico con error acotado) es la clase de problemas de decisión decidibles por un ordenador cuántico en tiempo polinomial con una probabilidad de error de como mucho 1/3 para todas las instancias.^[1] Es el análogo cuántico a la clase de complejidad BPP.

Un problema de decisión pertenece a BQP si existe un algoritmo cuántico (un algoritmo que se ejecuta en un ordenador cuántico) que resuelve el problema de decisión con alta probabilidad y que se ejecuta en tiempo polinomial. Una ejecución del algoritmo resolverá correctamente el problema de decisión con una probabilidad de al menos 2/3.

Definición

BQP puede verse como el conjunto de los lenguajes asociados a ciertas familias uniformes de circuitos cuánticos.^[1] Un lenguaje L pertenece a BQP si y solo si existe una familia polinomial uniforme de circuitos cuánticos $\{Q_{n}:n\in \mathbb {N} \}$ , tal que:

Para todo $n\in \mathbb {N}$ , Q_n toma n qubits como entrada y produce 1 bit como salida
Para cada x en L $\mathrm {Pr} (Q_{|x|}(x)=1)\geq {\tfrac {2}{3}}$
Para cada x que no esté en L, $\mathrm {Pr} (Q_{|x|}(x)=0)\geq {\tfrac {2}{3}}$

Alternativamente BQP puede ser definida en términos de máquinas de Turing cuánticas. Un lenguaje L pertenece a BQP si y solo si existe una máquina de Turing cuántica polinomial que acepta L con una probabilidad de error de como mucho 1/3 para todas las instancias.^[2]

Como ocurre con otras clases probabilísticas con "error acotado", la elección de 1/3 en la definición es arbitraria. Podemos ejecutar el algoritmo un número constante de veces y decidir por mayoría para conseguir cualquier probabilidad de error deseada mayor que 0 utilizando las cotas de Chernoff. La clase de complejidad tampoco cambia si permitimos un error tan grande como 1/2 − n^−c, donde c es cualquier constante positiva y n es la longitud de la entrada.^[3]

Computación cuántica

El número de qubits en el ordenador es una función polinomial del tamaño de la entrada. Por ejemplo, en el caso del algoritmo de Shor, un entero expresado en n-bits puede factorizarse utilizando aproximadamente 2n qubits.

Normalmente los cálculos en un ordenador cuántico terminan en una medición. Esto lleva al colapso de un estado cuántico a uno de los estados de la base. El estado cuántico medido será el estado correcto con alta probabilidad.

La computación cuántica ha despertado interés debido a que hay problemas de carácter práctico que se cree que no pertenecen a P pero sí pertenecen a la clase BQP. Algunos ejemplos son:

Factorización entera (ver algoritmo de Shor).^[4]
Logaritmo discreto.
Simulación de sistemas cuánticos.
Aproximación del polinomio de Jones a ciertas raíces de la unidad.

Relación con otras clases de complejidad

BQP está definida para un ordenador cuántico. Su correspondencia natural para un ordenador clásico (o una máquina de Turing junto con una fuente aleatoria) es BPP.

Como ocurre con P y BPP, BQP verifica BQP^BQP = BQP.^[2] Informalmente, esto es cierto ya que los algoritmos que toman un tiempo polinomial son cerrados bajo composición. Si un algoritmo polinomial llama a una subrutina polinomial un número polinomial de veces, el algoritmo resultante será también polinomial.

BQP contiene a P y BPP y está contenida en AWPP,^[5] PP^[6] y PSPACE.^[2]

BQP es baja para PP, con lo que una máquina PP no obtiene beneficio de resolver problemas en BQP instantáneamente, lo que proporciona evidencia de la posible diferencia de poder entre las dos clases. Las principales relaciones conocidas con clases de complejidad clásicas son

{\mathsf {P\subseteq BPP\subseteq BQP\subseteq AWPP\subseteq PP\subseteq PSPACE}}

Dado que el problema de P ≟ PSPACE aún no ha sido resuelto, se supone que la demostración de la desigualdad estricta entre estas clases y BQP es difícil.^[2] No se conoce la relación entre BQP y NP, aunque se conjetura que son incomparables. Desde mayo de 2018 se conoce que, relativa a un oráculo, BQP no está contenida en PH (una generalización de NP).^[7]

Añadiendo postselección a BQP obtenemos la clase de complejidad PostBQP que es igual a PP.^[8]^[9]

Véase también

Teoría de la complejidad cuántica

Referencias

↑ ^a ^b ^c Nielsen, Michael; Chuang, Isaac (2000). Quantum Computation and Quantum Information (en inglés) (décima edición). Cambridge University Press. ISBN 0-521-63503-9.
↑ ^a ^b ^c ^d Bernstein, Ethan; Vazirani, Umesh (October 1997). «Quantum Complexity Theory». SIAM Journal on Computing 26 (5): 1411-1473. doi:10.1137/S0097539796300921. Consultado el 23 de julio de 2018.
↑ Barak, Sanjeev Arora, Boaz (2009). Computational Complexity: A Modern Approach / Sanjeev Arora and Boaz Barak. Cambridge. p. 122. Consultado el 24 de julio de 2018.
↑ arXiv:quant-ph/9508027v2 Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, Peter W. Shor
↑ Fortnow, Lance; Rogers, John (1999). «Complexity limitations on Quantum computation». J. Comput. Syst. Sci. (Boston, MA: Academic Press) 59 (2): 240-252. ISSN 0022-0000. doi:10.1006/jcss.1999.1651.
↑ L. Adleman, J. DeMarrais, and M.-D. Huang. Quantum computability. SIAM J. Comput., 26(5):1524–1540, 1997.
↑ [1]
↑ Aaronson, Scott (2005). «Quantum computing, postselection, and probabilistic polynomial-time». Proceedings of the Royal Society A 461 (2063): 3473-3482. Bibcode:2005RSPSA.461.3473A. arXiv:quant-ph/0412187. doi:10.1098/rspa.2005.1546. . Preprint available at [2]
↑ Aaronson, Scott (11 de enero de 2004). «Complexity Class of the Week: PP». Computational Complexity Weblog. Consultado el 2 de mayo de 2008.

Enlaces externos

Enlace de Complexity Zoo a BQP Archivado el 3 de junio de 2013 en Wayback Machine.

Datos: Q601325

[Chuang2000-1] Nielsen, Michael; Chuang, Isaac (2000). Quantum Computation and Quantum Information (en inglés) (décima edición). Cambridge University Press. ISBN 0-521-63503-9.

[BernVazi-2] Bernstein, Ethan; Vazirani, Umesh (October 1997). «Quantum Complexity Theory». SIAM Journal on Computing 26 (5): 1411-1473. doi:10.1137/S0097539796300921. Consultado el 23 de julio de 2018.

[3] Barak, Sanjeev Arora, Boaz (2009). Computational Complexity: A Modern Approach / Sanjeev Arora and Boaz Barak. Cambridge. p. 122. Consultado el 24 de julio de 2018.

[Shor-4] rXiv:quant-ph/9508027v2 Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, Peter W. Shor

[5] Fortnow, Lance; Rogers, John (1999). «Complexity limitations on Quantum computation». J. Comput. Syst. Sci. (Boston, MA: Academic Press) 59 (2): 240-252. ISSN 0022-0000. doi:10.1006/jcss.1999.1651.

[6] L. Adleman, J. DeMarrais, and M.-D. Huang. Quantum computability. SIAM J. Comput., 26(5):1524–1540, 1997.

[7] [1]

[PostBQP=PP-8] Aaronson, Scott (2005). «Quantum computing, postselection, and probabilistic polynomial-time». Proceedings of the Royal Society A 461 (2063): 3473-3482. Bibcode:2005RSPSA.461.3473A. arXiv:quant-ph/0412187. doi:10.1098/rspa.2005.1546. . Preprint available at [2]

[9] Aaronson, Scott (11 de enero de 2004). «Complexity Class of the Week: PP». Computational Complexity Weblog. Consultado el 2 de mayo de 2008.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]