El problema de Simon

La siguiente función es un ejemplo de una función que satisface la propiedad requerida para${\displaystyle n=3}$:

En este caso,${\displaystyle s=110}$(es decir, la solución). Cada salida de${\displaystyle f}$ocurre dos veces, y las dos cadenas de entrada correspondientes a cualquier salida dada tienen una operación XOR bit a bit igual a${\displaystyle s=110}$.

Por ejemplo, las cadenas de entrada${\displaystyle 010}$y${\displaystyle 100}$ambos están mapeados (por${\displaystyle f}$) a la misma cadena de salida${\displaystyle 000}$. Eso es,${\displaystyle {\displaystyle f(010)=000}}$y${\displaystyle {\displaystyle f(100)=000}}$. Al aplicar XOR a 010 y 100 se obtiene 110, es decir${\displaystyle {\displaystyle 010\oplus 100=110=s}.}$

${\displaystyle s=110}$También se puede verificar usando las cadenas de entrada 001 y 111 que se asignan (por f) a la misma cadena de salida 010. Al aplicar XOR a 001 y 111 se obtiene 110, es decir${\displaystyle 001\oplus 111=110=s}$Esto da la misma solución.${\displaystyle s=110}$como antes.

En este ejemplo la función f es de hecho una función dos a uno donde${\displaystyle {\displaystyle s\neq 0^{n}}}$.

Intuitivamente, este es un problema difícil de resolver de manera "clásica", incluso si se usa aleatoriedad y se acepta una pequeña probabilidad de error. La intuición detrás de la dificultad es razonablemente simple: si se quiere resolver el problema clásicamente, se necesitan encontrar dos entradas diferentes.${\displaystyle x}$y${\displaystyle y}$para qué${\displaystyle f(x)=f(y)}$No necesariamente hay ninguna estructura en la función.${\displaystyle f}$Eso nos ayudaría a encontrar dos entradas de ese tipo: más específicamente, podemos descubrir algo sobre${\displaystyle f}$(o lo que hace) solo cuando, para dos entradas diferentes, obtenemos la misma salida. En cualquier caso, tendríamos que adivinar.${\displaystyle {\displaystyle \Omega ({\sqrt {2^{n}}})}}$diferentes entradas antes de que sea probable encontrar un par en el que${\displaystyle f}$toma la misma salida, como en el problema del cumpleaños . Dado que, clásicamente, para encontrar s con un 100% de certeza se requeriría comprobar${\displaystyle {\displaystyle \Theta ({\sqrt {2^{n}}})}}$En cuanto a las entradas, el problema de Simon busca encontrar s utilizando menos consultas que este método clásico.

El circuito cuántico (véase la imagen) es la implementación de la parte cuántica del algoritmo de Simon. La subrutina cuántica del algoritmo utiliza la transformada de Hadamard.$${\displaystyle H^{\otimes n}|k\rangle ={\frac {1}{\sqrt {2^{n}}}}\sum _{j=0}^{2^{n}-1}(-1)^{k\cdot j}|j\rangle }$$dónde${\displaystyle k\cdot j=k_{1}j_{1}\oplus \ldots \oplus k_{n}j_{n}}$, dónde${\displaystyle \oplus }$denota XOR.

Primero, el algoritmo comienza con dos registros, inicializados a${\displaystyle |0\rangle ^{\otimes n}|0\rangle ^{\otimes n}}$. Luego, aplicamos la transformada de Hadamard al primer registro, lo que da como resultado el estado

${\displaystyle {\frac {1}{\sqrt {2^{n}}}}\sum _ {k=0}^{2^{n}-1}|k\rangle |0\rangle ^{\otimes n}.}$

Consulta el oráculo${\displaystyle U_{f}}$para obtener el estado

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

Aplique otra transformación de Hadamard al primer registro. Esto producirá el estado

${\displaystyle {\frac {1}{\sqrt {2^{n}}}}\sum _{k=0}^{2^{n}-1}\left[{\frac {1}{\sqrt {2^{n}}}}\sum _{j=0}^{2^{n}-1}(-1)^{j\cdot k}|j\rangle \right]|f(k)\rangle =\sum _{j=0}^{2^{n}-1}|j\rangle \left[{\frac {1}{2^{n}}}\sum _{k=0}^{2^{n}-1}(-1)^{j\cdot k}|f(k)\rangle \right].}$

Finalmente, medimos el primer registro (el algoritmo también funciona si el segundo registro se mide antes que el primero, pero esto no es necesario). La probabilidad de medir un estado${\displaystyle |j\rangle }$es$${\displaystyle \left|\left|{\frac {1}{2^{n}}}\sum _{k=0}^{2^{n}-1}(-1)^{j\cdot k}|f(k)\rangle \right|\right|^{2}}$$Esto se debe a que tomar la magnitud de este vector y elevarla al cuadrado suma todas las probabilidades de todas las posibles mediciones del segundo registro que deben tener el primer registro como${\displaystyle |j\rangle }$Existen dos casos para nuestra medición:

1. ${\displaystyle s=0^{n}}$y${\displaystyle f}$es uno a uno.
2. ${\displaystyle s\neq 0^{n}}$y${\displaystyle f}$es dos a uno.

Para el primer caso,$${\displaystyle \left|\left|{\frac {1}{2^{n}}}\sum _{k=0}^{2^{n}-1}(-1)^{j\cdot k}|f(k)\rangle \right|\right|^{2}={\frac {1}{2^{n}}}}$$puesto que en este caso,${\displaystyle f}$es uno a uno, lo que implica que el rango de${\displaystyle f}$es${\displaystyle \{0,1\}^{n}}$, lo que significa que la suma es sobre cada vector base. Para el segundo caso, observe que existen dos cadenas,${\displaystyle x_{1}}$y${\displaystyle x_{2}}$, de tal manera que${\displaystyle f(x_{1})=f(x_{2})=z}$, dónde${\displaystyle z\in \mathrm {range} (f)}$. De este modo,$${\displaystyle \left|\left|{\frac {1}{2^{n}}}\sum _{k=0}^{2^{n}-1}(-1)^{j\cdot k}|f(k)\rangle \right|\right|^{2}=\left|\left|{\frac {1}{2^{n}}}\sum _{z\,\in \,\mathrm {range} (f)}((-1)^{j\cdot x_{1}}+(-1)^{j\cdot x_{2}})|z\rangle \right|\right|^{2}}$$Además, dado que${\displaystyle x_{1}\oplus x_{2}=s}$,${\displaystyle x_{2}=x_{1}\oplus s}$, y entonces$${\displaystyle {\begin{aligned}\left|\left|{\frac {1}{2^{n}}}\sum _{z\,\in \,\mathrm {range} (f)}((-1)^{j\cdot x_{1}}+(-1)^{j\cdot x_{2}})|z\rangle \right|\right|^{2}&=\left|\left|{\frac {1}{2^{n}}}\sum _{z\,\in \,\mathrm {range} (f)}((-1)^{j\cdot x_{1}}+(-1)^{j\cdot (x_{1}\oplus s)})|z\rangle \right|\right|^{2}\\&=\left|\left|{\frac {1}{2^{n}}}\sum _{z\,\in \,\mathrm {range} (f)}((-1)^{j\cdot x_{1}}+(-1)^{j\cdot x_{1}\oplus j\cdot s})|z\rangle \right|\right|^{2}\\&=\left|\left|{\frac {1}{2^{n}}}\sum _{z\,\in \,\mathrm {range} (f)}(-1)^{j\cdot x_{1}}(1+(-1)^{j\cdot s})|z\rangle \right|\right|^{2}\end{aligned}}}$$Esta expresión ahora es fácil de evaluar. Recordemos que estamos midiendo${\displaystyle j}$. Cuando${\displaystyle j\cdot s=1}$, entonces esta expresión se evaluará a${\displaystyle 0}$y cuando${\displaystyle j\cdot s=0}$, entonces esta expresión será${\displaystyle 2^{-n+1}}$.

Por lo tanto, ambos cuando${\displaystyle s=0^{n}}$y cuando${\displaystyle s\neq 0^{n}}$, nuestra medida${\displaystyle j}$Satisface${\displaystyle j\cdot s=0}$.

Ejecutamos la parte cuántica del algoritmo hasta obtener una lista de cadenas de bits linealmente independientes.${\displaystyle y_{1},\ldots ,y_{n-1}}$y cada uno${\displaystyle y_{k}}$Satisface${\displaystyle y_{k}\cdot s=0}$Por lo tanto, podemos resolver eficientemente este sistema de ecuaciones de forma clásica para encontrar${\displaystyle s}$.

La probabilidad de que${\displaystyle y_{1},y_{2},\dots ,y_{n-1}}$son linealmente independientes es al menos$${\displaystyle \prod _{k=1}^{\infty }\left(1-{\frac {1}{2^{k}}}\right)=0.288788\dots }$$Una vez que resolvemos el sistema de ecuaciones y obtenemos una solución${\displaystyle s'}$, podemos probar si${\displaystyle f(0^{n})=f(s')}$Si esto es cierto, entonces lo sabemos.${\displaystyle s'=s}$, desde${\displaystyle f(0^{n})=f(0^{n}\oplus s)=f(s)}$. Si es el caso que${\displaystyle f(0^{n})\neq f(s')}$, entonces eso significa que${\displaystyle s=0^{n}}$, y${\displaystyle f(0^{n})\neq f(s')}$desde${\displaystyle f}$es uno a uno.

Podemos repetir el algoritmo de Simon un número constante de veces para aumentar arbitrariamente la probabilidad de éxito, manteniendo la misma complejidad temporal.

Consideremos la instancia más simple del algoritmo, con${\displaystyle n=1}$En este caso, al evolucionar el estado de entrada a través de una puerta Hadamard y el oráculo se obtiene el estado (salvo renormalización):

${\displaystyle |0\rangle |f(0)\rangle +|1\rangle |f(1)\rangle .}$

Si${\displaystyle s=1}$, eso es,${\displaystyle f(0)=f(1)}$, entonces medir el segundo registro siempre da el resultado${\displaystyle |f(0)\rangle }$y siempre resulta en que el primer registro colapse al estado (salvo renormalización):

${\displaystyle |0\rangle +|1\rangle .}$

Por lo tanto, al aplicar un Hadamard y medir el primer registro siempre se obtiene el resultado.${\displaystyle |0\rangle }$. Por otro lado, si${\displaystyle f}$es uno a uno, es decir,${\displaystyle s=0}$, entonces medir el primer registro después del segundo Hadamard puede resultar en ambos${\displaystyle |0\rangle }$y${\displaystyle |1\rangle }$, con igual probabilidad.

Nos recuperamos${\displaystyle s}$a partir de los resultados de la medición al observar si medimos siempre${\displaystyle |0\rangle }$, en cuyo caso${\displaystyle s=1}$o medimos ambos${\displaystyle |0\rangle }$y${\displaystyle |1\rangle }$con igual probabilidad, en cuyo caso inferimos que${\displaystyle s=0}$Este plan fracasará si${\displaystyle s=0}$pero, a pesar de todo, siempre encontramos el resultado.${\displaystyle |0\rangle }$, pero la probabilidad de este evento es${\displaystyle 2^{-N}}$con${\displaystyle N}$el número de mediciones realizadas, y por lo tanto se puede hacer exponencialmente pequeño aumentando las estadísticas.

Consideremos ahora el caso con${\displaystyle n=2}$. La parte inicial del algoritmo da como resultado el estado (hasta la renormalización):$${\displaystyle |00\rangle |f(00)\rangle +|01\rangle |f(01)\rangle +|10\rangle |f(10)\rangle +|11\rangle |f(11)\rangle .}$$Si${\displaystyle s=(00)}$, significado${\displaystyle f}$es inyectivo, entonces encontrar${\displaystyle |f(x)\rangle }$en el segundo registro siempre colapsa el primer registro a${\displaystyle |x\rangle }$, para todos${\displaystyle x\in \{0,1\}^{2}}$En otras palabras, aplicando las compuertas de Hadamard y midiendo el primer registro los cuatro resultados${\displaystyle 00,01,10,11}$Por lo tanto, se encuentran con igual probabilidad.

Supongamos por otro lado${\displaystyle s\neq (00)}$, Por ejemplo,${\displaystyle s=(01)}$Luego midiendo${\displaystyle |f(00)\rangle }$en el segundo registro colapsa el primer registro al estado${\displaystyle |00\rangle +|10\rangle }$Y, en términos más generales, la medición.${\displaystyle |f(xy)\rangle }$da${\displaystyle |x,y\rangle +|x,y\oplus 1\rangle =|x\rangle (|0\rangle +|1\rangle )}$en el primer registro. Aplicar las compuertas de Hadamard y medir en el primer registro puede dar como resultado los siguientes resultados:${\displaystyle 00}$y${\displaystyle 10}$con igual probabilidad.

Un razonamiento similar se aplica a los demás casos: si${\displaystyle s=(10)}$Entonces, los posibles resultados son:${\displaystyle 00}$y${\displaystyle 01}$, mientras que si${\displaystyle s=(11)}$Los posibles resultados son${\displaystyle 00}$y${\displaystyle 11}$, compatible con el${\displaystyle j\cdot s=0}$regla analizada en el caso general.

Para recuperarse${\displaystyle s}$Por lo tanto, solo necesitamos distinguir entre estos cuatro casos, recopilando suficientes estadísticas para asegurar que la probabilidad de confundir una distribución de probabilidad de resultado con otra sea suficientemente pequeña.