# Non-Shannon inequalities in the entropy vector approach to causal structures

Mirjam Weilenmann and Roger Colbeck

Department of Mathematics, University of York, Heslington, York, YO10 5DD, UK.

A causal structure is a relationship between observed variables that in general restricts the possible correlations between them. This relationship can be mediated by unobserved systems, modelled by random variables in the classical case or joint quantum systems in the quantum case. One way to differentiate between the correlations realisable by two different causal structures is to use entropy vectors, i.e., vectors whose components correspond to the entropies of each subset of the observed variables. To date, the starting point for deriving entropic constraints within causal structures are the so-called Shannon inequalities (positivity of entropy, conditional entropy and conditional mutual information). In the present work we investigate what happens when non-Shannon entropic inequalities are included as well. We show that in general these lead to tighter outer approximations of the set of realisable entropy vectors and hence enable a sharper distinction of different causal structures. Since non-Shannon inequalities can only be applied amongst classical variables, it might be expected that their use enables an entropic distinction between classical and quantum causal structures. However, this remains an open question. We also introduce techniques for deriving inner approximations to the allowed sets of entropy vectors for a given causal structure. These are useful for proving tightness of outer approximations or for finding interesting regions of entropy space. We illustrate these techniques in several scenarios, including the triangle causal structure.

### ► References

[1] Antonio Acín, Nicolas Gisin, and Lluis Masanes. From Bell's theorem to secure quantum key distribution. Physical review letters, 97 (12): 120405, 2006. ISSN 0031-9007. 10.1103/​PhysRevLett.97.120405.
https://doi.org/10.1103/PhysRevLett.97.120405

[2] Jonathan Barrett. Information processing in generalized probabilistic theories. Physical Review A, 75: 032304, 2007. 10.1103/​PhysRevA.75.032304.
https://doi.org/10.1103/PhysRevA.75.032304

[3] Jonathan Barrett, Lucien Hardy, and Adrian Kent. No signaling and quantum key distribution. Physical review letters, 95 (1): 010503, 2005. ISSN 0031-9007. 10.1103/​PhysRevLett.95.010503.
https://doi.org/10.1103/PhysRevLett.95.010503

[4] Sergey I. Bastrakov and Nikolai Yu Zolotykh. Fast method for verifying Chernikov rules in Fourier-Motzkin elimination. Computational Mathematics and Mathematical Physics, 55 (1): 160-167, 2015. ISSN 0965-5425. 10.1134/​S0965542515010042.
https://doi.org/10.1134/S0965542515010042

[5] John S. Bell. On the Einstein-Podolsky-Rosen paradox. Physics, 1 (3): 195-200, 1964. ISSN 01923188. 10.1002/​prop.19800281202.
https://doi.org/10.1002/prop.19800281202

[6] Cyril Branciard, Denis Rosset, Nicolas Gisin, and Stefano Pironio. Bilocal versus nonbilocal correlations in entanglement-swapping experiments. Physical Review A, 85 (3): 032119, 2012. ISSN 1050-2947. 10.1103/​PhysRevA.85.032119.
https://doi.org/10.1103/PhysRevA.85.032119

[7] Samuel L. Braunstein and Carlton M. Caves. Information-theoretic Bell inequalities. Physical Review Letters, 61 (6): 662-665, 1988. ISSN 0031-9007. 10.1103/​PhysRevLett.61.662.
https://doi.org/10.1103/PhysRevLett.61.662

[8] Josh Cadney, Noah Linden, and Andreas Winter. Infinitely many constrained inequalities for the von Neumann entropy. IEEE Transactions on Information Theory, 58 (6): 3657-3663, 2012. ISSN 0018-9448. 10.1109/​TIT.2012.2185036.
https://doi.org/10.1109/TIT.2012.2185036

[9] Nicolas J. Cerf and Christoph Adami. Entropic Bell inequalities. Physical Review A, 55 (5): 3371-3374, 1997. ISSN 1050-2947. 10.1103/​PhysRevA.55.3371.
https://doi.org/10.1103/PhysRevA.55.3371

[10] T. H. Chan. Balanced information inequalities. IEEE Trans. Inf. Theor., 49 (12): 3261-3267, 2003. ISSN 0018-9448. 10.1109/​TIT.2003.820037.
https://doi.org/10.1109/TIT.2003.820037

[11] Rafael Chaves. Entropic inequalities as a necessary and sufficient condition to noncontextuality and locality. Physical Review A, 87 (2): 022102, 2013. ISSN 1050-2947. 10.1103/​PhysRevA.87.022102.
https://doi.org/10.1103/PhysRevA.87.022102

[12] Rafael Chaves and Costantino Budroni. Entropic nonsignaling correlations. Phys. Rev. Lett., 116: 240501, 2016. 10.1103/​PhysRevLett.116.240501.
https://doi.org/10.1103/PhysRevLett.116.240501

[13] Rafael Chaves and Tobias Fritz. Entropic approach to local realism and noncontextuality. Physical Review A, 85 (3): 032113, 2012. ISSN 1050-2947. 10.1103/​PhysRevA.85.032113.
https://doi.org/10.1103/PhysRevA.85.032113

[14] Rafael Chaves, Lukas Luft, and David Gross. Causal structures from entropic information: geometry and novel scenarios. New Journal of Physics, 16 (4): 043001, 2014a. ISSN 1367-2630. 10.1088/​1367-2630/​16/​4/​043001.
https://doi.org/10.1088/1367-2630/16/4/043001

[15] Rafael Chaves, Lukas Luft, Thiago O. Maciel, David Gross, Dominik Janzing, and Bernhard Schölkopf. Inferring latent structures via information inequalities. In Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, pages 112-121, Corvallis, Oregon, 2014b. AUAI Press. URL arXiv:1407.2256.
arXiv:1407.2256

[16] Rafael Chaves, Christian Majenz, and David Gross. Information-theoretic implications of quantum causal structures. Nature communications, 6: 5766, 2015. ISSN 2041-1723. 10.1038/​ncomms6766.
https://doi.org/10.1038/ncomms6766

[17] Sergei Nikolaevich Chernikov. Contraction of systems of linear inequalities. Soviet mathematics Doklady, 1, 1960.

[18] Sergei Nikolaevich Chernikov. The convolution of finite systems of linear inequalities. USSR Computational Mathematics and Mathematical Physics, 5 (1): 1-24, 1965. ISSN 00415553. 10.1016/​0041-5553(65)90064-9.
https://doi.org/10.1016/0041-5553(65)90064-9

[19] Boris S. Cirel'son. Quantum generalizations of Bell's inequality. Letters in Mathematical Physics, 4 (2): 93-100, 1980. 10.1007/​BF00417500.
https://doi.org/10.1007/BF00417500

[20] John F. Clauser, Michael A. Horne, Abner Shimony, and Richard A. Holt. Proposed experiment to test local hidden-variable theories. Physical Review Letters, 23 (15): 880-884, 1969. ISSN 0031-9007. 10.1103/​PhysRevLett.23.880.
https://doi.org/10.1103/PhysRevLett.23.880

[21] Roger Colbeck. Quantum and Relativistic Protocols For Secure Multi-Party Computation. PhD thesis, University of Cambridge, 2007. Also available as arXiv:0911.3814.
arXiv:0911.3814

[22] Roger Colbeck and Adrian Kent. Private randomness expansion with untrusted devices. Journal of Physics A: Mathematical and Theoretical, 44 (9): 095305, 2011. ISSN 1751-8113. 10.1088/​1751-8113/​44/​9/​095305.
https://doi.org/10.1088/1751-8113/44/9/095305

[23] Daniel Collins, Nicolas Gisin, Noah Linden, Serge Massar, and Sandu Popescu. Bell inequalities for arbitrarily high-dimensional systems. Physical review letters, 88 (4): 040404, 2002. ISSN 0031-9007. 10.1103/​PhysRevLett.88.040404.
https://doi.org/10.1103/PhysRevLett.88.040404

[24] Randall Dougherty. Computations of linear rank inequalities on six variables. In IEEE International Symposium on Information Theory, pages 2819-2823. IEEE, 2014. ISBN 978-1-4799-5186-4. 10.1109/​ISIT.2014.6875348.
https://doi.org/10.1109/ISIT.2014.6875348

[25] Randall Dougherty, Christopher Freiling, and Kenneth Zeger. Six new non-Shannon information inequalities. In IEEE International Symposium on Information Theory, pages 233-236. IEEE, 2006. ISBN 1-4244-0505-X. 10.1109/​ISIT.2006.261840.
https://doi.org/10.1109/ISIT.2006.261840

[26] Randall Dougherty, Chris Freiling, and Kenneth Zeger. Linear rank inequalities on five or more variables. e-print arXiv:0910.0284, 2009.
arXiv:0910.0284

[27] Randall Dougherty, Chris Freiling, and Kenneth Zeger. Non-Shannon information inequalities in four random variables. e-print arXiv:1104.3602 , 2011.
arXiv:1104.3602

[28] Artur K Ekert. Quantum cryptography based on Bell's theorem. Physical review letters, 67 (6): 661-663, 1991. ISSN 1079-7114. 10.1103/​PhysRevLett.67.661.
https://doi.org/10.1103/PhysRevLett.67.661

[29] Arthur Fine. Joint distributions, quantum correlations, and commuting observables. Journal of Mathematical Physics, 23 (7): 1306, 1982a. ISSN 00222488. 10.1063/​1.525514.
https://doi.org/10.1063/1.525514

[30] Arthur Fine. Hidden variables, joint probability, and the Bell inequalities. Physical Review Letters, 48 (5): 291-295, 1982b. ISSN 0031-9007. 10.1103/​PhysRevLett.48.291.
https://doi.org/10.1103/PhysRevLett.48.291

[31] Tobias Fritz. Beyond Bell's theorem: correlation scenarios. New Journal of Physics, 14 (10): 103001, 2012. ISSN 1367-2630. 10.1088/​1367-2630/​14/​10/​103001.
https://doi.org/10.1088/1367-2630/14/10/103001

[32] Tobias Fritz and Rafael Chaves. Entropic inequalities and marginal problems. IEEE Transactions on Information Theory, 59 (2): 803-817, 2013. ISSN 0018-9448. 10.1109/​TIT.2012.2222863.
https://doi.org/10.1109/TIT.2012.2222863

[33] Luis David Garcia, Michael Stillman, and Bernd Sturmfels. Algebraic geometry of Bayesian networks. Journal of Symbolic Computation, 39 (3-4): 331-355, 2005. 10.1016/​j.jsc.2004.11.007.
https://doi.org/10.1016/j.jsc.2004.11.007

[34] Daniel M. Greenberger, Michael Horne, and Anton Zeilinger. Going beyond Bell's theorem. In M. Kafatos, editor, Bell's Theorem, Quantum Mechanics and Conceptions of the Universe, pages 69-72. Kluwer Academic, Dordrecht, The Netherlands, 1989. 10.1007/​978-94-017-0849-4_10.
https://doi.org/10.1007/978-94-017-0849-4_10

[35] Daniel Hammer, Andrei Romashchenko, Alexander Shen, and Nikolai Vereshchagin. Inequalities for Shannon entropy and Kolmogorov complexity. Journal of Computer and System Sciences, 60 (2): 442-464, 2000. ISSN 00220000. 10.1006/​jcss.1999.1677.
https://doi.org/10.1006/jcss.1999.1677

[36] Joe Henson, Raymond Lal, and Matthew F Pusey. Theory-independent limits on correlations from generalized Bayesian networks. New Journal of Physics, 16 (11): 113043, 2014. ISSN 1367-2630. 10.1088/​1367-2630/​16/​11/​113043.
https://doi.org/10.1088/1367-2630/16/11/113043

[37] Aubrey William Ingleton. Representation of matroids. In Dominic J A Welsh, editor, Combinatorial Mathematics and its applications, pages 149-167. Academic Press, 1971. ISBN 0-12-743350-3.

[38] Aditya Kela, Kai von Prillwitz, Johan Aberg, Rafael Chaves, and David Gross. Semidefinite tests for latent causal structures. e-print arXiv:1701.00652, 2017.
arXiv:1701.00652

[39] Ciarán M. Lee and Robert W. Spekkens. Causal Inference via Algebraic Geometry: Feasibility Tests for Functional Causal Structures with Two Binary Observed Variables. Journal of Causal Inference, 5 (2), 2017. ISSN 2193-3685. 10.1515/​jci-2016-0013.
https://doi.org/10.1515/jci-2016-0013

[40] Elliott H. Lieb and Mary B. Ruskai. Proof of the strong subadditivity of quantum-mechanical entropy. Journal of Mathematical Physics, 14 (12): 1938, 1973. ISSN 00222488. 10.1063/​1.1666274.
https://doi.org/10.1063/1.1666274

[41] Konstantin Makarychev, Yury Makarychev, Andrei Romashchenko, and Nikolai Vereshchagin. A new class of non-Shannon-type inequalities for entropies. Communications in Information and Systems, 2 (2): 147-166, 2002. ISSN 15267555. 10.4310/​CIS.2002.v2.n2.a3.
https://doi.org/10.4310/CIS.2002.v2.n2.a3

[42] Frantisek Matus. Infinitely many information inequalities. In IEEE International Symposium on Information Theory, pages 41-44. IEEE, 2007. ISBN 978-1-4244-1397-3. 10.1109/​ISIT.2007.4557201.
https://doi.org/10.1109/ISIT.2007.4557201

[43] Dominic Mayers and Andrew Yao. Quantum cryptography with imperfect apparatus. In Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS-98), pages 503-509, Los Alamitos, CA, USA, 1998. IEEE Computer Society. 10.1109/​SFCS.1998.743501.
https://doi.org/10.1109/SFCS.1998.743501

[44] William J. McGill. Multivariate information transmission. Psychometrika, 19 (2): 97-116, 1954. ISSN 0033-3123. 10.1007/​BF02289159.
https://doi.org/10.1007/BF02289159

[45] N. David Mermin. Simple unified form for the major no-hidden-variables theorems. Physical Review Letters, 65 (27): 3373-3376, 1990. ISSN 0031-9007. 10.1103/​PhysRevLett.65.3373.
https://doi.org/10.1103/PhysRevLett.65.3373

[46] Nikolai Miklin, Alastair A. Abbott, Cyril Branciard, Rafael Chaves, and Costantino Budroni. The entropic approach to causal correlations. e-print arXiv:1706.10270, 2017.
arXiv:1706.10270

[47] Carl A. Miller and Yaoyun Shi. Universal security for randomness expansion from the spot-checking protocol. SIAM Journal on Computing, 46: 1304-1335, 2017. 10.1137/​15M1044333.
https://doi.org/10.1137/15M1044333

[48] David Monniaux. Quantifier elimination by lazy model enumeration. In Tayssir Touili, Byron Cook, and Paul Jackson, editors, Computer Aided Verification: 22nd International Conference, CAV 2010, Edinburgh, UK, pages 585-599, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg. URL https:/​/​hal.archives-ouvertes.fr/​hal-00472831v2.
https:/​/​hal.archives-ouvertes.fr/​hal-00472831v2

[49] Mervin E Muller. A note on a method for generating points uniformly on n-dimensional spheres. Communications of the ACM, 2 (4): 19-20, 1959. 10.1145/​377939.377946.
https://doi.org/10.1145/377939.377946

[50] Marcin Pawłowski, Tomasz Paterek, Dagomir Kaszlikowski, Valerio Scarani, Andreas Winter, and Marek Żukowski. Information causality as a physical principle. Nature, 461 (7267): 1101-1104, 2009. ISSN 0028-0836. 10.1038/​nature08400.
https://doi.org/10.1038/nature08400

[51] Judea Pearl. Causality: Models, Reasoning, and Inference. Cambridge University Press, 2nd edition, 2009. ISBN 0521773628. 10.1215/​00318108-110-4-639.
https://doi.org/10.1215/00318108-110-4-639

[52] Asher Peres. Incompatible results of quantum measurements. Physics Letters A, 151 (3-4): 107-108, 1990. ISSN 03759601. 10.1016/​0375-9601(90)90172-K.
https://doi.org/10.1016/0375-9601(90)90172-K

[53] Jacques Pienaar. Which causal structures might support a quantum-classical gap? New Journal of Physics, 19 (4): 043021, 2017. 10.1088/​1367-2630/​aa673e.
https://doi.org/10.1088/1367-2630/aa673e

[54] N. Pippenger. The inequalities of quantum information theory. IEEE Transactions on Information Theory, 49: 773-789, 2003. ISSN 0018-9448. 10.1109/​TIT.2003.809569.
https://doi.org/10.1109/TIT.2003.809569

[55] Stefano Pironio, Antonio Acín, Serge Massar, Antoine Boyer de la Giroday, Dzimitry N Matsukevich, Peter Maunz, Steven Olmschenk, David Hayes, Le Luo, T Andrew Manning, and Christopher Monroe. Random numbers certified by Bell's theorem. Nature, 464 (7291): 1021-1024, 2010. ISSN 1476-4687. 10.1038/​nature09008.
https://doi.org/10.1038/nature09008

[56] Sandu Popescu and Daniel Rohrlich. Quantum nonlocality as an axiom. Foundations of Physics, 24 (3): 379-385, 1994. ISSN 0015-9018. 10.1007/​BF02058098.
https://doi.org/10.1007/BF02058098

[57] Claude E Shannon. A mathematical theory of communication. Bell System Technical Journal, 27 (3): 379-423, 1948. ISSN 00058580. 10.1002/​j.1538-7305.1948.tb01338.x.
https://doi.org/10.1002/j.1538-7305.1948.tb01338.x

[58] Bastian Steudel and Nihat Ay. Information-theoretic inference of common ancestors. Entropy, 17 (4): 2304-2327, 2015. ISSN 1099-4300. 10.3390/​e17042304.
https://doi.org/10.3390/e17042304

[59] B.S. Tsirelson. Some results and problems on quantum Bell-type inequalities. Hadronic Journal Supplement, 8: 329-345, 1993. URL https:/​/​ci.nii.ac.jp/​naid/​10026857475/​en/​.
https:/​/​ci.nii.ac.jp/​naid/​10026857475/​en/​

[60] Umesh Vazirani and Thomas Vidick. Fully device-independent quantum key distribution. Physical review letters, 113 (14): 140501, 2014. ISSN 1079-7114. 10.1103/​PhysRevLett.113.140501.
https://doi.org/10.1103/PhysRevLett.113.140501

[61] Weidong Xu, Jia Wang, and Jun Sun. A projection method for derivation of non-Shannon-type information inequalities. In IEEE International Symposium on Information Theory, pages 2116-2120. IEEE, 2008. ISBN 978-1-4244-2256-2. 10.1109/​ISIT.2008.4595363.
https://doi.org/10.1109/ISIT.2008.4595363

[62] M. Weilenmann and R. Colbeck. Analysing causal structures with entropy. Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences, 473 (2207), 2017. 10.1098/​rspa.2017.0483.
https://doi.org/10.1098/rspa.2017.0483

[63] Mirjam Weilenmann and Roger Colbeck. Inability of the entropy vector method to certify nonclassicality in linelike causal structures. Physical Review A, 94: 042112, 2016. 10.1103/​PhysRevA.94.042112.
https://doi.org/10.1103/PhysRevA.94.042112

[64] H. Paul Williams. Fourier's method of linear programming and its dual. The American Mathematical Monthly, 93 (9): 681-695, 1986. 10.1080/​00029890.1986.11971923.
https://doi.org/10.1080/00029890.1986.11971923

[65] Elie Wolfe, Robert W. Spekkens, and Tobias Fritz. The inflation technique for causal inference with latent variables. e-print arXiv:1609.00672, 2016.
arXiv:1609.00672

[66] R.W. Yeung. A framework for linear information inequalities. IEEE Transactions on Information Theory, 43 (6): 1924-1934, 1997. ISSN 00189448. 10.1109/​18.641556.
https://doi.org/10.1109/18.641556

[67] Zhen Zhang. On a new non-Shannon type information inequality. Communications in Information and Systems, 3 (1): 47-60, 2003. ISSN 15267555. 10.4310/​CIS.2003.v3.n1.a4.
https://doi.org/10.4310/CIS.2003.v3.n1.a4

[68] Zhen Zhang and Raymond W. Yeung. A non-Shannon-type conditional inequality of information quantities. IEEE Transactions on Information Theory, 43 (6): 1982-1986, 1997. ISSN 00189448. 10.1109/​18.641561.
https://doi.org/10.1109/18.641561

[69] Zhen Zhang and R.W. Yeung. On characterization of entropy function via information inequalities. IEEE Transactions on Information Theory, 44 (4): 1440-1452, 1998. ISSN 00189448. 10.1109/​18.681320.
https://doi.org/10.1109/18.681320

### ► Cited by (beta)

[1] T Gläßle, D Gross, R Chaves, "Computational tools for solving a marginal problem with applications in Bell non-locality and causal modeling", Journal of Physics A: Mathematical and Theoretical 51, 484002 (2018).

[2] Thomas C. Fraser, Elie Wolfe, "Causal compatibility inequalities admitting quantum violations in the triangle structure", Physical Review A 98, 022113 (2018).

(The above data is from Crossref's cited-by service. Unfortunately not all publishers provide suitable and complete citation data so that some citing works or bibliographic details may be missing.)