Grover Search and the No-Signaling Principle

Ning Bao, Adam Bouland, and Stephen P. Jordan
Phys. Rev. Lett. 117, 120501 – Published 14 September 2016
PDFHTMLExport Citation

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.

  • Figure
  • Figure
  • Received 6 July 2016

DOI:https://doi.org/10.1103/PhysRevLett.117.120501

© 2016 American Physical Society

Physics Subject Headings (PhySH)

Gravitation, Cosmology & AstrophysicsQuantum Information, Science & Technology

Authors & Affiliations

Ning Bao

  • Institute for Quantum Information and Matter and Walter Burke Institute for Theoretical Physics, California Institute of Technology 452-48, Pasadena, California 91125, USA

Adam Bouland

  • Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, USA

Stephen P. Jordan

  • National Institute of Standards and Technology, Gaithersburg, Maryland 20899 and Joint Center for Quantum Information and Computer Science, University of Maryland, College Park, Maryland 20742, USA

Article Text (Subscription Required)

Click to Expand

Supplemental Material (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 117, Iss. 12 — 16 September 2016

Reuse & Permissions
Access Options
CHORUS

Article Available via CHORUS

Download Accepted Manuscript
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review Letters

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×