Quantum Computational Complexity in the Presence of Closed Timelike Curves

What are the consequences of modifying the laws of physics for the theory of computation? Considering this question in the context of quantum theory has led to a seemingly new class of computing devices known as quantum computers. In this talk I will discuss how modifying computation (in a quantum or classical context) to allow for closed timelike curves leads to a new model of computation. In particular I will discuss how such a model of computation with closed timlike curves can be formulated, whether it can be made robust to noise, and how recent results of Aaronson and Watrous show that this model is nothing more than the well studied complexity class PSPACE. Consequences of these results on foundational issues in quantum theory will also be discussed.