Part I: Semiclassical Gravity Efficiently Solves $\mathsf{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 $\mathsf{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 $\mathbb{T}^{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_{\rm Pl}M_{\rm vac} \approx M_{\rm 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.
Comments
PhD Thesis, University of Waterloo, September 2026 (342 pages)
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 T9,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.
Quantum computers are expected to revolutionize our ability to process information. The advancement from classical to quantum computing is a product of our advancement from classical to quantum physics -- the more our understanding of the universe grows, so does our ability to use it for computation. A natural question that arises is, what will physics allow in the future? Can more advanced theories of physics increase our computational power, beyond quantum computing? An active field of research in physics studies theoretical phenomena outside the scope of explainable quantum mechanics, that form when attempting to combine Quantum Mechanics (QM) with General Relativity (GR) into a unified theory of Quantum Gravity (QG). QG is known to present the possibility of a quantum superposition of causal structure and event orderings. In the literature of quantum information theory, this translates to a superposition of unitary evolution orders. In this work we show a first example of a natural computational model based on QG, that provides an exponential speedup over standard quantum computation (under standard hardness assumptions). We define a model and complexity measure for a quantum computer that has the ability to generate a superposition of unitary evolution orders, and show that such computer is able to solve in polynomial time two of the fundamental problems in computer science: The Graph Isomorphism Problem (GI) and the Gap Closest Vector Problem (GapCVP), with gap O(nn). These problems are believed by experts to be hard to solve for a regular quantum computer. Interestingly, our model does not seem overpowered, and we found no obvious way to solve entire complexity classes that are considered hard in computer science, like the classes NP and SZK.
We propose a novel operator-based formulation of quantum gravity grounded in two foundational principles: a discrete causal lattice and algebraic microcausality. Departing from traditional continuum approaches and wavefunction-based quantum mechanics, this framework models spacetime and matter as emergent phenomena arising from the algebraic structure of displacement operators. In this first part of a two-part series, we construct the foundational framework and demonstrate how key features of quantum mechanics—such as the uncertainty principle, de Broglie relations, and entanglement—emerge naturally without invoking wavefunctions, path integrals, or metric-based geometry. Operator non-commutativity on the causal lattice gives rise to a self-consistent quantum structure with natural ultraviolet finiteness, intrinsic time directionality, and a microcausal interpretation of measurement. This foundational part lays the groundwork for gravitational dynamics, cosmology, and the grand unification principles of gravity and the Standard Model to be explored in the sequel to quantum gravity part II.
In this thesis, we lay out the goal, and a broad outline, for a program that takes quantum mechanics in its minimal form to be the fundamental ontology of the universe. Everything else, including features like space-time, matter and gravity associated with classical reality, are emergent from these minimal quantum elements. We argue that the Hilbert space of quantum gravity is locally finite-dimensional, in sharp contrast to that of conventional field theory, which could have observable consequences for gravity. We also treat time and space on an equal footing in Hilbert space in a reparametrization invariant setting and show how symmetry transformations, both global and local, can be treated as unitary basis changes. Motivated by the finite-dimensional context, we use Generalized Pauli Operators as finite-dimensional conjugate variables and define a purely Hilbert space notion of locality based on the spread induced by conjugate operators which we call "Operator Collimation." We study deviations in the spectrum of physical theories, particularly the quantum harmonic oscillator, induced by finite-dimensional effects, and show that by including a black hole-based bound in a lattice field theory, the quantum contribution to the vacuum energy can be suppressed by multiple orders of magnitude. We then show how one can recover subsystem structure in Hilbert space which exhibits emergent quasi-classical dynamics. We explicitly connect classical features (such as pointer states of the system being relatively robust to entanglement production under environmental monitoring and the existence of approximately classical trajectories) with features of the Hamiltonian. We develop an in-principle algorithm based on extremization of an entropic quantity that can sift through different factorizations of Hilbert space to pick out the one with manifest classical dynamics. This discussion is then extended to include direct sum decompositions and their compatibility with Hamiltonian evolution. Following this, we study quantum coarse-graining and state-reduction maps in a broad context. In addition to developing a first-principle quantum coarse-graining algorithm based on principle component analysis, we construct more general state-reduction maps specified by a restricted set of observables which do not span the full algebra (as could be the case of limited access in a laboratory or in various situations in quantum gravity). We also present a general, not inherently numeric, algorithm for finding irreducible representations of matrix algebras. Throughout the thesis, we discuss implications of our work in the broader goal of understanding quantum gravity from minimal elements in quantum mechanics.
The synthesis of quantum and gravitational physics is sought through a finite, realistic, locally causal theory where gravity plays a vital role not only during decoherent measurement but also during non-decoherent unitary evolution. Invariant set theory is built on geometric properties of a compact fractal-like subset IU of cosmological state space on which the universe is assumed to evolve and from which the laws of physics are assumed to derive. Consistent with the primacy of IU, a non-Euclidean (and hence non-classical) state-space metric gp is defined, related to the p-adic metric of number theory where p is a large but finite Pythagorean prime. Uncertain states on IU are described using complex Hilbert states, but only if their squared amplitudes are rational and corresponding complex phase angles are rational multiples of 2π. Such Hilbert states are necessarily gp-distant from states with either irrational squared amplitudes or irrational phase angles. The gappy fractal nature of IU accounts for quantum complementarity and is characterised numerically by a generic number-theoretic incommensurateness between rational angles and rational cosines of angles. The Bell inequality, whose violation would be inconsistent with local realism, is shown to be gp-distant from all forms of the inequality that are violated in any finite-precision experiment. The delayed-choice paradox is resolved through the computational irreducibility of IU. The Schrödinger and Dirac equations describe evolution on IU in the singular limit at p=∞. By contrast, an extension of the Einstein field equations on IU is proposed which reduces smoothly to general relativity as p→∞. Novel proposals for the dark universe and the elimination of classical space-time singularities are given and experimental implications outlined.
Assuming the gravitational field is classical and that it couples to quantum fields via the semiclassical Einstein field equations, 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 dynamics afforded by the semiclassical Einstein field equations. 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.
The Problem of Time — the apparent incompatibility between quantum mechanics' time parameter t and general relativity's proper time τ — has been treated as a fundamental obstacle to quantum gravity. I argue that this is a level-confusion: both theories define time within their own entity-theoretic frameworks, generating an apparent opposition that disappears when time is relocated to a meta-structural layer. Drawing on the meta-level temporal structure T_SDT := (V_G, ≺) (Zeng 2026), the paper formalizes QM and GR time as two projections of a single Universal Time Formula, parameterized by entity-theoretic tokens. Four token specializations recover the corresponding time concepts. A Bridge Theorem establishes mutual compatibility of all token projections. A bidirectional QM-GR channel is constructed (forward: GR geometry → QM phase; reverse: discrete chain-pair → Lorentzian spacetime), composing into a self-consistent closed loop. Three further results move beyond dissolution toward unification. First, a Madelung-bridge construction derives the Schrödinger equation — Hilbert space, unitarity, Hamiltonian, quantum potential, Born rule — from the determination-graph axioms together with the continuum embedding (CL1), with no independent QM input; the derivation extends to Klein-Gordon. Second, a Planck-scale token μ = t_P / |A_{v'}| is constructed on the discrete 𝒢_D, where |A_{v'}| is the admissibility cardinality; under CL1, this single step-measure recovers QM (|A| ≫ 1) and GR (|A| = 1) as its two continuum limits, with Einstein's equation proved in the classical regime (|A| = 1) via a two-stage argument (Benincasa-Dowker action convergence + standard scalar-tensor variation). The exact quantum-gravitational correction is derived as a scalar-tensor equation with φ = 1/|A|. Third, the discrete determination graph without continuum embedding constitutes a self-contained Planck-scale quantum gravity theory: it has a well-defined path integral, a finite-dimensional S-matrix (unitary in the κ = 0 sector, isometric in the κ > 0 sector; no UV divergences), preserves information across black hole horizons, resolves singularities, derives the Past Hypothesis, and provides structural origins for gauge symmetry, Hawking radiation, spectral dimensionality, and the spin-statistics connection. The Problem of Time is not merely dissolved — it is replaced by a constructive framework in which QM and GR are unified as two limits of a single discrete structure.