Spacetime Quasicrystals and Computational Complexity Theory in the Road Towards Quantum Gravity
Abstract
Part I: Semiclassical Gravity Efficiently Solves NP-Complete Problems Assuming the gravitational field is classical and that it couples to quantum fields via the semiclassical Einstein field equations (EFEs), we show that the weak-field dynamics of a massive and non-relativistic qubit can in principle be used to solve an NP-complete problem in polynomial time. We attribute this vast computational power to the non-linear qubit dynamics afforded by the semiclassical EFEs. Consequently, the above two assumptions entail a violation of the Physical Extended Church--Turing Thesis, which we regard as evidence for the quantization of gravity. Part II: Spacetime Quasicrystals We generalize self-similar quasicrystals, such as the Penrose tilings, from Euclidean space to Minkowski spacetime. We construct the first examples of Lorentzian quasicrystals and identify their key novel features. We then explore possible connections to fundamental physics. First, we propose a speculative scenario in which our (3+1)D universe is embedded in a particularly symmetric (9+1)D torus 𝕋9,1, previously identified as the most symmetric toroidal compactification of the superstring. We suggest that this construction may shed light on the seesaw relation MPlMvac ≈ MEW2 between the Planck, vacuum-energy, and electroweak scales. Second, we replace the random causal sets of causal set theory with ordered, highly symmetric quasi-crystalline causal sets. We find suggestive evidence that our quasicrystals outperform Poisson random sets in the number-volume correspondence in both (1+1)D and (3+1)D, where such behaviour has been conjectured to be impossible. Finally, extending hyperuniformity from space to spacetime, we show that our (1+1)D quasicrystal is the first demonstrated example of a spacetime-hyperuniform structure.
Related
- Analysis of Polynomial Threshold Functions on Random Regular Graphs: Computational Complexity of Detecting Noisy Random Lifts
- Computational complexity of static output feedback stabilization
- The Computational Complexity of the Ungar Games on Distributive Lattices
- On the Computational Complexity of Hidden Markov Model Identification
- Computational complexity of the H-coloring problem in cubic graphs
BibTeX
@misc{mygdalas2026spacetime,
title = {{Spacetime Quasicrystals and Computational Complexity Theory in the Road Towards Quantum Gravity}},
author = {Sotirios Mygdalas},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.09855},
eprint = {2610.09855},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.09855},
}
RIS
TY - UNPB
TI - Spacetime Quasicrystals and Computational Complexity Theory in the Road Towards Quantum Gravity
AU - Sotirios Mygdalas
PY - 2026
DA - 2026/10/07
PB - arXiv
DO - 10.48550/arxiv.2610.09855
UR - https://arxiv.org/abs/2610.09855
AB - Part I: Semiclassical Gravity Efficiently Solves NP-Complete Problems Assuming the gravitational field is classical and that it couples to quantum fields via the semiclassical Einstein field equations (EFEs), we show that the weak-field dynamics of a massive and non-relativistic qubit can in principle be used to solve an NP-complete problem in polynomial time. We attribute this vast computational power to the non-linear qubit dynamics afforded by the semiclassical EFEs. Consequently, the above two assumptions entail a violation of the Physical Extended Church--Turing Thesis, which we regard as evidence for the quantization of gravity. Part II: Spacetime Quasicrystals We generalize self-similar quasicrystals, such as the Penrose tilings, from Euclidean space to Minkowski spacetime. We construct the first examples of Lorentzian quasicrystals and identify their key novel features. We then explore possible connections to fundamental physics. First, we propose a speculative scenario in which our (3+1)D universe is embedded in a particularly symmetric (9+1)D torus 𝕋^9,1, previously identified as the most symmetric toroidal compactification of the superstring. We suggest that this construction may shed light on the seesaw relation M_PlM_vac ≈ M_EW^2 between the Planck, vacuum-energy, and electroweak scales. Second, we replace the random causal sets of causal set theory with ordered, highly symmetric quasi-crystalline causal sets. We find suggestive evidence that our quasicrystals outperform Poisson random sets in the number-volume correspondence in both (1+1)D and (3+1)D, where such behaviour has been conjectured to be impossible. Finally, extending hyperuniformity from space to spacetime, we show that our (1+1)D quasicrystal is the first demonstrated example of a spacetime-hyperuniform structure.
ER -