Sometimes I feel like classical physicists must have felt when quantum mechanics first came marching through the door...
Lance Fortnow chats with Scott Aaronson about what physicists need to know about complexity, and Dave Bacon (almost)-snarks that maybe we should be asking what computer scientists need to know about complexity.
He is referring to quantum complexity of course, the premise being quantum computing represents the definitive description of all "efficient" computing devices, rather than a poly-time (or randomized poly-time) classical TM.
I'd like to think that all my years spent learning classical algorithms and complexity haven't gone to waste ;), but something Scott said on the podcast was very interesting. He argued that one should not expect that a QP algorithm will solve an NP-hard problem. Now I don't know if this is a view shared by the quantum computing community in general, but it's definitely something I didn't expect: I had always imagined that the odds were in favor rather than against BQP containing NP.
I would say that the view that BQP does not contain NP is very common among those working on quantum complexity theory. (Maybe slightly less common among the physicists working in the field.) I consider this consensus some of the best 'evidence' that the model of quantum computation is not unreasonable: if it were, surely it could solve all of NP and beyond.
ReplyDelete-Wim
Posted by Wim van Dam
As an undergraduate whos gone to all of one summer school on the topic, I would agree with Wim. Most remain hesistant to say anything definitive and the most "zealous" about it sound just like Aaronson in the podcast. I believe that the rest claim to be agnostic until the evidence is more concrete. I could be way off base, however.
ReplyDeletePosted by Jeff Hodges