¡Esta página será actualizada continuamente durante el semestre!
Reunión informativa: Miercóles 27 de
Noviembre, a las 2:00 p.m., en el aula 14-406.
Semestre: 2003-01
Nombre
materia: Fundamentos de computación cuántica
Código: CB120
Horario: Se
concertará con los estudiantes matriculados
Observación: En el contenido del curso para el
semestre 2003-01, se ha hecho especial enfásis en el tema
relacionado con los simuladores de computación cuántica, tal como
se puede observar en el contenido del curso.
Cualquier inquietud o sugerencia puede ser enviada a:
Andrés Sicard Ramírez. Email: asr (at) eafit (dot) edu (dot) co. Oficina: Bloque 3-206.
Mario Elkin Vélez Ruiz. Email: mvelez (at) eafit (dot) edu (dot) co. Oficina: Bloque 3-210.
Material
Texto Guía: Chuang y Nielsen (2000).
Textos introductorios: Chuang y Nielsen (2000), Gruska (1999) y Williams y Clearwater (1997).
Artículos introductorios: Rieffel y Polak (2000), Shor (2001), Sicard y Vélez (1999) y Vélez Ruiz y Sicard Ramírez (1999).
Los esquemas mentales que exige la nueva física para su comprensión, no son comparables a los de la física clásica, donde cada situación es representable por una imagen mental claramente intuible en el terreno de lo causal-determinista. Dadas las condiciones iniciales de un sistema, es posible saber con toda precisión la evolución del mismo, debido a que su comportamiento es expresable como un sistema de ecuaciónes diferenciales lineales y hasta cierto punto, es posible conocer sus múltiples relaciones con otros objetos. Contrariamente a esa imagen del mundo, la física moderna, en particular la mecánica cuántica, no permite esa estructuración; la intuición causal-determinista es remplazada por la intuición probabilista. Los eventos no se desenvuelven en el terreno del determinismo clásico sino más bién, en una suerte de evoluciones probabilistas.
Las máquinas de Turing cuánticas y los circuitos cuánticos son un modelo de la computación, tal como lo son las máquinas de Turing, las funciones recursivas y el λ-cálculo, entre otros. Estos modelos se inscriben dentro de un área conocida como computación cuántica, y como su nombre lo indica, hacen uso de las propiedades y efectos considerados por la mecánica cuántica. Esta área fue inicialmente sugerida por Richard Feymman en los años 80, formalizada por David Deutsch, en la forma de máquinas de Turing cuánticas en 1985 y en la forma de circuitos cuánticos en 1989 y demostrada su potencialidad por Peter Shor en 1994.
El trabajo de Shor señalo el aspecto fundamental en el cual se diferencian la computación clásica y la computación cuántica: la complejidad algorítmica. Esta diferencia consiste en que es posible definir algoritmos cuánticos cuya complejidad temporal sea menor que sus análogos clásicos (conocidos hasta el momento). En particular Shor realizó la descripción de un algoritmo cuántico de complejidad temporal polinómica para la factorización de números enteros.
Se espera que los estudiantes hayan visto los cursos de Álgebra Lineal y Matemáticas Especiales III.
El curso se ofrecerá bajo la modalidad de curso magistral, es decir, el curso tendra una intensidad semanal de 4 horas durante 15 semanas. En caso de ser necesario (de acuerdo al número de estudiantes matriculados) el curso se redefinirá como un curso dirigido, es decir, el curso tendra una intensidad de 2 horas semanales durante 15 semanas.
El curso será considerado como un curso de 4 créditos de libre configuración para los estudiantes que se matriculen formalmente en él.
Objetivo general
Comprender los modelos de computación cuántica con base en sus fundamentos matemáticos, físicos e informáticos.
Objetivos específicos
Observar la computaciónn cuántica desde los postulados de la mecánica cuántica.
Desarrollar habilidades para la manipulación formal de los elementos involucrados en la computación cuántica.
Establecer relaciones entre la computación cuántica y las interpretaciones de la tesis de Church-Turing.
Manipular los algoritmos de Shor y de Grover y sus implementaciones en diferentes simuladores de computación.
Adquirir elementos conceptuales en diferentes tópicos relacionados con la computación cuántica tales como: implementación de máquinas cuánticas, criptografía cuántica, teleportación, correción de errores, computación cuántica autorrefencial, computación cuántica continua, etc.
Contenidos
Introducción a la computación cuántica (Rieffel y Polak 2000; Williams y Clearwater 1997; Shor 2001). Duración 4 horas.
Cuántica y computación: una aproximación desde los postulados de la mecánica cuántica (Cohen-Tannoudji, Diu, y Laloë 1997; Dirac 1967; Vélez Ruiz y Sicard Ramírez 1999; Sicard Ramírez, Puerta Yepes, y Vélez Ruiz 1998). Duración 6 horas.
Circuitos cuánticos. Duración 14 horas.
3.1. Qubit, qubits, operadores de evolución, medidad cuánticas, compuertas cuánticas, construcción de circuitos cuánticos.
3.2. Reversivilidad y estados enredados (entanglement).
3.3 Paralelismo cuántico: problema de Deutsch (Sicard, Vélez, y Pérez 2002).
3.4. Transformada cuántica de Fourier.
Programación cuántica. Duración 12 horas.
4.1. QCL - A Programming Language for Quantum Computers
4.2. jaQuzzi - Interactive Quantum Computation
4.3. QCE - Quantum Computer Emulator
4.4. QuCalc: A Quantum Computation Package for Mathematica 4.0
4.5. Otros lenguajes
Algoritmos cuánticos. Duración 12 horas.
5.1. Algoritmo de Shor: factorización de un número entero en sus factores primos (Shor 1997; Volovich 2000).
5.2. Algoritmo de Grover: busqueda en una base de datos desorganizada (Grover 1996; Grover 2001).
Tópicos relacionados con la computación cuántica. Duración 10 horas.
6.1. Implementación de máquinas cuánticas (DiVincenzo 2000; Vélez Ruiz y Sicard Ramírez 2000).
6.2. Criptografía cuántica.
6.3. Correción de errores.
6.4. Computación cuántica autorrefencial (Sicard Ramírez y Vélez Ruiz 1999; Sicard 2001).
6.5. Computación cuántica continua (Sicard Ramírez y Vélez Ruiz 2000; Vélez y Sicard 2000).
6.6. Computación cuántica geométrica (Vélez Ruiz y Sicard Ramírez 2001–2002; Vélez Ruiz y Sicard Ramírez 2002–2003).
Andrés Sicard Ramírez y Mario Elkin Vélez Ruiz, miembros del grupo de Lógica y Computación y profesores del Departamento de Ciencias Básicas de la Universidad EAFIT.
Chuang, Isaac L. y Nielsen, Michael A. (2000). Quantum Computation and Quantum Information. Cambridge University Press.
Cohen-Tannoudji, Claude, Diu, Bernard y Laloë, Franck (1997). Quantum Mechanics. Vol. 1. Hermann, John Wiley y Sons.
Dirac, P. A. M. (1967). Principios de Mecánica Cuántica. Ediciones Arial.
DiVincenzo, David P. (2000). The Physical Implementation of Quantum Computation. En: Fortschritte der Physik 48.9–11, págs. 771-783. [ DOI ].
Grover, Lov K. (1996). A Fast Quantum Mechanical Algorithm for Database Search. En: Proceedings of the Twenty-eighth Annual ACM Symposium on Theory of Computing (STOC ’96), págs. 212-219. [ DOI ].
Grover, Lov K. (2001). From Schrödinger’s Equation to the Quantum Search Algorithm. En: Pramana—Journal of Physics 56.2, págs. 333-348. [ DOI ].
Gruska, Jozef (1999). Quantum Computing. McGraw-Hill International (UK) Limited.
Rieffel, Eleanor y Wolfgang Polak (2000). An Introduction to Quantum Computing for Non-Physicists. En: ACM Computing Surveys 32.3, págs. 300-335. [ DOI ].
Shor, Peter W. (1997). Polinomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. En: SIAM Journal on Computing 26.5, págs. 1484-1509. [ DOI ].
Shor, Peter W. (2001). Introduction to Quantum Algorithms. [ arXiv ].
Sicard, Andrés (2001). Autorreferencia en el Contexto de las Máquinas de Turing Cuánticas. Talk. V Evento Internacional de Matemáticas y Computación (COMAT). Universidad de Matanzas, Cuba. Noviembre 12–16. [ pdf ]
Sicard, Andrés y Vélez, Mario (1999). Algunos Elementos Introductorios Acerca de la Computación Cuántica. Talk. VII Encuentro ERM. Universidad de Antioquia, Medellı́n. Agosto 23–27. [ pdf ]
Sicard, Andrés, Vélez, Mario y Pérez, Carlos (2002). Paralelismo Cúantico: El Problema de Deutsch. En: Silicio 1.14, págs. 42-47. [ pdf ]
Sicard Ramı́rez, Andrés, Puerta Yepes, Marı́a Eugenia y Vélez Ruiz, Mario Elkin (1998). Lenguaje Subyacente a la Noción de Máquina Cuántica. Universidad EAFIT. Grant: 817405. [ pdf]
Sicard Ramı́rez, Andrés y Vélez Ruiz, Mario Elkin (1999). ¿Máquina de Turing Cuántica Autorrefencial: Una Posibilidad? Universidad EAFIT. Grant: 817407. [ tar.gz ]
Sicard Ramı́rez, Andrés y Vélez Ruiz, Mario Elkin (2000). Prototipo de un Modelo de Computación Cuántica Continua. Universidad EAFIT. Grant: 817424. [ tar.gz]