Quantum Computing since Democritus

by Scott Aaronson

(This was also the first complexity result I proved. Had I known that Adleman et al. had proved it a year before, I might never have gotten started in this business! Occasionally, it's better to have a small academic light cone.)