One of the points of Scott Aaronson's excellent "Quantum Computing since Democritus" is that if you can quickly solve NP problems, you basically have super powers. Forget about SAT or Travelling Salesman, you can now do fast automated theorem provers and the like. Depending on how it were solved, you wouldn't read about P=NP on arxiv, you'd read about someone making billions on the stock market. Aaronson describes it as being comparably implausible to having faster than light communication.
If this paper is true, then it looks to me like quantum computers would be a means of doing that. I'm skeptical. Know those sci-fi stories where they hand-wave a quantum computer to have infinite computing power? Then they simulate the universe or hack all the computers simultaneously or whatever. That's all a laughable misinterpretation of what current state-of-the-art quantum algorithms can do (even if we remove the technical details of constructing the machine). Well, if this paper holds up, then that's a whole lot closer to the truth, maybe!
(Disclaimer: not an expert. I really hope to see Aaronson's analysis of this soon.)
If this paper is true, then it looks to me like quantum computers would be a means of doing that. I'm skeptical. Know those sci-fi stories where they hand-wave a quantum computer to have infinite computing power? Then they simulate the universe or hack all the computers simultaneously or whatever. That's all a laughable misinterpretation of what current state-of-the-art quantum algorithms can do (even if we remove the technical details of constructing the machine). Well, if this paper holds up, then that's a whole lot closer to the truth, maybe!
(Disclaimer: not an expert. I really hope to see Aaronson's analysis of this soon.)