Computational tameness of classical non-causal models

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~$\mathrm{UP}\cap \mathrm{coUP}$. 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~$\mathsf{NP}-\mathsf{complete}$ problems, unless~$\mathrm{NP}=\mathrm{UP}\cap \mathrm{coUP}=\mathrm{coNP}$, which lets their existence in nature appear less implausible. This result gives a new characterization of~$\mathrm{UP}\cap \mathrm{coUP}$ in terms of fixed points.

7 pages, 3 figures, 1 algorithm, revised

References in corpus (9)

• Exponential Communication Complexity Advantage from Quantum Superposition of the Direction of Communication
• Introduction to the book "Quantum Theory: Informational Foundations and Foils"
• Closed timelike curves via post-selection: theory and experimental demonstration
• The quantum mechanics of time travel through post-selected teleportation
• Can closed timelike curves or nonlinear quantum mechanics improve quantum state discrimination or help solve hard problems?
• Reversible time travel with freedom of choice
• Closed Timelike Curves Make Quantum and Classical Computing Equivalent
• Computability Theory of Closed Timelike Curves
• Quantum mechanics and the time travel paradox

Cited by in corpus (11)

• Experimentally feasible computational advantage from quantum superposition of gate orders
• Quantum computation with indefinite causal structures
• Observer-dependent locality of quantum events
• Reversible time travel with freedom of choice
• Unlimited non-causal correlations and their relation to non-locality
• Reassessing the computational advantage of quantum-controlled ordering of gates
• Composition rules for quantum processes: a no-go theorem
• Equivalence of Grandfather and Information Antinomy Under Intervention
• An Atemporal Model of Physical Complexity
• Classical and Quantum Query Complexity of Boolean Functions under Indefinite Causal Order
• Flow of dynamical causal structures with an application to correlations