Norman Margolus: Quantum Limits on Classical Computation

Norm Margolus' (MIT) plenary talk from the Computing Community Consortium's October 2020 visioning workshop on Physics & Engineering Issues in Adiabatic/Reversible Classical Computing.

Abstract: How efficiently can large-scale classical computation be physically realized? We show that in the macroscopic classical realm, mechanics is discrete finite-state computation that achieves quantum bounds on speed and spatial resolution. This has interesting consequences for the interpretation of basic physical quantities. In the microscopic realm, we can harness deterministic wavefunction evolution to perform computation directly using discrete quantum degrees of freedom. If we use a perfect crystal of atoms that mimics the locality and uniformity of physical dynamics, the most efficient computations are again like classical mechanics, but with finite state.