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

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.