Saltar al contenido principal

Algoritmo de Simon

El algoritmo de Simon es un algoritmo de consulta cuántica para un problema conocido como el problema de Simon. Es un problema de promesa con un sabor similar a los problemas de Deutsch-Jozsa y Bernstein-Vazirani, pero con especificaciones distintas.

El algoritmo de Simon es significativo porque proporciona una ventaja exponencial de los algoritmos cuánticos sobre los clásicos (incluidos los probabilísticos), y la técnica que utiliza inspiró el descubrimiento por parte de Peter Shor de un algoritmo cuántico eficiente para la factorización de enteros.

El problema de Simon​

La función de entrada del problema de Simon tiene la forma

f:Σn→Σmf:\Sigma^n \rightarrow \Sigma^m

para enteros positivos nn y m.m. Podríamos restringir nuestra atención al caso m=nm = n en aras de la simplicidad, pero hay poco que ganar con esta suposición — el algoritmo de Simon y su análisis son básicamente los mismos en cualquier caso.

El problema de Simon

Entrada: una función f:Σn→Σmf:\Sigma^n \rightarrow \Sigma^m
Promesa: existe una cadena s∈Σns\in\Sigma^n tal que [f(x)=f(y)]⇔[(x=y)∨(x⊕s=y)][f(x) = f(y)] \Leftrightarrow [(x = y) \vee (x \oplus s = y)] para todo x,y∈Σnx,y\in\Sigma^n
Salida: la cadena ss

Vamos a desglosar la promesa para entender mejor lo que dice en un momento, pero primero debemos tener claro que exige que ff tenga una estructura muy especial — por lo que la mayoría de las funciones no cumplirán esta promesa. También es oportuno reconocer que este problema no pretende tener importancia práctica. Más bien, es un problema algo artificial diseñado a medida para ser fácil para las computadoras cuánticas y difícil para las clásicas.

Hay dos casos principales: el primero es que ss sea la cadena de todos ceros 0n,0^n, y el segundo es que ss no sea la cadena de todos ceros.

  • Caso 1: s=0n.s=0^n. Si ss es la cadena de todos ceros, podemos simplificar la afirmación de si y solo si en la promesa para que diga [f(x)=f(y)]⇔[x=y].[f(x) = f(y)] \Leftrightarrow [x = y]. Esto es equivalente a que ff sea una función uno a uno.

  • Caso 2: s≠0n.s\neq 0^n. Si ss no es la cadena de todos ceros, entonces el cumplimiento de la promesa para esta cadena implica que ff es dos a uno, lo que significa que para cada cadena de salida posible de f,f, hay exactamente dos cadenas de entrada que llevan a ff a producir esa salida. Además, estas dos cadenas de entrada deben tener la forma ww y w⊕sw \oplus s para alguna cadena w.w.

Es importante reconocer que solo puede existir una cadena ss que funcione si se cumple la promesa, por lo que siempre hay una única respuesta correcta para las funciones que satisfacen la promesa.

Aquí hay un ejemplo de una función de la forma f:Σ3→Σ5f:\Sigma^3 \rightarrow \Sigma^5 que satisface la promesa para la cadena s=011.s = 011.

f(000)=10011f(001)=00101f(010)=00101f(011)=10011f(100)=11010f(101)=00001f(110)=00001f(111)=11010\begin{aligned} f(000) & = 10011 \\ f(001) & = 00101 \\ f(010) & = 00101 \\ f(011) & = 10011 \\ f(100) & = 11010 \\ f(101) & = 00001 \\ f(110) & = 00001 \\ f(111) & = 11010 \end{aligned}

Hay 88 cadenas de entrada diferentes y 44 cadenas de salida diferentes, cada una de las cuales aparece dos veces — por lo que esta es una función dos a uno. Además, para cualesquiera dos cadenas de entrada distintas que produzcan la misma cadena de salida, vemos que el XOR bit a bit de estas dos cadenas de entrada es igual a 011,011, lo cual equivale a decir que una de ellas es igual a la otra con XOR aplicado con s.s.

Observa que lo único que importa de las cadenas de salida reales es si son iguales o diferentes para distintas elecciones de cadenas de entrada. Por ejemplo, en el ejemplo anterior, hay cuatro cadenas (10011,(10011, 00101,00101, 00001,00001, y 11010)11010) que aparecen como salidas de f.f. Podríamos reemplazar estas cuatro cadenas por cadenas distintas, siempre que sean todas diferentes entre sí, y la solución correcta s=011s = 011 no cambiaría.

Descripción del algoritmo​

Aquí hay un diagrama de circuito cuántico que representa el algoritmo de Simon.

Simon's algorithm

Para ser precisos, hay nn qubits en la parte superior sobre los que actúan las puertas Hadamard y mm qubits en la parte inferior que entran directamente en la puerta de consulta. Se parece mucho a los algoritmos que ya hemos discutido en la lección, pero esta vez no hay retroceso de fase; los mm qubits inferiores entran todos en la puerta de consulta en el estado ∣0⟩.\vert 0\rangle.

Para resolver el problema de Simon usando este circuito en realidad se necesitarán varias ejecuciones independientes del mismo seguidas de un paso de post-procesamiento clásico, que se describirá más adelante una vez analizado el comportamiento del circuito.

Análisis​

El análisis del algoritmo de Simon comienza de manera similar al algoritmo de Deutsch-Jozsa. Después de que se aplica la primera capa de puertas Hadamard a los nn qubits superiores, el estado se convierte en

12n∑x∈Σn∣0m⟩∣x⟩.\frac{1}{\sqrt{2^n}} \sum_{x\in\Sigma^n} \vert 0^m \rangle \vert x\rangle.

Cuando se aplica Uf,U_f, la salida de la función ff se aplica XOR sobre el estado de todos ceros de los mm qubits inferiores, por lo que el estado se convierte en

12n∑x∈Σn∣f(x)⟩∣x⟩.\frac{1}{\sqrt{2^n}} \sum_{x\in\Sigma^n} \vert f(x) \rangle \vert x\rangle.

Cuando se aplica la segunda capa de puertas Hadamard, obtenemos el siguiente estado usando la misma fórmula para la acción de una capa de puertas Hadamard que antes.

12n∑x∈Σn∑y∈Σn(−1)x⋅y∣f(x)⟩∣y⟩\frac{1}{2^n} \sum_{x\in\Sigma^n} \sum_{y\in\Sigma^n} (-1)^{x\cdot y} \vert f(x) \rangle \vert y\rangle

En este punto, el análisis diverge del de los algoritmos anteriores en esta lección.

Nos interesa la probabilidad de que las mediciones resulten en cada posible cadena y∈Σn.y\in\Sigma^n. Mediante las reglas para analizar mediciones descritas en la lección Sistemas múltiples del curso Fundamentos de información cuántica, encontramos que la probabilidad p(y)p(y) de obtener la cadena yy es igual a

p(y)=∥12n∑x∈Σn(−1)x⋅y∣f(x)⟩∥2.p(y) = \left\|\frac{1}{2^n} \sum_{x\in\Sigma^n} (-1)^{x\cdot y} \vert f(x) \rangle \right\|^2.

Para comprender mejor estas probabilidades, necesitaremos un poco más de notación y terminología. Primero, el rango de la función ff es el conjunto que contiene todas sus cadenas de salida.

range⁡(f)={f(x):x∈Σn}\operatorname{range}(f) = \{ f(x) : x\in \Sigma^n \}

Segundo, para cada cadena z∈range⁡(f),z\in\operatorname{range}(f), podemos expresar el conjunto de todas las cadenas de entrada que hacen que la función evalúe a esta cadena de salida zz como f−1({z}).f^{-1}(\{z\}).

f−1({z})={x∈Σn:f(x)=z}f^{-1}(\{z\}) = \{ x\in\Sigma^n : f(x) = z \}

El conjunto f−1({z})f^{-1}(\{z\}) se conoce como la preimagen de {z}\{z\} bajo f.f. Podemos definir la preimagen bajo ff de cualquier conjunto en lugar de {z}\{z\} de manera análoga — es el conjunto de todos los elementos que ff asigna a ese conjunto. (Esta notación no debe confundirse con la inversa de la función f,f, que puede no existir. El hecho de que el argumento en el lado izquierdo sea el conjunto {z}\{z\} en lugar del elemento zz es la pista que nos permite evitar esta confusión.)

Usando esta notación, podemos descomponer la suma en nuestra expresión para las probabilidades anteriores para obtener

p(y)=∥12n∑z∈range⁡(f)(∑x∈f−1({z})(−1)x⋅y)∣z⟩∥2.p(y) = \left\| \frac{1}{2^n} \sum_{z\in\operatorname{range}(f)} \Biggl(\sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y}\Biggr) \vert z \rangle \right\|^2.

Cada cadena x∈Σnx\in\Sigma^n está representada exactamente una vez por las dos sumaciones — básicamente estamos poniendo estas cadenas en cubos separados según qué cadena de salida z=f(x)z = f(x) producen al evaluar la función f,f, y luego sumando por separado sobre todos los cubos.

Ahora podemos evaluar el cuadrado de la norma euclidiana para obtener

p(y)=122n∑z∈range⁡(f)∣∑x∈f−1({z})(−1)x⋅y∣2.p(y) = \frac{1}{2^{2n}} \sum_{z\in\operatorname{range}(f)} \left\vert \sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y} \right\vert^2.

Para simplificar aún más estas probabilidades, veamos el valor

∣∑x∈f−1({z})(−1)x⋅y∣2(1)\left\vert \sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y} \right\vert^2 \tag{1}

para una selección arbitraria de z∈range⁡(f).z\in\operatorname{range}(f).

Si resulta que s=0n,s = 0^n, entonces ff es una función uno a uno y siempre hay un único elemento x∈f−1({z}),x\in f^{-1}(\{z\}), para todo z∈range⁡(f).z\in\operatorname{range}(f). El valor de la expresión (1)(1) es 11 en este caso.

Si, por otro lado, s≠0n,s\neq 0^n, entonces hay exactamente dos cadenas en el conjunto f−1({z}).f^{-1}(\{z\}). Para ser precisos, si elegimos w∈f−1({z})w\in f^{-1}(\{z\}) como cualquiera de estas dos cadenas, entonces la otra cadena debe ser w⊕sw \oplus s por la promesa en el problema de Simon. Usando esta observación podemos simplificar (1)(1) de la siguiente manera.

∣∑x∈f−1({z})(−1)x⋅y∣2=∣(−1)w⋅y+(−1)(w⊕s)⋅y∣2=∣(−1)w⋅y(1+(−1)s⋅y)∣2=∣1+(−1)y⋅s∣2={4y⋅s=00y⋅s=1\begin{aligned} \left\vert \sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y} \right\vert^2 & = \Bigl\vert (-1)^{w\cdot y} + (-1)^{(w\oplus s)\cdot y} \Bigr\vert^2 \\ & = \Bigl\vert (-1)^{w\cdot y} \Bigl(1 + (-1)^{s\cdot y}\Bigr) \Bigr\vert^2 \\ & = \Bigl\vert 1 + (-1)^{y\cdot s} \Bigr\vert^2 \\ & = \begin{cases} 4 & y \cdot s = 0\\[1mm] 0 & y \cdot s = 1 \end{cases} \end{aligned}

Así pues, resulta que el valor (1)(1) es independiente de la elección específica de z∈range⁡(f)z\in\operatorname{range}(f) en ambos casos.

Ahora podemos finalizar el análisis analizando los mismos dos casos que antes por separado.

  • Caso 1: s=0n.s = 0^n. En este caso la función ff es uno a uno, por lo que hay 2n2^n cadenas z∈range⁡(f),z\in\operatorname{range}(f), y obtenemos

    p(y)=122n⋅2n=12n.p(y) = \frac{1}{2^{2n}} \cdot 2^n = \frac{1}{2^n}.

    En palabras, las mediciones resultan en una cadena y∈Σny\in\Sigma^n elegida uniformemente al azar.

  • Caso 2: s≠0n.s \neq 0^n. En este caso ff es dos a uno, por lo que hay 2n−12^{n-1} elementos en range⁡(f).\operatorname{range}(f). Usando la fórmula anterior concluimos que la probabilidad de medir cada y∈Σny\in\Sigma^n es

    p(y)=122n∑z∈range⁡(f)∣∑x∈f−1({z})(−1)x⋅y∣2={12n−1y⋅s=00y⋅s=1p(y) = \frac{1}{2^{2n}} \sum_{z\in\operatorname{range}(f)} \Biggl\vert \sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y} \Biggr\vert^2 = \begin{cases} \frac{1}{2^{n-1}} & y \cdot s = 0\\[1mm] 0 & y \cdot s = 1 \end{cases}

    En palabras, obtenemos una cadena elegida uniformemente al azar del conjunto {y∈Σn:y⋅s=0},\{y\in\Sigma^n : y \cdot s = 0\}, que contiene 2n−12^{n-1} cadenas. (Como s≠0n,s\neq 0^n, exactamente la mitad de las cadenas binarias de longitud nn tienen producto punto binario 11 con ss y la otra mitad tiene producto punto binario 00 con s,s, como ya observamos en el análisis del algoritmo de Deutsch-Jozsa para el problema de Bernstein-Vazirani.)

Post-procesamiento clásico​

Ahora sabemos cuáles son las probabilidades para los posibles resultados de las mediciones cuando ejecutamos el circuito cuántico del algoritmo de Simon. ¿Es suficiente esta información para determinar ss?

La respuesta es sí, siempre que estemos dispuestos a repetir el proceso varias veces y aceptar que podría fallar con alguna probabilidad, que podemos hacer muy pequeña ejecutando el circuito suficientes veces. La idea esencial es que cada ejecución del circuito nos proporciona evidencia estadística sobre s,s, y podemos usar esa evidencia para encontrar ss con muy alta probabilidad si ejecutamos el circuito suficientes veces.

Supongamos que ejecutamos el circuito de forma independiente kk veces, para k=n+10.k = n + 10. No hay nada especial en este número particular de iteraciones — podríamos tomar kk más grande (o más pequeño) dependiendo de la probabilidad de fallo que estemos dispuestos a tolerar, como veremos. Elegir k=n+10k = n + 10 garantizará que tengamos más de un 99.999.9% de probabilidad de recuperar s.s.

Al ejecutar el circuito kk veces, obtenemos cadenas y1,...,yk∈Σn.y^1,...,y^{k} \in \Sigma^n. Para ser precisos, los superíndices aquí forman parte de los nombres de estas cadenas, no son exponentes ni índices de sus bits, por lo que tenemos

y1=yn−11⋯y01y2=yn−12⋯y02    ⋮yk=yn−1k⋯y0k\begin{aligned} y^1 & = y^1_{n-1} \cdots y^1_{0}\\[1mm] y^2 & = y^2_{n-1} \cdots y^2_{0}\\[1mm] & \;\; \vdots\\[1mm] y^{k} & = y^{k}_{n-1} \cdots y^{k}_{0} \end{aligned}

Ahora formamos una matriz MM con kk filas y nn columnas tomando los bits de estas cadenas como entradas con valores binarios.

M=(yn−11⋯y01yn−12⋯y02⋮⋱⋮yn−1k⋯y0k)M = \begin{pmatrix} y^1_{n-1} & \cdots & y^1_{0}\\[1mm] y^2_{n-1} & \cdots & y^2_{0}\\[1mm] \vdots & \ddots & \vdots \\[1mm] y^{k}_{n-1} & \cdots & y^{k}_{0} \end{pmatrix}

Ahora bien, en este punto no sabemos qué es ss — nuestro objetivo es encontrar esta cadena. Pero imagina por un momento que sí conocemos la cadena s,s, y formamos un vector columna vv a partir de los bits de la cadena s=sn−1⋯s0s = s_{n-1} \cdots s_0 de la siguiente manera.

v=(sn−1⋮s0)v = \begin{pmatrix} s_{n-1}\\ \vdots\\ s_0 \end{pmatrix}

Si realizamos la multiplicación matriz-vector MvM v módulo 22 — es decir, realizamos la multiplicación de la manera habitual y luego tomamos el resto de las entradas del resultado al dividir por 22 — obtenemos el vector de todos ceros.

Mv=(y1⋅sy2⋅s⋮yk⋅s)=(00⋮0)M v = \begin{pmatrix} y^1 \cdot s\\ y^2 \cdot s\\ \vdots\\[1mm] y^{k} \cdot s \end{pmatrix} = \begin{pmatrix} 0\\ 0\\ \vdots\\[1mm] 0 \end{pmatrix}

Es decir, tratada como un vector columna vv como se acaba de describir, la cadena ss siempre será un elemento del espacio nulo de la matriz M,M, siempre que hagamos la aritmética módulo 2.2. Esto es cierto tanto en el caso de que s=0ns = 0^n como en el de que s≠0n.s\neq 0^n. Para ser más precisos, el vector de todos ceros siempre está en el espacio nulo de M,M, y en el caso de que s≠0ns\neq 0^n se le suma el vector cuyas entradas son los bits de s.s.

La pregunta que queda es si habrá otros vectores en el espacio nulo de MM además de los correspondientes a 0n0^n y s.s. La respuesta es que esto se vuelve cada vez más improbable a medida que kk aumenta — y si elegimos k=n+10,k = n + 10, el espacio nulo de MM no contendrá otros vectores además de los correspondientes a 0n0^n y ss con más de un 99.999.9% de probabilidad. Más en general, si reemplazamos k=n+10k = n + 10 por k=n+rk = n + r para una elección arbitraria de un entero positivo r,r, la probabilidad de que los vectores correspondientes a 0n0^n y ss estén solos en el espacio nulo de MM es al menos 1−2−r.1 - 2^{-r}.

Usando álgebra lineal, es posible calcular eficientemente una descripción del espacio nulo de MM módulo 2.2. Específicamente, puede hacerse usando la eliminación gaussiana, que funciona de la misma manera cuando la aritmética se hace módulo 22 que con números reales o complejos. Siempre que los vectores correspondientes a 0n0^n y ss estén solos en el espacio nulo de M,M, lo cual ocurre con alta probabilidad, podemos deducir ss a partir de los resultados de este cálculo.

Dificultad clásica​

¿Cuántas consultas necesita un algoritmo de consulta clásico para resolver el problema de Simon? La respuesta es: muchas, en general.

Hay diferentes afirmaciones precisas que pueden hacerse sobre la dificultad clásica de este problema, y aquí hay solo una de ellas. Si tenemos cualquier algoritmo de consulta probabilístico, y ese algoritmo hace menos de 2n/2−1−12^{n/2 - 1} - 1 consultas, que es un número de consultas exponencial en n,n, entonces ese algoritmo fallará al resolver el problema de Simon con probabilidad al menos 1/2.1/2.

A veces, demostrar resultados de imposibilidad como este puede ser muy difícil, pero este no es demasiado difícil de demostrar mediante un análisis probabilístico elemental. Aquí, sin embargo, solo examinaremos brevemente la intuición básica detrás de él.

Estamos tratando de encontrar la cadena oculta s,s, pero mientras no consultemos la función en dos cadenas que tengan el mismo valor de salida, obtendremos información muy limitada sobre s.s. Hablando intuitivamente, todo lo que aprenderemos es que la cadena oculta ss no es el OR exclusivo de ningún par de cadenas distintas que hayamos consultado. Y si consultamos menos de 2n/2−1−12^{n/2 - 1} - 1 cadenas, todavía habrá muchas opciones para ss que no hemos descartado porque no hay suficientes pares de cadenas para hacerlo. Esto no es una demostración formal, es solo la idea básica.

Entonces, en resumen, el algoritmo de Simon nos proporciona una ventaja sorprendente de los algoritmos cuánticos sobre los clásicos dentro del modelo de consulta. En particular, el algoritmo de Simon resuelve el problema de Simon con un número de consultas que es lineal en el número de bits de entrada nn de nuestra función, mientras que cualquier algoritmo clásico, incluso si es probabilístico, necesita hacer un número de consultas que es exponencial en nn para resolver el problema de Simon con una probabilidad razonable de éxito.