
A quantum algorithm is a step-by-step procedure designed to run on quantum computers to solve problems efficiently.Los algoritmos cuánticos explotan tres recursos clave: paralelismo cuántico (superposición), entrelazamiento cuántico e interferencia de amplitudes. En lugar de probar opciones, transforman la superposición de todas las entradas de manera que al final la interferencia constructiva amplifica la amplitud de la respuesta correcta, mientras que la información incorrecta se anula mutuamente. La eficiencia a menudo se mide por el número de consultas al oráculo, una 'caja negra' que verifica la solución.
Las bases teóricas fueron sentadas por Richard Feynman en 1982, señalando que los sistemas cuánticos son difíciles de simular clásicamente. David Deutsch en 1985 formuló el concepto de máquina de Turing cuántica y presentó el primer ejemplo de algoritmo cuántico que requiere menos consultas al oráculo. En 1992, Deutsch y Richard Jozsa lo generalizaron mostrando una ventaja exponencial. En 1994, Peter Shor desarrolló el algoritmo de factorización, y en 1996, Lov Grover propuso un algoritmo de aceleración cuadrática para búsqueda.
Un algoritmo cuántico típico consta de cuatro etapas: inicialización del registro en una superposición de todos los estados de entrada (por ejemplo, transformada de Hadamard), aplicación del oráculo (cálculo cuántico de la función), amplificación de la solución correcta (por ejemplo, procedimiento de Grover o transformada cuántica de Fourier) y medición. La aceleración se logra porque las operaciones cuánticas actúan sobre las amplitudes, no sobre las probabilidades, y el número de estados posibles crece exponencialmente con el número de cúbits.
El algoritmo de Shor rompe los sistemas de cifrado modernos; el algoritmo de Grover acelera la búsqueda en bases de datos no ordenadas; la computación cuántica promete avances en la simulación de materiales y medicamentos.
El problema de Simon (búsqueda de una regularidad oculta en una caja negra), resuelto exponencialmente rápido por un ordenador cuántico, inspiró directamente a Peter Shor para crear el algoritmo de factorización: descomponer un número en factores primos.






















