Limits on Efficient Computation in the Physical World

INFORMAL SEMINAR
Topic:Limits on Efficient Computation in the Physical World
Speaker:Scot Aaronson
Affiliation:IAS
Date:Thursday, October 28
Time/Room:4:00pm - 6:00pm/S-101

I'll try to explain what we currently understand about the theoretical power of quantum computers, in a way that's accessible to a general math and physics audience. In particular, I'll demolish the popularly-held belief that quantum computing means unlimited exponential parallelism. I'll also critically examine speculative models of computation that go even beyond quantum computing, pointing out open research issues for those who know more physics than I do. The talk will include an experimental physics demonstration.