Un algoritmo cuántico es una receta de puertas que usa la interferencia para hallar una respuesta con menos pasos que cualquier método clásico conocido, en ciertos problemas. La ventaja rara vez es universal: algunos algoritmos son exponencialmente más rápidos, otros solo cuadráticamente, y muchos problemas no ganan nada. Saber cuál es cuál es la destreza.
Conceptos clave
- Problemas con oráculo: Deutsch-Jozsa, Bernstein-Vazirani y Simon muestran aceleraciones en un modelo limpio donde se consulta una caja negra.
- Transformada cuántica de Fourier: un cambio de base rápido que revela la periodicidad; es el corazón del algoritmo de Shor.
- Algoritmo de Shor: halla el periodo oculto tras la factorización de enteros y los logaritmos discretos, lo que amenaza a parte de la criptografía de clave pública.
- Búsqueda de Grover: una aceleración cuadrática para la búsqueda sin estructura, que amplifica una y otra vez el elemento marcado.
- Métodos variacionales y de simulación: simulación cuántica de sistemas físicos y bucles híbridos que ajustan de forma clásica los parámetros de un circuito.
Vocabulario
- Complejidad de consultas: el número de llamadas a un oráculo que necesita un algoritmo.
- Amplificación de amplitud: la generalización de la idea de Grover para subir la probabilidad de los resultados buenos.
- BQP: los problemas que una computadora cuántica resuelve en tiempo polinómico con error pequeño.
- Criptografía poscuántica: esquemas clásicos diseñados para resistir los ataques cuánticos conocidos.
Qué estudiar, en orden
- Los circuitos cuánticos y la medición, y el álgebra lineal que usan.
- Implementa Deutsch-Jozsa y Bernstein-Vazirani en un simulador y mira por qué la interferencia da la respuesta.
- Trabaja la búsqueda de Grover con cuatro y con ocho elementos, y cuenta las iteraciones.
- Aprende la transformada cuántica de Fourier y luego la estimación de fase.
- Sigue el algoritmo de Shor: la reducción clásica a la búsqueda del periodo y después el paso cuántico.
Etiquetas relacionadas
#quantum-computing #complexity #cryptography #algorithms #linear-algebra