Particularly, we already have some oracle separation results such as $\mathbf{BPP}^A\neq \mathbf{BQP}^A$ [Simon], $\mathbf{NP}^A\not\subseteq \mathbf{BQP}^A$ [BBBV], and $\mathbf{BQP}^A\not\subseteq \mathbf{NP}^A$ [Bernstein and Vazirani]. But given that most problems are non-relativising, how does such oracle separation even counted as evidence of unconditional separation? Or do we need to discuss it case-wisely?
$\begingroup$
$\endgroup$
3
-
2$\begingroup$ Who considers it as evidence? Perhaps you should ask them. $\endgroup$– Yuval FilmusJul 18, 2019 at 6:00
-
3$\begingroup$ Who are "Simon", "BBBV", and "Aaronson"? Of course, I can imagine who these people are, but what papers exactly are you referring to? $\endgroup$– dkaeaeJul 18, 2019 at 7:20
-
$\begingroup$ Simon's problem already yield an oracle separation between BPP and BQP, though not the first. BBBV showed the query lower bound for collision problem, which gives an oracle separation of NP from BQP as well. As for the third one, I think I might made an mistake that Bernstein and Vazirani are actually those showed oracle separation of BQP from NP using Recursive Fourier Sampling problem. $\endgroup$– Taylor HuangJul 18, 2019 at 14:53
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
6
It can hardly be considered evidence for inequality or equality. We know $\mathsf{IP} = \mathsf{PSPACE}$, but there is an oracle $A$ relative to which $\mathsf{IP}^A \neq \mathsf{PSPACE}^A$ (as proved here). Similarly, there are classes which are not equal, even though their relativized versions to a certain oracle are equal (see here for a couple examples).
The reason for all this is that, for a complexity class $\mathsf{C}$ (corresponding to a machine model which admits oracles) and an oracle $O$, $\mathsf{C}^O$ is potentially a different class altogether from $\mathsf{C}$—and it is probably best to treat it as such.
-
$\begingroup$ Don't we also know oracles $A$ and $B$ such that $\mathrm{P}^A=\mathrm{NP}^A$ but $\mathrm{P}^B\neq\mathrm{NP}^B$? $\endgroup$ Jul 18, 2019 at 13:41
-
1$\begingroup$ @DavidRicherby That is also true, but I chose not to mention it since $\mathsf{P} = \mathsf{NP}$ is still open (and there are reputed researchers on both sides of the fence). I give examples for both equality and inequality where either case has been actually proven. $\endgroup$– dkaeaeJul 18, 2019 at 14:13
-
1$\begingroup$ Sure. But my point is that these oracles suggest that oracle results aren't evidence on way or the other. Which ever way the $\mathrm{P}$ vs $\mathrm{NP}$ question is settled, there'll be an oracle that says the opposite. $\endgroup$ Jul 18, 2019 at 14:20
-
$\begingroup$ I knew there are non-relativising barrier for relations such as IP=PSPACE. But then why do we even care about oracle separation stuff, if it provides no evidence toward proving unconditional separation? $\endgroup$ Jul 18, 2019 at 14:58
-
$\begingroup$ @DavidRicherby Yes, but we already have (proven) examples which say the opposite either way. This makes the $\mathsf{P}$ and $\mathsf{NP}$ example rather superficial, at least in my POV. $\endgroup$– dkaeaeJul 19, 2019 at 7:09
$\begingroup$
$\endgroup$
At best, the evidence given is only heuristic and informal, but it is still important. Oracles in the examples you gave do address the general question: how does quantum computing compare to nondeterminism and randomness, in power? The oracles definitely do not answer the original unrelativized questions, rather they provide a different (related) black-box model where the question provably has a negative answer. Since unconditional lower bounds are very difficult to come by, oracles can be useful information, but again it's only heuristic.
