Benincasa-Dowker-Glaser causal set actions by quantum counting

Abstract

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 $\tilde{O}(n^2)$ running-time quantum algorithm to compute the Benincasa-Dowker-Glaser action in arbitrary spacetime dimensions for causal sets with $n$ 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 $O(n^2)$-size arbitrary subset of computational basis states encoding the classical description of a causal set of interest. We then construct depth $\tilde{O}(n)$ 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.

24 pages, 5 figures; published version

References in corpus (25)

• Observation of Gravitational Waves from a Binary Black Hole Merger
• Quantum Search by Local Adiabatic Evolution
• Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity
• Halving the cost of quantum addition
• The causal set approach to quantum gravity
• Novel constructions for the fault-tolerant Toffoli gate
• Quantum Gravity Phenomenology, Lorentz Invariance and Discreteness
• Progress in Measurements of the Gravitational Bending of Radio Waves Using the VLBA
• The Scalar Curvature of a Causal Set
• Parallelizing Quantum Circuits
• High-fidelity three-qubit iToffoli gate for fixed-frequency superconducting qubits
• Causal set d'Alembertians for various dimensions
• Single-step implementation of high fidelity $n$-bit Toffoli gate
• Towards a Definition of Locality in a Manifoldlike Causal Set
• A closed form expression for the causal set d'Alembertian
• Evidence for a Phase Transition in 2D Causal Set Quantum Gravity
• The Discrete Geometry of a Small Causal Diamond
• An efficient quantum algorithm for preparation of uniform quantum superposition states
• Improving the variational quantum eigensolver using variational adiabatic quantum computing
• Suppression of non-manifold-like sets in the causal set path integral
• Polylogarithmic-depth controlled-NOT gates without ancilla qubits
• Gravity and Matter in Causal Set Theory
• Finite Size Scaling in 2d Causal Set Quantum Gravity
• Rise of conditionally clean ancillae for efficient quantum circuit constructions
• Adiabatic quantum computing with parameterized quantum circuits