Tesis

Algunos Fundamentos de Teor´ de la ıa Computaci´n Cu´ntica o a
Jos´ Hugo Max Nava Kopp e 30 de Abril 2006

2 Resumen La computaci´n cu´ntica es una materia interdisciplinaria de reciente creaci´n, o a o por lo que es fecunda en temas de investigaci´n. o Los mejores pensadores de la historia captan y sacan provecho del zeitgeist. Las m´quinas forman una buena parte de este aire de la ´poca. Elreloj a e propag´ un pensamiento mecanicista en los cient´ o ıficos de su ´poca, siendo e Newton el mejor ejemplo, que cre´ una teor´ con una visi´n completamente o ıa o determinista y s´ ıncrona del Universo. La m´quina de vapor hizo lo propio en a su ´poca incrustando en las mentes de los cient´ e ıficos la idea de transferencia de calor, dando lugar a la teor´ de la termodin´mica. ıa a Hoy en d´tanto m´dicos, bi´logos y f´ ıa, e o ısicos utilizan a la computadora como la analog´ por excelencia en cada una de sus ´reas. La idea de computadora ıa a influy´ a Shannon [Shannon, 1948] a encontrar la equivalencia perfecta entre o energ´ e informaci´n. De tal manera que ahora sabemos que todo proceso ıa o f´ ısico es un procesamiento de informaci´n. Todo proceso es una computadora. o ¿Qu´ tipode computadora? es algo que se pregunt´ impl´ e o ıcitamente Feynmann en [Feynmann, 1982]. Hizo notar que, ciertamente, no son como nuestras computadoras de escritorio. No son siquiera como la m´quina ideal a detr´s de todas ellas: la M´quina de Turing. Si los procesos f´ a a ısicos tuvieran que ser explicados en t´rminos de un procesamiento de informaci´n como el e o que posee la M´quina deTuring, muchos procesos, como la interacci´n grava o itacional entre tres cuerpos en movimiento no podr´ ser posibles. Ser´ ıan ıa tan lento el procesamiento de la informaci´n, que los cuerpos se mantendr´ o ıan inm´viles por per´ o ıodos inmensos de tiempo, en espera a que el procesamiento de informaci´n se realizara. o El procesamiento cl´sico de informaci´n que es el procesamiento que tiene a olugar en el mundo descrito por la teor´ de Newton, y que es el aprehendido ıa por la M´quina de Turing, tiene limitantes bien conocidas. El procesamiento a cu´ntico de informaci´n, por otro lado, cuenta con caracter´ a o ısitcas que el cl´sico no cuenta. Algunas de estas caracter´ a ısticas le permiten manejar una cantidad de informaci´n no representable en el mundo cl´sico. A manera de o a pruebafehaciente de la superioridad cu´ntica sobre la cl´sica, en la actualia a dad existen un par de algoritmos que demuestran la ventaja computacional 2

3 cu´ntica [Shor, 1995], [Shor, 1996]. a En general las teor´ reciben un tratamiento muy diferente cuando se enıas cuentran en su etapa descriptiva que cuando se encuentran en la etapa de puestas en marcha para la humanidad. Pero, hist´ricamente lasm´quinas o a ligadas a las teor´ han aparecido simult´neamente o incluso antes que la ıas a teor´ misma. La computadora cu´ntica es una excepci´n a esta regla. ıa a o La etapa descriptiva para la computaci´n cu´ntica tuvo lugar de 1900 a o a 1950. Hoy en d´ nos encontramos en la etapa de puesta en marcha. Se ıa estima que para el 2020 deber´ ıamos ser capaces de tener una funcionando. El hecho depasar de teor´ de la mec´nica cu´ntica a teor´ de la computaci´n ıa a a ıa o cu´ntica, a˜ade el enfoque de cient´ a n ıficos e ingenieros de la computaci´n a la o mec´nica cu´ntica. Este enfoque incluye varios formalismos con los que los a a cient´ ıficos de la computaci´n gustamos de ver nuestro mundo, como son una o l´gica y un aut´mata, siendo la m´quina un caso aplicado (implementaci´n) o o a ode estas dos cosas. Asimismo, existe la necesidad indiscutible por un lenguaje de computaci´n. o En la actualidad se est´ trabajando en obtener estas tres elementos para la a computaci´n cu´ntica [Selinger, 2003] [Van Tonder(1), 2003] [Van Tonder, 2004]o a [Sabry, 2003] [Knill, 1996] [Van Tonder(2), 2003]. Asimismo, debido a la interdependencia que existe entre ciencias de la computaci´n y...