{"id":"arxiv/2606.14806","url":"https://arxiv.org/abs/2606.14806","tags":["gr-qc","hep-th","quant-ph"],"score":0,"title":"Semiclassical Gravity Efficiently Solves $\\mathsf{NP}$-Complete Problems","domain":"gr-qc","source":"arxiv","authors":["Matthew Fox","Chaitanya Karamchedu","Sotirios Mygdalas"],"reviews":0,"subject":"gr-qc","summary":"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.","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-06-11","reactions":{}}