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
 |
 |
|---|---|
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.