01660nas a2200157 4500008004100000245004900041210004800090260001500138300001100153490000800164520123800172100001401410700001801424700002401442856003601466 2016 eng d00aGrover search and the no-signaling principle0 aGrover search and the nosignaling principle c2016/09/14 a1205010 v1173 a
From an information processing point of view, 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: nonunitary dynamics, non-Born-rule measurement, cloning, and postselection. We find that each model admits superluminal signaling if and only if it admits a query complexity speedup over Grover's algorithm. Furthermore, we show that the physical resources required to send a superluminal signal scale polynomially with the resources needed to speed up Grover's algorithm. Hence, one can perform a physically reasonable experiment demonstrating superluminal signaling if and only if one can perform a reasonable experiment inducing a speedup over Grover's algorithm.
1 aBao, Ning1 aBouland, Adam1 aJordan, Stephen, P. uhttp://arxiv.org/abs/1511.00657