{'fraction_non_alphanumeric': 0.05365658330603182, 'fraction_numerical': 0.00866368170070256, 'mean_word_length': 3.933022086550548, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 6, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 20, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
No quantum realization of extremal no-signaling boxes

Pure states are very important in any theory since they represent states of maximal information about the system within the theory. Here, we show that no non-trivial (not local realistic) extremal states (boxes) of general no-signaling theories can be realized within quantum theory. We then explore three interesting consequences of this fact. Firstly, since the pure states are uncorrelated from the environment, the statement forms a no-go result against the most straightforward device-independent protocol for randomness or secure key generation against general no-signaling adversaries. It also leads to the interesting question whether all non-extremal boxes allow for non-local correlations with the adversary. Secondly, in addition to the fact that new information-theoretic principles (designed to pick out the set of quantum correlations from among all non signaling ones) can in consequence be tested on arbitrary non-local vertices to check their validity, it also allows the possibility of excluding from the quantum set any box of no-signaling correlations that can be distilled to a non-local vertex. Finally, it also forms a sufficient condition to identify non-local games with no quantum winning strategy, when one can show that the game has a single unique non-signaling winning strategy. We illustrate each of these consequences with the example of generalized Popescu-Rohrlich boxes.

Introduction. It is well-known that quantum mechanics allows for non-local correlations between spatially separated systems, i.e., correlations that cannot be explained by any local hidden variable theory as shown by the violation of Bell inequalities. The correlations described by quantum theory form a convex set which is sandwiched between the sets of classical correlations and general no-signaling correlations. By how much and why the quantum set is inside the no-signaling set has been the subject of intense research [1][2][3][4][5][6][7].
While the classical and no-signaling sets are known to form polytopes, the quantum set is convex but is not a polytope in general. Each point in the set describes a box of correlations, that is a set of conditional probability distributions for outputs given inputs. The extremal boxes (vertices) of the no-signaling polytope are the pure states of the no-signaling theory and their purity implies that they are completely uncorrelated with the environment. Consequently, access to an extremal non-local box would be of great advantage in cryptographic tasks, providing intrinsic certified randomness and keys secure against any eavesdropper even when the latter is limited only by the no-signaling principle. Extremal boxes are also of crucial importance in the program of deriving the set of quantum correlations from purely information-theoretic principles, being essential testbeds for checking the validity of such principles [2][3][4][5][6][7]. Furthermore, the extremal boxes are the ones that maximally violate Bell inequalities in no-signaling theories; for some Bell inequalities there exists a unique box that gives maximal violation. For instance, for the celebrated CHSH inequality [8], there exists a unique vertex known as the Popescu-Rohrlich (PR) box [9] which maximally violates the inequality. From these considerations, one arrives at the fundamental question: does quantum mechanics allow for the realization of extremal non-local no-signaling boxes? In other words, is there a Bell scenario (for some number of parties, inputs and outputs) for which the quantum set reaches a non-local vertex of the corresponding no-signaling polytope?
Here, we show that the answer to this question is negative: no quantum realization of any extremal non-local no-signaling box exists. To show this, we make use of recently discovered connections between contextuality and Bell scenarios and graph theory [6,10,11]. We then consider a few interesting consequences of this fact. Firstly, we consider the important class of Bell inequalities known as multi-player unique games and give a simple condition for identifying when the inequality is maximally violated by a single vertex. Our main result coupled with the fact that all unique games can be won with certainty in general no-signaling theories, then shows that quantum theory does not allow for a winning strategy for this subset of unique games.
Secondly, the non-local vertices being excluded from quantum theory implies that any box that can be distilled to such a vertex by operations (wirings) performed locally by the parties is also excluded. We present a generalization of previously disovered protocols for nonlocality distillation to the case of generalized PR boxes with more outcomes and parties, thus excluding new classes of boxes from the quantum set. Finally, the fact that vertices are decoupled from the environment (in particular, eavesdroppers in cryptographic tasks) leads us to consider if any box in the interior of the nosignaling polytope is always non-locally correlated with the environment. We present an extension (into an n + 1 party box) for the class of n party boxes realized as admixtures of the generalized PR box with the fully mixed box, showing that indeed for any non-zero fraction of noise, such a box exhibits non-local correlations with the eavesdropper's system. We conclude with some open questions.
Extremal no-signaling correlations. Consider the n-party Bell scenario labeled by (A i , X i ) with i ∈ [n] (with [n] := {1, . . . , n}), where the sets X i of size m i denote the respective inputs x i of the n parties, while the sets A i of size k i denote their respective outputs a i . The number of inputs m i and outputs k i for each party is arbitrary but for convenience of notation we will consider m i = m and k i = k, ∀i ∈ [n], whenever such a simplification does not affect the generality of the argument. A box P describes a set of conditional probability distributions P (a|x) with a = {a 1 , . . . , a n } ∈ A, x = {x 1 , . . . , x n } ∈ X where A = A 1 × . . . A n and similarly X = X 1 × . . . X n ; the Bell scenario corresponding to this box is denoted as B(n, m, k). The box P is a valid no-signaling box for the Bell scenario if it satisfies: (i) Positivity: P (a|x) ≥ 0 ∀a, x; (ii) Normalization: a P (a|x) = 1 ∀x; and (iii) No-signaling: The set of all boxes satisfying the above conditions forms the no-signaling convex polytope Here the constraints (i) -(iii) are written in terms of the matrix A and the vector |b , and the box P is written as a vector of length (mk) n . Boxes that satisfy in addition the integrality constraint: (iv) Integrality: P (a|x) ∈ {0, 1} are said to be classical (deterministic) boxes P d . The convex hull of these deterministic boxes gives rise to the classical polytope C(n, m, k) ⊆ NS(n, m, k). The set of quantum correlations Q(n, m, k) is defined as follows: P ∈ Q(n, m, k) if there exist a state |ψ , sets of measurement operators {E xi,ai i } for each party such that for all inputs and outputs with the measurement operators satisfying the requirements of hermiticity (E xi,ai , ∀x i ) and completeness ( ai E xi,ai i = 1 1, ∀x i ). This set is convex but in general is not a polytope, and C(n, m, k) ⊆ Q(n, m, k) ⊆ NS(n, m, k).
We are interested in the vertices of the no-signaling polytope, a box P being a vertex if it cannot be expressed as a non-trivial convex combination of the boxes in NS(n, m, k). The vertex of a polytope is a point such that the normal cone to the point has full dimension, and every vertex satisfies in a unique way a certain number of the inequality constraints in A · |P ≤ |b with equality. Formally the vertex is characterized as follows [12]: Fact 1. A box P is a vertex of the no-signaling polytope NS(n, m, k) if any only if rank(Ã) = (mk) n whereÃ denotes the sub-matrix of A consisting of those row vectors A i for which A i · |P = |b i .
For two distinct vertices P and P ′ , the corresponding sub-matrices are not equal Ã (P) =Ã(P ′ ) . A nonlocal vertex is one that does not belong to C(n, m, k). We use recently discovered connections between contextuality and non-local game scenarios to graph theory [6,10,11] to show that such a vertex also does not belong to the quantum set Q(n, m, k).

Theorem 1.
For some (arbitrary) (n, m, k), let P nl be a vertex of the no-signaling polytope NS(n, m, k) such that P nl / ∈ C(n, m, k). Then P nl / ∈ Q(n, m, k).
Non-local games with no quantum winning strategy. An immediate application of Theorem 1 is that if one is able to identify a non-local game that has a single unique winning no-signaling strategy (where by a winning strategy we mean one that achieves maximal value 1), then such a strategy (being a vertex) cannot be realized in quantum theory. So that denoting by ω q (g) the quantum value of the game (ω c (g) denotes the classical value), we have ω q (g) = 1. Here, we consider a class of Bell inequalities known as total unique games (g U ) for multiple players, which are a family of games of great interest in the field of hardness of approximation (in determining the algorithmic complexity of finding close to optimal solutions for optimization problems) as seen in the famous unique games conjecture [13]. A unique game is defined by the following winning condition: for each x and each set of outcomes of any chosen n − 1 parties, a (j) n−1 = a \ a j ∀j, the remaining party is required to output a single unique a j specified by a func- ; the term total refers to the fact that such a winning constraint is imposed for every set of inputs x. We now introduce the notion of a no-signaling graph associated with any non-local game.
Definition. For any non-local game g, we define the nosignaling graph G N S (g) = (V, E) associated with the game to have set of vertices v ∈ V, each of which is labeled by a set of inputs and outputs that wins the game, v = a (v) , x (v) .

Lemma 2.
A total multi-player unique game g U is won by a single unique non signaling box if and only if the no-signaling graph G N S (g U ) associated to the game is connected; for such a game ω q (g U ) = 1.
Proof. By definition for a unique game, only one term from the game constraint appears in each sum in the nosignaling constraint Eq.(1) for any x (i) , x' (i) , a. Hence, two vertices being connected implies that the corresponding probabilities are equal. Consequently, the nosignaling graph G N S (g U ) being connected implies that the box is uniform, with every winning event occurring with probability 1 k , where k is the number of outputs of the game. Since the total unique game considers all sets of inputs x, it is won by this specific no-signaling box alone, which must necessarily therefore be a vertex of the no-signaling polytope. By Theorem 1, we know that such a box cannot be realized by measurements on quantum states, so that ω q (g U ) = 1.
On the other hand, consider that the graph G N S (g U ) is disconnected, being composed of c > 1 components G c . By definition of the no-signaling graph and the winning constraint of the unique game, each G c consists of the same number k c of vertices from each setting , and zero otherwise. It is readily seen that each such box P c wins the game.
⊓ ⊔ An alternative (equivalent) characterization of the total unique game with single maximally violating box is that the block matrix composed of the permutation matrices associated to the functions σ (j) x defining the unique game in every n − 1|1 cut is irreducible. Let us now illustrate the above application with an example of the generalized PR box and show that the corresponding generalized CHSH game cannot be won quantumly. Example 1. The unique game g U,ex for n parties with inputs x i ∈ {0, 1} and outputs a i ∈ {0, . . . , k − 1} defined by the winning constraint: x i is won by a single no-signaling vertex for any n, k.
Proof. We show that the no-signaling graph G N S (g U,ex ) is connected so that the game is won by a single nosignaling box by Lemma 2. Firstly, note that the nosignaling graph G N S (g U ) for any unique game of n parties with m inputs each with k outputs is of size m n · k n−1 since for each set of inputs x (of which there are m n ) there are k n−1 outputs a that win the game. Therefore, for G N S (g U,ex ) with vertex set V, we have |V| = 2 n k n−1 . We may group the vertices into two The edges of the graph G N S (g U,ex ) can also be grouped into two sets based on V 0 and V 1 : n }, and ⊕ j denotes addition modulo j.

For u
Therefore, we have that the graph is regular with the degree of each vertex (the number of edges incident at each vertex) equal to n, so that the total number of edges in the graph is given by |E| = n2 n k n−1

2
. Let us divide the vertex set V into k n−1 subsets each of fixed a n−1 (outputs of the first n − 1 parties) which we denote by V an−1 with |V a n−1 | = 2 n . From the edge sets above, it is clear that the corresponding subgraphs G an−1 are connected. It remains to be shown that these k n−1 subgraphs are connected to each other.
To do this, let us form a new graph G ′ N S with each connected subgraph G an−1 as a single vertex in the new graph and edges between two vertices in G ′ N S if there exists an edge between any two vertices in the corresponding subgraphs. Due to the xor structure, the edges in set (2) above with u ∈ V 1 and v ∈ V 0 give rise to cyclic subgraphs of length k in G ′ N S . The vertex set of G ′ N S (of size k n−1 ) is thus partitioned in n − 1 different ways into k n−2 sets of vertices belonging to disjoint cyclic subgraphs of size k each. This guarantees that the graph G ′ N S is connected; and hence that the different subgraphs G an−1 for each a n−1 are connected to each other. The graph G N S (g U,ex ) is thus connected; by Lemma 2, we have that the game g U,ex is won by a unique no-signaling vertex, and hence cannot be won using quantum resources.

⊓ ⊔
In [14], it was shown that for two-player binary games g bin (where the output alphabet of the two players is binary), ω q (g bin ) = 1 if and only if ω c (g bin ) = 1. For the sub-class of binary games known as (total) XOR games (where the game winning constraint only depends on the XOR of the two players' outputs), this result can be seen as a consequence of Lemma 2. This is because for total XOR games, it is readily seen that the graph G N S is disconnected (and the corresponding block matrix composed of the two possible permutation matrices corresponding to correlations and anti-correlations is reducible) if and only if the game can be won with a classical deterministic strategy.
Exclusion of boxes by distilling many copies to a vertex. The fact that non-local extremal points of the nosignaling set in a single-shot scenario cannot be realized using quantum resources can also be used to exclude from the quantum set those boxes which can be distilled (with many copies in a sequential scenario) to such a vertex. In other words, if there exists a distillation protocol that deterministically maps a certain number of copies of a box P to a non-local vertex, then P / ∈ Q(n, m, k).
As an illustration, consider the box presented in the Example 1, defined as We now examine an admixture of the above non-local vertex with a locally correlated box P c,ex defined as A generalization of the distillation protocols in [15], [16], shows that for any ε ∈ (0, 1), many copies of the box can be distilled to the vertex P nl,ex n , so that the box P ε,n for arbitrary ε(> 0), n (arbitrarily close to the classical polytope) is immediately excluded from the quantum set. Proof. We show a protocol D (2) that maps P ⊗2 ε,n to P ε ′ ,n with ε ′ > ε; the statement then follows by iteration of D (2) . Let us denote by x i ⊕ a (2) i . We show that with probability ε ′ > ε, we have ⊕ n i=1 a i = n i=1 x i so that the iteration of the protocol succeeds in distilling the box P ε,n to the vertex P nl,ex n . Consider the action of the protocol on each of the four terms in P ⊗2 ε,n . (i) P nl,ex n ⊗2 : With the above choice of inputs, we have that  (iv) P c,ex n ⊗2 : we have that simply ⊕ i a i = 0 so that this box is mapped to P c,ex n . Overall, we see that the protocol D (2) maps P ⊗2 ε,n to ε ′ P nl,ex n + (1 − ε ′ ) P c,ex n with ε ′ = ε k n−1 k n−1 + 1 − ε > ε. Iterating this protocol for r = 2 j boxes for large j results in the distillation of the initial box P ε,n to the nonlocal vertex P nl,ex n .

It is readily seen that when
⊓ ⊔

Extensions of non-extremal boxes.
Perhaps the most crucial consequence of Theorem 1 is that it rules out the most straightforward protocol for obtaining secure keys or random bits, as we now demonstrate. Extremal nonlocal boxes of the no-signaling polytope cannot be correlated with the environment, i.e., if P = {P (a|x)} is an n-party box that is a vertex, and {P (a, b|x, y)} is any n + 1-party box of which P is the marginal, then necessarily, one has To see this, note that where we have used the no-signaling condition P (b|x, y) = P (b|y). Since {P (a|x)} is a vertex, the decomposition in Eq. (7) can only have a single term, so that for all b, y, we have P (a|x, b, y) = P (a|x), which translates to Access to an extremal box P would thus provide a tremendous advantage to the honest parties in cryptographic tasks where one considers the presence of an all-powerful adversary limited only by the relativistic causality constraint imposed by the no-signaling principle. For instance, in a noiseless scenario, one can readily design a protocol where the honest parties check for the presence of the extremal box in a device-independent manner and then obtain the intrinsic randomness from the box or use it to distribute secure keys, knowing that they are uncorrelated with the eavesdropper's system. Theorem 1 is thus a no-go result against this straightforward protocol. On the other hand, if P is not a vertex, then Eq. (7) shows that there can always be (classical) correlations with the eavesdropper's system.
A natural question then arises (see [17]) if any box P that is in the interior of the no-signaling polytope also allows for non-local correlations with an eavesdropper, i.e., if there is an extension into a boxP(a, e|x, z) such that P(a|x) is obtained as the marginal ofP upon tracing out the eavesdropper's system, andP exhibits non-locality in the cut (A 1 , . . . , A n )|E. This is especially interesting not only due to the fact that non-local correlations impart additional power to the eavesdropper, but that the analogous fact in quantum theory holds, namely a mixed state of n systems can always be extended into an entangled state of n+1 systems, i.e., ρ n = i λ i |i ⊗n i ⊗n | can be extended to |ψ n+1 = i √ λ i |i ⊗n+1 where the |i constitute an orthonormal basis, and λ i > 0 are the corresponding eigenvalues. For the vertices from Example 1 (given in Eq.(3)), which correspond to the Bell scenario B(n, 2, k), we show that any box obtained by admixing the vertex with the completely noisy box P 1 1 n with entries P 1 1 n (a|x) = 1 k n ∀a, x does admit an extension into an n+ 1 party boxP(a, e|x, z) with e ∈ {0, . . . , k − 1} and z ∈ {0, 1} such that the bipartite cut (A 1 , . . . , A n )|E exhibits non-local correlations. We note that the extremal points of the Bell scenario B(2, 2, k) have been characterized in [17] where it was shown that all the extremal boxes are of the form given in Eq. (3) for n = 2 up to a local relabeling of the inputs and outputs. We now examine the isotropic boxes of the form P iso ε,n = εP nl,ex n + (1 − ε)P 1 1 n .
We now show that for any ε ∈ [0, 1), the boxP ε,n+1 in the cut (A 1 , . . . , A n )|E violates the bipartite Bell inequality defined for P nl,ex 2 , i.e., with the winning constraint a ⊕ e = x · z. This is achieved by the following choice of inputs for the n + 1 parties: (x 1 = x, x 2 = . . . x n = 0, x n+1 = z) and the outputs (a = ⊕ n i=1 a i , e = a n+1 ). With this choice of inputs and outputs, the boxP ε,n+1 achieves in the cut (A 1 , . . . , A n )|E the value 4 − ε for the bipartite inequality which beats the local bound of 3 for any ε ∈ [0, 1). ⊓ ⊔

Conclusions.
We have seen that the non-local vertices of the no-signaling polytope of correlations admit no quantum realization and explored some consequences of this fact. An interesting question for future study is how close the quantum set can get to such a vertex, and whether a finite separation always exists. In this regard, it is pertinent to note that for Bell inequalities with algebraic violation (such as the GHZ paradoxes in [18]) or close to algebraic violation (such as the chained Bell inequalities in [19]), the quantum set only reaches the corresponding facet of the no-signaling polytope. Another question for further research is to identify other interesting classes of vertices than the one illustrated here, and construct novel distillation protocols for these. Finally, an open problem is whether all points in the interior of the no-signaling set allow for non-local correlations with the environment, and its consequences for cryptographic tasks.

Supplemental Material
Here we present the proof of the Theorem 1 stated in the main text. To do this, we first present some background information on recently discovered relations between contextuality and non-local game scenarios to graph theory.
In [20], a hierarchy of semi-definite programs was formulated for optimization with non-commuting variables, that is used to identify when a box P does not belong to the quantum set; it was also shown that the hierarchy converges to a set Q pr (n, m, k). Note that the set Q pr (n, m, k) described in this hierarchy can be in fact larger than Q(n, m, k) since the former set is defined for the probabilities given by with commutativity imposed on the measurements of different parties, i.e., ( E xi,ai i , E xj,aj j = 0 for i = j). In other words, the strict requirement of a tensor product structure of the operators of different parties is replaced with the requirement of only commutation between these operators. Since Q(n, m, k) ⊆ Q pr (n, m, k), the exclusion of the non-local vertices from Q pr (n, m, k) is sufficient to exclude them from the quantum set.
In the hierarchy, one considers sets of sequences of products of projection operators : i 1 , i 2 ∈ [n]}, etc. The convex sets Q l corresponding to different levels of the hierarchy are then constructed by testing for the existence of a certificate Γ l associated to the set of operators S l using a semi-definite program. The certificate Γ l corresponding to level l is a |S l | × |S l | matrix whose rows and columns are indexed by the operators in set S l , and is a complex Hermitian positive semi-definite matrix that satisfies the following constraints on its entries as well as constraints resulting from operator relations, Γ l Q,R = Γ l S,T if Q † R = S † T . The lack of existence of a positive semi-definite certificate corresponding to any level of the hierarchy implies the exclusion of the box from the quantum set. Recently, one of the levels of the hierarchy labeledQ(n, m, k) has been highlighted as the almost quantum set [21], owing to the fact that it was proven to satisfy most (all but the principle of information causality [4], there being numerical evidence in support of this too) of the reasonable information-theoretic principles designed to pick out quantum theory from among all no-signaling theories. The setQ is an intermediate level of the hierarchy associated to the set of operatorsS = 1 1 {E x1,a1 1 . . . E xn,an n : a i ∈ A i , x i ∈ X i }. As we shall see,Q(n, m, k) already excludes all the nonlocal no-signaling vertices.
Recently, a relationship was discovered between Bell scenarios, more general contextuality scenarios, and graph theory via the use of orthogonality graphs [6,10] and hypergraphs [11]. The orthogonality graph G B cor-responding to the Bell scenario B(n, m, k) is constructed as follows. Each event (a v |x v ) of the Bell scenario corresponds to a distinct vertex v of the graph and two such vertices are connected by an edge in the graph if the corresponding events are locally orthogonal [6], i.e.
Equivalently, each operator of the form E x1,a1 ). An orthonormal representation of a graph G with vertex set V and edge set E is a set of unit vectors {|u i : i ∈ V } where |u i ∈ R N for some N , |u i = 1 for all i ∈ V and u i |u j = 0 for (i, j) ∈ E (note that this differs from the original representation in [22] where non-adjacent vertices were assigned orthogonal vectors). Based on orthonormal representations, one constructs the theta body TH(G) of the graph which is a convex set introduced in [22] in relation to the graphtheoretic problem of finding a maximum weight stable set (a stable set is a set of mutually disconnected vertices) of the graph. We refer to [22,23] for details.

Definition ([22]). For any graph
We are now ready to provide the proof for the main theorem stated in the text. Theorem 1. For some (arbitrary) (n, m, k), let P nl be a vertex of the no-signaling polytope NS(n, m, k) such that P nl / ∈ C(n, m, k). Then P nl / ∈ Q(n, m, k).
Proof. We first examine the precise relation betweenQ and the set TH(G), noting that a relation in terms of (non-orthogonality) hypergraphs was proven in [11]. To do this, we first note that as shown in [6], normalization and no-signaling constraints on a box are equivalent to (maximum) clique inequalities on the orthogonality graph, where a clique inequality is an inequality of the form i∈c |P i ≤ 1 for some clique c in the graph (a clique is a set of mutually connected vertices). The fact that normalization is a clique inequality that is saturated for the orthogonality graph is clear. The fact that no-signaling can also be formulated as a maximum clique inequality (that is also saturated) is seen as follows [6]. Using the normalization constraints, the nosignaling constraints can be rewritten as aj P (a 1 , . . . , a j , . . . , a n |x 1 , . . . , x j , . . . , x n ) + a ′ j {ã1,...ãj−1,ãj+1...ãn} = {a1,...,aj−1,aj+1,...,an} P (ã 1 , . . . , a ′ j , . . . ,ã n |x 1 , . . . , x ′ j , . . . , x n ) = 1 ∀j, x j , x ′ j , x i (i = j) (13) Now, it is readily seen that all the events occurring in the above expression are locally orthogonal, so that the no-signaling constraints are maximum clique inequalities that are saturated for the orthogonality graph G B ; however we also note that not every maximum clique inequality of G B corresponds to a no-signaling or a normalization condition. We now define the subset T H (c) (G) ⊂ T H(G) as the set of boxes in TH(G) for which the maximum cliques c corresponding to the normalization and no-signaling constraints have i∈c | ψ|u i | 2 = 1, i.e., defining C n,ns as the set of maximum cliques corresponding to the normalization and no-signaling constraints, we have the following defini- Proof. The setQ of boxes P = {P (a|x)} is characterized by the existence of a certificate ΓQ which is aD ×D complex Hermitian positive semi-definite matrix with the following constraints on its entries acting on the systems of different parties i 1 and i 2 . As noted in [20], the question of existence of the complex Hermitian positive semi-definite matrix ΓQ is equivalent to the existence of a real symmetric positive semi-definite matrix defined as 1 2 (ΓQ + ΓQ * ). The set Q then consists of those boxes for which the certificate