\betaegin{equation}gin{document}

\thetaitle{On the tightness of correlation inequalities with no quantum violation}

\alphauthor{Ravishankar \sigmaurname{Ramanathan}}
\epsilonmail{ravishankar.r.10@gmail.com}
\alphaffiliation{National Quantum Information Center of Gda\'nsk,  81-824 Sopot, Poland}
\alphaffiliation{Institute of Theoretical Physics and Astrophysics, University of Gda\'{n}sk, 80-952 Gda\'{n}sk, Poland}
\alphauthor{Marco T\'ulio Quintino}
\alphaffiliation{D\'epartement de Physique Th\'eorique, Universit\'e de Gen\`eve, 1211 Gen\`eve, Switzerland}
\alphauthor{Ana Bel\'en Sainz}
\alphaffiliation{H. H. Wills Physics Laboratory, University of Bristol, Tyndall Avenue, Bristol, BS8 1TL, United Kingdom}
\alphauthor{Gl\'aucia Murta}

\alphaffiliation{Departamento de Fisica, Universidade Federal de Minas Gerais, Caixa Postal 702, 30123-970, Belo Horizonte, MG, Brazil}
\alphaffiliation{QuTech, Delft University of Technology, Lorentzweg 1, 2628 CJ Delft, The Netherlands}

\alphauthor{Remigiusz Augusiak}
\alphaffiliation{Center for Theoretical Physics, Polish Academy of Sciences, Aleja Lotnik\'ow 32/46, 02-668 Warsaw, Poland}

\betaegin{equation}gin{abstract}

We study the faces of the set of quantum correlations, i.e., the Bell and noncontextuality inequalities without any quantum violation.  
First, we investigate the question whether every proper (tight) Bell inequality for two parties, other than the trivial ones from positivity, normalization and no-signaling can be violated by quantum correlations, i.e., whether the classical Bell polytope or the smaller correlation polytope share any facets with their respective quantum sets. To do this, we develop {a recently derived bound on the quantum value of linear games} based on the norms of game matrices to give a simple sufficient condition to identify linear games with no quantum advantage. {Additionally we show how this bound can be extended to the general class of unique games.} We then show that the paradigmatic examples of correlation Bell inequalities with no quantum violation, namely the non-local computation games do not constitute tight Bell inequalities, not even for the correlation polytope. We also extend this to an arbitrary prime number of outcomes for a specific class of these games. 
We then study the faces in the simplest CHSH Bell scenario of binary dichotomic measurements, and identify edges in the set of quantum correlations in this scenario.

Finally, we relate the non-contextual polytope of single-party correlation inequalities with the cut polytope $CUT(\nuabla G)$, where $G$ denotes the compatibility graph of observables in the contextuality scenario and $\nuabla G$ denotes the suspension graph of $G$. We observe that there exist tight non-contextuality inequalities with no quantum violation, and furthermore that this set of inequalities is beyond those implied by the Consistent Exclusivity principle.
\epsilonnd{abstract}

\muaketitle
\sigmaection{Introduction}

In recent years there has been a growing interest in non-local quantum correlations, i.e., 
correlations generated in a Bell-type experiment which violate Bell inequalities \cite{Bell}.
On the one hand, their existence shows that quantum and classical mechanics 
fundamentally depart one from another, and, on the other hand, 
non-locality has been turned into a powerful resource allowing 
to perform tasks not known in classical physics. These are, for instance,
generation of cryptographic key that is secure against 
even post-quantum eavesdroppers \cite{securekey}, reduction of communication complexity \cite{CommCompl}, or
true randomness certification and amplification \cite{rand}.
{Therefore, for fundamental reasons as well as for applications,}  detection and characterization of the set of non-local correlations is of utmost importance in quantum information theory. 
{This not only restricts to correlations in Bell scenarios but also applies to general contextuality ones \cite{KS,AB,AFLS}, 
where contextual behaviours (i.e. conditional probability distributions stronger than allowed {by deterministic noncontextual models})
prove to be a necessary resource for quantum computation \cite{contcomp}.}

{In a bipartite Bell scenario, }we consider correlations between two parties Alice and Bob, who can perform $m_A, m_B$ measurements, and obtain $d_A, d_B$ outcomes respectively. A box $\muathcal{P}$ describes the set of conditional probability distributions $P(a,b|x,y)$ that can be obtained in such a Bell experiment, $\muathcal{P}$ is usually expressed as a real vector in $\muathbb{R}^{m_A m_B d_A d_B}$. The constraints of normalization, no-signaling and non-negativity of probabilities {imposed on $\muathcal{P}$ define the set of no-signaling boxes which constitutes a polytope in a reduced dimension. } Contained within the no-signaling polytope is the set of interest, namely that of the quantum correlations obtainable {from measurements in a bipartite quantum state,} and inside this set is the classical polytope of correlations realizable in a local realistic theory. For most of the applications mentioned previously and for fundamental reasons, we are interested in studying how the set of quantum correlations fits in between the classical and no-signaling polytopes. 

A proper (tight) Bell inequality is a facet of the classical polytope, which is not also a facet of the no-signaling one, i.e., one that does not merely rephrase the no-signaling, positivity and normalization conditions. In \cite{Gill}, Gill posed as an open question whether every proper (tight) Bell inequality is violated by quantum correlations. As a variant of the question, Avis et al. \cite{AII06} ask whether the correlation polytope in the binary outcome scenario (the set of correlations $\langle A_i B_j \rhoangle$ observable in a two-party experiment, not including the local terms $\langle A_i \rhoangle$, $\langle B_j \rhoangle$ themselves) shares any facets in common with the set of quantum correlations. In \cite{GYNI} it was shown that if three or more parties are involved in the Bell experiment, there exist multipartite tight Bell inequalities that do not allow for quantum violation. {These inqualities} led to the formulation of an information-theoretic principle called local orthogonality {(LO) \cite{LO}}, which serves to bound the set of correlations realizable in a physical theory. 
{In the bipartite case  LO reduces to the non-signaling condition, therefore bringing no nontrivial constraints to the set of bipartite correlations, and 
 all of the tight bipartite Bell inequalities found so far in the literature (as listed in \cite{facets}) are known to be violated in quantum theory. }
 {In the multipartite scenario it remains an open problem whether all facet-defining nontrivial Bell inequalities are of the local orthogonality form.}
{Let us remark that, beyond the scope of this paper, other questions on how the quantum set fits between the classical and no-signaling ones have also been intensively studied; in particular unbounded violations of Bell inequalities, i.e., large separations between the classical and quantum sets \cite{unb-viol}.} 

{The questions of how the quantum set of behaviours fits between the classical one and those explained by more general theories is one main research topic as well in contextuality \cite{KS}. Contextuality is a curious phenomenon that also signals the 
nonclassicality of quantum theory, and may be understood as a more general case of nonlocality 
scenarios that includes measurements on a single system \cite{AB, AFLS} 
 (there exist other inequivalent approaches to contextuality that will not be discussed in this work like \thetaextit{preparation and measurement contextuality by
Spekkens \thetaextit{et. al.} 
\cite{spekkens})}. Different aspects of the phenomenon have been explored in the literature \cite{adanrays,AQB+13,horodecki_measure}, 
and special interest has been put into understanding the boundary between quantum and more general theories as well. One example of 
this is the extension of LO to contextuality scenarios, called Consistent Exclusivity principle, that serves to bound
(although not tightly) the set of quantum behaviours. In particular, there is the similar open question of whether every facet of the 
classical polytope that coincides with one of the quantum set is of the CE form. }
 

In this paper, we first study the question of whether there are tight two-party Bell inequalities with no quantum violation. In addition to the binary outcome correlation Bell inequalities explored in \cite{AII06}, we also study their natural generalization to more outcomes known as linear games. We develop a simple sufficient condition for these games to 
exhibit no quantum violation based on the singular vectors of their game matrices \cite{RAM}, with which we identify new inequalities with this property.  A well-known class of two-party inequalities that do not allow for quantum violation are those arising from another information-theoretic principle, called no-NLC (no advantage in non-local computation) \cite{NLC}. 
Its generalization to the case of more outcomes was considered in \cite{RAM}. We show by an explicit decomposition into other valid inequalities 
of the classical and the correlation polytopes that a broad set of these inequalities do not constitute facets of both these polytopes. 
{Finally, we
also study the question {of tight inequalities} in the single-party scenario, namely non-contextuality inequalities with binary outcomes. 
{On the one hand, we identify the non-contextual polytope  that arises from the compatibility graph representing the measurements in the
experiment with a well explored object in  computer science named \thetaextit{cut polytope} \cite{DL97}. We use this relation to construct
many tight non-contextuality inequalities with no quantum violation.} On the other hand, we further characterise the polytope of behaviours 
that satisfy CE in this example, and show that not all tight non-contextuality inequalities with no quantum violation are among its facets.}

\sigmaection{Preliminaries}
\label{Preliminaries}

In this section, we establish the preliminary notions concerning the classical and no-signaling polytopes, and the notion of tight Bell inequalities. 
{Then we present the basics of contextuality scenarios and their sets of behaviours.}

\piaragraph{Polytopes.} 
Consider
a linear space $\muathbb{R}^n$ whose elements we denote by $\muathbf{p}$.
A convex polytope $P \sigmaubseteq \muathbb{R}^n$ (see \cite{Schrijver,comp-geom}) is the convex hull of a finite number of points in $\muathbb{R}^n$.
Alternatively, $P$ is a bounded polyhedron, where $Q\sigmaubset \muathbb{R}^n$ is a polyhedron if there is a 
system of finitely many inequalities $\thetaextbf{C} \cdot \thetaextbf{q} \leq \thetaextbf{b}$ such that 
$Q = \{ \thetaextbf{q} | \thetaextbf{C} \cdot \thetaextbf{q} \leq \thetaextbf{b}\}$. Here, $\muathbf{C}$ is a $m\thetaimes n$ 
matrix and $\muathbf{b}\in\muathbb{R}^m$ with $m$ being the number of inequalities.
   
Let $P \sigmaubseteq \muathbb{R}^{n}$, $\thetaextbf{c} \in \muathbb{R}^n$ and $b \in \muathbb{R}$. An inequality $\thetaextbf{c} \cdot \thetaextbf{p} \leq b$ is valid for $P$ if it holds for all $\thetaextbf{p} \in P$.  The hyperplane $H_{(\thetaextbf{c}, b)}$ given as

\betaegin{equation}gin{equation}
H_{(\thetaextbf{c}, b)} = \{ \thetaextbf{p} \in \muathbb{R}^n | \thetaextbf{c} \cdot \thetaextbf{p} = b\}
\epsilonnd{equation} 

is said to be a supporting hyperplane of the polytope $P$ if $\muax\{ \thetaextbf{c} \cdot \thetaextbf{p} | \thetaextbf{p} \in P\} = b$. Then, 
$F$ is a face of $P$ if $F = P$ or $F = P \cap H$ for some supporting hyperplane $H$ of $P$. A set $Q = \{\thetaextbf{p}_1, \deltaots, \thetaextbf{p}_k\} \sigmaubseteq \muathbb{R}^n$ is affinely dependent iff there exist $\lambda_1, \deltaots, \lambda_k \in \muathbb{R}$ not all zero such that $\sigmaum_{i=1}^{k} \lambda_i \thetaextbf{p}_i = \thetaextbf{0}$ and $\sigmaum_{i=1}^{k} \lambda_i = 1$. The dimension of $P$ is the smallest dimension of its affine hull, i.e., $dim(P) := \muax\{|Q| | Q \sigmaubseteq P, \thetaext{Q affinely independent}\}$. $F$ is a facet of $P$ if $F$ is a face and $dim(F) = dim(P)  - 1$. An inequality $\thetaextbf{c} \cdot \thetaextbf{p} \leq b$ is said to be facet-defining (or essential) for $P$ if $H_{(\thetaextbf{c}, b)}\cap P $ is a facet of $P$. Let $\thetaextbf{C} \cdot \thetaextbf{p} \leq \thetaextbf{b}$ be a system of valid inequalities for polytope $P$ such that for each facet $F$ of $P$, there is a row $\thetaextbf{c}_i \cdot \thetaextbf{p} \leq \thetaextbf{b}_i$ of $\thetaextbf{C} \cdot \thetaextbf{p} \leq \thetaextbf{b}$ such that $F = P \cap H_{\thetaextbf{c}_i, \thetaextbf{b}_i}$. Then $P = \{ \thetaextbf{p} \in \muathbb{R}^n | \thetaextbf{C} \cdot \thetaextbf{p} \leq \thetaextbf{b}\}$.

\piaragraph{Bell scenario and sets of correlations.} 
As explained in the introduction, we consider correlations between two parties Alice and Bob, who can perform $m_A, m_B$ measurements, and obtain $d_A, d_B$ outcomes respectively. Such a scenario is usually referred to as $(2,m_A,m_B,d_A,d_B)$. The correlations the parties 
generate in this way is described by the collection 
$\muathcal{P} = \{P(a,b|x,y)\}$ of conditional probabilities $P(a,b|x,y)$ that 
Alice and Bob obtained $a$ and $b$ upon performing the $x$-th and
$y$-th measurement, respectively with $a (b)=0,\ldots,d_A-1 (d_B - 1)$ and $x (y)=1,\ldots,m_A (m_B)$.
The usual way of dealing with such a collection is to treat it as a vector  $\thetaextbf{P}$ from $\muathbb{R}^{m_A m_B d_A d_B}$.
Now, in addition to the normalization conditions $\sigmaum_{a,b} P(a,b|x,y) = 1$ for all $x,y$, the no-signaling conditions

\betaegin{equation}gin{equation}\label{NS1}
\sigmaum_{a}P(a,b|x,y)=\sigmaum_{a}P(a,b|x',y)
\epsilonnd{equation}

for any $b$, $y$ and any pair $x\nueq x'$, and

\betaegin{equation}gin{equation}\label{NS2}
\sigmaum_{b}P(a,b|x,y)=\sigmaum_{b}P(a,b|x,y')
\epsilonnd{equation}

for any $a$, $x$, and any pair $y\nueq y'$, are imposed.  The set of boxes $\muathcal{P}$ {satisfying normalization and no-signaling} thus forms a convex polytope known as the no-signaling polytope $\muathcal{N}$ of dimension $D = m_A m_B (d_A - 1) (d_B - 1) + m_A (d_A -1) + m_B (d_B - 1)$.

In quantum theory Alice and Bob share some quantum state $\rhoho$ acting on some  Hilbert space $\muathcal{H}_A\omegaegatimes\muathcal{H}_B$, and perform POVM measurements on their share of this state. The set $\muathcal{Q}$ of quantum boxes so obtained forms a convex set if one does not constrain the dimension of $\rhoho$. 
In general, however, 
the boundary of $\muathcal{Q}$ remains unknown and is very difficult to determine
(see nevertheless, \cite{Masanes} for results in the two-input two-output scenario). Interestingly, some of the elements of $\muathcal{Q}$ 
can be generated by the parties without using any quantum state; in fact, the only 
resource needed to obtain them is some shared classical information,
also referred to as \thetaextit{shared randomness},
represented by a random variable $\lambda$ with probability distribution $p(\lambda)$.
Such correlations are those for which 

\betaegin{equation}gin{equation}\label{local}
P(a,b|x,y)=\sigmaum_{\lambda}p(\lambda)P_A(a|x,\lambda)P_B(b|y,\lambda).
\epsilonnd{equation}

and are said to admit a \thetaextit{local hidden variable} model. For simplicity we also call them \thetaextit{local} or \thetaextit{classical} {correlations}.
Here $P_A(a|x,\lambda)$ and $P_B(b|y,\lambda)$ are local probability distributions.

Local correlations again form a convex set, this time, however, 
it is a polytope $\muathcal{L}$, whose vertices 
are local deterministic correlations $\{P_{\muathrm{det}}(a,b|x,y)\}$ 
for which $P_{\muathrm{det}}(a,b|x,y)=P_A(a|x)P_B(b|y)$ 
and all local probabilities $P_A(a|x), P_B(b|y)\in\{0,1\}$ with $x (y)=1,\ldots,m_A (m_B)$
and $a (b)=1,\ldots,d_A (d_B)$. 
Since the work of Bell \cite{Bell}, we know that $\muathcal{L} \sigmaubsetneq \muathcal{Q}$, i.e., 
there exist quantum correlations $\muathbf{p}\in \muathcal{Q}$, termed non-local, 
which cannot be written as in Eq. (\rhoef{local}). 

And subsequently, from the work  of Popescu and Rohrlich \cite{PR} we have that the chain of inclusions
$\muathcal{L} \sigmaubsetneq \muathcal{Q}\sigmaubsetneq \muathcal{N}$ holds true. That is, 
local correlations form a proper subset of the set of quantum correlations, while the latter forms 
a proper subset of all nonsignaling correlations. There exist quantum correlations
that are not local, usually termed non-local, as well as nonsignaling correlations which are not quantum.

The Bell inequalities are linear inequalities 

\betaegin{equation}gin{equation}\label{dupa}
\muathbf{c}\cdot\muathbf{P}\leq b
\epsilonnd{equation}

that constrain the local set $\muathcal{L}$, and their violation 
signals non-locality. Here, $\muathbf{c}\in\muathbb{R}^N$ is some constant vector and 
$b$ stands for the so-called classical bound defined as
$b=\muax_{\muathbf{p}\in P_{\muathrm{L}}}\muathbf{c}\cdot\muathbf{P}$. 
As explained above, owing to the fact that $\muathcal{L}$ is a polytope, a finite amount of
such Bell inequalities is sufficient to fully characterize it. These correspond
to the facets of $\muathcal{L}$ and are usually called
\thetaextit{tight Bell inequalities} for the local Bell polytope. 

To check then whether a given Bell inequality (\rhoef{dupa})
defines a facet of the corresponding local polytope of dimension $D$
one needs to show that the classical deterministic boxes 
$\{P_{\muathrm{det}}(a,b |x,y)\}$ that achieve value $b$ 
for the inequality span an affine subspace of dimension $D-1$. 

In the study of tight two-party Bell inequalities, another local polytope has also been of interest namely the correlation polytope in the binary 
outcome scenario $(2,m_A,m_B,2,2)$. This is the polytope of possible two-party correlations $\langle A_x B_y \rhoangle$ achievable in a local realistic 
theory where $A_x, B_y$ denote dichotomic {events and $\langle A_x B_y \rhoangle=P(a=b|x,y)-P(a\nueq b|x,y)$}. While the local Bell polytope in this scenario 
is of dimension $m_A m_B + m_A + m_B$, the correlation polytope is of smaller dimension $m_A m_B$ by virtue of not considering the local
terms $\langle A_x \rhoangle$ and $\langle B_y \rhoangle$. In this binary output situation, there is a rich literature relating the local Bell polytope, 
the correlation polytope and the set of quantum correlations to convex sets studied in polyhedral combinatorics \cite{AII06, AHW10}.     

\piaragraph{{Contextuality scenarios and sets of behaviours.}} 

	Here we will focus on contextuality scenarios arising from compatibility graph scenarios, like the one discussed by Klyachko \cite{klyachko1,klyachko2} and equivalent to the marginal problem \cite{planeta,fritz}.
	
	{There are two ways to approach contextuality scenarios, both starting from a hypergraph but giving the vertices and edges a different interpretation. One starts from a compatibility hypergraph, where its vertices represent measurements and the hyperedges the sets of compatible measurements.  The other starts from an events  hypergraph, where vertices represent measurement outcomes and the hyperedges the measurements   \cite{AFLS}. Both include Bell scenarios as a particular family of general contextuality ones. Here we will briefly review the concepts relevant to this work.}

{Within the hypergraph approach of \cite{AFLS}, a contextuality scenario is defined as a hypergraph $H=(V,E)$ whose vertices $v \in V$ correspond to the events of the scenario, and where the hyperedges $e = \{v_1 , \cdots , v_k \} \in E$ (subsets of $V$) are the measurements of the scenario, with the vertices as the allowed measurement outcomes. In addition, every measurement is assumed to be complete, in the sense that every behaviour over the contextuality scenario $H$ satisfies the normalization condition $\sigmaum_{v \in e} P(v) = 1$ for every $e$, where $P(v)$ denotes the probability that outcome $v$ is obtained given that the measurement $e$ is performed. As classical behaviours we consider the ones that are explained via deterministic non-contextual (NC) hidden variable models and convex combinations of them; i.e. a behavior is classical if it can be explained by a convex sum of the ones where only one outcome happens with certainty for each measurement. The set of all classical behaviours forms the non-contextual polytope. Its facets are referred to as tight noncontextuality inequalities.}

{On a similar footing, a behaviour is quantum whenever the probabilities arise as $P(v) =\muathrm{tr}(\rhoho P_v)$, where $\rhoho$ and $\{P_v\}_{v \in V}$ are hermitian operators over some Hilbert space $\muathcal{H}$, and the projectors $P_v$ satisfy the following conditions: $\sigmaum_{v \in e} P_v = \omegaegapenone_{\muathcal{H}}$ for every measurement $e$ and $P_v \pierp P_u$ when $v$ and $u$ belong to the same measurement. }

{Within this framework, a natural notion of exclusiveness among events arises: two events which are outcomes of the same measurement are naturally exclusive. Then, in the language of graph theory, two distinct vertices $u$ and $v$ are orthogonal (denoted by $u \pierp v$) if there exists a hyperedge $e \in E$ such that $u \in e$ and $v \in e$. A proposed principle to bound the set of quantum models for contextuality scenarios is {\it Consistent Exclusivity} (CE) \cite{Henson, AFLS}, also refered to as {\it Global Exclusivity} \cite{cabello}. Here, we focus only on the constraints that it imposes over one copy of the system, which are expresed as follows: 
\betaegin{equation}gin{definition}\label{defCE}
A probabilistic model $P$ on a contextuality scenario $H$ satisfies CE$^1$ when $\sigmaum_{v \in S} P(v) \leq 1$ for every set $S \sigmaubset V$ of mutually orthogonal events. 
\epsilonnd{definition} 
We refer to the conditions in Def. \rhoef{defCE} as CE$^1$ inequalities, and usually denote each them by the set of orthogonal events $S$ that gives rise to it. It can be easily verified that, just like the Local Ortogonality inequalities \cite{LO}, the CE$^1$ inequalities also cannot be violated in quantum theory \cite{AFLS}.

{The other successful approach to contextuality \cite{AB} focuses instead on the set of measurements that are performed on the (possibly multipartite) system and the compatibility relations among them. Within this language, a compatibility hypergraph  is one where its vertices represent measurable quantities (namely, measurements) and hyperedges represent quantities that can be jointly measured i.e., compatible measurements. In addition, the hypergraph can be equipped with vertex weights denoting the number of possible outcomes of the corresponding measurement. Here we will focus on dichotomic observables, and hence simplify the scenario to unweighted hypergraphs.}

{Within this viewpoint, an assignment of probabilities to measurement outcomes (denoted as well by behaviour) is well defined as long as it satisfies the `no disturbance' condition (also referred to as No-Signaling in Bell scenarios, or sheaf-condition in \cite{AB}); that is, the (marginal) probability for obtaining an outcome when performing a measurement should not depend on the choice of other compatible measurements that are performed alongside.}

{Given a contextuality scenario with compatibility graph $G(V,E)$, a noncontextual deterministic behaviour is an assignment of an outcome to each measurement $M_i$ which does not depend on the other measurements that are compatible with it. This assignment then tells what are the outcomes that occur with certainty whenever compatible measurements are performed. When the scenario consists of dichotomic measurements, such deterministic assignments are equivalently determined by the assignment of a value $\pim 1$ to the {\it single correlators} $\muean{M_i} = P(1\varepsilonrti) - P(-1 \varepsilonrti)$. Moreover, in the case where the sets of compatible measurements have two elements (i.e. the compatibility structure is given by  a graph), the object of interest is the conditional probability distribution (a.k.a behaviour) $p(ab|ij)$, where $M_i$ and $M_j$ are compatible. A behaviour that satisfies the no-disturbance principle is equivalently represented by the single correlators $\muean{M_i}$ and its \thetaextit{full correlators} $\muean{M_i M_j} := P(a = b \varepsilonrti , j) - P(a\nueq b \varepsilonrti , j)$ \cite{GisinCG, AQB+13}.  On the one hand, the non-contextual (NC) polytope of behaviours (for a compatibility graph $G(V,E)$) is defined as the convex hull of deterministic noncontextual ones in $G(V,E)$. On the other hand, another object of interest is the \thetaextit{full-correlation} non-contextual polytope (FC-NC). This is indeed the projection of the NC polytope onto the subspace defined by the full correlators $\muean{M_i M_j}$. Facets of the full-correlation polytope are also facets of the complete one, and a violation of a full-correlation inequality implies a violation of a standard non-contextual one.}

\quad

The interest in finding facet-defining inequalities with no quantum advantage can simply be stated as an interest in finding the largest dimensional 
face of the set of quantum correlations that one can describe analytically. Such faces contribute to an enhanced understanding of this set that one may 
then use to identify information-theoretic principles underlying quantum correlations {for both Bell and general contextuality scenarios}. 

\sigmaection{Identifying inequalities with no quantum advantage}
\label{SECIII}
In this section, we study the question of how one may identify inequalities with no quantum advantage. For the binary outcome correlation inequalities, 
the quantum violation of the inequality is known to be calculable by a semidefinite program \cite{Tsirelson,Wehner}\cite{footnote1}.
{In Ref.~\cite{RKM+14} we proposed a necessary and sufficient condition for the lack of quantum advantage for these inequalities (XOR games).}
A simpler sufficient but not necessary condition was also given, namely that the game matrices have maximum singular vectors with $\pim 1$ entries 
only. Here, we extend the condition {of no quantum advantage} to the many-outcome scenario of linear games \cite{RAM, Hastad},
which are a class of the well-known unique games \cite{Khot}. 

\thetaextit{A bound on the quantum value of three outcome unique games.}
Unique games are a generalization of \thetaextsc{xor} games to arbitrary output alphabet and are defined as follows:
\betaegin{equation}gin{mydef}
A two-player unique game $(\thetaextsl{g}^{u}, q)$ is one where two players Alice and Bob receive questions $x$, $y$ from sets $Q_A$ and $Q_B$ respectively, chosen from a probability distribution $q(x,y)$ by a referee. They reply with respective answers $a, b \in [d]$. The game is defined by a winning constraint $b = \pii_{(x,y)}(a)$ for some set of permutations $\{\pii_{(x,y)} \} \sigmaubset \muathcal{S}_d$, where $\muathcal{S}_d$ denotes the permutation group on $d$ elements.  
\epsilonnd{mydef}
A sub-class of the unique games are the \thetaextsc{linear} games, where the output alphabet $[d]$ is identified with an Abelian group $G$ of size $d$, i.e., $a, b \in (G, +)$; and the winning constraint is given by $a + b = f(x,y)$ where $+$ denotes the addition operation in the Abelian group $G$ and $f : Q_A \thetaimes Q_B \rhoightarrow G$. The special case of the cyclic groups $\muathbb{Z}_d$ (integers under addition modulo $d$) is called an \thetaextsc{xor}-d game \cite{RAM}, and the further restriction to $\muathbb{Z}_2$ defines the \thetaextsc{xor} game \cite{Tsirelson}. The class of \thetaextsc{xor} games forms a highly interesting class of Bell inequalities that are also called ``correlation Bell inequalities" where the correlation function $\muathit{E}_{x,y} = \sigmaum_{k=0,1} (-1)^k P(a \omegaegaplus b \; \thetaext{mod 2} = k|x,y)$.

The value of the unique game is given by the expression 
\betaegin{equation}gin{equation}
\omegaegamega(\thetaextsl{g}^{u}) = \sigmaum_{\sigmaubstack{x \in Q_A \\ y \in Q_B}} \sigmaum_{a,b \in G} q(x,y) V(a,b|x,y) P(a,b|x,y),
\epsilonnd{equation}
where $V(a,b|x,y) = 1$ if $b =\pii_{(x,y)}(a)$ and $0$ otherwise. 
The maximum classical value of the game (the maximum over all deterministic assignments of $a, b$ or their convex combinations) is denoted $\omegaegamega_c(\thetaextsl{g}^{u})$, the value of the game achieved by a quantum strategy (POVM measurements on a shared entangled state of arbitrary Hilbert space dimension) is denoted $\omegaegamega_q(\thetaextsl{g}^{u})$, while the value achieved by no-signaling strategies (where neither party can signal their choice of input using the correlations) is denoted $\omegaegamega_{ns}(\thetaextsl{g}^{u})$. These games have been studied \cite{Hastad, Khot} in the context of hardness of approximation of several important optimization problems, in attempts to identify the existence of polynomial time algorithms to approximate the optimum solution of the problem to within a constant factor. For every unique game, $\omegaegamega_{ns}(\thetaextsl{g}^{u}) = 1$ since a no-signaling box exists that wins the game. Such a box is defined by the entries $P(a,b|x,y) = 1/d$ if $b = \pii_{(x,y)}(a)$ and $0$ otherwise for all input pairs $(x,y)$, this strategy clearly wins the game, and is no-signaling since the output distribution seen by each party is fully random for every input, i.e., $P(a|x) = P(b|y) = 1/d$.  

\sigmaubsection{Bounds on quantum value for unique games}

Let us first bound the quantum value of a unique game with three outputs using generalized norms from a set of matrices, bounds for more outcome unique games and their applications will be discussed elsewhere. 
\betaegin{equation}gin{prop}\label{thm2}
\label{norm-bound}
The quantum value of a three output unique game $\thetaextsl{g}^u$ with input sets $ Q_A, Q_B$  can be bounded as 
\betaegin{equation}gin{equation}
\omegaegamega_q(\thetaextsl{g}^{u}) \leq \frac{1}{3} \left[ 1 + \sigmaqrt{m_Am_B} \sigmaum_{k=1,2} \| {\sigmaf{P}}hi^{H}_k, {\sigmaf{P}}hi^{(01)H}_k \|_{\thetaext{gen}} \rhoight].
\epsilonnd{equation}

where 

\betaegin{equation}gin{equation}\label{gamematrix1}
{\sigmaf{P}}hi^{H}_{k} = \sigmaum_{(x,y) \in Q_A \thetaimes Q_B} q^H(x,y) \zetaeta^{-k f(x,y)} | x \rhoangle \langle y|
\epsilonnd{equation}

and

\betaegin{equation}gin{equation}\label{gamematrix2}
{\sigmaf{P}}hi^{(01) H}_{k} = \sigmaum_{(x,y) \in Q_A \thetaimes Q_B} q^{(01) H}(x,y) \zetaeta^{k f(x,y)} |x \rhoangle \langle y|
\epsilonnd{equation}
are the game matrices, with $\zetaeta= \epsilonxp(2 \pii i/3)$, $q^H(x,y)$ and $q^{(01) H}(x,y)$ are probability distributions as specified in the proof bellow, and 
$\| {\sigmaf{P}}hi^{H}_k, {\sigmaf{P}}hi^{(01)H}_k \|_{\thetaext{gen}}$
is defined as

\betaegin{equation}gin{eqnarray}
\label{eq:gen-norm}
&&\| {\sigmaf{P}}hi^{H}_k, {\sigmaf{P}}hi^{(01)H}_k \|_{\thetaext{gen}} := \nuonumber \\
&& \; \; \muax \{ \| {\sigmaf{P}}hi^{H}_k x_1 +  {\sigmaf{P}}hi^{(01)H}_k x_2 \| : \| x_1\| = 1, \|x_2 \|=1 \}.\nuonumber\\
\epsilonnd{eqnarray}
\epsilonnd{prop}

\betaegin{equation}gin{proof}
Consider a quantum strategy given by projective measurements $\{ {\sigmaf{P}}i_{x}^{a} \}$ for Alice and $\{ \Sigmaigma_{y}^{b} \}$ for Bob performed on a pure quantum state $ | {\sigmaf{P}}si \rhoangle \in \muathbb{C}^{d} \omegaegatimesimes \muathbb{C}^d$ for some arbitrary dimension $d$. Let us introduce the generalized correlators $\langle A_{x}^{k} \omegaegatimesimes B_{y}^{l} \rhoangle$ defined via the Fourier transform of the probabilities $P(a,b|x,y)$ as
\betaegin{equation}gin{equation}
\langle A_{x}^{k} \omegaegatimesimes B_{y}^{l} \rhoangle = \sigmaum_{a, b = 0}^{2} \zetaeta^{-(a k + b l)} P(a,b|x,y),
\epsilonnd{equation}  
where $\zetaeta = \epsilonxp(2 \pii i/3)$ and the unitary operators $A_{x}^{k}$ and $B_y^l$ are defined as
\betaegin{equation}gin{equation}
A_{x}^k = \sigmaum_{a = 0}^{2} \zetaeta^{-a k} {\sigmaf{P}}i_{x}^{a} \; \; \thetaext{and} \; \; B_{y}^l = \sigmaum_{b=0}^2 \zetaeta^{- b l} \Sigmaigma_{y}^b.
\epsilonnd{equation}

There are six possible permutations that enter the game, namely the elements of group $\muathcal{S}_3 := \{ e, (01), (02), (12), (012), (021)\}$ where the permutations are denoted as usual in the cycle notation, i.e., $(01) = (0 \rhoightarrow 1, 1 \rhoightarrow 0, 2 \rhoightarrow 2)$, etc. We consider the maximal abelian subgroup $H$ of $\muathcal{S}_3$ ($H < \muathcal{S}_3$) given by $H := \{e, (012), (021) \}$. The corresponding left coset obtained by the action of $(01)$ on $H$ is given by $(01) H = \{(01), (12), (02)\}$. In this simple case of three outputs, we immediately see that the  permutation constraints in the game $b = \pii_{x,y}(a)$ for $\pii_{x,y} \in H$ are simply constraints of the form $a \omegaegaminus b \; \thetaext{mod 3} = f^{\omegaegaminus}_{\pii_{x,y}}(x,y)$ with the correspondence $(f^{\omegaegaminus}_{e}(x,y) = 0, f^{\omegaegaminus}_{(012)}(x,y) = 2, f^{\omegaegaminus}_{(021)}(x,y) = 1)$. Similarly, permutation constraints $b = \pii_{x,y}(a)$ for $\pii_{x,y} \in (01) H$ correspond to constraints of the form $a \omegaegaplus b \; \thetaext{mod 3} = f^{\omegaegaplus}_{\pii_{x,y}}(x,y)$. We have that 
\betaegin{equation}gin{eqnarray}
&&P(b = \pii_{x,y}(a) | x,y) = P(a \omegaegaminus b = f^{\omegaegaminus}_{\pii_{x,y}} | x, y) \nuonumber \\
&& \; \; = \frac{1}{9} \sigmaum_{k, l=0}^{2} \sigmaum_{a=0}^{2} \zetaeta^{a (k+l) + f^{\omegaegaminus}_{\pii_{x,y}}(x,y) l} \langle A_x^k \omegaegatimesimes B_y^l \rhoangle  \nuonumber \\
&& \; \; = \frac{1}{3} \sigmaum_{k=0}^{2} \zetaeta^{- k f^{\omegaegaminus}_{\pii_{x,y}}} \langle A_x^k \omegaegatimesimes B_y^{-k} \rhoangle, \; \; \forall \pii_{x,y} \in H,
\epsilonnd{eqnarray}  
and similarly, 
\betaegin{equation}gin{eqnarray}
&&P(b = \pii_{x,y}(a) | x,y) = P(a \omegaegaplus b = f^{\omegaegaplus}_{\pii_{x,y}} | x, y) \nuonumber \\
&& \; \; = \frac{1}{9} \sigmaum_{k, l=0}^{2} \sigmaum_{a=0}^{2} \zetaeta^{a (k-l) + f^{\omegaegaplus}_{\pii_{x,y}}(x,y) l} \langle A_x^k \omegaegatimesimes B_y^l \rhoangle \nuonumber \\
&&\; \; = \frac{1}{3} \sigmaum_{k=0}^{2} \zetaeta^{k f^{\omegaegaplus}_{\pii_{x,y}}} \langle A_x^k \omegaegatimesimes B_y^k \rhoangle, \; \; \forall \pii_{x,y} \in (01) H. 
\epsilonnd{eqnarray}  
Now, let us define vectors $|\alphalpha_{k} \rhoangle, |\betaegin{equation}ta_{k} \rhoangle$ as
\betaegin{equation}gin{eqnarray}
&&|\alphalpha_{k} \rhoangle := \sigmaum_{x \in Q_A} \left((A_{x}^{k})^{\deltaagger} \omegaegatimesimes {\omegaegaperatorname{id}}entity \rhoight) |{\sigmaf{P}}si \rhoangle \omegaegatimesimes |x \rhoangle, \; \; \nuonumber \\
&&|\betaegin{equation}ta_{l} \rhoangle := \sigmaum_{y \in Q_B} \left({\omegaegaperatorname{id}}entity \omegaegatimesimes B_{y}^{k} \rhoight) |{\sigmaf{P}}si \rhoangle \omegaegatimesimes |y \rhoangle,
\epsilonnd{eqnarray}
and let us consider the "game matrices" defined in Eqs. (\rhoef{gamematrix1})  (\rhoef{gamematrix2}), where

$q^H(x,y) = q(x,y)$ for input pairs such that the winning constraint for this input pair comes from $H$, $\pii_{x,y} \in H$ and $q^H(x,y) = 0$ for the remaining input pairs. The distribution $q^{(01) H}(x,y)$ is defined analogously (as equal to $q(x,y)$ for pairs where the winning constraint comes from $(01) H$ and $0$ otherwise). Consequently, note that the matrices ${\sigmaf{P}}hi^{H}_{k}$ and ${\sigmaf{P}}hi^{(01) H}_{k}$ are such that $({\sigmaf{P}}hi^{H}_{k})_{i,j} \nueq 0$ only if  $({\sigmaf{P}}hi^{(01) H}_{k})_{i,j} = 0$ and vice versa. 

Now, we observe that the quantum value of the unique game can be written as
\betaegin{equation}gin{widetext}
\betaegin{equation}gin{eqnarray}
\omegaegamega_q(\thetaextsl{g}^{u}) &=& \frac{1}{3} \sigmaum_{k=0}^{2} \left[ \sigmaum_{(x,y) \in Q_A \thetaimes Q_B} q^H(x,y) \zetaeta^{-k f^{\omegaegaminus}_{\pii_{x,y}}} \langle A_x^k \omegaegatimesimes B_y^{-k} \rhoangle + q^{(01) H}(x,y) \zetaeta^{k f^{\omegaegaplus}_{\pii_{x,y}}(x,y)} \langle A_x^k \omegaegatimesimes B_y^k \rhoangle \rhoight] \nuonumber \\
& = & \frac{1}{3} \left[ 1 + \langle \alphalpha_1 | \muathbf{1} \omegaegatimesimes {\sigmaf{P}}hi^{H}_1 | \betaegin{equation}ta_2 \rhoangle +  \langle \alphalpha_1 | \muathbf{1} \omegaegatimesimes {\sigmaf{P}}hi^{(01) H}_1 | \betaegin{equation}ta_1 \rhoangle +\langle \alphalpha_2 | \muathbf{1} \omegaegatimesimes {\sigmaf{P}}hi^{H}_2 | \betaegin{equation}ta_1 \rhoangle + \langle \alphalpha_2 | \muathbf{1} \omegaegatimesimes {\sigmaf{P}}hi^{(01)H}_2 | \betaegin{equation}ta_2 \rhoangle \rhoight] \nuonumber \\
&\leq & \frac{1}{3} \left[1 +  \sigmaqrt{m_Am_B}\| {\sigmaf{P}}hi^{H}_1, {\sigmaf{P}}hi^{(01)H}_1 \|_{\thetaext{gen}} +  \sigmaqrt{m_Am_B} \| {\sigmaf{P}}hi^{H}_2, {\sigmaf{P}}hi^{(01)H}_2 \|_{\thetaext{gen}} \rhoight].
\epsilonnd{eqnarray} 
\epsilonnd{widetext}
Here, $\| {\sigmaf{P}}hi^{H}_k, {\sigmaf{P}}hi^{(01)H}_k \|_{\thetaext{gen}}$ is defined as in Eq. (\rhoef{eq:gen-norm}).
Compare with the usual spectral norm of a matrix $\| A \| = \muax \{ \|A x \| : \| x \| = 1 \}$. 
\epsilonnd{proof}

For more outcome unique games, the above bound can be generalized by identifying maximal abelian subgroups of the group of permutations appearing in the game, this approach will be pursued elsewhere. On the other hand,
when restricted to the scenario of linear games with $m_A, m_B$ inputs, the above method of proof recovers the bound that we derived in \cite{RAM}, namely
\betaegin{equation}gin{equation}
\label{bound}
\omegaegamega_q(\thetaextsl{g}^{l}) \leq \frac{1}{d} \left[ 1 + \sigmaqrt{m_A m_B} \sigmaum_{k=1}^{d-1} \| {\sigmaf{P}}hi_k \| \rhoight]
\epsilonnd{equation} 

with game matrices given by 

\betaegin{equation}gin{equation}\label{Ziobro}
{\sigmaf{P}}hi_k = \sigmaum_{x=1}^{m_A} \sigmaum_{y=1}^{m_B} q(x,y) \zetaeta^{k f(x,y)} | x \rhoangle \!\langle y |.
\epsilonnd{equation}

The advantage of formulating bounds on the quantum value in terms of game matrices is that it allows for an easy sufficient condition to recognize and construct games with no quantum advantage.  
\betaegin{equation}gin{prop}
\label{prop:qeqc}
Let $G$ be a linear game with $d$ outputs and let ${\sigmaf{P}}hi_1, \deltaots, {\sigmaf{P}}hi_{d-1}$ denotes its corresponding game matrices. If the maximum left and right singular vectors $|u_1 \rhoangle, |v_1 \rhoangle$ of ${\sigmaf{P}}hi_1$ are composed of roots of unity entries, and if in addition the maximum singular vectors of ${\sigmaf{P}}hi_k$ are obtained from $|u_1 \rhoangle, |v_1 \rhoangle$ by the substitution $\zetaeta \rhoightarrow \zetaeta^k$, then $\omegaegamega_q(G) = \omegaegamega_c(G)$.  
\epsilonnd{prop}
\betaegin{equation}gin{proof}
As in the proof of the norm-based bounds on the quantum value, we use the generalized correlators $\langle A_x^k \omegaegatimesimes B_y^l \rhoangle$ to express the probabilities $P(a,b|x,y)$ as
\betaegin{equation}gin{equation}
P(a,b|x,y) = \frac{1}{d^2} \sigmaum_{k,l=0}^{d-1} \zetaeta^{a k + b l} \langle A_x^k \omegaegatimesimes B_y^l \rhoangle,
\epsilonnd{equation} 
so that the quantum success probability in the linear game can be expressed as
\betaegin{equation}gin{equation}
\omegaegamega_q^{(l)}(G) = \muax_{\{{\sigmaf{P}}i_{x}^a \}, \{\Sigmaigma_{y}^b \}}  \frac{1}{d} \sigmaum_{k=0}^{d-1} \left[ \sigmaum_{x=1}^{m_A} \sigmaum_{y=1}^{m_B} q(x,y) \zetaeta^{k f(x,y)} \langle A_x^k \omegaegatimesimes B_y^k \rhoangle \rhoight],
\epsilonnd{equation}
with $A_x^k$ and $B_y^l$ given in general by 

\betaegin{equation}gin{equation}
A_x^k = \sigmaum_{a=0}^{d-1} \zetaeta^{-a k} {\sigmaf{P}}i_{x}^a,\quad
B_y^l = \sigmaum_{b=0}^{d-1} \zetaeta^{- b l} \Sigmaigma_{y}^b.
\epsilonnd{equation}

In terms of the matrices ${\sigmaf{P}}hi_k$ defined in Eq. (\rhoef{Ziobro}) and the vectors $| \alphalpha_k \rhoangle = \sigmaum_{x=1}^{m_A} ((A_x^k)^{\deltaagger} \omegaegatimesimes \thetaextbf{1})| \pisi \rhoangle \omegaegatimesimes |x \rhoangle$, $| \betaegin{equation}ta_l \rhoangle = \sigmaum_{y=1}^{m_B} (\thetaextbf{1} \omegaegatimesimes B_y^l)| \pisi \rhoangle \omegaegatimesimes |y \rhoangle$, we can equivalently write
\betaegin{equation}gin{equation}
\omegaegamega_q^{(l)}(G) =  \muax_{\{| \alphalpha_k \rhoangle \}, \{| \betaegin{equation}ta_k \rhoangle \}} \frac{1}{d} \left[1 + \sigmaum_{k=1}^{d-1} \langle \alphalpha_k | \muathbf{1} \omegaegatimesimes {\sigmaf{P}}hi_k | \betaegin{equation}ta_k \rhoangle \rhoight].
\epsilonnd{equation}

The classical success probability $\omegaegamega_c^{(l)}(G)$ is achieved by a deterministic strategy where Alice returns a set of deterministic outcomes $\{\hat{a}_x\}$ and similarly Bob returns $\{ \hat{b}_y \}$ upon receiving their respective inputs $x$ and $y$. Noting that $P_c(a \omegaegaplus_d b = f(x,y) | x,y) = \frac{1}{d} \sigmaum_{k=0}^{d-1} \zetaeta^{k(f(x,y) - \hat{a}_x - \hat{b}_y)} = 1$ if $f(x,y) = \hat{a}_x \omegaegaplus_d \hat{b}_y$ and $0$ otherwise, 
we see that $\omegaegamega_c^{(l)}(G)$ can be written as
\betaegin{equation}gin{equation}
\omegaegamega_c^{(l)}(G) = \muax_{\{\hat{a}_x\}, \{\hat{b}_y\}} \frac{1}{d} \sigmaum_{k=0}^{d-1} \left[ \sigmaum_{x=1}^{m_A} \sigmaum_{y=1}^{m_B} q(x,y) \zetaeta^{k (f(x,y) - \hat{a}_x - \hat{b}_y)} \rhoight].
\epsilonnd{equation}
It is then readily seen that when the conditions stated in the proposition are met, the left and right singular vectors $|u_1 \rhoangle$ and $|v_1 \rhoangle$ of ${\sigmaf{P}}hi_1$ corresponding to the maximum singular value define a consistent classical strategy that achieves the bound on the quantum value.  
\epsilonnd{proof}

The sufficient condition in Proposition \rhoef{prop:qeqc} is useful in constructing novel inequalities where quantum theory offers no advantage over classical theories. An example of a linear game with four outputs with no quantum advantage (that does not belong to the $NLC_d$ class explained below) is as follows. 
\[
{\sigmaf{P}}hi_{ex} = (1/56) \betaegin{equation}gin{bmatrix}
    7       & -3 & 3 i & i \\
    -3      & 7 & i & 3 i \\
    -3 i & - i & 7 & -3  \\
    - i  & -3 i & -3 & 7
\epsilonnd{bmatrix}\]
This game matrix ${\sigmaf{P}}hi_{ex}$ has maximum eigenvector $[-i,i,-1,1]$, and a classical strategy where Alice and Bob ouput as their four outputs $[1,3,0,2]$ and $[3,1,0,2]$ respectively achieves the quantum success probability in the game. 

\sigmaubsection{Non-local computation games}

The paradigmatic class of inequalities with no quantum advantage are given by the non-local computation games \cite{NLC}.
These concern the 
distributed computation of a boolean function 

$f:\{0,1\}^n\muapsto\{0,1\}$

mapping $n$ bits to a single bit. Consider
that two parties, Alice and Bob, receive input strings of length $n$, 
$\muathbf{x}_n=(x_1,\ldots,x_n)$ and $\muathbf{y}_n=(y_1,\ldots,y_n)$, respectively. 
Each bit $x_i$ and $y_i$ is distributed with equal probability, ensuring that 
neither Alice nor Bob is able to correctly learn the bit $z_i=x_i\omegaegaplus_2 y_i$, where $\omegaegaplus_2$ stands for addition modulo two. 
Now, in order to 
perform distributed computation of the function $f$, Alice 
and Bob must output bits $a$ and $b$ such that 

\betaegin{equation}gin{equation}
\label{eq:binary-nlc-fn}
a\omegaegaplus b=f(x_1\omegaegaplus y_1,\ldots,x_n\omegaegaplus y_n)\epsilonquiv f(\muathbf{z}_n).
\epsilonnd{equation}

To this end, they can agree on any strategy beforehand, however, after receiving
inputs, no communication can be exchanged between them.
Alice's and Bob's common aim is to maximize, for a 
given input probability distribution 

\betaegin{equation}gin{equation}
\label{eq:binary-nlc-pr}
p(\muathbf{x}_n,\muathbf{y}_n)=(1/2^n)p(\muathbf{x}_n\omegaegaplus_2 \muathbf{y}_n)\epsilonquiv(1/2^n)p(\muathbf{z}_n)
\epsilonnd{equation}

the average probability of success in this task:

\betaegin{equation}gin{equation}
\omegaegamega=\frac{1}{2^n}\sigmaum_{\thetaextbf{x}_n,\thetaextbf{y}_n\in\{0,1\}^n}p(\muathbf{z}_n)p(a\omegaegaplus b=f(\muathbf{z}_n)|\muathbf{x}_n,\muathbf{y}_n).
\epsilonnd{equation}

In what follows we will denote this task by $NLC_2$.

One immediately realizes that the above game, fits very well with
the Bell scenario outlined in Sec. \rhoef{Preliminaries}. Now, $x,y=1,\ldots,2^n$ (encoded into 
$n$-bit strings $\muathbf{x}_n$ and $\muathbf{y}_n$) are the choices of measurements
that Alice and Bob can perform on some quantum state $\rhoho$
(which due to the convexity argument can be taken pure), while 
$a$ and $b$ stand for the measurements outcomes. 
It is then natural to ask 
how local $\muathcal{L}$ and quantum correlations $\muathcal{Q}$
perform at $NLC_2$, and, in particular, whether quantum theory provides any advantage in this task. Quite surprisingly, it turns out 
that this is not the case and for no quantum state and measurements 
the success probability $\omegaegamega$ can surpass the maximal success probability
over all classical correlations $\omegaegamega_{\muathrm{c}}=\muax_{\muathbf{p}\in P_{\muathrm{L}}}\omegaegamega$ \cite{NLC}. In other words, 
for any such task, $\omegaegamega_{\muathrm{q}}=\omegaegamega_{\muathrm{c}}$ with
$\omegaegamega_{\muathrm{q}}=\muax_{\muathbf{p}\in \muathcal{Q}}\omegaegamega$.

On the other hand, there exist super-quantum correlations 
obeying the no-signaling principle that can still surpass $\omegaegamega_{\muathrm{q}}$. 
So, there might exist a more general theory, respecting the 
no-signaling principle, which at this task can be more powerful than
quantum theory. This observation, being so striking, was then exploited 
to propose a principle to pick out the quantum $\muathcal{Q}$
from $\muathcal{N}$: \thetaextit{quantum correlations are those that perform no better than
classical ones at the $NLC_2$ task}.

In Ref. \cite{NLC} only games with binary outcomes 
were studied and they posed as an open question the consideration of functions $f$ with multi-bit outputs as well as functions with 
higher input and output alphabets. Such generalization was recently proposed 
in Ref. \cite{RAM}. Let us briefly recall it here. To this end, let us 
consider a function $f:\muathbb{Z}_d^n\muapsto\muathbb{Z}_d$ mapping $n$
dits to a single one with $\muathbb{Z}_d=\{0,\ldots,d-1\}$. Imagine then that 
Alice and Bob are given string of $n$ \thetaextit{dits}, $\muathbf{x}_n$ and $\muathbf{y}_n$, 
and their aim is to provide dits $a,b\in\muathbb{Z}_d$ such that $a\omegaegaplus_d b=f(\muathbf{z}_n)$, 
where $z_i=x_i\omegaegaplus_d y_i$ and $\omegaegaplus_d$ denotes addition modulo $d$. We have demonstrated
in Ref. \cite{RAM} that for the class of functions $f$ given by 

\betaegin{equation}gin{eqnarray}\label{condition}
f(\muathbf{z}_n)&=&g(x_1\omegaegaplus_d y_1
,\ldots,x_{n-1}\omegaegaplus_d y_{n-1})\cdot (x_n\omegaegaplus_d y_n)\nuonumber\\
&\epsilonquiv & g(\muathbf{x}_{n-1}\omegaegaplus_d \muathbf{y}_{n-1})\cdot (x_n\omegaegaplus_d y_n)
\epsilonnd{eqnarray}

where $g:\muathbb{Z}_d^{n-1}\muapsto \muathbb{Z}_d$ is any function, 
and for probability distributions 

\betaegin{equation}gin{equation}\label{condition2}
p(\muathbf{x}_n,\muathbf{y}_n)
=\frac{1}{d^{n+1}}p(\muathbf{x}_{n-1}\omegaegaplus_d\muathbf{y}_{n-1}),
\epsilonnd{equation}

quantum correlations perform no better than classical one in 
maximizing the average success probability of winning this game

\betaegin{equation}gin{equation}
\omegaegamega=\frac{1}{d^{n}}\sigmaum_{\muathbf{x}_n\muathbf{y}_n\in\muathbb{Z}_d^n}p(\muathbf{z}_n)p(a \omegaegaplus_d b=f(\muathbf{z}_n)|\muathbf{x}_n,\muathbf{y}_n).
\epsilonnd{equation}

Below we denote games defined by Eqs. (\rhoef{condition})
and (\rhoef{condition2}) by $NLC_d$.

Interestingly, as we will see below, the restriction to functions given 
by Eq. (\rhoef{condition}) is vital for the proof that quantum correlations 
do not provide any advantage over the classical ones in $NLC_d$. In fact, otherwise
it is not difficult to find an example of a non-local computation task for 
which $\omegaegamega_{\muathrm{q}}> \omegaegamega_{\muathrm{cl}}$ if only $d\gammaeq 3$. To this end, 
let us consider the case of $d=3$ and $n=1$ (each Alice and Bob receive a single trit
$x$ and $y$, respectively) and a function $f:\muathbb{Z}_3\muapsto \muathbb{Z}$
given by

\betaegin{equation}gin{equation}
f(z)=\left\{
\betaegin{equation}gin{array}{ll}
1,& z=2\\
0,& z=0,1.
\epsilonnd{array}
\rhoight.
\epsilonnd{equation}

Assuming then that $p(x,y)=(1/3)p(x\omegaegaplus_3 y)=1/9$, it is not difficult to 
realize that the maximal classical value of this game amounts to $\omegaegamega_{\muathrm{cl}}=2/3$ 
(just by algorithmically checking all possible deterministic strategies). 
On the other hand, the game matrices 
corresponding to the above game are

\betaegin{equation}gin{equation}\label{exampleNLC3}
{\sigmaf{P}}hi_1=\frac{1}{9}\left(
\betaegin{equation}gin{array}{ccc}
1 & 1 & \omegaegamega\\
1 & \omegaegamega &1 \\ 
\omegaegamega &1 &1
\epsilonnd{array}
\rhoight)
\epsilonnd{equation}

and ${\sigmaf{P}}hi_2={\sigmaf{P}}hi_1^*$, where the asterisk stands for the standard complex conjugation.
The operator norms of these matrices are $\|{\sigmaf{P}}hi_1\|=\|{\sigmaf{P}}hi_2\|=\sigmaqrt{3}$, and consequently, our bound 
(\rhoef{bound}) implies that the maximal quantum value is upper-bounded as 
$\omegaegamega_{\muathrm{q}}\leq (1/3)[1+2\sigmaqrt{3}/3]\alphapprox 0.7182$.
Finally, taking the two-qutrit maximally entangled state 
$\kappaet{\pisi_3^+}=(1/\sigmaqrt{3})\sigmaum_{i=0}^2\kappaet{ii}$ and optimizing 
over one-qutrit measurements on Alice and Bob sites, one finds 
that the maximal value is lower bounded as $\omegaegamega_{\muathrm{q}}\gammaeq 0.7124$, 
thus, clearly, $\omegaegamega_{\muathrm{q}}>\omegaegamega_{\muathrm{cl}}$ for this game. 
In fact, the numerical investigations of \cite{Liang} show that the lower bound in fact gives the quantum value for this game 
\cite{footnote2}. 
This example in the three-outcome scenario at first glance appears rather surprising in view
of the result of Ref. \cite{NLC} stating that all binary non-local computation tasks
exhibit no quantum advantage, however there is a clear reason for this. For $d \gammaeq 3$, one has functions of the form $(x_n \omegaegaplus_d y_n)^2$ which are equivalent to the $\thetaext{CHSH}_d$ game $f_{\thetaext{CHSH}_d}(x_n, y_n) = x_n \cdot y_n$ under local relabellings. Quantum theory gives an advantage in the $\thetaext{CHSH}_d$ game so that we see that the restriction of the functions to the condition in Eq.(\rhoef{condition}) is necessary. 

\sigmaection{Tightness of $NLC_d$}
In this section, we investigate the tightness of the paradigmatic class of two-party Bell inequalities with no quantum advantage, namely the $NLC_d$ inequalities.  
{In \cite{GYNI} the authors have shown that $NLC_2$ are not facet defining inequalities for the case of two and three input bits. However the proof of non-tightness for any number of input bits was left as an open problem. }

Recall that non-local computation is a game 
in which Alice and Bob receive $n$-dit strings $\muathbf{x}_n$ and $\muathbf{y}_n$
with $x_i,y_i\in\muathbb{Z}_d$ and must output dits $a$ and $b$ such that 
$a\omegaegaplus_d b=f(\muathbf{x}_{n}\omegaegaplus_d \muathbf{y}_{n})$
for some function $f$ fulfilling the condition (\rhoef{condition}). We additionally 
assume that the probability distribution $p(\muathbf{x}_n,\muathbf{y}_n)$ is given by Eq. (\rhoef{condition2}).
These games give rise to Bell inequalities which can explicitly be 
stated as

\betaegin{equation}gin{equation}\label{inequalities}
\frac{1}{d^n}\sigmaum_{\muathbf{x}_n,\muathbf{y}_n\in\muathbb{Z}_d^n}p(\muathbf{z}_n)
p(a\omegaegaplus_d b=f(\muathbf{z}_n)|\muathbf{x}_n,\muathbf{y}_n)\leq \omegaegamega_{\muathrm{c}}.
\epsilonnd{equation}

As already explained, one approach to show that an inequality
does not define a facet of the local polytope is to prove that there are fewer than $D$ affinely 
independent classical deterministic boxes saturating it, i.e. achieving the classical value. Here, we use an alternative approach based on the following straightforward observation, 
namely that the inequality is non-tight if we can exhibit a decomposition of the inequality into other inequalities that define supporting hyperplanes for the polytope. 

\betaegin{equation}gin{lemma}
\label{facet-lem}
If $P$ is a polytope, then the intersection of two faces of $P$ is a face of $P$. 
A facet of $P$ cannot be obtained as the intersection of two or more different faces of $P$. 
\epsilonnd{lemma}

\betaegin{equation}gin{proof}

Suppose $F$ and $G$ are two faces of $P$, so there are corresponding supporting hyperplanes $H_{(\thetaextbf{c}_{F}, b_{F})}$ and $H_{(\thetaextbf{c}_{G}, b_{G})}$ given as
\betaegin{equation}gin{eqnarray}
H_{(\thetaextbf{c}_{F}, b_{F})} &:=& \{\thetaextbf{p} | \thetaextbf{c}_{F} \cdot \thetaextbf{p} = b_{F}\} \nuonumber \\
H_{(\thetaextbf{c}_{G}, b_{G})} &:=& \{\thetaextbf{p} | \thetaextbf{c}_{G} \cdot \thetaextbf{p} = b_{G} \},
\epsilonnd{eqnarray}
such that $F = P \cap H_{(\thetaextbf{c}_{F}, b_{F})}$ and $G = P \cap H_{(\thetaextbf{c}_{G}, b_{G})}$. The halfspace 
\betaegin{equation}gin{equation}
\{ \thetaextbf{p} | (\thetaextbf{c}_{F} + \thetaextbf{c}_{G}) \cdot \thetaextbf{p} \leq b_{F} + b_{G}\}
\epsilonnd{equation}
contains $P$ and for any $\thetaextbf{p} \in P$, we have that $(\thetaextbf{c}_{F} + \thetaextbf{c}_{G}) \cdot \thetaextbf{p} = b_{F} + b_{G}$ only when both $\thetaextbf{c}_{F} \cdot \thetaextbf{p} = b_{F}$ and $\thetaextbf{c}_{G} \cdot \thetaextbf{p} = b_{G}$.  
Hence the intersection of $F$ and $G$ is the intersection of $P$ with the hyperplane $H_{(\thetaextbf{c}_{F} + \thetaextbf{c}_{G}, b_{F} + b_{G})}$, and so $F \cap G$ is a face of $P$. If $F \cap G$ is a facet of $P$, then by the above argument, we have that $F$ and $G$ must also be facets of $P$. The affinely independent boxes $\thetaextbf{p}$ that define $F \cap G$ also define $F$ and $G$ and so $F = G$. This shows that a facet cannot be obtained as the intersection of two (or more) differing faces. 

\epsilonnd{proof}

\sigmaubsection{$NLC_2$ XOR games} 
Our first aim now is to prove that none of the $NLC$ inequalities is tight in the case $d=2$, that is, 
such Bell inequalities do not give rise to facets of the corresponding local 
polytope. The NLC inequalities are also the interesting case of the XOR games that would serve as paradigmatic candidates 
for facets shared by the elliptope and the the cut polytope for the bipartite graph in the question posed by Avis et al. \cite{AII06} (cf. Section \rhoef{sec:cut-poly}). We will later see how to generalize this to arbitrary prime $d$ but for a restricted class of functions. 

Note that the $NLC$ games with $n=1$ (i.e., functions $k \cdot (x_n \omegaegaplus y_n) + \deltaelta$ with $k,\deltaelta \in \{0, 1\}$) 
are uninteresting because there is a simple classical strategy that wins these games, namely $a(x_n) = k \cdot x_n $ and $b(y_n) = k \cdot y_n+ \deltaelta$ so that $w_c = w_q = w_{ns}$ for them. The interesting games are with $n > 1$ where $w_c = w_q < w_{ns} = 1$. The fact that $w_{ns} = 1$ simply follows from the fact that these games belong to the class of XOR games, for which a no-signaling strategy always exists to win the game, namely one where $P(a,b | \thetaextbf{x}_n, \thetaextbf{y}_n) = \frac{1}{2}$ when $a \omegaegaplus_2 b = f(\thetaextbf{x}_n, \thetaextbf{y}_n)$ and $0$ otherwise. 

\betaegin{equation}gin{thm}
The binary outcome non-local computation game $NLC$ inequalities for arbitrary functions $f(x_1 \omegaegaplus y_1, \deltaots, x_n \omegaegaplus y_n)$ (Eq.(\rhoef{eq:binary-nlc-fn})) and arbitrary probability distributions $p(\thetaextbf{x}_n, \thetaextbf{y}_n) = \frac{1}{2^n}p(x_1 \omegaegaplus y_1, \deltaots, x_n \omegaegaplus y_n)$ (Eq.(\rhoef{eq:binary-nlc-pr})) do not define facets of the local Bell polytope or the correlation polytope for any number $n > 1$ of input bits. 
\epsilonnd{thm}
\betaegin{equation}gin{proof}
The idea of the proof is to exhibit a decomposition of the NLC game Bell inequality for function $f(x_1 \omegaegaplus y_1, \deltaots, x_n \omegaegaplus y_n)$ and probability distribution $\frac{1}{2^n} p(x_1 \omegaegaplus y_1, \deltaots, x_n \omegaegaplus y_n)$ as a sum of inequalities that are valid for the Bell polytope and the correlation polytope so that by Lemma \rhoef{facet-lem}, the NLC inequality cannot define a facet of either of these polytopes. More precisely, we identify two subgames $NLC^{x_1 = 0}_{\thetaext{sub}}$ and $NLC^{x_1 = 1}_{\thetaext{sub}}$ that define inequalities $\thetaextbf{c}_{NLC_0} \cdot \thetaextbf{p} \leq \omegaegamega_{c}(NLC^{x_1 = 0}_{\thetaext{sub}})$ and $\thetaextbf{c}_{NLC_1} \cdot \thetaextbf{p} \leq \omegaegamega_{c}(NLC^{x_1 = 1}_{\thetaext{sub}})$ that themselves can be violated in quantum theory, but which sum up to the NLC Bell inequality which admits no quantum violation, i.e., 
\betaegin{equation}gin{eqnarray}
\label{eq:nlc-decomp}
\thetaextbf{c}_{NLC} &=& \thetaextbf{c}_{NLC_0} + \thetaextbf{c}_{NLC_1} \nuonumber \\
\omegaegamega_{c}({NLC}) &=& \omegaegamega_{c}(NLC^{x_1 = 0}_{\thetaext{sub}}) + \omegaegamega_{c}(NLC^{x_1 = 1}_{\thetaext{sub}}). 
\epsilonnd{eqnarray}

We define $NLC^{x_1 = j}_{\thetaext{sub}}$ as the subgame of the $NLC$ game with $x_1$ fixed to the value $j$ for $j=0,1$. In other words, $NLC^{x_1 = j}_{\thetaext{sub}}$ corresponds to the function $f(j \omegaegaplus y_1, x_2 \omegaegaplus y_2, \deltaots, x_n \omegaegaplus y_n)$ and probability distribution $p(j, x_2, \deltaots, x_n, y_1, \deltaots, y_n) = \frac{1}{2^n}p(j \omegaegaplus y_1, x_2 \omegaegaplus y_2, \deltaots, x_n \omegaegaplus y_n)$. Notice that the maximum algebraic and no-signaling value of the $NLC^{j}_{\thetaext{sub}}$ Bell inequality is $\frac{1}{2}$. Clearly, by definition $\thetaextbf{c}_{NLC} = \sigmaum_{j=0,1} \thetaextbf{c}_{NLC_j}$, our aim is now to show that $\omegaegamega_{c}(NLC^{x_1 = j}_{\thetaext{sub}}) = \frac{1}{2} \omegaegamega_{c}({NLC})$ so that Eq.(\rhoef{eq:nlc-decomp}) holds. We do this by showing that the optimal classical strategy for the subgame $NLC^{x_1 = j}_{\thetaext{sub}}$ is the same as the optimal classical strategy for the game $NLC$ restricted to the case $x_1 = j$.  

\betaegin{equation}gin{lemma}
\label{lem:class-strat-nlc}
$\omegaegamega_{c}(NLC^{x_1 = j}_{\thetaext{sub}}) = \frac{1}{2} \omegaegamega_{c}({NLC})$.
\epsilonnd{lemma}
\betaegin{equation}gin{proof}
The game matrix ${\sigmaf{P}}hi^{x_1 =j}$ for the subgame $NLC^{x_1 = j}_{\thetaext{sub}}$ is given by the entries
\betaegin{equation}gin{eqnarray}
{\sigmaf{P}}hi^{x_1 = j}_{(j,x_2 \deltaots, x_n), (y_1, \deltaots, y_n)} &=& \frac{1}{2^n} (-1)^{f(j \omegaegaplus y_1, x_2 \omegaegaplus y_2, \deltaots, x_n \omegaegaplus y_n)} \nuonumber \\ &&\thetaimes p(j \omegaegaplus y_1, x_2 \omegaegaplus y_2, \deltaots, x_n \omegaegaplus y_n). \nuonumber \\
\epsilonnd{eqnarray} 
We now further consider the subgames $NLC^{x_1 = j, y_1 = k}_{\thetaext{sub}}$ with $k = 0,1$, i.e., with game matrices ${\sigmaf{P}}hi^{x_1 = j, y_1 =k}$ that have entries
\betaegin{equation}gin{eqnarray}
{\sigmaf{P}}hi^{x_1 = j, y_1 =k}_{(j,x_2 \deltaots, x_n), (k,y_2 \deltaots, y_n)} &=& \frac{1}{2^n} (-1)^{f(j \omegaegaplus k, x_2 \omegaegaplus y_2, \deltaots, x_n \omegaegaplus y_n)} \cdot \nuonumber \\ && p(j \omegaegaplus k, x_2 \omegaegaplus y_2, \deltaots, x_n \omegaegaplus y_n). \nuonumber \\
\epsilonnd{eqnarray} 
Now, notice that the subgame $NLC^{x_1 = j, y_1 = k}_{\thetaext{sub}}$ itself has the structure of an NLC game with $n-1$ bits input to each party. This in particular implies by the results of \cite{NLC} that the corresponding game matrix ${\sigmaf{P}}hi^{x_1 = j, y_1 =k}$ is diagonal in the basis formed by the (normalized) Hadamard vectors $|u_l\rhoangle$ with $l = 1, \deltaots, 2^{n-1}$,
\betaegin{equation}gin{eqnarray}
{\sigmaf{P}}hi^{x_1 =j, y_1 = k} = \sigmaum_{l=1}^{2^{n-1}} \lambda^{x_1 =j, y_1 =k}_l | u_l \rhoangle \langle u_l |.
\epsilonnd{eqnarray}
The maximum no-signaling value of the subgame $NLC^{x_1 = j, y_1 = k}_{\thetaext{sub}}$ is 
\betaegin{equation}gin{equation}
\omegaegamega_{ns}(NLC^{x_1 = j, y_1 = k}) = \sigmaum_{x_2, \deltaots, x_n, y_2, \deltaots, y_n} {\sigmaf{P}}hi^{x_1 = j, y_1 =k}_{(j,x_2 \deltaots, x_n), (k,y_2 \deltaots, y_n)}.
\epsilonnd{equation} 
As shown in \cite{NLC} the optimal classical strategy for the game $NLC^{x_1 = j, y_1 = k}_{\thetaext{sub}}$ is given  by the eigenvector $|u_{l_{max}}\rhoangle$ corresponding to the eigenvalue of maximum absolute value $\varepsilonrt \lambda^{x_1 = j, y_1 = k}_{l_{max}} \varepsilonrt$. Alice outputs according to $(-1)^{a(x_1=j, x_2, \deltaots,x_n)} = |u_{l_{max}}\rhoangle_{x_2, \deltaots, x_n}$ and Bob outputs according to $(-1)^{b(y_1=k, y_2, \deltaots,y_n)} = sgn(\lambda^{x_1 =j, y_1 =k}_{l_{max}}) \cdot |u_{l_{max}}\rhoangle_{y_2, \deltaots, y_n}$. We therefore see that the game matrix we are interested in ${\sigmaf{P}}hi^{x_1 = j}$ can be written as

${\sigmaf{P}}hi^{x_1 = j} = \sigmaum_{l=1}^{2^{n-1}} |u_l \rhoangle \langle v_l|$,

where 

$|v_l \rhoangle = |w_l\rhoangle \omegaegatimesimes |u_l\rhoangle$, 

with 

\betaegin{equation}gin{equation}
|w_l \rhoangle = \betaegin{equation}gin{bmatrix} \lambda^{x_1 = j, y_1 =0}_l \\  \lambda^{x_1 = j, y_1 =1}_l \epsilonnd{bmatrix}.
\epsilonnd{equation}

The optimal classical value of the game $NLC^{x_1 = j}_{\thetaext{sub}}$ is given as 
\betaegin{equation}gin{eqnarray}
\omegaegamega_c(NLC^{x_1 = j}_{\thetaext{sub}}) &=& \frac{1}{2}\left[ 1 + \muax_{|s_A \rhoangle, |s_B \rhoangle} \langle s_A | {\sigmaf{P}}hi^{x_1 =j} | s_B \rhoangle \rhoight]\nuonumber \\
&=& \frac{1}{2}\left[1  + \muax_{|s_A \rhoangle, |s_B \rhoangle} \sigmaum_{l=1}^{2^{n-1}} \langle s_A | u_l \rhoangle \langle v_l | s_B \rhoangle\rhoight], \nuonumber \\
\epsilonnd{eqnarray}
where the maximization is over all vectors $|s_A \rhoangle, |s_B \rhoangle$ with $\pim 1$ entries. 

Now, any general strategy vector can be written in terms of the basis formed by the Hadamard vectors, therefore 
the classical strategies $| s_A \rhoangle, |s_B \rhoangle$ can be writen as 
\betaegin{equation}gin{eqnarray}
|s_A \rhoangle &=& \sigmaqrt{2^{n-1}}  \sigmaum_{i_A=1}^{2^{n-1}} \gammaamma^{A}_{i_A} | u_{i_A} \rhoangle, \nuonumber \\
|s_B \rhoangle &=&  \sigmaqrt{2^{n-1}} \sigmaum_{i_B=1}^{2^{n-1}} \sigmaum_{\muu_B=0,1} \gammaamma^{B}_{i_B,\muu_B} \betaegin{equation}gin{bmatrix}
    1 \\ 
    (-1)^{\muu_B}
\epsilonnd{bmatrix}

\omegaegatimesimes |u_{i_B} \rhoangle,
\epsilonnd{eqnarray}
where, $\sigmaum_{i_A} |\gammaamma^{A}_{i_A}|^2=1$ and $\sigmaum_{i_B, \muu_B} |\gammaamma^{B}_{i_B,\muu_B}|^2=1$, 
reflects the fact that deterministic classical strategy vectors for Alice and Bob have norms $2^{n-1}$ and $2^n$ respectively.

Optimizing over such strategies gives us
\betaegin{equation}gin{widetext}
\betaegin{equation}gin{eqnarray}
\label{eq:cl-strat}
\omegaegamega_c(NLC^{x_1 = j}_{\thetaext{sub}})
&\leq& \frac{1}{2} \left[1+2^{n-1} \muax_{\{\gammaamma^{A}_{i_A}\}, \{\gammaamma^{B}_{i_B, \muu_B}\}} \sigmaum_{i_A, i_B, \muu_B} (\gammaamma^{A}_{i_A})^{*} \gammaamma^{B}_{i_B, \muu_B} \deltaelta_{i_A, i_B} \cdot  \left|  \lambda^{x_1 = j, y_1 =0}_{i_B} \pim  \lambda^{x_1 = j, y_1 =1}_{i_B} \rhoight| \rhoight], \nuonumber \\
&\leq &\frac{1}{2} \left[1+2^{n-1} \muax_l \sigmaum_{k=0,1} \varepsilonrt \lambda^{x_1 =j, y_1 =k}_{l} \varepsilonrt \rhoight].
\epsilonnd{eqnarray}
\epsilonnd{widetext}
where we have used the constraints $\sigmaum_{i_A} |\gammaamma^{A}_{i_A}|^2=1$ and $\sigmaum_{i_B, \muu_B} |\gammaamma^{B}_{i_B,\muu_B}|^2=1$ and the Cauchy-Schwarz inequality to bound the value.  

The upper bound in Eq.(\rhoef{eq:cl-strat}) is achieved by choosing a Hadamard strategy, i.e., with 
\betaegin{equation}gin{eqnarray}
\label{eq:cl-strat-2}
| s_A \rhoangle &=& \sigmaqrt{2^{n-1}} | u_l \rhoangle, \nuonumber \\
|s_B \rhoangle &=& \sigmaqrt{2^{n-1}} \betaegin{equation}gin{bmatrix} sgn(\lambda^{x_1 =j, y_1 =0}_{l}) \\ sgn(\lambda^{x_1 =j, y_1 =1}_{l})  \epsilonnd{bmatrix} \omegaegatimesimes |u_l \rhoangle
\epsilonnd{eqnarray}
 for the value of $l$ that maximizes $\sigmaum_{k=0,1} \varepsilonrt \lambda^{x_1 =j, y_1 =k}_{l} \varepsilonrt $. The maximum value thus achieved is 
\betaegin{equation}gin{equation}
\omegaegamega_{c}(NLC^{x_1 = j}_{\thetaext{sub}}) = \frac{1}{2} \left[1 + 2^{n-1} \sigmaum_{k=0,1} \varepsilonrt \lambda^{x_1 =j, y_1 =k}_{l} \varepsilonrt \rhoight].
\epsilonnd{equation} 
Now, the NLC game matrices have the symmetry \cite{NLC} that ${\sigmaf{P}}hi^{x_1 = j, y_1 = k} = {\sigmaf{P}}hi^{x_1 = j \omegaegaplus 1, y_1 = k \omegaegaplus 1}$. 
This implies that the game matrices ${\sigmaf{P}}hi^{x_1 =j, y_1 = k}$ for $j=0,1$ are equivalent to each other under a relabeling of the inputs for Bob, so that we have 
\betaegin{equation}gin{equation}
\label{eq:subgame-eq}
\omegaegamega_{c}(NLC^{x_1 = 0}_{\thetaext{sub}}) = \omegaegamega_{c}(NLC^{x_1 = 1}_{\thetaext{sub}}).
\epsilonnd{equation} 

Moreover, we have shown that the maximum classical value of both the subgames $NLC^{x_1 = j}_{\thetaext{sub}}$ for $j=0,1$ is
achieved by a Hadamard strategy in Eq.(\rhoef{eq:cl-strat-2}), i.e., $|s_A^{j} \rhoangle$ is given by a Hadamard vector of 
length $2^{n-1}$ and $|s_B^{j} \rhoangle$ is given by a Hadamard vector of length $2^n$. As mentioned,
the $NLC$ game matrices have the property that ${\sigmaf{P}}hi^{x_1 = j, y_1 = k} = {\sigmaf{P}}hi^{x_1 = j \omegaegaplus 1, y_1 = k \omegaegaplus 1}$ so 
that $sgn(\lambda^{x_1 =j, y_1 = k}_{l}) = sgn(\lambda^{x_1 =j \omegaegaplus 1, y_1 = k \omegaegaplus 1}_{l})$ giving that Bob's optimal 
strategy vector $|s_B^{j} \rhoangle$ remains the same for $j=0,1$ up to an overall $\pim$ sign. This implies that Alice's optimal
strategy vector $|s_A^{j} \rhoangle$ to achieve $\omegaegamega_c(NLC^{x_1 = j}_{\thetaext{sub}})$ also remains the same for $j=0,1$ up to 
a $\pim$ sign. Since the direct sum of the two Hadamard vectors of length $2^{n-1}$ is a Hadamard vector of length
$2^n$, this defines a Hadamard strategy for both Alice and Bob for the game $NLC$ that achieves the value 
\betaegin{equation}gin{equation}
\label{eq:nlc-opt-strat}
\omegaegamega_c(NLC) \gammaeq \omegaegamega_{c}(NLC^{x_1 = 0}_{\thetaext{sub}}) + \omegaegamega_{c}(NLC^{x_1 = 1}_{\thetaext{sub}}).
\epsilonnd{equation}
Since by definition of a subgame, $\omegaegamega_c(NLC) \leq \omegaegamega_{c}(NLC^{x_1 = 0}_{\thetaext{sub}}) + \omegaegamega_{c}(NLC^{x_1 = 1}_{\thetaext{sub}})$, we have equality in Eq.(\rhoef{eq:nlc-opt-strat}). Then using Eq.(\rhoef{eq:subgame-eq}), we obtain the statement of the Lemma. 

\epsilonnd{proof}
Remark that the quantum value of the games $NLC^{x_1=j}_{\thetaext{sub}}$ themselves does not have to equal to their classical 
value, as the bound in Eq.(\rhoef{eq:cl-strat}) of Lemma \rhoef{lem:class-strat-nlc} is derived through a maximization over 
$\pim 1$ vectors $|s_A \rhoangle, |s_B\rhoangle$ and hence only applies to the classical value and not the quantum value 
of these games. By Lemma \rhoef{lem:class-strat-nlc} then we 
have $\omegaegamega_{c}(NLC^{x_1 = j}_{\thetaext{sub}}) = \frac{1}{2} \omegaegamega_{c}({NLC})$, so that Eq.(\rhoef{eq:nlc-decomp}) holds, giving that the $NLC$ games do not constitute facets of the Bell polytope. Since the decomposition in Eq.(\rhoef{eq:nlc-decomp}) is into XOR game inequalities that are valid for the correlation polytope as well (since they do not involve any local marginal terms), the $NLC$ game Bell inequalities do not constitute facets of the correlation polytope either. 
\epsilonnd{proof}

\sigmaubsection{$NLC_d$ LINEAR games}
Let us now proceed to investigate the tightness of $NLC_d$ games defined by the functions $f$ in Eq.(\rhoef{condition}) and probability distributions $p(\muathbf{x}_n,\muathbf{y}_n)$ given by Eq. (\rhoef{condition2}) for arbitrary prime $d$ and arbitrary $n$ input dits. As we have already seen, this restriction on the functions is necessary for these inequalities to define faces of the quantum set $\muathcal{Q}$. 

As shown in \cite{RAM}, these games are composed of $d$ different subgames that are the building blocks of the $NLC_d$ game matrices ${\sigmaf{P}}hi_k$ with $k \in \{1, \deltaots, d-1\}$. These subgames take the form $G(t) := \{a \omegaegaplus_d b = t \cdot (x \omegaegaplus_d y)\}$ where $t \in \{0, \deltaots, d-1\}$, and they can be readily seen to be won by a classical strategy where Alice outputs $a(x) = t \cdot x$ and Bob outputs $b(y) = t \cdot y$. For $i \in \{0, \deltaots, d-1\}$, let $\lambda_{NLC_d}(i)$ denote the weighted number of times the game $G(i)$ occurs in the first block of $d$ rows of the $NLC_d$ game matrix ${\sigmaf{P}}hi_1$, i.e.
\betaegin{equation}gin{equation}
\label{eq:lambda-d}
\lambda_{NLC_d}(i) :=\sigmaum_{\sigmatackrel{\thetaextbf{y}_{n-1} }{\thetaext{ s.t.} g(y_1, \deltaots, y_{n-1}) = i}} p(y_1, \deltaots, y_{n-1}).
\epsilonnd{equation}
Let $\leftambda_{NLC_d} := \muax_{i \in \{0, \deltaots, d-1\}} \lambda_{NLC_d}(i)$ and let $i_{\thetaext{max}}$ denote the value of $i$ for which this maximum is achieved. Observe that $1/d \leq \leftambda_{NLC_d} \leq 1$. We showed in \cite{RAM} that the optimal classical strategy in the $NLC_d$ game is for Alice to output $a(\muathbf{x}_n) = i_{\thetaext{max}} \cdot x_n$ and for Bob to output $b(\muathbf{y}_n) = i_{\thetaext{max}} \cdot y_n$. Such a strategy achieves the optimal value for the game
\betaegin{equation}gin{equation}
\omegaegamega_c(NLC_d) = \omegaegamega_q(NLC_d) = \frac{1}{d} \left( 1 + (d-1) \leftambda_{NLC_d} \rhoight).
\epsilonnd{equation} 
We now show that for games with $\leftambda_{NLC_d} \gammaeq 1/2$, a decomposition into other valid inequalities for the corresponding Bell polytope can be found so that the $NLC_d$ games with this property also do not define facets of the Bell polytope.

\betaegin{equation}gin{prop}
Any $NLC_d$ game for arbitrary prime $d$ and arbitrary number of input dits $n$ satisfying $\leftambda_{NLC_d} \gammaeq 1/2$ does not define a facet of the corresponding Bell polytope.   
\epsilonnd{prop}
\betaegin{equation}gin{proof}
As before, the proof works by a decomposition into valid face-defining inequalities $NLC_d^{s}$ of the corresponding Bell polytope. The subgames $NLC_d^{s}$ correspond to a function $g(\thetailde{x}_1 \omegaegaplus_d y_1, \deltaots, \thetailde{x}_{n-1} \omegaegaplus_d y_{n-1}) \cdot (x_{n} \omegaegaplus_d y_{n})$ with fixed inputs $\thetailde{x}_i \in \{0,\deltaots, d-1\}$, which for definiteness we fix to $\thetailde{x}_i = 0$ for $i \in \{0, \deltaots, n-1\}$. In other words, in the sub-game $NLC_d^{s}$, Alice receives a single dit input $x_n$ while Bob receives $n$ dits $y_1, \deltaots, y_n$ with probability $\frac{1}{d^{n+1}} p(y_1, \deltaots, y_{n-1})$. The probabilities in the sub-game do not sum to $1$, the maximum no-signaling value of the sub-game is $\frac{1}{d^{n-1}}$ with a factor of $d^2$ coming from the $d^2$ choices of $(x_n, y_n)$ for fixed $(y_1, \deltaots, y_{n-1})$ which form the $d \thetaimes d$ subgames $G(j)$.

Recall that $\leftambda_{NLC_d} := \muax_{i \in \{0, \deltaots, d-1\}} \lambda_{NLC_d}(i)$ where $\lambda_{NLC_d}(i)$ is given by Eq.(\rhoef{eq:lambda-d}). We show now that when $\leftambda_{NLC_d} \gammaeq \frac{1}{2}$, an optimal classical strategy for each of the subgames $NLC_d^{s}$ is identical to the optimal classical strategy for the game $NLC_d$ itself, giving that the Bell inequality corresponding to the game $NLC_d$ can be decomposed into valid face-defining inequalities corresponding to the subgames $NLC_d^{s}$ as in Lemma \rhoef{facet-lem}. As explained earlier, from \cite{RAM} we know that the optimal classical strategy in the $NLC_d$ game is for Alice to output $a(\muathbf{x}_n) = i_{\thetaext{max}} \cdot x_n$ and for Bob to output $b(\muathbf{y}_n) = i_{\thetaext{max}} \cdot y_n$. This strategy for the $NLC_d^{s}$ subgame gives the following lower bound
\betaegin{equation}gin{equation}
\label{eq:class-nlcd-sub}
\omegaegamega_c(NLC_d^{s}) \gammaeq \frac{1}{d^n} \left( 1 +  (d-1) \leftambda_{NLC_d} \rhoight). 
\epsilonnd{equation}

Let us now show that any other classical strategy for $NLC_d^{s}$ does not achieve a larger value than in (\rhoef{eq:class-nlcd-sub}) so that the inequality there is in fact an equality. To do this, we examine classical strategies for the subgames $G(t)$ defined by the winning constraint $\{a \omegaegaplus_d b = t \cdot (x \omegaegaplus_d y)\}$. Fix any $t \in \{0, \deltaots, d-1\}$ and consider any arbitrary deterministic strategy for Alice, i.e., a set of Alice's deterministic outputs $a(x) \in \{0, \deltaots, d-1\}$. For $k \in \{0, \deltaots, d-1\}$, let $\muathcal{A}^{(t)}_k$ denote the set of inputs for which Alice outputs according to an optimal strategy, i.e., $\muathcal{A}^{(t)}_k = \{x : a(x) = t \cdot x \omegaegaplus_d k\}$, let $\muathcal{A}^{(t)}_{k_{\thetaext{max}}}$ denote the set of maximum cardinality $m_t = |\muathcal{A}^{(t)}_{k_{\thetaext{max}}}| = \muax_{k} | \muathcal{A}^{(t)}_k|$. Note that $1 \leq m_t \leq d$.  

Bob's optimal strategy for the game $G(t)$ is then clearly seen to be to output $b(y) = t \cdot y \omegaegaminus_d k$, such a strategy satisfies $m_t d$ of the $d^2$ winning constraints in $G(t)$. Now, given Alice's deterministic strategy, consider game $G(t')$ for any other value of $t' \nueq t$ and the analogous sets $\muathcal{A}^{(t')}_{k'}$ with $m_{t'} = |\muathcal{A}^{(t')}_{{k'}_{\thetaext{max}}}| = \muax_{k'} | \muathcal{A}^{(t')}_{k'}|$. Due to the fact that for any $k' \in \{0, \deltaots, d-1\}$, the equation
\betaegin{equation}gin{equation}
t \cdot x \omegaegaplus_d k_{\thetaext{max}} = t' \cdot x \omegaegaplus_d k',
\epsilonnd{equation} 
is satisfied for at most one value of $x \in \{0, \deltaots, d-1\}$, we have that $m_{t'} \leq d - m_{t} + 1$. This gives that for any deterministic strategy by Bob for the game $G(t')$, at most $(d - m_t + 1) d$ of the $d^2$ winning constraints in $G(t')$ can be satisfied. 

Now the subgame $NLC_d^{s}$ is composed of $\leftambda_{NLC_d}$ blocks of $G(t)$ for some fixed $t$ and $(1- \leftambda_{NLC_d})$ blocks of games $G(t')$ for $t' \nueq t$. The above analysis then implies that any classical deterministic strategy for $NLC_d^{s}$ can at best achieve the value
\betaegin{equation}gin{equation}
\label{eq:class-nlcd-sub2}
\omegaegamega_c(NLC_d^{s}) \leq \frac{1}{d^n} \left[ (d-m_t+1) + \leftambda_{NLC_d} (2 m_t - d - 1) \rhoight].
\epsilonnd{equation}
Comparing Eqs.(\rhoef{eq:class-nlcd-sub2}) and (\rhoef{eq:class-nlcd-sub}), we see that with $\leftambda_{NLC_d} \gammaeq \frac{1}{2}$ and $1 \leq m_t \leq d$, $\omegaegamega_c(NLC_d^{s}) = \frac{1}{d^n}\left( 1 + (d-1) \leftambda_{NLC_d} \rhoight)$. The fact that the optimal classical strategy for $NLC_d$ is also optimal for the subgames $NLC_d^{s}$ then implies by Lemma \rhoef{facet-lem} that the Bell inequalities corresponding to the games $NLC_d$ are not facets of the Bell polytope. Again, note that the inequalities $NLC_d^{s}$ themselves may be violated in quantum theory.   
\epsilonnd{proof}

\sigmaection{Faces in the (2,2,2,2,2) CHSH polytope}
\label{sec:CHSH-face}
We have so far seen that many of the paradigmatic Bell inequalities with no quantum violation only describe low-dimensional faces of the corresponding Bell and correlation polytopes. In this section, we look at the simplest and most well-studied Bell scenario, namely that of two parties each measuring two binary observables; explicitly Alice performs binary measurements $A_1, A_2$ and Bob measures $B_1, B_2$. The Bell polytope in this scenario is an $8$-dimensional polytope with the only non-trivial facets known to be the CHSH inequalities (up to local relabelings of inputs and outputs and exchange of parties), and the correlation polytope in this scenario is a $4$-dimensional polytope also with the tight inequalities being the CHSH inequalities. In the set of quantum boxes $\muathcal{Q}$, and the set $\muathcal{E}$ of quantum correlations $\langle A_i B_j \rhoangle$, these inequalities are well-known to be violated up to the Tsirelson bound. Here, we identify a necessary and sufficient condition for a correlation inequality in this scenario to be not violated in quantum theory, as such we identify the faces of the set of quantum correlations in this simplest scenario. 
Recall that we are not interested in the trivial facets $\langle A_i B_j \rhoangle = \pim 1$ that are also facets of the no-signaling polytope, we are looking for inequalities that have $\omegaegamega_c = \omegaegamega_q < \omegaegamega_{ns}$. 

Any correlation inequality here can be written up to relabelings in the form
\betaegin{equation}gin{eqnarray}
\label{eq:chsh-corr-1}
&&p_1 \langle A_1 B_1 \rhoangle + p_2 \langle A_1 B_2 \rhoangle + p_3 \langle A_2 B_1 \rhoangle - p_4 \langle A_2 B_2 \rhoangle 
\nuonumber \\
&&\qquad \leq 1 - 2 in\{p_i \},
\epsilonnd{eqnarray}
where we normalize to $\sigmaum_{i} p_i = 1$ and we may choose without loss of generality 
$in\{p_i \} = p_4$. Equivalently, this is the XOR game
\betaegin{equation}gin{eqnarray}
\label{eq:chsh-corr}
&&p_1 P(a \omegaegaplus b = 0 | A_1, B_1) + p_2 P(a \omegaegaplus b = 0|A_1, B_2) +\nuonumber \\&& p_3 P(a \omegaegaplus b = 0 | A_2, B_1) + p_4 P(a \omegaegaplus b = 1|A_2, B_2) \nuonumber \\ && \qquad \leq 1 - p_4.
\epsilonnd{eqnarray} 

\betaegin{equation}gin{prop}
The necessary and sufficient condition for the weighted CHSH inequality (\rhoef{eq:chsh-corr-1}) to describe a non-trivial face of the set of quantum correlations is that $p_4 < p_1,p_2, p_3$ and
\betaegin{equation}gin{equation}
\label{eq:chsh-face}
(p_2 p_3 + p_1 p_4)^2 \leq (p_1 + p_2)(p_1 + p_3)(p_2 - p_4)(p_3 - p_4).
\epsilonnd{equation}
\epsilonnd{prop}
\betaegin{equation}gin{proof}
In \cite{RKM+14}, we identified a necessary and sufficient condition for an XOR game to have no quantum advantage. For the game matrix given as $\thetailde{{\sigmaf{P}}hi} = \betaegin{equation}gin{pmatrix}
  p_1 & p_2  \\
  p_3 & -p_4 
 \epsilonnd{pmatrix}$ 
with $p_4 = in \{p_i\}$, and for the optimal classical strategy matrix $S_c = | s_A \rhoangle \langle s_B |$, 

the necessary and sufficient condition for the game to have $\omegaegamega_c = \omegaegamega_q$ is that $\Sigmaigma, \leftambda \sigmaucc 0$ or $\Sigmaigma, \leftambda \pirec 0$ and 
 \betaegin{equation}gin{equation}
 \rhoho(\leftambda^{-1} \thetailde{{\sigmaf{P}}hi}^T \Sigmaigma^{-1} \thetailde{{\sigmaf{P}}hi}) = 1. 
 \epsilonnd{equation}
Here $\Sigmaigma = \thetaext{diag}({\langle i |\thetailde{{\sigmaf{P}}hi} |s_B \rhoangle \langle s_A |i \rhoangle}_{i=1,2} )$, $\leftambda = \thetaext{diag}({\langle s_A |\thetailde{{\sigmaf{P}}hi} |i\rhoangle \langle i|s_B \rhoangle}_{i=1,2} )$ and $\rhoho( \cdot )$ denotes the spectral radius. 

Explicitly, for the weighted CHSH game with $p_4 = in\{p_i\}$, one of the optimal strategies is for Alice and Bob to output correlated answers $|s_A \rhoangle = |s_B \rhoangle = (1,1)^T$, in which case

we have $\Sigmaigma = \betaegin{equation}gin{pmatrix}
  p_1  + p_2 & 0  \\
  0 & p_3-p_4 
 \epsilonnd{pmatrix}$ and $\leftambda = \betaegin{equation}gin{pmatrix}
  p_1 + p_3 & 0  \\
  0 & p_2 -p_4 
 \epsilonnd{pmatrix}$. 

The condition $\Sigmaigma, \leftambda \sigmaucc 0$ then gives $p_4 < p_3, p_2$. 
The condition on the spectral radius gives by a straightforward calculation of the eigenvalues of $\leftambda^{-1} \thetailde{{\sigmaf{P}}hi}^T \Sigmaigma^{-1} \thetailde{{\sigmaf{P}}hi}$ the condition in Eq.(\rhoef{eq:chsh-face}). This leaves the possibility that either $p_4 = p_1$ or $p_4 < p_1$. When $p_4 = p_1$, the condition Eq.(\rhoef{eq:chsh-face}) reduces to $p_4 = p_1 = 0$ which are the trivial inequalities with $w_c = 1$.
\epsilonnd{proof}
Note that analogous conditions hold when $p_4$ is not the minimum, for instance when $in\{p_i\} = p_2$ we have the equivalent condition $(p_2 p_3 + p_1 p_4)^2 < (p_1 - p_2)(p_1 + p_3)(p_4 - p_2)(p_3 + p_4)$. Also, note that while Eq.(\rhoef{eq:chsh-corr}) also defines an edge of the $8$-dimensional quantum set $\muathcal{Q}$, there may also exist other inequalities involving local terms for the Bell polytope here that define higher-dimensional faces of $\muathcal{Q}$. 

\sigmaection{Single-system binary outcome inequalities without quantum violation}
\label{sec:cut-poly}

{The main result we present in this section is tight noncontextuality inequalities that have no quantum violation and cannot be recovered by the CE principle (see definition \rhoef{defCE}).} Formally, it is stated as follows
\betaegin{equation}gin{thm}
{There exist tight  nontrivial noncontextuality inequalities (facets of the non-contextual polytope) with no quantum violation (but violated in general non-disturbing theories) that, moreover, are not in the form of a constraint imposed by the Consistent Exclusivity principle. }
\epsilonnd{thm}
 We focus on dichotomic measurements, where the output labels are taken as $+1$ and $-1$, and contextuality scenarios where the compatibility structure has at most two compatible measurements in each context, and therefore can be represented by a compatibility graph. We will first present two results from which the main theorem follows. 
	

Finding all the facets of the noncontextual polytope for a given scenario can be accomplished by algorithms such as PORTA \cite{PORTA} 
and cdd \cite{cdd} for small scenarios, whereas for more {complex ones the problem becomes computationally intractable. 
Instead of applying these algorithms,} {in this work} {we obtain noncontextuality inequalities by exploiting the connection between the 
\thetaextit{cut polytope} \cite{DL97} of a compatibility graph and its noncontextual polytope. 
Such a connection was first established by Avis \thetaextit{et al} \cite{ito} in Bell scenarios, and here we make the explicit statement 
for general contextuality ones.} {This will allow us to obtain general statements for contextuality by exploring some established results on cut polytopes.}
 
 {Given a graph $G=(V,E)$, a  cut of $G$ is defined by a subset $S \sigmaubset V$, and consists of those edges joining a vertex of S to a vertex not in S. The edge incidence vector of a cut is a binary vector $\varepsilonc{x}^S$ of size $|E|$. Its components are: $\varepsilonc{x}^S(j) = 0$ if edge $j$ is not present in the cut, and $\varepsilonc{x}^S(j) = 1$ otherwise.  The cut polytope of G is the convex hull of the edge incidence vectors: $\{ \varepsilonc{x}^S | \thetaext{S is a cut} \}$}.
 
We first explore a remark made by Avis \thetaextit{et al} that one can define the cut polytope  in terms of \thetaextit{anti-correlations} 	
\betaegin{equation}gin{equation}
 x_{i j}:= p(a\nueq b|ij),
 	\epsilonnd{equation}  	
{where $x_{ij}$ is short for $ 	\varepsilonc{x}^S(\{i,j\})$. That is, the FC-NC (full correlation non-contextual) polytope of $G$ and the cut polytope of $G$ are isomorphic, where the bijection between the two sets is given by the affine transformation 
 \betaegin{equation}gin{equation}
			  \muean{M_iM_j}=1-2x_{ij}.
 \epsilonnd{equation}
	Now we will show that a similar statement can be made between the NC-polytope of $G$ and the cut polytope of the \thetaextit{suspension graph} of $G$. Recall that the { suspension graph} $\nuabla G  := (V',E')$ of a graph G is obtained from G by adding one new vertex $O$ which is adjacent to all other vertices of $G$. 	
 	}
 	

\betaegin{equation}gin{prop}\label{prop:cut}
Let $G(V,E)$ be a compatibility graph representing a contextuality scenario. {The NC polytope of this scenario is isomorphic to the cut polytope of the suspension graph $\nuabla G $, via the affine transformations:
\betaegin{equation}gin{align}	\label{affine}
		\muean{M_iM_j}=&1-2x_{ij}  \nuonumber \\
		\muean{M_i}=& 1-2x_{iO	}.
\epsilonnd{align}}
\epsilonnd{prop}       

\betaegin{equation}gin{proof}

{We will show that every edge incidence vector of $\nuabla G $ defines a deterministic non-contextual behaviour and vice-versa, from which the statement about the identity of their convex hulls follows. }

{First arrange the components of $\varepsilonc{x}^S$ as follows: the first $n$ components relate to the edges of type
$  E_0 \{ \{O, v\} | v \in V \}$, i.e. are $x_{O \, i}$ \,,  and the others to those of the type $E = \{ \{v, w\} | v,w \in V \}$, i.e. are  $x_{ij}$.} 

{On the one hand, to show that the edge incidence vector of a cut S provides a deterministic non contextual 
model for the $x_{ij}$, we only need to prove that the model is noncontextual, that is, that it factorises properly at the level 
of correlators via the map \epsilonqref{affine}. What we mean by this is that we should prove that $\muean{M_i M_j} = \muean{M_i} \muean{M_j}$, i.e. $1 - 2 \, x_{ij} = (1 - 2 \, x_{O\,i}) (1 - 2 \, x_{O\,j})$. For this note that there are only 8 ways of separating the vertices $i$, $j$ and $O$ into groups of `in S’ and `outside S', and a case by case inspection proves the equality.}

{On the other hand, now we need to prove that every deterministic non contextual models is 
mapped to an edge incidence vector of a cut S. That is, for each non contextual deterministic strategy we need to find a cut S. One way to do is it the following: Let S be the set of vertex $O$ plus all the vertices that denote measurements that give outcome $-1$. It is easy to check that the anti-correlations $p(a\nueq b|ij)$ coincide with the edge incidence vector of the cut S.}
\epsilonnd{proof}

Considerable effort has been devoted to characterising the cut polytopes of complete graphs. Many general inequalities are known \cite{DL97}, and we have the complete list of tight inequalities for complete graph with seven or less measurements \cite{k7}. Moreover, it is conjectured that a complete characterisation is known for the case of eight and nine \cite{k89} measurements (all these inequalities can be also found in the website \cite{site}). 

Now we move on to presenting our examples. Consider the case where the compatibility graph is $G=K_n$, i.e. a complete
graph where all the $n$ measurements are pairwise compatible, { but not necessarily jointly compatible}.
When studying quantum correlations, since we are working with projective measurements, {they are indeed jointly measurable}, and therefore these are scenarios where the quantum set coincides with the noncontextual polytope. That is, all the facets of the cut polytope $CUT(\nuabla K_n)$ are tight noncontextuality inequalities with no quantum advantage. 
	 

{The question of interest now is whether these tight inequalities with no quantum violation are CE inequalities. 
{ In what follows, we will first translate the question in the hypergraph framework of \cite{AFLS} and then characterise the constraints imposed by CE.}

{In K$_n$, the contexts of compatible measurements have two elements, and the quantity of interest is the behaviour $P(ab|i j)$, where $a,b \in \{-1,1\}$ and $i \nueq j \in \{M_1, \ldots, M_n\}$. These $M_i$ are the measurements in the contextuality scenario, which in this dichotomic case we will also refer to as observables. This allows to interpret the compatibility graph K$_n$ as a hypergraph $H_n$ as follows. In the language of \cite{AFLS}, each context may be considered as a measurement with output set $\{ (-1,-1),(-1,1),(1,-1),(1,1) \}$. Hence, the set of events that characterize the contextuality scenario $H_n$ is $V(H) = \{(ab|i j) | a,b \in \{-1,1\} \, , i, j \in \{M_1, \ldots, M_n\} \land i<\,j \}$. The hyperedges of $H_n$ correspond to either normalization conditions or no-disturbance conditions. Hence, 
\betaegin{equation}gin{widetext} 
\betaegin{equation}gin{equation*}
\betaegin{equation}gin{aligned}
E = & \betaig\{ \{(-1,-1|i, j),(-1,1|i, j),(1,-1|i, j),(1,1|i, j)\} | i, j \in \{M_1, \ldots, M_n\} \land i < j \betaig\} \\
& \cup \betaig\{ \{(-1,-1|i, j),(-1,1|i, j),(1,-1|i, k),(1,1|i, k)\} | i, j, k \in \{M_1, \ldots, M_n\} \land i \nueq j \nueq k \betaig\}.
\epsilonnd{aligned}
\epsilonnd{equation*}
\epsilonnd{widetext} }

{It is easy to see that for every hyperedge $e \in E$, $\sigmaum_{v \in e} P(v) = 1$, and that the no-disturbance principle is satisfied. Note also that the (family of) hyperedges of the form $\{(-1,-1|i,j),(-1,1|i,j),(1,-1|i, k),(1,1|i,k)\}$ corresponds (are isomorphic) to the following sequential protocol: first measure $i$, if the outcome is $a=-1$ measure then $j$, and otherwise $k$. The no-disturbance condition assures that these sequential measurements are complete. These type of hyperedges are the so called ``measurement protocols'' in appendix D of \cite{AFLS}.}

As mentioned in section \rhoef{Preliminaries}, two events are exclusive if and only if they belong to a same hyperedge 
$e \in E$. In what follows, {we characterise the CE inequalities that arise in these scenarios.}

\betaegin{equation}gin{prop}\label{LOsets} 
{All nontrivial $CE^1$ inequalities are given by: 	
\betaegin{equation}gin{equation}\label{cecons}
	\betaegin{equation}gin{aligned}
	-\muean{M_i M_j} - \muean{M_j M_k} - \muean{M_k M_i} &\leq 1 \\
	-\muean{M_i M_j} + \muean{M_j M_k} + \muean{M_k M_i} &\leq 1 \\
	\muean{M_i M_j} - \muean{M_j M_k} + \muean{M_k M_i} &\leq 1 \\
	\muean{M_i M_j} + \muean{M_j M_k} - \muean{M_k M_i} &\leq 1 
	\epsilonnd{aligned},
	\epsilonnd{equation}}
		for every choice of three measurements $M_i,M_j,M_k$. 
\epsilonnd{prop}

\betaegin{equation}gin{proof}

The proof consists of two parts. First, we show that the maximum sets of orthogonal events in $H_n$ have size four, and correspond to the trivial constrains given by normalization and no-disturbance conditions. Finally, we show that the non-trivial maximal sets of orthogonal events in $H_n$ have size $3$ and give rise to such CE inequalities.

Let $S$ be a set of mutually orthogonal events on $H_n$. Note that for every two events in $S$, the corresponding contexts must have at least one observable in common. Hence, we divide the proof by cases. 

First, consider the case where all the events in $S$ relate to the same context, which we denote by $ij$. Hence, the maximal set is $\{ (ab|ij) : a,b \in \{-1,1\} \}$, where all possible values for the outcomes are allowed.

Second, consider the case where two contexts are encompassed in the events of $S$, i.e. these may have either the form $(\cdot | ij)$ or $(\cdot | ik)$. Without loss of generality, suppose $(ab|ij) \in S$. Then, $(\betaar{a}c|ik) \in S$ for any $c$. Hence, the maximal sets in this case have the form $\{(ab|ij),(a\betaar{b}|ij),(\betaar{a}c|ik),(\betaar{a}\betaar{c}|ik)\}$ for fixed $a,b,c$, i.e. correspond to measurement protocols over K$_n$. 

Third, consider the case where three contexts are encompassed in the events of $S$. One option is to take the contexts as $ij$, $ik$ and $jk$. Without loss of generality, suppose $(ab|ij) \in S$. Then, for an event with $ik$ to be orthogonal to $(ab|ij)$, it should have outputs $(\betaar{a}c|ik)$, for any value of $c$. Similarly for $jk$, we have $(\betaar{b}d|jk)$, for any value of $d$. However, if we want both events to belong to $S$, they should further satisfy $(\betaar{a}c|ik) \pierp (\betaar{b}d|jk)$, which implies $d=\betaar{c}$. Hence, the maximal sets $S$, characterized by the parameters $a,b,c,i,j,k$, consist of three elements and read
$$
S = \{ (ab|ij), (\betaar{a}c|ik),  (\betaar{b}\betaar{c}|jk)\}.
$$
The other option is to take the contexts as $ij$, $ik$ and $il$, i.e. they all have $i$ as the common observable. It's easy to check that, since the observables are binary, there is no possible assignment of outputs for which the events are pairwise orthogonal. Hence, this choice of three contexts does not give rise to any set of mutually exclusive events. 

Finally, we are left with the case where four or more contexts are encompassed in the events of $S$. In this case, since every pair of contexts should have one observable in common, the only possibility is that all of them share the same observable, i.e. $i j_1,\ldots, i j_k$. However, since these are binary observables, it is not possible to assign outputs in a way that assures the pairwise orthogonality of every pair of events with different contexts. Hence, such a situation may never give rise to a set of mutually exclusive events. 

Now we move on to unravel the constraints that CE$^1$ imposes over the space of events in $H_n$. For the first case, those are $\sigmaum_{a,b} P(ab|ij) \leq 1$, which is trivially satisfied due to normalization of the behaviour $P$. For the second case, the constraints take the form $\sigmaum_b P(ab|ij) + \sigmaum_c P(\betaar{a}c|ik) \leq 1$, which is guaranteed by the no-disturbance condition.
Indeed, the no-disturbance condition implies $\sigmaum_c P(\betaar{a}c|ik) = \sigmaum_c P(\betaar{a}c|ij)$, hence the statement follows from normalization. Finally, in the third case the CE$^1$ constraint reads $P(ab|ij)+P(\betaar{a}c|ik)+P(\betaar{b}\betaar{c}|jk) \leq 1$, which is a nontrivial CE inequality.

All the possible choices of the outcomes $a,b,c$ will give rise to all the CE inequalities for each choice of three measurements $M_i,M_j,M_k$. When translated into the correlators $\muean{M_i M_j}$ they take the form of eq.~ \epsilonqref{cecons}. 

\epsilonnd{proof}
{Note that this lemma is a peculiarity of contextuality scenarios which do not arise from Bell Scenarios. Indeed, due to the local structure of the latter, the orthogonality between $(ab|ij)$ and $(\betaar{b}\betaar{c}|jk)$ is not defined for $i \nueq j  \nueq k$. Hence, there is no contradiction with the fact that LO$^1\epsilonquiv$ NS for bipartite Bell Scenarios \cite{LO}. }

{We have seen that the inequalities that define the set of behaviors that satisfy CE$^1$ have a very simple form. We remark that the inequalities presented at eq \epsilonqref{cecons} are also known as \thetaextit{triangle inequalities} in the cut polytope literature (see chapter 27 of \cite{DL97}) and they were already explored in noncontextuality \cite{triangle}. Also, they represent all tight NC-inequalities in the the complete compatibility graph scenario with three vertices \cite{liang2,AQB+13}.}
	
	 However, the set of noncontextual behavious in $K_n$ (which coincides with the quantum set) is defined by the facets of the CUT polytope of $\nuabla K_n$ (see  \cite{site} for a list of all known cut polytope inequalities for complete graph scenarios with less than ten measurements ). Therefore, facet defining inequalities for $CUT(\nuabla K_n)$ which are not of triangular form are tight noncontextuality inequalities with no quantum violation and not in the form of a Consistency Exclusivity constraint. 

One example of this is the \thetaextit{pentagonal inequality} 
	\betaegin{equation}gin{equation}
	\sigmaum_{1\leq i<j<n} b_i b_j x_{ij} \leq 0,
	\epsilonnd{equation}
	with $b_1=b_2=b_3=1, b_4=b_5=-1$, which is facet defining for the cut polytope of a complete graph with five vertices.

	Let us associate vertex $5$ with the additional vertex $O$ in $\nuabla K_4$. A direct application of the affine map \epsilonqref{affine} provides us the tight noncontextuality inequality	
		\betaegin{equation}gin{equation}\label{ineq:pent}
		\sigmaum_{1\leq i<j<n} -b_i b_j \muean{M_iM_j} \leq 2,  \; 
		\epsilonnd{equation}
with $b_1=b_2=b_3=1, b_4=b_5=-1$, where $M_5 = \omegaegapenone$. Direct inspection shows that this inequality is not in the form of CE, and therefore provides one explicit example of a tight noncontextuality inequality without quantum violation we are searching for. 

In addition to the database presented in \cite{site}, chapters 28-30 of \cite{DL97} present a family of inequalities for the cut polytope of any complete graph.

One class is given by the \thetaextit{hypermetric inequalties} that are respected by any point in the cut polytope of $K_n$
	\betaegin{equation}gin{equation}
			\sigmaum_{1\leq i<j<n} b_i b_j x_{ij} \leq 0, \; \thetaext{where } b_i\in \muathbb{Z} \thetaext{ and } \; \sigmaum_i b_i=1.
		\epsilonnd{equation}
Triangle inequalities and the pentagonal one are particular examples of hypermetric inequalities. 
For the hypermetric inequalities to be tight conditions need to be imposed on the coeffients $b_i$; some of these are known (see chapter 28 of \cite{DL97}). For instance, the inequalities are tight whenever $b_1=b_2=\ldots=b_{n-2}=1,\; b_{n-1}=-1$ and $b_n=4-n$ (theorem 28.2.4 (iiib) of ref \cite{DL97}).
As a remark, note that in general theories that satisfy the no-disturbance condition one can construct boxes where $\muean{M_iM_j} = \pim 1$ while $ \muean{M_i}= 0$, such that they achieve the maximum algebraic value of these inequalities.	 

\sigmaection{Conclusion}
In this paper, we presented progress toward the resolution of the question whether there are tight two-party Bell inequalities that are also facets 
of the quantum set of correlations, focusing on the paradigmatic cases of XOR games and linear games. 
We formulated a simple sufficient condition to
identify and construct games with no quantum advantage within these classes. We then showed that the well-known class of Bell inequalities corresponding
to non-local computation tasks are not tight in both the binary outcome case and in the generalization to arbitrary prime outputs for a special class of 
functions, i.e., they do not define facets of the corresponding Bell polytopes. We then identified correlation inequalities that define faces of the set 
of quantum correlations in the simplest Bell scenario corresponding to the CHSH polytope.

Then we moved on to general contextuality scenrios, and studied the question in this single-party scenario, namely non-contextuality inequalities 
with binary outcomes. Here we identified the polytope of non-contextual behaviours with the cut polytope of the suspension graph of the compatibility 
graph representing the measurements in the experiment. Moreover, we characterised the polytope of behaviours that satisfy consistent exclusivity 
inequalities for compatibility graphs that are complete. We then found that, in this particular case (which is not a Bell scenario) there are tight 
non-contextuality inequalities with no quantum advantage that are not in the Consistent Exclusivity form. An open problem is to find an interpretation of 
these inequalities as an information theoretic task. 

Finally, two main questions are still open: whether the two-party correlation polytope shares any facets with the Tsirelson elliptope and whether 
the two-party Bell polytope shares any facets with the quantum correlation set.

\thetaextit{ Acknowledgements.} We are grateful to P. Horodecki and M. Horodecki for useful discussions,
R.R. thanks J.-D. Bancal and Y.-C. Liang for asking the question answered in Section \rhoef{sec:CHSH-face}. 
R. R. is supported by the ERC AdG grant QOLAPS.
M.T.Q. acknowledges financial support from the Swiss National Science Foundation (grant PP00P2 138917, Starting grant DIAQ).
A.B.S. acknowledges the support from the ERC AdG NLST. 
G. M. acknowledges support from NWO VIDI, ERC Starting Grant and the Brazilian agency Fapemig.
R. A. acknowledges support from the European Union's Horizon 2020 research and innovation programme under the Marie Sk\l{}odowska-Curie 
N-MuQuas Grant No. 705109. 

\betaegin{equation}gin{thebibliography}{99}

\betaibitem{Bell}J. S. Bell, Physics \thetaextbf{1}, 195 (1964).

\betaibitem{securekey} A. K. Ekert, Phys. Rev. Lett. \thetaextbf{67}, 661 (1991); A. Ac\'in \thetaextit{et al.}, 
Phys. Rev. Lett. \thetaextbf{98}, 230501 (2007).

\betaibitem{CommCompl}H. Buhrman \thetaextit{et al.}, Rev. Mod. Phys. \thetaextbf{82}, 665 (2010).

\betaibitem{rand}S. Pironio et al., Nature (London) \thetaextbf{464}, 1021 (2010); R.
Colbeck, Ph.D. thesis, University of Cambridge, 2007; 

R. Colbeck and R. Renner, Nat. Phys. \thetaextbf{8}, 450 (2010).

\betaibitem{KS} Simon Kochen and Ernst P. Specker, J. Math. Mech. 17, 59–87 (1967).

\betaibitem{AB} Samson Abramsky and Adam Brandenburger, New Journal of Physics 13, no. 11, 113036 (2011).
 
\betaibitem{AFLS} A. Ac\'in, T. Fritz, A. Leverrier, A.~ B. Sainz, Comm. in Mat. Phys. vol. 334, pp 533-628 (2015).

\betaibitem{contcomp} M. Howard, J.~ J. Wallman, V. Veitch, and J. Emerson, Nature 510, 351 (2014). R. Raussendorf, D.~ E. Browne, N. Delfosse, C. Okay, and J. Bermejo-Vega, arXiv:1511.08506 (2015). N. Delfosse, P. Allard Guerin, J. Bian, and R. Raussendorf, Phys. Rev. X 5, 021003 (2015). 

\betaibitem{Gill}
R. Gill. 
\thetaextit{Problem 26. Bell inequalities holding for all quantum states.} 
O. Kr\"{u}ger and R. F. Werner, editors,
\thetaextit{Some Open Problems in Quantum Information Theory}, 
arXiv:quant-ph/0504166 (2005). 

\betaibitem{AII06}
D. Avis, H. Imai and T. Ito,

J. of Phys. A: Math. and General \thetaextbf{39}, 36 (2006). 

\betaibitem{GYNI}
M. L. Almeida, J.-D. Bancal, N. Brunner, A. Ac\'{i}n, N. Gisin and S. Pironio,
Phys. Rev. Lett. \thetaextbf{104}, 230404 (2010).

\betaibitem{LO}T. Fritz \thetaextit{et al.}, Nat. Comm. \thetaextbf{4}, 2263 (2013); A. B. Sainz \thetaextit{et al.}, 
Phys. Rev. A \thetaextbf{89}, 032117 (2014).

\betaibitem{facets}
\thetaextit{www.faacets.com}. 

\betaibitem{unb-viol}
H. Buhrman, O. Regev, G. Scarpa, and R. de Wolf. 

Theory Comput., \thetaextbf{8}:623 (2012); 

M. Junge and C. Palazuelos. 

Comm. in Math. Phys., 1 (2011);
M. Junge, C. Palazuelos, D. P\'{e}rez-Garc\'{ı}a, I. Villanueva, and M. M. Wolf. 

Comm.
Math. Phys., 300(3):715 (2010).

\betaibitem{spekkens} R. W. Spekkens, D. H. Buzacott, A. J. Keehn, B. Toner,
and G. J. Pryde, Phys. Rev. Lett. 102, 010401 (2009).

\betaibitem{adanrays} A. Cabello, J.~ M. Estebaranz, and G. Garc\'ia-Alcaine, Phys. Lett. A 212 (1996). A. Cabello, Phys. Rev. Lett. 101, 210401 (2008).

\betaibitem{AQB+13}

M. Ara\'{u}jo, Marco T\'{u}lio Quintino, C. Budroni, M. T. Cunha and A. Cabello,
Phys. Rev. A \thetaextbf{88}, 022118 (2013). 

\betaibitem{horodecki_measure} A. Grudka, K. Horodecki, M. Horodecki, P. Horodecki, R. Horodecki, P. Joshi, W. Kłobus, A. Wójcik, Phys. Rev. Lett. 112, 120401 (2014).

\betaibitem{RAM}R. Ramanathan, R. Augusiak, and G. Murta, 

Phys. Rev. A \thetaextbf{93}, 022333 (2016).

\betaibitem{NLC}
N. Linden, S. Popescu, A. J. Short and A. Winter,
Phys. Rev. Lett. \thetaextbf{99}, 180502 (2007).

\betaibitem{DL97}
M. M. Deza and M. Laurent. 
\thetaextit{Geometry of Cuts and Metrics}, vol. 15 of Algorithms and
Combinatorics, Springer, (1997).

\betaibitem{comp-geom}
M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf,
\thetaextit{Computational Geometry: Algorithms and Applications} (Third Edition), Springer-Verlag, Heidelberg (2008).  

\betaibitem{Schrijver}
A. Schrijver, \thetaextit{Combinatorial Optimization. Polyhedra and Efficiency}, Vol. A, volume 24 of Algorithms and Combinatorics, Springer-Verlag, Berlin (2003).  

\betaibitem{Masanes}Ll. Masanes, 

arXiv:quant-ph/0309137.

\betaibitem{PR}
S. Popescu and D. Rohrlich,
Foundations of Physics \thetaextbf{24} (3): 379–385 (1994).

\betaibitem{AHW10}
D. Avis, P. Hayden and M. W. Wilde,

Phys. Rev. A \thetaextbf{82}, 030102(R) (2010).

\betaibitem{klyachko1} A. Klyachko, arXiv:quant-ph/0206012 (2002).

\betaibitem{klyachko2} A. A. Klyachko, M. A. Can, S. Binicioglu, and A. S. Shumovsky, Phys. Rev. Lett. 101, 020403 (2008).

\betaibitem{planeta}  R. Chaves, T. Fritz  Phys. Rev. A 85, 032113 (2012).

\betaibitem{fritz} T. Fritz, R. Chaves IEEE Trans. on Information Theory, vol. 59, pages 803 - 817 (2013).

\betaibitem{Henson} J. Henson, arXiv:1210.5978 (2012).

\betaibitem{cabello} A. Cabello, Phys. Rev. Lett. 110, 060402 (2013).

\betaibitem{GisinCG}
 D. Collins and N. Gisin. J. Phys. A, Volume 37, Number 5, pages 1775 (2004).

 \betaibitem{Wehner}S. Wehner, Phys. Rev. A \thetaextbf{73}, 022110 (2006).

\betaibitem{Tsirelson}
B. S. Cirel’son, 
Lett. Math. Phys. \thetaextbf{4}, 83 (1980).

\betaibitem{footnote1}
Note that Tsirelson's
theorem implies that the set of full-correlation quantum boxes is equivalent to the set of full-correlation boxes described by
first level of the hierarchy introduced in \cite{NPA}.

\betaibitem{RKM+14}
R. Ramanathan, A. Kay, G. Murta and P. Horodecki,
Phys. Rev. Lett. \thetaextbf{113}, 240401 (2014). 

\betaibitem{Hastad}
J. H{\.a}stad, J. ACM, \thetaextbf{48} (4): 798 (2001).

\betaibitem{Khot}
S. Khot, G. Kindler, E. Mossel, and R. O’Donnell, SIAM J. Comput., 37(1): 319 (2007).

\betaibitem{Liang}
Y-C. Liang, C-W. Lim and D-L. Deng,
Phys. Rev. A \thetaextbf{80}, 052116 (2009).

\betaibitem{footnote2}
One can note that the game given by Eq. \epsilonqref{exampleNLC3} 
is described by the function $f(x,y)=x\cdot y+\deltaelta_{x,2}+\deltaelta_{y,2}$,  which is equivalent to $CHSH_3$ up to local terms.

\betaibitem{PORTA} http://comopt.ifi.uni-heidelberg.de/software/PORTA/

\betaibitem{cdd} https://www.inf.ethz.ch/personal/fukudak/old/

\betaibitem{ito}  D. Avis, H. Imai, T. Ito, Y. Sasaki  Journal of Physics A: Mathematical and General, Volume 38, Number 50 (2005).

\betaibitem{k7}  V.P. Grishukhin, European Journal of Combinatorics, 11, 115-117 
\betaibitem{k89} T. Christof, G. Reinelt, Efficient parallel facet enumeration for 0/1-polytopes, Technical report, Institut für Angewandte Mathematik, Universität Heidelberg, 1997.

\betaibitem{site} https://www.iwr.uni-heidelberg.de/groups/comopt/\\
software/SMAPO/cut/cut.html

\betaibitem{triangle} P Kurzynski, D Kaszlikowski  arXiv:1309.6777 

\betaibitem{liang2} Y-C Liang, R. W. Spekkens, H. M. Wiseman Physics Reports, vol 506, issues 1-2, pp 1-39 (2011).

\betaibitem{NPA}M. Navascu\'es, S. Pironio, and A. Ac\'in, New J. Phys. \thetaextbf{10},  073013 (2008).

\epsilonnd{thebibliography}

\epsilonnd{document}