Nonlocality and its connections to entanglement are fundamental features of quantum mechanics that have found numerous applications in quantum information science. A set of correlations is said to be nonlocal if it cannot be reproduced by spacelike-separated parties sharing randomness and performing local operations. An important practical consideration is that the runtime of the parties has to be shorter than the time it takes light to travel between them. One way to model this restriction is to assume that the parties are computationally bounded. We therefore initiate the study of nonlocality under computational assumptions and derive the following results: (a) We define the set
NeL (not-efficiently-local) as consisting of all bipartite states whose correlations arising from local measurements cannot be reproduced with shared randomness and \emph{polynomial-time} local operations. (b) Under the assumption that the Learning With Errors problem cannot be solved in \emph{quantum} polynomial-time, we show that
NeL=ENT, where
ENT is the set of \emph{all} bipartite entangled states (pure and mixed). This is in contrast to the standard notion of nonlocality where it is known that some entangled states, e.g. Werner states, are local. In essence, we show that there exist (efficient) local measurements producing correlations that cannot be reproduced through shared randomness and quantum polynomial-time computation. (c) We prove that if
NeL=ENT unconditionally, then
BQP=PP. In other words, the ability to certify all bipartite entangled states against computationally bounded adversaries gives a non-trivial separation of complexity classes. (d) Using (c), we show that a certain natural class of 1-round delegated quantum computation protocols that are sound against
PP provers cannot exist.
A standard approach to quantifying resources is to determine which operations on the resources are freely available, and to deduce the partial order over resources that is induced by the relation of convertibility under the free operations. If the resource of interest is the nonclassicality of the correlations embodied in a quantum state, i.e., e n t a n g l e m e n t , then the common assumption is that the appropriate choice of free operations is Local Operations and Classical Communication (LOCC). We here advocate for the study of a different choice of free operations, namely, Local Operations and Shared Randomness (LOSR), and demonstrate its utility in understanding the interplay between the entanglement of states and the nonlocality of the correlations in Bell experiments. Specifically, we show that the LOSR paradigm (i) provides a resolution of the anomalies of nonlocality , wherein partially entangled states exhibit more nonlocality than maximally entangled states, (ii) entails new notions of genuine multipartite entanglement and nonlocality that are free of the pathological features of the conventional notions, and (iii) makes possible a resource-theoretic account of the self-testing of entangled states which generalizes and simplifies prior results. Along the way, we derive some fundamental results concerning the necessary and sufficient conditions for convertibility between pure entangled states under LOSR and highlight some of their consequences, such as the impossibility of catalysis for bipartite pure states. The resource-theoretic perspective also clarifies why it is neither surprising nor problematic that there are mixed entangled states which do not violate any Bell inequality. Our results motivate the study of LOSR-entanglement as a new branch of entanglement theory.
The statistics of local measurements performed on certain entangled states can be reproduced using a local hidden variable (LHV) model. While all known models make use of an infinite amount of shared randomness, we show that essentially all entangled states admitting a LHV model can be simulated with finite shared randomness. Our most economical model simulates noisy two-qubit Werner states using only log_{2}(12)≃3.58 bits of shared randomness. We also discuss the case of positive operator valued measures, and the simulation of nonlocal states with finite shared randomness and finite communication. Our work represents a first step towards quantifying the cost of LHV models for entangled quantum states.