×

Computational tools for solving a marginal problem with applications in Bell non-locality and causal modeling. (English) Zbl 1416.81028

Summary: Marginal problems naturally arise in a variety of different fields: basically, the question is whether some marginal/partial information is compatible with a joint probability distribution. To this aim, the characterization of marginal sets via quantifier elimination and polyhedral projection algorithms is of primal importance. In this work, before considering specific problems, we review polyhedral projection algorithms with focus on applications in information theory, and, alongside known algorithms, we also present a newly developed geometric algorithm which walks along the face lattice of the polyhedron in the projection space. One important application of this is in the field of quantum non-locality, where marginal problems arise in the computation of Bell inequalities. We apply the discussed algorithms to discover many tight entropic Bell inequalities of the tripartite Bell scenario as well as more complex networks arising in the field of causal inference. Finally, we analyze the usefulness of these inequalities as nonlocality witnesses by searching for violating quantum states.

MSC:

81P40 Quantum coherence, entanglement, quantum correlations
81P05 General and philosophical questions in quantum theory
94A15 Information theory (general)
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
81P45 Quantum information, communication, networks (quantum-theoretic aspects)
81P15 Quantum measurement theory, state operations, state preparations
94A17 Measures of information, entropy
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Studený, M., Marginal problem in different calculi of ai, Advances in Intelligent Computing—IPMU, 348-359, (1994), Berlin: Springer, Berlin
[2] Lauritzen, S. L.; Spiegelhalter, D. J., Local computations with probabilities on graphical structures and their application to expert systems, J. R. Stat. Soc. B, 157-224, (1988) · Zbl 0684.68106
[3] Pearl, J., Causality, (2009), Cambridge: Cambridge University Press, Cambridge
[4] Spirtes, P.; Glymour, N.; Scheienes, R., Causation, Prediction, and Search, (2001), Cambridge, MA: MIT Press, Cambridge, MA
[5] Yeung, R. W., Information Theory, Network Coding, (2008), Berlin: Springer, Berlin
[6] Bell, J. S., On the Einstein-Podolsky-Rosen paradox, Physics, 1, 195, (1964) · doi:10.1103/PhysicsPhysiqueFizika.1.195
[7] Pitowsky, I., Quantum Probability-Quantum Logic, (1989), Berlin: Springer, Berlin · Zbl 0668.60096
[8] Brunner, N.; Cavalcanti, D.; Pironio, S.; Scarani, V.; Wehner, S., Bell nonlocality, Rev. Mod. Phys., 86, 419-478, (2014) · doi:10.1103/RevModPhys.86.419
[9] Pitowsky, I., Correlation polytopes: their geometry and complexity, Math. Program., 50, 395-414, (1991) · Zbl 0741.90054 · doi:10.1007/BF01594946
[10] Branciard, C.; Gisin, N.; Pironio, S., Characterizing the nonlocal correlations created via entanglement swapping, Phys. Rev. Lett., 104, (2010) · doi:10.1103/PhysRevLett.104.170401
[11] Branciard, C.; Rosset, D.; Gisin, N.; Pironio, S., Bilocal versus nonbilocal correlations in entanglement-swapping experiments, Phys. Rev. A, 85, (2012) · doi:10.1103/PhysRevA.85.032119
[12] Fritz, T., Beyond bell’s theorem: correlation scenarios, New J. Phys., 14, (2012) · Zbl 1448.81026 · doi:10.1088/1367-2630/14/10/103001
[13] Tavakoli, A.; Skrzypczyk, P.; Cavalcanti, D.; Acín, A., Nonlocal correlations in the star-network configuration, Phys. Rev. A, 90, (2014) · doi:10.1103/PhysRevA.90.062109
[14] Chaves, R.; Kueng, R.; Brask, J. B.; Gross, D., Unifying framework for relaxations of the causal assumptions in bell’s theorem, Phys. Rev. Lett., 114, (2015) · doi:10.1103/PhysRevLett.114.140403
[15] Chaves, R., Polynomial bell inequalities, Phys. Rev. Lett., 116, (2016) · Zbl 1356.81098 · doi:10.1103/PhysRevLett.116.010402
[16] Tavakoli, A., Bell-type inequalities for arbitrary noncyclic networks, Phys. Rev. A, 93, (2016) · doi:10.1103/PhysRevA.93.030101
[17] Lee, C. M.; Spekkens, R. W., Causal inference via algebraic geometry: necessary and sufficient conditions for the feasibility of discrete causal models, J. Caus. Infer., 5, (2017)
[18] Wolfe, E.; Spekkens, R. W.; Fritz, T., The inflation technique for causal inference with latent variables, (2016)
[19] Carvacho, G.; Andreoli, F.; Santodonato, L.; Bentivegna, M.; Chaves, R.; Sciarrino, F., Experimental violation of local causality in a quantum network, Nat. Commun., 8, 14775, (2017) · doi:10.1038/ncomms14775
[20] Andreoli, F.; Carvacho, G.; Santodonato, L.; Chaves, R.; Sciarrino, F., Maximal qubit violation of n-locality inequalities in a star-shaped quantum network, New J. Phys., 19, (2017) · Zbl 1516.81009 · doi:10.1088/1367-2630/aa8b9b
[21] Geiger, D.; Meek, C., Quantifier elimination for statistical problems, 226-235, (1999), San Mateo, CA: Morgan Kaufmann Publishers, San Mateo, CA
[22] Garcia, L. D.; Stillman, M.; Sturmfels, B., Algebraic geometry of bayesian networks, J. Symb. Comput., 39, 331-355, (2005) · Zbl 1126.68102 · doi:10.1016/j.jsc.2004.11.007
[23] Braunstein, S. L.; Caves, C. M., Information-theoretic bell inequalities, Phys. Rev. Lett., 61, 662-665, (1988) · doi:10.1103/PhysRevLett.61.662
[24] Cerf, N. J.; Adami, C., Entropic bell inequalities, Phys. Rev. A, 55, 3371-3374, (1997) · doi:10.1103/PhysRevA.55.3371
[25] Chaves, R.; Fritz, T., Entropic approach to local realism and noncontextuality, Phys. Rev. A, 85, (2012) · doi:10.1103/PhysRevA.85.032113
[26] Fritz, T.; Chaves, R., Entropic inequalities and marginal problems, IEEE Trans. Inf. Theory, 59, 803, (2013) · Zbl 1364.94231 · doi:10.1109/TIT.2012.2222863
[27] Chaves, R., Entropic inequalities as a necessary and sufficient condition to noncontextuality and locality, Phys. Rev. A, 87, (2013) · doi:10.1103/PhysRevA.87.022102
[28] Chaves, R.; Luft, L.; Gross, D., Causal structures from entropic information: geometry and novel scenarios, New J. Phys., 16, (2014) · Zbl 1451.81008 · doi:10.1088/1367-2630/16/4/043001
[29] Henson, J.; Lal, R.; Pusey, M. F., Theory-independent limits on correlations from generalized bayesian networks, New J. Phys., 16, (2014) · Zbl 1451.81028 · doi:10.1088/1367-2630/16/11/113043
[30] Kurzyński, P.; Kaszlikowski, D., Information-theoretic metric as a tool to investigate nonclassical correlations, Phys. Rev. A, 89, (2014) · doi:10.1103/PhysRevA.89.012103
[31] Poh, H. S.; Markiewicz, M.; Kurzyński, P.; Cerè, A.; Kaszlikowski, D.; Kurtsiefer, C., Probing quantum-classical boundary with compression software, New J. Phys., 18, (2016) · Zbl 1456.68038 · doi:10.1088/1367-2630/18/3/035011
[32] Chaves, R.; Budroni, C., Entropic nonsignaling correlations, Phys. Rev. Lett., 116, (2016) · doi:10.1103/PhysRevLett.116.240501
[33] Weilenmann, M.; Colbeck, R., Inability of the entropy vector method to certify nonclassicality in linelike causal structures, Phys. Rev. A, 94, (2016) · doi:10.1103/PhysRevA.94.042112
[34] Weilenmann, M.; Colbeck, R., Non-shannon inequalities in the entropy vector approach to causal structures, Quantum, 2, 57, (2018) · doi:10.22331/q-2018-03-14-57
[35] Budroni, C.; Miklin, N.; Chaves, R., Indistinguishability of causal relations from limited marginals, Phys. Rev. A, 94, (2016) · doi:10.1103/PhysRevA.94.042127
[36] Weilenmann, M.; Colbeck, R., Analysing causal structures with entropy, Proc. R. Soc. A, 473, 20170483, (2017) · Zbl 1404.82017 · doi:10.1098/rspa.2017.0483
[37] Miklin, N.; Abbott, A. A.; Branciard, C.; Chaves, R.; Budroni, C., The entropic approach to causal correlations, New J. Phys., 19, (2017) · Zbl 1516.81041 · doi:10.1088/1367-2630/aa8f9f
[38] Pienaar, J., Which causal structures might support a quantum-classical gap?, New J. Phys., 19, (2017) · doi:10.1088/1367-2630/aa673e
[39] Pawłowski, M.; Paterek, T.; Kaszlikowski, D.; Scarani, V.; Winter, A.; Żukowski, M., Information causality as a physical principle, Nature, 461, 1101-1104, (2009) · doi:10.1038/nature08400
[40] Short, A. J.; Wehner, S., Entropy in general physical theories, New J. Phys., 12, (2010) · Zbl 1360.94170 · doi:10.1088/1367-2630/12/3/033023
[41] Dahlsten, O. C O.; Lercher, D.; Renner, R., Tsirelson’s bound from a generalized data processing inequality, New J. Phys., 14, (2012) · Zbl 1448.81101 · doi:10.1088/1367-2630/14/6/063024
[42] Barnum, H.; Barrett, J.; Clark, L. O.; Leifer, M.; Spekkens, R.; Stepanik, N.; Wilce, A.; Wilke, R., Entropy and information causality in general probabilistic theories, New J. Phys., 12, (2010) · Zbl 1360.81026 · doi:10.1088/1367-2630/12/3/033024
[43] Chaves, R.; Majenz, C.; Gross, D., Information-theoretic implications of quantum causal structures, Nat. Commun., 6, 5766, (2015) · doi:10.1038/ncomms6766
[44] Chaves, R.; Brask, J. B.; Brunner, N., Device-independent tests of entropy, Phys. Rev. Lett., 115, (2015) · doi:10.1103/PhysRevLett.115.110501
[45] Budroni, C.; Cabello, A., Bell inequalities from variable-elimination methods, J. Phys. A: Math. Theor., 45, (2012) · Zbl 1252.81011 · doi:10.1088/1751-8113/45/38/385304
[46] Williams, H. P., Fourier’s method of linear programming and its dual, Am. Math. Mon., 93, 681-695, (1986) · Zbl 0618.90065 · doi:10.1080/00029890.1986.11971923
[47] Duffin, R.; Balinski, M., On fourier’s analysis of linear inequality systems, Pivoting and Extension, 71-95, (1974), Berlin: Springer, Berlin
[48] Huynh, T.; Lassez, C.; Lassez, J-L, Fourier algorithm revisited, 117-131, (1990), Berlin: Springer, Berlin · Zbl 1493.68401
[49] Davenport, J. H.; Heintz, J., Real quantifier elimination is doubly exponential, J. Symb. Comput., 5, 29-35, (1988) · Zbl 0663.03015 · doi:10.1016/S0747-7171(88)80004-X
[50] Lassez, J-L, Querying constraints, 288-298, (1990), New York: ACM, New York
[51] Lassez, C.; Lassez, J. L., Quantifier elimination for conjunctions of linear constraints via a convex hull algorithm, Symbolic and Numerical Computation for Artificial Intelligence, (1990), New York: Academic, New York
[52] Huynh, T.; Lassez, C.; Lassez, J-L, Practical issues on the projection of polyhedral sets, Ann. Math. Artif. Intell., 6, 295-315, (1992) · Zbl 0875.68821 · doi:10.1007/BF01535523
[53] Imbert, J., Fourier’s elimination: which to choose?, PPCP, 1, 117-129, (1993)
[54] Simon, A.; King, A., Exploiting sparsity in polyhedral analysis, 336-351, (2005), Berlin: Springer, Berlin · Zbl 1141.68654
[55] Jones, C. N.; Kerrigan, E. C.; Maciejowski, J. M., Equality set projection: a new algorithm for the projection of polytopes in halfspace representation, Technical Report CUED/F-INFENG/TR.463, (2004)
[56] Würflinger, L. E.; Bancal, J-D; Acín, A.; Gisin, N.; Vértesi, T., Nonlocal multipartite correlations from local marginal probabilities, Phys. Rev. A, 86, (2012) · doi:10.1103/PhysRevA.86.032117
[57] Gläßle, T., Pythonic shannon type inequality finder, (2016)
[58] McMullen, P., The maximum numbers of faces of a convex polytope, Mathematika, 17, 179-184, (1970) · Zbl 0217.46703 · doi:10.1112/S0025579300002850
[59] Khachiyan, L., Polynomial algorithms in linear programming, USSR Comput. Math. Math. Phys., 20, 53-72, (1980) · Zbl 0459.90047 · doi:10.1016/0041-5553(80)90061-0
[60] Karmarkar, N., A new polynomial-time algorithm for linear programming, 302-311, (1984), New York: ACM, New York · Zbl 0557.90065
[61] Dantzig, G. B., Origins of the simplex method, A History of Scientific Computing, 141-151, (1990), New York: ACM, New York
[62] Spielman, D.; Teng, S-H, Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time, 296-305, (2001), New York: ACM, New York · Zbl 1323.68636
[63] Monniaux, D.; Byron Cook, T. T.; Jackson, P., Quantifier elimination by lazy model enumeration, CAV 2010, 585-599, (2010), Berlin: Springer, Berlin
[64] Khachiyan, L.; Boros, E.; Borys, K.; Elbassioni, K.; Gurvich, V., Generating all vertices of a polyhedron is hard, Discrete Comput. Geom., 39, 174-190, (2008) · Zbl 1147.05040 · doi:10.1007/s00454-008-9050-5
[65] Bremner, D. D., On the complexity of vertex and facet enumeration for convex polytopes, PhD Thesis, (1998)
[66] Sommerville, D. M Y., The relations connecting the angle-sums and volume of a polytope in space of n dimensions, Proc. R. Soc. A, 115, 103-119, (1927) · JFM 53.0578.03 · doi:10.1098/rspa.1927.0078
[67] Elbassioni, K.; Lotker, Z.; Seidel, R., Upper bound on the number of vertices of polyhedra with-constraint matrices, Inf. Process. Lett., 100, 69-71, (2006) · Zbl 1185.68777 · doi:10.1016/j.ipl.2006.05.011
[68] Taylor, R.; Rajan, V., The efficient computation of uncertainty spaces for sensor-based robot planning, 231-236, (1988), Piscataway, NJ: IEEE, Piscataway, NJ
[69] Chazelle, B., An optimal convex hull algorithm in any fixed dimension, Discrete Comput. Geom., 10, 377-409, (1993) · Zbl 0786.68091 · doi:10.1007/BF02573985
[70] Balinski, M. L., On the graph structure of convex polyhedra in n-space, Pac. J. Math., 11, 431-434, (1961) · Zbl 0103.39602 · doi:10.2140/pjm.1961.11.431
[71] Grünbaum, B., Convex Polytopes, (1967), Berlin: Springer, Berlin
[72] McRae, W. B.; Davidson, E. R., An algorithm for the extreme rays of a pointed convex polyhedral cone, SIAM J. Comput., 2, 281-293, (1973) · Zbl 0267.65083 · doi:10.1137/0202023
[73] Chand, D. R.; Kapur, S. S., An algorithm for convex polytopes, J. ACM, 17, 78-86, (1970) · Zbl 0199.50902 · doi:10.1145/321556.321564
[74] Avis, D.; Bremner, D.; Seidel, R., How good are convex hull algorithms?, 7, 265-301, (1997) · Zbl 0877.68119 · doi:10.1016/S0925-7721(96)00023-5
[75] Gläßle, C. T., C++ Fourier-Motzkin eliminator, (2016)
[76] Christof, T.; Löbel, A., \( \mathtt{PORTA} \)—Polyhedron representation transformation algorithm, (2009)
[77] Fukuda, K., C implementation of the double description method
[78] Lörwald, S.; Reinelt, G., Panda: a software for polyhedral transformations, EURO J. Comput. Optim., 3, 297-308, (2015) · Zbl 1331.52001 · doi:10.1007/s13675-015-0040-0
[79] Fine, A., Hidden variables, joint probability, and the Bell inequalities, Phys. Rev. Lett., 48, 291-295, (1982) · doi:10.1103/PhysRevLett.48.291
[80] Clauser, J. F.; Horne, M. A.; Shimony, A.; Holt, R. A., Proposed experiment to test local hidden-variable theories, Phys. Rev. Lett., 23, 880-884, (1969) · Zbl 1371.81014 · doi:10.1103/PhysRevLett.23.880
[81] Zukowski, M.; Zeilinger, A.; Horne, M. A.; Ekert, A. K., ‘Event-ready-detectors’ bell experiment via entanglement swapping, Phys. Rev. Lett., 71, 4287-4290, (1993) · doi:10.1103/PhysRevLett.71.4287
[82] Tura, J.; Augusiak, R.; Sainz, A. B.; Vértesi, T.; Lewenstein, M.; Acín, A., Detecting nonlocality in many-body quantum states, Science, 344, 1256-1258, (2014) · Zbl 1355.81192 · doi:10.1126/science.1247715
[83] Collins, D.; Gisin, N.; Linden, N.; Massar, S.; Popescu, S., Bell inequalities for arbitrarily high-dimensional systems, Phys. Rev. Lett., 88, (2002) · Zbl 1243.81029 · doi:10.1103/PhysRevLett.88.040404
[84] Lewenstein, M.; Bruß, D.; Cirac, J. I.; Kraus, B.; Kuś, M.; Samsonowicz, J.; Sanpera, A.; Tarrach, R., Separability and distillability in composite quantum systems—a primer, J. Mod. Opt., 47, 2481-2499, (2000) · Zbl 1003.81006 · doi:10.1080/09500340008232176
[85] Bruß, D., Characterizing entanglement, J. Math. Phys., 43, 4237-4251, (2002) · Zbl 1060.81505 · doi:10.1063/1.1494474
[86] Gurvits, L., Classical deterministic complexity of edmonds’ problem and quantum entanglement, 10-19, (2003), New York: ACM, New York
[87] Gharibian, S., Strong NP-hardness of the quantum separability problem, Quantum Inf. Comput., 10, 343-360, (2010) · Zbl 1234.81033
[88] Peres, A., Separability criterion for density matrices, Phys. Rev. Lett., 77, 1413-1415, (1996) · Zbl 0947.81003 · doi:10.1103/PhysRevLett.77.1413
[89] Horodecki, M.; Horodecki, P.; Horodecki, R., Separability of mixed states: necessary and sufficient conditions, Phys. Lett. A, 223, 1-8, (1996) · Zbl 1037.81501 · doi:10.1016/S0375-9601(96)00706-2
[90] Chaves, R.; Luft, L.; Maciel, T. O.; Gross, D.; Janzing, D.; Schölkopf, B., Inferring latent structures via information inequalities, 112-121, (2014), Arlington, VA: AUAI Press, Arlington, VA
[91] Schmied, R.; Bancal, J-D; Allard, B.; Fadel, M.; Scarani, V.; Treutlein, P.; Sangouard, N., Bell correlations in a Bose-Einstein condensate, Science, 352, 441-444, (2016) · Zbl 1355.81052 · doi:10.1126/science.aad8665
[92] Steudel, B.; Janzing, D.; Schölkopf, B., Causal markov condition for submodular information measures, 464-476, (2010), Madison, WI: OmniPress, Madison, WI
[93] Steudel, B.; Ay, N., Information-theoretic inference of common ancestors, CoRR, (2010)
[94] Jarlskog, C., A recursive parametrization of unitary matrices, J. Math. Phys., 46, (2005) · Zbl 1111.15027 · doi:10.1063/1.2038607
[95] Acín, A.; Andrianov, A.; Costa, L.; Jané, E.; Latorre, J. I.; Tarrach, R., Generalized schmidt decomposition and classification of three-quantum-bit states, Phys. Rev. Lett., 85, 1560-1563, (2000) · doi:10.1103/PhysRevLett.85.1560
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.