Grover Search and the No-Signaling Principle
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 do...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
American Physical Society
2016
|
| Online Access: | http://hdl.handle.net/1721.1/105886 https://orcid.org/0000-0002-8556-8337 |
| _version_ | 1826211212688359424 |
|---|---|
| author | Bao, Ning Jordan, Stephen P. Bouland, Adam Michael |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Bao, Ning Jordan, Stephen P. Bouland, Adam Michael |
| author_sort | Bao, Ning |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T15:02:22Z |
| format | Article |
| id | mit-1721.1/105886 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T15:02:22Z |
| publishDate | 2016 |
| publisher | American Physical Society |
| record_format | dspace |
| spelling | mit-1721.1/1058862022-09-29T12:15:12Z Grover Search and the No-Signaling Principle Bao, Ning Jordan, Stephen P. Bouland, Adam Michael Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Bouland, Adam Michael 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. National Science Foundation (U.S.) (Alan T. Waterman Award Grant 1249349) DuBridge Postdoctoral Fellowship National Science Foundation (U.S.) (Physics Frontiers Center, Institute for Quantum Information and Matter. Grant PHY-1125565) Gordon and Betty Moore Foundation (Grant GBMF-12500028) United States. Dept. of Energy. Office of High Energy Physics (Award DE-SC0011632) National Science Foundation (U.S.). Graduate Research Fellowship Program (Grant 1122374) 2016-12-20T14:45:50Z 2016-12-20T14:45:50Z 2016-09 2016-07 2016-09-14T22:00:14Z Article http://purl.org/eprint/type/JournalArticle 0031-9007 1079-7114 http://hdl.handle.net/1721.1/105886 Bao, Ning, Adam Bouland, and Stephen P. Jordan. “Grover Search and the No-Signaling Principle.” Physical Review Letters 117.12 (2016): n. pag. © 2016 American Physical Society https://orcid.org/0000-0002-8556-8337 en http://dx.doi.org/10.1103/PhysRevLett.117.120501 Physical Review Letters Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. American Physical Society application/pdf American Physical Society American Physical Society |
| spellingShingle | Bao, Ning Jordan, Stephen P. Bouland, Adam Michael Grover Search and the No-Signaling Principle |
| title | Grover Search and the No-Signaling Principle |
| title_full | Grover Search and the No-Signaling Principle |
| title_fullStr | Grover Search and the No-Signaling Principle |
| title_full_unstemmed | Grover Search and the No-Signaling Principle |
| title_short | Grover Search and the No-Signaling Principle |
| title_sort | grover search and the no signaling principle |
| url | http://hdl.handle.net/1721.1/105886 https://orcid.org/0000-0002-8556-8337 |
| work_keys_str_mv | AT baoning groversearchandthenosignalingprinciple AT jordanstephenp groversearchandthenosignalingprinciple AT boulandadammichael groversearchandthenosignalingprinciple |