Quantum algorithms for discrete spacetimes

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

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.