En realidad, hay una lista completa de algoritmos cuánticos en este enlace: Quantum Algorithm Zoo.
Algunos de los que creo son más notables:
- El algoritmo de búsqueda de Grover (mencionado por Andrew Lucas en su respuesta)
- Transformada de Fourier (también dada por Andrew)
- El algoritmo de Shor para la factorización (también dado por Andrew)
- Resolviendo sistemas lineales (ie [math] Ax = b [/ math])
- Flujos de red
- Simulación de QFTs topológicos.
- Cálculo de árboles NAND (se pueden usar para resolver juegos de 2 jugadores)
- Recocido cuántico
El último no es realmente como los demás. El recocido cuántico le proporciona un algoritmo, sí, pero con eso puede codificar muchos algoritmos diferentes. En cierto sentido, es un algoritmo de aproximación que le permite minimizar alguna función. Si puede codificar un problema de optimización en esa forma, puede obtener una buena aceleración. El análisis de complejidad es más difícil para él, ya que en realidad no está tomando medidas discretas, por lo que aún no se puede comparar con los otros algoritmos cuánticos. Cómo interpretar la complejidad de una instancia de partícula de un algoritmo de recocido cuántico sigue siendo una pregunta de investigación abierta.
En general, el principio que permite que los algoritmos cuánticos sean tan exitosos es la interferencia, que para empezar es la base de la mecánica cuántica. La razón por la que puede hacer factoring tan rápido es porque reorganiza las respuestas “incorrectas” para que se cancelen entre sí. Entonces, lo que quiere hacer es explotar la interferencia de estas amplitudes de onda en su algoritmo, que es algo que obviamente no puede hacer con un esquema de cálculo clásico. Otra forma de decir esto es que las computadoras cuánticas son buenas para encontrar el período.