DROPS

Document

DOI: 10.4230/LIPIcs.FSTTCS.2014.469

One Time-traveling Bit is as Good as Logarithmically Many

Authors: Ryan O'Donnell and A. C. Cem Say

Published in: LIPIcs, Volume 29, 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)

Abstract

We consider computation in the presence of closed timelike curves (CTCs), as proposed by Deutsch. We focus on the case in which the CTCs carry classical bits (as opposed to qubits). Previously, Aaronson and Watrous showed that computation with polynomially many CTC bits is equivalent in power to PSPACE. On the other hand, Say and Yakaryilmaz showed that computation with just 1 classical CTC bit gives the power of "postselection", thereby upgrading classical randomized computation (BPP) to the complexity class BPP_path and standard quantum computation (BQP) to the complexity class PP. It is natural to ask whether increasing the number of CTC bits from 1 to 2 (or 3, 4, etc.) leads to increased computational power. We show that the answer is no: randomized computation with logarithmically many CTC bits (i.e., polynomially many CTC states) is equivalent to BPP_path. (Similarly, quantum computation augmented with logarithmically many classical CTC bits is equivalent to PP.) Spoilsports with no interest in time travel may view our results as concerning the robustness of the class BPP_path and the computational complexity of sampling from an implicitly defined Markov chain.

Cite as

Ryan O'Donnell and A. C. Cem Say. One Time-traveling Bit is as Good as Logarithmically Many. In 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 29, pp. 469-480, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{odonnell_et_al:LIPIcs.FSTTCS.2014.469,
  author =	{O'Donnell, Ryan and Cem Say, A. C.},
  title =	{{One Time-traveling Bit is as Good as Logarithmically Many}},
  booktitle =	{34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)},
  pages =	{469--480},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-77-4},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{29},
  editor =	{Raman, Venkatesh and Suresh, S. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2014.469},
  URN =		{urn:nbn:de:0030-drops-48646},
  doi =		{10.4230/LIPIcs.FSTTCS.2014.469},
  annote =	{Keywords: Time travel, postselection, Markov chains, randomized computation}
}

Search Results

Documents authored by Cem Say, A. C.

One Time-traveling Bit is as Good as Logarithmically Many

Abstract

Cite as

Thanks for your feedback!

Could not send message