Reporte19

Introducción al modelo cuántico de
computación

Grupo de Computación Cuántica

TECHNICAL REPORT Nº 19
Junio 2003

Grupo de Computación Cuántica

Dep. Matemática Aplicada. E.U. Informática Ctra. de Valencia Km. 7, 28031 Madrid, Spain e_mail: jglopez@eui.upm.es

Departamento de Matemática Aplicada E.U. Informática. U. Politécnica Madrid Ctra. de Valencia Km. 7
28031 Madrid, EspañaIntroduccio´n al modelo
cu´antico de computacio´n∗

Grupo de Computacio´n Cua´ntica†

3 de junio de 2003

Abstract

En este art´ıculo introducimos el modelo cuantico de computacio´n que siguen la mayor´ıa de los in- vestigadores que trabajan en este tema. Su principal caracter´ıstica es la capacidad para realizar simultaneamente un nu´mero exponencialde operaciones. Esta propiedad, denominada paralelismo
cuantico, permitio´ a P. W. Shor disen˜ar un algoritmo polinomial para factorizar nu´meros enteros. Este resultado es quiza´s el hito mas notable de la computacion cuantica. Sin embargo, es preciso mencionar que se trata de un modelo de computacio´n teorico. Hasta ahora no se han construidoordenadores cuanticos que puedan aplicar este modelo de computacio´n, aunque existe una intensa actividad investigadora en esta l´ınea.

1 Introduccio´n

La computaci´on cu´antica empez´o a desarrollarse en la d´ecada de los ochenta a ra´ız de las propuestas
de Paul Benioff, David Deutsch y Richard Feynman. En 1982 Benioff [3] y Feynman [7]sugirieron independientemente que, dado el elevado coste computacional del c´alculo de la evoluci´on de sistemas
cuanticos, la evoluci´on de estos sistemas se podr´ıa considerar como una herramienta de c´alculo m´as que como un objeto a calcular. Poco despu´es, en 1985, y tambi´en de forma independiente Deutsch [5] propone
la bu´squeda de un ordenador que sea capaz de simulareficientemente un sistema f´ısico arbitrario. La conjunci´on de todas estas ideas han conducido a la concepci´on actual de ordenador cu´antico.

Cuestionar el sistema de computaci´on cl´asico, que cuenta con una s´olida base te´orica y con el aval de infinidad de aplicaciones en todos los ´ambitos de la vida cotidiana, s´olo tiene sentido si el modelo que
sepropone como alternativo es potencialmente mejor que el actual. Efectivamente as´ı lo hacen Benioff, Deutsch y Feynman, fundamentando sus propuestas sobre la posibilidad de que los sistemas cu´anticos tengan mayor potencia de c´alculo que los cl´asicos. El argumento que todos utilizan para apuntar esta posibilidad es el hecho de que la simulaci´on de un ordenadorcu´antico (sistema cu´antico) en un ordenador cl´asico requiere una gran cantidad de operaciones.

El principal m´etodo para aumentar la capacidad de c´alculo de un ordenador cl´asico es el procesamiento
en paralelo. Los ordenadores que soportan este esquema de programaci´on disponen de varios cientos o miles de procesadores. Sabemos que la capacidad de almacenamiento de informaci´ony la capacidad de
calculo de un ordenador son proporcionales al nu´mero de celdas de memoria y al nu´mero de procesadores respectivamente, es decir, al “taman˜o” del ordenador. Entonces la capacidad de un ordenador cl´asico (de almacenamiento y de c´alculo) crece linealmente con respecto a su taman˜o.

En un ordenador cu´antico la situaci´on cambia por completo, hasta el punto quesu capacidad crece exponencialmente con respecto a su taman˜o. Este hecho, estrechamente relacionado con el principio
de superposici´on de la Mec´anica Cu´antica, se denomina paralelismo cu´antico. Llamamos qubits o bits
cuanticos a los sistemas cu´anticos elementales, es decir, a los sistemas cu´anticos de dos estados. Los sistemas cuanticos de n...