Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Grover search and the no-signaling principle

Published

Author(s)

Ning Bao, Bouland Adam, Stephen P. Jordan

Abstract

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 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 speedups 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.
Citation
Physical Review Letters
Volume
117

Keywords

quantum computation, Grover search, causality, black holes

Citation

Bao, N. , Adam, B. and Jordan, S. (2016), Grover search and the no-signaling principle, Physical Review Letters, [online], https://doi.org/10.1103/PhysRevLett.117.120501 (Accessed October 24, 2021)
Created September 13, 2016, Updated October 12, 2021