Hispanopedia WikiEn la teoría de la complejidad computacional , el tiempo polinomial cuántico exacto ( EQP o, a veces, QP ) es la clase de problemas de decisión que pueden ser resueltos por una computadora cuántica con probabilidad de error cero y en tiempo polinomial garantizado en el peor de los casos. Es el análogo cuántico de la clase de complejidad P. Esto contrasta con la computación cuántica de error limitado , donde se espera que los algoritmos cuánticos se ejecuten en tiempo polinomial, pero no siempre lo hacen.
En la definición original de EQP, cada lenguaje se calculaba mediante una única máquina de Turing cuántica (QTM), utilizando un conjunto finito de compuertas cuyas amplitudes podían calcularse en tiempo polinomial. Sin embargo, algunos resultados han requerido el uso de un conjunto infinito de compuertas. Las amplitudes en el conjunto de compuertas suelen ser números algebraicos.
Referencias
- Esbozos de informática teórica
- Teoría de la complejidad cuántica
