Benincasa-Dowker-Glaser causal set actions by quantum counting

Causal set theory is an approach to quantum gravity in which spacetime is fundamentally discrete while retaining local Lorentz invariance. The Benincasa-Dowker-Glaser action is the causal set equivalent to the Einstein-Hilbert action underpinning Einstein's general theory of relativity. We present a ˜𝑂⁡(𝑛2) running-time quantum algorithm to compute the Benincasa-Dowker-Glaser action in arbitrary spacetime dimensions for causal sets with 𝑛 elements, which is asymptotically optimal and offers a polynomial speedup compared to all known classical or quantum algorithms. To do this, we prepare a uniform superposition over an 𝑂⁡(𝑛2)-size arbitrary subset of computational basis states encoding the classical description of a causal set of interest. We then construct depth ˜𝑂(𝑛)-depth oracle circuits testing for different discrete volumes between pairs of causal set elements. Repeatedly performing a two-stage variant of quantum counting using these oracles yields the desired algorithm.