Quantum Computing since Democritus

by Scott Aaronson

Church–Turing Thesis: “Anything that is efficiently computable in the physical world is computable in polynomial time on a standard Turing machine.”