Black Holes, Firewalls, and the Limits of Quantum Computers - Scott Aaronson
From Katie Gentilello on January 11th, 2018
Quantum 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.