A fundamental problem is to understand why quantum theory only violates some noncontextuality (NC) inequalities and identify the physical principles that prevent higher-than-quantum violations. We prove that quantum theory only violates those NC inequalities whose exclusivity graphs contain, as induced subgraphs, odd cycles of length five or more, and/or their complements. In addition, we show that odd cycles are the exclusivity graphs of a well-known family of NC inequalities and that there is also a family of NC inequalities whose exclusivity graphs are the complements of odd cycles. We characterize the maximum noncontextual and quantum values of these inequalities, and provide evidence supporting the conjecture that the maximum quantum violation of these inequalities is exactly singled out by the exclusivity principle.
We prove that a necessary condition for genuinely quantum correlations is that the structure of relationships of exclusivity between the events tested contains, as induced structures, (i) odd cycles of length 5 or more, and/or (ii) their complements. Family (i) is a well-known family of quantum structures. Family (ii) is identified here as a family of quantum structures. We characterize its maximum classical and quantum values and show that it provides valuable information on the dimension of the system. We show that the present knowledge in graph theory is compatible with/strongly suggests that the quantum correlations of family (i)/(ii) are singled out by the principle that the sum of probabilities of pairwise exclusive events cannot exceed 1.
Contextuality is one way of capturing the nonclassicality of quantum theory.The contextual nature of a theory is often witnessed via the violation of noncontextuality inequalities-certain linear inequalities involving probabilities of measurement events.Using the exclusivity graph approach (one of the two main graph theoretic approaches for studying contextuality), it was shown [Cabello et al.Phys. Rev. A 88, 032104 (2013); Chudnovsky et al.Ann. Math. 164, 51 (2006)] that a necessary and sufficient condition for witnessing contextuality is the presence of an odd number of events (greater than three) which are either cyclically or anticyclically exclusive.Thus, the noncontextuality inequalities the underlying exclusivity structure of which is as stated, either cyclic or anticyclic, are fundamental to quantum theory.We show that there is a unique noncontextuality inequality for each nontrivial cycle and anticycle.In addition to the foundational interest, we expect this to aid the understanding of contextuality as a resource to quantum computing and its applications to local self-testing.
A necessary condition for the probabilities of a set of events to exhibit Bell non-locality or Kochen-Specker contextuality is that the graph of exclusivity of the events contains induced odd cycles with five or more vertices, called odd holes, or their complements, called odd antiholes. From this perspective, events whose graph of exclusivity are odd holes or antiholes are the building blocks of contextuality. For any odd hole or antihole, any assignment of probabilities allowed by quantum theory can be achieved in specific contextuality scenarios. However, here we prove that, for any odd hole, the probabilities that attain the quantum maxima cannot be achieved in Bell scenarios. We also prove it for the simplest odd antiholes. This leads us to the conjecture that the quantum maxima for any of the building blocks cannot be achieved in Bell scenarios. This result sheds light on why the problem of whether a probability assignment is quantum is decidable, while whether a probability assignment within a given Bell scenario is quantum is, in general, undecidable. This also helps to understand why identifying principles for quantum correlations is simpler when we start by identifying principles for quantum sets of probabilities defined with no reference to specific scenarios. This article is part of the theme issue 'Quantum contextuality, causality and freedom of choice'.
The most promising candidate for being the fundamental principle of quantum contextuality is the Exclusivity principle, which states that the sum of the probabilities of a set of pairwise exclusive events cannot exceed 1. By itself, the Exclusivity principle singles out the maximum quantum value for some important Bell and noncontextuality inequalities. We can get better results if we apply the E principle to more sophisticated scenarios. This happens because this principle exhibits activation effects: a distribution satisfying this principles does not necessarily satisfy it when combined with other distributions. Activation effects can be used to prove that the Exclusivity principle singles out the set of quantum distributions for the most simple noncontextuality inequality. It is still not known if the exclusivity principle solves the problem of explaining quantum contextuality completely, but many results have been proven that support the conjecture that it might. The main purpose of this thesis is to discuss in detail the situations in which the E principle can be used to rule out distributions outside the quantum set.
Non-contextuality (NC) and Bell inequalities can be expressed as bounds
Ω for positive linear combinations
S of probabilities of events,
S≤Ω. Exclusive events in
S can be represented as adjacent vertices of a graph called the exclusivity graph of
S. In the case that events correspond to the outcomes of quantum projective measurements, quantum probabilities are intimately related to the Grötschel-Lovász-Schrijver theta body of the exclusivity graph. Then, one can easily compute an upper bound to the maximum quantum violation of any NC or Bell inequality by optimizing
S over the theta body and calculating the Lovász number of the corresponding exclusivity graph. In some cases, this upper bound is tight and gives the exact maximum quantum violation. However, in general, this is not the case. The reason is that the exclusivity graph does not distinguish among the different ways exclusivity can occur in Bell-inequality (and similar) scenarios. An interesting question is whether there is a graph-theoretical concept which accounts for this problem. Here we show that, for any given
N-partite Bell inequality, an edge-coloured multigraph composed of
N single-colour graphs can be used to encode the relationships of exclusivity between each party's parts of the events. Then, the maximum quantum violation of the Bell inequality is exactly given by a refinement of the Lovász number that applies to these edge-coloured multigraphs. We show how to calculate upper bounds for this number using a hierarchy of semi-definite programs and calculate upper bounds for
I3,
I3322 and the three bipartite Bell inequalities whose exclusivity graph is a pentagon. The multigraph-theoretical approach introduced here may remove some obstacles in the program of explaining quantum correlations from first principles.
Non-contextuality (NC) and Bell inequalities can be expressed as bounds Ω for positive linear combinations S of probabilities of events, S≤Ω. Exclusive events in S can be represented as adjacent vertices of a graph called the exclusivity graph of S. In the case that events correspond to the outcomes of quantum projective measurements, quantum probabilities are intimately related to the Grötschel-Lovász-Schrijver theta body of the exclusivity graph. Then, one can easily compute an upper bound to the maximum quantum violation of any NC or Bell inequality by optimizing S over the theta body and calculating the Lovász number of the corresponding exclusivity graph. In some cases, this upper bound is tight and gives the exact maximum quantum violation. However, in general, this is not the case. The reason is that the exclusivity graph does not distinguish among the different ways exclusivity can occur in Bell-inequality (and similar) scenarios. An interesting question is whether there is a graph-theoretical concept which accounts for this problem. Here we show that, for any given N-partite Bell inequality, an edge-coloured multigraph composed of N single-colour graphs can be used to encode the relationships of exclusivity between each party's parts of the events. Then, the maximum quantum violation of the Bell inequality is exactly given by a refinement of the Lovász number that applies to these edge-coloured multigraphs. We show how to calculate upper bounds for this number using a hierarchy of semi-definite programs and calculate upper bounds for I3, I3322 and the three bipartite Bell inequalities whose exclusivity graph is a pentagon. The multigraph-theoretical approach introduced here may remove some obstacles in the program of explaining quantum correlations from first principles.