A Caltech Library Service

Grover search and the no-signaling principle

Bao, Ning and Bouland, Adam and Jordan, Stephen P. (2016) Grover search and the no-signaling principle. Physical Review Letters, 117 (12). Art. No. 120501. ISSN 0031-9007. doi:10.1103/PhysRevLett.117.120501.

[img] PDF - Published Version
See Usage Policy.

[img] PDF - Submitted Version
See Usage Policy.

[img] PDF - Supplemental Material
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription Material Paper
Bao, Ning0000-0002-3296-1039
Bouland, Adam0000-0002-8556-8337
Additional Information:© 2016 American Physical Society. Received 6 July 2016; published 14 September 2016. We thank Patrick Hayden, Daniel Harlow, David Meyer, Andrew Childs, and Debbie Leung for useful discussions. Portions of this Letter are a contribution of NIST, an agency of the U.S. government, and are not subject to U.S. copyright. This material is based upon work supported by the DuBridge Postdoctoral Fellowship, by the Institute for Quantum Information and Matter, an NSF Physics Frontiers Center (NFS Grant No. PHY-1125565) with support of the Gordon and Betty Moore Foundation (GBMF-12500028), by the U.S. Department of Energy, Office of Science, Office of High Energy Physics, under Award No. DE-SC0011632, by the NSF Graduate Research Fellowship under Grant No. 1122374, and by the NSF Alan T. Waterman award under Grant No. 1249349. N. B. and A. B. would also like to thank QuICS for their hospitality during the completion of this project.
Group:Institute for Quantum Information and Matter
Funding AgencyGrant Number
DuBridge Postdoctoral FellowshipUNSPECIFIED
Institute for Quantum Information and Matter (IQIM)UNSPECIFIED
NSF Physics Frontiers CenterUNSPECIFIED
Gordon and Betty Moore FoundationGBMF-12500028
Department of Energy (DOE)DE-SC0011632
NSF Graduate Research FellowshipDGE-1122374
Issue or Number:12
Record Number:CaltechAUTHORS:20160601-130025540
Persistent URL:
Official Citation:Grover Search and the No-Signaling Principle Ning Bao, Adam Bouland, and Stephen P. Jordan Phys. Rev. Lett. 117, 120501 (2016)
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:67546
Deposited By: Tony Diaz
Deposited On:01 Jun 2016 20:06
Last Modified:11 Nov 2021 03:50

Repository Staff Only: item control page