4
$\begingroup$

Context:

In quantum complexity theory and quantum information, there are several papers which study the implications of closed timelike curves (CTCs). In 2008, Aaronson and Watrous published their legendary 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. In the paper's abstract they specifically mention:

While closed timelike curves (CTCs) are not known to exist, studying their consequences has led to nontrivial insights in general relativity, quantum information, and other areas.

Now, this sounds pretty interesting, although I haven't really read any of the papers related to CTCs.

Questions:

  1. In brief, what really are closed timelike curves?
  2. Would it be possible to give a general idea about why this "time travel" of information can make quantum computing equivalent to classical computing, without diving too much into the details?
  3. What other non-trivial insights have the study of CTCs provided us in the context of quantum information?

I do intend to work through some of the papers on CTCs myself and perhaps also write an answer to this question at some point. But the aim of this thread is to gather some ideas about the "big picture" regarding why quantum information theorists and complexity theorists are interested in CTCs.


†: The abstract says that "given any quantum circuit (not necessarily unitary), a fixed-point of the circuit can be (implicitly) computed in polynomial space". I'm not sure how this relates to sending information via CTCs, causing quantum computing to be no more efficient than classical computing.

$\endgroup$
4
$\begingroup$

I just recently have been watching a series great YouTube lectures by Ryan O'Donnell at Carnegie Mellon. The last one in particular has some answers to the above question - especially the last 10 minutes or so.

I will summarize my limited understanding. Misunderstandings are my own...

  • A "closed timelike curve" (CTC) may be something akin to a wormhole in spacetime. Ends of the wormhole may connect disparate regions of space.
  • We can put a circuit in the CTC - with inputs on one end, and outputs on another end.
  • Suppose our circuit is a $\mathsf{NOT}$ gate.
  • If we put a classical $0$ into one mouth of the wormhole, then we get out a $1$ on the other end. But because the wormhole is closed, this can create a contradiction - as if we went back in time to kill our grandfather
  • But David Deutsch says we shouldn't put in a classical bit into the mouths of the wormhole! And further the operation performed in the wormhole shouldn't just be a classical $\mathsf{NOT}$ operation, but can be any quantum gate.
  • Indeed we can put in a qubit in a uniform superposition of $\vert 0\rangle+\vert 1\rangle$.
  • If we through such a qubit into the mouth of a CTC we won't get a contradiction - the negation of $\frac{1}{\sqrt{2}}\vert 0\rangle+ \frac{1}{\sqrt{2}}\vert 1\rangle$ is also $\frac{1}{\sqrt{2}}\vert 0\rangle+ \frac{1}{\sqrt{2}}\vert 1\rangle$
  • Thus $\frac{1}{\sqrt{2}}\vert 0\rangle+ \frac{1}{\sqrt{2}}\vert 1\rangle$ is a fixed point of the $\mathsf{NOT}$ gate.
  • Deutsch showed that any circuit has such a fixed point, that avoids such a violation/grandfather paradox
  • However, even though it's likely computationally difficult to determine what the fixed point of a circuit is, Deutsch and Aaronson and Watrous take it as a given that consistency of causality requires a CTC to automagically give the fixed point.
  • For example, if we have a CTC, and we feed it a $\mathrm{SAT}$ problem framed in the correct way, then the fixed points would correspond to only those solutions to the $\mathrm{SAT}$ problem.
  • O'Donnell describes how followups of Aaronson and Watrous leads to positive results with reference to sampling problems/quantum supremacy
  • That is, O'Donnell outlines a proof that if approximate sampling on a quantum computer were equivalent to approximate sampling on classical computer, then the polynomial time hierarchy collapses
  • The proof relies on the work of Aaronson and Watrous in ways that I'm not entirely sure of.
  • The net is that if quantum supremacy is achieved via approximate sampling, then under some reasonable hypothesis we can say that the "proof" as it were is related to non-trivial insights about the power of closed timelike curves.
$\endgroup$
  • $\begingroup$ That lecture series looks excellent. Thanks! I'll try to read through your answer in detail in the next few days. :) $\endgroup$ – Sanchayan Dutta May 19 at 13:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.