Computational tameness of classical non-causal models

DOI10.1098/RSPA.2017.0698MaRDI QIDQ4556871zbMATH OpenOpenAlexWikidataFDO

Authors Ämin Baumeler, S. Wolf

Publication date 28 November 2018

Published in Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1611.05641

zbMATH Keywords

causalitycomplexity theoryclosed timelike curvesnon-causal computationunambiguous polynomial time

Mathematics Subject Classification ID

Quantum computation (81P68) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Abstract: We show that the computational power of the non-causal circuit model, i.e., the circuit model where the assumption of a global causal order is replaced by the assumption of logical consistency, is completely characterized by the complexity class~$operatornamemathsfUPcapoperatornamemathsfcoUP$. An example of a problem in that class is factorization. Our result implies that classical deterministic closed timelike curves (CTCs) cannot efficiently solve problems that lie outside of that class. Thus, in stark contrast to other CTC models, these CTCs cannot efficiently solve~$operatornamemathsfNP-complete$ problems, unless~$operatornamemathsfNP=operatornamemathsfUPcapoperatornamemathsfcoUP=operatornamemathsfcoNP$, which lets their existence in nature appear less implausible. This result gives a new characterization of~$operatornamemathsfUPcapoperatornamemathsfcoUP$ in terms of fixed points.

Recommendations

• Closed timelike curves make quantum and classical computing equivalent
• Computation with multiple CTCs of fixed length and width
• One time-traveling bit is as good as logarithmically many
• Computation with Narrow CTCs
• Device-independent test of causal order and relations to fixed-points

Cites work

• scientific article; zbMATH DE number 3814972 (Why is no real title available?)
• An Example of a New Type of Cosmological Solutions of Einstein's Field Equations of Gravitation
• Causality. Models, reasoning, and inference
• Closed timelike curves make quantum and classical computing equivalent
• Computational Complexity
• Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
• Empty space-times admitting a three parameter group of motions
• Exact space-times in Einstein's general relativity.
• Gravitational Field of a Spinning Mass as an Example of Algebraically Special Metrics
• On the Complexity of Nash Equilibria and Other Fixed Points
• On total functions, existence theorems and computational complexity
• One-way permutations and self-witnessing languages
• PRIMES is in P
• Quantum computation with programmable connections between gates
• Quantum computing, postselection, and probabilistic polynomial-time
• Quantum theory: informational foundations and foils
• Relative complexity of checking and evaluating
• Revisiting consistency conditions for quantum states of systems on closed timelike curves: an epistemic perspective
• Self-witnessing polynomial-time complexity and prime factorization
• The polynomial-time hierarchy
• The simplest causal inequalities and their violation
• The space of logically consistent classical processes without causal order
• Threshold Computation and Cryptographic Security
• Time travel: Deutsch vs. teleportation
• Weinberg’s nonlinear quantum mechanics and the Einstein-Podolsky-Rosen paradox

Cited in

(5)

• Reversible time travel with freedom of choice
• Equivalence of grandfather and information antinomy under intervention
• Closed timelike curves make quantum and classical computing equivalent
• Device-independent test of causal order and relations to fixed-points
• Physical computational complexity and first-order logic

This page was built for publication: Computational tameness of classical non-causal models

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