El problema de Simón

Problema en informática

En la teoría de la complejidad computacional y la computación cuántica , el problema de Simon es un problema computacional que se ha demostrado que se resuelve exponencialmente más rápido en una computadora cuántica que en una computadora clásica (es decir, tradicional). El algoritmo cuántico que resuelve el problema de Simon, generalmente llamado algoritmo de Simon , sirvió como inspiración para el algoritmo de Shor . ^[1] Ambos problemas son casos especiales del problema del subgrupo oculto abeliano , que ahora se sabe que tiene algoritmos cuánticos eficientes.

El problema se plantea en el modelo de complejidad del árbol de decisiones o complejidad de consultas y fue concebido por Daniel R. Simon en 1994. ^[2] Simon presentó un algoritmo cuántico que resuelve el problema de Simon exponencialmente más rápido con exponencialmente menos consultas que el mejor algoritmo clásico probabilístico (o determinista). En particular, el algoritmo de Simon utiliza un número lineal de consultas y cualquier algoritmo probabilístico clásico debe utilizar un número exponencial de consultas.

Este problema produce una separación de oráculo entre las clases de complejidad BPP (complejidad de consulta clásica de error acotado) y BQP (complejidad de consulta cuántica de error acotado). ^[3] Esta es la misma separación que logra el algoritmo de Bernstein-Vazirani , y diferente de la separación proporcionada por el algoritmo de Deutsch-Jozsa , que separa P y EQP . A diferencia del algoritmo de Bernstein-Vazirani, la separación del algoritmo de Simon es exponencial .

Debido a que este problema supone la existencia de un oráculo de "caja negra" altamente estructurado para lograr su aceleración, este problema tiene poco valor práctico. ^[4] Sin embargo, sin dicho oráculo, las aceleraciones exponenciales no se pueden demostrar fácilmente, ya que esto probaría que P es diferente de PSPACE .

Descripción del problema

Dada una función (implementada por una caja negra o un oráculo) con la promesa de que, para algún desconocido , para todos , ${\displaystyle f:\{0,1\}^{n}\rightarrow \{0,1\}^{n}}$ ${\displaystyle s\in \{0,1\}^{n}}$ ${\displaystyle x,y\in \{0,1\}^{n}}$

${\displaystyle f(x)=f(y)}$si y sólo si , ${\displaystyle x\oplus y\in \{0^{n},s\}}$

donde denota XOR bit a bit . El objetivo es identificar haciendo la menor cantidad posible de consultas. Tenga en cuenta que ${\displaystyle \oplus }$ ${\displaystyle s}$ ${\displaystyle f(x)}$

${\displaystyle a\oplus b=0^{n}}$Si y sólo si ${\displaystyle a=b}$

Además, para algunos y en , es único (no igual a ) si y solo si . Esto significa que es dos a uno cuando , y uno a uno cuando . También es el caso que implica , es decir, que muestra cómo es periódico. ${\displaystyle x}$ ${\displaystyle s}$ ${\displaystyle x\oplus y=s}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle s\neq 0^{n}}$ ${\displaystyle f}$ ${\displaystyle s\neq 0^{n}}$ ${\displaystyle s=0^{n}}$ ${\displaystyle x\oplus y=s}$ ${\displaystyle y=s\oplus x}$ $${\displaystyle f(x)=f(y)=f(x\oplus {s})}$$ ${\displaystyle f}$

La formulación del problema de decisión asociado al problema de Simon es distinguir cuándo ( es uno a uno) y cuándo ( es dos a uno). ${\displaystyle s=0^{n}}$ ${\displaystyle f}$ ${\displaystyle s\neq 0^{n}}$ ${\displaystyle f}$

Ejemplo

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

En este caso, (es decir, la solución). Cada salida de 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}$ ${\displaystyle f}$ ${\displaystyle s=110}$

Por ejemplo, las cadenas de entrada y se asignan (mediante ) a la misma cadena de salida . Es decir, y . Al aplicar XOR a 010 y 100 se obtiene 110, es decir ${\displaystyle 010}$ ${\displaystyle 100}$ ${\displaystyle f}$ ${\displaystyle 000}$ ${\displaystyle {\displaystyle f(010)=000}}$ ${\displaystyle {\displaystyle f(100)=000}}$ ${\displaystyle {\displaystyle 010\oplus 100=110=s}.}$

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

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

Problema de dureza

Intuitivamente, este es un problema difícil de resolver de una manera "clásica", incluso si uno usa aleatoriedad y acepta una pequeña probabilidad de error. La intuición detrás de la dificultad es razonablemente simple: si quieres resolver el problema de manera clásica, necesitas encontrar dos entradas diferentes y para las cuales . No hay necesariamente ninguna estructura en la función que nos ayude a encontrar dos de esas entradas: más específicamente, podemos descubrir algo sobre (o lo que hace) solo cuando, para dos entradas diferentes, obtenemos la misma salida. En cualquier caso, necesitaríamos adivinar diferentes entradas antes de tener la probabilidad de encontrar un par en que tome 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 verificar las entradas, el problema de Simon busca encontrar s usando menos consultas que este método clásico. ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle f(x)=f(y)}$ ${\displaystyle f}$ ${\displaystyle f}$ ${\displaystyle {\displaystyle \Omega ({\sqrt {2^{n}}})}}$ ${\displaystyle f}$ ${\displaystyle {\displaystyle \Theta ({\sqrt {2^{n}}})}}$

Algoritmo de Simon

Circuito cuántico que representa/implementa el algoritmo de Simon

El algoritmo en su conjunto utiliza una subrutina para ejecutar los dos pasos siguientes:

1. Ejecute la subrutina cuántica las veces esperadas para obtener una lista de cadenas de bits linealmente independientes . ${\displaystyle O(n)}$ ${\displaystyle y_{1},...,y_{n-1}}$
2. Cada uno satisface , por lo que podemos resolver el sistema de ecuaciones que esto produce para obtener . ${\displaystyle y_{k}}$ ${\displaystyle y_{k}\cdot s=0}$ ${\displaystyle s}$

Subrutina cuántica

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

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

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

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

${\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].}$

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

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

Para el primer caso, ya que en este caso, es uno a uno, lo que implica que el rango de es , lo que significa que la suma es sobre cada vector base. Para el segundo caso, observe que existen dos cadenas, y , tales que , donde . Por lo tanto, Además, ya que , , y por lo tanto Esta expresión ahora es fácil de evaluar. Recuerde que estamos midiendo . Cuando , entonces esta expresión se evaluará como , y cuando , entonces esta expresión será . $${\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}}}}$$ ${\displaystyle f}$ ${\displaystyle f}$ ${\displaystyle \{0,1\}^{n}}$ ${\displaystyle x_{1}}$ ${\displaystyle x_{2}}$ ${\displaystyle f(x_{1})=f(x_{2})=z}$ ${\displaystyle z\in \mathrm {range} (f)}$ $${\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}}$$ ${\displaystyle x_{1}\oplus x_{2}=s}$ ${\displaystyle x_{2}=x_{1}\oplus s}$ $${\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}}}$$ ${\displaystyle j}$ ${\displaystyle j\cdot s=1}$ ${\displaystyle 0}$ ${\displaystyle j\cdot s=0}$ ${\displaystyle 2^{-n+1}}$

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

Posprocesamiento clásico

Ejecutamos la parte cuántica del algoritmo hasta que tengamos una lista linealmente independiente de cadenas de bits y cada una satisfaga . Por lo tanto, podemos resolver este sistema de ecuaciones de manera clásica y eficiente para encontrar . ${\displaystyle y_{1},\ldots ,y_{n-1}}$ ${\displaystyle y_{k}}$ ${\displaystyle y_{k}\cdot s=0}$ ${\displaystyle s}$

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

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

Ejemplos explícitos del algoritmo de Simon para unos pocos qubits

Un qubit

Consideremos la instancia más simple del algoritmo, con . En este caso, se hace evolucionar el estado de entrada a través de una compuerta Hadamard y el oráculo da como resultado el estado (hasta la renormalización): ${\displaystyle n=1}$

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

Si , es decir, , entonces la medición del segundo registro siempre arroja el resultado , y siempre da como resultado que el primer registro colapse al estado (hasta la renormalización): ${\displaystyle s=1}$ ${\displaystyle f(0)=f(1)}$ ${\displaystyle |f(0)\rangle }$

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

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

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

Dos qubits

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

Supongamos, por otro lado , por ejemplo, . Entonces, la medición en el segundo registro colapsa el primer registro al estado . Y, de manera más general, la medición da como resultado . Por lo tanto, la aplicación de puertas de Hadamard y la medición en el primer registro pueden dar como resultado los resultados y con probabilidades iguales. ${\displaystyle s\neq (00)}$ ${\displaystyle s=(01)}$ ${\displaystyle |f(00)\rangle }$ ${\displaystyle |00\rangle +|10\rangle }$ ${\displaystyle |f(xy)\rangle }$ ${\displaystyle |x,y\rangle +|x,y\oplus 1\rangle =|x\rangle (|0\rangle +|1\rangle )}$ ${\displaystyle 00}$ ${\displaystyle 10}$

Un razonamiento similar se aplica a los otros casos: si entonces los resultados posibles son y , mientras que si los resultados posibles son y , de manera compatible con la regla discutida en el caso general. ${\displaystyle s=(10)}$ ${\displaystyle 00}$ ${\displaystyle 01}$ ${\displaystyle s=(11)}$ ${\displaystyle 00}$ ${\displaystyle 11}$ ${\displaystyle j\cdot s=0}$

Para recuperarnos , sólo necesitamos distinguir entre estos cuatro casos y recopilar suficientes estadísticas para garantizar que la probabilidad de confundir una distribución de probabilidad de resultado con otra sea suficientemente pequeña. ${\displaystyle s}$

Complejidad

El algoritmo de Simon requiere consultas a la caja negra, mientras que un algoritmo clásico necesitaría al menos consultas. También se sabe que el algoritmo de Simon es óptimo en el sentido de que cualquier algoritmo cuántico para resolver este problema requiere consultas. ^{[5] [6]} ${\displaystyle O(n)}$ ${\displaystyle \Omega (2^{n/2})}$ ${\displaystyle \Omega (n)}$

Véase también

• Algoritmo de Jozsa

Referencias

1. Shor, Peter W. (1 de enero de 1999). "Algoritmos de tiempo polinomial para factorización prima y logaritmos discretos en una computadora cuántica". SIAM Review . 41 (2): 303–332. arXiv : quant-ph/9508027 . doi :10.1137/S0036144598347011. ISSN  0036-1445.
2. Simon, Daniel R. (1997-10-01). "Sobre el poder de la computación cuántica". Revista SIAM de Computación . 26 (5): 1474–1483. doi :10.1137/S0097539796298637. ISSN  0097-5397.
3. Preskill, John (1998). Apuntes de la clase de Física 229: Información y computación cuántica. pp. 273–275.
4. Aaronson, Scott (2018). Introducción a la ciencia de la información cuántica. Notas de clase (PDF) . pp. 144–151.
5. Koiran, P.; Nesme, V.; Portier, N. (2007), "La complejidad de consulta cuántica del problema del subgrupo oculto abeliano", Theoretical Computer Science , 380 (1–2): 115–126, doi : 10.1016/j.tcs.2007.02.057 , consultado el 6 de junio de 2011
6. Koiran, P.; Nesme, V.; Portier, N. (2005), "Un límite inferior cuántico para la complejidad de consulta del problema de Simon", Proc. ICALP , 3580 : 1287–1298, arXiv : quant-ph/0501060 , Bibcode :2005quant.ph..1060K , consultado el 6 de junio de 2011