标题： 量子引力计算机：不定因果结构的计算理论 显示英文标题

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

摘要： 量子引力计算机是一种特定的量子引力效应起作用的计算机。 在广义相对论中，因果结构是非固定的。 在量子理论中，非固定量受量子不确定性的影响。 因此，在量子引力理论中很可能存在不定因果结构。 这意味着特定的时间间隔是否为类时间隔没有事实可言。 我们研究了这对计算理论的影响。 经典和量子计算包括通过一系列时间步长改变计算机的状态。 这很可能是不可能的，因为如果因果结构不确定，时间步长的概念就毫无意义。 我们证明了即使在不存在确定因果结构的情况下，也可以使用某种框架（因果体形式主义）建立一个计算模型，该框架是为了在这种情况下关联数据而开发的。 物理理论对应于一个因果体，Lambda（这是一个包含不同时空区域之间因果关系信息的数学对象）。 计算机由一对{Lambda, S}给出，其中 S 是一组门。 在因果体形式主义内，我们探讨了是否存在通用量子引力计算机的可能性。 我们还检查了量子引力计算机是否比量子（或经典）计算机更强大。 特别是，我们询问不定因果结构是否可以作为计算资源。 显示英文摘要

摘要： 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.