Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Quantum Complexity and Fundamental Physics

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


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.

Colloquium Image: Quantum Complexity

Scientific cartoon
Credit: Courtesy of


Created October 22, 2009, Updated January 3, 2017