A combinatorial approach to nonlocality and contextuality (Q2258010)

It is an extremely massive paper (almost 100 pages) shrouded in the rather arcane jargon deemed by now to be instrumental to pinpoint the otherwise elusive notions that in the recent decades stemmed out of the \textit{EPR} paradox and the Bell's inequality. The problem however is always that of characterizing in some compelling way the incompatibility between the quantum world and some kind of (more or less hidden) classical model trying to reproduce it, and this is done here by dissecting the age-old ideas of \textit{non-locality} and \textit{contextuality} from the standpoint of graph theory. The authors consider the measurements and their outcomes as embedded in a hypergraph setting where outcomes are vertices, and measurements are edges connecting them. Such an hypergraph \(H\) is called a ``contextuality scenario''. A probabilistic model on \(H\) then is an assignment of a probability \(p(v)\) to each vertex in such a way that the sum of the \(p(v)\) for a given measurement \(e\) is \(1\). In the set \(\mathcal{G}(H)\) of all these probabilistic models there are both the subsets \(\mathcal{C}(H)\) and \(\mathcal{Q}(H)\) of classical and quantum models. The crossing to the non-locality is implemented by means of products of the contextuality scenarios \(H_A\) and \(H_B\) with edges representing joint measurements. In order, however, to rule out in a natural way the possibility of \textit{signaling models}, it is expedient to adopt the so called Foulis-Randall product \(H_A\otimes H_B\), which however is not associative, and hence can not be naively extended to three or more scenarios. Anyway also this snag can be circumvented at the price of some further formal intricacy (that the authors themselves advise to skip): this leads also to particular case of the Bell scenarios \(B_{n,k,m}\) consisting of \(n\) parties, each having access to \(k\) local measurements with \(m\) possible outcomes. The (duly defined) classical character of a probabilistic model \(p\) on a contextuality scenario \(H\) can now be detected by looking -- in the notation of the graph theory as summarized in one of the four thick Appendices at the end of the paper -- at the value of the the \textit{weighted fractional packing} number \(\alpha^*\) of the non-orthogonality graph \(\mathrm{NO}(H)\). The classical models can also be adapted to the product scenarios. Enter the quantum models. In the words of the authors: ``understanding the set of quantum models represents one approach for understanding the counterintuitive aspects of quantum theory: if one can find a simple physical or information-theoretic principle which characterizes the set of quantum models, one would have found an indirect explanation for why our world obeys the laws of quantum theory.'' Predictably enough a probabilistic model is \textit{quantum} when it is paired to the usual Hilbert space structure; there exist however different contextuality scenarios \(H\) and \(H'\) with the same vertices and probability model \(p\) such that \(p\) is quantum on \(H\) but not on \(H'\). The quantum models on product scenarios are subsequently analyzed, and it is found that ``quantum models on \(B_{n,k,m}\) correspond exactly to the usual `quantum correlations' in Bell scenarios.'' The Kochen-Specker theorem is finally discussed in the present setting. It is remarked at this point that ``it is very difficult to determine whether a given probabilistic model \(p\in\mathcal{G}(H)\) is quantum or not ... Hence, it is important to have good approximations to \(\mathcal{Q}(H)\) for which membership can be algorithmically determined.'' It is relevant then to extend to all the contextuality scenarios ``the hierarchy of semidefinite programs characterizing quantum correlations with the commutativity paradigm'' introduced in a few previous papers to solve the case of Bell scenarios. For a quantum model \(p\in \mathcal{Q}(H)\) the said hierarchy consists in a sequence \(\mathcal{Q}(H)\subseteq\ldots\mathcal{Q}_n(H)\subseteq\ldots\mathcal{Q}_1(H)\) such that the membership of \(p\) in \(\mathcal{Q}_n(H)\) can be algorithmically established. It is found furthermore that \(\mathcal{Q}_n(H)\) converges to \(\mathcal{Q}(H)\) so that if \(p\in\mathcal{Q}_n\) for all \(n\), then this imply that \(p\in\mathcal{Q}\). The the first term \(\mathcal{Q}_1(H)\) of the hierarchy is then characterized at length The old-fashioned compatibility of observables in a contextuality scenario \(H\) is now recast in the form of the probabilistic models \(p\) satisfying a \textit{consistent exclusivity} property \(\mathrm{CE}^1\) holding on independent sets of vertices in the non-orthogonality graph \(\mathrm{NO}(H)\). This property -- again disclosed by the weighted fractional packing number of \(\mathrm{NO}(H)\) -- states that the total probability of any collection of pairwise exclusive outcomes is not greater than \(1\), which however is not trivial ``since the probabilities \(p(v)\) of a probabilistic model are conditional probabilities representing the probability that outcome \(v\) occurs given that a measurement \(e\) with \(v\in e\) has been performed.'' The concept of \textit{local orthogonality} (\(\mathrm{LO}\)) -- recently introduced in ``the [never ending] search for `physical' principles characterizing quantum correlations'' -- is now a ``special case of \(\mathrm{CE}\) when using [the author's] definition of Bell scenario.'' When extending these ideas to product scenarios the iterated \(\mathrm{CE}^n\) property (\(\mathrm{CE}^\infty\) when holding for every \(n\)) is then put in relation to the \textit{weighted independence} number \(\alpha\) and \textit{Shannon capacity} \(\Theta\) of \(\mathrm{NO}(H)\). It is found however (Theorem 7.4.3) that the \(\mathrm{CE}\) principle can characterize neither the quantum models \(\mathcal{Q}\), nor the first level \(\mathcal{Q}_1\) of their hierarchy of semidefinite programs, and the authors are also able to prove (1) ``that violations of Consistent Exclusivity can be obtained by activation'', namely that Consistent Exclusivity is not closed under taking tensor products (Theorem 7.5.3), and (2) that \(\mathcal{CE}^\infty\) is not always convex (Theorem 7.5.4). They consequently (to get physically realistic models) propose to extend the \(\mathrm{CE}\) principle in such a way that the set of \textit{quantum} probabilistic models that satisfies it is convex and closed under \(\otimes\). Also this \(\mathrm{ECE}\) principle, however, ``goes a long way in achieving a characterization of the quantum set, but there still remains a gap'' as counterexamples show. The conditions are then examined under which ``the classical set \(\mathcal{C}(H)\) coincides with \(\mathcal{CE}^1(H)\) ... When this is the case, no quantum contextuality is possible in particular.'' The authors finally ``study the computational complexity of various decision problems associated to contextuality scenarios.'' The problem of finding if a complexity scenario admits classical models is found to be \textbf{NP}-complete. As for the analogous problem for quantum models, however, they fail to construct an algorithm for deciding it and they put forward the conjecture that this problem is undecidable. The paper ends with a substantial section devoted to particular examples.