# $BQP$ vs $QMA$?

The central problem of complexity theory is arguably $P$ vs $NP$.

However, since Nature is quantum, it would seem more natural to consider the classes $BQP$ (ie decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances) ans $QMA$ (the quantum equivalent of $NP$) instead.

My questions:

1) Would a solution to the $P$ vs $NP$ problem give a solution to $BQP$ vs $QMA$?

2) Do the three barriers of relativization, natural proofs and algebrization also apply to the $BQP$ vs $QMA$ problem?

1) No implication is known in either direction. We know that P=NP implies P=PH. But we don't know if BQP and QMA are in PH, so maybe P could equal NP yet BQP and QMA still wouldn't collapse. (On the other hand, note that QMA⊆PP⊆P#P, so certainly P=P#P would imply BQP=QMA.) To show that BQP=QMA implies P=NP seems even more hopeless in the present state of knowledge.

2) Absolutely, all three barriers apply with full force to BQP vs. QMA (and even to the "easier" problem of proving P≠PSPACE). First, relative to a PSPACE oracle (or even the low-degree extension of a PSPACE oracle), we have

P = NP = BQP = QMA = PSPACE,

so certainly nonrelativizing and non-algebrizing techniques will be needed to separate any of these classes. Second, to get a natural proofs barrier for putting stuff outside BQP, all you need is a pseudorandom function family that's computable in BQP, which is a formally weaker requirement than a pseudorandom function family computable in P.

Addendum: Let me say something about a "metaquestion" which you didn't ask but hinted at, of why people still focus on P vs. NP even though we believe Nature is quantum. Personally, I've always seen P vs. NP as nothing more than the "flagship" for a whole bunch of barrier questions in complexity theory (P vs. PSPACE, P vs. BQP, NP vs. coNP, NP vs. BQP, the existence of one-way functions, etc), none of which we know how to answer, and all of which are related in the sense that any breakthrough with one would very likely lead to breakthroughs with the others (even where we don't have formal implications between the questions, which in many cases we do). P vs. NP isn't inherently more fundamental than any of the others -- but if we have to pick one question to serve as the poster child for complexity, then it's a fine choice.