Curso: Computación y Criptografía Cuántica
Lección 3. Algoritmos Cuánticos
Dra. Alfonsa García, Dr. Francisco García, Dr. Jesús García - 23/07/2014
En esta lección se presenta una introducción a los principales algoritmos que usan computación cuántica.
El curso completo se compone de tres lecciones:
Lección 1. Modelo de Computación Cuántica
Lección 2. Criptografía Cuántica
Lección 3. Algoritmos Cuánticos
Si deseas descargar las diapositivas del curso en formato pdf, o las soluciones a los ejercicios propuestos, puedes hacerlo desde esta dirección del Material de GIEMATIC (Grupo de innovación educativa).
Los tres vídeos de apoyo a las lecciones de este MOOC presentados por el Dr. Jesús García, son los siguientes:
También puedes ver estos vídeos del "Seminario de Introducción a la Computación y Criptografía Cuántica" directamente en YouTube desde sus correspondientes enlaces:
Seminario de introducción a la Computación y Criptografía Cuántica: 1
Seminario de introducción a la Computación y Criptografía Cuántica: 2
Seminario de introducción a la Computación y Criptografía Cuántica: 3
El tiempo recomendado para el seguimiento de esta lección y la realización de actividades propuestas es de 10 horas semanales durante dos semanas. Puedes ampliar la información consultando el libro Quantum Computation and Quantum Information [6].
Temario
- Apartado 3.1. Introducción
- Apartado 3.2. Primeros algoritmos cuánticos
- Apartado 3.3. Búsqueda no estructurada. Algoritmo de Grover
- Apartado 3.4. Transformada cuántica de Fourier
- Apartado 3.5. Algoritmo de Shor
- Apartado 3.6. Test de autoevaluación
- Apartado 3.7. Referencias bibliográficas y enlaces de interés
Objetivos
El objetivo de esta lección es presentar una introducción a los principales algoritmos cuánticos y en concreto:
- 1. Entender cómo el paralelismo cuántico se puede usar para realizar cálculos de forma más eficiente.
- 2. Ser capaz de describir circuitos cuánticos para la resolución de los problemas de Deustch, Deutsch-Jozsa y Simon.
- 3. Conocer el algoritmo de Grover y analizar su complejidad.
- 4. Conocer el algoritmo de Shor y analizar su complejidad.
APARTADO 3.1. INTRODUCCIÓN
Un algoritmo es un proceso encaminado a realizar una tarea específica.
Cada etapa de un algoritmo cuántico se especifica mediante una puerta cuántica, que no es otra cosa que una transformación unitaria en el espacio de Hilbert. Por tanto, el algoritmo se expresa mediante composición de transformaciones unitarias y en consecuencia siempre es reversible, porque toda transformación unitaria tiene inversa.
Representaremos los algoritmos mediante circuitos, que evolucionan de izquierda a derecha, en los que se representan las distintas puertas cuánticas usando los símbolos introducidos en la Lección 1.
Con frecuencia, muchos algoritmos de computación clásica incluyen etapas que se pueden concretar en la evaluación de una función sobre distintos parámetros de entrada. El paralelismo cuántico permite evaluar una función simultáneamente sobre todas las posibles cadenas de n bits, lo que supone un aumento exponencial de la velocidad de cálculo. El problema es que la información queda "oculta" en las amplitudes del estado cuántico resultante, y para acceder a ella se requiere una medición cuántica, que destruye parte de la información.
Generalmente los algoritmos cuánticos son probabilísticos y suele ser fácil utilizar el paralelismo cuántico. Lo difícil es conseguir que la probabilidad de obtener el resultado buscado sea grande.
Al estudiar la complejidad de los algoritmos cuánticos es habitual comparar la complejidad en el peor de los casos, con el mejor algoritmo clásico conocido, o, si el problema está resuelto, con el mejor algoritmo clásico posible.
En esta lección se presentan algunos algoritmos cuánticos que resuelven problemas clásicos con una importante ganancia computacional. El más relevante de ellos es el algoritmo de factorización de Shor [7]. Se trata del resultado más prometedor de la computación cuántica por lo que puede suponer de ruptura con los estándares actuales de seguridad criptográfica.
Aunque el ordenador cuántico aún tenga muchas dificultades tecnológicas, ya hay avances teóricos muy significativos en algorítmica cuántica y se han estudiado distintas posibilidades técnicas para implementar los algoritmos desarrollados. Además también se han diseñado algunos lenguajes de programación cuántica.
Cuestiones para investigar:
Busca información en [3] sobre las características del lenguaje de programación cuántica Quipper.
APARTADO 3.2. PRIMEROS ALGORITMOS CUÁNTICOS
Veremos en esta sección tres algoritmos de indudable importancia histórica, que intentan resolver problemas relativos a funciones booleanas. Recordemos que toda función boolena f de n bits en m bits se puede implementar mediante la puerta cuántica Uf
|
|
3.2.1 Problema de Deutsch: Dada una función booleana f: {0,1}-->{0,1}, se trata de ver si es constante (f(0)=f(1)) o no evaluándola una sola vez.
Es obvio que clásicamente hay que evaluar f(0) y f(1) para resolver el problema planteado. Sin embargo, cuánticamente sólo es preciso evaluar Uf una vez, gracias al paralelismo cuántico.
A continuación, se muestra el circuito que resuelve el problema y la evolución del estado de 2-qubit |00> según se van aplicando las transformaciones unitarias del circuito.
Introducimos la siguiente notación:
|
|
Para seguir adecuadamente la evolución del estado a lo largo del circuito hay que recordar que:
La medida del primer qubit del estado de salida se hace con la base B1. Si el resultado de la medida es 0 la función es contante y si es 1 no lo es.
Aunque generalmente los algoritmos cuánticos son probabilísticos, en este caso se obtiene un algoritmo determinista para resolver el problema, ya que se consigue la solución con probabilidad 1. Por tratarse de un problema de complejidad constante, no podemos sacar ninguna conclusión al compararlo con los algoritmos clásicos.
3.2.2 Problema de Deutsch-Jozsa: Dada una función booleana f: {0,1}n -->{0,1}, constante o balanceada, se trata de ver si es constante o es balanceada, evaluándola una sola vez.Es sencillo probar que clásicamente hay que evaluar f sobre la mitad más 1 de las cadenas de n bits para resolver el problema planteado. Sin embargo, cuánticamente sólo es preciso evaluar Uf una vez, para obtener la solución con probabilidad 1. Por tanto en la resolución de este problema, el modelo cuántico supone una ganancia exponencial.
A continuación se muestra el circuito que resuelve el problema y la evolución del estado de (n+1)-qubit, según se van aplicando las transformaciones unitarias del circuito.
 El |0> de la primera línea del circuito es ahora un n-qubit y W es la transformación de Walsh-Hadamard, que transforma el |0> en una superposición de todos los estados de la base Bn . |
|
Analicemos el resultado de la última medida suponiendo primero que f es constante y después que es balanceada. Si es constante, el estado final del n-qubit es |0> y si es balanceada es ortogonal a |0>.
Por tanto la medida final del n-qubit permite determinar si f es constante o balanceada con probabilidad 1.
3.2.3 Problema de Simon:
Determinar, con el mínimo número posible de evaluaciones, el periodo de una función f de (Z2)n en (Z2)n, periódica y 2 a 1.
Definiciones: (Z2)n es el espacio vectorial de las cadenas de n bits (con la suma módulo 2 bit a bit). Se dice que una función f de (Z2)n en (Z2)n es periódica de periodo T (donde T es una cadena de n bits) si para toda cadena k se verifica que f(T+k)=f(k) y se dice que es 2 a 1 si para toda cadena h de la imagen de f hay dos cadenas k1 y k2 tales que f(k1)=f(k2)=h.
Ejercicio 3.2.1
Pon un ejemplo de función periódica y 2 a 1 definida en (Z2)3.
El problema de Simon fue una de las primeras cuestiones que se resolvieron en computación cuántica con ganancia exponencial. Clásicamente, para resolver el problema es necesario evaluar f sobre la mitad más 1 de los elementos del dominio. Es decir, 2(n-1)+ 1 evaluaciones. Si queremos la solución con una probabilidad de error menor que ε, se puede conseguir con 2(n-1)/2 (1-ε)1/2 evaluaciones. Cuánticamente el problema se puede resolver con O(n-1) evaluaciones.
|
Algoritmo cuántico para el problema de Simon: 1. Inicializar el 2n-qubit |0>|0> 2. Aplicar Wn a los n primeros qubits 3. Aplicar Uf 4. Medir los n últimos qubits (resultado j=j1 ... jn) 5. Aplicar de nuevo Wn a los n primeros qubits 6. Medir los n primeros qubits. Devolver el resultado k=k1 ... kn |
|
El resultado final es un entero k (cadena de n bits) de modo que k·T=0.
Veamos la evolución del algoritmo:
La primera medida da como resultado cualquier valor de la imagen de f con probabilidad 1/2(n-1), por ser una función 2 a 1, y la segunda cualquier valor k, que cumple T·k=0, también con probabilidad 1/2(n-1).
Al aplicar el algoritmo evaluamos una vez la transformación unitaria Uf y obtenemos una ecuación lineal homogénea, T·k=0, con incógnitas (los bits de T) y coeficientes en el cuerpo Z2 (los bits de k).
Debemos repetir el algoritmo hasta obtener un sistema lineal homogéneo de rango n-1. La solución no nula de este sistema será el periodo de la función.
Ejercicio 3.2.2
Calcula la probabilidad de que, al aplicar n-1 veces el algoritmo cuántico que resuelve el problema de Simon, se obtenga un sistema de rango n-1.
APARTADO 3.3. BÚSQUEDA NO ESTRUCTURADA. ALGORITMO DE GROVER
Muchos problemas, que se pueden denominar problemas de búsqueda, se pueden plantear de la siguiente forma: Hallar x en un conjunto de posibles soluciones tal que la sentencia f(x)=1 sea cierta.
Un problema de búsqueda no estructurada es aquel para cuya resolución no se puede usar ninguna hipótesis relativa a la estructura del espacio de soluciones. Por ejemplo, una búsqueda en una lista alfabetizada, como la búsqueda del número de un usuario en la guía telefónica, es un problema de búsqueda estructurada. Mientras que la búsqueda en la misma guía del titular de un número concreto sería una búsqueda no estructurada.
En una búsqueda estructurada, se puede usar la estructura ordenada de la lista para construir algoritmos eficientes, pero en una búsqueda no estructurada lo habitual es comprobar aleatoriamente la veracidad de la sentencia.
En el modelo de computación clásico, para un espacio de búsqueda de tamaño N, sería necesario evaluar f un promedio de N/2 veces y N veces en el peor de los casos. Los algoritmos clásicos de búsqueda no estructurada requieren por tanto O(N) evaluaciones de f.
Lov K. Grover probó en 1996 (ver [4]) que un problema de búsqueda no estructurada, con solución única, se puede resolver cuánticamente con O(√N) evaluaciones de f.
Descripción del algoritmo:
Partimos de una lista de tamaño N. Supondremos, incrementando la lista si es preciso, que N=2n para algún n.
Trabajaremos con los índices de los elementos de la lista, es decir con números enteros x entre 0 y 2n -1 y queremos localizar x tal que f(x)=1.
La computación cuántica permite evaluar f simultáneamente sobre todos los posibles inputs, sin más que construir una superposición de todos los estados de la base ortonormal Bn, lo que se obtiene, a partir de |0>, con la transformación de Walsh-Hadamard.
El problema es que no se puede leer el resultado obtenido sin destruir el estado. La idea que aplicaremos es ir modificándolo de modo que se vaya incrementando la amplitud de la solución y disminuyendo la de aquellos x que no verifican f(x)=1. Así conseguiremos, al medir el registro resultante, tener un acierto con probabilidad alta.
|
|
Los pasos 2 y 3 algoritmo se deben repetir hasta conseguir que la probabilidad de fallo sea menor que una cota admisible prefijada.
Supongamos que s es el número buscado y que hemos realizado k iteraciones, en cada una de ellas el estado inicial Wn(|0>) se ha ido modificando, cambiando las amplitudes de cada uno de los |x>. De este modo, tras k iteraciones todos los estados |x>, con x≠s tendrán la misma amplitud, que denominamos mk, y |s> tendrá una amplitud diferente, que denominamos bk.
Podemos escribir el estado resultante de la forma:
Las amplitudes verifican:
|
|
Cuando se mide el estado, después de k iteraciones la probabilidad de acierto (obtener s en la medida) será |bk|2 y la de fallo (N-1)|mk|2.
Se puede demostrar (ver [6]) que el número óptimo de iteraciones es la parte entera de (π N1/2)/4 y que con estas iteraciones la probabilidad de fallo es menor que 1/N.
Ejercicio 3.3.1
Determina el número óptimo de iteraciones del algoritmo de Grover para encontrar la solución en un problema de búsqueda no estructurada con 10000 datos y solución única.
Comprueba que la probabilidad de acierto no mejora al aumentar el número de iteraciones por encima del número óptimo.
Cuestiones para reflexionar e investigar:
Consulta en [5] la interpretación geométrica del algoritmo de Grover y justifica el número óptimo de iteraciones.
Busca en [1] y [6] información sobre el Algoritmo de Grover para problemas con más de una solución.
APARTADO 3.4. TRANSFORMADA CUÁNTICA DE FOURIER
La transformada cuántica de Fourier (QFT) es una transformación unitaria de Hn en Hn, que para cada n-qubit |j>, de la base Bn, se define como:
.jpg)
Nótese que j es una cadena de n bits, que representa la expresión binaria de un número entre 0 y 2n-1 y cuando no hay lugar a confusión escribimos directamente este número.
Por ejemplo, la imagen de |0> es justamente una superposición de todos los estados de la base.
Es decir Fn(|0>)=Wn(|0>).
Ejercicio 3.4.1
Determina la QFT de los cuatro estados de la base de H2 y la matriz asociada a la transformación unitaria F2.
Realmente la QFT es una generalización de la Transformada Discreta de Fourier, que transforma una lista f0 ...fQ-1 de Q números complejos en otra lista de igual longitud definida por:
Clásicamente el cálculo de la Transformada discreta de Fourier de una lista de Q números requiere Q2 productos complejos, o bien Qlog(Q) si se usa el algoritmo FFT de transformada rápida.
Peter Shor propuso en 1996 un algoritmo cuántico, polinomial en n, para calcular la QFT de los Q=2n estados de la base de Bn.
El circuito tiene Parte_Entera(n/2) puertas Swap, n puertas H y n(n-1)/2 puertas Control-Rk con;
Una importante aplicación de la QFT, que se usa para el algoritmo polinomial de factorización de Shor, es el cálculo el periodo de una función entera, que se basa en la siguiente propiedad:
Dada una función entera f de periodo T (divisor de Q), su transformada cuántica de Fourier se anula en todos los elementos del dominio salvo en los múltiplos de la frecuencia w (que verifica wT=Q). Es decir:
Ejercicio 3.4.2
Demuestra la propiedad anterior.
Esta propiedad permite obtener la frecuencia w y en consecuencia el periodo T. Para ello se aplica la QFT a f y a continuación se miden todos los qubits. De este modo se obtiene un valor wk con 0 ≤ k < T y devolvemos como resultado w'=mcd(wk, Q), que coincidirá o será múltiplo de w.
APARTADO 3.5. ALGORITMO DE SHOR
La factorización de números enteros es un problema muy actual. La dificultad de este problema, infructuosamente atacado hasta el momento, nos permite considerar la multiplicación de números enteros como una función de dirección única.
La aplicación más importante de este hecho es el sistema criptográfico de clave pública RSA. La seguridad de este sistema radica en la imposibilidad práctica de factorizar números grandes, con centenares de dígitos. Otros protocolos de clave pública como ElGamal se basan en otro problema de alta dificultad computacional: el problema del logaritmo discreto.
Pero la computación cuántica puede modificar radicalmente el estatus actual de la seguridad informática, ya que Shor propuso en 1994 (ver [7]) un algoritmo cuántico para resolver de modo eficiente tanto el problema de la factorización de un número entero como el problema del logaritmo discreto.
Como todos los algoritmos de computación cuántica, el algoritmo de Shor es probabilístico: da la respuesta correcta con alta probabilidad, y la probabilidad de fallo puede ser disminuida repitiendo el algoritmo.
Hasta ahora sólo se ha podido implementar en computadoras cuánticas con un pequeño número qubits y en consecuencia sólo se ha podido experimentar para factorizar números pequeños.
A continuación, se presentan las ideas básicas del Algoritmo de Shor. Para un estudio más detallado se recomienda [2].
El algoritmo se compone de dos partes. La primera convierte el problema de encontrar un factor propio de un número en el problema de encontrar el período de una función, y se puede implementar clásicamente. La segunda parte encuentra el período, usando la QFT, y es responsable de la aceleración cuántica.
Algoritmo para encontrar un factor propio
Si el algoritmo no falla devuelve un factor propio de N |
|
El paso 3 es el paso más costoso del algoritmo anterior y es equivalente a encontrar el periodo de la función f(k)=ak mod N, para lo que se puede utilizar la transformada cuántica de Fourier.
|
|
El algoritmo de Shor para encontrar un factor propio de N es polinomial en el número de dígitos de N.
Teniendo en cuenta que hay que repetir el algoritmo O(loglog(N)) veces, se concluye que el algoritmo de Shor resuelve el problema de factorización de N en tiempo O(log4(N)loglog (N)).
Ejercicio 3.5.1
Uno de los mejores algoritmos clásicos de factorización es el algoritmo de Pollard y Strassen de 1976, que tiene complejidad O(2n/4 n2), siendo n el número de dígitos. Si se quiere factorizar un número con n= 200 dígitos, calcula el tiempo necesario para realizar 2n/4 n2 operaciones, en una máquina que realice 109 operaciones por segundo.
Teniendo en cuenta que el algoritmo de Shor tiene complejidad O(log4(N)loglog (N)), con N=2n, compara el tiempo anterior con el que se tardaría en realizar n4log(n) operaciones.
APARTADO 3.6. TEST DE AUTOEVALUACIÓN
1. Dada f de {0,1}2 en {0,1}2 tal que f(a,b)=(0,b), la transformación unitaria asociada Uf verifica:
2. Dada f de Z23 en Z23, periódica y 2 a 1, se aplica el algoritmo cuántico para resolver el problema de Simon dos veces y como resultado de las mediciones se obtienen los valores k= 001 y k=011. Se puede asegurar que el periodo de f es
a) T=010.
b) T=100.
c) No se puede determinar el periodo.
3. La transformada cuántica de Fourier sobre estados de n-qubits Fn verifica:
a) Coincide con la transformación de Walsh-Hadamard, es decir Fn(|x>)= Wn(|x>) para todo n-qubit |x>.
b) Fn(|x>)= Wn(|x>) si y solo si x=0.
c) Para n=1, la transformación unitaria F1 coincide con W1=H .
4. Se pretende factorizar N=221 con el algoritmo de Shor y se elige aleatoriamente a=11. Entonces:
a) El periodo de f(k)=11k mod 221 es 48 y por tanto mcd(1124+1,221) es un factor de 221.
b) El periodo de f(k)=11k mod 221 es 48 y por tanto 1124+1 mod 221 es un factor de 221.
c) El periodo de f(k)=11k mod 221 no es 48.
5. El algoritmo de Shor propone la utilización de computación cuántica para:
a) Reducir el problema de factorizar N al de encontrar el periodo de una función del tipo f(k)=ak mod N.
b) Calcular el periodo de una función del tipo f(k)=ak mod N.
c) Evaluar de modo más eficiente las potencias ak mod N
APARTADO 3.7. REFERENCIAS BIBLIOGRÁFICAS Y ENLACES DE INTERÉS
[1] Boyer, M.; Brassard G.; Hoyer, P. and Tapp, A. Tight bounds on quantum searching, Workshop of Phys. Comp. 96 (1996), pp. 36--43 (arXiv:quant-ph/9605034 v1).
[2] García López, J. Factorización polinomial de números enteros, La Gaceta de la RSME, 7 (2004), pp. 517--537
[3] Green, A.S., Lumsdaine, P.F., Ross, N.J., Selinger, P., Valiron, B. An Introduction to Quantum Programming in Quipper. In Proceedings of the 5th International Conference on Reversible Computation (2013), Victoria, BC, Canada. Lecture Notes in Computer Science 7948:110-124, Springer.
[4] Grover, L.K. A fast quantum mechanical algorithm for database search. Proceedings of the 28th ACM Symposium on the Theory of Computing (1996), pp. 212--219 (arXiv:quant-ph/9605043).
[5] Lomonaco, S.J. Grover's Quantum Search Algorithm, Proceedings of the Symposia of Applied Mathematics (2000) (arXiv:quant-ph/0010040 v2).
[6] Nielsen, M.A., Chuang, L.I. Quantum Computation and Quantum Information, Cambridge University Press, 2000.
[7] Shor, P.W. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, SIAM J. Comput. 26 (1994) pp.1484--1509 (arXiv:quant-ph/9508027).
http://www.fisicafundamental.net/misterios/computacion.html
http://www.ic-itcr.ac.cr/~jcastro/libro/libro/libro.html
http://www.csee.umbc.edu/~lomonaco/ams/Lecture_Notes.html