35
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
34
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Hi Scott, thanks a lot for this great answer! And your addendum addresses exactly what I had in mind. $\endgroup$
    – Anthony Leverrier
    Nov 24, 2010 at 22:29
  • 7
    $\begingroup$ I suppose the importance of P vs. NP, as the "flagship" problem of complexity theory, indicates something about the history of the theory of computation. After the logicians, it seems to have been combinatoricists who pursued the subject with most interest. Perhaps if complexity theory had been developed by operator theorists instead, the flagship problem for "hardness" would not be boolean satisfiability, 3-colouring, or the traveling salesman problem, but the problem of determining whether a sum of k-local positive semidefinite operators is positive definite. (Which is k-QSAT, of course.) $\endgroup$
    – Niel de Beaudrap
    Nov 25, 2010 at 9:50
  • $\begingroup$ Yes, I guess that as long as new techniques are required for any such problem (P vs NP, BQP vs QMA, etc), it doesn't hurt too much to focus on one specific problem. $\endgroup$
    – Anthony Leverrier
    Nov 25, 2010 at 13:51
  • 8
    $\begingroup$ A side comment - if you consider quantum computing as your definition of feasible computation, you'd probably look at BQP vs NP as the central question, and not BQP vs QMA. The reason is that NP still captures a huge fraction of the questions we want to solve (or want to stay hard for crypto), regardless if we try to solve them with a classical or quantum computer. $\endgroup$
    – Boaz Barak
    Nov 26, 2010 at 6:24
  • 1
    $\begingroup$ @Boaz - Do you think NP problems are intrinsically more relevant that QMA problems, or that it appears to be the case for the moment because we are more used to think in terms of classical problems than quantum ones? $\endgroup$
    – Anthony Leverrier
    Nov 26, 2010 at 10:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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