# Is $BQP$ in $P^{NP}$?

I read in the introduction of this paper

http://www.scottaaronson.com/papers/uncompute.pdf

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

http://arxiv.org/pdf/quant-ph/9701001v1.pdf

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}$?

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

Green and Pruim  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.