Quantum Complexity and Fundamental Physics

Quantum Complexity and Fundamental Physics

Scott Aaronson
Computer Science and Artificial Intelligence Laboratory
Massachusetts Institute of Technology

Friday, May 29, 2009
10:30 a.m., Green Auditorium
VTC to Boulder will be Room 1107

colloquim image
Courtesy of xkcd.com

What are the ultimate limits on what can feasibly be computed in the physical world? In this talk, I'll try to show how this question ties together many of the central concerns of math, computer science, and physics. I'll also explain how research in quantum computing has transformed our understanding of the question over the last fifteen years. Finally, I'll offer a concrete conjecture—that there is no physical means to solve certain computationally complex problems (NP-complete)—and discuss the evidence for this conjecture, as well as the implications for physics if it's accepted.

Anyone outside NIST wishing to attend must be sponsored by a NIST employee and receive a visitor badge. For more information, call Kum J. Ham at 301-975-4203.

Colloquia are videotaped and available in the NIST Research Library.

Created October 22, 2009, Updated September 21, 2016