  Two of the key properties of quantum physics are the no-signaling principle
and the Grover search lower bound. That is, despite admitting
stronger-than-classical correlations, quantum mechanics does not imply
superluminal signaling, and despite a form of exponential parallelism, quantum
mechanics does not imply polynomial-time brute force solution of NP-complete
problems. Here, we investigate the degree to which these two properties are
connected. We examine four classes of deviations from quantum mechanics, for
which we draw inspiration from the literature on the black hole information
paradox. We show that in these models, the physical resources required to send
a superluminal signal scale polynomially with the resources needed to speed up
Grover's algorithm. Hence the no-signaling principle is equivalent to the
inability to solve NP-hard problems efficiently by brute force within the
classes of theories analyzed.
