Bell Inequalities from Polyhedral Sampling
Christian Staufenbiel · 2026
Read Bell Inequalities from Polyhedral Sampling by Christian Staufenbiel (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-22859.txt.
Introduction
Staufenbiel presents Adjacency Sampling, a faster but partial method for finding Bell inequalities. Such inequalities certify quantum correlations and underpin device-independent key distribution. Enumerating every inequality means solving a hard facet problem on the Bell polytope, so the new method trades completeness for speed. Even so, it reproduces all known classes on previously solved polytopes. Where no complete enumeration exists it vastly expands known lists, including more than 25 times the earlier count in one scenario and nearly triple in another.
Catalog record
| CREATOR | Christian Staufenbiel |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 20133 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.22859
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Bell Inequalities from Polyhedral Sampling Christian Staufenbiel Abstract Bell inequalities play a central role in certifying quantum correlations and underpin protocols such as device-independent quantum key distribution. However, enumerating all Bell inequalities for a given scenario remains intractable beyond the simplest cases, as it requires solving a computationally hard facet enumeration problem on the associated Bell polytope. We propose the Adjacency Sampling method, which builds on the Adjacency Decomposition method but sacrifices completeness for speed. On previously solved Bell polytopes, the method reproduces every known class of inequalities. For scenarios where no complete enumeration exists, it greatly exceeds existing partial results: in ℒ 3 , 3 , 3 , 3 \mathcal{L}_{3,3,3,3} we obtain over 1.29 × 10 8 1.29\times 10^{8} classes, more than 25 times the previous count; in ℒ 4 , 5 , 2 , 2 \mathcal{L}_{4,5,2,2} we nearly triple the known list to 49 358 classes; and for ℒ 4 , 6 , 2 , 2 \mathcal{L}_{4,6,2,2} we report over 4.3 million classes. 1 Introduction Consider two spatially separated parties, each choosing from a set of measurement settings and observing one of several possible outcomes. This setup, known as a Bell scenario, lies at the heart of the study of non-locality in quantum mechanics. Bell showed that the correlations arising between the two parties from any local classical theory must satisfy certain linear inequalities [ 4 ] , now known as Bell inequalities. A violation of such an inequality certifies that the observed correlations are genuinely quantum and cannot be explained by any local classical model. Such quantum correlations have been confirmed in a loophole-free experimental test [ 15 ] . Beyond their foundational role, Bell inequalities have found practical applications, most notably in device-independent quantum key distribution (DIQKD) [ 1 ] , where the security of protocols relies on the verified violation of such inequalities. A Bell scenario is characterized by the number of settings and outcomes available to each party. Determining all Bell inequalities for a given scenario amounts to finding the facets of the associated Bell polytope [ 5 ] , a problem that is computationally hard in general [ 2 ] . While several exact algorithms exist [ 12 , 3 , 6 ] , they quickly become intractable as the number of settings and outcomes grows. For this reason, the complete set of Bell inequalities is known only for a few small scenarios. Recently, alternative approaches have been proposed that aim to generate possibly incomplete lists of Bell inequalities [ 16 , 7 ] . In this paper, we introduce the Adjacency Sampling (AS) method , a modification of the Adjacency Decomposition Method [ 6 ] that sacrifices completeness for a drastically reduced runtime. Although designed as a sampling technique, it recovers all known Bell inequalities, up to symmetry, for all tested, previously enumerated scenarios. To further test the method’s capabilities, we also validate it against enumerated Cut polytopes. Applying the method to larger, previously unsolved scenarios yields a significant number of new Bell inequalities. For \mathcal{L}_{3,3,3,3} , we identify more than 1.29\times 10^{8} classes of inequalities, compared to the previously known 4.8 million [ 19 ] . For \mathcal{L}_{4,5,2,2} , we find 49 358 classes, extending the 18 277 reported by Cope and Colbeck [ 7 ] . We also present the first results for \mathcal{L}_{4,6,2,2} , identifying more than 4.3 million classes of Bell inequalities. The remainder of this paper is organized as follows. Section 2 introduces the necessary background on convex polytopes, the dual description problem, and Bell and Cut polytopes. Section 3 reviews the Adjacency Decomposition Method. Section 4 presents the Adjacency Sampling Method and its implementation. Section 5 evaluates the method and presents new Bell inequalities. Section 6 concludes and gives an outlook for future research. 2 Convex Polytopes This section introduces the concepts for polytopes required in this work. For more thorough discussions on polytopes and their features refer to the books by Grünbaum [ 14 ] or Ziegler [ 24 ] . A convex polytope \mathcal{P} is defined as the convex hull over a finite set \mathcal{K}=\{x_{1},\ldots,x_{n}\} , where x_{i}\in\mathbb{R}^{d} : \mathcal{P}=conv(\mathcal{K})=\{\lambda_{1}x_{1}+\ldots+\lambda_{n}x_{n}\;:\;\lambda_{i}\geq 0,\;\sum_{i}\lambda_{i}=1\} (1) The minimal representation of \mathcal{P} is uniquely identified by its extremal points / vertices \mathcal{V}(\mathcal{P}) (V-representation). Equivalently, \mathcal{P} can be described as the intersection of m half-spaces (H-representation) \mathcal{P}=\{x\in\mathbb{R}^{d}\;|\;A\cdot x\leq b\}, (2) where A\in\mathbb{R}^{m\times d} and b\in\mathbb{R}^{m} . Any non-empty intersection of a supporting hyperplane \mathcal{H} in \mathbb{R}^{d} (i.e. \mathcal{H} does not cut through \mathcal{P} ) is called a face \mathcal{F} of \mathcal{P} \mathcal{F}=\mathcal{H}\cap\mathcal{P}. (3) It is important to note that \mathcal{F} is again a polytope of dimension k\leq dim(\mathcal{P}) , denoted as k -face or k -polytope. For a d -polytope \mathcal{P} , the (d-1) -faces are called facets, and the description of \mathcal{P} by the facet-defining inequalities is the minimal H-representation. 2.1 Automorphisms The combinatorial automorphism group of a polytope Aut(\mathcal{P}) contains all automorphisms of \mathcal{P} that preserve the face-inclusion relation, i.e. any face \mathcal{F} remains a face of \mathcal{P} under the transformation. Such transformations of \mathcal{P} can be represented by permutations \pi\in S_{n} of its vertices: \pi(\mathcal{P})=conv(\{v_{\pi(1)},\ldots,v_{\pi(n)}\})=\mathcal{P}. The automorphism group Aut(\mathcal{P}) is a subgroup of the symmetric group S_{n} where n=|\mathcal{V}(\mathcal{P})| . The automorphism group induces an equivalence relation on the faces of a polytope, e.g. for two faces \mathcal{F}_{1},\mathcal{F}_{2} : \mathcal{F}_{1}\equiv\mathcal{F}_{2}\leftrightarrow\exists\,\pi\in Aut(\mathcal{P})\;with\;\mathcal{F}_{1}=\pi(\mathcal{F}_{2}) A set of equivalent facets is called an orbit or facet-class . 2.2 Dual Description Problem Transforming between the H- and V-representation of any polytope is known as the dual description problem. Vertex Enumeration describes the process of obtaining the vertices \mathcal{V}(\mathcal{P}) from the H-representation, while the opposite process is known as Facet Enumeration . The conversion has wide-ranging applications in combinatorial optimization [ 9 ] and quantum information [ 5 ] . Several general-purpose algorithms have been developed for this task: Double Description Method [ 12 ] , Reverse search algorithms [ 3 ] , and beneath-and-beyond algorithms [ 17 ] , each subject to limitations in terms of scalability or suitability for specific polytope structures. In particular, the exponential behavior of the problem leads to extensive runtimes with increasing size of the input [ 2 ] . Recently, more efficient implementations of known methods yielded complete H-representations of polytopes, which were previously unavailable [ 8 ] . 2.3 Bell Polytopes Originally, Bell inequalities provided mathematical constraints to test if reality obeys local realism , a physical principle violated by the formulation of quantum mechanics [ 11 , 4 ] . Besides ruling out local-hidden-variable theories [ 15 ] , Bell inequalities found various applications such as Quantum Key Distribution [ 23 ] . Bell inequalities are the facets of the so-called Bell Polytope or Local Polytope \mathcal{L} . The task of finding Bell inequalities is thus a facet enumeration problem on such polytopes. A detailed introduction to the Bell Polytope can be found elsewhere [ 5 ] . The vertices \mathcal{V}(\mathcal{L}) can simply be derived from all possible deterministic correlations between the parties in a Bell experiment. In this work, we consider such experiments with two parties, where the first (second) party has m_{a} ( m_{b} ) inputs and n_{a} ( n_{b} ) outputs. The corresponding polytope is referred to by \mathcal{L}_{m_{a},m_{b},n_{a},n_{b}} . The