I'm reading Scott Aaronson's book, Quantum Computing Since Democritus, which according to Amazon.com is frequently bought together with Schrödinger's Killer App (the second, funniest book on quantum computing to appear this year).
In spite of Stephen Wolfram's scathing review, and apparent exponential growth of mind-bending computer science acronyms, I am finding it quite enjoyable and, as a simple-minded quantum physicist, I am also finding that I'm learning quite a lot and, against my own will, thinking a lot about computer complexity theory.
A particular comment by Aaronson, connecting the P vs NP business to something in physics, struck a nerve. I first heard about this business in graduate school in the 1980s when the mathematics students would jokingly scrawl "P=NP!" on the chalkboard only to find the next day somebody added a slash so it read "P≠NP!" and they all had a good laugh and the physics students all just shook their heads.
I had to wrestle with this again in 1994 after Shor's algorithm hit the fan and, as a reviewer of quantum computing proposals for the Department of Defense, I had to have at least some idea of what all these proposals were talking about. However I felt it was all really a bunch of non-physical mumbo jumbo about what the computer scientists thought were hard or not hard problems, even though they could not much prove anything.
I really did not care if it turned out that P=NP or not and most physicists I talk to don't much care either. If it indeed turns out that someday P=NP it would just mean that the computer scientists were not trying hard enough to find a proof and in any case it had little to do with physics.
However I'm ready to not quite eat but perhaps just reheat my 'umble pie. The bit in Scott's book that struck a nerve was his discussion of the feeling that if P=NP, even on a quantum computer, then we would have 'God-like' powers. Again that sounds just like hype but here's the physics.
From the 1998 paper by Daniel Abrams and Seth Lloyd we know that if quantum mechanics was nonlinear, with even a small non-linearity of the Weinberg type, then we could build super-duper quantum computers to solve not only NP-complete problems, but also the supposed even harder class of #P problems, all in polynomial time on the nonlinear quantum mechanics machine.
However the Weinberg model for nonlinear quantum mechanics would also permit superluminal communication and the violation of the second law of thermodynamics. The superluminal communication is the worst as this would lead to a violation of Einstein causality, something that never happens in ordinary linear quantum theory. It is well known that with superluminal communication, allowing you to send messages backwards in time, you can get a computational speedup by just letting your classical computer run for an exponential amount of time and then have it transmit the answer backwards in time to you so that the overall effect is a polynomial-time computation.
So if Nature gave us Weinberg nonlinear quantum mechanics, instead of ordinary linear quantum mechanics, we could use that to compute NP-complete and #P problems in polynomial time, violate causality, and for extra credit violate the second law of thermodynamics. Physicists should be very concerned if we could do the latter two things and hence, I posit along with Aaronson, that physicists should be very concerned if we could do the first two things as well.
Beware! There is no proof that the ability to solve NP-complete or #P problems implies the violation of causality or the second law. But it is suggestive that there is one resource, nonlinear quantum mechanics of the Weinberg type, that allows you do all of these — that is it gives us 'God-like' powers.
I suggest then that physicists who shudder at the thought of a theory that implies a violation of Einstein causality and the second law should also shudder at the thought that someday we will find a polynomial route to solving NP-complete problems using the laws of physics as we currently understand them.
In spite of Stephen Wolfram's scathing review, and apparent exponential growth of mind-bending computer science acronyms, I am finding it quite enjoyable and, as a simple-minded quantum physicist, I am also finding that I'm learning quite a lot and, against my own will, thinking a lot about computer complexity theory.
A particular comment by Aaronson, connecting the P vs NP business to something in physics, struck a nerve. I first heard about this business in graduate school in the 1980s when the mathematics students would jokingly scrawl "P=NP!" on the chalkboard only to find the next day somebody added a slash so it read "P≠NP!" and they all had a good laugh and the physics students all just shook their heads.
I had to wrestle with this again in 1994 after Shor's algorithm hit the fan and, as a reviewer of quantum computing proposals for the Department of Defense, I had to have at least some idea of what all these proposals were talking about. However I felt it was all really a bunch of non-physical mumbo jumbo about what the computer scientists thought were hard or not hard problems, even though they could not much prove anything.
I really did not care if it turned out that P=NP or not and most physicists I talk to don't much care either. If it indeed turns out that someday P=NP it would just mean that the computer scientists were not trying hard enough to find a proof and in any case it had little to do with physics.
However I'm ready to not quite eat but perhaps just reheat my 'umble pie. The bit in Scott's book that struck a nerve was his discussion of the feeling that if P=NP, even on a quantum computer, then we would have 'God-like' powers. Again that sounds just like hype but here's the physics.
From the 1998 paper by Daniel Abrams and Seth Lloyd we know that if quantum mechanics was nonlinear, with even a small non-linearity of the Weinberg type, then we could build super-duper quantum computers to solve not only NP-complete problems, but also the supposed even harder class of #P problems, all in polynomial time on the nonlinear quantum mechanics machine.
However the Weinberg model for nonlinear quantum mechanics would also permit superluminal communication and the violation of the second law of thermodynamics. The superluminal communication is the worst as this would lead to a violation of Einstein causality, something that never happens in ordinary linear quantum theory. It is well known that with superluminal communication, allowing you to send messages backwards in time, you can get a computational speedup by just letting your classical computer run for an exponential amount of time and then have it transmit the answer backwards in time to you so that the overall effect is a polynomial-time computation.
So if Nature gave us Weinberg nonlinear quantum mechanics, instead of ordinary linear quantum mechanics, we could use that to compute NP-complete and #P problems in polynomial time, violate causality, and for extra credit violate the second law of thermodynamics. Physicists should be very concerned if we could do the latter two things and hence, I posit along with Aaronson, that physicists should be very concerned if we could do the first two things as well.
Beware! There is no proof that the ability to solve NP-complete or #P problems implies the violation of causality or the second law. But it is suggestive that there is one resource, nonlinear quantum mechanics of the Weinberg type, that allows you do all of these — that is it gives us 'God-like' powers.
I suggest then that physicists who shudder at the thought of a theory that implies a violation of Einstein causality and the second law should also shudder at the thought that someday we will find a polynomial route to solving NP-complete problems using the laws of physics as we currently understand them.
No comments:
Post a Comment