matemático

Introducci´ n a la computaci´ n cu´ ntica
o
o
a
Salvador E. Venegas Andraca
Tecnol´ gico de Monterrey Campus Estado de M´ xico
o
e
http://www.cem.itesm.mx/dia/escuelaverano
svenegas@itesm.mx, sva@mindsofmexico.org y salvador.venegas@gmail.com
Julio de 2007

1

1

Introducci´ n
o

La mec´ nica cu´ ntica es la rama de la f´sica que describe el comportamiento de la naturaleza aesa
a
ı
calas muy peque˜ as (por ejemplo, el comportamiento de los atomos). La teor´a de la computaci´ n
n
´
ı
o
se encarga de estudiar si un problema es susceptible de ser resuelto utilizando una computadoa, as´
ı
como la cantidad de recursos (tiempo, energ´a) que se debe invertir en caso de existir soluci´ n. En
ı
o
consecuencia, la computaci´ n cu´ ntica hace uso de la mec´ nica cu´ntica con el objetivo de incremeno
a
a
a
tar nuestra capacidad computacional para el procesamiento de informaci´ n y soluci´ n de problemas.
o
o
Por otra parte, la teor´a de la informaci´ n cu´ ntica estudia los m´ todos, capacidades y l´mites que las
ı
o
a
e
ı
leyes de la f´sica imponen en la transmisi´ n y recuperaci´ n de informaci´ n.
ı
o
o
o
El estudio formal de lacomputaci´ n cu´ ntica comenz´ con las preguntas que Richard Feynman
o
a
o
plante´ sobre dos temas: 1) la posibilidad de simular sistemas cu´ nticos, y 2) las leyes de la f´sica
o
a
ı
que caracterizan al proceso de calcular [92, 93]. A partir de ese trabajo, la computaci´ n cu´ ntica ha
o
a
avanzado a paso firme; por ejemplo, se ha definido formalmente la estructura de una computadora
cu´ ntica[3], se han encontrado resultados espectaculares como el algoritmo de Shor [4] (capaz de
a
factorizar un n´ mero entero muy largo en tiempo razonable utilizando una computadora cu´ ntica
u
a
[4, 7]) y el algoritmo de Grover [5] (este algoritmo encuentra elementos en conjuntos desordenados
de forma m´ s eficiente que cualquier algoritmo posible ejecutado en computadoras convencionales
a
[5,7]), y se ha dise˜ ado una teor´a y pr´ ctica de la criptograf´a usando las propiedades de la f´sica
n
ı
a
ı
ı
cu´ ntica [6]. En el futuro mediato, la computaci´ n cu´ ntica tendr´ gran impacto en la industria de la
a
o
a
a
computaci´ n y el desarrollo de protocolos de criptograf´a y seguridad computacional [12–14].
o
ı
La computaci´ n y la informaci´ n cu´ nticas representan un retote´ rico y experimental por la
o
o
a
o
cantidad y complejidad de problemas a resolver. A pesar de dichos retos, los avances realizados hasta
ahora permiten ya pensar en aplicaciones de esta disciplina en areas del conocimiento tales como la
´
Inteligencia Artificial, el Reconocimiento de Patrones [16–23, 91] y la Bioinform´ tica [24–26]. De
a
hecho, la computaci´ n cu´ ntica ha dado yasus primeros frutos en la industria pues desde 2003 hay
o
a
un sistema de criptograf´a cu´ ntica disponible en el mercado [27, 30], y los experimentos realizados
ı
a
en diversos laboratorios (por ejemplo [28, 29]) ofrecen resultados muy prometedores.
Universidades de prestigio internacional como Oxford [31], Cambridge [32], Harvard [33], Viena
[34], Caltech [35] y MIT [36] llevan a caboinvestigaci´ n en estas disciplinas con financiamiento
o
p´ blico (Estados Unidos, Reino Unido, Alemania, Francia, Australia y Brasil, entre otros gobieru
nos) y privado (Lucent Technologies [37], Hewlett Packard [38], IBM [39] y Fujitsu [40], entre otras
empresas). La computaci´ n cu´ ntica es importante para los gobiernos debido a que la creaci´ n de
o
a
o
computadoras cu´ nticas implicar´la existencia de escenarios de alta vulnerabilidad (las computadoa
a
ras cu´ nticas ser´ n capaces de descifrar, en horas o minutos, los c´ digos de encriptaci´ n que hoy
a
a
o
o
tomar´a mucho tiempo resolver. En consecuencia, la confidencialidad de mensajes electr´ nicos se
ı
o
ver´ afectada). Por su parte, la industria del c´ mputo ha invertido recursos sustanciales en esta esa
o...