Computation with multiple CTCs of fixed length and width

DOI10.1007/S11047-012-9337-6MaRDI QIDQ256423zbMATH OpenOpenAlexFDO

Authors A. C. Cem Say, Abuzer Yakaryılmaz

Publication date 9 March 2016

Published in Natural Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11047-012-9337-6

zbMATH Keywords

closed timelike curve (CTC)CTC-based computationdeterministic pushdown automatalimited nondeterminismpolynomial-time probabilistic and quantum algorithmspostselectionprobabilistic automataquantum automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Recommendations

• Computation with Narrow CTCs
• One time-traveling bit is as good as logarithmically many
• Closed timelike curves make quantum and classical computing equivalent
• Perfect state distinguishability and computational speedups with postselected closed timelike curves
• Simulations of closed timelike curves

Cites work

• scientific article; zbMATH DE number 5595162 (Why is no real title available?)
• scientific article; zbMATH DE number 3765145 (Why is no real title available?)
• scientific article; zbMATH DE number 2150277 (Why is no real title available?)
• scientific article; zbMATH DE number 3254906 (Why is no real title available?)
• A Time Complexity Gap for Two-Way Probabilistic Finite-State Automata
• Closed timelike curves make quantum and classical computing equivalent
• Nondeterminism and Boolean operations in pda's
• On probabilistic pushdown automata
• Perfect state distinguishability and computational speedups with postselected closed timelike curves
• Probabilistic automata
• Proving the power of postselection
• Pushdown automata with bounded nondeterminism and bounded ambiguity
• Quantum Computability
• Quantum computing, postselection, and probabilistic polynomial-time
• Succinctness of two-way probabilistic and quantum finite automata
• Two-way finite automata with quantum and classical states.
• Two-way pushdown automata
• Unbounded-error quantum computation with small space bounds

Cited in

(8)

• The weakness of CTC qubits and the power of approximate counting
• Simulations of closed timelike curves
• Revisiting integer factorization using closed timelike curves
• Closed timelike curves make quantum and classical computing equivalent
• Computation with Narrow CTCs
• Computational tameness of classical non-causal models
• One time-traveling bit is as good as logarithmically many
• Perfect state distinguishability and computational speedups with postselected closed timelike curves

This page was built for publication: Computation with multiple CTCs of fixed length and width

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q256423)