Introducción

En esta primera lección del curso, formularemos un marco algorítmico sencillo -conocido como modelo de consulta- y exploraremos las ventajas que ofrecen los ordenadores cuánticos dentro de este marco.

El modelo de consulta de la computación es como una placa de Petri para las ideas algorítmicas cuánticas. Es rígido y antinatural en el sentido de que no representa con exactitud el tipo de problemas computacionales que suelen interesarnos en la práctica, pero sin embargo ha demostrado ser increíblemente útil como herramienta para desarrollar técnicas algorítmicas cuánticas. Esto incluye los que hacen funcionar los algoritmos cuánticos más conocidos, como el algoritmo de Shor para la factorización de enteros. El modelo de consulta también resulta ser un marco muy útil para explicar las técnicas algorítmicas cuánticas.

Después de introducir el modelo de consulta en sí, hablaremos del primer algoritmo cuántico que se descubrió, que es el algoritmo de Deutsch, junto con una extensión del algoritmo de Deutsch conocida como el algoritmo de Deutsch-Jozsa. Estos algoritmos demuestran ventajas cuantificables de los ordenadores cuánticos sobre los clásicos en el contexto del modelo de consulta. A continuación, hablaremos de un algoritmo cuántico conocido como algoritmo de Simon, que ofrece una ventaja más sólida y satisfactoria de los cálculos cuánticos sobre los clásicos, por razones que se explicarán cuando lleguemos a él.

Vídeo de la lección

En el siguiente vídeo, John Watrous le guía a través del contenido de esta lección sobre algoritmos de consulta cuántica. También puede abrir el vídeo YouTube de esta lección en una ventana aparte. Descargue las diapositivas de esta lección.