Quantum Computing since Democritus

by Scott Aaronson

that is, whether quantum computing is more powerful than classical. Today, we have evidence that this is indeed the case, most notably Shor's algorithm for factoring and discrete log.