BQP

En Teoría de la complejidad computacional, BQP representa la clase de algoritmos que pueden ser resueltos en un computador cuántico en tiempo polinómico con un margen de error promedio inferior a 1/4.Dicho de otra forma, existe un algoritmo cuántico cuya cota superior en tiempo es polinómica para resolver ese problema, tal que la probabilidad de obtener una respuesta equivocada es menor de 25%.El nivel de error de 1/4 es arbitrario, cualquier valor real k tal que 0 < k < 1/2 podría ser utilizado sin cambiar el conjunto BQP.La idea es que si la probabilidad de error es pequeña, la ejecución del algoritmo un número suficiente de veces lleva a una probabilidad exponencialmente pequeña de que la mayoría de las ejecuciones sean erróneas.El número de qubits en el computador depende del tamaño del problema. Por ejemplo, ya se conocen algoritmos para factorizar un entero de n bits utilizando solo 2n qubits.La computación cuántica ha despertado interés debido a que problemas que se supone no pertenecen a P pertenecen a la clase BQP. Actualmente solo se han clasificado tres de esos problemas:factorización entera (ver algoritmo de Shor)Logaritmo discretoSimulación de sistemas cuánticos (ver Computador cuántico universal)La clase BQP se define basándose en un computador cuántico. La clase correspondiente para una máquina de Turing se llama BPP.BQP contiene a P y a BPP y está contenida en PP y en PSPACE.