7
$\begingroup$

Simon's problem is the following: Given oracle access to a Boolean function $f: \{0,1\}^n\rightarrow \{0,1\}^n$, and promised that precisely one of the following two cases is true, decide which of these is the case:

  1. $f$ is injective
  2. There exists a non-zero bitstring $s\in \{0,1\}^n$ such that $f(x) = f(y) \Leftrightarrow x=y \oplus s$.

Simon's algorithm can solve this problem using exponentially fewer queries than any classical randomized algorithm. According to Wikipedia this problem "yields an oracle separation between the complexity classes BPP and BQP."

I would like to understand why this implication holds. In particular I would be most interested in a complete, pedagogical proof of this statement. Thank you for your help.

$\endgroup$
4
  • $\begingroup$ @D.W. I'd like to understand why there is an oracle $O \subset \{0,1\}^*$ and a language $L\subset \{0,1\}^*$ such that there is an oracle-Turing machine $M_1$ in $BQP^O$ that recognizes $L$, but there no oracle-TM in $BPP^O$ that does. $\endgroup$
    – gen
    Nov 29, 2022 at 17:48
  • $\begingroup$ Thanks for the response! That sounds like a good start. Please don't add information in the comments. Instead, edit your question to expand on it and improve it. Make sure it reads well for someone who encounters it for the first time (don't use "EDIT:"). $\endgroup$
    – D.W.
    Nov 29, 2022 at 18:57
  • $\begingroup$ Do you have any guesses on how you might instantiate that oracle $O$? What are the natural choices, given the definition of Simon's problem? Do you have any guesses on how you might define $L$? Are there any natural candidates, given the definition of Simon's problem? $\endgroup$
    – D.W.
    Nov 29, 2022 at 18:57
  • $\begingroup$ I'm not sure, @D.W. Can you describe what $L$ or $O$ should be and maybe I can fill in the gaps? I'm not familiar with relativized separations. $\endgroup$
    – gen
    Nov 30, 2022 at 4:18

1 Answer 1

11
+50
$\begingroup$

Let $\mathscr{F}$ be the collection of all functions $F:\{0,1\}^*\rightarrow\{0,1\}^*$, such that for every $n$, the restriction $F_n:=F|_{\{0,1\}^n}$ (restriction of $F$ on $\{0,1\}^n$) satisfies the promise of Simon's problem. For each $F\in\mathscr{F}$, let $L(F)\subseteq\{0\}^*$ be the unary language $$L(F)=\{0^n\mid F_n\textrm{ is injective}\}.$$ We have:

  • For every $F\in\mathscr{F}$, $L(F)\in\mathsf{BQP}^F$. This is because to decide if $x\in L(F)$, we can first check if $x=0^n$ for some $n$, and if so, we apply Simon's algorithm to decide if $F_n$ is injective, with bounded error (Since the $\mathsf{BQP}$ machine has oracle access to $F$, it just creates the uniform superposition over $\{0,1\}^n$ to make queries to $F_n$).
  • There exists $F\in\mathscr{F}$ such that $L(F)\notin\mathsf{BPP}^F$. At a high level, this is proved by diagonalization, due to the fact that $\mathscr{F}$ is uncountable while the set of $\mathsf{BPP}$ oracle machines is countable. In detail, the proof goes as follows.

We enumerate polynomial-time probablistic oracle Turing machines as $$\mathcal{M}_1,\mathcal{M}_2,\ldots,\mathcal{M}_i,\ldots$$ and construct our $F$ while enumerating them. Starting from $\mathcal{M}_1$, and suppose it has time bound $p_1(n)=\mathrm{poly}(n)$. That means on input $0^n$, it only makes oracle queries on strings of length at most $p_1(n)$. We claim the following (because of the classical query lower bound on Simon's problem):

There exist $n\in\mathbb{N}$, and $F_1,\ldots,F_{p_1(n)}$, such that $\mathcal{M}_1$ does NOT give the correct answer on $0^n$ (That is, it rejects with probability at least $1/3$ in case that $F_n$ is injective, and vice versa).

Generally, if at $\mathcal{M}_i$ (with time bound $p_i(n)$) we already fixed $F_1,\ldots,F_N$, then

There exist $n>N$, and $F_{N+1},\ldots,F_{p_i(n)}$, such that $\mathcal{M}_i$ does NOT give the correct answer on $0^n$.

This is because if not, we can always hardwire $F_1,\ldots,F_N$, and brute force every function on at most $N$ bits, to get a classical query algorithm for Simon's problem with $p_i(n)+O(1)$ queries, which violates the $2^{\Omega(n)}$ classical query lower bound.

In the end, we obatin a function $F\in\mathscr{F}$ such that every $\mathcal{M}_i$, when calling the oracle $F$, is at some point incorrect in deciding $L(F)$. Therefore $L(F)\notin\mathsf{BPP}^F$, and $F$ is an oracle such that $\mathsf{BQP}^F\neq \mathsf{BPP}^F$.

Finally, it is easy to convert $F$ into a function $O$ with one-bit output if you insist on $O$ being a language. Just let $O(x,i)=F(x)_i$, and any oracle machine calling $F$ can be modified into one calling $O$ and vice versa, with polynomial overhead. Therefore we also have $\mathsf{BQP}^O\neq \mathsf{BPP}^O$.


I believe the above argument is pretty standard for proving oracle separations, which is why it was often omitted. If you are interested, you can also read the oracle separation between $\mathsf{BQP}$ and $\mathsf{PH}$ by Raz and Tal, where at the end of the proof they used the same argument, in a probabilistic fashion.

$\endgroup$
1
  • $\begingroup$ Thank you for taking the time to post this answer. $\endgroup$
    – gen
    Dec 3, 2022 at 17:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.