Grover search and the no-signaling principle
- Creators
-
Bao, Ning
-
Bouland, Adam
- Jordan, Stephen P.
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
Additional details
- Eprint ID
- 67546
- Resolver ID
- CaltechAUTHORS:20160601-130025540
- DuBridge Postdoctoral Fellowship
- Institute for Quantum Information and Matter (IQIM)
- NSF Physics Frontiers Center
- NSF
- PHY-1125565
- Gordon and Betty Moore Foundation
- GBMF-12500028
- Department of Energy (DOE)
- DE-SC0011632
- NSF Graduate Research Fellowship
- DGE-1122374
- Created
-
2016-06-01Created from EPrint's datestamp field
- Updated
-
2021-11-11Created from EPrint's last_modified field
- Caltech groups
- Institute for Quantum Information and Matter