Abstract
So far, most of the literature on (quantum) contextuality and the Kochen–Specker theorem seems either to concern particular examples of contextuality, or be considered as quantum logic. Here, we develop a general formalism for contextuality scenarios based on the combinatorics of hypergraphs, which significantly refines a similar recent approach by Cabello, Severini and Winter (CSW). In contrast to CSW, we explicitly include the normalization of probabilities, which gives us a much finer control over the various sets of probabilistic models like classical, quantum and generalized probabilistic. In particular, our framework specializes to (quantum) nonlocality in the case of Bell scenarios, which arise very naturally from a certain product of contextuality scenarios due to Foulis and Randall. In the spirit of CSW, we find close relationships to several graph invariants. The recently proposed Local Orthogonality principle turns out to be a special case of a general principle for contextuality scenarios related to the Shannon capacity of graphs. Our results imply that it is strictly dominated by a low level of the Navascués–Pironio–Acín hierarchy of semidefinite programs, which we also apply to contextuality scenarios.
We derive a wealth of results in our framework, many of these relating to quantum and supraquantum contextuality and nonlocality, and state numerous open problems. For example, we show that the set of quantum models on a contextuality scenario can in general not be characterized in terms of a graph invariant.
In terms of graph theory, our main result is this: there exist two graphs \({G_1}\) and \({G_2}\) with the properties
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Abramsky S., Brandenburger A.: The sheaf-theoretic structure of non-locality and contextuality. N. J. Phys. 13(11), 113036 (2011)
Abramsky, S., Mansfield, S., Barbosa, R.S.: The cohomology of non-locality and contextuality, In: Proceedings 8th International Workshop on Quantum Physics and Logic (Nijmegen, 2011) (2011)
Alon N.: The Shannon capacity of a union. Combinatorica 18(3), 301–310 (1998)
Alon, N., Lubetzky, E.: The Shannon capacity of a graph and the independence numbers of its powers. IEEE Trans. Inf. Theory 52(5), (2006)
Amaral B., Cunha M.T., Adán C.: The exclusivity principle forbids sets of correlations larger than the quantum set. Phys. Rev. A 89, 030101 (2014)
Anderson I.: Combinatorics of Finite Sets. Oxford University Press, Oxford (1987)
Anjos M.F.: On semidefinite programming relaxations for the satisfiability problem. Math. Methods Oper. Res. 60(3), 349–367 (2004)
Araújo M., Quintino M.T., Budroni C., Cunha M.T., Cabello A.: All noncontextuality inequalities for the n-cycle scenario. Phys. Rev. A 88, 022118 (2013)
Avis D., Imai H., Ito T.: On the relationship between convex bodies related to correlation experiments with dichotomic observables. J. Phys. A 39, 11283 (2006)
Bachoc C., Pécher A., Thiéry A.: On the theta number of powers of cycle graphs. Combinatorica 33(3), 297–317 (2013)
Barnum, H., Fuchs, C.A., Renes, J.M., Wilce, A.: Influence-free states on compound quantum systems (2005). arXiv:quant-ph/0507108
Barrett J.: Information processing in generalized probabilistic theories. Phys. Rev. A 75(3), 032304 (2007)
Barrett J., Leifer M.: The de Finetti theorem for test spaces. N. J. Phys. 11(3), 033024 (2009)
Barrett J., Pironio S.: Popescu-rohrlich correlations as a unit of nonlocality. Phys. Rev. Lett. 95, 140401 (2005)
Bell J.S.: On the Einstein–Podolsky–Rosen paradox. Physics 1, 195–200 (1964)
Berge, C.: Färbung von Graphen, deren sämtliche bzw. deren ungerade Kreise starr sind. Wiss. Z. Martin- Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 10(114) (1961)
Berge C.: Motivations and history of some of my conjectures. Discrete Math. 165–166, 61–70 (1997)
Brouwer A.E., Haemers W.: Spectra of Graphs. Springer, Berlin (2011)
Brunner N., Cavalcanti D., Pironio S., Scarani V., Wehner S.: Bell nonlocality. Rev. Mod. Phys. 86(419), (2014)
Cabello A.: Experimentally testable state-independent quantum contextuality. Phys. Rev. Lett. 101(21), 210401 (2008)
Cabello, A.: Specker’s fundamental principle of quantum mechanics (2012). arXiv:1212.1756
Cabello A.: A simple explanation of the quantum violation of a fundamental inequality. Phys. Rev. Lett. 110, 060402 (2013)
Cabello A.: Twin inequality for fully contextual quantum correlations. Phys. Rev. A 87, 010104 (2013)
Cabello A., Danielsen L.E., López-Tarrida A.J., Portillo J.R.: Basic exclusivity graphs in quantum correlations. Phys. Rev. A 88, 032104 (2013)
Cabello A., Estebaranz J., García-Alcaine G.: Bell–Kochen–Specker theorem: a proof with 18 vectors. Phys. Lett. A 212(4), 183–187 (1996)
Cabello, A., Severini, S., Winter, A.: (Non-)Contextuality of physical theories as an axiom (2010). arXiv:1010.2163. Updated version: Phys. Rev. Lett. 112, 040401 (2014)
Chaves R., Fritz T.: Entropic approach to local realism and noncontextuality. Phys. Rev. A 85(3), 032113 (2012)
Chudnovsky M., Robertson N., Seymour P., Thomas R.: The strong perfect graph theorem. Ann. Math. (2) 164(1), 51–229 (2006)
Clauser J.F., Horne M.A., Shimony A., Holt R.A.: Proposed experiment to test local hidden-variable theories. Phys. Rev. Lett. 23(15), 880–884 (1969)
Codenotti B., Gerace I., Resta G.: Some remarks on the Shannon capacity of odd cycles. Ars Combinatoria 66, 243–257 (2003)
Coecke, B., Moore, D., Wilce, A.: Operational quantum logic: an overview. Curr. Res. Oper. Quantum Logic, 1–36 (2000)
D’Ariano, G.M.: Probabilistic theories: what is special about quantum mechanics? Philosophy of Quantum Information and Entanglement (2010)
Edmonds J., Fulkerson D. R.: Bottleneck extrema. J. Combin. Theory 8(3), 299–306 (1970)
Eiter T.: Exact transversal hypergraphs and application to Boolean \({\mu}\)-functions. J. Symbolic Comput. 17(3), 215–225 (1994)
Engel K.: Sperner Theory, Encyclopedia of Mathematics and its Applications, vol. 65. Cambridge University Press, Cambridge (1997)
Fekete M.: Über die Verteilung der Wurzeln bei gewissen algebraischen Gleichungen mit ganzzahligen Koeffizienten. Math. Z. 17(1), 228–249 (1923)
Fine A.: Hidden variables, joint probability, and the Bell inequalities. Phys. Rev. Lett. 48(5), 291–295 (1982)
Foulis D., Piron C., Randall C.: Realism, operationalism and quantum mechanics. Found. Phys. 13(8), 813–841 (1983)
Foulis D.J., Greechie R.J., Rüttimann G.T.: Filters and supports in orthoalgebras, Internat. J. Theoret. Phys. 31(5), 789–807 (1992)
Foulis D.J., Randall C.H.: Operational statistics. I. Basic concepts. J. Math. Phys. 13, 1667–1675 (1972)
Foulis, D.J., Randall, C.H.: Empirical logic and tensor products 5, 9–20 (1981)
Foulis D.J., Randall, C.H.: What are quantum logics and what ought they to be? Current Issues in Quantum Logic, pp. 35–52 (1981)
Fritz T.: Tsirelson’s problem and Kirchberg’s conjecture. Rev. Math. Phys. 24, 1250012 (2012)
Fritz T., Chaves R.: Entropic inequalities and the marginal problem. IEEE Trans. Inf. Theory 59, 803–817 (2013)
Fritz T., Netzer T., Thom A.: Can you compute the operator norm?. Proc. Am. Math. Soc. 142, 4265–4276 (2014)
Fritz T., Sainz A., Augusiak R., Brask J.B., Chaves R., Leverrier A., Acín A.: Local orthogonality: a multipartite principle for correlations. Nature Comm. 4, 2263 (2012)
Fritz, T., Sainz, A.B., Leverrier, A.: Probabilistic models on contextuality scenarios (2013). arXiv:1307.0145
Gottlob, G., Leone, N., Scarcello, F.: Hypertree decompositions: a survey. In: Mathematical Foundations of Computer Science, pp. 37–57 (2001)
Greechie R.J.: Orthomodular lattices admitting no states. J. Combin. Theory Ser. A 10, 119–132 (1971)
Greenberger D.M., Horne M.A., Shimony A., Zeilinger A.: Bell’s theorem without inequalities. Am. J. Phys. 58(12), 1131–1143 (1990)
Grötschel M., Padberg M.W.: On the symmetric travelling salesman problem. I. Inequalities. Math. Program. 16(3), 265–280 (1979)
Haag R.: Local quantum physics. Texts and Monographs in Physics, 2nd ed. Springer, Berlin (1996)
Haemers W.: On some problems of Lovász concerning the Shannon capacity of a graph. IEEE Trans. Inform. Theory 25(2), 231–232 (1979)
Haemers, W.: An upper bound for the Shannon capacity of a graph. In: Algebraic Methods in Graph Theory, Vol. I, II (Szeged, 1978), pp. 267–272 (1981)
Henson, J.: Quantum contextuality from a simple principle? (2012). arXiv:1210.5978
Imrich, W., Klavz̆ar, S. (eds): Product Graphs: Structure and Recognition. Wiley-Intersciene, New York (2000)
Junge M., Navascués M., Palazuelos C., Pérez-García D., Scholz V.B., Werner R.F.: Connes embedding problem and Tsirelson’s problem. J. Math. Phys. 52(1), 012102, 12 (2011)
Kadison, R.V., Ringrose, J.R.: Fundamentals of the theory of operator algebras, vol. I. Pure and Applied Mathematics, Elementary Theory, vol. 100. Academic Press Inc. [Harcourt Brace Jovanovich Publishers], New York (1983)
Karp, R.M.: Reducibility Among Combinatorial Problems, pp. 85–103 (1972)
Klyachko A.A., Can M.A., Binicioglu S., Shumovsky A.S.: A simple test for hidden variables in spin-1 system. Phys. Rev. Lett. 101, 020403–020406 (2008)
Knuth DcE.: The sandwich theorem. Electron. J. Comb. 1, A1 (1994)
Kochen S., Specker E.P.: The problem of hidden variables in quantum mechanics. J. Math. Mech. 17, 59–87 (1967)
Lasserre, J.B.: An explicit equivalent positive semidefinite program for nonlinear 0–1 programs. SIAM J. Optim. 12(3), 756–769 (2002) (electronic).
Laurent M.: A comparison of the Sherali-adams, Lovász–Schrijver and Lasserre relaxations for 0-1 programming. Math. Oper. Res. 28(3), 470–496 (2003)
Liang Y.-C., Spekkens Robert W., Wiseman Howard M.: Specker’s parable of the overprotective seer: a road to contextuality, nonlocality and complementarity. Phys. Rep. 506(1–2), 1–39 (2011)
Lisonĕk, P., Badziąg, P., Portillo, J., Cabello, A.: The simplest Kochen–Specker set (2013). arXiv:1308.6012
Lovász L.: Normal hypergraphs and the perfect graph conjecture. Discrete Math. 2(3), 253–267 (1972)
Lovász L.: Kneser’s conjecture, chromatic number, and homotopy. J. Combin. Theory Ser. A 25(3), 319–324 (1978)
Lovász L.: On the Shannon capacity of a graph. IEEE Trans. Inform. Theory 25(1), 1–7 (1979)
Lane, S.M., Moerdijk, I.: Sheaves in geometry and logic. In: Universitext. Springer, New York (1979). A first introduction to topos theory, Corrected reprint of the 1992 edition
Naddef D., Pochet Y.: The symmetric traveling salesman polytope revisited. Math. Oper. Res. 26(4), 700–722 (2001)
Navascués, M., Guryanova, Y., Hoban, M., Acín, A.: Almost Quantum Correlations (2014). arXiv:1403.4621
Navascués M., Pironio S., Acín A.: Bounding the set of quantum correlations. Phys. Rev. Lett. 98(1), 010401 (2007)
Navascués M., Pironio S., Acín A.: A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations. N. J. Phys. 10(7), 073013 (2008)
Pavičić M., McKay B.D., Megill N.D., Fresl K.: Graph approach to quantum systems. J. Math. Phys. 51(10), 102103, 31 (2010)
Pavičić M., Merlet J.-P., McKay B., Megill Norman D.: Kochen–Specker vectors. J. Phys. A 38(7), 1577–1592 (2005)
Pironio S.: Lifting bell inequalities. J. Math. Phys. 46, 062112 (2005)
Pironio S., Acín A., Brunner N., Gisin N., Massar S., Scarani V.: Deviceindependent quantum key distribution secure against collective attacks. N. J. Phys. 11, 045021 (2009)
Pironio S., Acín A., Massar S., de la Giroday A.B., Matsukevich D., Maunz P., Olmschenk S., Hayes D., Luo L., Manning T.A., Monroe C.: Random numbers certified by Bell’s theorem. Nature 464, 1021–1024 (2010)
Pironio S., Navascués M., Acín A.: Convergent relaxations of polynomial optimization problems with noncommuting variables. SIAM J. Optim. 20(5), 2157–2180 (2010)
Popescu S., Rohrlich D.: Quantum nonlocality as an axiom. Found. Phys. 24(3), 379–385 (1994)
The Univalent Foundations Program, Homotopy type theory. Self-published (2013). Available at homotopytypetheory.org/book
Randall C.H., Foulis D.J.: Operational statistics. II. Manuals of operations and their logics. J. Math. Phys. 14, 1472–1480 (1973)
Sainz A.B., Fritz T., Augusiak R., Brask J.B., Chaves R., Leverrier A., Acín A.: Exploring the Local Orthogonality principle. Phys. Rev. A 89, 032117 (2014)
Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, pp. 216–226 (1978)
Schrijver A.: Combinatorial Optimization. Polyhedra and Efficiency, Algorithms and Combinatorics, vol. 24. Springer, Berlin (2003)
Shannon, C.E.: The zero error capacity of a noisy channel. In: Institute of Radio Engineers. Transactions on Information Theory, IT-2, no. September 8–19 (1956)
Shultz F.W.: A characterization of state spaces of orthomodular lattices. J. Combin. Theory Ser. A 17, 317–328 (1974)
Specker, E.: The logic of non-simultaneously decidable propositions (1960). Translation from the German original by M.P. Seevinck (2011), arXiv:1103.4537
Spekkens R.W.: Contextuality for preparations, transformations, and unsharp measurements. Phys. Rev. A 71(5), 052108 (2005)
Svozil K.: Randomness & Undecidability in Physics. World Scientific Publishing Co. Inc., River Edge (1993)
Svozil, K., Tkadlec, J.: Greechie diagrams, nonexistence of measures in quantum logics and Kochen–Specker-type constructions. J. Math. Phys. 37(11) (1996)
Tarski, A. (ed.): A Decision Method for Elementary Algebra and Geometry 2nd ed. University of California Press, Berkeley and Los Angeles (1951)
Tkadlec, J.: Diagrams of Kochen–Specker type constructions. Internat. J. Theoret. Phys. 39(3), 921–926 (2000). Quantum structures ’98 (Liptovský Ján)
Tsirelson B.S.: Some results and problems on quantum Bell-type inequalities. Hadronic J. Suppl. 8, 329–345 (1993)
Voloshin V.I.: Introduction to Graph and Hypergraph Theory. Nova Science Publishers Inc., New York (2009)
V.N. N.: Consistent families of measures and their extensions. Theory of Probability and its Applications 7(2), 147–163 (1962)
Weisstein, E.W.: Generalized quadrangle. From MathWorld-A Wolfram Web Resource, mathworld.wolfram.com/GeneralizedQuadrangle.html
Wilce, A.: Formalism and interpretation in quantum theory, 2008. A slightly edited version of a paper to appear as part of a Festchrift for Jeff Bub
Wilce, A.: Test spaces. In: Handbook of Quantum Logic and Quantum Structures-Quantum Logic, pp. 443–549 (2009)
Wolf, M.M., Cubitt, T.S., Perez-García, D.: Are problems in quantum information theory (un)decidable? (2011). http://arxiv.org/abs/1111.5425
Wright, R.: The state of the pentagon: a nonclassical example. In: Mathematical Foundations of Quantum Theory (Proc. Conf., Loyola Univ., New Orleans, La., 1977), pp. 255–274 (1978)
Yan B.: Quantum correlations are tightly bound by the exclusivity principle. Phys. Rev. Lett. 110, 260406 (2013)
Zeh, H.D.: Quantum nonlocality vs. Einstein locality (2006). http://www.rzuser.uni-heidelberg.de/~as3/nonlocality.html
Ziegler G.M.: Lectures on polytopes. In: Graduate Texts in Mathematics, vol. 152. Springer, New York (1995)
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by A. Winter
We thank Mateus Araújo, Adán Cabello, Ravi Kunjwal, Simone Severini, Alexander Wilce, Andreas Winter, Elie Wolfe and Gilles Zémor for comments and discussion, András Salamon for help with a reference, and Will Traves for help on \({\texttt{MathOverflow}}\). Research at Perimeter Institute is supported by the Government of Canada through Industry Canada and by the Province of Ontario through the Ministry of Economic Development and Innovation. T.F. was supported by the John Templeton foundation. Part of this work was done while A.L. was at the Institute for Theoretical Physics, ETH Zürich. A.L. was supported by the Swiss National Science Foundation through the National Centre of Competence in Research “Quantum Science and Technology”, by the CNRS through the PEPS ICQ2013 TOCQ, and through the European Research Council (Grant No. 258932). A.B.S. was supported by the ERC SG PERCENT and by the Spanish projects FIS2010-14830 and FPU:AP2009-1174 PhD grant. A.A. was supported by the ERC CoG QITBOX, the Spanish projects FOQUS and DIQIP and the John Templeton Foundation.
Rights and permissions
About this article
Cite this article
Acín, A., Fritz, T., Leverrier, A. et al. A Combinatorial Approach to Nonlocality and Contextuality. Commun. Math. Phys. 334, 533–628 (2015). https://doi.org/10.1007/s00220-014-2260-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00220-014-2260-1