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.

Minor edits and clarifications. Results unchanged. 33 pages

References in corpus (8)

• NP-complete Problems and Physical Reality
• A Simple Proof that Toffoli and Hadamard are Quantum Universal
• Can closed timelike curves or nonlinear quantum mechanics improve quantum state discrimination or help solve hard problems?
• Violations of the Born rule in cool state-dependent horizons
• Aspects of the Papadodimas-Raju Proposal for the Black Hole Interior
• Optimal state discrimination and unstructured search in nonlinear quantum mechanics
• Closed Timelike Curves Make Quantum and Classical Computing Equivalent
• Completeness is Unnecessary for Fast Nonlinear Quantum Search

Cited by in corpus (12)

• Deriving Grover's lower bound from simple physical principles
• Branches of the Black Hole Wave Function Need Not Contain Firewalls
• Fast optimization algorithms and the cosmological constant
• Oracles and query lower bounds in generalised probabilistic theories
• Any modification of the Born rule leads to a violation of the purification and local tomography principles
• Computational pseudorandomness, the wormhole growth paradox, and constraints on the AdS/CFT duality
• Complementarity and the unitarity of the black hole $S$-matrix
• Experimental limit on non-linear state-dependent terms in quantum theory
• Black holes as Andreev reflecting mirrors
• Microstate Distinguishability, Quantum Complexity, and the Eigenstate Thermalization Hypothesis
• Information-Theoretic Meaning of Quantum Information Flow and Its Applications to Amplitude Amplification Algorithms
• $T$-depth-optimized Quantum Search with Quantum Data-access Machine