Algoritmo cuántico
Un algoritmo cuántico es un algoritmo que se ejecuta en un modelo realista de computación cuántica, como el modelo de circuito cuántico, como el que se ilustra en la figura. 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. Se usa la notación de Landau para definir la relación entre la talla de la entrada del problema y el número de pasos necesarios para resolverlo, o el número de posiciones de memoria que se utilizan durante su resolución.
El algoritmo de Deutsch-Jozsa fue propuesto por David Deutsch y Richard Jozsa en 1992 y fue mejorado posteriormente por Richard Cleve, Artur Ekert, Chiara Macchiavello, y Michele Mosca en 1998. Su función es determinar si una función de tipo caja negra es «constante» o «balanceada». Esto es, dada una función que para una entrada de n bits da un solo bit de salida, determinar si la salida es independiente de la entrada o si para la mitad de las entradas es 0 y para la otra mitad es 1. 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 y espacio . Es responsable de buena parte de la atención que se le ha dedicado a la computación cuántica, por su relación con el problema RSA de importancia fundamental en criptografía.
El algoritmo de Grover, publicado por Lov Grover en 1996, demostró que un problema de utilidad práctica podía ser resuelto más rápidamente que el mejor algoritmo clásico posible. El algoritmo realiza una búsqueda en una base de datos desordenada con N entradas en un número de pasos de orden , consumiendo un espacio de memoria de orden .
El desarrollo de la primera corrección de errores cuántica, propuesta también por Peter Shor en 1995, fue el primer paso hacia la computación cuántica a prueba de errores. 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.