Quantum algorithms for discrete spacetimes

有各种迹象表明，从根本上或有效地说，时空可能是离散的。其中包括黑洞熵的有限性，圈量子引力中体积算符的离散谱，以及弦理论中的对偶性。为了捕捉这种离散底层的现象学，连续性如何在更大的尺度上出现，以及在哪里寻找预测和新的物理，人们需要对这些离散结构上的物理进行数值模拟，特别是因为洛伦兹不变性强加的随机性禁止某些分析方法1。然而，最大的挑战之一是，有趣的现象在更大的范围内出现，而不是那些通过经典计算可以计算的现象。另一方面，时空作为离散的、随机的、偏序的数学公式2，使人们有理由相信量子算法可以提供优势。具体地说，已经有许多解决图问题的量子算法提供了优势。修改这样的算法来处理离散的顺序是很自然的，同时也是新颖和具有挑战性的，因为模拟时空的随机顺序的价态(一个元素的最近邻居的数量)很大。此外，我们将放在计算机上的物理已经是离散的。由于将量子算法用于物理或化学的主要障碍之一是在量子计算机使用的离散变量/量子位中编码连续变量的精确度和实现成本的损失，因此在不需要近似的情况下更有可能获得有用的量子优势。

There are various indications that spacetime, fundamentally or effectively, may be discrete. These include the finiteness of black hole entropy, the discrete spectrum of the volume operator in loop quantum gravity and dualities in string theory. To capture the phenomenology of such a discrete substratum, how continuity emerges in larger scales, and where to look for predictions and new physics one needs to numerically simulate the physics on these discrete structures, especially since the randomness imposed by Lorentz invariance prohibits certain analytic approaches1. One of the greatest challenges, however, is that interesting phenomena arise in larger scales than those that are computationally tractable with classical computing. On the other hand, the mathematical formulation of spacetime as a discrete, random, partial order2, give grounds to believe that quantum algorithms could offer advantages. Specifically, there are already many quantum algorithms for graph problems offering advantage. Modifying such algorithms to deal with discrete orders is natural and at the same time novel and challenging, because of the large valence (number of nearest neighbours of an element) of the random orders that model spacetime. Moreover, the physics we will put on the computer is already discrete. Since one of the major obstacles in using quantum algorithms for physics or chemistry, is loss of accuracy and implementation cost of encoding continuous variables in the discrete variables/qubits that quantum computers use, the prospect of useful quantum advantage in a scenario where no approximation is needed is more likely.