Computational tameness of classical non-causal models
arXiv:1611.05641 · doi:10.1098/rspa.2017.0698
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~. 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~ problems, unless~, which lets their existence in nature appear less implausible. This result gives a new characterization of~ in terms of fixed points.
arXiv comment7 pages, 3 figures, 1 algorithm, revised
References in corpus (33)
- Quantum correlations with no causal order
- In defense of the epistemic view of quantum states: a toy theory
- Quantum computations without definite causal structure
- Experimental Superposition of Orders of Quantum Gates
- Computational advantage from quantum-controlled ordering of gates
- Perfect discrimination of no-signalling channels via quantum superposition of causal structures
- Nonlinear quantum mechanics implies polynomial-time solution for NP-complete and #P problems
- Exponential Communication Complexity Advantage from Quantum Superposition of the Direction of Communication
- The completeness of quantum theory for predicting measurement outcomes
- Introduction to the book "Quantum Theory: Informational Foundations and Foils"
- Quantum from principles
- Quasi-quantization: classical statistical theories with an epistemic restriction
- The Interpretation of Quantum Mechanics: Many Worlds or Many Words?
- Closed timelike curves via post-selection: theory and experimental demonstration
- Quantum superposition of the order of parties as a communication resource
- The quantum mechanics of time travel through post-selected teleportation
- The simplest causal inequalities and their violation
- Quantum computation with programmable connections between gates
- Can closed timelike curves or nonlinear quantum mechanics improve quantum state discrimination or help solve hard problems?
- Quantum Computational Complexity in the Presence of Closed Timelike Curves
- The space of logically consistent classical processes without causal order
- Computers with closed timelike curves can solve hard problems
- Effective Quantum Time Travel
- Relativistic quantum information and time machines
- Perfect signaling among three parties violating predefined causal order
- Treating Time Travel Quantum Mechanically
- Reversible time travel with freedom of choice
- Non-causal computation
- Closed Timelike Curves Make Quantum and Classical Computing Equivalent
- Revisiting consistency conditions for quantum states of systems on closed timelike curves: an epistemic perspective
- Computability Theory of Closed Timelike Curves
- Quantum mechanics and the time travel paradox
- Causality Violation and Nonlinear Quantum Mechanics
Cited by in corpus (12)
- 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
- Causality - Complexity - Consistency: Can Space-Time Be Based on Logic and Computation?
- Composition rules for quantum processes: a no-go theorem
- Equivalence of Grandfather and Information Antinomy Under Intervention
- An Atemporal Model of Physical Complexity
- Flow of dynamical causal structures with an application to correlations
- Classical and Quantum Query Complexity of Boolean Functions under Indefinite Causal Order