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)f(x) that takes an nn-bit input xx and returns an nn-bit output. We are promised that there exists an ss such that for all x1x_1 and x2x_2:

f(x1)=f(x2)x2=sx1\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)f(x) does behind the scenes, its output is the same for inputs x1x_1 and x2x_2 if and only if x2=sx1x_2 = s \oplus x_1, or, equivalently, x1=sx2x_1 = s \oplus x_2.

The goal is to find the nn-bit number ss, using as few calls to ff as possible. There are two cases: if s=0s = 0, then ff is one-to-one, since x2=0x1=x1x_2 = 0 \oplus x_1 = x_1. Otherwise, if s0s \neq 0, then ff is two-to-one by definition: for every x1x_1 there exists exactly one x2x_2 such that x2=sx1x_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=x1x2s = x_1 \oplus x_2. For nn-bit numbers, this takes O(2n)\mathcal{O}(\sqrt{2^n}) guesses (the square root is due to the birthday paradox).

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

Simon's circuit

The XOR oracle UfU_f implements ff, and has the following action for nn-bit aa and bb:

abUfabf(a)\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 02n\Ket{0}^{\otimes 2 n}, we apply the Hadamard gate HH to each of the first nn qubits:

0n0nHn+n0n=12nx=02n1x0n\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 x\Ket{x} is shorthand for x1xn\Ket{x}_1 \cdots \Ket{x}_n. In other words, we now have an equal superposition of all possible inputs xx, with a constant 0n\Ket{0}^{\otimes n} beside it. We give this to the oracle UfU_f:

12nx=02n1x0nUf12nx=02n1xf(x)\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 HnH^{\otimes n} to the first nn qubits again, which, thanks to the definition of the Hadamard transform, yields the following, where xyx \cdot y is the bitwise dot product:

12nx=02n1xf(x)Hn12nx=02n1(y=02n1(1)xyy)f(x)\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 nn qubits first, yielding f(x1)\Ket{f(x_1)} for some x1x_1. Doing this leaves the 2n2n qubits in the following state, where f(x1)=f(x2)f(x_1) = f(x_2) and x2=sx1x_2 = s \oplus x_1:

ifs=0:12ny=02n1(1)x1yyf(x1)ifs0:12n+1y=02n1((1)x1y+(1)x2y)yf(x1)\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=0s = 0, we get an equiprobable superposition of all yy. So, when we measure the first nn qubits, the result is a uniformly random number, regardless of the phase (1)x1y(-1)^{x_1 \cdot y}.

If s0s \neq 0, the situation is more interesting, because we can only measure yy-values where:

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

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

(1)x1y+(1)x1ysy=(1)x1y+(1)x1y(1)sy0\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 sys \cdot y is even. In other words, when we measure the first nn qubits, we get a random yy-value, for which sys \cdot y is guaranteed to be even.

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

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

This tells us something about ss, albeit not much. But if we run Simon’s algorithm NN times, we get various yy-values y1,...,yNy_1, ..., y_N, from which we can build a system of linear equations:

sy1=0(mod2)sy2=0(mod2)syN=0(mod2)\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 yy-values would be linearly independent (when regarded as vectors of bits), in which case only N=n1N = n - 1 equations would be necessary. Simon’s algorithm is therefore O(n)\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.

References

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