Quantum Computing since Democritus

by Scott Aaronson

I would think that any world in which we could solve NP-complete problems efficiently would not look much like our world. For NP-intermediate problems like factoring and Graph Isomorphism,