# All Entangled Quantum States Are Nonlocal

It is a fact that the outcomes of measurements performed on spatially separated (i.e., noncommunicating) quantum systems sometimes exhibit correlations, which cannot be explained classically, in terms of information shared beforehand. Such correlations, called nonlocal, are revealed by the violation of a suitable Bell inequality [1,2]. Another peculiarly nonclassical feature of quantum theory is the existence of quantum entanglement, i.e., the property possessed by composite quantum systems whose joint state cannot be written in product form (or, more generally, as a mixture of states in product form). Even if nonlocality and entanglement are indeed intimately related, it is nowadays widely accepted that they are in fact two well distinct concepts: first of all, because there exist entangled quantum states which behave “locally” in many aspects [3,4]; second, because quantum states that appear to be “maximally nonlocal” are generally not the “maximally entangled” ones [5]. Such a quantitative distinction is made clear by looking upon nonlocality and entanglement as two inequivalent resources.

In the resource theory of quantum entanglement, the operational paradigm is commonly known as local operations and classical communication (LOCC) [6]: separated parties are only allowed to exchange classical messages, while quantum operations (i.e., preparation of quantum states, quantum measurements, etc.) can only happen locally. In particular, quantum states cannot be directly sent across separated locations. The LOCC paradigm, originally formulated in order to describe the “distant laboratories model”, is nowadays generally accepted as the natural operational paradigm for studying quantum entanglement as a resource [7]: indeed, classical communication cannot generate entanglement, which hence becomes a physical resource that can be processed, but not created.

In a resource theory of nonlocality, on the other hand, the LOCC paradigm seems unjustified: even mere classical communication constitutes in fact a nonlocal resource and, as such, cannot be granted freely. For this reason, some authors consider the natural operational paradigm of nonlocality to be that of local operations and shared randomness (LOSR) [8]. (A notable exception to this argument occurs if nonlocality is measured in terms of private correlations: in this case, public classical communication can be freely allowed [9].) In the LOSR framework, separated parties are forbidden all sorts of communication, being allowed though to “synchronize” their local operations with respect to a common classical random variable shared in advance. Hence, nonlocal correlations being defined as those correlations that cannot be simulated by shared randomness [10], nonlocality naturally becomes a resource in the LOSR paradigm.

The resource theory of quantum entanglement, with respect to the resource theory of nonlocality, has received until now much more attention in the literature: correspondingly, many results are known about the interconversion of quantum states by LOCC transformations [7], while much less is known about the LOSR case [8]. The aim of the present Letter is to contribute to bridging this gap, by providing a set of necessary and sufficient conditions for the existence of an LOSR protocol transforming one distributed quantum state into another. Such conditions, rather than algebraic, are operational, in the sense that they are expressed in terms of the payoffs that a quantum state yields in nonlocal games. More precisely, the main result of this Letter is to show that one quantum state can be transformed into another by means of an LOSR protocol, if and only if the former yields a higher payoff than the latter for a whole class of nonlocal games, which we call semiquantum nonlocal games. A remarkable merit of our analysis is to provide a simple and insightful proof of the fact that all entangled quantum states are nonlocal [11]: a corollary of our main result is that any entangled quantum state yields a strictly higher payoff than every separable state, in at least one semiquantum nonlocal game. This general fact will also be illustrated in an explicit example, clarifying how semiquantum nonlocal games are able to faithfully witness entanglement.

*Nonlocality ordering.—*In order to rigorously state the main result (Prop. 1 below), we first need to introduce some notation and a few definitions. In what follows, all quantum systems are finite dimensional (i.e., their Hilbert spaces, denoted by $\mathcal{H}$, are finite dimensional) and index sets (denoted by $\mathcal{S}$, $\mathcal{T}$, $\mathcal{X}$, and $\mathcal{Y}$) contain only a finite number of elements. The convex set of probability distributions defined on an index set $\mathcal{X}$ is denoted by $\mathcal{P}(\mathcal{X})$. The set of linear operators acting on a Hilbert space $\mathcal{H}$ is denoted by $\mathsf{L}(\mathcal{H})$. The set of density matrices (i.e., positive semidefinite, trace-one operators) is denoted by $\mathsf{S}(\mathcal{H})\subset \mathsf{L}(\mathcal{H})$.

A random source of states of a quantum system $A$ is represented by an ensemble $\tau =(\{p(s),{\tau}^{s}\};s\in \mathcal{S})$, where $p\in \mathcal{P}(\mathcal{S})$ and ${\tau}^{s}\in \mathsf{S}({\mathcal{H}}_{A})$, for all $s$. Given an outcome set $\mathcal{X}=\{x\}$ and a quantum system $A$ with Hilbert space ${\mathcal{H}}_{A}$, an $\mathcal{X}$-probability operator-valued measure ( $\mathcal{X}$-POVM, for short) on $A$ is a family $P=({P}^{x};x\in \mathcal{X})$ of positive semidefinite operators ${P}^{x}\in \mathsf{L}({\mathcal{H}}_{A})$, such that $\sum _{x\in \mathcal{X}}{P}^{x}=\mathbb{1}$. We denote by $\mathcal{M}(A;\mathcal{X})$ the convex set of all $\mathcal{X}$-POVMs on $A$. A POVM $P\in \mathcal{M}(A;\mathcal{X})$ induces, via the relation $p(x)=\mathrm{Tr}[{P}^{x}\varrho ]$, a linear function $P\mathrm{\text{:}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\varrho \mapsto P\varrho $ from $\mathsf{S}({\mathcal{H}}_{A})$ to $\mathcal{P}(\mathcal{X})$. POVMs in $\mathcal{M}(A;\mathcal{X})$ are used to model measurements performed on a quantum system $A$ with outcomes in $\mathcal{X}$.

The notion of nonlocal games is of central importance in our discussion (we begin here by considering the bipartite case; the multipartite case follows directly and will be briefly discussed at the end of the paper):

*Definition 1.—*The rules of a nonlocal game ${\mathsf{G}}_{\mathrm{nl}}$ consist of the following: four index sets $\mathcal{S}=\{s\}$, $\mathcal{T}=\{t\}$, $\mathcal{X}=\{x\}$, and $\mathcal{Y}=\{y\}$; two probability distributions $p\in \mathcal{P}(\mathcal{S})$ and $q\in \mathcal{P}(\mathcal{T})$; a payoff function $\wp \mathrm{\text{:}}\mathcal{S}\times \mathcal{T}\times \mathcal{X}\times \mathcal{Y}\to \mathbb{R}$. A referee picks indices $s\in \mathcal{S}$ and $t\in \mathcal{T}$ at random with probabilities $p(s)$ and $q(t)$, and sends them separately to two players, say Alice and Bob, respectively. The two players, without communicating with each other, must compute answers $x\in \mathcal{X}$ and $y\in \mathcal{Y}$, respectively, and send them to the referee, who will then pay them both (i.e., the game is collaborative) an amount equal to $\wp (s,t,x,y)$. (It is understood that a negative payoff means a loss; i.e., the players must pay the referee.)

First, the players are told the rules of the game. Knowing the rules, the players are allowed to agree on any strategy and to share any possible (static) resource. Later on, the players and the referee agree to begin the game, and, from that moment on, an implicit rule of all nonlocal games forbids the players to communicate. According to quantum theory then, anything the two players can do is to share a bipartite quantum state ${\varrho}_{AB}\in \mathsf{S}({\mathcal{H}}_{A}\otimes {\mathcal{H}}_{B})$ and, depending on the questions $s$ and $t$ they are presented, perform independent measurements on $A$ and $B$ with values in $\mathcal{X}$ and $\mathcal{Y}$, respectively.

Imagine now that the state ${\varrho}_{AB}$ shared between Alice and Bob is fixed. It is a well-defined question to ask “how good” is the state ${\varrho}_{AB}$ for playing a given nonlocal game ${\mathsf{G}}_{\mathrm{nl}}$. In order to answer this question, it is convenient to use a mathematical model in which the referee communicates her questions to Alice and Bob by means of a quantum channel. This means that the referee, depending on which questions $s\in \mathcal{S}$ and $t\in \mathcal{T}$ she picked, prepares two auxiliary quantum systems ${A}_{0}$ and ${B}_{0}$, with dimensions $\mathrm{dim}{\mathcal{H}}_{{A}_{0}}\u2a7e|\mathcal{S}|$ and $\mathrm{dim}{\mathcal{H}}_{{B}_{0}}\u2a7e|\mathcal{T}|$, in the orthonormal states ${\pi}^{s}\mathrm{\text{\u2236}}=|s\u27e9\u27e8s|$ and ${\pi}^{t}\mathrm{\text{\u2236}}=|t\u27e9\u27e8t|$, and sends them to Alice and Bob, respectively. We suppose that the states are transmitted without noise. Since Alice and Bob exactly know which game they are playing and which state they are sharing, the payoff they expect to gain (on average) can be expressed by the following formula:

where $\mu (x,y|s,t)$ is the joint conditional probability distribution computed as

and the maximization is performed over all POVMs $P\in \mathcal{M}({A}_{0}A;\mathcal{X})$ and $Q\in \mathcal{M}(B{B}_{0};\mathcal{Y})$.

The function ${\wp}^{*}({\varrho}_{AB};{\mathsf{G}}_{\mathrm{nl}})$ in (1) measures the “nonlocal utility” of ${\varrho}_{AB}$ in playing a nonlocal game ${\mathsf{G}}_{\mathrm{nl}}$. Accordingly, if another state ${\sigma}_{{A}^{\prime}{B}^{\prime}}\in \mathsf{S}({\mathcal{H}}_{{A}^{\prime}}\otimes {\mathcal{H}}_{{B}^{\prime}})$ is such that ${\wp}^{*}({\sigma}_{{A}^{\prime}{B}^{\prime}};{\mathsf{G}}_{\mathrm{nl}})\u2a7d{\wp}^{*}({\varrho}_{AB};{\mathsf{G}}_{\mathrm{nl}})$, we say that ${\varrho}_{AB}$ is better than ${\sigma}_{{A}^{\prime}{B}^{\prime}}$ for playing ${\mathsf{G}}_{\mathrm{nl}}$. By extending this definition to all nonlocal games, we can introduce the following relation:

*Definition 2.—*A bipartite state ${\varrho}_{AB}\in \mathsf{S}({\mathcal{H}}_{A}\otimes {\mathcal{H}}_{B})$ is said to be (definitely) more nonlocal than another bipartite state ${\sigma}_{{A}^{\prime}{B}^{\prime}}\in \mathsf{S}({\mathcal{H}}_{{A}^{\prime}}\otimes {\mathcal{H}}_{{B}^{\prime}})$, written ${\varrho}_{AB}{\succcurlyeq}_{\mathrm{nl}}{\sigma}_{{A}^{\prime}{B}^{\prime}}$, if and only if ${\wp}^{*}({\varrho}_{AB};{\mathsf{G}}_{\mathrm{nl}})\u2a7e{\wp}^{*}({\sigma}_{{A}^{\prime}{B}^{\prime}};{\mathsf{G}}_{\mathrm{nl}})$, for all nonlocal games ${\mathsf{G}}_{\mathrm{nl}}$.

The above definition can be equivalently reformulated in terms of Bell inequalities [2] as follows. Since it is known that to any nonlocal game there corresponds a Bell inequality and, conversely, to any Bell inequality there corresponds a nonlocal game [12], we can equivalently say that ${\varrho}_{AB}{\succcurlyeq}_{\mathrm{nl}}{\sigma}_{{A}^{\prime}{B}^{\prime}}$, if and only if ${\varrho}_{AB}$ appears to be more nonlocal than ${\sigma}_{{A}^{\prime}{B}^{\prime}}$ with respect to all Bell inequalities (or, more precisely speaking, all Bell expressions [13]).

*Local operations and shared randomness.—*Let us now turn to the LOSR paradigm within quantum theory (again, we begin with the bipartite case): a completely positive trace-preserving (CPTP) map $\mathcal{E}\mathrm{\text{:}}\mathsf{L}({\mathcal{H}}_{A}\otimes {\mathcal{H}}_{B})\to \mathsf{L}({\mathcal{H}}_{{A}^{\prime}}\otimes {\mathcal{H}}_{{B}^{\prime}})$ is said to be an LOSR transformation, if it can be written as $\sum _{i}\nu (i){\mathcal{E}}^{i}\otimes {\mathcal{F}}^{i}$, where ${\mathcal{E}}^{i}\mathrm{\text{:}}\mathsf{L}({\mathcal{H}}_{A})\to \mathsf{L}({\mathcal{H}}_{{A}^{\prime}})$ and ${\mathcal{F}}^{i}\mathrm{\text{:}}\mathsf{L}({\mathcal{H}}_{B})\to \mathsf{L}({\mathcal{H}}_{{B}^{\prime}})$ are CPTP maps for all $i$, and $\nu (i)$ is a probability distribution [14]. We then introduce the following definition:

*Definition 3.—*A bipartite state ${\varrho}_{AB}\in \mathsf{S}({\mathcal{H}}_{A}\otimes {\mathcal{H}}_{B})$ is said to be LOSR sufficient for another bipartite state ${\sigma}_{{A}^{\prime}{B}^{\prime}}\in \mathsf{S}({\mathcal{H}}_{{A}^{\prime}}\otimes {\mathcal{H}}_{{B}^{\prime}})$, written ${\varrho}_{AB}\rightarrowtail {\sigma}_{{A}^{\prime}{B}^{\prime}}$, if and only if there exists an LOSR transformation mapping ${\varrho}_{AB}$ into ${\sigma}_{{A}^{\prime}{B}^{\prime}}$.

It is a rather straightforward exercise to prove that the relation $\rightarrowtail $ implies the relation ${\succcurlyeq}_{\mathrm{nl}}$. In fact, ${\varrho}_{AB}{\succcurlyeq}_{\mathrm{nl}}({\mathcal{E}}^{i}\otimes {\mathcal{F}}^{i}){\varrho}_{AB}$ trivially holds for all $i$. On the other hand, the payoff achievable with the convex combination $\sum _{i}\nu (i)({\mathcal{E}}^{i}\otimes {\mathcal{F}}^{i}){\varrho}_{AB}$ cannot exceed the best payoff achievable with each of its components; i.e., there exists $i$ such that $({\mathcal{E}}^{i}\otimes {\mathcal{F}}^{i}){\varrho}_{AB}{\succcurlyeq}_{\mathrm{nl}}\sum _{i}\nu (i)({\mathcal{E}}^{i}\otimes {\mathcal{F}}^{i}){\varrho}_{AB}$. This proves the claim.

It is also straightforward to prove that separable states are the end points of the relation $\rightarrowtail $, i.e., for any separable state ${\sigma}_{{A}^{\prime}{B}^{\prime}}$, ${\varrho}_{AB}\rightarrowtail {\sigma}_{{A}^{\prime}{B}^{\prime}}$, for all ${\varrho}_{AB}$. Suppose, in fact, that ${\sigma}_{{A}^{\prime}{B}^{\prime}}\in \mathsf{S}({\mathcal{H}}_{{A}^{\prime}}\otimes {\mathcal{H}}_{{B}^{\prime}})$ is a separable state, i.e., ${\sigma}_{{A}^{\prime}{B}^{\prime}}=\sum _{i}\nu (i){\gamma}_{{A}^{\prime}}^{i}\otimes {\chi}_{{B}^{\prime}}^{i}$, for some probability distribution $\nu (i)$ and some local states ${\gamma}^{i}\in \mathsf{S}({\mathcal{H}}_{{A}^{\prime}})$ and ${\chi}^{i}\in \mathsf{S}({\mathcal{H}}_{{B}^{\prime}})$. Then, there always exists a “discard-and-prepare” LOSR map $\mathcal{E}\mathrm{\text{:}}\mathsf{L}({\mathcal{H}}_{A}\otimes {\mathcal{H}}_{B})\to \mathsf{L}({\mathcal{H}}_{{A}^{\prime}}\otimes {\mathcal{H}}_{{B}^{\prime}})$ such that ${\sigma}_{{A}^{\prime}{B}^{\prime}}=\mathcal{E}({\varrho}_{AB})$, for all ${\varrho}_{AB}\in \mathsf{S}({\mathcal{H}}_{A}\otimes {\mathcal{H}}_{B})$, proving the claim.

These two facts together make it easy to verify that, in any nonlocal game ${\mathsf{G}}_{\mathrm{nl}}$, all separable states yield exactly the same payoff ${\wp}_{\mathrm{sep}}({\mathsf{G}}_{\mathrm{nl}})$. This remark will be useful in what follows.

*Semiquantum nonlocal games.—*At this point, the question of whether the implication can be reversed, i.e., whether the relation ${\succcurlyeq}_{\mathrm{nl}}$ implies $\rightarrowtail $ or not, naturally arises, and its answer is “no.” Let us consider in fact those entangled quantum states (called LHVPOV states [4]) for which a local-hidden-variable model exists, describing the outcome statistics of every local POVM measurement performed on them. This means that, for any nonlocal game ${\mathsf{G}}_{\mathrm{nl}}$, the expected payoff obtainable from such entangled states never exceeds that obtainable from separable states. However, it is impossible to create an entangled state (even if LHVPOV) by acting with LOSR transformations on separable states. This proves the claim that ${\succcurlyeq}_{\mathrm{nl}}$ does not imply $\rightarrowtail $.

The relation ${\succcurlyeq}_{\mathrm{nl}}$ is too weak to imply $\rightarrowtail $. We hence introduce a stronger version of ${\succcurlyeq}_{\mathrm{nl}}$, by suitably enlarging the set of nonlocal games we consider. The extended notion of nonlocal games we need is the following:

*Definition 4.—*The rules of a semiquantum nonlocal game ${\mathsf{G}}_{\mathrm{sq}}$ consist of: four index sets $\mathcal{S}=\{s\}$, $\mathcal{T}=\{t\}$, $\mathcal{X}=\{x\}$, and $\mathcal{Y}=\{y\}$; two quantum systems ${A}_{0}$ and ${B}_{0}$; two random sources $\tau =(\{p(s),{\tau}^{s}\};s\in \mathcal{S})$ and $\omega =(\{q(t),{\omega}^{t}\};t\in \mathcal{T})$ on ${A}_{0}$ and ${B}_{0}$, respectively; a payoff function $\wp \mathrm{\text{:}}\mathcal{S}\times \mathcal{T}\times \mathcal{X}\times \mathcal{Y}\to \mathbb{R}$. A referee picks indices $s\in \mathcal{S}$ and $t\in \mathcal{T}$ at random with probabilities $p(s)$ and $q(t)$, and sends the corresponding states ${\tau}^{s}$ and ${\omega}^{t}$ to Alice and Bob, respectively, (without revealing the actual indices $s$ and $t$ though). The two players, without communicating with each other, must compute answers $x\in \mathcal{X}$ and $y\in \mathcal{Y}$, respectively, and send them to the referee, who will then pay them both an amount equal to $\wp (s,t,x,y)$.

In other words, while in conventional nonlocal games the referee asks the players “classical” questions, in semiquantum nonlocal games the referee is allowed to ask them “quantum” questions. Clearly, semiquantum nonlocal games contain, as special cases, conventional nonlocal games (Def. 1), whenever the states that the referee sends to Alice and Bob are perfectly distinguishable, i.e., classical. The situation is depicted in Fig. 1.

As in the case of conventional nonlocal games, the two players are allowed to share a bipartite quantum state, say ${\varrho}_{AB}$, so that the expected payoff ${\wp}^{*}({\varrho}_{AB};{\mathsf{G}}_{\mathrm{sq}})$ is given by the same formula (1), the only difference being that the joint conditional probability distribution $\mu (x,y|s,t)$ is now computed as

Analogously to what was done before, we can compare the nonlocal utility of two quantum states for all semiquantum nonlocal games and introduce the following relation:

*Definition 5.—*Given two bipartite states ${\varrho}_{AB}\in \mathsf{S}({\mathcal{H}}_{A}\otimes {\mathcal{H}}_{B})$ and ${\sigma}_{{A}^{\prime}{B}^{\prime}}\in \mathsf{S}({\mathcal{H}}_{{A}^{\prime}}\otimes {\mathcal{H}}_{{B}^{\prime}})$, we define the relation ${\varrho}_{AB}{\succcurlyeq}_{\mathrm{sq}}{\sigma}_{{A}^{\prime}{B}^{\prime}}$, meaning that ${\wp}^{*}({\varrho}_{AB};{\mathsf{G}}_{\mathrm{sq}})\u2a7e{\wp}^{*}({\sigma}_{{A}^{\prime}{B}^{\prime}};{\mathsf{G}}_{\mathrm{sq}})$, for all semiquantum nonlocal games ${\mathsf{G}}_{\mathrm{sq}}$.

Since semiquantum nonlocal games contain conventional nonlocal games as a special case, the relation ${\succcurlyeq}_{\mathrm{sq}}$ implies the relation ${\succcurlyeq}_{\mathrm{nl}}$. Moreover, along the same line of thoughts used above to show that $\rightarrowtail $ implies ${\succcurlyeq}_{\mathrm{nl}}$, it is straightforward to prove that $\rightarrowtail $ also implies ${\succcurlyeq}_{\mathrm{sq}}$.

*A fundamental equivalence.—*We are now ready to state the main result of this Letter:

*Proposition 1.—*Given two bipartite states ${\varrho}_{AB}$ and ${\sigma}_{{A}^{\prime}{B}^{\prime}}$, ${\varrho}_{AB}{\succcurlyeq}_{\mathrm{sq}}{\sigma}_{{A}^{\prime}{B}^{\prime}}$ if and only if ${\varrho}_{AB}\rightarrowtail {\sigma}_{{A}^{\prime}{B}^{\prime}}$.

The proof of Prop. 1 is based on arguments very similar to those used in Ref. [15], and crucially uses the separation theorem between convex sets [16]. Being rather technical in nature, we omit it here, pointing the interested reader to the Supplemental Material accompanying this Letter [17]. Here we only discuss one important consequence of our main result, that is, Prop. 1 implies that any entangled state is strictly more nonlocal than every separable state, as stated in the following corollary:

*Corollary 1.—*In any semiquantum nonlocal game ${\mathsf{G}}_{\mathrm{sq}}$, all separable quantum states yield exactly the same payoff ${\wp}_{\mathrm{sep}}({\mathsf{G}}_{\mathrm{sq}})$. Moreover, a quantum state ${\varrho}_{AB}$ is entangled if and only if there exists a semiquantum nonlocal game ${\mathsf{G}}_{\mathrm{sq}}$, for which ${\wp}^{*}({\varrho}_{AB};{\mathsf{G}}_{\mathrm{sq}})>{\wp}_{\mathrm{sep}}({\mathsf{G}}_{\mathrm{sq}})$.

In other words, any entangled quantum state has a form of nonlocality, which is “hidden” [11] for conventional nonlocal games (and hence Bell inequalities), but becomes apparent when playing semiquantum nonlocal games. The proof of the above corollary is a direct consequence of the fact that separable states, being the end points of the relation $\rightarrowtail $, are also the end points of the relation ${\succcurlyeq}_{\mathrm{sq}}$, due to the equivalence established by Prop. 1.

*An example.—*In order to illustrate the superiority of semiquantum nonlocal games, with respect to conventional ones, in witnessing entanglement, we describe now the example of a semiquantum nonlocal game, in which every entangled state gives rise to joint question-answer probability distributions that cannot be explained as coming from any separable state, even if supplemented with an unlimited amount of shared randomness. This is true also for entangled LHVPOV states, which are instead completely indistinguishable from separable states, if only conventional nonlocal games (Def. 1) are considered. The example, directly stemming from the proof of Proposition 1 (see [17]), is described here only in the case of two-qubit states; we remark, however, that the same construction can be easily carried over to any finite-dimensional case.

In our example, $\mathcal{S}=\mathcal{T}=\mathcal{X}=\mathcal{Y}=\{1,2,3,4\}$, the auxiliary quantum systems used by the referee to encode her questions are represented by two qubits, i.e., ${\mathcal{H}}_{{A}_{0}}\cong {\mathcal{H}}_{{B}_{0}}\cong {\mathbb{C}}^{2}$, and the “question states” are the four tetrahedral states $|{\psi}_{1}\u27e9$, $|{\psi}_{2}\u27e9$, $|{\psi}_{3}\u27e9$, and $|{\psi}_{4}\u27e9$ defined by Davies [18]. Notice that the choice of the question states is somewhat arbitrary: the important point is that their density matrices constitute a basis for the linear space $\mathsf{L}({\mathbb{C}}^{2})$. (The definition of the probability distributions on $\mathcal{S}$ and $\mathcal{T}$, as well as that of the payoff function, are not necessary for our argument and can be omitted.)

Given a two-qubit state ${\varrho}_{AB}$, let us consider the joint conditional question-answer probability distribution $\overline{\mu}(x,y|s,t\parallel \varrho )$ computed as

where ${B}^{1}$, ${B}^{2}$, ${B}^{3}$, ${B}^{4}$ are, respectively, the four orthogonal Bell measurements on ${\Phi}^{+}$, ${\Phi}^{-}$, ${\Psi}^{+}$, ${\Psi}^{-}$. In the process of proving Prop. 1 (see [17]), it is also shown that, in particular, the two-qubit state ${\varrho}_{AB}$ is entangled if and only if, for any (possibly higher-dimensional) separable state ${\sigma}_{{A}^{\prime}{B}^{\prime}}$ and for any possible POVMs $P\in \mathcal{M}({A}_{0}{A}^{\prime};\mathcal{X})$ and $Q\in \mathcal{M}({B}^{\prime}{B}_{0};\mathcal{Y})$,

In fact, one can easily check, following the proof of Prop. 1, that an equality in the above equation, for some separable state ${\sigma}_{{A}^{\prime}{B}^{\prime}}$ and some POVMs $P$ and $Q$, would imply the existence of an LOSR transformation mapping ${\sigma}_{{A}^{\prime}{B}^{\prime}}$ into ${\varrho}_{AB}$, hence leading to a contradiction, due to the fact that LOSR transformations cannot create entangled states from separable ones. In other words, the state ${\varrho}_{AB}$ is entangled if and only if the joint conditional probability distribution $\overline{\mu}(x,y|s,t\parallel \varrho )$, computed in Eq. (2), is out of reach for any possible separable state, even with the help of unlimited shared randomness (represented here by the possibility of ${\sigma}_{{A}^{\prime}{B}^{\prime}}$ being on a higher-dimensional Hilbert space).

*Multipartite states.—*Before concluding, we remark here that our approach can be straightforwardly extended to consider multipartite LOSR transformations $\mathcal{E}\mathrm{\text{:}}\mathsf{L}({\mathcal{H}}_{A}\otimes {\mathcal{H}}_{B}\otimes {\mathcal{H}}_{C}\otimes \cdots )\to \mathsf{L}({\mathcal{H}}_{{A}^{\prime}}\otimes {\mathcal{H}}_{{B}^{\prime}}\otimes {\mathcal{H}}_{{C}^{\prime}}\otimes \cdots )$ of the form $\mathcal{E}=\sum _{i}\nu (i){\mathcal{E}}^{i}\otimes {\mathcal{F}}^{i}\otimes {\mathcal{G}}^{i}\otimes \cdots $, where ${\mathcal{E}}^{i}\mathrm{\text{:}}\mathsf{L}({\mathcal{H}}_{A})\to \mathsf{L}({\mathcal{H}}_{{A}^{\prime}})$, ${\mathcal{F}}^{i}\mathrm{\text{:}}\mathsf{L}({\mathcal{H}}_{B})\to \mathsf{L}({\mathcal{H}}_{{B}^{\prime}})$, ${\mathcal{G}}^{i}\mathrm{\text{:}}\mathsf{L}({\mathcal{H}}_{C})\to \mathsf{L}({\mathcal{H}}_{{C}^{\prime}})$, and so on, are all CPTP maps, for all $i$. This can be done by considering multipartite semiquantum nonlocal games, in which all the players independently receive their “quantum questions” from the referee, and by following the same arguments used to prove the bipartite case.

*Conclusions.—*We showed that one quantum state can be transformed into another by means of an LOSR protocol, if and only if the former is “more nonlocal” than the latter, where nonlocality is quantified by means of semiquantum nonlocal games (Def. 5). As a by-product, we obtained a clear-cut proof that any entangled quantum state is always nonlocal, a fact that should be considered in light of previous works reaching the same conclusion, although from very different routes [11]. In order to support our analysis and show the superiority of semiquantum nonlocal games, with respect to conventional ones, in witnessing entanglement, we also provided an explicit example of a semiquantum nonlocal game, in which any entangled state gives rise to joint question-answer probability distributions that cannot be explained classically, even if an unlimited amount of shared randomness is granted.

## References

- A. Einstein, B. Podolsky, and N. Rosen, Phys. Rev.
**47**, 777 (1935). - J. S. Bell, Physics
**1**, 195 (1964); ; J. F. Clauser, M. A. Horne, A. Shimony, and R. A. Holt, Phys. Rev. Lett.**23**, 880 (1969). - R. F. Werner, Phys. Rev. A
**40**, 4277 (1989); ; N. Gisin, Phys. Lett. A**154**, 201 (1991); ; R. Horodecki, P. Horodecki, and M. Horodecki,**200**, 340 (1995). - J. Barrett, Phys. Rev. A
**65**, 042302 (2002). - A. A. Méthot and V. Scarani, Quantum Inf. Comput.
**7**, 157 (2007). - C. H. Bennett, G. Brassard, S. Popescu, B. Schumacher, J. A. Smolin, and W. K. Wootters, Phys. Rev. Lett.
**76**, 722 (1996); ; C. H. Bennett, D. P. DiVincenzo, J. A. Smolin, and W. K. Wootters, Phys. Rev. A**54**, 3824 (1996). - R. Horodecki, P. Horodecki, M. Horodecki, and K. Horodecki, Rev. Mod. Phys.
**81**, 865 (2009). - D. D. Dukaric and S. Wolf, arXiv:0808.3317v2; M. Forster, S. Winkler, and S. Wolf, Phys. Rev. Lett.
**102**, 120401 (2009); ; M. Forster and S. Wolf, Phys. Rev. A**84**, 042112 (2011). - R. Gallego, L. E. Würflinger, A. Acín, M. Navascués, arXiv:1112.2647v1.
- A. J. Short, S. Popescu, and N. Gisin, Phys. Rev. A
**73**, 012101 (2006). - S. Popescu, Phys. Rev. Lett.
**74**, 2619 (1995); ; N. Gisin, Phys. Lett. A**210**, 151 (1996); ; A. Peres, Phys. Rev. A**54**, 2685 (1996); ; L. Masanes, Y.-C. Liang, and A. C. Doherty, Phys. Rev. Lett.**100**, 090403 (2008). - J. Silman, S. Machnes, and N. Aharon, Phys. Lett. A
**372**, 3796 (2008). - T. Vértesi and E. Bene, Phys. Rev. A
**82**, 062115 (2010). - D. Beckman, D. Gottesman, M. A. Nielsen, and J. Preskill, Phys. Rev. A
**64**, 052309 (2001). - F. Buscemi, Commun. Math. Phys.
**310**, 625 (2012). - R. T. Rockafellar,
*Convex Analysis*(Princeton University Press, Princeton, 1970), Corollary 11.4.2 therein. - See Supplemental Material at http://link.aps.org/supplemental/10.1103/PhysRevLett.108.200401 for the proof of Proposition 1.
- E. B. Davies, IEEE Trans. Inf. Theory
**24**, 596 (1978), proof of Proposition 8 therein.