This lecture develops the classical computational models that bridge to quantum computation within computational complexity theory: randomized computation, its bounded-error complexity classes, and reversible computation grounded in the thermodynamics of information. It establishes that error probability in a randomized decision procedure can be exponentially suppressed by majority voting (Chernoff bound), that information erasure carries an unavoidable thermodynamic cost (Landauer's principle) while logically reversible computation does not, and that a universal reversible gate set can simulate any Boolean circuit efficiently. It closes by defining the quantum circuit model and its complexity classes as generalizations of these classical notions.
This lecture develops the classical computational models that bridge to quantum computation within computational complexity theory: randomized computation, its bounded-error complexity classes, and r…