Grover search and the no-signaling principle
arXiv:1511.00657 · doi:10.1103/PhysRevLett.117.120501
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.
arXiv commentMinor edits and clarifications. Results unchanged. 33 pages
References in corpus (25)
- Strengths and Weaknesses of Quantum Computing
- Black Holes: Complementarity or Firewalls?
- Integration with respect to the Haar measure on unitary, orthogonal and symplectic group
- Grover's quantum searching algorithm is optimal
- Quantum Algorithms for Quantum Field Theories
- Jerusalem Lectures on Black Holes and Quantum Information
- Better Late than Never: Information Retrieval from Black Holes
- State-Dependent Bulk-Boundary Maps and Black Hole Complementarity
- The black hole final state
- Simulation of topological field theories by quantum computers
- Nonlinear quantum mechanics implies polynomial-time solution for NP-complete and #P problems
- Quantum Computation vs. Firewalls
- NP-complete Problems and Physical Reality
- A Simple Proof that Toffoli and Hadamard are Quantum Universal
- Comment on "The black hole final state"
- 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
- Computers with closed timelike curves can solve hard problems
- Aspects of the Papadodimas-Raju Proposal for the Black Hole Interior
- No-signaling Principle Can Determine Optimal Quantum State Discrimination
- Optimal state discrimination and unstructured search in nonlinear quantum mechanics
- Quantum Search with General Nonlinearities
- Nonlinear Quantum Search Using the Gross-Pitaevskii Equation
- 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 -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
- -depth-optimized Quantum Search with Quantum Data-access Machine