Quantum gravity computers: On the theory of computation with indefinite causal structure

Abstract

A quantum gravity computer is one for which the particular effects of quantum gravity are relevant. In general relativity, causal structure is non-fixed. In quantum theory non-fixed quantities are subject to quantum uncertainty. It is therefore likely that, in a theory of quantum gravity, we will have indefinite causal structure. This means that there will be no matter of fact as to whether a particular interval is timelike or not. We study the implications of this for the theory of computation. Classical and quantum computations consist in ivolving the state of the computer through a sequence of time steps. This will, most likely, not be possible for a quantum gravity computer because the notion of a time step makes no sense if we have indefinite causal structure. We show that it is possible to set up a model for computation even in the absence of definite causal structure by using a certain framework (the causaloid formalism) that was developed for the purpose of correlating data taken in this type of situation. Corresponding to a physical theory is a causaloid, Lambda (this is a mathematical object containing information about the causal connections between different spacetime regions). A computer is given by the pair {Lambda, S} where S is a set of gates. Working within the causaloid formalism, we explore the question of whether universal quantum gravity computers are possible. We also examine whether a quantum gravity computer might be more powerful than a quantum (or classical) computer. In particular, we ask whether indefinite causal structure can be used as a computational resource.

24 pages. For proceedings of "Quantum Reality, Relativistic Causality, and Closing the Epistemic Circle: An International Conference in Honour of Abner Shimony"

References in corpus (4)

• Towards Quantum Gravity: A Framework for Probabilistic Theories with Non-Fixed Causal Structure
• NP-complete Problems and Physical Reality
• An invitation to loop quantum gravity
• Probability Theories with Dynamic Causal Structure: A New Framework for Quantum Gravity

Cited by in corpus (40)

• Experimental Superposition of Orders of Quantum Gates
• Experimental Verification of an Indefinite Causal Order
• Causal and causally separable processes
• Quantum Shannon theory with superpositions of trajectories
• Communication through quantum-controlled noise
• Time-delocalized quantum subsystems and operations: on the existence of processes with indefinite causal structure in quantum mechanics
• Optimal quantum networks and one-shot entropies
• The Operator Tensor Formulation of Quantum Theory
• The space of logically consistent classical processes without causal order
• Functional Quantum Computing: An Optical Approach
• Operational quantum theory without predefined time
• Quantum-coherent mixtures of causal relations
• Quantum Theory, namely the pure and reversible theory of information
• Experimental Aspects of Indefinite Causal Order in Quantum Mechanics
• Bounding quantum correlations with indefinite causal order
• Causal Boxes: Quantum Information-Processing Systems Closed under Composition
• Observer-dependent locality of quantum events
• Perfect signaling among three parties violating predefined causal order
• Causal structure in the presence of sectorial constraints, with application to the quantum switch
• Analysing causal structures with entropy
• Noncausal Page-Wootters circuits
• Higher-order Process Matrix Tomography of a passively-stable Quantum SWITCH
• Quantum correlations in time
• Correlation Measure Equivalence in Dynamic Causal Structures of Quantum Gravity
• Experimentally demonstrating indefinite causal order algorithms to solve the generalized Deutsch's problem
• Classical communication through quantum causal structures
• Composition rules for quantum processes: a no-go theorem
• Practical computational advantage from the quantum switch on a generalized family of promise problems
• Quantum to classical transitions in causal relations
• Revisiting dynamics of quantum causal structures -- when can causal order evolve?
• Quantum Gravity: Has Spacetime Quantum Properties?
• Quantum Time and the Time-Dilation induced Interaction Transfer mechanism
• Smooth Entropy Transfer of Quantum Gravity Information Processing
• Empirical adequacy of the time operator canonically conjugate to a Hamiltonian generating translations
• Reality, Causality, and Quantum Theory
• Quantum Correlations in Space-Time: Foundations and Applications
• Tripartite non-classical correlations without backwards in time signalling
• String Theory - Nomological Unification and the Epicycles of the Quantum Field Theory Paradigm
• Quantum collapse as undecidable proposition in an Everettian multiverse
• Ruling out the class of statistical processes involving two noninteracting identical particles in two modes