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: 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.

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

`* (`

output_number) <- inputinput_number

Cutm_Am_B|n_Xn_An_B|a[XA_{1}]a[XA_{2}] ...a[XA_{m_A}]a[XB_{1}]a[XB_{2}] ...a[XB_{m_B}]a[A_{1}B_{1}]a[A_{1}B_{2}] ...a[A<= 0_{m_A}B_{m_B}]

Corm_Am_B|n_Xn_An_B|b[A_{1}]b[A_{2}] ...b[A_{m_A}]b[B_{1}]b[B_{2}] ...b[B_{m_B}]b[A_{1}B_{1}]b[A_{1}B_{2}] ...b[A<= 0_{m_A}B_{m_B}]

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 K_{1,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 CUT_{8} uses only 7 nodes of K_{8}, 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 A_{i} and 3(=n_B) of them is labelled as B_{j}.

The third line contains the coefficients in terms of the correlation polytope of the complete bipartite graph K_{m_A,m_B}.

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

[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.