Session P5: Quantum Information Meets Gravitation

8:00 AM–11:00 AM, Wednesday, March 12, 2008
Morial Convention Center Room: RO1

Sponsoring Unit: GQI
Chair: Matthew Leifer, Institute for Quantum Computing

Abstract ID: BAPS.2008.MAR.P5.1

Abstract: P5.00001 : Quantum Computational Complexity in the Presence of Closed Timelike Curves

8:00 AM–8:36 AM

Preview Abstract

Author:

  Dave Bacon
    (University of Washington)

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.

To cite this abstract, use the following reference: http://meetings.aps.org/link/BAPS.2008.MAR.P5.1