BQP

Clase de complejidad

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.​ 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.