List of Bell inequalities derived by triangular elimination

Here is a program to generate tight Bell inequalities from the list of facets of the cut polytope of the complete graph. For background information about triangular elimination, see [1].

List and program

List: from-cut8.txt

Program: countbell.tar.gz

Program is written in Objective Caml and Perl. To run the program, you need the list [3] of facets of the cut polytope of the complete graph. For usage of the program, see README in the archive.

Format of list

Output of the program has 3 lines for each generated tight Bell inequalities.

* (output_number) <- input input_number
Cut m_A m_B | n_X n_A n_B | a[XA1] a[XA2] ... a[XAm_A] a[XB1] a[XB2] ... a[XBm_B] a[A1B1] a[A1B2] ... a[Am_ABm_B] <= 0
Cor m_A m_B | n_X n_A n_B | b[A1] b[A2] ... b[Am_A] b[B1] b[B2] ... b[Bm_B] b[A1B1] b[A1B2] ... b[Am_ABm_B] <= 0

For example, from-cut8.txt contains the following Bell inequality.

* (40381) <- input 144
Cut 5 5 | 1 3 3 | 1 0 -1 0 0 0 -1 -1 0 0 -1 0 -1 1 0 -1 0 -1 -1 1 -1 1 0 0 -1 -1 -1 0 0 0 0 1 -1 0 0 <= 0
Cor 5 5 | 1 3 3 | 0 -1 -1 -1 0 -2 0 -2 0 0 1 0 1 -1 0 1 0 1 1 -1 1 -1 0 0 1 1 1 0 0 0 0 -1 1 0 0 <= 0

The tight Bell inequaities are numbered in the order in which they are generated. The first line contains this number (output_number) as well as the number of the original facet of the cut polytope of the complete graph to which triangular elimination is applied (input_number).

The second line contains the coefficients of the generated Bell inequality in terms of the cut polytope of the complete tripartite graph K1,m_A,m_B. It also contains information on how the nodes of the complete graph are labelled. In the example above, the 144th facet of CUT8 uses only 7 nodes of K8, and the 7 nodes are labelled so that 1(=n_X) of them is labelled as X, 3(=n_A) of them are labelled as Ai and 3(=n_B) of them is labelled as Bj.

The third line contains the coefficients in terms of the correlation polytope of the complete bipartite graph Km_A,m_B.

In the notation used in [2], the Bell inequality above is represented as:

References

[1]
D. Avis, H. Imai, T. Ito and Y. Sasaki.
Two-party Bell inequalities derived from combinatorics via triangular elimination.
Journal of Physics A: Mathematical and General, vol. 38, no. 50, pp. 10971–10987, Dec. 2005.
Manuscript appeared in arXiv:quant-ph/0505060, May 2005. Revised in v3, Sept. 2005.

[2]
D. Collins and N. Gisin.
A relevant two qubit Bell inequality inequivalent to the CHSH inequality.
Journal of Physics A: Mathematical and General, 37(5):1775–1787, Feb. 2004.
Also available at arXiv:quant-ph/0306129.

[3]
Research Group Discrete Optimization, University of Heidelberg.
Cut polytope in SMAPO—“Small” 0/1-Polytopes in Combinatorial Optimization.


Tsuyoshi Ito