Quantum Computing since Democritus

by Scott Aaronson

NP-complete problems are not efficiently solvable by physical means, and that if a theory suggests otherwise, more likely than not that indicates a problem with the theory.