Introducción
Los algoritmos cuánticos ofrecen ventajas demostrables sobre los algoritmos clásicos en el modelo de consulta de la computación. Pero, ¿qué ocurre con un modelo de computación más estándar, en el que las instancias del problema se proporcionan explícitamente y no en forma de un oráculo o caja negra? Esto resulta ser una pregunta mucho más difícil, y para abordarla debemos primero establecer una base sólida para nuestra investigación. Ese es precisamente el propósito principal de esta lección.
Comenzamos discutiendo los costos computacionales — tanto para la computación clásica como para la cuántica — y cómo pueden medirse. Este es un concepto general que puede aplicarse a una amplia variedad de problemas computacionales — pero por simplicidad lo consideramos principalmente a través del prisma de la teoría algorítmica de números, que se ocupa de tareas computacionales que deberían resultar familiares a la mayoría de los lectores: aritmética básica, cálculo del máximo común divisor y factorización de enteros. Aunque la teoría algorítmica de números es un campo de aplicación estrecho, estos problemas son buenos para ilustrar las cuestiones fundamentales (y resultan ser muy relevantes para la lección siguiente).
Nuestro enfoque está en los algoritmos y no en el hardware en constante mejora sobre el que se ejecutan. En consecuencia, nos interesa menos cuántos segundos, minutos u horas requiere un cálculo particular, y más cómo escala el costo de ejecutar un algoritmo a medida que las instancias del problema para las que se ejecuta se hacen más grandes. Nos enfocamos en este aspecto del costo computacional reconociendo que los algoritmos son de importancia fundamental y que, con hardware cada vez más potente y fiable, se aplican naturalmente a instancias de problemas cada vez más grandes.
Finalmente, nos dirigimos a una tarea de importancia crítica: ejecutar cálculos clásicos en computadoras cuánticas. Esta tarea no es importante porque esperemos reemplazar las computadoras clásicas por computadoras cuánticas — lo cual parece extremadamente improbable en un futuro previsible, si es que ocurre —, sino porque abre muchas posibilidades interesantes para los algoritmos cuánticos. Concretamente, los cálculos clásicos que se ejecutan en computadoras cuánticas están disponibles como subrutinas, lo que permite aprovechar décadas de investigación y desarrollo en algoritmos clásicos para obtener ventajas cuánticas.
Video de la lección
En el siguiente video, John Watrous recorre el contenido de esta lección sobre los fundamentos algorítmicos de la computación cuántica. Alternativamente, puedes abrir el video de YouTube de esta lección en una ventana separada. Descargar diapositivas de esta lección.