Un modelo de computación no convencional:
La
Computación Cuántica
Juan Antonio Nepomuceno Chamorro
Un poco de historia:
Richard P. Feynman
D. Deutsch
Bernstein, Vazirani
Yao
Mikhael Shor
¿simulación de
procesos cuánticos?
ordenador siguiendo
leyes cuánticas
algoritmo de
factorización
(gran interés e inversión en la
Computación Cuántica debido a las
importantes consecuencias a nivel
criptográfico)
La teoría cuántica: el concepto de
superposición
A nivel atómico observamos comportamientos
que no coinciden con lo que la intuición nos
dice que debería ocurrir
La teoría cuántica explica estos
comportamientos
Proceso computacional cuántico:
computamos teniendo en cuenta “todas las posibles historias a la vez”
El carácter ondulatorio: Experimento de Young
La luz es un tipo de onda
La interferencia entre
ondas provoca el patrón
de rayado de la pantalla
El concepto de superposición:
Repetimos el experimento con un cañón
de electrones (los lanza a velocidad
constante)
Con una abertura
Con dos aberturas
El concepto de superposición:
Repetimos el experimento con un cañón
de electrones (los lanza a velocidad
constante)
Con una abertura
¿?
Con dos aberturas
No coincide con lo que la
intuición nos dice. ¿Electrones
individuales comportándose
como ondas?
El concepto de superposición:
¿Cómo explicamos el fenómeno?
Parece como si el electrón supiese diferenciar
cuando ambas aberturas están abiertas y
cuando no.
Se comporta como una onda, ¿interaccionan los
electrones unos con otros? NO: pues llegan por
separado a la primera pantalla.
Además, si intentamos medir
por qué abertura pasa el
electrón colocando un
aparato de medida, el
resultado del experimento
(con ambas abiertas) no es el
mismo: se pierde el efecto
“ondulatorio”.
El concepto de superposición:
Explicación de la Teoría Cuántica:
No podemos determinar qué hace el electrón, y
si lo intentamos, modificamos su comportamiento:
su posición es una indeterminación.
Aceptamos como mejor explicación:
• El electrón “se divide” en dos
• Interacciona consigo mismo
mundo real
explicación teoría cuántica
Superposición:
se considera que ocurren
las dos posibilidades.
(Si tratamos de medir se
destruye y sólo
contemplamos una en
particular).
Bit cuántico o qubit :


Superposición: debido a la incertidumbre de los procesos cuánticos
consideramos que ocurren todas las posibilidades
Observación: una vez que interactuamos la superposición se pierde y
sólo tenemos una de las posibilidades contempladas.
bit clásico: 0 o 1
Qubit: al estar en un proceso cuántico,
consideramos ambas posibilidades
|0i+|1i
(
2 H, espacio de Hilbert)
con ,  2 C amplitudes y tal que: ||2+||2=1
… y al observarlo obtendremos 0 con
probabilidad ||2 o 1 con probabilidad ||2
• indeterminación
• carácter ondulatorio
• distribución de probabilidad
Un proceso computacional de tipo cuántico consistirá básicamente en:
0
0
0
0
superposición
Preparar una superposición
adecuada:
|i=1|1i+2|2i+…+n|ni
con i 2 C, |i |2=1
Un proceso computacional de tipo cuántico consistirá básicamente en:
0
0
0
0
superposición
evoluciones unitarias
|i=1|1i+2|2i+…+n|ni
Someter dicha superposición a una
serie de evoluciones unitarias:
|i se transforma en |i mediante
una matriz (unitaria)
“evolución unitaria”
Un proceso computacional de tipo cuántico consistirá básicamente en:
0
0
0
0
superposición
|i=1|1i+2|2i+…+n|ni
evoluciones unitarias
Medición e interpretar
resultados
Observamos (medimos) la
superposición resultante:
t=0
obtendremos un elemento en
concreto con Auna
determinada
nivel subatómico
se cumplen a la
vez, simultáneamente, todas las
probabilidad
historias, calculemos a nivel
subatómico: “paralelismo cuántico”
100%
Modelo Cuántico vs. Probabilista:
Lente que refracta
al 50 %
¿En qué se diferencia el
modelo cuántico del
probabilista?
Espejo
reflectante
¿?
Modelo Probabilista:
1
2
0
La probabilidad de que se siga este camino
de computación es de 1 1 1
1
2
1
2
1
2
1
2
 
2 2
4
1
0
1
la probabilidad de obtener 0
en el proceso completo es de:
1
4

1
4

1
2
Modelo Cuántico vs. Probabilista:
1
1 
2
¿En qué se diferencia el
modelo cuántico del
probabilista?
1
1
1  11
2
1
2
1
0 
2
0
1
2
Modelo Cuántico:
1
2
1
|0
1
la amplitud es:
1
2
1
2

1
|1
|0
2
1
2
1
2
|1
la amplitud es: 
0
2
2
1
2
(y la probabilidad es
(– ½)2 = 1/4)
2
la probabilidad de obtener 0  1 1 
   0
en el proceso completo es de:  2 2 
(sumamos las amplitudes y
consideramos su cuadrado)
0 00
Modelo Cuántico vs. Probabilista:
Las diferencias:
1. “Filosofía de la superposición”
Interferencia: carácter
ondulatorio i.e.,
cancelación de dos
posibles computaciones
2. Interferencia
•
Transformaciones unitarias
•
Reversibilidad
árbol de computaciones :
Modelo Probabilista
Modelo Cuántico
Modelo Cuántico vs. Probabilista:
Las diferencias:
1. “Filosofía de la superposición”
2. Interferencia
Se puede seguir paso a
paso la computación
•
Transformaciones unitarias
•
Reversibilidad
un sólo camino de la computación
probabilidad
probabilidad al
medir



Modelo Probabilista
| c i |2
Si tratamos de
observar un paso
intermedio
destruimos el
proceso
Modelo Cuántico
Ejemplo1 : codificación
Codificamos los números de 0 a 15 :

Con bits: 0000= 0•23+0•22+0•21+0•20= 0
… o por ejemplo …
1001= 1•23+0•22+0•21+1•20= 9
Necesitamos 16 combinaciones diferentes para codificar las 16 posibilidades

Con qubits:
=
•23 +
•22 +
•21 +
•20
Codificamos de una sola vez todas las 16 posibilidades y podemos hacer
cálculos con todas a la vez
Pero, ¿si efectuamos una medición?
Ejemplo1 : codificación
Codificamos los números de 0 a 15 :

Con bits: 0000= 0•23+0•22+0•21+0•20= 0
… o por ejemplo …
1001= 1•23+0•22+0•21+1•20= 9
Necesitamos 16 combinaciones diferentes para codificar las 16 posibilidades

Con qubits:
=
•23 +
•22 +
•21 +
•20 =
=9
Al observar la superposición esta colapsa a un
estado en concreto: sólo tenemos en ese
momento un valor concreto.
Mientras no realicemos ninguna medición
estamos trabajando con los 16 valores
simultáneamente.
Ejemplo2 : resolviendo un problema de búsqueda
Sea una función ,f, que toma valores en {x0 , …, xn } y vale 0 en todos los puntos y 1 en
tan sólo uno. Se trata hallar ese valor en concreto.
¿encontrar y2 {x0 , …, xn } tq f(y)=1?
Codificamos la información de una
manera adecuada:
mediante un operador habitual en
transformaciones cuánticas:
Podemos representar así las
amplitudes de la superposición
inicial
|0i → (1 / √2n)  |xii (operador H-W)
Aplicamos un operador adecuado para obtener el resultado:
1) que discrimine en cierta forma la solución del resto
2) que haga que en el proceso de medición la solución sea
la que tenga más probabilidades de salir
Gn = -Hn Rn Hn Vf
Observamos y sacamos conclusiones
Ejemplo2 : resolviendo un problema de búsqueda
¿encontrar y2 {x0 , …, xn } tq f(y)=1?
|0i codificamos la información
Gn operador cuántico:
1) DISCRIMINA
2) RESALTA
(un solo paso de computación)
Observamos y obtenemos con más probabilidad
la solución que el resto (probabilidad controlada)
y=xi
(y lo obtenemos con una
probabilidad de |ci|2)
Algoritmos Cuánticos: (son un tipo particular de algoritmos probabilistas)
Básicamente hay de dos tipos:

De búsquedas en base de datos sin estructura o “consulta
a oráculos”


Tipo Shor: que sacan partido de comportamientos de tipo
periódico por medio de la Transformada Cuántica de
Fourier


Algoritmo de Grover, …
Algoritmo de factorización de Shor, …
(Simulaciones Cuánticas) …
¿y la implementación?
Se estima que podremos llegar a tener un ordenador
cuántico en los próximos 20 o 30 años:
en 2001 IBM consigue factorizar n=15 utilizando el
algoritmo de Shor con un ordenador de 7 qubits
Nace la Criptografía Cuántica
Nuevas preguntas, nuevos problemas, nuevos
paradigmas …
… etc…


Circuitos Cuánticos…
para qué servirán los ordenadores cuánticos o
aspectos de teoría de la complejidad

Hacia un Software Cuántico

Nuevos paradigmas

… etc …
Descargar

Document