Semiclassical Gravity Efficiently Solves $\mathsf{NP}$-Complete Problems

View PDF HTML (experimental) Abstract: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 $\mathsf{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.

Comments: 15 pages

Subjects: General Relativity and Quantum Cosmology (gr-qc); High Energy Physics - Theory (hep-th); Quantum Physics (quant-ph) Cite as: arXiv:2606.14806 [gr-qc]   (or arXiv:2606.14806v1 [gr-qc] for this version)   https://doi.org/10.48550/arXiv.2606.14806 arXiv-issued DOI via DataCite (pending registration) Submission history From: Matthew Fox [view email] [v1] Thu, 11 Jun 2026 23:42:07 UTC (17 KB)