Semiclassical Gravity Efficiently Solves NP-Complete Problems

General Relativity and Quantum Cosmology Title: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.