<p>Let <span class="math-container">$\mathscr{F}$</span> be the collection of all functions <span class="math-container">$F:\{0,1\}^*\rightarrow\{0,1\}^*$</span>, such that for every <span class="math-container">$n$</span>, the restriction <span class="math-container">$F_n:=F|_{\{0,1\}^n}$</span> (restriction of <span class="math-container">$F$</span> on <span class="math-container">$\{0,1\}^n$</span>) satisfies the promise of Simon's problem. For each <span class="math-container">$F\in\mathscr{F}$</span>, let <span class="math-container">$L(F)\subseteq\{0\}^*$</span> be the unary language
<span class="math-container">$$L(F)=\{0^n\mid F_n\textrm{ is injective}\}.$$</span>
We have:</p>
<ul>
<li>For every <span class="math-container">$F\in\mathscr{F}$</span>, <span class="math-container">$L(F)\in\mathsf{BQP}^F$</span>. This is because to decide if <span class="math-container">$x\in L(F)$</span>, we can first check if <span class="math-container">$x=0^n$</span> for some <span class="math-container">$n$</span>, and if so, we apply Simon's algorithm to decide if <span class="math-container">$F_n$</span> is injective, with bounded error (Since the <span class="math-container">$\mathsf{BQP}$</span> machine has oracle access to <span class="math-container">$F$</span>, it just creates the uniform superposition over <span class="math-container">$\{0,1\}^n$</span> to make queries to <span class="math-container">$F_n$</span>).</li>
<li>There exists <span class="math-container">$F\in\mathscr{F}$</span> such that <span class="math-container">$L(F)\notin\mathsf{BPP}^F$</span>. At a high level, this is proved by diagonalization, due to the fact that <span class="math-container">$\mathscr{F}$</span> is uncountable while the set of <span class="math-container">$\mathsf{BPP}$</span> oracle machines is countable. In detail, the proof goes as follows.</li>
</ul>
<p>We enumerate polynomial-time probablistic oracle Turing machines as
<span class="math-container">$$\mathcal{M}_1,\mathcal{M}_2,\ldots,\mathcal{M}_i,\ldots$$</span>
and construct our <span class="math-container">$F$</span> while enumerating them. Starting from <span class="math-container">$\mathcal{M}_1$</span>, and suppose it has time bound <span class="math-container">$p_1(n)=\mathrm{poly}(n)$</span>. That means on input <span class="math-container">$0^n$</span>, it only makes oracle queries on strings of length at most <span class="math-container">$p_1(n)$</span>. We claim the following (because of the classical query lower bound on Simon's problem):</p>
<blockquote>
<p>There exist <span class="math-container">$n\in\mathbb{N}$</span>, and <span class="math-container">$F_1,\ldots,F_{p_1(n)}$</span>, such that <span class="math-container">$\mathcal{M}_1$</span> does NOT give the correct answer on <span class="math-container">$0^n$</span>
(That is, it rejects with probability at least <span class="math-container">$1/3$</span> in case that <span class="math-container">$F_n$</span> is injective, and vice versa).</p>
</blockquote>
<p>Generally, if at <span class="math-container">$\mathcal{M}_i$</span> (with time bound <span class="math-container">$p_i(n)$</span>) we already fixed <span class="math-container">$F_1,\ldots,F_N$</span>, then</p>
<blockquote>
<p>There exist <span class="math-container">$n&gt;N$</span>, and <span class="math-container">$F_{N+1},\ldots,F_{p_i(n)}$</span>, such that <span class="math-container">$\mathcal{M}_i$</span> does NOT give the correct answer on <span class="math-container">$0^n$</span>.</p>
</blockquote>
<p>This is because if not, we can always hardwire <span class="math-container">$F_1,\ldots,F_N$</span>, and brute force every function on at most <span class="math-container">$N$</span> bits, to get a classical query algorithm for Simon's problem with <span class="math-container">$p_i(n)+O(1)$</span> queries, which violates the <span class="math-container">$2^{\Omega(n)}$</span> classical query lower bound.</p>
<p>In the end, we obatin a function <span class="math-container">$F\in\mathscr{F}$</span> such that every <span class="math-container">$\mathcal{M}_i$</span>, when calling the oracle <span class="math-container">$F$</span>, is at some point incorrect in deciding <span class="math-container">$L(F)$</span>. Therefore <span class="math-container">$L(F)\notin\mathsf{BPP}^F$</span>, and <span class="math-container">$F$</span> is an oracle such that <span class="math-container">$\mathsf{BQP}^F\neq \mathsf{BPP}^F$</span>.</p>
<p>Finally, it is easy to convert <span class="math-container">$F$</span> into a function <span class="math-container">$O$</span> with one-bit output if you insist on <span class="math-container">$O$</span> being a language. Just let <span class="math-container">$O(x,i)=F(x)_i$</span>, and any oracle machine calling <span class="math-container">$F$</span> can be modified into one calling <span class="math-container">$O$</span> and vice versa, with polynomial overhead. Therefore we also have <span class="math-container">$\mathsf{BQP}^O\neq \mathsf{BPP}^O$</span>.</p>
<hr />
<p>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 <span class="math-container">$\mathsf{BQP}$</span> and <span class="math-container">$\mathsf{PH}$</span> by <a href="https://eccc.weizmann.ac.il/report/2018/107/" rel="noreferrer">Raz and Tal</a>, where at the end of the proof they used the same argument, in a probabilistic fashion.</p>

CC BY-SA 4.0
2022-12-03T17:48:20.253Z
Thank you for taking the time to post this answer.
gen
CC BY-SA 4.0
2022-12-03T08:54:09.040Z
2022-12-05T21:46:49.637Z
2022-12-05T21:46:49.637Z
Wei Zhan
<p>Simon's problem is the following: Given oracle access to a Boolean function <span class="math-container">$f: \{0,1\}^n\rightarrow \{0,1\}^n$</span>, and promised that precisely one of the following two cases is true, decide which of these is the case:</p>
<ol>
<li><span class="math-container">$f$</span> is injective</li>
<li>There exists a non-zero bitstring <span class="math-container">$s\in \{0,1\}^n$</span> such that <span class="math-container">$f(x) = f(y) \Leftrightarrow x=y \oplus s$</span>.</li>
</ol>
<p>Simon's algorithm can solve this problem using exponentially fewer queries than any classical randomized algorithm. According to <a href="https://en.wikipedia.org/wiki/Simon%27s_problem" rel="noreferrer">Wikipedia</a> this problem &quot;yields an oracle separation between the complexity classes BPP and BQP.&quot;</p>
<p>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.</p>

CC BY-SA 4.0
2022-11-29T17:48:21.243Z
@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.
gen
CC BY-SA 4.0
2022-11-29T18:57:20.003Z
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:").
D.W.
CC BY-SA 4.0
2022-11-29T18:57:22.110Z
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?
D.W.
CC BY-SA 4.0
2022-11-30T04:18:03.017Z
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.
gen
<cc.complexity-theory><quantum-computing><separation>
How do separations of query complexities imply complexity class separations relative to oracles?
gen
# How do separations of query complexities imply complexity class separations relative to oracles?

(Asked by: username_0 on 2022-11-28)

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](https://en.wikipedia.org/wiki/Simon%27s_problem) 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.

**Tags:** cc.complexity-theory, quantum-computing, separation

> **Comments:**
> **username_0**: @username_1 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.  
> **username_1**: 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:").  
> **username_1**: 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?  
> **username_0**: I'm not sure, @username_1 Can you describe what $L$ or $O$ should be and maybe I can fill in the gaps? I'm not familiar with relativized separations.  

---

## 1 answers

### Answer by username_2 on 2022-12-03. Score: 14 | Accepted answer

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](https://eccc.weizmann.ac.il/report/2018/107/), where at the end of the proof they used the same argument, in a probabilistic fashion.

> **Comments:**
> **username_0**: Thank you for taking the time to post this answer.  

---

