Re:A Polynomial Time Bounded-Error Quantum Algorithm for Boo...
by NegativeK on Wednesday July 22, 2015 @08:55AM
(#9929293)
As another commenter pointed out, being able to crack NP problems quickly will give you theorem provers.
At that point quantum computing research will receive gobs of funding -- and our knowledge will absolutely explode.
You can debate whether it's the absolute top discovery, but this would be a lever to shift around the entire math and computer science field. If it wasn't a shaky paper, of course.
Re:A Polynomial Time Bounded-Error Quantum Algorithm for Boo...
by hiddencost on Wednesday July 22, 2015 @10:04AM
(#9929686)
You're right. Century is silly. A tractable algorithm for P = NP would be the single greatest discovery of science. Implications would dwarf gravity and DNA.
(Side note: until scott aaronson says otherwise, this paper is wrong. )
Re:A Polynomial Time Bounded-Error Quantum Algorithm for Boo...
by andyjohnson0 on Wednesday July 22, 2015 @08:12AM
(#9929080)
"Discovery of the century" is a shorthand for really important. Don't take it literally. Proving P=NP would be extremely significant in mathematics, though.
Re:A Polynomial Time Bounded-Error Quantum Algorithm for Boo...
by mekkz on Wednesday July 22, 2015 @08:32AM
(#9929175)
Nobody doubts that proving P=NP would be the discovery of the century, but that's not what this paper is trying to prove.
Re:A Polynomial Time Bounded-Error Quantum Algorithm for Boo...
by andyjohnson0 on Wednesday July 22, 2015 @10:01AM
(#9929671)
You're correct. They're claiming an algorithm to solve an NP hard problem in polynomial time.
I was thinking of "if this paper is a contribution to eventually proving/disproving P=NP...", but failed to express that.
Re:A Polynomial Time Bounded-Error Quantum Algorithm for Boo...
by invernomut0 on Wednesday July 22, 2015 @08:10AM
(#9929071)
Note: This century started in 2000, not one hundred years ago.
Heck, most of the early groundwork in the computational field is probably more important than an algorithm that is useful only on quantum computers.