Curso electivo: CB120 Fundamentos de Computación Cuántica

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

  1. Texto Guía: Chuang and Nielsen (2000).

  2. Textos introductorios: Chuang and Nielsen (2000), Gruska (1999) y Williams and Clearwater (1997).

  3. Artículos introductorios: Rieffel and Polak (2000), Shor (2000), Sicard and Vélez (1999) y Vélez Ruiz and Sicard Ramírez (1999).

Introducción

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.

Prerrequisitos, intensidad semanal y número de créditos

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.

Programa propuesto

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

  1. Observar la computaciónn cuántica desde los postulados de la mecánica cuántica.

  2. Desarrollar habilidades para la manipulación formal de los elementos involucrados en la computación cuántica.

  3. Establecer relaciones entre la computación cuántica y las interpretaciones de la tesis de Church-Turing.

  4. Manipular los algoritmos de Shor y de Grover y sus implementaciones en diferentes simuladores de computación.

  5. 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

  1. Introducción a la computación cuántica (Rieffel and Polak 2000; Williams and Clearwater 1997; Shor 2000). Duración 4 horas.

  2. Cuántica y computación: una aproximación desde los postulados de la mecánica cuántica (Cohen-Tannoudji, Diu, and Laloë 1997; Dirac 1967; Vélez Ruiz and Sicard Ramírez 1999; Sicard Ramírez, Puerta Yepes, and Vélez Ruiz 1998). Duración 6 horas.

  3. 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, and Pérez 2002).

    3.4. Transformada cuántica de Fourier.

  4. 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

  5. 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).

  6. 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 and 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 and Vélez Ruiz 1999; Sicard 2001).

    6.5. Computación cuántica continua (Sicard Ramírez and Vélez Ruiz 2000; Vélez and Sicard 2000).

    6.6. Computación cuántica geométrica (Vélez Ruiz and Sicard Ramírez 2001–2002; Vélez Ruiz and Sicard Ramírez 2002–2003).

Profesores

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.

Referencias

Chuang, Isaac L., and Michael A. Nielsen. 2000. Quantum computation and quantum information. Cambridge University Press.
Cohen-Tannoudji, Claude, Bernard Diu, and Franck Laloë. 1997. Quantum mechanics. Vol. 1. Hermann; John Wiley; Sons.
Dirac, P. A. M. 1967. Principios de mecánica cuántica. Ediciones Arial.
DiVincenzo, David P. 2000. The physical implementation of quantum computation. Fortschr. Phys. 48, no. 9–11: 771–83.
Grover, Lov K. 1996. A fast quantum mechanical algorithm for database search. Proceedings of the twenty-eighth annual ACM symposium on theory of computing (STOC ’96).
---. 2001. From schrödinger’s equation to the quantum search algorithm.
Gruska, Jozef. 1999. Quantum computing. McGraw-Hill International (UK) Limited.
Rieffel, Eleanor, and Wolfgang Polak. 2000. An introduction to quantum computing for non-physicists. ACM Computing Surveys 32, no. 3: 300–335. doi:10.1145/367701.367709.
Shor, Peter W. 1997. Polinomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing 26, no. 5: 1484–1509. doi:10.1137/S0097539795293172.
---. 2000. Introduction to quantum algorithms.
Sicard, Andrés. 2001. Autorreferencia en el contexto de las máquinas de Turing cuánticas. Talk.
Sicard, Andrés, and Mario Vélez. 1999. Algunos elementos introductorios acerca de la computación cuántica. Talk.
Sicard, Andrés, Mario Vélez, and Carlos Pérez. 2002. Paralelismo cúantico: El problema de Deutsch. Silicio 1, no. 14: 42–47.
Sicard Ramírez, Andrés, María Eugenia Puerta Yepes, and Mario Elkin Vélez Ruiz. 1998. Lenguaje subyacente a la noción de máquina cuántica.
Sicard Ramírez, Andrés, and Mario Elkin Vélez Ruiz. 1999. ¿Máquina de Turing cuántica autorrefencial: Una posibilidad?
---. 2000. Prototipo de un modelo de computación cuántica continua.
Vélez, Mario, and Andrés Sicard. 2000. Computación cuántica: Una perspectiva desde lo continuo. Revista Universidad EAFIT 36, no. 118: 41–46.
Vélez Ruiz, Mario Elkin, and Andrés Sicard Ramírez. 2001–2002. Computación cuántica geométrica.
---. 2002–2003. Computación cuántica geométrica no abeliana.
Vélez Ruiz, Mario E., and Andrés Sicard Ramírez. 1999. Cuántica y computación: Una aproximación desde los postulados de la mecánica cuántica.
---. 2000. Sobre algunos modelos de implementación para la computación cuántica.
Volovich, I. V. 2000. Quantum computing and Shor’s factoring algorithm.
Williams, Colin P., and Scott H. Clearwater. 1997. Explorations in quantum computing. Springer-Telos.