Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published September 16, 2016 | Published + Submitted + Supplemental Material
Journal Article Open

Grover search and the no-signaling principle

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.

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.

Attached Files

Published - PhysRevLett.117.120501.pdf

Submitted - 1511.00657v1.pdf

Supplemental Material - supergrover_supplemental.pdf

Files

supergrover_supplemental.pdf
Files (968.2 kB)
Name Size Download all
md5:8ecae62078721905cf69fcdc40a33952
482.4 kB Preview Download
md5:f335aac59db84f485765c50e41a6b050
317.6 kB Preview Download
md5:a548b01e67cde2547f879daa396a8ef7
168.2 kB Preview Download

Additional details

Created:
August 20, 2023
Modified:
October 18, 2023