Semiclassical gravity is the best we can currently do for a theory of gravity without invoking speculative ideas that are currently untestable. If the paper holds up (I haven't read it), then there are several possibilities:

1. Maybe P = NP, and semiclassical gravity isn't special. 2. Maybe P = NP, and the way we'll prove it is finding an efficient way to simulate semiclassical gravity. 3. P = NP is a hypothesis about traditional theories of computation, but they don't rule out that we can build a special machine that solves them. There's a stronger hypothesis, the extended Church-Turing thesis (ECTT), that says this is impossible. Maybe the extended Church-Turing thesis is wrong, and this is how we'll show it. 4. If ECTT thesis is right, then maybe we can conduct an experiment where semiclassical gravity fails. This gives us a clue to new physics. 5. If we can't eventually conduct an experiment, then at least we learn about a new angle on complexity -- problems that can be efficiently solved this way but not by a deterministic Turing machine.

Both quantum mechanics and general relativity are thought to satisfy the ECTT, so the fact that our most experimentally successful combination of the two doesn't is of some interest. (Semiclassical gravity is thought to fail eventually, but in a way that's out of reach of current experiments.)