The characterization of the set of quantum correlations is a problem of fundamental importance in quantum information. The question whether every proper (tight) Bell inequality is violated in quantum theory is an intriguing one in this regard. Here we make significant progress in answering this question, by showing that every tight Bell inequality is violated by ``almost-quantum'' correlations, a semidefinite programming relaxation of the set of quantum correlations. As a consequence, we show that many (classes of) Bell inequalities including two-party correlation Bell inequalities and multioutcome nonlocal computation games, which do not admit quantum violations, are not facets of the classical Bell polytope. To do this, we make use of the intriguing connections between Bell correlations and the graph-theoretic Lov\'asz-theta set, discovered by Cabello-Severini-Winter (CSW). We also exploit connections between the cut polytope of graph theory and the classical correlation Bell polytope, to show that correlation Bell inequalities that define facets of the lower dimensional correlation polytope are violated in quantum theory.
Quantum correlations which violate a Bell inequality are presumed to power better-than-classical protocols for solving communication complexity problems (CCPs). How general is this statement? We show that violations of correlation-type Bell inequalities allow advantages in CCPs, when communication protocols are tailored to emulate the Bell no-signaling constraint (by not communicating measurement settings). Abandonment of this restriction on classical models allows us to disprove the main result of, inter alia, \cite{BZ02}; we show that quantum correlations obtained from these communication strategies assisted by a small quantum violation of the CGLMP Bell inequalities do not imply advantages in any CCP in the input/output scenario considered in the reference. More generally, we show that there exists quantum correlations, with nontrivial local marginal probabilities, which violate the I3322 Bell inequality, but do not enable a quantum advantange in any CCP, regardless of the communication strategy employed in the quantum protocol, for a scenario with a fixed number of inputs and outputs
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 of whether every proper (facet-defining) 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 nonlocal computation games, do not constitute facet-defining 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 Clauser-Horne-Shimony-Holt Bell scenario of binary dichotomic measurements, and identify edges in the set of quantum correlations in this scenario. Finally, we relate the noncontextual polytope of single-party correlation inequalities with the cut polytope $\text{CUT}(\mathbf{\ensuremath{\nabla}}G)$, where
G denotes the compatibility graph of observables in the contextuality scenario and $\mathbf{\ensuremath{\nabla}}G$ denotes the suspension graph of
G. We observe that there exist facet-defining noncontextuality inequalities with no quantum violation, and furthermore that this set of inequalities is beyond those implied by the consistent exclusivity principle.