Computation with multiple CTCs of fixed length and width
Tóm tắt
We examine some variants of computation with closed timelike curves (CTCs), where various restrictions are imposed on the memory of the computer, and the information carrying capacity and range of the CTC. We give full characterizations of the classes of languages decided by polynomial time probabilistic and quantum computers that can send a single classical bit to their own past. We show that, given a time machine with constant negative delay, one can implement CTC-based computations without the need to know about the runtime beforehand. Chaining multiple instances of such fixed-length CTCs, the power of postselection can be endowed to deterministic computers, all languages in
$$\mathsf{NP} \cup \mathsf{coNP}$$
can be decided with no error in worst-case polynomial time, and all Turing-decidable languages can be decided in constant expected time. We provide proofs of the following facts for weaker models: Augmenting probabilistic computers with a single CTC leads to an improvement in language recognition power. Quantum computers under these restrictions are more powerful than their classical counterparts. Some deterministic models assisted with multiple CTCs are more powerful than those with a single CTC.
Tài liệu tham khảo
Aaronson S (2005) Quantum computing, postselection, and probabilistic polynomial-time. Proc R Soc A 461(2063):3473–3482
Aaronson S, Watrous J (2009) Closed timelike curves make quantum and classical computing equivalent. Proc R Soc A 465(2102):631–647
Adleman LM, DeMarrais J, Huang M-DA (1997) Quantum computability. SIAM J Comput 26(5):1524–1540
Ambainis A, Watrous J (2002) Two–way finite automata with quantum and classical states. Theoret Comput Sci 287(1):299–311
Bacon D (2004) Quantum computational complexity in the presence of closed timelike curves. Phys Rev A 70(032309)
Brun TA, Wilde MM (2012) Perfect state distinguishability and computational speedups with postselected closed timelike curves. Found Phys 42(3):341–361
Deutsch D (1991) Quantum mechanics near closed timelike lines. Phys Rev D 44(10):3197–3217
Dwork C, Stockmeyer L (1990) A time complexity gap for two-way probabilistic finite-state automata. SIAM J Comput 19(6):1011–1123
Freivalds R (1981) Probabilistic two-way machines. In: Proceedings of the International Symposium on Mathematical Foundations of Computer Science, pp 33–45
Gray JN, Harrison MA, Ibarra OH (1967) Two-way pushdown automata. Inf Control 11:30–70
Herzog C (1997) Pushdown automata with bounded nondeterminism and bounded ambiguity. Theoret Comput Sci 181:141–157
Hoogeboom HJ, Engelfriet J (2004) Pushdown automata. In: Formal languages and applications. (Studies in fuzziness and soft computing, vol 148), chap 6. Springer, New York, pp 117–138
Hromkovič J, Schnitger G (2010) On probabilistic pushdown automata. Inf Comput 208(8):982–995
Lloyd S, Maccone L, Garcia-Patron R, Giovannetti V, Shikano Y (2010a) The quantum mechanics of time travel through post-selected teleportation. Technical report, arXiv:1007.2615
Lloyd S, Maccone L, Garcia-Patron R, Giovannetti V, Shikano Y, Pirandola S, Rozema LA, Darabi A, Soudagar Y, Shalm LK, Steinberg AM (2010b) Closed timelike curves via post-selection: Theory and experimental demonstration. Technical report, arXiv:1005.2219
Morris MS, Thorne KS, Yurtsever U (1988) Wormholes, time machines, and the weak energy condition. Phys Rev Lett 61(13):1446–1449
Rabin MO (1963) Probabilistic automata. Inf Control 6:230–243
Shepherdson JC (1959) The reduction of two–way automata to one-way automata. IBM J Res Dev 3:198–200
Sipser M (2006) Introduction to the theory of computation, 2nd edn. Thomson Course Technology, Boston
Wotschke D (1978) Nondeterminism and boolean operations in PDA’s. J Comput Syst Sci 16(3):456–461
Yakaryılmaz A, Say ACC (2010) Succinctness of two-way probabilistic and quantum finite automata. Discr Math Theoret Comput Sci 12(4):19–40
Yakaryılmaz A, Say ACC (2011a) Proving the power of postselection. Technical report, arXiv:1111.3125 (Prepublication version of paper accepted for publication in Fundamenta Informaticae in 2012)
Yakaryılmaz A, Say ACC (2011b) Unbounded-error quantum computation with small space bounds. Inf Comput 279(6):873–892
Yao ACC (1993) Quantum circuit complexity. In FOCS1993: Proceedings of the Thirty-fourth IEEE Symposium on Foundations of Computer Science, pp 352–361