MathJax

Thursday, March 6, 2014

Nonlinear Quantum Mechanics, NP and the Polynomial Hierarchy

I've been reading Scott Aaronson's Quantum Computing since Democritus and he makes a point that "physicist complexity classes" should be closed under oracle calls to themselves. That is, PCCPCC = PCC for any complexity class PCC which is equivalent to the computational power of some laws of physics. This is because the physics should include oracle calls to other computer built with the same physics. What does this mean for nonlinear QM? We know NP and coNP are contained in BNLQP (Bounded-Error Nonlinear Quantum Polynomial-Time). So that NPNP  is contained in BNLQPBNLQP = BNLQP and in this way the entire polynomial hierarchy is contained inside BNLQP. Just how big is BNLQP?  The physically reasonable complexity class argument would mean $latex PH \subseteq BNLQP $ If NP is strictly contained in BNLQP, can we find reasonable laws of physics such that a computer built with those physics can solve NP (and nothing more) in polynomial time? Then, using physical reasoning we could prove that NPNP=NP=PH=coNP. If we prove NP \neq

Polynomial Hierarchy on Wikipedia


No comments:

Post a Comment