Minimum number of oracle call to solve Simon problem by a (NDTM) non-deterministic Turing machine?

Question

Simon's problem is a computational problem used to demonstrate an oracle separation between BQP and BPP classes.

• It is known that the minimum number of oracle calls to be made by the BQP machine is $\Omega(n)$.

• For the BPP machine, the lower bound of the oracle call is $\Omega(2^{n/2})$.

My query: I am trying to find a lower bound on the number of Oracle calls to be made by an NP machine to solve Simon's problem.

My attempt: I estimate two calls to the Oracle are sufficient for the NDTM machine to solve the problem.

Step I: NDTM guess the string $s\in \{0,1\}^n$.

Step II: NDTM calls the oracle at any $x\in_{R} \{0,1\}^n$ and note down the oracle output $f(x)$.

Step III: Again, NDTM calls the oracle at $x+s$ and notes down the oracle output $f(x+s)$. Then it checks if indeed $f(x)=f(x+s)$. If yes, then declare string $s$ as the answer.

• Is the above argument correct?

• Can the minimum number of Oracle queries be reduced to one?

Answer 1

No, your argument is not correct. A possible value of $s$ is $0^n$ (indeed, the decision version of Simon's problem is to distinguish $s=0^n$ from $s\ne0^n$, hence thus value is important).

Thus, your algorithm must be ready to guess $0^n$ as a potential value of $s$. But as you can see, whenever the algorithm guesses $0^n$, it will always accept and output this value as $f(x)=f(x\oplus0^n)$ no matter what, even if the actual value of $s$ is different!

In order to positively verify the $s=0^n$ case, an NP machine has to certify that the function is one-to-one rather than two-to-one. It needs an exponential number of queries to do that.

More precisely, any nondeterministic machine solving the problem, or even just its decision version (with $s=0^n$ being the YES instances, and $s\ne0^n$ the NO instances), must make at least $2^{(n+1)/2}$ oracle queries. This can be proved by a simple adversary argument:

First, set the oracle to the identity function $f(x)=x$. Then the NP machine much accept and output $s=0^n$ on some computation path $P$.

Let $X\subseteq\{0,1\}^n$ be the set of oracle calls made on $P$, and assume for contradiction that $|X|<2^{(n+1)/2}$. Since there are $\le\binom{|X|}2+1\le|X|^2/2<2^n$ elements in the set $\{x\oplus y:x,y\in X\}$, we can choose $s\in\{0,1\}^n\smallsetminus X$. We define a new oracle $g$ as follows: for each pair of elements $\{x,x\oplus s\}$, we define $f(x)=f(x\oplus s)\in\{x,x\oplus s\}$ in some way, making sure that $f(x)=x$ for $x\in X$. (We can do that because by the choice of $s$, it cannot happen that both $x$ and $x\oplus s$ belong to $X$.)

Then if we run the machine with oracle $g$, $P$ is still an accepting path that outputs “$s=0^n$”, as $g\supseteq f\restriction X$; but this value is different from the actual $s$.

On the other hand, it is possible to solve the problem even deterministically using $O(2^{n/2})$ oracle queries (and overall running time $2^{n/2}n^{O(1)}$). The algorithm is as follows:

• Query $f(x)$ for all $x$ in the sets $X=\{0,1\}^{\lfloor n/2\rfloor}\times\{0\}^{\lceil n/2\rceil}$ and $Y=\{0\}^{\lfloor n/2\rfloor}\times\{0,1\}^{\lceil n/2\rceil}$.

• If $f(x)=f(y)$ for some $x\in X$ and $y\in Y$ other than $x=y=0^n$, then output $s=x\oplus y\ne0^n$.

• Otherwise, output $s=0^n$.