Show simple item record

dc.contributor.authorAaronson, Scott
dc.date.accessioned2018-01-16T20:45:36Z
dc.date.available2018-01-16T20:45:36Z
dc.date.issued2017-12-04
dc.identifier.urihttp://hdl.handle.net/1853/59107
dc.descriptionPresented on December 4, 2017 at 11:00 a.m. in the Klaus Advanced Computing Building, room 1116.en_US
dc.descriptionScott Aaronson is David J. Bruton Centennial Professor of Computer Science at the University of Texas at Austin. Aaronson's research in theoretical computer science has focused mainly on the capabilities and limits of quantum computers.en_US
dc.descriptionRuntime: 74:16 minutesen_US
dc.description.abstractQuantum computers are proposed devices that would exploit quantum mechanics to solve certain specific problems dramatically faster than we know how to solve them with today's computers. In the popular press, quantum computers are often presented, not just as an exciting frontier of science and technology (which they are), but as magic devices that would work by simply trying every possible solution in parallel. However, research over the past 25 years has revealed that the truth is much more subtle and problem-dependent: for some types of problems, quantum computers would offer only modest speedups or no speedups at all. These limitations are entirely separate from the practical difficulties of building quantum computers (such as "decoherence"), and apply even to the fully error-corrected quantum computers we hope will be built in the future. In this talk, I'll give a crash course on what computer science has learned about both the capabilities and the limitations of quantum computers. Then, in a final section, I'll describe a remarkable and unexpected connection -- made just within the last five years -- where the conjectured limitations of quantum computers have been applied to issues in fundamental physics. These include Hawking's black-hole information puzzle (in its modern incarnation as the "firewall paradox"), and understanding the growth of wormholes in the so-called gauge/gravity duality that emerged from string theory.en_US
dc.format.extent74:16 minutes
dc.language.isoen_USen_US
dc.relation.ispartofseriesARC Colloquiumen_US
dc.subjectComputational complexityen_US
dc.subjectNP-complete problemsen_US
dc.subjectQuantum computingen_US
dc.titleBlack Holes, Firewalls, and the Limits of Quantum Computersen_US
dc.typeLectureen_US
dc.typeVideoen_US
dc.contributor.corporatenameGeorgia Institute of Technology. Algorithms, Randomness and Complexity Centeren_US
dc.contributor.corporatenameUniversity of Texas at Austin. Dept. of Computer Scienceen_US


Files in this item

This item appears in the following Collection(s)

  • ARC Talks and Events [64]
    Distinguished lectures, colloquia, seminars and speakers of interest to the ARC community

Show simple item record