<jupyter_start><jupyter_text>Algoritmo de Simón En esta sección, primero presentamos el problema de Simon y los algoritmos clásicos y cuánticos para resolverlo. Luego implementamos el algoritmo cuántico usando Qiskit y lo ejecutamos en un simulador y dispositivo.  1. IntroducciónEl algoritmo de Simon, presentado por primera vez en la Referencia [1], fue el primer algoritmo cuántico en mostrar una aceleración exponencial frente al mejor algoritmo clásico para resolver un problema específico. Esto inspiró los algoritmos cuánticos basados en la transformada cuántica de Fourier, que se utiliza en el algoritmo cuántico más famoso: el algoritmo de factorización de Shor. 1a. El problema de Simón Tenemos una función de caja negra desconocida $f$, que se garantiza que sea uno a uno ($1:1$) o dos a uno ($2:1$), donde uno a uno y dos- Las funciones a uno tienen las siguientes propiedades:- **uno a uno** : asigna exactamente una salida única para cada entrada. Un ejemplo con una función que toma 4 entradas es:$$f(1) \rightarrow 1, \quad f(2) \rightarrow 2, \quad f(3) \rightarrow 3, \quad f(4) \rightarrow 4$$- **dos a uno** : mapea exactamente dos entradas a cada salida única. Un ejemplo con una función que toma 4 entradas es:$$f(1) \rightarrow 1, \quad f(2) \rightarrow 2, \quad f(3) \rightarrow 1, \quad f(4) \rightarrow 2$$Este mapeo de dos a uno está de acuerdo con una cadena de bits oculta, $b$, donde:$$ \textrm{dado }x_1,x_2: \quad f(x_1) = f(x_2) \ \textrm{está garantizado}: \quad x_1 \oplus x_2 = b $$Dada esta caja negra $f$, ¿qué tan rápido podemos determinar si $f$ es uno a uno o dos a uno? Entonces, si $f$ resulta ser dos a uno, ¿con qué rapidez podemos determinar $b$? Resulta que ambos casos se reducen al mismo problema de encontrar $b$, donde una cadena de bits de $b={000...}$ representa el uno a uno $f$.  1b. Algoritmo de Simón  Solución clásicaClásicamente, si queremos saber qué es $b$ con 100% de certeza para un $f$ dado, tenemos que verificar hasta $2^{n−1}+1$ entradas, donde n es el número de bits en el aporte. Esto significa verificar un poco más de la mitad de todas las entradas posibles hasta que encontremos dos casos de la misma salida. Al igual que el problema de Deutsch-Jozsa, si tenemos suerte, podríamos resolver el problema con nuestros dos primeros intentos. Pero si obtenemos un $f$ que es uno a uno, o tenemos *mucha* mala suerte con un $f$ que es dos a uno, entonces nos quedamos con los $2^{n−1}+ completos. 1$. Hay algoritmos conocidos que tienen un límite inferior de $\Omega(2^{n/2})$ (consulte la Referencia 2 a continuación), pero, en términos generales, la complejidad crece exponencialmente con n.  Solución CuánticaEl circuito cuántico que implementa el algoritmo de Simon se muestra a continuación.![imagen1](images/simon_steps.png)Donde la función de consulta, $\text{Q}_f$ actúa sobre dos registros cuánticos como:$$ \lvert x \rangle \lvert a \rangle \rightarrow \lvert x \rangle \lvert a \oplus f(x) \rangle $$En el caso específico de que el segundo registro esté en el estado $|0\rangle = |00\dots0\rangle$ tenemos:$$ \lvert x \rangle \lvert 0 \rangle \rightarrow \lvert x \rangle \lvert f(x) \rangle $$El algoritmo implica los siguientes pasos.   Dos registros de entrada $n$-qubit se inicializan en el estado cero:$$\lvert \psi_1 \rangle = \lvert 0 \rangle^{\otimes n} \lvert 0 \rangle^{\otimes n} $$    Aplique una transformada de Hadamard al primer registro:$$\lvert \psi_2 \rangle = \frac{1}{\sqrt{2^n}} \sum_{x \in {0,1}^{n} } \lvert x \rangle\lvert 0 \rangle^ {\ veces n} $$      Aplicar la función de consulta $\text{Q}_f$:$$ \lvert \psi_3 \rangle = \frac{1}{\sqrt{2^n}} \sum_{x \in {0,1}^{n} } \lvert x \rangle \lvert f(x) \rango $$      Mida el segundo registro. Se observará un cierto valor de $f(x)$. Debido a la configuración del problema, el valor observado $f(x)$ podría corresponder a dos posibles entradas: $x$ y $y = x \oplus b $. Por lo tanto el primer registro se convierte en:$$\lvert \psi_4 \rangle = \frac{1}{\sqrt{2}} \left( \lvert x \rangle + \lvert y \rangle \right)$$donde omitimos el segundo registro ya que se ha medido.      Aplicar Hadamard en el primer registro:$$ \lvert \psi_5 \rangle = \frac{1}{\sqrt{2^{n+1}}} \sum_{z \in {0,1}^{n} } \left[ (-1) ^{x \cdot z} + (-1)^{y \cdot z} \right] \lvert z \rangle $$      Medir el primer registro dará una salida solo si:$$ (-1)^{x \cdot z} = (-1)^{y \cdot z} $$lo que significa: $$ x \cdot z = y \cdot z \ x \cdot z = \left( x \oplus b \right) \cdot z \ x \cdot z = x \cdot z \oplus b \cdot z \ b \cdot z = 0 \text{ (mod 2)} $$Se medirá una cadena $z$, cuyo producto interior con $b = 0$. Así, repitiendo el algoritmo $\approx n$ veces, podremos obtener $n$ diferentes valores de $z$ y se puede escribir el siguiente sistema de ecuaciones:$$ \begin{casos} b \cdot z_1 = 0 \ b \cdot z_2 = 0 \ \quad \vdots \ b \cdot z_n = 0 \end{casos}$$A partir de la cual se puede determinar $b$, por ejemplo mediante eliminación gaussiana.Entonces, en este problema en particular, el algoritmo cuántico realiza exponencialmente menos pasos que el clásico. Una vez más, puede ser difícil imaginar una aplicación de este algoritmo (aunque inspiró el algoritmo más famoso creado por Shor), pero representa la primera prueba de que puede haber una aceleración exponencial en la resolución de un problema específico mediante el uso de un cuántico. ordenador en lugar de uno clásico.  2. EjemploVeamos el ejemplo del algoritmo de Simon para 2 qubits con la cadena secreta $b=11$, de modo que $f(x) = f(y)$ si $y = x \oplus b$. El circuito cuántico para resolver el problema es:![imagen2](images/simon_example.png)    Dos registros de entrada de $2$-qubit se inicializan en el estado cero:$$\lvert \psi_1 \rangle = \lvert 0 0 \rangle_1 \lvert 0 0 \rangle_2 $$    Aplicar puertas de Hadamard a los qubits en el primer registro:$$\lvert \psi_2 \rangle = \frac{1}{2} \left( \lvert 0 0 \rangle_1 + \lvert 0 1 \rangle_1 + \lvert 1 0 \rangle_1 + \lvert 1 1 \rangle_1 \right) \lvert 0 0 \rangle_2 $$    Para la cadena $b=11$, la función de consulta se puede implementar como $\text{Q}_f = CX_{1_a 2_a}CX_{1_a 2_b}CX_{1_b 2_a}CX_{1_b 2_b}$ (como se ve en la diagrama de circuito anterior):$$ \begin{aligned} \lvert \psi_3 \rangle = \frac{1}{2} ( ; &amp; \lvert 0 0 \rangle_1 ; \lvert 0\oplus 0 \oplus 0, &amp; 0 \oplus 0 \oplus 0 \rangle_2 &amp;\[5 puntos]- &amp; \lvert 0 1 \rangle_1 ; \lvert 0\oplus 0 \oplus 1, &amp; 0 \oplus 0 \oplus 1 \rangle_2 &amp;\[6pt]- &amp; \lvert 1 0 \rangle_1 ; \lvert 0\oplus 1 \oplus 0, &amp; 0 \oplus 1 \oplus 0 \rangle_2 &amp;\[6pt]- &amp; \lvert 1 1 \rangle_1 ; \lvert 0\oplus 1 \oplus 1, &amp; 0 \oplus 1 \oplus 1 \rangle_2 &amp; ; )\ \end{alineado} $$Por lo tanto:$$ \begin{aligned} \lvert \psi_3 \rangle = \frac{1}{2} ( \quad &amp; \lvert 0 0 \rangle_1 \lvert 0 0 \rangle_2 &amp; \[6pt]- &amp; \lvert 0 1 \rangle_1 \lvert 1 1 \rangle_2 &amp; \[6pt]- &amp; \lvert 1 0 \rangle_1 \lvert 1 1 \rangle_2 &amp; \[6pt]- &amp; \lvert 1 1 \rangle_1 \lvert 0 0 \rangle_2 &amp; ; )\ \end{alineado} $$          Medimos el segundo registro. Con una probabilidad de $50\%$, veremos $\lvert 0 0 \rangle_2$ o $\lvert 1 1 \rangle_2$. Por el bien del ejemplo, supongamos que vemos $\lvert 1 1 \rangle_2$. El estado del sistema es entonces    $$ \lvert \psi_4 \rangle = \frac{1}{\sqrt{2}} \left( \lvert 0 1 \rangle_1 + \lvert 1 0 \rangle_1 \right) $$donde omitimos el segundo registro ya que se ha medido.      Aplicar Hadamard en el primer registro $$ \lvert \psi_5 \rangle = \frac{1}{2\sqrt{2}} \left[ \left( \lvert 0 \rangle + \lvert 1 \rangle \right) \otimes \left( \lvert 0 \rangle - \lvert 1 \rangle \right) + \left( \lvert 0 \rangle - \lvert 1 \rangle \right) \otimes \left( \lvert 0 \rangle + \lvert 1 \ rangle \right) \right] \\ = \frac{1}{2\sqrt{2}} \left[ \lvert 0 0 \rangle - \lvert 0 1 \rangle + \lvert 1 0 \rangle - \lvert 1 1 \rangle + \lvert 0 0 \rangle + \lvert 0 1 \rangle - \lvert 1 0 \rangle - \lvert 1 1 \rangle \right] \\ = \frac{1}{\sqrt{2}} \ izquierda( \lvert 0 0 \rangle - \lvert 1 1 \rangle \right)$$      Medir el primer registro dará $\lvert 0 0 \rangle$ o $\lvert 1 1 \rangle$ con la misma probabilidad.    Si vemos $\lvert 1 1 \rangle$, entonces:$$ b \cdot 11 = 0 $$lo que nos dice que $b \neq 01$ o $10$, y las dos posibles soluciones restantes son $b = 00$ o $b = 11$. Tenga en cuenta que $b = 00$ siempre será una solución trivial para nuestras ecuaciones simultáneas. Si repetimos los pasos 1-6 muchas veces, solo mediríamos $|00\rangle$ o $|11\rangle$ como$$ segundo \cdot 11 = 0 $$ $$ segundo \cdot 00 = 0 $$son las únicas ecuaciones que satisfacen $b=11$. Podemos verificar $b=11$ eligiendo una entrada aleatoria ($x_i$) y comprobando $f(x_i) = f(x_i \oplus b)$. Por ejemplo:$$ 01 \omás b = 10 $$ $$ f(01) = f(10) = 11$$     3. Implementación de QiskitAhora implementamos el algoritmo de Simon para un ejemplo con $3$-qubits y $b=110$.<jupyter_code># importing Qiskit
from qiskit import IBMQ, Aer
from qiskit.providers.ibmq import least_busy
from qiskit import QuantumCircuit, transpile

# import basic plot tools
from qiskit.visualization import plot_histogram
from qiskit_textbook.tools import simon_oracle<jupyter_output><empty_output><jupyter_text>La función `simon_oracle` (importada arriba) crea un oráculo Simon para la cadena de bits `b` . Esto se da sin explicación, pero discutiremos el método en la [sección 4](oracle) .En Qiskit, las mediciones solo se permiten al final del circuito cuántico. En el caso del algoritmo de Simon, en realidad no nos importa la salida del segundo registro y solo mediremos el primer registro.<jupyter_code>b = '110'

n = len(b)
simon_circuit = QuantumCircuit(n*2, n)

# Apply Hadamard gates before querying the oracle
simon_circuit.h(range(n))    
    
# Apply barrier for visual separation
simon_circuit.barrier()

simon_circuit = simon_circuit.compose(simon_oracle(b))

# Apply barrier for visual separation
simon_circuit.barrier()

# Apply Hadamard gates to the input register
simon_circuit.h(range(n))

# Measure qubits
simon_circuit.measure(range(n), range(n))
simon_circuit.draw()<jupyter_output><empty_output><jupyter_text>3a. Experimenta con simuladoresPodemos ejecutar el circuito anterior en el simulador.<jupyter_code># use local simulator
aer_sim = Aer.get_backend('aer_simulator')
results = aer_sim.run(simon_circuit).result()
counts = results.get_counts()
plot_histogram(counts)<jupyter_output><empty_output><jupyter_text>Como ya conocemos $b$, podemos verificar que estos resultados satisfacen $b\cdot z = 0 \pmod{2}$:<jupyter_code># Calculate the dot product of the results
def bdotz(b, z):
    accum = 0
    for i in range(len(b)):
        accum += int(b[i]) * int(z[i])
    return (accum % 2)

for z in counts:
    print( '{}.{} = {} (mod 2)'.format(b, z, bdotz(b,z)) )<jupyter_output>110.111 = 0 (mod 2)
110.001 = 0 (mod 2)
110.110 = 0 (mod 2)
110.000 = 0 (mod 2)<jupyter_text>Usando estos resultados, podemos recuperar el valor de $b = 110$ resolviendo este conjunto de ecuaciones simultáneas. Por ejemplo, digamos que primero medimos `001` , esto nos dice:$$ \require{cancel} \begin{aligned} b \cdot 001 &amp;= 0 \ (b_2 \cdot 0) + (b_1 \cdot 0) + (b_0 \cdot 1) &amp; = 0 \ (\cancel{b_2 \ cdot 0}) + (\cancel{b_1 \cdot 0}) + (b_0 \cdot 1) &amp; = 0 \ b_0 &amp; = 0\ \end{alineado} $$Si a continuación medimos `111` , tenemos:$$ \require{cancel} \begin{aligned} b \cdot 111 &amp;= 0 \ (b_2 \cdot 1) + (b_1 \cdot 1) + (\cancel{0 \cdot 1}) &amp; = 0 \ (b_2 \cdot 1) + (b_1 \cdot 1) &amp; = 0 \ \end{alineado} $$Lo que nos dice:$$ b_2 = b_1 = 0, \quad b = 000 $$o$$ b_2 = b_1 = 1, \quad b = 110 $$De los cuales $b = 110$ es la solución no trivial de nuestras ecuaciones simultáneas. Podemos resolver estos problemas en general usando [la eliminación gaussiana](https://mathworld.wolfram.com/GaussianElimination.html) , que tiene un tiempo de ejecución de $O(n^3)$.  3b. Experimente con dispositivos realesEl circuito de la [sección 3a](simulation) utiliza $2n = 6$ qubits, mientras que, en el momento de escribir este artículo, muchos dispositivos IBM Quantum solo tienen 5 qubits. Ejecutaremos el mismo código, pero en su lugar usaremos $b=11$ como en el ejemplo de la sección 2, que requiere solo 4 qubits.<jupyter_code>b = '11'
n = len(b)
simon_circuit_2 = QuantumCircuit(n*2, n)

# Apply Hadamard gates before querying the oracle
simon_circuit_2.h(range(n))

# Query oracle
simon_circuit_2 = simon_circuit_2.compose(simon_oracle(b))

# Apply Hadamard gates to the input register
simon_circuit_2.h(range(n))

# Measure qubits
simon_circuit_2.measure(range(n), range(n))
simon_circuit_2.draw()<jupyter_output><empty_output><jupyter_text>Este circuito es ligeramente diferente al circuito que se muestra en la [sección 2](example) . Las salidas son diferentes, pero las colisiones de entrada son las mismas, es decir, ambas tienen la propiedad de que $f(x) = f(x \oplus 11)$.<jupyter_code># Load our saved IBMQ accounts and get the least busy backend device with less than or equal to 5 qubits
IBMQ.load_account()
provider = IBMQ.get_provider(hub='ibm-q')
backend = least_busy(provider.backends(filters=lambda x: x.configuration().n_qubits >= n and 
                                   not x.configuration().simulator and x.status().operational==True))
print("least busy backend: ", backend)

# Execute and monitor the job
from qiskit.tools.monitor import job_monitor
shots = 1024
transpiled_simon_circuit = transpile(simon_circuit_2, backend, optimization_level=3)
job = backend.run(transpiled_simon_circuit)
job_monitor(job, interval=2)
# Get results and plot counts
device_counts = job.result().get_counts()
plot_histogram(device_counts)
# Calculate the dot product of the results
def bdotz(b, z):
    accum = 0
    for i in range(len(b)):
        accum += int(b[i]) * int(z[i])
    return (accum % 2)

print('b = ' + b)
for z in device_counts:
    print( '{}.{} = {} (mod 2) ({:.1f}%)'.format(b, z, bdotz(b,z), device_counts[z]*100/shots))<jupyter_output>b = 11
11.00 = 0 (mod 2) (41.9%)
11.01 = 1 (mod 2) (5.0%)
11.10 = 1 (mod 2) (6.4%)
11.11 = 0 (mod 2) (46.7%)<jupyter_text>Como vemos, los resultados más significativos son aquellos para los que $b\cdot z = 0$ (mod 2). Los otros resultados son erróneos, pero tienen una menor probabilidad de ocurrir. Suponiendo que es poco probable que midamos los resultados erróneos, podemos usar una computadora clásica para recuperar el valor de $b$ resolviendo el sistema lineal de ecuaciones. Para este caso de $n=2$, $b = 11$.  4. oráculoEl [ejemplo](example) anterior y la [implementación](implementation) del algoritmo de Simon son específicos para valores específicos de $b$. Para extender el problema a otras cadenas de bits secretas, debemos discutir la función de consulta de Simon u Oracle con más detalle.El algoritmo de Simon trata de encontrar una cadena de bits oculta $b \in {0,1}^n$ de un oráculo $f_b$ que satisface $f_b(x) = f_b(y)$ si y solo si $y = x \oplus b$ para todo $x \in {0,1}^n$. Aquí, $\oplus$ es la operación XOR bit a bit. Por lo tanto, si $b = 0\ldots 0$, es decir, la cadena de bits de todos ceros, entonces $f_b$ es una función 1 a 1 (o permutación). De lo contrario, si $b \neq 0\ldots 0$, entonces $f_b$ es una función de 2 a 1.En el algoritmo, el oráculo recibe $|x\rangle|0\rangle$ como entrada. Con respecto a un $b$ predeterminado, el oráculo escribe su salida en el segundo registro para que transforme la entrada en $|x\rangle|f_b(x)\rangle$ tal que $f(x) = f(x\ oplus b)$ para todo $x \in {0,1}^n$.Dicha función de caja negra se puede realizar mediante los siguientes procedimientos.- Copie el contenido del primer registro al segundo registro. $$ |x\rangle|0\rangle \rightarrow |x\rangle|x\rangle $$- **(Creación de mapeo 1 a 1 o 2 a 1)** Si $b$ no es todo cero, entonces existe el índice mínimo $j$ para que $b_j = 1$. Si $x_j = 0$, entonces XOR el segundo registro con $b$. De lo contrario, no cambie el segundo registro. $$ |x\rangle|x\rangle \rightarrow |x\rangle|x \oplus b\rangle~\mbox{if}~x_j = 0~\mbox{para el menor índice j} $$- **(Creación de permutaciones aleatorias)** Permuta y voltea aleatoriamente los qubits del segundo registro. $$ |x\rangle|y\rangle \rightarrow |x\rangle|f_b(y)\rangle $$  5. Problemas1. Implemente un oráculo general de Simon usando Qiskit.2. Pruebe su oráculo general Simon con la cadena de bits secreta $b=1001$, en un simulador y dispositivo. ¿Los resultados son los que esperas? Explicar por qué.  6. Referencias1. <NAME> (1997) "Sobre el poder de la computación cuántica" SIAM Journal on Computing, 26(5), 1474–1483, [doi:10.1137/S0097539796298637](https://doi.org/10.1137/S0097539796298637)2. <NAME> y <NAME>. Separación óptima en complejidades de consultas exactas para el problema de Simon. Revista de Ciencias de la Computación y Sistemas 97: 83-93, 2018, [https://doi.org/10.1016/j.jcss.2018.05.001](https://doi.org/10.1016/j.jcss.2018.05.001)<jupyter_code>import qiskit.tools.jupyter
%qiskit_version_table<jupyter_output>/usr/local/anaconda3/envs/terra-unstable/lib/python3.9/site-packages/qiskit/aqua/__init__.py:86: DeprecationWarning: The package qiskit.aqua is deprecated. It was moved/refactored to qiskit-terra For more information see <https://github.com/Qiskit/qiskit-aqua/blob/main/README.md#migration-guide>
  warn_package('aqua', 'qiskit-terra')
{'fraction_non_alphanumeric': 0.118570686370721, 'fraction_numerical': 0.036483288114068, 'mean_word_length': 4.087812041116006, 'pattern_counts': {'":': 0, '<': 30, '<?xml version=': 0, '>': 31, 'https://': 5, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '7', 'dir': 'jupyter-structured-clean-dedup', 'id': '356250', 'license': 'Apache-2.0', 'n_tokens_mistral': 6699, 'n_tokens_neox': 6110, 'n_words': 2386, 'path': 'es/notebooks/ch-algorithms/simon.ipynb', 'repo_name': 'TanyaJazzTeam/platypus', 'size': '17341'}