Algoritmos cuánticos
Un algoritmo cuántico es un algoritmo que se ejecuta en un modelo realista de computación cuántica, como el modelo de circuito cuántico, como el que se ilustra en la figura.1 La teoría de lacomplejidad computacional le asigna la clase BQP a los algoritmos que pueden ser resueltos en uncomputador cuántico en tiempo polinómico con un margen de error promedio inferior a 1/4. En elanálisis de los algoritmos cuánticos es habitual comparar la cota superior asintótica con el mejor algoritmo clásico conocido, o, si el problema está resuelto, con el mejor algoritmo clásico posible. Se usa la notación de Landau para definir la relación entre la talla de la entrada del problema y el número de pasos necesarios para resolverlo, o el número de posiciones de memoria que se utilizan durante su resolución.
El algoritmo de Deutsch-Jozsa fue propuesto por David Deutsch y Richard Jozsa en 19922 y fue mejorado posteriormente por Richard Cleve, Artur Ekert, Chiara Macchiavello, y Michele Mosca en 1998.3 Su función es determinar si una función de tipo caja negra 
es «constante» o «balanceada». Esto es, dada una función que para una entrada de n bits da un sólo bit de salida, determinar si la salida es independiente de la entrada o si para la mitad de las entradas es 0 y para la otra mitad es 1. El planteamiento del problema excluye todas las otras posibles funciones. El algoritmo no tiene apenas utilidad práctica, pero es uno de los primeros ejemplos de un algoritmo cuántico que se ha demostrado que es exponencialmente más rápido que cualquier posible algoritmo clásico determinista.
es «constante» o «balanceada». Esto es, dada una función que para una entrada de n bits da un sólo bit de salida, determinar si la salida es independiente de la entrada o si para la mitad de las entradas es 0 y para la otra mitad es 1. El planteamiento del problema excluye todas las otras posibles funciones. El algoritmo no tiene apenas utilidad práctica, pero es uno de los primeros ejemplos de un algoritmo cuántico que se ha demostrado que es exponencialmente más rápido que cualquier posible algoritmo clásico determinista.
El algoritmo de Shor, propuesto por Peter Shor en 1995 y relacionado con la aritmética modular, descompone en factores un número N en tiempo 
y espacio 
.4 Es responsable de buena parte de la atención que se le ha dedicado a la computación cuántica, por su relación con el problema RSA de importancia fundamental en criptografía.
y espacio .4 Es responsable de buena parte de la atención que se le ha dedicado a la computación cuántica, por su relación con el problema RSA de importancia fundamental en criptografía.
El algoritmo de Grover, publicado por Lov Grover en 1996,5 demostró que un problema de utilidad práctica podía ser resuelto más rápidamente que el mejor algoritmo clásico posible. El algoritmo realiza una búsqueda en una base de datos desordenada con N entradas en un número de pasos de orden 
, consumiendo un espacio de memoria de orden .
, consumiendo un espacio de memoria de orden .
El desarrollo de la primera corrección de errores cuántica, propuesta también por Peter Shor en 1995,6 fue el primer paso hacia la computación cuántica a prueba de errores. Supuso un avance significativo porque por las leyes mecánica cuántica no es posible usar las estrategias habituales para la detección y corrección de errores de la computación clásica.
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/2evaluaciones. 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.2Calcula 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:
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.
Algoritmo para la transformada cuántica de Fourier
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.2Demuestra 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 comoElGamal 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.
No hay comentarios:
Publicar un comentario