Download (1/2) ¿Qué es la Computación Cuántica? (2
Document related concepts
Transcript
Introducción a la Computación Cuántica ¿Qué es la Computación Cuántica? (1/2) Disciplina nacida de la física y la computación, cuyo objetivo incluye: a) [Para computer scientists] Crear computadoras y algoritmos que aprovechen las propiedades cuánticas de la materia. Se busca aumentar la capacidad de las computadoras para resolver problemas y procesar información. Salvador Elías Venegas Andraca Tecnológico de Monterrey, campus Estado de México Centro de Computación Cuántica, universidad de Oxford ¿Qué es la Computación Cuántica? (2/2) b) [Para físicos] Desarrollar herramientas que permitan aguzar nuestra intuición en el estudio de la mecánica cuántica. Razones para estudiar y hacer investigación en computación cuántica (1/2) c) [Para cualquier científico] En nuestro intento por controlar sistemas cuánticos individuales, tendremos un laboratorio para aprender más sobre la estructura del universo. Desde la ciencia: d) [Para la industria del cómputo y comunicaciones] • Conocer las leyes que la naturaleza impone en nuestra capacidad para hacer cómputo. Comprender y aprovechar los efectos de la miniaturización a escala atómica/sub-atómica. • Aumentar nuestro entendimiento sobre la naturaleza y sus leyes (en particular, la mecánica cuántica). Razones para estudiar y hacer investigación en computación cuántica (2/2) Teoría de la computación clásica (1/3) Objetivo Desde la tecnología y su comercialización: • La miniaturización alcanzará en algunos años escalas atómicas (por ejemplo, transistores de 45 nm fabricados por Intel). En consecuencia, es necesario aprender a controlar sistemas cuánticos individuales, para así poder usarles en el procesamiento de información. Conocer las capacidades y límites fundamentales de los procedimientos finitos (algoritmos) usados en la solución de problemas. La teoría de la computación clásica se divide en: • Teoría de autómatas. Estudio de diversos modelos de computación. • Para que México sea productor, y no un simple consumidor, de tecnología computacional y comunicaciones (entregar artículos). • Teoría de la computabilidad. Dado un problema, ¿puede ser éste resuelto o no con un procedimiento finito? • Teoría de la complejidad. Supongamos que un problema puede ser resuelto usando un algoritmo. En ese caso, ¿cuántos recursos (tiempo/número de compuertas) hay que invertir en la solución? 1 Teoría de la computación clásica (2/3) Teoría de la computación clásica (3/3) ¿Cómo nace la teoría de la computación clásica? En respuesta a las preguntas planteadas por Hilbert, en 1936 Alan Turing propuso lo siguiente [1]: En los primeros años del siglo XX, David Hilbert preguntó si era posible realizar una formulación rigurosa de la matemática. En particular, esta pregunta llevó a Hilbert a formular el Problema de la Decisión (Entscheidungsproblem o Decision problem), el cual se puede enunciar así: a) Definición de la expresión “método sistemático”, la cual es equivalente a “procedimiento finito” b) Un modelo de computación conocido como “Máquina de Turing” ¿Existe un procedimiento el cual permita determinar, en un nú número finito de pasos, si un enunciado creado con ló lógica de primer orden1 es vá válido? El concepto de procedimiento finito, hoy equivalente al de algoritmo, se encuentra en el corazón del pensamiento de Hilbert. 1La lógica de primer orden es un formalismo de razonamiento lógico deductivo. c) Un modelo de computación conocido como “Máquina Universal de Turing” d) La tesis Church-Turing en la que se postula la equivalencia de máquinas de Turing con los procedimientos finitos para la solución de problemas Máquinas de Turing Teoría de la complejidad Definición. Máquina Determinística de Turing (MDT). Una MDT se compone de un sistema de control de estados, una cabeza de lectura/escritura y una cinta infinita hecha de casillas numeradas …, -3,-2,-1,0,1,2,3… Un programa para una MDT Se compone de: Símbolos de la cinta {S} Estados de la máquina {Q} Función de transición Lo siguiente suena a trabalenguas pero es importante: Ejemplos Problema sencillo: determinar si un número es divisible entre 4. Problema difícil: factorizar un número entero de tamaño arbitrario. ¿Cómo definir/caracterizar matemáticamente el adjetivo “difícil”? 1. Escogiendo un modelo computacional (generalmente, una máquina universal de Turing) 2. Cuantificando el uso/consumo de recursos (tiempo/número de compuertas) invertidos en un algoritmo La máquina universal de Turing (MUT) es una máquina de Turing que puede simular a cualquier máquina de Turing. Subrayemos que: Sí, es importante tomar en cuenta dichas propiedades físicas. Algunas razones son: La teoría de la computación clásica es una teoría matemática que NO toma en cuenta las propiedades físicas de los sistemas en los que se implantan algoritmos. ¿Es esto importante? 1. Gasto energético (conjunto universal de compuertas) OR AND NOT Las primeras dos compuertas tienen dos bits de entrada y uno de salida. Al procesar información con estas dos compuertas es necesario borrar un bit. 2 De acuerdo al principio de Landauer [2], el acto de borrar información implica un gasto energético: Principio de Landauer. Suponga que una computadora borra un bit de información. Entonces, la cantidad de energía disipada en el medio ambiente es al menos igual a KTln2, donde K es la constante de Boltzmann y T es la temperatura de la computadora. Luego, parte del calor que desprende un microprocesador y, en general, una computadora, se debe al acto de borrar información. 3. Simulación de sistemas físicos La simulación computacional (clásica) eficiente (i.e. con complejidad temporal polinomial) de sistemas físicos no siempre es posible. En particular, la simulación computacional de sistemas físicos gobernados por las leyes de la mecánica cuántica se puede convertir en un problema de orden exponencial (i.e. no polinomial), respecto del número de partículas a simular [4]. 2. Ley de Moore La complejidad de un circuito integrado se duplica cada 18-24 meses y los costos se mantienen La complejidad de un circuito integrado es directamente proporcional al número de transistores en dicho circuito. Luego, una consecuencia directa de la ley de Moore es que el tamaño de los transistores decrece constantemente. Dado este constante avance en la miniaturización, se espera que en algunos años el tamaño de transistores y demás componentes alcance escalas atómicas [3]. ¿Es posible crear un modelo computacional, esto es, un modelo matemático para la ejecución de algoritmos, que al implantarse en un sistema físico: 1)No gaste energía innecesariamente, 2) tome en cuenta los efectos de la miniaturización, y 3) pueda simular sistemas cuánticos? Sí lo es. El modelo en cuestión es una combinación de dos teorías: computación reversible y mecánica cuántica. Modelo de computación reversible (1/4) Modelo de computación reversible (2/4) Ejemplo de compuerta reversible: compuerta de Toffoli Definición. Reversibilidad. Suponga que estamos ejecutando un proceso de cómputo E y que estamos en el paso ei de dicho proceso. En el argot computacional, se dice que el proceso E es reversible si y sólo si después de ejecutar el paso ei+1 es posible calcular, de nueva cuenta, el paso ei. Definición. Compuerta reversible. Objeto matemático que lleva a cabo una operación lógica reversible. Nota obvia pero importante: las compuertas reversibles usan el mismo número de bits en la entrada y en la salida. X1 X2 X3 X1 T X2 F= X3 XOR (X1 AND X2) Definición. Modelo de computación reversible. Modelo matemático creado para la ejecución de algoritmos utilizando compuertas reversibles. 3 Modelo de computación reversible (3/4) Modelo de computación reversible (4/4) Tabla de verdad de la compuerta de Toffoli Entrada X1 0 0 0 0 1 1 1 1 X2 0 0 1 1 0 0 1 1 La compuerta de Toffoli es universal, esto es, para cualquier función computable Salida X3 0 1 0 1 0 1 0 1 X1 0 0 0 0 1 1 1 1 X2 0 0 1 1 0 0 1 1 F f(X1, X2, …, Xn) 0 1 0 1 0 1 1 0 existe un circuito M creado sólo con compuertas de Toffoli tal que M calcula el valor de f para cualquier combinación de variables X1, X2, …, Xn [5,6]. ¿Existen sistemas físicos cuyo comportamiento temporal (evolución) sea como el de una compuerta reversible? Entonces, y de acuerdo a lo visto hasta ahora, el desarrollo de computadoras cuánticas permitirá: Respuesta: Sí. Los sistemas (cerrados) que trabajan de acuerdo a las leyes de la mecánica cuántica. 1) Aprovechar los efectos cuánticos que la miniaturización trae consigo, y 2) Ejecutar algoritmos bajo un esquema de mínimo consumo energético. Breve introducción a la mecánica cuántica (1/9) Breve introducción a la mecánica cuántica (2/9) Sea H un espacio de Hilbert (i.e. un espacio vectorial complejo con producto interno) y sea |ψ> un elemento de H. Entonces, iii) La superposición es también propiedad de sistemas clásicos, pero algunas de las consecuencias de la superposición en mecánica cuántica NO tienen contraparte en el mundo clásico, por ejemplo: Postulado 1. Vector de estado. A cada sistema físico cerrado asociaremos un espacio de Hilbert H. El sistema físico está totalmente descrito por un vector de estado ψ , el cual es un vector unitario de H. i) La dimensión de H depende de los grados de libertad de la propiedad física en consideración. ii) El postulado 1 implica que cualquier combinación lineal de vectores de estado es también un vector de estado [7]. Este hecho se conoce con el nombre de principio de superposición. 1) Experimento doble rendija 2) Sistemas en entanglement Para profundizar en este tema, estudiaremos un caso sencillo pero fundamental en computación cuántica: el qubit. 4 Breve introducción a la mecánica cuántica (3/9) Breve introducción a la mecánica cuántica (4/9) Primus inter pares: definición de qubit. Primus inter pares: definición de qubit. En la teoría clásica de la computación, la información se almacena y manipula en forma de bits. La estructura matemática-física de un bit es simple: basta con definir dos valores (por ejemplo, 0 y 1) y relacionar dichos valores con dos distintos resultados de la medición de un sistema físico clásico (i.e., no cuántico). La contraparte cuántica del bit es el qubit. Un qubit es un sistema cuántico con al menos dos estados distinguibles y es la unidad básica de almacenamiento y procesamiento de información. Ejemplos: Un electrón (spin up – spin down) Un fotón (polarización vertical-horizontal) Ejemplo tradicional: la diferencia de potencial entre el emisor y el colector de un transistor bipolar Si la diferencia de potencial entre E y C es menor que 0.5V entonces se registra un ‘0’ lógico. Si la diferencia de potencial entre E y C es mayor que 4.5V entonces se registra un ‘1’ lógico. Breve introducción a la mecánica cuántica (6/9) Breve introducción a la mecánica cuántica (5/9) Primus inter pares: definición de qubit. Primus inter pares: definición de qubit. Usando la base computacional Un qubit se puede representar matemáticamente como un vector unitario en un espacio de Hilbert H bidimensional: B ={ p , q } Def. Sea H un espacio de Hilbert bidimensional y una base de H. La forma general de un qubit ψ , usando la base B , se escribe de la siguiente manera: donde a, b θ 2 ψ = cos ,ψ, 2 ψ = a p +b q y son números complejos que cumplen con a + b =1 2 2 ψ podemos escribir ,0, z C ={0 , 1} como θ 1 2 0 + eiφ sen Los ángulos θ y Φ definen un punto en la esfera de Bloch. Nota importante: N x A diferencia de los bits, NO se puede hacer copias de qubits en lo general [8,9] (No-cloning theorem). ,1, Breve introducción a la mecánica cuántica (7/9) Breve introducción a la mecánica cuántica (8/9) Postulado 3. Medición de un sistema cuántico. Postulado 2. Evolución de un sistema cuántico. La evolución de un sistema cuántico cerrado con vector de estado |ψ> se describe a través de un operador unitario Û . El estado del sistema cuántico en el tiempo t2 respecto del tiempo t1 es dado por ψ t2 = Uˆ ψ La medición en mecánica cuántica es un proceso inherentemente probabilístico. Por ejemplo, si tenemos n qubits con ecuación 1 (0 + 1 ) 2 ψ = Y usamos operadores (proyectores) de medición t1 Los operadores unitarios Û son reversibles, i.e. Uˆ cualquier operador unitario Û . con resultados de medición −1 α y 0 0 y 1 1 β = Uˆ † existe para Entonces n 2 veces obtendremos α y n 2 veces obtendremos β Ejemplos: Operadores de Pauli, y el operador Hadamard. 5 Breve introducción a la mecánica cuántica (9/9) ¿Existe una versión cuántica de la máquina de Turing? Postulado 4. Estados cuánticos múltiples. Producto tensorial en notación de Dirac. El producto tensorial es un método para crear espacios vectoriales a partir de otros espacios vectoriales. Si tenemos n espacios vectoriales bidimensionales, el producto tensorial de estos espacios tendrá dimensión 2n . Sí. En [10], David Deutsch hizo dos contribuciones fundamentales a la teoría de la computación cuántica: 1) Proponer una máquina universal de Turing cuántica. 2) El principio de Church-Turing, una versión física (physics-oriented) de la tesis de Church-Turing. Principio de Church-Turing. Todo sistema físico finito puede ser perfectamente simulado por una máquina computadora universal, la cual también trabaja con recursos finitos. (Every finitely realizable physical system can be perfectly simulated by a universal model computing machine operating by finite means). Propiedades computación cuántica Entanglement ¿Qué es un entangled state/estado enmarañado? La computación cuántica hace uso de dos fenómenos en la creación de algoritmos: Superposición y entanglement 1) Experimento básico (ejemplo experimento: parametric down conversion). 2) Correlación que sólo se encuentra entre estados cuánticos (desigualdades de Bell). 3) Estados enmarañados vs estados producto. 4) Hay consenso sobre cómo cuantificar entanglement entre estados puros de dos sistemas cuánticos. En cualquier otro caso, el campo está abierto. 5) Dos medidas para cuantificar entanglement: medidas de Wootters y de von Neumann. Algunos logros en computación cuántica (1/2) 1. Algoritmos cuánticos •Algoritmo de Shor: factorización de números primos en tiempo polinomial [14]. •Algoritmo de Grover: Localización de un elemento en un conjunto desordenado en O(sqrt(n)) (el mejor algoritmo clásico tarda O(n)) [15]. •Algoritmos de búsqueda usando caminatas cuánticas [16]. Algunos logros en computación cuántica (2/2) ¿Productos comerciales? •Sistemas comerciales de criptografía y redes cuánticas: Idquantique http://www.idquantique.com/ (Suiza) Magiq http://www.magiqtech.com/ (EE. UU.) ¿Experimentos a gran escala? 2. Criptografía cuántica •Desencriptación de mensajes (encriptados) en tiempo polinomial: la generación de llave privada a partir de la pública es un problema de complejidad es equivalente a la de la factorización de número enteros de tamaño arbitrario [11,17]. •Detección de espías (eavesdropper) utilizando las propiedades de la mecánica cuántica (medición de estados cuánticos) [11]. •DARPA Quantum Network. Red de 6 nodos que conecta a las universidades de Harvard y Boston. La red transmite información a través de fibras ópticas y lo hace utilizando protocolos puramente cuánticos. •Tranmisión de información cuántica (fotones) a largas distancias. 6 Redes cuánticas (1/6) En redes de computadoras clásicas, la información se transmite de dos formas: 1. Copia de información entre sistemas físicos adyacentes Estudiemos ahora la forma en la que se transmite información en una red cuántica. 2. Desplazamiento, a lo largo de un canal, de un sistema físico con información. ¿Es posible utilizar estos esquemas para transmitir información entre sistemas cuánticos? Redes cuánticas (2/6) Redes cuánticas (3/6) 2. Desplazamiento de un sistema físico con información Candidatos: electrones, fotones e iones 1. Copia de información entre sistemas físicos adyacentes • Teorema de la no clonación (no-cloning theorem) [8,9] No es posible copiar estados cuánticos arbitrarios, i.e. no es posible llevar a cabo la operación Û ( ψ φ ) = ψ ψ Redes cuánticas (4/6) ¿Existe algún camino alternativo? - Transmitir información usando cualquier de estos sistemas físicos significa que debemos manipular estas partículas de forma individual. -Esta manipulación implica, con probabilidad no despreciable, que la partícula, entre en contacto con variables externas y, en consecuencia, que pierda información (decoherence) [11,12]. Redes cuánticas (5/6) El segundo paso consiste en que Bart se comunique clásicamente con Homero (por ejemplo, por teléfono) para que Homero pueda tomar su qubit, Sí, la teletransportación cuántica [13] |Ψ > Circuito Teletransportación Circuito Teletransportación (par EPR y compuertas) (par EPR y compuertas) La teletransportación cuántica se divide en dos pasos. El primero consiste en que el qubit que le pertenece a Bart interactúe con el circuito de teletransportación. |Ψ > Note que Bart YA NO tiene su qubit. La teletransportación cuántica NO es lo mismo que copiar qubits. Luego, no se viola el teorema de la no clonación. 7 Redes cuánticas (6/6) Comercial Nota aclaratoria: Segunda escuela mexicana de verano en computación e información cuánticas La teletransportación cuántica consiste en transferir información a través de un canal cuántico. Organizada por: Tecnológico de Monterrey y universidad de Leeds NO es lo mismo que transferir MASA. Fecha: 9 al 20 de julio de 2007 Sede: Tecnológico de Monterrey, campus Estado de México http://www.cem.itesm.mx/dia/escuelaverano/ http://www.mindsofmexico.org/sva svenegas@itesm.mx , sva@mindsofmexico.org Bibliografía (1/2) [1] Alan Turing. On Computable Numbers, with an Application to the Entscheidung Problem. Proceedings of the London Mathematical Society, 42 pp. 230-265 (1936-37). [2] Rolf Landauer. Irreversibility and Heat generation in the Computing Process. IBM Journal of Research and Development, 3 pp.183-191 (1961). [3] Seth Lloyd. Programming the Universe. Alfred A. Knopf (2006). [4] Richard P. Feynman. Simulating Physics with Computers. International Journal of Theoretical Physics, 21 (6/7) pp. 467-488 (1982) y The Feynman Lectures on Computation. Penguin Books (1999). [5] T. Toffoli. Reversible Computing. MIT Technical Report MIT/LCS/TM-151 (1980) [6] E. Fredkin and T. Toffoli. Conservative logic. International Journal of Theoretical Physics, 21 pp. 219–253 (1982). [7] C. Cohen-Tannoudji, B. Diu y F. Laloe. Quantum Mechanics, vols. 1 & 2. Wiley (1997). [8] D. Dieks. Communication by EPR devices. Physics Letters A 92(6) pp. 271-272 (1982). [9] W.K. Wootters y W.H. Zurek. A single quantum cannot be cloned. Nature, pp. 299-300 (1982). [10] D. Deutsch. Quantum theory, the Church-Turing Principle and the Universal Quantum Computer. Proceedings of the Royal Society of London, series A, 400(1818) pp. 97-117, (1985). Bibliografía (2/2) [11] The physics of quantum information. D. Bouwmeester et al, Eds. Springer (2000) [12] How to build a 300 bit, 1 Giga-operation quantum computer. A.Steane, quant-ph/0412165 (2004). [13] Teleporting an Unknown Quantum State via Dual Classical and Einstein-Podolsky-Rosen Channels. C.H. Bennett, G. Brassard, C. Crepeau, R. Jozsa, A. Peres, and W. Wootters, Phys. Rev. Lett. 70, pp 1895-1899 (1993). [14] P. Shor. Polynomial-Time Algorithms for Prime Factorization and Discrete Algorithms on a Quantum Computer. Proceedings of the 35th Annual Symposium on Foundations of Computer Science, pp. 124–134, IEEE Computer Society Press (1994). [15] .K. Grover. A fast quantum mechanical algorithm for database search. Proceedings 28th annual ACM Symposium Theory of Computing, pp. 212–219 (1996). [16] S.E. Venegas Andraca. Discrete Quantum Walks and Quantum Image Processing. Tesis de doctorado, universidad de Oxford (2006). [17] M.I. Nielsen e I.L. Chuang. Quantum Computation and Quantum Information. CUP (2000). 8