Quantum Computing since Democritus

by Scott Aaronson

computational complexity theory reinvented the millennia-old concept of mathematical proof – making it probabilistic, interactive, and cryptographic.