6

Why does Simon's algorithm show that there exists an oracle $O$ such that $\mathsf{BPP}^O$ is not equal to $\mathsf{BQP}^O$?

To show that $\mathsf{BQP}^O$ is larger than $\mathsf{BPP}^O$, one needs to find a language $L$ in $\mathsf{BQP}^O$ that is not in $BPP^O$. For the case of Simon's problem showing this separation, what is $O$ and what is $L$?

Simon's problem is an example of a problem where the quantum algorithm takes exponentially fewer queries than all possible classical algorithms. This gives a black box separation (i.e. a query separation) between $\mathsf{BPP}$ and $\mathsf{BQP}$. But how does this imply an oracle separation between $\mathsf{BPP}$ and $\mathsf{BQP}$?

xutinal
  • 61
  • 3

2 Answers2

2

Oracle separations and black-box separations are effectively synonymous.

Simon didn't give any specific language $L$ that can be solved more efficiently on a quantum computer than on a classical computer, because he did not, in particular, instantiate his this by applying it to a language that satisfies his promise. Rather, he gave a class of languages $O$, and showed that, relative to this class, $\mathsf{BPP}^O\ne\mathsf{BQP}^O$.

We say "in the black-box setting, a quantum computer needs fewer oracle calls than a classical computer to solve an instance of Simon's problem." We don't yet have a particular instance of a language that is in Simon's class of languages - that satisfies Simon's promise -because we don't know how to instantiate it concretely, even after ~30 years.

Mark Spinelli
  • 11,947
  • 2
  • 19
  • 65
  • 1
    I'm confused by why "Oracle separations and black-box separations are effectively synonymous."

    I understand an oracle separation between BQP and BPP to mean that there exists an oracle O for which BQP^O is not equal to BPP^O (i.e. there exists a language L that can be decided by a BQP machine with access to O that cannot be decided by a BPP machine with access to O). And I understand a black-box separation between BQP and BPP to mean that there exists an oracle O for which the BQP machine requires fewer queries to learn O than the BPP machine. Why are the two definitions above synonymous?

     – xutinal Oct 22 '22 at 15:43
  • The answer says that Simon "gave a class of languages O" and showed that BPP^O is not equal to BQP^O. But what is this class O of languages? – xutinal Oct 22 '22 at 15:46
  • 1
    The class $O$ contains any language to decide Simon's problem of whether $s\ne 0$ if for all $x,y$ in the domain $f(x)=f(y)=f(x\oplus s)$ for a function $f$ that satisfies Simon's promise. – Mark Spinelli Oct 22 '22 at 16:04
  • What does "language to decide Simon's problem of whether $s\neq 0$" mean? – xutinal Oct 22 '22 at 16:09
  • In this paper (https://dl.acm.org/doi/pdf/10.1145/3313276.3316315), it states that "It is well known that this implies an oracle O relative to which BQP is not contained in PH." Again, I don't understand why showing "an explicit black-box (promise) problem that can be solved by a polynomial-time quantum algorithm with only one query, but cannot be solved by a classical algorithm in the polynomial-time hierarchy" implies "an oracle O relative to which BQP is not contained in PH." – xutinal Oct 22 '22 at 16:15
1

From Footnote 1 in the paper you mentioned in your comment (Oracle Separation of BQP and PH by Raz and Tal)

In our entire discussion of black-box complexity classes, we consider complexity classes of promise problems, rather than decision problems. Nevertheless, separations of classes of promise problems in the black-box model imply oracle separations of the corresponding classes of decision problems in the “real” world

The footnote then refers to Aaronson's paper BQP and the polynomial hierarchy which says:

We should clarify that there are two questions here: whether $\mathsf{BQP} \subseteq \mathsf{PH}$ and whether $\mathsf{PromiseBQP} \subseteq \mathsf{PromisePH}$. In the unrelativized world, it is entirely possible that quantum computers can solve promise problems outside the polynomial hierarchy, but that all languages in $\mathsf{BQP}$ are nevertheless in $\mathsf{PH}$. However, for the specific purpose of constructing an oracle $A$ such that $\mathsf{BQP}^A \not \subset \mathsf{PH}^A$, the two questions are equivalent, basically because one can always “offload” a promise into the construction of the oracle $A$.

Then he gave a proof for this claim.

You can find a related discussion in the comments under this blogpost: https://scottaaronson.blog/?p=451 (comments #21-23)

Egretta.Thula
  • 9,972
  • 1
  • 11
  • 30