Quantum Computing since Democritus

by Scott Aaronson

But in a survey6 I wrote years ago, I explained why the ability to solve NP-complete problems would give us “godlike” powers – arguably, even more so than the ability to transmit superluminal signals or reverse the Second Law of Thermodynamics.