<p>Sorry for the very "big picture" answer from a non-quantum-theorist, but this contrast might help: you could describe <em>algorithms</em> as the study of how to solve computational problems, whereas <em>complexity theory</em> 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.</p>

<p>(For instance, an <span class="math-container">$n^{100000}$</span> 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 <span class="math-container">$2^{0.00000001n}$</span> time algorithm for SAT would change our understanding of complexity much less, even though it would have huge practical implications.)</p>

<p>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.</p>

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

CC BY-SA 4.0
2019-05-21T14:53:30.333Z
Oh, it's not a good idea to accept this answer, because I didn't address Q2 and there is hope that someone such as Scott will come on and reply...
usul
CC BY-SA 4.0
2019-05-24T01:17:47.893Z
I know it's beside your point, but "A 2^(0.00000001n) time algorithm for SAT wouldn't change our understanding of complexity at all" is just false!
Ryan Williams
CC BY-SA 4.0
2019-05-24T03:22:27.830Z
@RyanWilliams, thanks/sorry for overstating the case - will edit.
usul
CC BY-SA 4.0
2019-06-01T23:05:30.963Z
What I meant was that such SAT algorithms, besides potentially being of practical importance, would also imply longstanding lower bounds in complexity. Not as famous as P != NP but still very interesting
Ryan Williams
CC BY-SA 4.0
2019-05-21T04:23:54.980Z
2019-05-24T03:22:48.373Z
2019-05-24T03:22:48.373Z
usul
<p>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 <a href="http://vixra.org/pdf/1307.0150v1.pdf" rel="nofollow noreferrer"> for perturbation study</a>. References <a href="https://arxiv.org/pdf/quant-ph/9711070.pdf" rel="nofollow noreferrer">for optimality</a>, and <a href="https://arxiv.org/abs/1110.6713" rel="nofollow noreferrer"> information geometric study of Grover search</a>.</p>

<p><a href="https://arxiv.org/abs/quant-ph/9910115v3" rel="nofollow noreferrer">Alvarez et al</a> 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".</p>

CC BY-SA 4.0
2019-05-22T05:46:12.573Z
2019-05-22T05:46:12.573Z
user3483902
<p>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.</p>

<p>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.) </p>

<p>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!) </p>

CC BY-SA 4.0
2024-03-15T16:28:05.060Z
Regarding my comments about tape-head reversals, I have since learned that actually they are closely related to a fairly robust notion of complexity that arises in multiple settings, namely parallel time https://doi.org/10.1109/SFCS.1979.29, see also https://doi.org/10.1109/SFCS.1989.63544, https://doi.org/10.1137/0220039, http://dx.doi.org/10.1016/j.tcs.2008.04.026.
Joshua Grochow
CC BY-SA 4.0
2019-05-22T18:04:00.080Z
2019-05-22T18:11:10.637Z
2019-05-22T18:11:10.637Z
Joshua Grochow
<p><strong>Context</strong>:</p>

<p>There are <a href="https://scholar.google.co.in/scholar?hl=en&amp;as_sdt=0%2C5&amp;q=closed+timelike+curves+quantum+%22complexity%22&amp;btnG=" rel="noreferrer">several papers</a> that study the implications of <a href="https://en.wikipedia.org/wiki/Closed_timelike_curve" rel="noreferrer">closed timelike curves (CTCs)</a> to quantum complexity. In 2008, Aaronson and Watrous published their <a href="https://royalsocietypublishing.org/doi/10.1098/rspa.2008.0350" rel="noreferrer">famous paper</a> 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. </p>

<p><strong>Questions</strong>:</p>

<ul>
<li><p><a href="https://arxiv.org/abs/0808.2669" rel="noreferrer">The abstract</a> clearly says that closed timelike curves are <em>not</em> 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? </p></li>
<li><p>Are there any other <a href="https://en.wikipedia.org/wiki/World_line" rel="noreferrer">world lines</a> 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)?</p></li>
</ul>

<p>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. </p>

<hr>

<p><sup><strong>Note</strong>: I <a href="https://quantumcomputing.stackexchange.com/questions/6192">previously asked</a> about this on Quantum Computing SE, in the context of quantum information theory, but here I'm <em>specifically</em> trying to view it through the lenses of a complexity theorist or computer scientist.</sup></p>

CC BY-SA 4.0
2019-05-19T21:07:08.360Z
[Here's a (part of a) lecture on it from Scott Aaronson himself](https://youtu.be/hJibtaTmLtU?t=1030), titled "Computational Phenomena in Physics" from the mini workshop *Lens of Computation on the Sciences*.
Yonatan N
CC BY-SA 4.0
2019-05-20T00:56:45.340Z
Every engineered construct started with physical experiments, which in turn, started with thought experiments... There is also a relatively new lecture on the subject by Aaronson here: https://www.youtube.com/watch?v=Ha4eG8gLSK4
Avi Tal
CC BY-SA 4.0
2019-05-20T14:16:48.557Z
Why? Because it’s fun to play with time-travel!
Frédéric Grosshans
<cc.complexity-theory><quantum-computing><big-picture>
Why exactly are complexity theorists interested in closed timelike curves?
Sanchayan Dutta
# Why exactly are complexity theorists interested in closed timelike curves?

(Asked by: username_0 on 2019-05-19)

**Context**:

There are [several papers](https://scholar.google.co.in/scholar?hl=en&as_sdt=0%2C5&q=closed+timelike+curves+quantum+%22complexity%22&btnG=) that study the implications of [closed timelike curves (CTCs)](https://en.wikipedia.org/wiki/Closed_timelike_curve) to quantum complexity. In 2008, Aaronson and Watrous published their [famous paper](https://royalsocietypublishing.org/doi/10.1098/rspa.2008.0350) 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](https://arxiv.org/abs/0808.2669) 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](https://en.wikipedia.org/wiki/World_line) 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](https://quantumcomputing.stackexchange.com/questions/6192) 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.

**Tags:** cc.complexity-theory, quantum-computing, big-picture
> **Comments:**
> **username_1**: [Here's a (part of a) lecture on it from Scott Aaronson himself](https://youtu.be/hJibtaTmLtU?t=1030), titled "Computational Phenomena in Physics" from the mini workshop *Lens of Computation on the Sciences*.  
> **username_2**: Every engineered construct started with physical experiments, which in turn, started with thought experiments... There is also a relatively new lecture on the subject by Aaronson here: https://www.youtube.com/watch?v=Ha4eG8gLSK4  
> **username_3**: Why? Because it’s fun to play with time-travel!  

---

## 3 answers

### Answer by username_7 on 2019-05-22. Score: 9 | Accepted answer

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!)

> **Comments:**
> **username_7**: Regarding my comments about tape-head reversals, I have since learned that actually they are closely related to a fairly robust notion of complexity that arises in multiple settings, namely parallel time https://doi.org/10.1109/SFCS.1979.29, see also https://doi.org/10.1109/SFCS.1989.63544, https://doi.org/10.1137/0220039, http://dx.doi.org/10.1016/j.tcs.2008.04.026.  

---

### Answer by username_4 on 2019-05-21. Score: 9

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.

> **Comments:**
> **username_4**: Oh, it's not a good idea to accept this answer, because I didn't address Q2 and there is hope that someone such as Scott will come on and reply...  
> **username_5**: I know it's beside your point, but "A 2^(0.00000001n) time algorithm for SAT wouldn't change our understanding of complexity at all" is just false!  
> **username_4**: @RyanWilliams, thanks/sorry for overstating the case - will edit.  
> **username_5**: What I meant was that such SAT algorithms, besides potentially being of practical importance, would also imply longstanding lower bounds in complexity. Not as famous as P != NP but still very interesting  

---

### Answer by username_6 on 2019-05-22. Score: 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](http://vixra.org/pdf/1307.0150v1.pdf). References [for optimality](https://arxiv.org/pdf/quant-ph/9711070.pdf), and  [information geometric study of Grover search](https://arxiv.org/abs/1110.6713).

[Alvarez et al](https://arxiv.org/abs/quant-ph/9910115v3) 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".


---

