<jupyter_start><jupyter_text>Simon's Algorithm Problem statement:Given: a function $f$ acting on bit strings $f:\{0,1\}^n \rightarrow \{0,1\}^n$ and a promise that $f(x)=f(x \oplus s)$ for all $x$ (addition mod 2). The goal is to use Simon's algorithm to find the unknown string $s$.  Example:For example, if $n = 3$, then the following function is an example of a function that satisfies the required and just mentioned property:|$x$|   $$f(x)$$||---|------||000|	101||001|	010||010|	000||011|	110||100|	000||101|	110||110|	101||111|	010| Given $f$ is a two-to-one function i.e. it maps exactly two inputs to every unique output, and we find 2 values of input $x$ that have the same output, $f(x_1)=f(x_2)$ then it is guaranteed that $x_1 \oplus x_2 = s$For example, the input strings $011$ and $101$ are both mapped by $f$ to the same output string $110$. If we XOR $011$ and $101$ we obtain $s$, that is:$$011 \oplus 101 = 110$$so for this example $s = 110$  Problem hardnessTo solve this classically, you need to find two different inputs $x$ and $y$ for which $f(x)=f(y)$. Given $f$ is a blackbox, we can discover something about $f$ (or what it does) only when, for two different inputs, we obtain the same output. In any case, we would need to guess $ \Omega ({\sqrt {2^{n}}})$ different inputs before being likely to find a pair on which $f$ takes the same output.  Simon's AlgorithmThe high-level idea behind Simon's algorithm is to "probe" a quantum circuit "enough times" to find $n-1$ (linearly independent) n-bit strings, that is$$ y_{1},y_{2},\dots ,y_{n-1}\in \{0,1\}^{n} $$such that the following equations are satisfied$$ \begin{aligned}y_{1}\cdot s&=0\\y_{2}\cdot s&=0\\&\,\,\,\vdots \\y_{n-1}\cdot s&=0\end{aligned}$$ where $ y_{i}\cdot s$ is the modulo-2 dot product; that is, $ y_{i}\cdot s=y_{i1}s_{1}\oplus y_{i2}s_{2}\oplus \dots \oplus y_{in}s_{n} $So, this linear system contains $n-1$ linear equations in $n$ unknowns (i.e. the bits of $s$, and the goal is to solve it to obtain $s$, and $s$ is fixed for a given function $f$. Simon's quantum circuitThe quantum circuit below is the implementation (and visualization) of the quantum part of Simon's algorithm.The circuit acts on $2n$ qubits (where $n$ is the length of the bit string in question (i.e., $n=3$ for our example). Apply a Hadamard gate to the first $n$ qubits, then apply $U_f$ - which is an oracle (or "black box"), which knows how to compute $f$ , then apply a Hadamard gate to the first $n$ qubits.For more details on Simon's algorithm refer to [Wikipedia]()  IMPORTS and SETUP<jupyter_code>from braket.circuits import Circuit
from braket.devices import LocalSimulator
import numpy as np
import time
import matplotlib.pyplot as plt
%matplotlib inline

# Sets the device to run the circuit on
device = LocalSimulator()<jupyter_output><empty_output><jupyter_text>Circuit Definition1. We start by applying Hadamard gates to the first $n$-qubits. 2. We apply the oracle/black box ($U_f$ gate) to map to $f(x)$. Here we build it dynamically based on our chosen value of $s$. (You can experiment by setting $s$ to other values and different lengths).3. We apply Hadamard Gate to the first $n$-qubits.<jupyter_code>s = '110'
n = len(str(s))

circ = Circuit()

## Apply Hadamard gates to first n qubits before querying the oracle 
circ.h(range(n)) 

# Generic Oracle to implement function f(x) with chosen value of s. 
# Apply cnot only for bits of s that are 1
for i in range(n):
    if int(s[i]) == 1:
        for j in range(n):
            circ.cnot(i, n + j)


# Apply Hadamard gates to the first n qbits
circ.h(range(n)) 


print(circ)<jupyter_output><empty_output><jupyter_text>Now run the circuit<jupyter_code>task = device.run(circ, shots=2*n-1)<jupyter_output><empty_output><jupyter_text>Analyze the resultsThe measurements are performed on all $2n$ qubits. We are only interested in the first $n$ qubits. So we count the unique results of first $n$ qubits and plott the results<jupyter_code>result = task.result()
print(f"measurement_counts: {result.measurement_counts}\n")


# Simulate partial measurement by seperating out first n bits
answer_plot = {}
for measresult in result.measurement_counts.keys():
    measresult_input = measresult[:len(str(s))]
    if measresult_input in answer_plot:
        answer_plot[measresult_input] += result.measurement_counts[measresult]
    else:
        answer_plot[measresult_input] = result.measurement_counts[measresult] 

print(f"measurement_of_input_registers: {answer_plot}\n")
plt.bar(answer_plot.keys(), answer_plot.values())
plt.show()<jupyter_output><empty_output><jupyter_text>Using these results, we can recover the value of $s$<jupyter_code>y1,y2 = answer_plot.keys()

s_calc = int(y1)^int(y2)
    
print(f"Bitwise XOR / Dot product of the 2 results y1 and y2 retrieves our unknown string 's' --> {s_calc}\n")<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.11995905834186285, 'fraction_numerical': 0.0255885363357216, 'mean_word_length': 4.681395348837209, 'pattern_counts': {'":': 0, '<': 21, '<?xml version=': 0, '>': 22, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '5', 'dir': 'jupyter-structured-clean-dedup', 'id': '558630', 'license': 'Apache-2.0', 'n_tokens_mistral': 1679, 'n_tokens_neox': 1562, 'n_words': 639, 'path': '.ipynb_checkpoints/05-Simons_Algorithm-LocalSimulator-checkpoint.ipynb', 'repo_name': 'jag-p/braket-sample-notebooks', 'size': '4885'}