Dada una función (implementada por una caja negra u oráculo) con la promesa de que, por algún desconocido , para todos ,
- si y solo si ,
El objetivo es identificar s haciendo la menor cantidad posible de consultas af (x) .
Otro enunciado común de este problema es el de distinguir caso, donde la función es uno a uno, desde el caso, donde la función es dos a uno y satisface .
Ejemplo
Por ejemplo, si , entonces la siguiente función es un ejemplo de una función que satisface la propiedad requerida y recién mencionada:
| |
---|
000 | 101 |
001 | 010 |
010 | 000 |
011 | 110 |
100 | 000 |
101 | 110 |
110 | 101 |
111 | 010 |
En este caso, (es decir, la solución). Se puede verificar fácilmente que cada salida de ocurre dos veces, y las dos cadenas de entrada correspondientes a cualquier salida dada tienen XOR bit a bit igual a .
Por ejemplo, las cadenas de entrada y ambos están mapeados (por ) a la misma cadena de salida . y . Si aplicamos XOR a 010 y 100 obtenemos 110, es decir también se puede verificar usando cadenas de entrada 001 y 111 que están mapeadas (por f) a la misma cadena de salida 010. Si aplicamos XOR a 001 y 111, obtenemos 110, es decir . Esto da la misma solución resolvimos antes.
En este ejemplo, la función f es de hecho una función de dos a uno donde.
Para una función uno a uno, tal que
Dureza del problema
Intuitivamente, este es un problema muy difícil de resolver de una manera "clásica", incluso si se usa la aleatoriedad y se acepta una pequeña probabilidad de error. La intuición detrás de la dureza es razonablemente simple: si desea resolver el problema de manera clásica, necesita encontrar dos entradas diferentes y para cual . No hay necesariamente ninguna estructura en la función que nos ayudaría a encontrar dos de estas 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, tendríamos que adivinar diferentes entradas antes de que sea probable encontrar un par en el que toma la misma salida, según el problema de cumpleaños . Dado que, clásicamente, para encontrar s con un 100% de certeza, sería necesario verificar hastaentradas, el problema de Simon busca encontrar s usando menos consultas que este método clásico.
Ocurrencia
La idea de alto nivel detrás del algoritmo de Simon es "sondear" (o "muestrear") un circuito cuántico (ver la imagen a continuación) "suficientes veces" para encontrar ( linealmente independientes ) cadenas de n bits, es decir
tal que se satisfagan las siguientes ecuaciones
dónde es el módulo-2 producto de punto ; es decir,, y , por y para .
Entonces, este sistema lineal contiene ecuaciones lineales en incógnitas (es decir, las partes de ), y el objetivo es resolverlo para obtener , y es fijo para una función dada . No siempre existe una solución (única).
Circuito cuántico de Simon
Circuito cuántico que representa / implementa el algoritmo de Simon
El circuito cuántico (vea la imagen) es la implementación (y visualización) de la parte cuántica del algoritmo de Simon.
Primero se prepara un estado cuántico de todos ceros (esto se puede hacer fácilmente). El estado representa dónde es el número de qubits. Luego, la mitad de este estado se transforma mediante una transformación de Hadamard. A continuación, el resultado se introduce en un oráculo (o "caja negra"), que sabe cómo calcular. Dónde actúa sobre los dos registros como . Después de eso, parte de la salida producida por el oráculo se transforma utilizando otra transformación de Hadamard. Finalmente, se realiza una medición del estado cuántico global resultante. Es durante esta medición que recuperamos las cadenas de n bits,, mencionado en la subsección anterior.
El algoritmo de Simon se puede considerar como un algoritmo iterativo (que hace uso de un circuito cuántico) seguido de un algoritmo (posiblemente) clásico para encontrar la solución a un sistema lineal de ecuaciones.
En esta sección, se explica cada parte del algoritmo de Simon (en detalle). Puede ser útil mirar la imagen del circuito cuántico de Simon anterior mientras lee cada una de las siguientes subsecciones.
Aporte
El algoritmo de Simon comienza con la entrada , dónde es el estado cuántico con ceros.
(El símbolo es el símbolo típico utilizado para representar el producto tensorial . Para no saturar la notación, el símbolo a veces se omite: por ejemplo, en la oración anterior, es equivalente a . En este artículo, se utiliza (a menudo) para eliminar la ambigüedad o para evitar confusiones).
Ejemplo
Entonces, por ejemplo, si , entonces la entrada inicial es
- .
Primera transformación de Hadamard
Después de eso, la entrada (como se describe en la subsección anterior) se transforma utilizando una transformación de Hadamard . Específicamente, la transformación de Hadamard (el producto tensorial también se puede aplicar a matrices) se aplica a la primera qubits, es decir, al estado "parcial" , de modo que el estado compuesto después de esta operación es
dónde denota cualquier cadena de n bits (es decir, la suma es sobre cualquier cadena de n bits). El termino se puede factorizar fuera de la suma porque no depende de (es decir, es una constante con respecto a ), y .
Ejemplo
Supongamos (de nuevo) , entonces la entrada es y la transformación de Hadamard es
Si ahora aplicamos al primero , es decir, al estado
obtenemos
Para obtener el estado cuántico compuesto final, ahora podemos tensor del producto con , es decir
Oráculo
Luego llamamos al oráculo o caja negra ( en la imagen de arriba) para calcular la función en la entrada transformada , para obtener el estado
Segunda transformación de Hadamard
Luego aplicamos la transformada de Hadamard a los estados de la primera qubits del estado , para obtener
dónde puede ser o , Dependiendo de , dónde , por . Entonces, por ejemplo, si y , luego , que es un número par. Así, en este caso,, y es siempre un número no negativo.
La intuición detrás de esta transformación inversa de Hadamard que se aplica aquí se puede encontrar en las notas de clase de CMU
Reescribamos ahora
como sigue
Esta manipulación será conveniente para comprender las explicaciones en los siguientes apartados. El orden de las sumas se ha invertido.
Medición
Después de haber realizado todas las operaciones descritas anteriormente, al final del circuito se realiza una medición .
Ahora hay dos casos posibles que debemos considerar por separado
- o
- , dónde .
Primer caso
Primero analicemos el caso (especial) , Lo que significa que es (por requisito) una función uno a uno (como se explicó anteriormente en la "descripción del problema").
Tengamos en cuenta que el estado cuántico antes de la medición es
Ahora, la probabilidad de que la medición dé como resultado cada cadena es
Esto se sigue de
porque los dos vectores solo difieren en el orden de sus entradas, dado que es uno a uno .
El valor del lado derecho, es decir
se ve más fácilmente como .
Por lo tanto, cuando , el resultado es simplemente una distribución uniforme -cadena de bits.
Segundo caso
Analicemos ahora el caso , dónde . En este caso, es una función de dos a uno, es decir, hay dos entradas que se asignan a la misma salida de .
El análisis realizado en el primer caso sigue siendo válido para este segundo caso, es decir, la probabilidad de medir cualquier cadena dada. todavía se puede representar como
Sin embargo, en este segundo caso, todavía tenemos que averiguar cuál es este valor de es. Veamos por qué en las siguientes explicaciones.
Dejar , la imagen de . Dejar (es decir es una salida de la función ), luego para cada , hay uno (y solo uno) , tal que ; además, también tenemos, que es equivalente a (consulte la sección "descripción del problema" anterior para una revisión de este concepto).
Por lo tanto, tenemos
Dado que , entonces podemos reescribir el coeficiente como sigue
Dado que , luego podemos escribir la expresión anterior como
Entonces, además se puede escribir como
Número impar
Ahora si es un número impar, entonces . En ese caso,
En consecuencia, tenemos
Dado que , entonces nunca tendremos este caso, es decir, sin cadena se ve (después de la medición) en este caso.
(Este es el caso en el que tenemos una interferencia destructiva ).
Número par
Si, en cambio, es un número par (por ejemplo, cero), entonces . En ese caso,
Entonces tenemos
Es el caso de la interferencia constructiva ,
. Entonces, en resumen, para este segundo caso, tenemos las siguientes probabilidades
Postprocesamiento clásico
Cuando ejecutamos el circuito (operaciones) anterior, hay dos casos:
- en el caso (especial) donde (es decir ), los resultados de la medición en cada cadena con probabilidad
- en el caso (dónde ), la probabilidad de obtener cada cadena es dado por
Por tanto, en ambos casos, el resultado de la medición es una cadena que satisface , y la distribución es uniforme en todas las cadenas que satisfacen esta restricción.
¿Es esta información suficiente para determinar ? La respuesta es "sí", siempre que el proceso (arriba) se repita varias veces (y se acepte una pequeña probabilidad de falla). Específicamente, si se ejecuta el proceso anterior veces, obtenemos instrumentos de cuerda , tal que
Este es un sistema de ecuaciones lineales en incógnitas (es decir, las partes de ), y el objetivo es resolverlo para obtener . Tenga en cuenta que cada uno de los que obtenemos después de cada medición (para cada "ronda" del proceso) es, por supuesto, el resultado de una medición, por lo que se conoce (al final de cada "ronda").
Solo obtenemos una solución única distinta de cero si tenemos "suerte" y son linealmente independientes. La probabilidad de que son linealmente independientes es al menos
Si tenemos independencia lineal, podemos resolver el sistema para obtener una solución candidata y prueba eso . Si, lo sabemos , y el problema ha sido resuelto. Si, debe ser eso (porque, si esto no fuera así, la única solución distinta de cero a las ecuaciones lineales habría sido ). De cualquier manera, una vez que tengamos independencia lineal, podremos resolver el problema.