T 2902

•

SIN SIGLA

INGENIERO MILLONARIO.

25/4/2024

¡Este material tiene más páginas!

Entonces, ¿te gustó este material?

Ayude a animar a otros estudiantes a mejorar el contenido

¿Te gustó este material? ¡Compartir! 🧡

Algoritmos y Programación

4288 Materiales compartidos

Descarga la aplicación para disfrutar aún más

Lea materiales sin conexión, sin usar Internet. Además de muchas otras características!

Vista previa del material en texto

UNIVERSIDAD MAYOR DE SAN ANDRÉS

FACULTAD DE CIENCIAS PURAS Y NATURALES
CARRERA DE INFORMÁTICA

TESIS DE GRADO
“ANÁLISIS COMPARATIVO ENTRE UN ALGORITMO
CUÁNTICO Y UN ALGORITMO CLÁSICO APLICADO A
LA COMPRESIÓN DE INFORMACIÓN”

PARA OPTAR AL TÍTULO DE LICENCIATURA EN INFORMÁTICA
MENCIÓN INGENIERÍA DE SISTEMAS INFORMÁTICOS

POSTULANTE: Luis Alvaro Nina Chura
TUTOR METODOLÓGICO: M. Sc. Miguel Cotaña Mier
REVISOR: Lic. Grover Alex Rodriguez Ramirez

LA PAZ - BOLIVIA
2014

UNIVERSIDAD MAYOR DE SAN ANDRÉS
FACULTAD DE CIENCIAS PURAS Y NATURALES
CARRERA DE INFORMÁTICA

LA CARRERA DE INFORMÁTICA DE LA FACULTAD DE CIENCIAS PURAS Y
NATURALES PERTENECIENTE A LA UNIVERSIDAD MAYOR DE SAN ANDRÉS
AUTORIZA EL USO DE LA INFORMACIÓN CONTENIDA EN ESTE
DOCUMENTO SI LOS PROPÓSITOS SON ESTRICTAMENTE ACADÉMICOS.

LICENCIA DE USO

El usuario está autorizado a:

a) visualizar el documento mediante el uso de un ordenador o dispositivo móvil.
b) copiar, almacenar o imprimir si ha de ser de uso exclusivamente personal y privado.
c) copiar textualmente parte(s) de su contenido mencionando la fuente y/o haciendo la
referencia correspondiente respetando normas de redacción e investigación.

El usuario no puede publicar, distribuir o realizar emisión o exhibición alguna de este
material, sin la autorización correspondiente.

TODOS LOS DERECHOS RESERVADOS. EL USO NO AUTORIZADO DE LOS
CONTENIDOS PUBLICADOS EN ESTE SITIO DERIVARA EN EL INICIO DE
ACCIONES LEGALES CONTEMPLADOS EN LA LEY DE DERECHOS DE AUTOR.

Dedicado:
A mi madre, por apoyarme
en momentos difíciles y
siempre confiar en mí.

AGRADECIMIENTOS
A mis padres.
A todos los docentes que compartieron su conocimiento a lo largo
de estos años de estudio.
A mi revisor Lic. Grover Alex Rodriguez Ramirez y tutor M. Sc.
Miguel Cotaña Mier por su paciencia, compresión y tiempo
supervisando el presente trabajo.

Luis Alvaro Nina Chura

ÍNDICE ESPECÍFICO

1. Marco Referencial .....................................................................................................13
1.1. Introducción ................................................................................................................. 13
1.2. Antecedentes ............................................................................................................... 14
1.3. Planteamiento del Problema ......................................................................................... 15
1.4. Formulación del Problema ............................................................................................ 16
1.5. Hipótesis ....................................................................................................................... 16
1.6. Identificación de Variables.........................................................................................16
1.6.1. Variable Dependiente..........................................................................................16
1.6.2. Variable Independiente .......................................................................................16
1.6.3. Operacionalización de variables ..........................................................................16
1.7. Objetivos ...................................................................................................................... 17
1.7.1. Objetivo General ....................................................................................................... 17
1.7.2. Objetivos Específicos ................................................................................................. 17
1.8. Justificación .................................................................................................................. 17
1.8.1. Técnica ...............................................................................................................17
1.8.2. Social..................................................................................................................17
1.8.3. Práctica ...............................................................................................................17
1.8.4. Económica ..........................................................................................................18
1.9. Limites y Alcances ....................................................................................................18
1.10. Diseño Metodológico ..........................................................................................18
2. Marco Teórico ...........................................................................................................20
2.1. Fundamentos de la mecánica cuántica .......................................................................... 20
2.1.1. Dualidad Onda Partícula ............................................................................................ 20
2.1.2. El Experimento De La Doble Ranura .......................................................................... 20
2.1.3. Principio De Incertidumbre De Heisemberg ............................................................... 20
2.1.4. Postulados ................................................................................................................ 21
2.1.5. El Gato De Schrödinger ............................................................................................. 23
2.1.6. Entrelazamiento cuántico ......................................................................................... 24
2.1.7. La Paradoja EPR ........................................................................................................ 25

2.1.8. Cuantificación del entrelazamiento ........................................................................... 26
2.1.9. Estados de Bell .......................................................................................................... 26
2.1.10. Algoritmos Cuánticos ................................................................................................ 27
2.1.10.1. Algoritmo de Deutsch............................................................................................ 27
2.1.10.2. Algoritmo Deutsch-Jozsa ....................................................................................... 28
2.1.10.3. La Transformada Cuántica de Fourier .................................................................... 28
2.1.10.4. Algoritmo de Factorización de Shor ....................................................................... 30
2.1.10.5. Algoritmo de Grover ............................................................................................. 32
2.2. Conceptos Básicos ........................................................................................................ 35
2.2.1. Espacios de Hilbert .................................................................................................... 37
2.2.2. El Qbit ....................................................................................................................... 38
2.2.3. Representación y medición del estado de un Qbit ..................................................... 39
2.2.4. Definición de la esfera de Bloch ................................................................................ 40
2.2.5. Múltiples Qbits ......................................................................................................... 42
2.2.6. Puertas cuánticas ...................................................................................................... 43
2.2.6.1. Compuertas cuánticas para un qubit ..................................................................... 43
a) Puerta de Identidad ......................................................................................................43
b) Puerta Hadamard.......................................................................................................... 44
c) Puertas de Pauli ............................................................................................................ 44
d) Puerta Cambio de Fase ................................................................................................. 45
e) Puerta ..................................................................................................................... 45
2.2.6.2. Puertas cuánticas para dos qbits ........................................................................... 45
2.2.7. Reversibilidad ........................................................................................................... 45
2.2.8. Puertas Reversibles ................................................................................................... 46
2.2.8.1. CNOT .................................................................................................................... 46
2.2.8.2. Toffoli ................................................................................................................... 47
2.2.8.3. Fredkin .................................................................................................................. 47
2.2.9. Teorema de no clonación .......................................................................................... 48
2.3. Computación cuántica .................................................................................................. 49
2.4. Computador cuántico ................................................................................................... 50

2.5. Entropía ........................................................................................................................ 50
2.6. Información clásica ....................................................................................................... 50
2.6.1. Entropía de Shannon ................................................................................................. 50
2.6.2. Codificación .............................................................................................................. 51
2.6.3. Compresión de datos ................................................................................................ 52
2.6.3.1. Compresión sin perdida......................................................................................... 52
a) Compresores Estadísticos ............................................................................................. 53
Compresor Shannon-Fano............................................................................................. 53
Compresor Huffman ..................................................................................................... 54
Compresores Aritméticos .............................................................................................. 55
b) Compresores Basados en Diccionario ............................................................................ 56
Compresión RLE ............................................................................................................ 56
Compresión LZ77 .......................................................................................................... 57
Compresión LZSS .......................................................................................................... 57
Compresión LZ78 .......................................................................................................... 57
Compresión LZW........................................................................................................... 58
2.6.3.2. Compresión con perdida ....................................................................................... 58
a) Compresión de imágenes: JPEG .................................................................................... 59
b) Compresión de video: MPEG ......................................................................................... 60
2.7. Información cuántica .................................................................................................... 61
2.7.1. Operador de densidad .............................................................................................. 61
2.7.2. Medición de la matriz de densidad ............................................................................ 62
2.7.3. Entropía de Von Neumann ........................................................................................ 63
2.7.4. Codificación de fuente .............................................................................................. 64
2.7.4.1. Codificación de estados puros. Teorema de Schumacher....................................... 64
2.7.4.2. Codificación de mezclas estadísticas. Información de Holevo ................................ 65
2.8. Codificación superdensa ............................................................................................... 66
2.9. Metodología de desarrollo ............................................................................................ 67
2.9.1. Procedimiento del diseño ......................................................................................... 67
2.9.2. Diagrama de las estructuras de datos ........................................................................ 67

3. Diseño metodológico .................................................................................................69
3.1. Comparación formal ..................................................................................................69
3.2. Descripción del algoritmo propuesto ..........................................................................72
3.3. Desarrollo de Software ..............................................................................................76
3.3.1. Diagrama general ...................................................................................................... 76
3.3.2. Fase 1 (entradas, salidas) .......................................................................................... 78
3.3.2.1. Submódulo leerArhivos ......................................................................................... 79
3.3.2.2. Submódulo codificarHuffman ................................................................................ 79
3.3.2.3. Submódulo codificarArchivos ................................................................................ 80
3.3.3. Fase 2 (Diagramas Jackson) ....................................................................................... 83
3.3.3.1. Submódulo leerArchivos ....................................................................................... 86
3.3.3.2. Submódulo codificarHuffman ................................................................................ 87
3.3.3.3. Submódulo codificarArchivos ................................................................................ 87
3.3.4. Fase 3 (Implementación: diagramas de flujo) ............................................................ 92
3.3.4.1. Submódulos leerArchivo ....................................................................................... 95
3.3.4.2. Submódulos codificarHuffman .............................................................................. 96
3.3.4.3. Sub módulos codificarArchivos .............................................................................. 97
3.3.5. Implementación: Pseudocódigo .............................................................................. 105
3.3.5.1. Submódulos leerArchivos .................................................................................... 107
3.3.5.2. Submódulos codificarHuffman ............................................................................ 108
3.3.5.3. Submódulo codificarArchivos ..............................................................................108
4. Presentación y análisis de resultados ........................................................................ 114
4.1. Diseño experimental ................................................................................................... 114
4.2. Procedimiento ............................................................................................................ 114
4.3. Datos experimentales ................................................................................................. 117
4.4. Cálculos y resultados................................................................................................... 120
4.5. Prueba de Hipótesis .................................................................................................... 123
5. Conclusiones ........................................................................................................... 126
Bibliografía ..................................................................................................................... 127

ÍNDICE DE TABLAS
TABLA 2.1: TABLA DE VERDAD CNOT. ................................................................................................................. 46
TABLA 2.2: TABLA DE VERDAD TOFFOLI................................................................................................................. 47
TABLA 2.3: TABLA DE VERDAD DE FREDKIN ............................................................................................................ 48
TABLA 2.4: EJEMPLO DE SHANNON–FANO BALANCEADO. ......................................................................................... 53
TABLA 2.5: EJEMPLO CÓDIGO HUFFMAN............................................................................................................... 54
TABLA 3.2.1: REPRESENTACIÓN DE LA LETRA “A” EN CÓDIGO ASCII Y BINARIO. .............................................................. 72
TABLA 4.1: TAMAÑO DE CODIFICACIÓN HUFFMAN Y PROPUESTO. ............................................................................. 118
TABLA 4.2: TIEMPO DE CODIFICACIÓN HUFFMAN Y PROPUESTO. ............................................................................... 119

ÍNDICE DE FIGURAS
FIGURA 2.1: EL GATO DE SCHRÖDINGER Y LA SUPERPOSICÍON CUÁNTICA ....................................................................... 24
FIGURA 2.2: CIRCUITO CUÁNTICO DEL ALGORITMO DE DEUTSCH. ................................................................................ 28
FIGURA 2.3: PUERTA DE HADAMARD. .................................................................................................................. 30
FIGURA 2.4: CIRCUITO DE TCF PARA TRES QUBITS. .................................................................................................. 30
FIGURA 2.5: IMPLEMENTACIÓN DEL CIRCUITO CUÁNTICO DEL ALGORITMO DE SHOR. ........................................................ 31
FIGURA 2.6: PRIMER PASO DEL ALGORITMO DE GROVER. .......................................................................................... 32
FIGURA 2.7: OPERADOR DE GROVER. ................................................................................................................... 33
FIGURA 2.8: REFLEXIÓN EN EL PLANO Y SOBRE EL VECTOR . ......................................................................... 33
FIGURA 2.9: REFLEXIÓN EN EL PLANO Y SOBRE EL VECTOR . .......................................................................... 34
FIGURA 2.10: CIRCUITO COMPLETO DEL ALGORITMO DE GROVER. ............................................................................... 34
FIGURA 2.11: REPRESENTACIÓN ESQUEMÁTICA DE COORDENADAS ESFÉRICAS. ................................................................ 39
FIGURA 2.12: ESFERA DE BLOCH. ........................................................................................................................ 40
FIGURA 2.13: CIRCUITO CNOT. ......................................................................................................................... 46
FIGURA 2.14: COMPUERTA CUÁNTICA TOFFOLI. ..................................................................................................... 47
FIGURA 2.15: COMPUERTA CUÁNTICA FREDKIN ...................................................................................................... 48
FIGURA 2.16: ÁRBOL HUFFMAN DE LA TABLA 2.5: EJEMPLO CÓDIGO HUFFMAN. ........................................................... 55
FIGURA 2.17: UN EJEMPLO DE LA CODIFICACIÓN DE TRES MENSAJES CON LA DISTRIBUCIÓN DE PROBABILIDAD
. .................................................................................................................................................... 55
FIGURA 2.18: COMPRESIÓN RLE. ....................................................................................................................... 56
FIGURA 2.19: EJEMPLO DE JPEG EN ESCALA DE GRISES, 640*480 PIXELES. .................................................................. 59
FIGURA 2.20: PROCESO JPEG. ........................................................................................................................... 60
FIGURA 2.21: CUADROS MPEG. ........................................................................................................................ 61
FIGURA 2.22: ESTRUCTURAS BÁSICAS DEL MÉTODO JACKSON. .................................................................................... 68
FIGURA 3.3.1: DIAGRAMA GENERAL. ................................................................................................................... 77
FIGURA 3.3.2: MÓDULO LEERARHIVOS. ............................................................................................................... 78
FIGURA 3.3.3: MÓDULO CODIFICARHUFFMAN. ...................................................................................................... 78
FIGURA 3.3.4: MÓDULO CODIFICARARCHIVOS. ...................................................................................................... 78
FIGURA 3.3.5: SUBMÓDULO CREARFRECUENCIAS. ................................................................................................... 79
FIGURA 3.3.6: SUBMÓDULO ESTAKEY................................................................................................................... 79
FIGURA 3.3.7: SUBMÓDULO ENTROPIASHANNON. .................................................................................................. 79
FIGURA 3.3.8: SUBMÓDULO ENTROPIANEUMANN. ................................................................................................. 80
FIGURA 3.3.9: SUBMÓDULO KET. ........................................................................................................................ 80
FIGURA 3.3.10: SUBMÓDULO BRA. ..................................................................................................................... 80
FIGURA 3.3.11: SUBMÓDULO NORMALIZARESTADOS. .............................................................................................. 80
FIGURA 3.3.12: SUBMÓDULO VOLVERVECTOR. ...................................................................................................... 81
FIGURA 3.3.13: SUBMÓDULO GRAMSCHMIDT. ...................................................................................................... 81
FIGURA 3.3.14: SUBMÓDULO BASEORTONORMAL. ................................................................................................. 81
FIGURA 3.3.15: SUBMÓDULO CODIFICACIÓN. ........................................................................................................ 81
FIGURA 3.3.16: SUBMÓDULO PRUEBADECODIFICAR. ............................................................................................... 82
FIGURA 3.3.17: SUBMÓDULO VOLVERABINARIO. ...................................................................................................82
FIGURA 3.3.18: SUBMÓDULO DECIMALABINARIO. .................................................................................................. 82
FIGURA 3.3.19: MÓDULO LEERARCHIVOS. ............................................................................................................ 83
FIGURA 3.3.20: MÓDULO CODIFICARHUFFMAN. .................................................................................................... 84
FIGURA 3.3.21: MÓDULO CODIFICARARCHIVOS. .................................................................................................... 85
FIGURA 3.3.22: SUBMÓDULO CREARFRECUENCIAS. ................................................................................................. 86
FIGURA 3.3.23: SUBMÓDULO ESTAKEY. ............................................................................................................... 86
FIGURA 3.3.24: SUBMÓDULO ENTROPIASHANNON. ................................................................................................ 87
FIGURA 3.3.25: SUBMÓDULO BASEORTONORMAL. ................................................................................................. 87

FIGURA 3.3.26: SUBMÓDULO KET. ...................................................................................................................... 87
FIGURA 3.3.27: SUBÓDULO CODIFICACIÓN. ........................................................................................................... 88
FIGURA 3.3.28: SUBMÓDULO DECIMALABINARIO. .................................................................................................. 88
FIGURA 3.3.29: SUBMÓDULO ENTROPIANEUMANN. ............................................................................................... 89
FIGURA 3.3.30: SUBMÓDULO GRAMSCHMIDT. ...................................................................................................... 89
FIGURA 3.3.31: SUBMÓDULO KET. ...................................................................................................................... 90
FIGURA 3.3.32: SUBMÓDULO NORMALIZARESTADOS. .............................................................................................. 90
FIGURA 3.3.33: SUBMÓDULO PRUEBADECODIFICAR. ............................................................................................... 90
FIGURA 3.3.34: SUBMÓDULO VOLVERABINARIO. ................................................................................................... 91
FIGURA 3.3.35: SUBMODULO VOLVERVECTOR. ...................................................................................................... 91
FIGURA 3.3.36: MÓDULO LEERARCHIVO. ............................................................................................................. 92
FIGURA 3.3.37: MÓDULO CODIFICARHUFFMAN. .................................................................................................... 93
FIGURA 3.3.38: MÓDULO CODIFICARARCHIVOS. .................................................................................................... 94
FIGURA 3.3.39: MÓDULO CREARFRECUENCIAS. ..................................................................................................... 95
FIGURA 3.3.40: MÓDULO ESTAKEY. .................................................................................................................... 96
FIGURA 3.3.41: MÓDULO ENTROPIASHANNON. ..................................................................................................... 96
FIGURA 3.3.42: MÓDULO BASEORTONORMAL. ...................................................................................................... 97
FIGURA 3.3.43: MÓDULO BRA. .......................................................................................................................... 98
FIGURA 3.3.44: MÓDULO DECIMALABINARIO. ...................................................................................................... 98
FIGURA 3.3.45: MÓDULO CODIFICACION. ............................................................................................................. 99
FIGURA 3.3.46: MÓDULO ENTROPIANEUMANN. .................................................................................................. 100
FIGURA 3.3.47: MÓDULO GRAMSCHMIDT. ......................................................................................................... 101
FIGURA 3.3.48: MÓDULO KET. ........................................................................................................................ 102
FIGURA 3.3.49: MÓDULO NORMALIZARESTADOS. ................................................................................................ 102
FIGURA 3.3.50: MÓDULO PRUEBADECODIFICAR. .................................................................................................. 103
FIGURA 3.3.51: MÓDULO VOLVERABINARIO. ...................................................................................................... 104
FIGURA 3.3.52: MÓDULO VOLVERVECTOR. ......................................................................................................... 105
FIGURA 3.3.53: PSEUDOCÓDIGO LEERARCHIVOS .................................................................................................. 105
FIGURA 3.3.54: PSEUDOCÓDIGO CODIFICARHUFFMAN. .......................................................................................... 106
FIGURA 3.3.55: PSEUDOCÓDIGO CODIFICARARCHIVOS. .......................................................................................... 106
FIGURA 3.3.56: PSEUDOCÓDIGO CREARFRECUENCIAS. ........................................................................................... 107
FIGURA 3.3.57: PSEUDOCÓDIGO ESTAKEY. ......................................................................................................... 107
FIGURA 3.3.58: PSEUDOCÓDIGO ENTROPIASHANNON............................................................................................ 108
FIGURA 3.3.59: PSEUDOCÓDIGO CODIFICACION. .................................................................................................. 108
FIGURA 3.3.60: PSEUDOCÓDIGO BRA. ............................................................................................................... 108
FIGURA 3.3.61: PSEUDOCÓDIGO BASEORTONORMAL. ........................................................................................... 109
FIGURA 3.3.62: PSEUDOCÓDIGO DECIMALABINARIO. ............................................................................................ 110
FIGURA 3.3.63: PSEUDOCÓDIGO ENTROPIANEUMANN. .......................................................................................... 110
FIGURA 3.3.64: PSEUDOCÓDIGO GRAMSCHMIDT. ................................................................................................. 111
FIGURA 3.3.65: PSEUDOCÓDIGO KET. ................................................................................................................ 111
FIGURA 3.3.66: PSEUDOCÓDIGO NORMALIZARESTADOS. ........................................................................................ 111
FIGURA 3.3.67: PSEUDOCÓDIGO PRUEBADECODIFICAR. ......................................................................................... 112
FIGURA 3.3.68: PSEUDOCÓDIGO VOLVERABINARIO. ............................................................................................. 112
FIGURA 3.3.69: PSEUDOCÓDIGO VOLVERVECTOR. ................................................................................................ 113
FIGURA 4.1: PANTALLA PRINCIPAL DEL SOFTWARE. ................................................................................................ 114
FIGURA 4.2: PANTALLA CODIFICACIÓN HUFFMAN. ................................................................................................. 115
FIGURA 4.3: PANTALLA CODIFICACIÓN PROPUESTA. ............................................................................................... 116
FIGURA 4.4: PANTALLAPRINCIPAL TRAS EJECUTAR LOS BOTONES DE CODIFICACIÓN. ....................................................... 117

RESUMEN
Un nuevo rumbo en la solución de problemas computacionales es la que ofrece la
computación cuántica. Nuevos teoremas, leyes, definiciones las cuales se pretenden aplicar,
en este trabajo, en una de las áreas en la cual todavía se está trabajando, la compresión de
datos. Se desarrollara un método de compresión de datos utilizando fundamentos de
computación cuántica, para seguidamente comparar los rasgos del tiempo y tamaño de
compresión con un método de compresión clásico (Huffman). Cabe mencionar que para
agilizar los cálculos se recurrirá a un prototipo para el análisis de los rasgos mencionados
anteriormente.
Las investigaciones relacionadas al área de computación cuántica no son nuevas, existen
varios algoritmos cuánticos que resuelven distintos problemas (factorización de números,
búsqueda en base de datos, determinación del tipo de función, entre otros), y no puede
faltar la codificación, la finalidad del trabajo es brindar un enfoque ligeramente distinto, a
los ya existentes, puesto que se utiliza el concepto de sistema de ecuaciones. Y de esta
forma aportando un conocimiento más al ya existente.
Para un mejor desarrollo del trabajo, se lo divido en las siguientes secciones:
En el capítulo 1 se dará una breve introducción, se citara fuentes bibliográficas en las cuales
está basado el presente trabajo, y se planteara una hipótesis y objetivos.
En el capítulo 2 se extraerá la información necesaria para entender los nuevos conceptos
concernientes a la computación cuántica, información clásica y distintos métodos de
compresión con y sin perdida.
En el capítulo 3 se describirá el método planteado en detalle, para luego desarrollar el
prototipo empleando la metodología Jackson.
En el capítulo 4 se procederá a aceptar o rechazar la hipótesis planteada en la capitulo1,
para la cual se realizar distintas pruebas en las cuales se utilizara el prototipo desarrollado
en la sección anterior.
Finalmente en el capítulo 5 se describirá las conclusiones a las que se llego tras concluir las
secciones anteriores.

ABSTRACT
A new direction in solving computational problems is offered by quantum computing. New
theorems, laws, definitions which they are applied, in this paper, in one of the areas which
are still being worked, data compression. A method of data compression using
fundamentals of quantum computing, to then compare the features of time and size of
compression with a classic compression method (Huffman) was developed. It is noteworthy
that the calculations to expedite call on a prototype for the analysis of the features
mentioned above.
Research related to the area of quantum computing are not new, several quantum
algorithms that solve different problems (factoring numbers search database, determining
the type of function, etc.), and cannot miss the coding order work is to provide a slightly
different approach to existing, since the concept of system of equations is used. And thus
providing a further existing knowledge.
For better development work, it divided into the following sections:
Will give a brief introduction in Chapter 1, bibliographic sources in which this paper is
based was cited, and a hypothesis and objectives are raised.
In chapter 2 the information needed to understand new concepts concerning quantum
computing, classical information and different methods of compression without loss will be
removed.
In chapter 3 the method proposed in detail, and then develop the prototype using the
methodology described Jackson.
In Chapter 4 we will proceed to accept or reject the hypothesis in chapter1, for which
various tests in which the prototype developed in the previous section was used is
performed.
Finally, in chapter 5 the conclusions that was reached after completing the previous
sections will be described.
13

1. Marco Referencial
1.1. Introducción
Si en anteriores décadas cualquier científico o ingeniero, relacionado con el campo de la
electrónica, hubiera propuesto que en años posteriores las computadoras, que hasta ese
momento eran de gran tamaño y solo tenían carácter científico, estaría presentes en los
hogares y serian tan comunes como tener un radio o un televisor, habrían sido tomados
como tipos muy soñadores y poco realistas. E incluso sustentar que con el pasar de los años
esas mismas computadoras irían reduciendo en peso, tamaño y precio, habría sido tomado
como una idea totalmente loca.
Sin embargo hoy en día existe toda de una gama de computadoras personales de todo tipo
tamaño y precio, es más, actualmente están presentes los llamados dispositivos móviles,
Smartphone que prácticamente son minicomputadoras, con costos relativamente bajos.
Estos sucesos nos hacen reflexionar y cuestionarnos, de cómo avanza la tecnología, que
aparatos hoy en día son tomados como fantasía de ciencia ficción, y mañana serán tan
comunes como un Smartphone.
No obstante todo este avance tecnológico no es algo que apareció espontáneamente, tiene
sus inicios en aéreas como la física y matemática, principalmente física, y si por un
momento nos detenemos a pensar que es un bit, podemos llegar a la conclusión que es un
cero (0) ó uno (1), apagado o prendido respectivamente.
Pero porque decimos que principalmente se apoya en la área de la física, porque muchos de
los componentes electrónicos de una computadora emplean principios de la física clásica,
así por ejemplo la fuente de poder transforma un voltaje de entrada de (110-220) voltios a
voltajes mucho menores de 5, 7, 9, 12 voltios, que son con los que trabajan la mayoría de
de los componentes electrónicos como los lectores de Dvd, placa base, microprocesador.
Bajo este entendido, si una computadora utiliza principios de física clásica, ¿podrá utilizar
principios de física cuántica? La respuesta es sí, y lo más sorprendente es que ya hace
tiempo se planteo esta idea. Es más ya existen algunas computadoras cuánticas, que
emplean principios de computación cuántica, la más rescatable, es el uso del Qbit (quantum
bit), un análogo del bit clásico.
Si existen computadoras cuánticas no pueden faltar los algoritmos cuánticos, entre los que
podemos mencionar al algoritmo de factorización de Shor, algoritmo de búsqueda de
Grover, la transformada cuántica de Fourier, entre algunos, los cuales emplean
fundamentos de computación cuántica.
14

Pero al existir algoritmos de búsqueda, factorización, determinación de tipo de función, no
pudieron faltar algoritmos de codificación/decodificación cuántica, y es precisamente el
tema de este trabajo. Se plantea un método que hace uso de fundamentos de computación
cuántica (Qbit) para lograr una codificación/decodificación de qbits en un entorno clásico
1
.
1.2. Antecedentes
Actualmente se realizaron diversos trabajos, relacionados con la codificación cuántica,
muchos de ellos son artículos en los cuales, sus autores, describen su método y presentan
sus conclusiones. Entre los consultados, para este trabajo, tenemos:
“Efficient and exact quantum compression
2
”
Este artículo escrito por el Departamento de Ciencia de la Computación, de la Universidad
Duke Durham. Plantea un algoritmo basado en la idea de divide y vencerás, para una
compresión/descompresión cuántica optima, usando operaciones
cuánticas elementales, dando como resultado el primer algoritmo cuasi lineal.
“Quantum source coding and data compression
3
”
Este artículo presenta la compresión de Schumacher, teoremas y demostraciones de la
entropía de Von Neumann, el cual es una media de la información cuántica, siendo similar
a la entropía de Shannon (el cual pertenece a la información clásica).
“Quantum-inspired Huffman Coding
4
”
Este artículo presenta un método en el cual empleando conceptos de computacióncuántica
(bra y kets) se puede conseguir códigos Huffman en un tiempo .
“Adaptive Quantum Lossless Compresion
5
”
Este artículo plantea un nuevo algoritmo cuántico de compresión sin pérdida, con la
característica de no necesitar las probabilidades a priori. La principal idea es asumir que
todos los símbolos tienen idéntica probabilidad, y después de cada iteración las mismas son
actualizadas.

1
Emular qbits en una computadora que usa bits.
2 (H. Reif & Chakraborty, 2007).
3 (Petz, 2014).
4 (Tolba, Rashad, & El-Dosuky, 2007).
5 (Essam, 2007).
15

“A quantum analog of Huffman coding
6
”
En este artículo, se analiza una generalización de la codificación Huffman en el caso
cuántico, construyendo códigos Huffman, inspirados en un esquema cuántico. Además que
el número de pasos computacionales en el proceso de codificación y decodificación de
estados cuánticos puede ser realizado en un tiempo poli-logarítmico.
“Lossless Quantum Data Compression and Secure Direct Communication
7
”
Esta obra es una tesis, está dividida en tres partes, Conceptos de Información, Compresión
de Datos Cuánticos y Criptografía. La primera parte nos sumerge en los conceptos de
información clásica y cuántica. La segunda parte trata de la compresión de Schumacher y
además nos plantea ejemplos. Finalmente la tercera parte trata de la criptografía clásica y
cuántica.
1.3. Planteamiento del Problema
En la actualidad el procesamiento de información ha pasado del uso de los bits clásicos al
uso de bits cuánticos (qbits), la diferencia más relevante entre ellos es la llamada
superposición cuántica, rasgo fundamental que dota de mayor poderío a la hora de realizar
cálculos, puesto que a diferencia de un bit clásico, un qbit puede estar en un estado de cero
y uno simultáneamente. Además para una fácil representación de un qbit, en este trabajo, se
ha adoptado la representación vector columna (Notación de Dirac), el cual representa un
qbit de la siguiente manera:

El rasgo de superposición fue aprovechado por Peter Shor, para desarrollar el primer
algoritmo cuántico de factorización, el cual es capaz de factorizar números grandes en
pocos segundos, y de esta manera destruyendo las bases de la criptografía moderna. Otro
algoritmo cuántico relevante es el de búsqueda de Grover.
Pero es imposible pensar que no existiera una teoría de información cuántica, detrás de
estos algoritmos, y es justamente la teoría que nos ayuda dar respuesta a las siguientes
preguntas:
¿Se puede utilizar bits para representar qbits?
¿Existirá diferencia en el tiempo que tarda la codificación/decodificación, de un archivo de
texto plano, cuando se emplean qbits?

6 (Braunstein, Fuchs, Gottesman, & Lo, 1999).
7 (Boström, 2004).
16

¿Un método de codificación que emplea fundamentos de computación cuántica, en un
ambiente clásico, será más eficaz que un método de codificación clásica?
1.4. Formulación del Problema
¿Qué impacto tendrá un método de codificación que emplea fundamentos de computación
cuántica, en un ambiente clásico, en el tiempo y tamaño de codificación con respecto a un
método de codificación clásica?
1.5. Hipótesis
“La codificación de un archivo de texto, utilizando fundamentos de computación cuántica,
produce una codificación más rápida y de menor tamaño con respecto a una codificación
clásica (Huffman)”.
1.6. Identificación de Variables
1.6.1. Variable Dependiente
Codificación más rápida y de menor tamaño.
1.6.2. Variable Independiente
Archivo de texto.
1.6.3. Operacionalización de variables
Nombre de la variable Definición conceptual
Definición
Instrumental
Definición Operacional
Codificación más
rápida y de menor
tamaño
Proceso que comienza
tras seleccionar un
archivo de texto y
termina cuando el
método propuesto
concluye.
Se observa en la
interfaz de salida
del prototipo.
Se compara el tiempo y
tamaño que toma el
método propuesto, con
respecto a la codificación
clásica (Huffman) y ambos
números se dividen y se
obtiene una relación.
(Número racional)
17

1.7. Objetivos
1.7.1. Objetivo General
Desarrollar un método de codificación de datos, empleando conceptos de computación
cuántica.
1.7.2. Objetivos Específicos
Recopilar información de los diferentes tipos de codificación que emplean bits.
Compendiar información de los fundamentos y rasgos de la computación cuántica.
Diseñar y desarrollar una aplicación para realizar pruebas de codificación.
Analizar rasgos como el tiempo y el tamaño, tras el proceso de codificación.
1.8. Justificación
1.8.1. Técnica
Las investigaciones relacionadas al área de computación cuántica no son nuevas, existen
varios algoritmos cuánticos que resuelven distintos problemas (factorización de números,
búsqueda en base de datos, determinación del tipo de función, entre otros), y no puede
faltar la codificación, y en los trabajos que se reviso se encontró varios métodos de
codificación, el planteado en este trabajo brinda un enfoque ligeramente distinto, puesto
que se utiliza el concepto de sistema de ecuaciones.
1.8.2. Social
En la búsqueda de documentos similares, relacionados al presente trabajo, lamentable no se
encontró mucha documentación en nuestra carrera, si bien existen documentos relacionados
con computación cuántica, no eran del todo orientados a la codificación cuántica, y por lo
que ahora se ofrece un aporte más.
1.8.3. Práctica
En los trabajos revisados la mayoría constan de aspectos base en común, del mismo modo
el presente trabajo no se distancia demasiado de aquellos aspectos, pero al final se toma
18

otra perspectiva para lograr una codificación cuántica, por lo que se considera que se
ofrece un método diferente a los consultados.
1.8.4. Económica
El propósito de la investigación no es generar alguna compensación monetaria, más bien se
inclina a aportar conocimiento, satisfacer una curiosidad personal. Intentar ser un punto de
referencia para trabajos posteriores.
1.9. Limites y Alcances
Lo que se pretende en el presente trabajo, es buscar información, estudiarla, analizarla,
desarrollar un método de codificación/decodificación usando principios de computación
cuántica y finalmente realizar una comparación del método planteado, con un método de
codificación de la computación clásica (Huffman). Cabe mencionar que la comparación se
realizara con la ayuda de un pequeño prototipo, el cual será desarrollado en la herramienta
informática MatLab.
Por otro lado, como se menciono en la justificación, el método planteado es muy similar a
los trabajos consultados, y no se pretende desarrollar una nueva teoría, puesto que ya existe
todo un mundo de teoremas y definiciones ya planteadas, solo se emplearan estas mismas
teorías para lograr el propósito mencionado en líneas anteriores.
1.10. Diseño Metodológico
La metodología empleada, en el estudio y desarrollo del presente trabajo, se rige bajo el
método científico experimental, puesto que la hipótesis que se pretende probar requiere de
varias muestras de archivos de texto, las cuales serán procesadas por el prototipo, el cual
presentara de forma más rápida los datos como el tiempo y tamaño de codificación, para su
posterior análisis.
Para el desarrollo del presente trabajo se consideran los siguientes pasos:
Desarrollo de un prototipo, bajo la metodología Jackson y técnica descendente
(Tod-Down).
Se seleccionará varios archivos de texto plano, los cuales serán procesados por el
prototipo.

Cada archivo será codificado de forma clásica (Huffman) y forma cuántica (método
planteado) y en ambos casos se calculara el tiempo que toma la codificación y cuál
es el tamaño de la tras codificación.

Se analizara los resultados que nos lanza el prototipo tras la codificacióny se
procederá a tener una posición frente a nuestra hipótesis.

Finalmente se llegara a conclusiones, y si es posible se brindara algunas
recomendaciones.

2. Marco Teórico
2.1. Fundamentos de la mecánica cuántica
La mecánica cuántica (QM: Quantum Mechanics) surge como necesidad para explicar
hechos inexplicables en el mundo de la mecánica clásica. Cuando se intenta utilizar la
mecánica y la electrodinámica clásicas para explicar los fenómenos atómicos, los resultados
a que conducen se encuentran en franca contradicción con la experiencia. Ningún
paradigma científico puede resistir este resultado de confrontación con la realidad. (Hecht,
2005)
2.1.1. Dualidad Onda Partícula
La luz no es una onda continua, a veces se comporta como una partícula; se comporta como
si viniera en pedazos, en trocitos, en cuantos, los cuantos de luz se llaman fotones.
(Mullington)
2.1.2. El Experimento De La Doble Ranura
Es una metáfora de la dualidad onda partícula, un haz de electrones choca contra una
pantalla que tiene dos ranuras paralelas y después contra otra pantalla.
Al hacer este experimento con las luces prendidas no ocurre nada inusual, los electrones no
formar ningún patrón.
Pero cuando apagamos las luces, en la pantalla se observa una serie de máximos (puntos
donde se acumulan electrones) y mininos (puntos que evitan), esto es lo que esperaría ver si
enviaras ondas y no partículas a través de la doble ranura. (Mullington)
2.1.3. Principio De Incertidumbre De Heisemberg
En la Física Cuántica existe una limitación sobre la certeza con la que se pueden medir dos
o más magnitudes no compatibles simultáneamente. Este hecho fue formulado por el
científico alemán Werner Heisenberg, quien demostró que la incertidumbre en el
conocimiento de la posición de una partícula, multiplicada por la incertidumbre en su
cantidad de movimiento (o "momentum"), nunca puede ser más pequeña que una cierta
21

cantidad, la constante de Planck
8
. Además, este límite es una propiedad fundamental e
ineludible, que no depende de la forma en que se realicen las medidas, ni del tipo de
partícula. (J. Santos, 2003)
Establece que esas dos propiedades de una partícula no pueden conocerse simultáneamente
con exactitud. Cuando se conoce exactamente el impulso de una partícula (o sea el
producto de su masa por su velocidad), su ubicación resulta ser completamente incierta. Y a
su vez, cuando se conoce exactamente la ubicación, el impulso no puede ser determinado.
(J. Funes, 2004)
El principio de incertidumbre significa que el universo es más complejo de lo que se
suponía pero no irracional. (Hecht, 2005)
Ecuación 2.1
2.1.4. Postulados
Se describirán los postulados de la mecánica cuántica en términos de matrices de densidad,
siendo útil, esta formulación, para describir sistemas cuánticos cuyos estados no son
completamente conocidos.
Es posible que algunos conceptos no sean comprendidos en su totalidad, pero estos serán
desarrollados en secciones posteriores.
Postulado 1: Existe un espacio vectorial con producto interno (llamado espacio de Hilbert
), asociado a cualquier sistemas físico aislado. Un estado de ese sistema es
completamente descrito por una matriz , llamada matriz de densidad, tal que
y . Si el sistema está en el estado con probabilidad
, para entonces la matriz de densidad está dada por:

Cuando , para diremos que el conjunto es un conjunto de
estados puros
9
. Caso contrario, es un conjunto de estados mixtos. (Lavor, 2006)
Postulado 2: La evolución de un sistema cuántico aislado es descrita por un operador lineal
que preserva el producto interno (operador unitario). O sea, el estado del sistema, en
tiempo , está relacionado al estado , en tiempo , a través de un operador unitario
que depende apenas de y . O sea, (Lavor, 2006)

8 Constante física descubierta por Max Planck .
9 Un estado puro hace referencia a estar máximamente determinado.
22

Postulado 3: Las medidas sobre sistemas cuánticos son descritas por un conjunto de
operadores de medida tal que

Donde es el operador de identidad. Si el estado del sistema anterior a la medida está dado
por , la probabilidad de ocurrir el resultado esta dado por

Y el estado del sistema después de la medida está dado por:

Asociado a cada , podemos definir otros operadores , dados por

Podemos demostrar que los operadores son hermitinianos ( , positivos
( y . Un conjunto con esas características esta de
definido como un POVM
10
. En lugar el conjunto , se usa con frecuencia, un POVM
para describir a los operadores de medida. (Lavor, 2006)
Postulado 4: El estado compuesto por estados, , es el producto tensorial
.
Un estado que no puede ser escrito como producto tensorial de estados
es llamado enredado. Todas las propiedades que diferencian los estados
cuánticos de los estados clásicos son consecuencia del enredo. Por ejemplo el estado

Puede ser escrito como

10 POVM: En ciertas ocasiones el estado de un sistema puede ser medido una sola vez y no se tiene interés en
el estado del sistema después de la medición. A este tipo de mediciones se les conoce como mediciones
POVM (Positive Operator Valued Measurements). (Mendoza Vázquez, 2010)
23

Pero no podemos hacer lo mismo con el estado

O sea, es un estado no enredado y es un estado enredado.
Para describir la evolución de sistemas cuánticos que no están aislados, se usara una
herramienta matemática llamada operaciones cuánticas. Una operación cuántica puede
ser descrita por la representación del operador suma, dada por

Los operadores son elementos de operación de , es el operador
identidad y es el operador densidad del sistema.
Las operaciones cuánticas pueden representar los operadores descritos en el Postulado 2

Y las medidas descritas en el Postulado 3,

Además, pueden también ser utilizadas para representar las alteraciones provocadas por el
paso de un estado a través de un canal cuántico cualquiera. (Lavor, 2006)
2.1.5. El Gato De Schrödinger
Erwin Schrödinger planteo un interesante modelo que ilustra la naturaleza azarosa de la
mecánica cuántica. Cuando se habla del “gato de Schrödinger” se está haciendo referencia a
una paradoja que surge de un célebre experimento imaginario propuesto por Erwin
24

Schrödinger en el año 1937 para ilustrar las diferencias entre interacción y medida en el
campo de la mecánica cuántica. (Hecht, 2005)
Schrödinger usa como experimento la desintegración radioactiva. Las posibilidades son
dos: tiene lugar la desintegración del átomo o no tiene lugar. El instrumento de medición es
un detector que activa un diabólico martillo que, en caso de que ocurra la desintegración,
golpea un recipiente de cristal con veneno y lo rompe. Y ahora Schrödinger mete su
instrumento dentro de una caja negra sin ventanas ni puertas, junto con un gato. La función
de onda
11
representara entonces el estado gato vivo - gato muerto. (Álvarez
Nodarse, 2009)
Si lo que ocurre en el interior de la caja lo intentamos describir aplicando las leyes de la
mecánica cuántica, llegamos a una conclusión muy extraña. El gato vendrá descrito por una
función de onda extremadamente compleja resultado de la superposición de dos estados
combinados al cincuenta por ciento: “gato vivo” y “gato muerto”. Es decir, aplicado el
formalismo cuántico, el gato estaría a la vez vivo y muerto; se trataría de dos estados
indistinguibles. (Hecht, 2005)
Figura 2.1: El gato de Schrödinger y la superposicíon cuántica

Fuente: Extraído de (Álvarez Nodarse, 2009)
2.1.6. Entrelazamiento cuántico
El entrelazamiento es un fenómeno cuántico, sin equivalente clásico, en cual los estados de
dos o más subsistemas se deben describir haciendo referencia a losestados del sistema
total, incluso cuando la separación entre los subsistemas es grande.

11 La Función De Onda es un instrumento matemático, un almacén de información sobre el sistema físico.
(García Alcaine, 2005)
25

Las mediciones realizadas sobre algún observable de un sistema que está entrelazado con
otros parecen influenciar instantáneamente a estos.
Esto parecería sugerir que alguna influencia debería estar propagándose “instantáneamente”
entre los sistemas, a pesar de la separación entre ellos, lo que violaría la velocidad máxima
de propagación de las interacciones.
El entrelazamiento cuántico fue en un principio utilizado por A Einstein, B. Podolsky y N.
Rosen (EPR) como un argumento para intentar probar la incompletitud de la mecánica
cuántica como teoría física, alegando que las correlaciones predichas por la mecánica
cuántica son inconsistentes con el Principio De Realismo Local
12
(D. Blanco, 2010)
En los años 1920 – 1930, surgió un nuevo paradigma que indica que los sistemas no
observados son indeterminados (gato de Schrödinger). O sea, cuánticamente, una pelota de
tenis no posee posición, la adquiere cuando es observada. Muchos físicos objetaron esta
nueva visión de la naturaleza. El objetor más prominente fue Albert Einstein. En su famoso
trabajo del año 1935 y conocido como el “EPR paper”, junto a Nathan Rosen y Boris
Podolsky llevando como titulo las iníciales de los autores, propuso un experimento que
pensaba podría demostrar que la mecánica cuántica no era una teoría completa de la
naturaleza. (Hecht, 2005)
Si el sistema total se encuentra en un estado puro el enredo se manifiesta en que el estado
total no puede expresarse como producto de estados para cada una de sus partes (desde el
punto de vista matemático), y en que ninguna de dichas partes por separado se encuentra en
un estado puro (desde el punto de vista físico). (García Alcaine, 2005)
2.1.7. La Paradoja EPR
En el trabajo original de Einstein, Podolsky, Rosen se hace un análisis del entrelazamiento
que presenta un sistema de dos partículas que interactúan durante un intervalo de tiempo
determinado y luego son separadas espacialmente, en términos del momento lineal
13
y las
posiciones de las partículas. (D. Blanco, 2010)
Einstein, Podolsky, Rosen proponían que:
En una teoría completa, cada elemento corresponde a un elemento de la realidad, una
condición suficiente para que una cantidad física sea real, es la posibilidad de predecirla
con certeza sin interrumpir el sistema, por tanto: La descripción de la realidad dada por la

12
El principio de realismo local es una conjunción entre el Principio de Localidad y la asunción de que todas
las magnitudes físicas tienen valores preexistentes para cada medición incluso antes de que se realice la
medición.
13 Momento lineal, ímpetu o momentum es una magnitud física del tipo vectorial que describe el movimiento
de un cuerpo en cualquier teoría mecánica.
26

función de onda de la mecánica cuántica no está completa; o estas dos cantidades no
pueden tener una realidad simultánea; así uno llega a la conclusión de que la descripción de
la realidad dada por una función de onda no está completa. (Mullington)
La meta de EPR era demostrar que la mecánica cuántica era incompleta demostrando que le
faltaba algún esencial elemento de la realidad. EPR deseaba forzar un regreso a una visión
más clásica del mundo, una en la cual las propiedades de un sistema existían
independientemente de su medición. (Hecht, 2005)
2.1.8. Cuantificación del entrelazamiento
Para (Mendoza Vázquez, 2010) definir si un estado se encuentra entrelazado o no es
relativamente sencillo pero medir o cuantificar la cantidad de entrelazamiento del estado no
lo es. Algunas condiciones necesarias que cualquier tipo de medición de entrelazamiento
sobre un estado debe de satisfacer los siguientes postulados:
No negatividad: ( ) 0
( ) = 0 sí y solo sí es separable.
Operaciones Locales Unitarias no modifican el valor ( ).
no aumenta su promedio sobre operaciones locales clásicas: , donde
el estado bajo operaciones locales es obtenido con probabilidad .
es continua.
es aditiva (sobre estados puros):
2.1.9. Estados de Bell
Un estado de Bell o también conocido como par EPR, es definido como un estado de
máximo entrelazamiento cuántico de dos qubits. Un estado se encuentra máximamente
entrelazado si podemos construir a partir de él cualquier otro estado de la base usando
operaciones locales y comunicaciones clásicas (LOCC). Una operación local es aquella
operación que no actúa en dos qubits simultáneamente. Cualesquiera otros estados pueden
ser formados a través de operaciones unitarias actuando en este estado. Los estados de Bell
forman una base ortogonal del espacio de estados cuánticos de dos qubits denominada base
de Bell. (Mendoza Vázquez, 2010)

2.1.10. Algoritmos Cuánticos
2.1.10.1. Algoritmo de Deutsch
Permite determinar si una función lógica de qubits es constante o balanceada. Una
función básica de una computadora clásica es la evaluación de una función lógica con
bits de entrada y un bit de salida, esto es

Definimos una función balanceada como aquella cuyos valores de salida pueden ser
opuestas para la mitad de sus entradas. Una función de un solo bit la definimos como
función constante, si ocurre que ó .
Si una función es balanceada o constante es una propiedad global. El algoritmo de Deutsch
ayudará a saber si una función de un qubit es una función constante o una función
balanceada. El primer paso es denotar un operador unitario que actúe sobre dos qubits,
con la propiedad de que es la función identidad en el primer qubit y produzca una
compuerta OR exclusiva del segundo qubit con una función que usa al primer qubit como
argumento,

Como es un qubit, entonces puede estar en un estado superpuesto.
El algoritmo de Deutsch utiliza los resultados anteriores para explotar el que un estado se
encuentre en una superposición para obtener información sobre la propiedad global de una
función. El procedimiento es el siguiente:

Figura 2.2: Circuito Cuántico del Algoritmo de Deutsch.

Fuente: Extraído de (Mendoza Vázquez, 2010)
Descripción del algoritmo de Deutsch:
Aplicar las compuertas Hadamard al estado inicial | para producir el producto
de estados de dos superposiciones.
Aplicar al estado obtenido.
Aplicar una compuerta Hadamard al primer qubit dejando libre el segundo qubit.
(Mendoza Vázquez, 2010)
2.1.10.2. Algoritmo Deutsch-Jozsa
El algoritmo de Deutsch-Jozsa es una generalización del algoritmo de Deutsch. Nos
permite deducir si una función es constante o balanceada pero para una función con
múltiples valores de entrada, esto es una función de qubits. Si es constante entonces
los valores de salida son los mismos para todas las . Si es balanceada entonces
para la mitad de las entradas y para la otra mitad de las entradas.
(Mendoza Vázquez, 2010)
2.1.10.3. La Transformada Cuántica de Fourier
Para (T. Perry, 2010) el análogo cuántico de la Transformada Discreta de Fourier es la
Transformada cuántica de Fourier (TCF). La TDF
14
toma una serie de números
complejos y produce una serie de números complejos ,
similarmente, La TCF toma un vector estado:

y ejecuta la TDF sobre el estado dándonos:

14 Transformada Discreta de Fourier.
29

La principal ventaja de la TCF, es el hecho que esta puede hacer una TDF sobre la
superposición de estados. Esto puede ser hecho sobre una superposición similar al
siguiente:

o donde las amplitudes de probabilidad de un estado son valores diferentes.
La FCT es un operador unitario, y es reversible. De hecho se usa la Transformadacuántica
de Fourier Inversa (TCF
-1
) para el algoritmo de Shor. La TCF esta defino como:
dado un vector estado :

donde es el número de qubits, la está definida como:

Nosotros también podemos representar la TCF como una matriz:

donde .
Para lograr que esto sea fácil de entender, identificaremos la parte importante de la
sumatoria que necesitamos para representa la matriz (cuya etiqueta será ):

donde .
30

Ahora usando la sumatoria, aquí están algunos valores para e para :

Implementación de la TCF:
La TCF para un qubit es simplemente el siguiente circuito:
Figura 2.3: Puerta de Hadamard.

Fuente: Extraído de (T. Perry, 2010).
Para tres qubits la TCF es el siguiente circuito:
Figura 2.4: Circuito de TCF para tres qubits.

Fuente: Extraído de (T. Perry, 2010).
Se puede extender esta lógica para qubits usando H (Hadamart) y diferentes
rotaciones de puertas (ver sección 2.2.6.1):

2.1.10.4. Algoritmo de Factorización de Shor
En 1994 Peter Shor publicó el artículo "Algorithms for quantum computation, discrete
31

logarithms and factorig" en donde mostró un nuevo enfoque al algoritmo de factorización,
combinando principios de la mecánica cuántica con la teoría de números. Este algoritmo ha
creado gran interés en computación cuántica debido a que los sistemas criptográficos basan
su seguridad en la dificultad de factorizar números muy grandes. (Mendoza Vázquez, 2010)
Shor descubrió un algoritmo que puede sacar provecho de una computadora cuántica para
calcular factores de números grandes en un tiempo polinomial. Utilizando computadoras
convencionales tal problema es un extremadamente intensivo de pasos computacionales,
tanto así que elementos de la criptografía están basados en la factorización a tal grado que
es difícil de factorizar números enteros sobre computadoras clásicas.
El algoritmo en si es extremadamente complejo de explicar. El algoritmo de Shor toma un
número entero positivo como la entrada, y la salida son factores no triviales de si estos
existen. Esto puede muy brevemente ser resumido en estos cinco pasos:
Paso 1: Determinamos si N es primo o una potencia de un primo usando un
algoritmo polinomial. Si es cualquiera de los dos, lo declaramos y salimos.

Paso 2: Elegimos un número entero aleatorio , y ejecutamos el
algoritmo de Euclides para determinar si . Si esto no es igual a
elegimos un nuevo .

Paso 3: Encontramos un periodo usando el circuito cuántico de la Figura 2.5:
Figura 2.5: Implementación del circuito cuántico del algoritmo de Shor.

Fuente: Extraído de (Allcock, 2010)
Paso 4: Si es impar o volvemos al paso 2 y elegimos un número
.
32

Paso 5: Usando el algoritmos de Euclides para calcular la y
. Retornamos el último de las soluciones no triviales. (Allcock,
2010)
2.1.10.5. Algoritmo de Grover
La búsqueda en base de datos es una tarea fundamental del procesamiento de información.
Dada una base de datos, a menudo es deseable encontrar un determinado estado en medio
de un conjunto de posibles estados, suministrado como una lista desordenada. Esto es
equivalente al problema de encontrar un “objetivo” especifico dentro de una base de datos
“señalada” en una situación donde se conoce que existe tal entrada en la base de datos,
puesto que cada posible estado de la base de datos corresponde a tener una entrada distinta.
Lov Grover descubrió un algoritmo cuántico para la búsqueda en base de datos que tiene
una eficiencia que supera a los algoritmos clásicos de búsqueda suministrando una
velocidad cuadrática: una consulta clásica toma pasos y usando este algoritmo puede
ejecutarse en pasos. Aunque menos dramático que incrementar la velocidad
provista por los algoritmos cuánticos involucra encontrar el periodo, tal mejora todavía es
importante, por ejemplo, la Transformada Rápida De Fourier es de importancia práctica
como una mejora de la Transformada de Fourier clásica. (Jaeger, 2007)
Este algoritmo es útil para aquellos problemas en los que identificar una solución es
sencillo pero encontrarla es tremendamente complicado. Se trata de un algoritmo que en
general es probabilístico y su objetivo será intentar que la solución correcta sea la más
probable. (Coello de Portugal Vázquez, 2013)
Descripción del algoritmo:
El primer paso del algoritmo es colocar qubits en superposición utilizando
puertas de Hadamard. Además, se debe utilizar un qubit más para el subespacio del oráculo
preparado como en el algoritmo de Deutsch en el estado: :
Figura 2.6: Primer paso del algoritmo de Grover.

Fuente: Extraído de (Coello de Portugal Vázquez, 2013).
33

Ahora hay que repetir veces el operador de Grover Figura 2.7:
Figura 2.7: Operador de Grover.

Fuente: Extraído de (Coello de Portugal Vázquez, 2013).
Los qubits superiores están inicialmente en el estado: , así que, si es
el estado solución y es el estado conjunto del resto de componentes, podemos
separarlo de la forma:

Por simplicidad,
Al estar el qubit auxiliar en el estado preparado, el efecto del oráculo será simplemente el
de cambiar la fase de la componente solución: . Si visualizamos las
componentes en su forma vectorial, podemos entender este efecto como una reflexión en el
plano definido por y sobre el vector :
Figura 2.8: Reflexión en el plano y sobre el vector .

Fuente: Extraído de (Coello de Portugal Vázquez, 2013).
34

El siguiente paso del algoritmo es aplicar el operador . El operador
de cambio de fase invierte todas las componentes de la superposición excepto la
componente , es decir, realiza la operación . El efecto conjunto del operador
sería , que geométricamente es una vez más una
reflexión, esta vez sobre el vector :
Figura 2.9: Reflexión en el plano y sobre el vector .

Fuente: Extraído de (Coello de Portugal Vázquez, 2013).
Girar el vector para aproximarlo hacia , vector solución del problema. Es fácil ver
que si repetimos estas reflexiones un número adecuado de veces, llegara un punto de
acercamiento máximo al vector solución y, por tanto, una probabilidad máxima de obtener
la respuesta correcta en la medida. Se puede demostrar que el número de veces que se debe
aplicar el operador de Grover para garantizar la probabilidad máxima es , es
decir, el orden de complejidad del algoritmo es . (Coello de Portugal Vázquez,
2013)
Figura 2.10: Circuito completo del algoritmo de Grover.

Fuente: Extraído de (Coello de Portugal Vázquez, 2013).

2.2. Conceptos Básicos
Notación de Dirac
En 1930 en el libro Principios de la Mecánica Cuántica Paul Dirac introdujo una notación
para poder describir estados cuánticos y funciones lineales, conocida como notación Bra-
Ket. Con esta notación podemos representar un estado base de elementos con una cadena
binaria de longitud , mientras que con la representación de vectores columna
necesitaríamos componentes para definir el mismo vector. (Mendoza Vázquez, 2010)
Los elementos de un espacio vectorial son descritos como . En el caso de que el
espacio sea completo y posea producto interno (o sea, ser un espacio de Hilbert), las
funciones lineales limitados pueden ser entendidos como proyección en algún vector.
Luego es interesante escribir los elementos del espacio dual como , que cuando es
aplicado en , esto es entendido como “realizar el producto interno ”.
Con la notación de Dirac es muy simple entender la acción de un operador escrito de forma
en el vector , Tenemos el vector multiplicado por el producto interno
, siendo esta “asociatividad” la ventaja principal de la notación. (Coelho
Quintino, 2010)
Ket
Asociamos a cada función de onda un vector (o Ket) en un espacio vectorial lineal ,
tal que la información cuántica del sistema se almacena en sí mismo. La
información de este vector Ket puede verse como un vector columna. Un Ket nos ayudaa
definir el estado de un sistema físico. Si tenemos dos estados cuánticos distintos y
entonces el Ket:
(*)
Dónde. , es un nuero complejo. (Mendoza Vázquez, 2010)
Bra (Dual)
Dirac definió un vector bra como una función lineal que asocia un número complejo a todo
ket de mediante el producto escalar. Asumimos que para cada ket existe un bra, y lo
denotamos como . El bra es llamado el dual del vector ket. Entonces se puede referir al
vector bra como un vector renglón, permitiendo así el producto de un vector renglón
con un vector columna .
El bra asociado al ket anterior (*) está dado por:

La norma del ket es real, no negativo, y se define como: , donde la
norma es igual cero únicamente si el ket es cero.
El dual de un vector , denotado por , es un vector transpuesto de con los
elementos sustituidos por sus conjugados. O sea, (Lavor, 2006)
Producto Interno
El producto interno de un par de vectores , es un número complejo denotado por:

Donde . Si su producto interno es cero entonces los vectores son ortogonales
15
.
(Mendoza Vázquez, 2010)
Producto Externo
Se define el producto externo como:

Que denota un operador que mapea el ket a otro ket mediante el bra

Donde . (Mendoza Vázquez, 2010)
Una definición realmente simple y concisa, es extraída de (Lavor, 2006), que dice:
Dados dos vectores , el producto interno y el producto externo
está definido respectivamente, por

Note que son vectores “columna” y son vectores “fila”.
Producto Tensorial
(D. Blanco, 2010) señala que el producto tensorial es una forma de combinar espacios,
operadores y vectores. Suponiendo que y son espacios de Hilbert de dimensión y

15 Vectores que formar un ángulo de 90°.
37

respectivamente. Entonces el espacio generado por el producto tensorial es un
nuevo y más grande espacio de Hilbert de dimensión . El producto tensorial de dos
vectores y cuyos espacios son y respectivamente es un vector en
denotado como . Suponiendo que A y B son dos operadores lineales sobre
y respectivamente entonces es el operador lineal
16
en definido por

Para tratar estados con más de un q-bit, precisamos del concepto de producto tensorial.
Para el nuestros propósitos, definimos el producto tensorial , entre las matrices
y , como la matriz
,
Donde es el elemento de la fila y de la columna de . Note que la dimensión de la
matriz es y que el producto tensorial no es conmutativo. (Lavor, 2006)
2.2.1. Espacios de Hilbert
El estado de un sistema cuántico particular se representa mediante un rayo
17
de un espacio
vectorial complejo llamado Espacio de Hilbert. (Guzmán Estrada, 2004)
Por un espacio de Hilbert siempre se entenderá un espacio vectorial complejo
dimensionalmente finito con un producto interno lineal conjugado en la primera
variable y lineal en la segunda. (Pantaleón Martínez, 2003)
Es un espacio vectorial definido sobre los complejos, es decir, cumple con las propiedades
que definen un espacio vectorial cuyo campo es el conjunto de los complejos.
En este espacio es posible definir un producto interno, que no es más que un mapeo
de un par ordenado de vectores en el campo complejo asociado al espacio, y que satisface
las siguientes propiedades:
Positividad: , la igualdad se cumple si
Linealidad:

16 Sean y espacios vectoriales reales. Una trasformación lineal de en es una función que asigna a
cada vector un vector único y que satisface, para cada y en y cada escalar .(Las
trasformaciones lineales con frecuencia se llaman operadores lineales)
17 El rayo es una clase de equivalencia de vectores que difieren por la multiplicación por un escalar complejo.
El estado del sistema está determinado por un representante de esta clase de equivalencia cuyo módulo es

Simetría:
Es completo en la norma . Esto es importante en los espacios funcionales
de dimensiones infinitos; asegura la convergencia de ciertas expansiones en autofunciones,
el análisis de Fourier de los vectores. (Guzmán Estrada, 2004)
2.2.2. El Qbit
La palabra qubit es una abreviatura de quantum bit, y como es lógico a partir de su nombre,
su papel es análogo al del propio bit en computación clásica, es decir, la unidad básica de
información en esta clase de ordenadores.
El qubit, como el bit, es antes de nada un objeto matemático. Aunque sea utilizado a partir
de objetos físicos en un contexto real, el asunto de pensar en él como una entidad abstracta
nos otorga la ventaja de que, con independencia de la manera que empleemos para utilizar
un qubit, ya sea mediante los estados de polarización de un fotón o el nivel de excitación de
un electrón, nuestro estudio será el mismo, y la teoría en torno a él no variará.
Del mismo modo en que un bit posee un estado, 0 o 1, un qubit también posee estados. Dos
estados análogos para un qubit son los estados y . La diferencia principal entre un bit
y un qubit es que éste último puede además existir en una superposición de estos dos
estados, lo que se escribe por medio de combinaciones lineales:

Los números y son números complejos, pero en la mayoría de los casos pueden
suponerse como reales.
Desde un punto de visto algebraico, un qubit es un elemento de un espacio vectorial de
dimensión dos, donde una base de ese espacio son los estados y . El hecho de que se
pueda definir un producto escalar de manera natural otorga de hecho a este espacio la
estructura de espacio de Hilbert. Dicho espacio queda definido si consideramos que los
estados y forman no sólo una base
18
, sino una base ortonormal
19
. De ese modo el
producto escalar de dos elementos cualesquiera de este espacio queda completamente
definido a partir de sus coordenadas. (López Muñoz, 2007)
Un bit cuántico o qubit es típicamente un sistema microscópico, como un átomo, un espín
nuclear o un fotón. Los estados booleanos 0 y 1 se representan por un par fijo de estados
perfectamente distinguibles de un qubit (por ejemplo, las polarizaciones horizontal y

18 Conjunto finito de vectores , para un espacio , que son linealmente independiente y generan
un espacio .
19 Conjunto de vectores, en el cual cada par de ellos es ortogonal ya además cada uno ellos tiene norma 1.
39

vertical de un fotón: , ). Un qubit también puede existir en un continuo de
estados intermedios o superposiciones, representados matemáticamente por combinaciones
lineales complejas de los estados base y . (H. Bennett & P. DiVincenzo, 2003)
Un qubit se puede ver como un sistema con dos estados posibles tal cómo el spin de un
electrón, que puede ser o o como un fotón polarizado “horizontal” o
“verticalmente”. De esta forma, un sistema de qubits tendrá disponibles estados
cuánticos mutuamente ortogonales. (Vela Llausí, 2009)
El qubit es un estado cuántico que pertenece a un estado de espacio de estados de
dimensión 2. (Coelho Quintino, 2010)
2.2.3. Representación y medición del estado de un Qbit
El espacio de estados del qubit se puede representar mediante un espacio vectorial
complejo bidimensional de módulo 1. Equivalentemente, se pueden representar puntos en
la superficie de una esfera; esta superficie se llama esfera de Bloch. Cada estado del qubit
corresponde a un punto de la superficie de una esfera de radio unidad. Esto esencialmente
significa que un qubit tiene dos grados de libertad locales. Estos grados de libertad podrían
ser la longitud y latitud, o como es más habitual, dos ángulos y en coordenadas
esféricas, como se muestra en la figura:
Figura 2.11: Representación esquemática de coordenadas esféricas.

Fuente: Extraído de (Moret Bonillo, 2013)
Si se asigna el estado al “polo norte” de la esfera, el estado correspondiente es: