Quantum Computing Stack Exchange is a question and answer site for engineers, scientists, programmers, and computing professionals interested in quantum computing. It only takes a minute to sign up.
Sign up to join this community
Simon's problem is that you are given a function $f : \{0,1\}^n \to \{0,1\}^n$ such that $f(x)=f(y)$ if and only if $x \bigoplus y$ is either $0^n$ or some unknown $s$. The problem is to find $s$. If $s=0^n$, then $f$ is 1 to 1 otherwise 2 to 1.
What is the classical complexity for Simon's problem?
Wikipedia says $\sqrt {2^n}$ but without any proof. Is there any site or book where I can find the proof for this?
To determine the classical complexity of a problem you need two things, of course: an upper bound (generally an algorithm) and a lower bound.
There is an easy randomized algorithm that works with high probability given $O(2^{n/2})$ queries to the function $f$: for a suitable constant $c>0$, generate $k = c 2^{n/2}$ strings $x_1,\ldots,x_k\in\{0,1\}^n$ uniformly at random, compute $f(x_j)$ for each $j\in\{1,\ldots,k\}$, and check to see if there is a collision. If you find distinct strings $x$ and $y$ with $f(x) = f(y)$, then answer $s = x \oplus y$ (which is guaranteed to be correct). Otherwise answer $s = 0^n$ (which might be wrong if you were unlucky). The probability that this succeeds depends on the choice of $c$, but for any desired constant probability of error $\varepsilon$ there is a constant $c$ that yields success probability $1-\varepsilon$. The analysis is essentially that of the generalized birthday problem, and it can be found in numerous books and lecture notes.
There is, in fact, a classical deterministic algorithm that succeeds with certainty and requires $O(2^{n/2})$ queries to $f$. The idea is to choose the strings $x_1,\ldots,x_k$ in advance so that $$ \{x_i\oplus x_j \,:\, i,j\in\{1,\ldots,k\}\} = \{0,1\}^n, $$ so a collision will be guaranteed if there is one. This paper describes one way to do this:
Guangya Cai and Daowen Qiu. Optimal separation in exact query complexities for Simon's problem. Journal of Computer and System Sciences 97: 83-93, 2018.
The lower bound is more difficult, as lower bounds generally are, if you want a formal analysis. Simon's original paper proved that any probabilistic algorithm making $2^{n/4}$ queries to $f$ can determine whether or not $s=0^n$ with probability at most $1/2 + 2^{-n/2}$, assuming that $f$ is chosen randomly from a certain distribution that gives $s=0^n$ with probability $1/2$. In other words, a probabilistic algorithm making $2^{n/4}$ queries gives only an exponentially small advantage over random guessing. You can find a proof of the stronger claim that $\Omega(2^{n/2})$ queries are required for a classical algorithm to solve Simon's problem with probability at least 3/4 in these lecture notes:
Richard Cleve. Classical lower bound for Simon's problem. Lecture Notes, 2011.
Sources on quantum computing tend to give a classical complexity of $\sqrt{2^n}$ but not the proof. I believe the sources on classical cryptography call this algorithm birthday attack and use it to find collisions of hash functions (which is effectively what the Simon's algorithm does). You should be able to find the math details looking for it in crypto context - Crypto StackExchange even has a dedicated tag for birthday attack.
Here's a partial explanation.
Start by thinking about the 2 bit case. We first evaluate $f(00)$, and we learn nothing. Then, we evaluate (say) $f(01)$. Now we can compare the values, and see if $s=01$, or not. Next we calculate a new value, say $f(10)$. By comparing to $f(00)$, we can determine if $s=10$ but, also, by comparing to $f(01)$, we simultaneously check if $s=11$.
Now, there are $2^n-1$ possible values of $s$ (I'm ignoring the $s=000...0$ case). If we were cunning, by selecting the right $k$ values of $x\in\{0,1\}^n$ values, then so long as $\binom{k}{2}\geq 2^n-1$, this could be possible as you could have checked $\binom{k}{2}$ different values of $s$. This is achieved by $k\sim 2^{n/2}$. Now, there still remains a careful argument about what those $k$ values are that you need to select, which I'm not presenting here. It's probably worthwhile trying a few small cases (as I did for $n=2$ above) to gain some understanding.
