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 ${\displaystyle \{Q_{n}:n\in \mathbb {N} \}}$, tal que:

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

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

Enlaces externos

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

Esta página se editó por última vez el 30 sep 2023 a las 16:47.