PDF de programación - Simulación de Cómputo Cuántico

CENTRO DE INVESTIGACIÓN Y DE ESTUDIOS AVANZADOS

DEL INSTITUTO POLITÉCNICO NACIONAL

DEPARTAMENTO DE COMPUTACIÓN

Simulación de Cómputo Cuántico

Tesis que presenta

Mireya Paredes López

Para obtener el grado de

Maestro en Ciencias

En la especialidad de

Computación

Director de la Tesis: Dr. Guillermo B. Morales Luna

México, D. F., a 10 de Enero del 2007.

Dedico esta tesis a la memoria de mi hermana “Livis”.

II

Agradecimientos

Agradecimientos

III

Este logro ha sido producto del esfuerzo de muchas personas e instituciones, a quie-

nes quiero agradecer el gran apoyo que me brindaron durante los últimos años.

Quiero expresar mi agradecimiento al CINVESTAV y muy particularmente a todos
los investigadores del ahora Departamento de Computación. Primero por darme la
oportunidad de colaborar con ustedes y segundo por haberme puesto los retos necesa-
rios para demostrar mi capacidad.

Sin el apoyo económico del Consejo Nacional de Ciencia y Tecnología (CONACyT)
no me hubiera sido posible dedicarme de tiempo completo a mis estudios de maestría,
por lo que le agradezco el gran interés en formar profesionistas que como yo están
interesados en hacer de México un país cada vez mejor.

Otro gran apoyo económico que recibí fue por parte del Consejo Mexiquense de
Ciencia y Tecnología (COMECyT) mediante la Beca-Tesis promoción 2006. Con esta
beca pude completar mis estudios, por lo que agradezco plenamente al Estado de Mé-
xico por apoyar y financiar el avance tecnológico de la entidad.

Sin duda alguna, agradezco la guía de mi asesor Guillermo Morales. Sus consejos,

observaciones y pláticas amenas me hicieron conocer la gran persona que es.

Una persona a quien debo agradecerle su colaboración en esta tesis es al Dr. Carlos
Rentería, profesor de ESFM, quien me ayudó a encontrar una solución a un problema
importante en este trabajo (toma de mediciones). Sus conocimientos y habilidades con
las matemáticas fueron la clave principal.

Agradezco todo el apoyo incondicional a Amilcar, quien siempre estuvo al tanto del
trabajo. Los días que me tuve que levantar temprano, él lo hizo, los días que me tuve
que quedar tarde, él se quedó tarde. Su motivación constante fue lo que me mantuvo
firme en todo momento.

Un especial agradecimiento al excelente profesor Rafael Baquero, quien con toda la
paciencia del mundo me enseñó una nueva forma de ver la vida. Espero en el futuro
fungir como su servidora y con un granito de arena poder ayudar a materializar sus
sueños.

Quiero nombrar a mis amigos Noel Ramírez, mejor conocido como el “troll”, e Israel
Vite, a quienes admiro y respeto por la paciencia que me han tenido y quienes además
sé que no son compañeros de viaje sino amigos para toda la vida.

Agradezco a todos mis compañeros de viaje por su amistad y compañerismo, quie-
nes hicieron más placentera mi estancia en el CINVESTAV, especialmente a Edna, a
Gildardo, a Jorge, a Francisco, a Leonor y a Héctor. Todavía recuerdo las horas de ten-
sión para pasar cierta materia.

Indiscutiblemente Sofia es la secretaria más simpática y eficiente que he conocido,

por ello, quiero agradecerle todo el soporte que me brindó durante mi estancia.

Definitivamente quiero agradecer a mis padres, quienes no siempre estuvieron de
acuerdo con mi decisión, pero aún así siempre la respetaron. La presencia de ellos y la
de mis hermanos siempre fue suficiente para continuar con el siguiente día.

Finalmente, quiero mencionar a mi gran amigo, compañero y amante Mario Augus-

to, a quien le debo todo.

IV

Agradecimientos

Índice general

Índice de Figuras

Índice de Tablas

Índice de Algoritmos

Resumen

Abstract

Introducción

1. Un vistazo a la computación cuántica

.

1.1. Antecedentes
. .
1.2. Conceptos generales

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
.
1.2.1. Bits cuánticos .
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
.
1.2.2. Registros cuánticos . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2.3. Toma de mediciones . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2.4. Compuertas cuánticas . . . . . . . . . . . . . . . . . . . . . . . . .
1.2.5. Algoritmos cuánticos . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2.6. Paralelismo cuántico . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3. Algoritmo cuántico de Deutsch-Jozsa . . . . . . . . . . . . . . . . . . . .

2. Diseño de un lenguaje de programación cuántica: GAMA

2.1. Características de GAMA . . . . . . . . . . . . . . . . . . . . . . . . . . . .
.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2. Entidades cuánticas .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
.
.
.
2.2.1. Escalares .
.
.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
.
2.2.2. Vectores .
2.2.3. Matrices . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. .
2.2.4. Operaciones mixtas . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3. Definición del lenguaje de programación . . . . . . . . . . . . . . . . . .
2.3.1. Analizador léxico . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3.2. Analizador sintáctico . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3.3. Análisis semántico . . . . . . . . . . . . . . . . . . . . . . . . . . .

3. El intérprete

3.1. La máquina de instrucciones . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.1. Componentes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

VIII

X

XIII

1

2

3

7
7
10
10
11
12
12
15
15
16

19
20
20
21
21
22
22
23
23
25
35

39
39
40

VI

ÍNDICE GENERAL

. .

. .

3.2. Esquema general del intérprete . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3. Fase de análisis
3.4. Fase de ejecución . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.5. Tabla de símbolos . .
3.5.1. Tipos de símbolos . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.5.2. Manejo de la tabla de símbolos . . . . . . . . . . . . . . . . . . . .
3.5.3. Ámbito de las variables . . . . . . . . . . . . . . . . . . . . . . . .
3.6. Manejador de errores .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.7. Descripción de las clases CQregister y CQgate . . . . . . . . . . . . . . . .
3.7.1. La clase CQregister . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.7.2. La clase CQgate . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.8.1. Discusión de la factorización . . . . . . . . . . . . . . . . . . . . .
3.8.2. Algoritmo de medición mediante la factorización de qubits
. . .
3.8.3. Conclusiones de la medición . . . . . . . . . . . . . . . . . . . . .

3.8. Toma de medición .

.

.

4. Entorno de simulación

4.1.

. . . . . . . . . . . . . . . . . . . . . . . . . . . .
Integración del entorno .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.1.1. La edición . .
4.1.2. La ejecución .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.1.3. La depuración . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2.1.
Interfaz de usuario . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2.2. El núcleo del depurador . . . . . . . . . . . . . . . . . . . . . . . .
4.2.3. Formato de mensajes . . . . . . . . . . . . . . . . . . . . . . . . . .

. .

.

.

.

4.2. El depurador .

5. Pruebas de efectividad

5.1.1. El operador Uf
5.1.2. Pseudocódigo .

5.1. Algoritmo de Deutsch-Jozsa . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
.
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2. Simulación en GAMA . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.3. Resultado .

. .

.

.

.

.

.

6. Resultados y conclusiones
. .
. .
. .

.
.
6.1. Resultados .
.
6.2. Conclusiones . .
. .
6.3. Trabajo a futuro . .

.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

A. Listado de componentes léxicos

B. Gramática de GAMA

C. Tablas de conversiones de tipos

D. Prueba del algoritmo de Deutsch-Jozsa

Bibliografía

40
41
41
44
44
46
46
47
48
48
48
49
50
52
58

61
61
62
63
64
65
66
67
69

71
71
73
75
76
76

81
81
83
83

85

89

93

95

96

ÍNDICE GENERAL

VII

VIII

ÍNDICE GENERAL

Índice de figuras

1.1. Flujo de un algoritmo cuántico básico.
. . . . . . . . . . . . . . . . . . . .
1.2. Circuito cuántico para la evaluación de f (x) simultáneamente. Acepta
entradas como |x, yi y las transforma al estado x, y ⊕ f (x) . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . . . .

2.1. Componentes principales en la definición de GAMA.
2.2.

Interacción del analizador léxico con el sintáctico.

3.1. Esquema general del intérprete. . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . .
3.2. Máquina de instrucciones para la estructura while.
3.3. Máquina de instrucciones para la estructura if-else.
. . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . .
3.4. Estructura de un símbolo.
3.5. Ámbito de variables globales y locales. . . . . . . . . . . . . . . . . . . . .
3.6. Relación de los coeficientes bk’s del polinomo P con γij.
. . . . . . . . . .

Interfaz gráfica multidocumentos.

clase de vista y la clase controladora.

4.1. Modelo MVC, mostrando la interacción entre la clase modeladora, la
. . . . . . . . . . . . . . . . . . . .
4.2. Arquitectura Modelo-Vista de Qt.
. . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . .
4.3.
4.4. Proceso de comunicación entre la interfaz gráfica y el proceso intérprete.
4.5. Vista de un programa en depuración.
. . . . . . . . . . . . . . . . . . . .
5.