Categories: Algorithms, Quantum information.

# Simon’s algorithm

Simon’s algorithm was the first proof that quantum computers are able to solve some problems exponentially faster than classical computers. In the same spirit as the Deutsch-Jozsa algorithm and the Bernstein-Vazirani algorithm, the problem it solves, known as Simon’s problem, is of no practical use, but nevertheless Simon’s algorithm is an important landmark.

Simon’s problem is this: we are given a “black box” function $f(x)$ that takes an $n$-bit input $x$ and returns an $n$-bit output. We are promised that there exists an $s$ such that for all $x_1$ and $x_2$:

\begin{aligned} f(x_1) = f(x_2) \quad \Leftrightarrow \quad x_2 = s \oplus x_1 \end{aligned}

In other words, regardless of what $f(x)$ does behind the scenes, its output is the same for inputs $x_1$ and $x_2$ if and only if $x_2 = s \oplus x_1$, or, equivalently, $x_1 = s \oplus x_2$.

The goal is to find the $n$-bit number $s$, using as few calls to $f$ as possible. There are two cases: if $s = 0$, then $f$ is one-to-one, since $x_2 = 0 \oplus x_1 = x_1$. Otherwise, if $s \neq 0$, then $f$ is two-to-one by definition: for every $x_1$ there exists exactly one $x_2$ such that $x_2 = s \oplus x_1$.

A classical computer solves this by randomly guessing inputs, until it finds two that give the same output, and then $s = x_1 \oplus x_2$. For $n$-bit numbers, this takes $\mathcal{O}(\sqrt{2^n})$ guesses (the square root is due to the birthday paradox).

A quantum computer needs to query $f$ only $\mathcal{O}(n)$ times, although the exact number varies due to the algorithm’s probabilistic nature. It uses the following circuit:

The XOR oracle $U_f$ implements $f$, and has the following action for $n$-bit $a$ and $b$:

\begin{aligned} \Ket{a} \Ket{b} \quad \to \boxed{U_f} \to \quad \Ket{a} \Ket{b \oplus f(a)} \end{aligned}

Starting from the state $\Ket{0}^{\otimes 2 n}$, we apply the Hadamard gate $H$ to each of the first $n$ qubits:

\begin{aligned} \Ket{0}^{\otimes n} \Ket{0}^{\otimes n} \quad \to \boxed{H^{\otimes n}} \to \quad \Ket{+}^{\otimes n} \Ket{0}^{\otimes n} = \frac{1}{\sqrt{2^n}} \sum_{x = 0}^{2^n - 1} \Ket{x} \Ket{0}^{\otimes n} \end{aligned}

Where $\Ket{x}$ is shorthand for $\Ket{x}_1 \cdots \Ket{x}_n$. In other words, we now have an equal superposition of all possible inputs $x$, with a constant $\Ket{0}^{\otimes n}$ beside it. We give this to the oracle $U_f$:

\begin{aligned} \frac{1}{\sqrt{2^n}} \sum_{x = 0}^{2^n - 1} \Ket{x} \Ket{0}^{\otimes n} \quad \to \boxed{U_f} \to \quad \frac{1}{\sqrt{2^n}} \sum_{x = 0}^{2^n - 1} \Ket{x} \Ket{f(x)} \end{aligned}

Then we apply $H^{\otimes n}$ to the first $n$ qubits again, which, thanks to the definition of the Hadamard transform, yields the following, where $x \cdot y$ is the bitwise dot product:

\begin{aligned} \frac{1}{\sqrt{2^n}} \sum_{x = 0}^{2^n - 1} \Ket{x} \Ket{f(x)} \quad \to \boxed{H^{\otimes n}} \to \quad &\frac{1}{2^n} \sum_{x = 0}^{2^n - 1} \bigg( \sum_{y = 0}^{2^n - 1} (-1)^{x \cdot y} \Ket{y} \bigg) \Ket{f(x)} \end{aligned}

Next, we measure all qubits. The order in which we do this does not matter, but, for clarity, let us measure the last $n$ qubits first, yielding $\Ket{f(x_1)}$ for some $x_1$. Doing this leaves the $2n$ qubits in the following state, where $f(x_1) = f(x_2)$ and $x_2 = s \oplus x_1$:

\begin{alignedat}{2} &\mathrm{if} \: s = 0: \qquad &&\frac{1}{\sqrt{2^{n}}} \sum_{y = 0}^{2^n - 1} (-1)^{x_1 \cdot y} \Ket{y} \Ket{f(x_1)} \\ &\mathrm{if} \: s \neq 0: \qquad &&\frac{1}{\sqrt{2^{n+1}}} \sum_{y = 0}^{2^n - 1} \Big( (-1)^{x_1 \cdot y} + (-1)^{x_2 \cdot y} \Big) \Ket{y} \Ket{f(x_1)} \end{alignedat}

If $s = 0$, we get an equiprobable superposition of all $y$. So, when we measure the first $n$ qubits, the result is a uniformly random number, regardless of the phase $(-1)^{x_1 \cdot y}$.

If $s \neq 0$, the situation is more interesting, because we can only measure $y$-values where:

\begin{aligned} (-1)^{x_1 \cdot y} + (-1)^{x_2 \cdot y} \neq 0 \end{aligned}

Since $x_2 = s \oplus x_1$ by definition, we can rewrite this as follows:

\begin{aligned} (-1)^{x_1 \cdot y} + (-1)^{x_1 \cdot y \oplus s \cdot y} = (-1)^{x_1 \cdot y} + (-1)^{x_1 \cdot y} (-1)^{s \cdot y} \neq 0 \end{aligned}

Clearly, the expression can only be nonzero if $s \cdot y$ is even. In other words, when we measure the first $n$ qubits, we get a random $y$-value, for which $s \cdot y$ is guaranteed to be even.

In both cases $s = 0$ and $s \neq 0$, we measure a $y$-value that satisfies the equation:

\begin{aligned} s \cdot y = 0 \:\:(\bmod 2) \end{aligned}

This tells us something about $s$, albeit not much. But if we run Simon’s algorithm $N$ times, we get various $y$-values $y_1, ..., y_N$, from which we can build a system of linear equations:

\begin{aligned} s \cdot y_1 &= 0 \:\:(\bmod 2) \\ s \cdot y_2 &= 0 \:\:(\bmod 2) \\ &\:\:\vdots \\ s \cdot y_N &= 0 \:\:(\bmod 2) \end{aligned}

This can be solved efficiently by a classical computer. In the best-case scenario, all those $y$-values would be linearly independent (when regarded as vectors of bits), in which case only $N = n - 1$ equations would be necessary. Simon’s algorithm is therefore $\mathcal{O}(n)$.

It may feel like “cheating” to use a classical computer at the end. Remember that the point of this algorithm is to limit the number of oracle queries, which we did successfully. Querying an oracle might be a very expensive operation, so that is a big improvement! That said, Simon’s algorithm currently has no known practical uses.

1. J.S. Neergaard-Nielsen, Quantum information: lectures notes, 2021, unpublished.
2. S. Aaronson, Introduction to quantum information science: lecture notes, 2018, unpublished.