Why exactly are complexity theorists interested in closed timelike curves?

Question

Context:

There are several papers that study the implications of closed timelike curves (CTCs) to quantum complexity. In 2008, Aaronson and Watrous published their famous paper on this topic which shows that certain forms of time travel can make classical and quantum computing equivalent i.e. quantum computers provide no computational advantage if they can send information to the past through closed-timelike curves.

Questions:

• The abstract clearly says that closed timelike curves are not known to exist. So why exactly are complexity theorists interested in this topic? Does the study of CTCs provide some non-trivial insight into the fundamentals of complexity theory?

• Are there any other world lines that are popularly studied in the context of complexity theory? If yes, why? If not, why not (and then what's so special about CTCs)?

I haven't really gotten around to working through the CTC papers, but I'm trying to get an idea of the "big picture" here, so as to understand the motivation behind studying this topic.

---

^{Note: I previously asked about this on Quantum Computing SE, in the context of quantum information theory, but here I'm specifically trying to view it through the lenses of a complexity theorist or computer scientist.}

Answer 1

I think the big question here is "What does the complexity/power of algorithms look like in our universe?" If we ignore relativity and QM, then plain vanilla Turing machines are a decent model. But relativity and QM are our current best physical theories for explaining the universe, so the question is whether taking relativistic or quantum effects changes the complexity landscape.

In the case of QM, this is now also motivated by the potential for the engineering of working quantum computers. In the case of CTCs, although they aren't known to exist, my understanding is they they are allowed according to relativity. So the question is: if they did exist and we could take advantage of them, what else could computers do / how does complexity change? (Same goes for QM, we're just closer to quantum computers existing.)

Finally, a bit about personal taste; although this is subjective, the question itself is at least a little about subjective taste, so I hope this is appropriate. I actually want to (amicably) disagree with usul a little here. I don't think that all resources are necessarily interesting to (most) complexity theorists. For example, on a Turing machine one can consider head reversals as a resource (how many times does the tape head change direction during a computation?). One can even show this is a Blum complexity measure, with gap, speed-up, and hierarchy theorems analogous to time or space. I've seen this given as a fun exercise in undergrad courses, but haven't seen a whole lot of research about it. Why? Perhaps you because it feels more model-dependent and less relevant to other things people care about regarding the complexity of algorithms. Similarly, people study hyper computation (what could a TM do with infinitely many steps); while there's certainly more research into this, I think it is less well motivated from physical reality... My point here is not to malign any particular research directions (in fact, I think they're somewhat interesting), but more that I don't think complexity theorists are necessarily interested in CTCs "by definition", but rather there are additional considerations that lead to them being interesting to many. (And, of course, probably not all complexity theorists find them interesting!)

Answer 2

Sorry for the very "big picture" answer from a non-quantum-theorist, but this contrast might help: you could describe algorithms as the study of how to solve computational problems, whereas complexity theory studies the resources (especially time) required in theory to solve them. How hard are these problems really at some fundamental level, and how are they classified by resource requirements? This question is considered interesting regardless of how many or what kinds of resources puny humans happen to have at their disposal.

(For instance, an $n^{100000}$ time algorithm for SAT would totally upend our view of complexity theory even if it never impacted any algorithms we could run in this universe. A $2^{0.00000001n}$ time algorithm for SAT would change our understanding of complexity much less, even though it would have huge practical implications.)

The question of how much time is needed in theory to solve a problem changes if you allow CTCs, therefore they are interesting to complexity theory by definition.

So I feel your first question is like asking why computability theorists would study Turing degrees higher than zero; it's what they do.

Answer 3

If one considers geodesics as a worldline geometric analysis of Grover search, show under a metric that Grover search follows a geodesic. Under small perturbations too, Grover search works well. Also, given a perturbation, under a type of kahler metric - the Fubini-Study metric - Grover search cannot follow a geodesic, see for perturbation study. References for optimality, and information geometric study of Grover search.

Alvarez et al started with showing Grover search follows a geodesic under the Fubini-Study metric, and they explored other quantum algorithms such as Shors algorithm. Though this was done in context of Fisher information, still showed that under the Fubini-Study metric Grover search follows a geodesic. Also, Alvarez et al show under Fisher information assumptions - "Shor's factorization does not preserve constant Fisher's information".