Algoritmo cuántico
[1] La teoría de la complejidad computacional le asigna la clase BQP a los algoritmos que pueden ser resueltos en un computador cuántico en tiempo polinómico con un margen de error promedio inferior a 1/4.
En el análisis de los algoritmos cuánticos es habitual comparar la cota superior asintótica con el mejor algoritmo clásico conocido, o, si el problema está resuelto, con el mejor algoritmo clásico posible.
El planteamiento del problema excluye todas las otras posibles funciones.
El algoritmo no tiene apenas utilidad práctica, pero es uno de los primeros ejemplos de un algoritmo cuántico que se ha demostrado que es exponencialmente más rápido que cualquier posible algoritmo clásico determinista.
El algoritmo de Shor, propuesto por Peter Shor en 1995 y relacionado con la aritmética modular, descompone en factores un número N en tiempo
El algoritmo de Grover, publicado por Lov Grover en 1996,[5] demostró que un problema de utilidad práctica podía ser resuelto más rápidamente que el mejor algoritmo clásico posible.
Supuso un avance significativo porque por las leyes mecánica cuántica no es posible usar las estrategias habituales para la detección y corrección de errores de la computación clásica.
