Quantum Computing since Democritus

by Scott Aaronson

This is all talk and blather, though. Can we actually see what the trade-offs are between the number of hypotheses we consider and how much confidence we can have in predicting the future? One way we do this was formalized by Leslie Valiant in 1984.