Scott Aaronson: Computability Theory of Closed Timelike Curves

A talk by Scott Aaronson at the Workshop on Computational Complexity and High Energy Physics, hosted July 31 to August 2, 2017 by the Joint Center for Quantum Information and Computer Science at the University of Maryland. Abstract: In a seminal 1991 paper, David Deutsch proposed a formal model of closed timelike curves (CTCs), or time travel into the past, which used linear algebra to "resolve the grandfather paradox." In 2008, John Watrous and I showed that, under Deutsch's model, both a classical computer and a quantum computer with access to a polynomial-size CTC could solve exactly the problems in PSPACE. In this talk, I'll review this result and then give a new extension to the setting of computability theory. Namely, I'll show that a classical or quantum computer with access to a Deutschian CTC (with no bound on its size) could solve exactly the problems that are Turing-reducible to the halting problem. Just like in the complexity setting, the most technically interesting part is the upper bound on the power of quantum computers with access to a Deutschian CTC. This is joint work with Mohammad Bavarian and Giulio Gueltrini.