Simon's Algorithm

Simon's Algorithm, proposed by Daniel Simon in 1994, was the first quantum algorithm to show an exponential speedup over any possible classical algorithm (including probabilistic ones) for a decision problem. It addresses the 'hidden period' or 'hidden subgroup' problem, which serves as the direct mathematical precursor to Shor's factoring algorithm.

Imagine a function that maps inputs to outputs such that it is 'two-to-one', meaning every output has exactly two inputs that map to it. Furthermore, these two inputs always differ by a secret binary shift $s$ (i.e., $f(x) = f(y)$ if and only if $x \oplus y = s$). Classically, to find this secret shift $s$, you have to search for a collision, two different inputs that yield the same output. By the Birthday Paradox, you would need to query about $\sqrt{2^n}$ inputs before finding a match. Simon's algorithm does not search for collisions directly. Instead, it prepares a quantum superposition, queries the oracle once, and measures a state that is guaranteed to be perpendicular to the secret shift ($y \cdot s = 0$). By repeating this process about $n$ times, we get a system of linear equations that we can easily solve classically to find $s$.

Let $f: \{0,1\}^n \to \{0,1\}^n$ be a function. We are promised that there exists a hidden bitstring $s \in \{0,1\}^n$ such that for all $x, y \in \{0,1\}^n$:

$$f(x) = f(y) \iff x \oplus y \in \{0, s\}$$

If $s = 0^n$, the function is one-to-one. If $s \neq 0^n$, the function is two-to-one.

Classical Complexity: To find $s$ with high probability, any classical algorithm (even probabilistic) must query the oracle $\Omega(2^{n/2})$ times, due to the birthday bound.

Quantum Complexity: Simon's algorithm finds $s$ using $O(n)$ quantum queries and $O(n^3)$ classical post-processing steps, representing an exponential speedup.

Circuit Construction: Unlike previous algorithms, Simon's algorithm uses an $n$-qubit target register to store the $n$-bit output of $f(x)$. 1. Initialize: Two registers of $n$ qubits, $|0\rangle^{\otimes n} |0\rangle^{\otimes n}$. 2. Superposition: Apply $H^{\otimes n}$ to the first register: $$|\psi_1\rangle = \left( \frac{1}{\sqrt{2^n}} \sum_{x \in \{0,1\}^n} |x\rangle \right) |0\rangle^{\otimes n}$$ 3. Oracle Query: Apply the unitary oracle $U_f |x\rangle|0\rangle = |x\rangle|f(x)\rangle$: $$|\psi_2\rangle = \frac{1}{\sqrt{2^n}} \sum_{x \in \{0,1\}^n} |x\rangle |f(x)\rangle$$ 4. Measurement of Second Register: We measure the second register. Suppose we obtain a specific output value $f(x_0)$. Due to the two-to-one property, the first register collapses to a superposition of the only two inputs that map to $f(x_0)$: $$|\psi_3\rangle = \frac{1}{\sqrt{2}} (|x_0\rangle + |x_0 \oplus s\rangle)$$ 5. Interference: Apply $H^{\otimes n}$ to the first register: $$|\psi_4\rangle = \frac{1}{\sqrt{2^{n+1}}} \sum_{y \in \{0,1\}^n} \left( (-1)^{x_0 \cdot y} + (-1)^{(x_0 \oplus s) \cdot y} \right) |y\rangle$$ Since $(x_0 \oplus s) \cdot y = (x_0 \cdot y) \oplus (s \cdot y)$, we can factor this as: $$|\psi_4\rangle = \frac{1}{\sqrt{2^{n+1}}} \sum_{y \in \{0,1\}^n} (-1)^{x_0 \cdot y} \left( 1 + (-1)^{s \cdot y} \right) |y\rangle$$

• If $s \cdot y = 1 \pmod 2$, then $1 + (-1)^1 = 0$. The amplitude of $|y\rangle$ is 0.
• If $s \cdot y = 0 \pmod 2$, then $1 + (-1)^0 = 2$. The amplitude of $|y\rangle$ is non-zero.