I read in the introduction of this paper


that there is a problem $B$ such that $BQP^B \not\subset P^{NP^B}$, and that $B$ is in $BPP$. But, using the fact that $BPP$ is in $BQP$ and that $BQP$ is low for itself (i.e. $BQP^{BQP}=BQP$), as proved in


can we state that $BQP^B \subseteq BQP^{BPP} \subseteq BQP^{BQP} = BQP$ and thus $BQP \not\subset P^{NP^B}$ and finally $BQP \not\subset P^{NP}$?

  • $\begingroup$ I'm missing why $BQP \not\subset {P^{NP}}^{B} \Rightarrow BQP \not\subset P^{NP}$. $\endgroup$ – Luke Mathieson Feb 2 '15 at 11:40
  • $\begingroup$ Because $P^{NP^B}$ is at least as large as $P^{NP}$. Am I wrong? $\endgroup$ – neophyte Feb 2 '15 at 12:57
  • $\begingroup$ Yes of course, apparently my brain broke for a moment. $\endgroup$ – Luke Mathieson Feb 2 '15 at 22:41

I think your logic is valid, but not sound.

The problem is that the oracle $B$ is not what's in $BPP$. The question being asked about $B$ is what's in $BPP$.

When Scott Aaronson's paper "Quantum Lower Bound for Recursive Fourier Sampling" says

Green and Pruim [10] gave an oracle B for which $BQP \not\subset P^{NP}$. [...] while Green and Pruim’s problem is in BPP

the noun phrase "Green and Pruim’s problem" is not refering to $B$.

The Problem

The referenced paper "Relativized Separation of EQP from $P^{NP}$" defines a problem $L$.

The input to $L$ is a predicate $B$ and a range parameter $n$. The predicate $B$ accepts natural numbers between $2^n$ and $2^{n+1}$, and returns either true or false for each. It is promised that $B$ will return true for either exactly $\frac{1}{4} 2^n$ of the allowed inputs, or else for exactly $\frac{3}{4} 2^n$ of them.

The output $L(B, n)$ is the classification of the relevant range of $B$ into the promised quarter-true or quarter-false categories.

The Separation

A $P^{NP}$ machine can't compute $L$ because $B$ has too many inputs to check. There's exponentially many spots to check (w.r.t. $n$), so eventually any accepting path must be leaving a huge proportion unchecked. An adversary can start with some arbitrary accepting input, simulate the proposed $P^{NP}$ machine to find out which inputs the machine checks on one path that accepts that input, then toggle inputs that that particular path didn't check to create a should-be-non-accepting input that fools the machine into accepting.

(Note: I implicitly assumed that $B$ could be inspected only by querying it. This fails e.g. if $B$ is provided as a circuit diagram. That's why $B$ will end up being our oracle.)

A $BPP$ machine can compute $L$ easily: just sample $B(x)$ at a random allowed $x$ and return that. The odds of getting it wrong are $\frac{1}{4}$, which is less than the typical-but-arbitrarily allowed $\frac{1}{3}$. You can sample more to make it more reliable.

A $BQP$ machine can also compute $L$, with the $BPP$ strategy.

An $EQP$ machine can use Grover's algorithm to solve $L$ with certainty. (Also works for BQP, but overkill.)

The Oracle

So we have a decision problem $L(B, n)$ that separates $P^{NP}$ and $BQP$, but relying crucially on the assumption that the machine is limited to querying $B$. Furthermore, we don't have enough input space to specify all of $B$'s outputs, and we can't use a compact representation like a program or circuit because that violates the only-querying-allowed assumption. Thus we're forced to cheat and give $B$ to the machine as an oracle.

This raises the issue of how to pick $B$. What if we picked a weak $B$, such as one where $L(B, n)$ is always $0$? Something that a $P^{NP}$ machine could be hardcoded into defeating? Fortunately we can get around that by choosing $B$ with diagonalization: iterate all $P^{NP}$ machines and use the $2^i$ to $2^{i+1}$ range of $B$ to defeat the $i$'th machine by the adversarial method I explained earlier.

Thus $B$ is an oracle that tells you something about how $P^{NP}$ machines try to query predicates, not an oracle about solving some problem in $BPP$. So it is not necessarily the case that $B \subset BPP$. It's probably not the case, actually, since computing a bounded version of $B$ involves simulating exponentially many $P^{NP}$ machines.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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