Doh! You are correct. I had been looking at a previous paper (which this new paper references). The previous paper showed that you can use any non-linearity in QM to solve NP-complete problems, and the new one shows that semi-classical gravity + QM has such a non-linearity. The earlier paper: https://arxiv.org/pdf/quant-ph/9801041
alt Hacker News
Doh! You are correct. I had been looking at a previous paper (which this new paper references). The previous paper showed that you can use any non-linearity in QM to solve NP-complete problems, and the new one shows that semi-classical gravity + QM has such a non-linearity. The earlier paper: https://arxiv.org/pdf/quant-ph/9801041