Ex7 5
$\def\abs#1{|#1|}\def\i{\mathbf {i}}\def\ket#1{|{#1}\rangle}\def\bra#1{\langle{#1}|}\def\braket#1#2{\langle{#1}|{#2}\rangle}\def\tr{\mathord{\mbox{tr}}}\mathbf{Exercise\ 7.5}$
Show that a classical solution to Simon's problem requires $O(2^{n/2})$ calls to the black box, and describe such a classical algorithm.
page revision: 0, last edited: 18 Nov 2012 19:31
A call to $f$ does not reveal much about the hidden $n$-bit string $a$. But if we find a pair $x,y$ such that $f(x) = f(y)$, then we know that $x = y \oplus a$ by the property of $f$ and we can retrieve $a$ by
(1)So Simon's problem is about finding a collision for the 2-1 function $f$.
There are $2^n$ different input values to $f$ and they split into $\frac12 2^n = 2^{n-1}$ pairs that will produce $a$. If we do $t$ queries to $f$ without finding a collision, then we can form $\binom{t}{2}$ pairs that did not collide and hence did not produce $a$. Since
(2)this can at most rule out $t^2$ values of the $2^n$ possible values for $a$ (possibly much less). Hence, to have $t^2 > 2^n$, we need at least
(3)On the other hand, given $t-1$ queries without collision, then the likelihood that a collision is found in query number $t$ is
(4)since we can form $\binom{t}2$ pairs among the $t$ queries and there are $2^n - (t-1)$ values to choose from in query $t$. But if $t = 2^{n/2}$ we have
(5)that is, the chance for collision is fair. This gives a complexity of $O(2^{n/2})$ for finding a collision.
A more exact calculation of the probability of finding a collision after $t$ queries can be done by the formula for the "Birthday Paradox". First compute the probability $P'$ that no collision is found in $t$ queries, then compute the probability $P = 1 - P'$ that at least one collision is found.
(6)After the first query there are $2^n - 1$ values to chose from, but only $2^n - 2$ values avoiding collision. After second query: $2^n - 2$ values to chose from, but only $2^n - 4$ values avoiding collision, and so on. Therefore
Then find $t$ such that $P = 1 - P' > \frac12$, but this is hard to evaluate.