# 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.