Se sabe que la factorización entera está en NP (ya que puede verificar la respuesta en tiempo polinómico), pero generalmente se cree que es “NP-intermedia”, es decir, no en P pero tampoco NP-hard. El hecho de que el algoritmo de Shor esté en BQP (es decir, se puede resolver en una computadora cuántica en tiempo polinómico con alta probabilidad de dar la respuesta correcta) no cambió eso.
Sabemos que P es definitivamente un subconjunto de BQP, pero el pensamiento general entre los científicos de la computación es que es mejor que P no sea igual a BQP, ya que eso significaría que todos los algoritmos cuánticos conocidos pueden ejecutarse en una computadora clásica en tiempo polinómico (y por lo tanto las computadoras cuánticas en realidad no proporcionan ninguna mejora sobre las clásicas).
El punto que estoy tratando de aclarar es que la creencia predominante en la comunidad informática es que la factorización de enteros no está en P. La introducción de algoritmos cuánticos efectivamente agregó algunas clases de complejidad más que, en términos generales, se encuentran entre P y NP, pero la relación entre todas estas clases de complejidad aún se desconoce. La factorización entera era y todavía se cree que es NP-intermedia.
- ¿La PSI que representa una partícula en movimiento tiene que ser una función compleja en la mecánica cuántica?
- ¿Se aplicará la ley de Moore a la computación cuántica?
- ¿Cuáles son las habilidades de una computadora cuántica?
- ¿Dónde existe la mecánica cuántica en la vida real?
- ¿En qué se diferencia la física cuántica de la química cuántica?
Apéndice:
Es un error común, perpetuado también en Quora, que una computadora cuántica “intenta todas las soluciones en paralelo” o algo así. Esto es completamente incorrecto .
La aceleración lograda en los algoritmos cuánticos se basa en el hecho de que, a diferencia de las probabilidades clásicas, las amplitudes de probabilidad cuántica pueden interferir entre sí. Algoritmos como Shor aprovechan esta interferencia de manera inteligente para lograr una aceleración exponencial sobre los algoritmos clásicos conocidos, incluidos los basados en la aleatoriedad clásica (por ejemplo, pertenecen a la clase de complejidad BPP).
Para reiterar, las computadoras cuánticas ciertamente no realizan en ningún sentido múltiples cálculos clásicos en paralelo.
