Document Open Access Logo

One Time-traveling Bit is as Good as Logarithmically Many

Authors Ryan O'Donnell, A. C. Cem Say

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2014.469.pdf
  • Filesize: 0.5 MB
  • 12 pages

Document Identifiers

Author Details

Ryan O'Donnell
A. C. Cem Say

Cite As Get BibTex

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) https://doi.org/10.4230/LIPIcs.FSTTCS.2014.469

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.

Subject Classification

Keywords
  • Time travel
  • postselection
  • Markov chains
  • randomized computation

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Scott Aaronson. Is quantum mechanics an island in Theoryspace? Technical Report quant-ph/0401062, arXiv, 2004. Google Scholar
  2. Scott Aaronson. Limits on Efficient Computation in the Physical World. PhD thesis, University of California, Berkeley, 2004. Google Scholar
  3. Scott Aaronson. NP-complete problems and physical reality. ACM SIGACT News, 36(1):30-52, 2005. Google Scholar
  4. Scott Aaronson. Quantum computing, postselection, and probabilistic polynomial-time. Proceedings of the Royal Society A, 461(2063):3473-3482, 2005. Google Scholar
  5. Scott Aaronson and John Watrous. Closed timelike curves make quantum and classical computing equivalent. Proceedings of the Royal Society A, 465(2102):631-647, 2009. Google Scholar
  6. David Aldous. Reversible Markov chains and random walks on graphs, 2002. URL: http://www.stat.berkeley.edu/~aldous/RWG/book.pdf.
  7. Venkat Anantharam and Pantelis Tsoucas. A proof of the Markov chain tree theorem. Statistics & Probability Letters, 8(2):189-192, 1989. Google Scholar
  8. Søren Asmussen, Peter Glynn, and Hermann Thorisson. Stationarity detection in the initial transient problem. ACM Transactions on Modeling and Computer Simulation, 2(2):130-157, 1992. Google Scholar
  9. James Aspnes, David Fischer, Michael Fischer, Ming-Yang Kao, and Alok Kumar. Towards understanding the predictability of stock markets from the perspective of computational complexity. In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 745-754, 2001. Google Scholar
  10. James Aspnes, David Fischer, Michael Fischer, Ming-Yang Kao, and Alok Kumar. Towards understanding the predictability of stock markets from the perspective of computational complexity. In New Directions in Statistical Physics, pages 129-151. Springer Berlin Heidelberg, 2004. Google Scholar
  11. Dave Bacon. Quantum computational complexity in the presence of closed timelike curves. Physical Review A, 70(3):032309, 2004. Google Scholar
  12. Elmar Böhler, Christian Glaßer, and Daniel Meister. Small bounded-error computations and completeness. Technical Report 69, Electronic Colloquium on Computational Complexity, 2003. Google Scholar
  13. Elmar Böhler, Christian Glaßer, and Daniel Meister. Error-bounded probabilistic computations between MA and AM. Journal of Computer and System Sciences, 72(6):1043-1076, 2006. Google Scholar
  14. Andrei Broder. Generating random spanning trees. In Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, pages 442-447, 1989. Google Scholar
  15. Todd Brun. Computers with closed timelike curves can solve hard problems efficiently. Foundations of Physics Letters, 16(3):245-253, 2003. Google Scholar
  16. David Deutsch. Quantum mechanics near closed timelike lines. Physical Review D, 44(10):3197-3217, 1991. Google Scholar
  17. Lance Fortnow. Complexity class of the week: BPP_path, February 2003. URL: http://blog.computationalcomplexity.org/2003/02/complexity-class-of-week-bpppath.html.
  18. John Friedman, Michael Morris, Igor Novikov, Fernando Echeverria, Gunnar Klinkhammer, Kip Thorne, and Ulvi Yurtsever. Cauchy problem in spacetimes with closed timelike curves. Physical Review D, 42(6):1915-1930, 1990. Google Scholar
  19. John Gill. Computational complexity of probabilistic Turing machines. In Proceedings of the 6th Annual ACM Symposium on Theory of Computing, pages 91-95, 1974. Google Scholar
  20. Kurt Gödel. An example of a new type of cosmological solutions of Einstein’s field equations of gravitation. Reviews of Modern Physics, 21(3):447-450, 1949. Google Scholar
  21. Yenjo Han, Lane Hemaspaandra, and Thomas Thierauf. Threshold computation and cryptographic security. SIAM Journal on Computing, 26(1):59-78, 1997. Google Scholar
  22. Yenjo Hem, Lane Hemaspaandra, and Thomas Thierauf. Threshold computation and cryptographic security. In Proceedings of the 4th Annual International Symposium on Algorithms and Computation, pages 230-239, 1993. Google Scholar
  23. Terrell Hill. Studies in irreversible thermodynamics IV: diagrammatic representation of steady state fluxes for unimolecular systems. Journal of Theoretical Biology, 10(3):442-459, 1966. Google Scholar
  24. Hans-Helmut Kohler and Eva Vollmerhaus. The frequency of cyclic processes in biological multistate systems. Journal of Mathematical Biology, 9(3):275-290, 1980. Google Scholar
  25. F. Thomson Leighton and Ronald Rivest. The Markov Chain Tree Theorem. Technical Report TM-249, Massachusetts Institute of Technology, 1983. Google Scholar
  26. Seth Lloyd, Lorenzo Maccone, Raul Garcia-Patron, Vittorio Giovannetti, and Yutaka Shikano. The quantum mechanics of time travel through post-selected teleportation. Technical Report 1007.2615, arXiv, 2010. Google Scholar
  27. László Lovász and Peter Winkler. Exact mixing in an unknown Markov chain. Electronic Journal of Combinatorics, 2:Research Paper 15, 1995. Google Scholar
  28. Piotr Pokarowski. Directed forests with application to algorithms related to Markov chains. Applicationes Mathematicae, 26(4):395-414, 1999. Google Scholar
  29. James Propp and David Wilson. How to get a perfectly random sample from a generic markov chain and generate a random spanning tree of a directed graph. Journal of Algorithms, 27(2):170-217, 1998. Google Scholar
  30. Heinz Prüfer. Neuer Beweis eines Satzes über Permutationen. Archiv der Mathematik und Physik, 27:742-744, 1918. Google Scholar
  31. A. C. Cem Say and Abuzer Yakaryılmaz. Computation with multiple CTCs of fixed length and width. Natural Computing, 11(4):579-594, 2012. Google Scholar
  32. Ronen Shaltiel and Christopher Umans. Pseudorandomness for approximate counting and sampling. Computational Complexity, 15(4):298-341, 2006. Google Scholar
  33. Yaoyun Shi. Both Toffoli and controlled-NOT need little help to do universal quantum computing. Quantum Information & Computation, 3(1):84-92, 2003. Google Scholar
  34. Bruno Shubert. A flow-graph formula for the stationary distribution of a Markov chain. Institute of Electrical and Electronics Engineers. Transactions on Systems, Man, and Cybernetics, SMC-5(5):565-566, 1975. Google Scholar
  35. Janos Simon. On some central problems in computational complexity. PhD thesis, Cornell University, 1975. TR 75-224. Google Scholar
  36. Alexander Wentzell and Mark Freidlin. On small random perturbations of dynamical systems. Russian Mathematical Surveys, 25(1):1-55, 1970. Google Scholar
  37. Wikipedia. Prüfer sequence, July 2014. URL: http://en.wikipedia.org/wiki/Prufer_sequence.
  38. David Wilson. Generating random spanning trees more quickly than the cover time. In Proceedings of the 28th Annual ACM Symposium on Theory of Computing, pages 296-303, 1996. Google Scholar
  39. Michael Wolf. Quantum channels & operations: guided tour, 2012. URL: http://www-m5.ma.tum.de/foswiki/pub/M5/Allgemeines/MichaelWolf/QChannelLecture.pdf.
  40. Abuzer Yakaryılmaz and A. C. Cem Say. Proving the power of postselection. Fundamenta Informaticae, 123(1):107-134, 2013. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact