Algoritmos

Algoritmos cuánticos

algoritmo de Deutsch-Jozsa es un algoritmo cuántico, propuesto por David Deutsch y Richard Jozsa en 1992. Fue uno de los primeros algoritmos diseñados para ejecutar sobre un computador cuántico y que tiene el potencial de ser más eficiente que los algoritmos clásicos al aprovechar el paralelismo inherente de los estados de superposición cuánticos.

En el problema de Deutsch-Jozsa nos dan una función cuántica (que para nosotros es una caja negra) f(x₁, x₂,..., x_n) que toma n bits de entrada x₁, x₂,..., x_n y devuelve un valor binario f(x₁, x₂,..., x_n). Sabemos que la función es constante (0 en todas las entradas o 1 en todas las entradas) o balanceada (devuelve 1 para la mitad de las entradas y 0 para la otra mitad); el problema es entonces determinar cómo es la función (constante o balanceada) aplicando entradas a la caja negra y observando su salida.

Algoritmo de Deutsch

Circuito cuántico que implementa el algoritmo de Deutsch.

Esta es una versión del algoritmo para una función f(x) de una sola entrada. Se utilizan dos qubits auxiliares en los cálculos. El algoritmo se ilustra en la figura de la derecha.

El bloque H es una puerta Hadamard cuya operación es la siguiente:

${\displaystyle H(|0\rangle )={\frac {1}{\sqrt {2}}}(|0\rangle +|1\rangle )}$

${\displaystyle H(|1\rangle )={\frac {1}{\sqrt {2}}}(|0\rangle -|1\rangle )}$

El bloque U_f realiza la operación siguiente:

${\displaystyle U_{f}(|0\rangle |0\rangle )=|0\rangle |0\oplus f(0)\rangle =|0\rangle |f(0)\rangle }$

${\displaystyle U_{f}(|0\rangle |1\rangle )=|0\rangle |1\oplus f(0)\rangle =|0\rangle |{\overline {f(0)}}\rangle }$

${\displaystyle U_{f}(|1\rangle |0\rangle )=|1\rangle |0\oplus f(1)\rangle =|1\rangle |f(1)\rangle }$

${\displaystyle U_{f}(|1\rangle |1\rangle )=|1\rangle |1\oplus f(1)\rangle =|1\rangle |{\overline {f(1)}}\rangle }$

Además,

${\displaystyle U_{f}(|0\rangle (|0\rangle -|1\rangle ))=|0\rangle |f(0)-{\overline {f(0)}}\rangle =|0\rangle |(-1)^{f(0)}(|0\rangle -|1\rangle )}$

${\displaystyle U_{f}(|1\rangle (|0\rangle -|1\rangle ))=|1\rangle |f(1)-{\overline {f(1)}}\rangle =|1\rangle |(-1)^{f(1)}(|0\rangle -|1\rangle )}$

${\displaystyle U_{f}(|x\rangle (|0\rangle -|1\rangle ))=|x\rangle |(-1)^{f(x)}(|0\rangle -|1\rangle )}$

La entrada al circuito es: ${\displaystyle |a\rangle =|0\rangle |1\rangle }$, que atraviesa dos puestas Hardamard (véase la figura) obteniéndose ${\displaystyle |b\rangle =(1/2)(|0\rangle +|1\rangle )(|0\rangle -|1\rangle )}$. Esto atraviesa el bloque U_f obteneniéndose

${\displaystyle |c\rangle =(1/2)\{|0\rangle |(-1)^{f(0)}(|0\rangle -|1\rangle )+|1\rangle |(-1)^{f(1)}(|0\rangle -|1\rangle )\}}$

Esta expresión puede escribirse:

${\displaystyle |c\rangle =\left\{{\begin{array}{ll}\pm (|0\rangle +|1\rangle )|(|0\rangle -|1\rangle )&{\mbox{si }}~f(0)=f(1)\\\pm (|0\rangle -|1\rangle )|(|0\rangle -|1\rangle )&{\mbox{si }}~f(0)\neq f(1)\end{array}}\right.}$

Al atravesar la última puerta de Hadamard obtenemos:

${\displaystyle |d\rangle =\left\{{\begin{array}{ll}\pm {\frac {1}{\sqrt {2}}}|0\rangle (|0\rangle -|1\rangle )&{\mbox{si }}~f(0)=f(1)\\\pm {\frac {1}{\sqrt {2}}}|1\rangle (|0\rangle -|1\rangle )&{\mbox{si }}~f(0)\neq f(1)\end{array}}\right.}$

Puesto que si ${\displaystyle f(0)=f(1),f(0)\oplus f(1)=0}$ y si ${\displaystyle f(0)\neq f(1),f(0)\oplus f(1)=1}$, podemos escribir

${\displaystyle \pm {\frac {1}{\sqrt {2}}}|f(0)\oplus f(1)\rangle (|0\rangle -|1\rangle )}$

Este es el resultado final: midiendo el primer qubit de la ecuación obtenemos ${\displaystyle f(0)\oplus f(1)}$. Si resulta el valor 0, entonces la función f(x) es constante, mientras que si resulta 1, la función es balanceada.

Algoritmo de Deutsch-Jozsa

Circuito cuántico que implementa el algoritmo de Deutsch-Jozsa.

Esta es la versión general del algoritmo para funciones f(x) de n entradas.

En este caso, la entrada al circuito es:

${\displaystyle |a\rangle =|0\rangle ^{\oplus n}|1\rangle }$

A continuación de las puertas Hadamard se obtiene:

${\displaystyle |b\rangle ={\frac {1}{\sqrt {2^{n}}}}\sum _{x=0}^{2^{n}-1}|x\rangle {\frac {|0\rangle -|1\rangle }{\sqrt {2}}}}$

A la salida del bloque U_f se tiene:

${\displaystyle |c\rangle =\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}|x\rangle {\frac {|0\rangle -|1\rangle }{\sqrt {2}}}}$

La última puerta Hadamard produce la siguiente salida

${\displaystyle |d\rangle =\sum _{z=0}^{2^{n}-1}\sum _{x=0}^{2^{n}-1}(-1)^{x\cdot z+f(x)}|z\rangle {\frac {|0\rangle -|1\rangle }{\sqrt {2}}}}$

Y por último, realizando la medición, se obtiene z. En el caso en que la función f(x) sea balanceda, las contribuciones para ${\displaystyle (0,\ldots ,0)}$ se cancelan y la medida de z debe dar una combinación distinta. Por el contrario, si f(x) es constante se obtiene ${\displaystyle (0,\ldots ,0)}$ en la medida, pues el resto de las contribuciones se cancelan en este caso. Por consiguiente, comprobando si z es cero o distinto de cero se sabe que la función es, respectivamente, constante o balanceada.

Algoritmo de Deutsch-Jozsa

Sea  el conjunto de valores de verdad clásicos. De las  funciones booleanas  dos son constantes y las otras dos son equilibradas. Al nombrarlas

se tiene que las funciones constantes son  y , y las equilibradas son  y .

El propósito del algoritmo de Deutsch-Jozsa es decidir, para una  dada, si acaso es constante o equilibrada ``utilizando un solo paso de cómputo''.
Sea  una matriz permutación de orden  tal que .  es pues unitaria. De hecho es muy similar al funcionamiento de la compuerta ``negación controlada'', salvo que en aquella, la función  es propiamente la identidad. En la tabla 1 ilustramos la acción de  refiriéndonos solamente a los índices de vectores básicos.

Recuadro 1: Acción de la matriz unitaria  en el algoritmo de Deutsch-Jozsa.

(0,0) (0,) (0,1) (0, ) (1,0) (1,) (1,1) (1, )

Considerando el operador de Hadamard , hagamos . Primero se tiene,  y  y luego . Claramente,  Por tanto,

 

En consecuencia,

 

vale decir, al aplicar el algoritmo cuántico  (nótese que utilizamos notación algebraica: los operadores se aplican de derecha a izquierda), partiendo del vector básico  se obtiene un vector de la forma  donde  es un signo y  es una señal que indica si acaso  es o no equilibrada. En otras palabras, la respuesta  coincide con , donde  es la disyunción excluyente, XOR. La auscultación del valor  se realiza siguiendo el postulado de medición, y su valor está apareciendo leyendo sólo el primer qubit. Al efectuar la medición se elige al vector básico  con probabilidad .

algoritmo de Grover es un algoritmo cuántico para la búsqueda en una secuencia no ordenada de datos con N componentes en un tiempo O (N^1/2), y con una necesidad adicional de espacio de almacenamiento de O(logN) (véase notación O). Fue inventado por Lov K. Grover en 1996.

En una búsqueda normal de un dato, si tenemos una secuencia desordenada se debe realizar una inspección lineal, que necesita un tiempo de O (N), por lo que el algoritmo de Grover es una mejora bastante sustancial, evitando, además, la necesidad de la ordenación previa. La ganancia obtenida es "sólo" de la raíz cuadrada, lo que contrasta con otras mejoras de los algoritmos cuánticos que obtienen mejoras de orden exponencial sobre sus contrapartidas clásicas.

Al igual que otros algoritmos de naturaleza cuántica, el algoritmo de Grover es un algoritmo de carácter probabilístico, por lo que produce la respuesta correcta con una determinada probabilidad de error, que, no obstante, puede obtenerse tan baja como se desee por medio de iteraciones.

Aplicaciones

Aunque el propósito del algoritmo es, como ha sido indicado, la búsqueda en una secuencia, se podría describir de una manera más adecuada como la "inversión de una función". Así, si tenemos la función y=f (x), que puede ser evaluada en un computador cuántico, este algoritmo nos permite calcular el valor de x cuando se nos da como entrada el valor de y. Invertir una función puede relacionarse con la búsqueda en una secuencia, si consideramos que la misma es una función que produce el valor de y como la posición ocupada por el valor x en dicha secuencia.

El algoritmo de Grover también se puede utilizar para el cálculo de la media y la mediana de un conjunto de números, y para resolver otros problemas de naturaleza análoga. También se puede utilizar para resolver algunos problemas de naturaleza NP-completa, por medio de inspecciones exhaustivas en un espacio de posibles soluciones. Esto resulta en una apreciable mejora sobre soluciones clásicas.

Descripción

Inicialización

Se considera una secuencia desordenada con N componentes. El algoritmo requiere un espacio de estados N-dimensional H, que puede ser modelado con log₂N qubits.

Numeremos las entradas de la secuencia con 0, 1,... (N-1); y seleccionemos un observable Ω, actuando sobre H, con N autovalores distintos conocidos. Cada uno de los autovalores de Ω codifica una de las entradas de la secuencia, de una forma que se describirá más adelante. Denotaremos los autoestados utilizando la notación bra-ket en la forma:

${\displaystyle \{|0\rangle ,|1\rangle ,\cdots ,|N-1\rangle \}}$

y los autovalores correspondientes como

${\displaystyle \{\lambda _{0},\lambda _{1},\cdots ,\lambda _{N-1}\}}$

Ahora tomamos un operador unario, U_ω, que actúa como una subrutina que compara las diferentes entradas de acuerdo al criterio de búsqueda. El algoritmo no especifica como funciona la subrutina, pero debe ser una subrutina cuántica que trabaje bajo una superposición de estados. Además, debe actuar de manera especial sobre uno de los autoestados, |ω>, que corresponderá con la entrada que satisface el criterio de búsqueda. Más precisamente, requeriremos U_ω con los siguientes efectos:

${\displaystyle U_{\omega }|\omega \rangle =-|\omega \rangle }$

${\displaystyle U_{\omega }|x\rangle =|x\rangle \qquad {\mbox{para todo}}\ x\neq \omega }$

En concreto,

${\displaystyle \langle \omega |\omega \rangle =1}$.

${\displaystyle \langle \omega |x\rangle =\langle x|\omega \rangle =0}$.

${\displaystyle U_{\omega }|\omega \rangle =(I-2|\omega \rangle \langle \omega |)|\omega \rangle =|\omega \rangle -2|\omega \rangle \langle \omega |\omega \rangle =-|\omega \rangle }$.

${\displaystyle U_{\omega }|x\rangle =(I-2|\omega \rangle \langle \omega |)|x\rangle =|x\rangle -2|\omega \rangle \langle \omega |x\rangle =|x\rangle }$.

Nuestro objetivo es identificar el autoestado |ω>, o de manera equivalente, el autovalor ω, tal que U_ω actúa especialmente sobre él.

Iteraciones del algoritmo

Los pasos del algoritmo de Grover son los siguientes:

1. Inicializar el sistema al estado

   ${\displaystyle |s\rangle ={\frac {1}{\sqrt {N}}}\sum _{x}|x\rangle }$

2. Realizar la siguiente iteración r (N) veces. Donde la función r (N) se describe más adelante.
   1. Aplicar el operador ${\displaystyle U_{\omega }}$
   2. Aplicar el operador ${\displaystyle U_{s}=2\left|s\right\rangle \left\langle s\right|-I}$.
3. Realizar la medida Ω. La medida corresponderá al valor λ_ω con una cierta probabilidad que se puede aproximar a 1, para un cierto N>>1. A partir de λ_ω, se puede obtener ω.

Podemos escribir las operaciones realizadas:

${\displaystyle \langle s|s\rangle =1}$.

${\displaystyle \langle \omega |s\rangle =\langle s|\omega \rangle ={\frac {1}{\sqrt {N}}}}$.

${\displaystyle U_{\omega }|s\rangle =(I-2|\omega \rangle \langle \omega |)|s\rangle =|s\rangle -2|\omega \rangle \langle \omega |s\rangle =|s\rangle -{\frac {2}{\sqrt {N}}}|\omega \rangle }$.

${\displaystyle U_{s}(|s\rangle -{\frac {2}{\sqrt {N}}}|\omega \rangle )=(2\left|s\right\rangle \left\langle s\right|-I)(|s\rangle -{\frac {2}{\sqrt {N}}}|\omega \rangle )}$

${\displaystyle =2\left|s\right\rangle \left\langle s\right|s\rangle -|s\rangle -{\frac {4}{\sqrt {N}}}\left|s\right\rangle \left\langle s\right|\omega \rangle +{\frac {2}{\sqrt {N}}}|\omega \rangle }$

${\displaystyle =2|s\rangle -|s\rangle -{\frac {4}{\sqrt {N}}}\cdot {\frac {1}{\sqrt {N}}}|s\rangle +{\frac {2}{\sqrt {N}}}|\omega \rangle ={\frac {N-4}{N}}|s\rangle +{\frac {2}{\sqrt {N}}}|\omega \rangle }$

${\displaystyle ={\frac {1}{N{\sqrt {N}}}}\left((N-4)\sum _{x\neq w}|x\rangle +(3N-4)|\omega \rangle \right)}$

Después de aplicar los dos operadores ( ${\displaystyle U_{\omega }}$ y ${\displaystyle U_{s}}$ ), la amplitud del elemento buscado se ve incrementado. Y esta es una iteración de Grover.

Número de iteraciones

Ahora consideramos el plano definido por |s> y |ω>. Sea |ω^×> que es perpendicular a |ω>. Entonces |ω> es uno de los vectores base, y tenemos

${\displaystyle \langle \omega |s\rangle ={\frac {1}{\sqrt {N}}}}$

En términos geométricos, hay un ángulo (π/2 - θ) entre |ω> y |s>, where θ dado por:

${\displaystyle \cos \left({\frac {\pi }{2}}-\theta \right)={\frac {1}{\sqrt {N}}}}$

${\displaystyle \sin \theta ={\frac {1}{\sqrt {N}}}}$

El operador U_ω es un reflejo del hiperplano ortogonal a |ω> para los vectors en el plano definido por |s> y |ω>, además, actúa como un reflejo de la línea |ω^×>. El operador U_s es un reflejo de la línea |s>.

Entonces, el vector de estado permanece en el plano de |s> y |ω> tras cada aplicación de U_s y tras cada aplicación de U_ω, y se puede comprobar que el operador U_sU_ω de cada paso de iteración rota el vector de estado en un ángulo de 2θ hacia |ω>.

El algoritmo se detendrá cuando el vector de estado se acerca a |ω> tras esto, las siguientes iteraciones rotan el vector de estado fuera de |ω>, reduciendo la probabildad de obtener la respuesta correcta. El número de iteraciones necesarias es dado por r. Para alinear correctamente el vector de estado con |ω>, necesitamos:

${\displaystyle {\frac {\pi }{2}}-\theta =2\theta r}$

${\displaystyle r={\frac {({\frac {\pi }{\theta }}-2)}{4}}}$

Una consideración es que r debe ser entero, por lo que, en general, r será el entero más cercano a (π/θ - 2)/4. Entonces, el ángulo entre |ω> y el vector de estado final es O(θ), y la probabilidad de obtener una respuesta incorrecta es O(1 - cos²θ) = O (sin²θ).

Entonces, para N>>1, θ ≈ N^-1/2, tenemos

${\displaystyle r\rightarrow {\frac {\pi {\sqrt {N}}}{4}}}$

Además, la probabilidad de obtener una respuesta incorrecta será O(1/N), que tiende a 0 para un valor de N suficientemente elevado.

Implementación

A continuación presentamos una implementación concreta del algoritmo de Grover. Supongamos que tenemos una secuencia de 2ⁿelementos que vamos a referenciar por su índice x. Supongamos también que disponemos de una función f (x) que nos dice si el valor almacenado en la posición x es el que estamos buscando. En concreto sea f (x)=1 para el valor buscado y f (x)=0 para el resto.

Oráculo

Oráculo.

A partir de la función f (x) vamos a construir un oráculo, tal como se muestra en la figura de la derecha. El funcionamiento de este bloque es el mismo que el correspondiente del algoritmo de Deutsch-Jozsa. La operación de este bloque es:

${\displaystyle U_{f}(|x\rangle (|0\rangle -|1\rangle ))=(-1)^{f(x)}|x\rangle |(|0\rangle -|1\rangle )}$

Puesto que el último estado no se modifica, vamos a ignorarlo y escribiremos:

${\displaystyle U_{f}(|x\rangle )=(-1)^{f(x)}|x\rangle }$

Inversión sobre la media

Inversión sobre la media.

El bloque que lo realiza se muestra en la figura de la derecha. Esta operación puede escribirse:

${\displaystyle H^{\oplus n}(2|0\rangle \langle 0|-I)H^{\oplus n}=2|\psi \rangle \langle \psi |-I}$

con ${\displaystyle \textstyle \psi ={\frac {1}{\sqrt {2^{n}}}}\sum _{x=0}^{2^{n}-1}|x\rangle }$.

Esta operación se interpreta como inversión sobre la media, pues si lo aplicamos sobre un estado genérico ${\displaystyle \textstyle a=\sum _{x=0}^{2^{n}-1}a_{x}|x\rangle }$, obtenemos:

${\displaystyle (2|\psi \rangle \langle \psi |-I)(\sum _{x=0}^{2^{n}-1}a_{x}|x\rangle )=\sum _{x=0}^{2^{n}-1}\left(2\langle a\rangle -a_{x}\right)|x\rangle }$,

en donde ${\displaystyle \textstyle \langle a\rangle =(1/2^{n})\sum _{x=0}^{2^{n}-1}a_{x}}$

Iteración de Grover

Algoritmo de Grover. En detalle se muestra una de las iteraciones.

Una iteración de Grover se compone de dos pasos:

1. Aplicación del oráculo
2. Inversión sobre la media

Por tanto, la iteración de Grover puede escribirse:

${\displaystyle G_{f}=(2|\psi \rangle \langle \psi |-I)U_{f}}$.

El algoritmo completo se muestra en la figura de la derecha.

Interpretación

Hagamos las cuentas para la primera iteración de Grover. Preparamos un estado haciendo pasar el qubit |0> (realmente compuesto de n ceros) a través de una puerta de Hadamard:

${\displaystyle |a\rangle =H^{\oplus n}|0\rangle ={\frac {1}{\sqrt {2^{n}}}}\sum _{x=0}^{2^{n}-1}|x\rangle }$

Este estado pasa a través del oráculo, obteniendo:

${\displaystyle |b\rangle =U_{f}(|a\rangle )={\frac {1}{\sqrt {2^{n}}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}|x\rangle }$

A continuación, aplicamos la inversión sobre la media, y obtenemos:

${\displaystyle |c\rangle =(2|\psi \rangle \langle \psi |-I)(|b\rangle )={\frac {1}{\sqrt {2^{n}}}}\sum _{x=0}^{2^{n}-1}(2$-b_{x})|x\rangle }

${\displaystyle ={\frac {1}{2^{n}{\sqrt {2^{n}}}}}\sum _{x=0}^{2^{n}-1}\left(2\left(\sum _{y=0}^{2^{n}-1}b_{y}\right)-2^{n}b_{x}\right)|x\rangle }$

${\displaystyle ={\frac {1}{2^{n}{\sqrt {2^{n}}}}}\sum _{x=0}^{2^{n}-1}\left(2\left(\sum _{y=0}^{2^{n}-1}(-1)^{f(y)}\right)-2^{n}(-1)^{f(x)}\right)|x\rangle }$

Interpretemos ahora este resultado. Supongamos que en la posición x_i se encuentra el valor buscado, esto es, f (x_i)=1 y para el resto, f (x)=0, obtenemos:

${\displaystyle |c\rangle ={\frac {1}{2^{n}{\sqrt {2^{n}}}}}\sum _{x=0}^{2^{n}-1}\left(2\left((2^{n}-1)(+1)+(-1)\right)-2^{n}(-1)^{f(x)}\right)|x\rangle }$

${\displaystyle ={\frac {2^{n+1}+2^{n}-4}{2^{n}{\sqrt {2^{n}}}}}|x_{i}\rangle +{\frac {2^{n+1}-2^{n}-4}{2^{n}{\sqrt {2^{n}}}}}\sum _{x=0,x\neq x_{i}}^{2^{n}-1}|x\rangle }$

Como puede observarse, el término que nos interesa aumenta su amplitud en comparación con demás los términos. Repitiendo esta operación en varias iteraciones, este efecto se verá incrementado. Si al final del algoritmo hacemos un medición, muy probablemente obtendremos el valor buscado.

Algoritmo de Grover

Descripción del problema

Un algoritmo de búsqueda es el que nos permite encontrar un elemento x₀ en un conjunto posible de soluciones (estructura de datos) que cumpla una determinada proposición f(x). Dentro de este tipo de problemas están la búsqueda en una base de datos o el coloreado ordenado de una gráfica.

Si no sabemos nada sobre la estructura del espacio de soluciones estamos ante un problema desestructurado, como el que resolvió Lov K. Grover en 1996. Un ejemplo sería la búsqueda de un teléfono en una guía telefónica sin conocer el nombre. Clásicamente el mejor algoritmo aleatorio nos llevaría a un coste de O(N) (si se quiere N/2 consultas de media) para una base de datos de tamaño N. Con el algoritmo de Grover se mejora este resultado con una ganancia cuadrática de orden O(√N). El algoritmo de Grover es probabilístico, es decir, sólo da la respuesta correcta con cierta probabilidad (al contrario que el de Deutsch por ejemplo que era determinista).

Lógicamente nuestra proposición aquí está implementada por un oráculo que actúe de la siguiente forma:

Por tanto, asumimos que de entrada necesitaremos un registro fuente de n qubits tal que N=2ⁿ y uno adicional para almacenar la información de la función. (Nótese el hecho de que conocer de antemano x₀ no es lo mismo que reconocerlo entre un conjunto de estados).

Estrategia

La estrategia será preparar un estado superposición de todas las entradas del catálogo:

después aplicar el oráculo que nos dé todos los valores de la veracidad de la proposición sobre las entradas:

para en último lugar desbalancear los pesos estadísticos de forma que halla suficiente probabilidad de encontrar el estado |x₀>|1>. Para ello hay que utlizar las operaciones de cambio de signo e inversión sobre el promedio.

Cambio de signo

Se trata de aplicar un cambio de signo al elemento que cumpla la proposición, de forma que quede de algún modo marcado (figura).

En el algoritmo clásico esto ya supondría, lógicamente, el haberlo encontrado, pero recordemos que aquí el elemento sigue dentro de un estado global que todavía no podremos medir por no tener la suficiente certeza de que el resultado nos va a dar nuestro elemento. El operador a implementar será de la forma:

La forma de implementar este algoritmo es preparando un estado destino, tal como hicimos para el de Deutsch-Jozsa (inicializandolo a |1> y aplicando Hadamard), en |0> - |1>. De este modo el oráculo de la función nos dará un cambio de signo cuando ésta sea 1.

es decir, al no alterarse el segundo registro lo que se tiene es que:

De esta forma el oráculo marca la solución del problema, mediante el operador cambio de signo:

Para N=4 por ejemplo este operador oráculo se puede implementar mediante las siguientes puertas de tipo Toffoli, dependiendo de si el x₀=0,1,2,3: