Date:
Tue, 11/06/201916:00-19:00
Location:
Location: Levin building, Lecture Hall No. 8 , Safra Campus
Lecturer: Prof.Scott Aaronson, University of Texas
Abstract:
One of the most basic questions at the intersection of computer science and physics is: can NP-complete problems be efficiently solved using the resources of the physical world? I'll survey the status of this question in 2019, touching on the P vs. NP problem; analog
computing using soap bubbles, protein folding, and more; the theoretical capabilities and the realizability of quantum computers; and proposals for going even beyond quantum computers, based on quantum field theories, quantum gravity, closed timelike curves, and various hypothetical modifications to quantum mechanics.
Abstract:
One of the most basic questions at the intersection of computer science and physics is: can NP-complete problems be efficiently solved using the resources of the physical world? I'll survey the status of this question in 2019, touching on the P vs. NP problem; analog
computing using soap bubbles, protein folding, and more; the theoretical capabilities and the realizability of quantum computers; and proposals for going even beyond quantum computers, based on quantum field theories, quantum gravity, closed timelike curves, and various hypothetical modifications to quantum mechanics.