CaltechAUTHORS
  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. http://resolver.caltech.edu/CaltechAUTHORS:20160601-130025540

[img] PDF - Published Version
See Usage Policy.

164Kb
[img] PDF - Submitted Version
See Usage Policy.

310Kb
[img] PDF - Supplemental Material
See Usage Policy.

471Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20160601-130025540

Abstract

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
http://dx.doi.org/10.1103/PhysRevLett.117.120501DOIArticle
http://journals.aps.org/prl/abstract/10.1103/PhysRevLett.117.120501PublisherArticle
http://journals.aps.org/prl/supplemental/10.1103/PhysRevLett.117.120501PublisherSupplemental Material
https://arxiv.org/abs/1511.00657arXivDiscussion Paper
ORCID:
AuthorORCID
Bao, Ning0000-0002-3296-1039
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:IQIM, Institute for Quantum Information and Matter
Funders:
Funding AgencyGrant Number
DuBridge Postdoctoral FellowshipUNSPECIFIED
Institute for Quantum Information and Matter (IQIM)UNSPECIFIED
NSF Physics Frontiers CenterUNSPECIFIED
NSFPHY-1125565
Gordon and Betty Moore FoundationGBMF-12500028
Department of Energy (DOE)DE-SC0011632
NSF Graduate Research FellowshipDGE-1122374
Record Number:CaltechAUTHORS:20160601-130025540
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20160601-130025540
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
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:01 Jun 2016 20:06
Last Modified:09 Nov 2016 21:04

Repository Staff Only: item control page