Download (1/2) ¿Qué es la Computación Cuántica? (2

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