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 that takes an -bit input and returns an -bit output. We are promised that there exists an such that for all and :
In other words, regardless of what does behind the scenes, its output is the same for inputs and if and only if , or, equivalently, .
The goal is to find the -bit number , using as few calls to as possible. There are two cases: if , then is one-to-one, since . Otherwise, if , then is two-to-one by definition: for every there exists exactly one such that .
A classical computer solves this by randomly guessing inputs, until it finds two that give the same output, and then . For -bit numbers, this takes guesses (the square root is due to the birthday paradox).
A quantum computer needs to query only times, although the exact number varies due to the algorithm’s probabilistic nature. It uses the following circuit:
The XOR oracle implements , and has the following action for -bit and :
Starting from the state , we apply the Hadamard gate to each of the first qubits:
Where is shorthand for . In other words, we now have an equal superposition of all possible inputs , with a constant beside it. We give this to the oracle :
Then we apply to the first qubits again, which, thanks to the definition of the Hadamard transform, yields the following, where is the bitwise dot product:
Next, we measure all qubits. The order in which we do this does not matter, but, for clarity, let us measure the last qubits first, yielding for some . Doing this leaves the qubits in the following state, where and :
If , we get an equiprobable superposition of all . So, when we measure the first qubits, the result is a uniformly random number, regardless of the phase .
If , the situation is more interesting, because we can only measure -values where:
Since by definition, we can rewrite this as follows:
Clearly, the expression can only be nonzero if is even. In other words, when we measure the first qubits, we get a random -value, for which is guaranteed to be even.
In both cases and , we measure a -value that satisfies the equation:
This tells us something about , albeit not much. But if we run Simon’s algorithm times, we get various -values , from which we can build a system of linear equations:
This can be solved efficiently by a classical computer. In the best-case scenario, all those -values would be linearly independent (when regarded as vectors of bits), in which case only equations would be necessary. Simon’s algorithm is therefore .
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.
- J.S. Neergaard-Nielsen, Quantum information: lectures notes, 2021, unpublished.
- S. Aaronson, Introduction to quantum information science: lecture notes, 2018, unpublished.