BQP
De Wikipedia, la enciclopedia libre
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 de computación cuántica 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 con una pequeña probabilidad de error se corre el algoritmo un número suficiente de veces se llega a una probabilidad exponencialmente pequeña de que la mayoría de las corridas 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 discreto
- Simulación de sistemas cuánticos (ver Computador cuántico universal)
La clase QBP 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.
| clases de complejidad más importantes |
| L | NL | P | NP | Co-NP | NP-C | Co-NP-C | NP-hard | UP | #P | #P-C | NC | P-C |
| PSPACE | PSPACE-C | EXPTIME | EXPSPACE | BQP | BPP | RP | ZPP | PCP | IP | PH |
