Computational tameness of classical non-causal models

DOI10.1098/RSPA.2017.0698zbMATH Open1402.81082arXiv1611.05641OpenAlexW2550835866WikidataQ51557579 ScholiaQ51557579MaRDI QIDQ4556871FDOQ4556871

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)

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.

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

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

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)

Cites Work

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

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)