Signaling Polytopes

Let $\mathcal{C}_d^{X\to Y}$ denote the set of classical signaling correlations produced using one-way, noiseless classical communication and shared randomness. This set is a convex polyhedron that we refer to as the signaling polytope. As a convex polyhedron, the signaling polytope $\mathcal{C}_d^{X \to Y}$ admits two equivalent descriptions^{[Ziegler2012]}:

• Vertex Description: Let $\mathcal{V}_d^{X\to Y}\subset\mathcal{C}_d^{X\to Y}$ denote the set of signaling polytope vertices. Then, the signaling polytope is defined as the convex-hull of its vertices $\mathcal{V}_d^{X\to Y}$,

\[ \mathcal{C}_d^{X \to Y} = \text{Conv}(\mathcal{V}_d^{X \to Y}).\]

• Half-Space Description: Let $\mathcal{F}_d^{X \to Y}$ denote the set of closed half-space inequalities on $\mathbb{R}^{Y \times X}$ that tightly bound the signaling polytope $\mathcal{C}_d^{X\to Y}$. We refer to an inequality in $\mathcal{F}_d^{X \to Y}$ as a facet. Then, the signaling polytope is defined as the intersection of all inequalities in $\mathcal{F}_d^{X\to Y}$,

\[ \mathcal{C}_d^{X\to Y} = \cap\{\mathcal{F}_d^{X \to Y}\}.\]

The BellScenario.LocalPolytope module provides tools for computing each of these representations.

Vertices

A signaling polytope vertex $\mathbf{V}\in\mathcal{V}_d^{X \to Y}$ must satisfy:

• Elements $V(y|x) \in \{0,1\}$ for all $y\in\mathcal{Y}$ and $x\in\mathcal{X}$
• $\text{Rank}(\mathbf{V}) \leq d$

The total number of vertices in $\mathcal{V}_d^{X \to Y}$ is then counted by ^{[DallArno2017]}

\[|\mathcal{V}_d^{X \to Y}| = \sum_{c=1}^d \left\{X \atop c \right\}\binom{Y}{c}c!,\]

where $\{\}$ denotes Stirling's number of the second kind and $\binom{Y}{c}$ denotes $Y$ $choose$ $c$.

Code Example: Counting Vertices

Signaling polytope vertices can be counted using the BellScenario.LocalPolytope.num_vertices method.

using BellScenario

X = 4    # num inputs
Y = 4    # num outputs
d = 2    # dit signaling

scenario = LocalSignaling(X, Y, d)

# Count the number of vertices for the signaling polytope
num_vertices = LocalPolytope.num_vertices(scenario)

88

Code Example: Enumerating Vertices

The set of vertices $\mathcal{V}_d^{X \to Y}$ can be enumerated using the BellScenario.LocalPolytope.vertices method. Since vertices have 0/1 elements, they can be represented by BellScenario.DeterministicStrategy.

using BellScenario

X = 4    # num inputs
Y = 4    # num outputs
d = 2    # dit signaling

scenario = LocalSignaling(X, Y, d)

# Compute vertices in the "normalized" subspace.
# These vertices can be fed directly into polytope transformation methods.
vertices = LocalPolytope.vertices(scenario)

# Convert each vertex into a `DeterministicStrategy` matrix form.
deterministic_strategies = map(v -> convert(DeterministicStrategy, v, scenario), vertices)

88-element Array{DeterministicStrategy,1}:
 [1 1 1 1; 0 0 0 0; 0 0 0 0; 0 0 0 0]
 [0 0 0 0; 1 1 1 1; 0 0 0 0; 0 0 0 0]
 [0 0 0 0; 0 0 0 0; 1 1 1 1; 0 0 0 0]
 [0 0 0 0; 0 0 0 0; 0 0 0 0; 1 1 1 1]
 [1 1 1 0; 0 0 0 1; 0 0 0 0; 0 0 0 0]
 [0 0 1 0; 1 1 0 1; 0 0 0 0; 0 0 0 0]
 [1 1 0 0; 0 0 1 1; 0 0 0 0; 0 0 0 0]
 [1 0 1 0; 0 1 0 1; 0 0 0 0; 0 0 0 0]
 [0 1 0 0; 1 0 1 1; 0 0 0 0; 0 0 0 0]
 [0 1 1 0; 1 0 0 1; 0 0 0 0; 0 0 0 0]
 ⋮
 [0 0 0 0; 0 0 0 0; 0 1 1 0; 1 0 0 1]
 [0 0 0 0; 0 0 0 0; 1 0 0 0; 0 1 1 1]
 [0 0 0 0; 0 0 0 0; 0 0 0 1; 1 1 1 0]
 [0 0 0 0; 0 0 0 0; 1 1 0 1; 0 0 1 0]
 [0 0 0 0; 0 0 0 0; 0 0 1 1; 1 1 0 0]
 [0 0 0 0; 0 0 0 0; 0 1 0 1; 1 0 1 0]
 [0 0 0 0; 0 0 0 0; 1 0 1 1; 0 1 0 0]
 [0 0 0 0; 0 0 0 0; 1 0 0 1; 0 1 1 0]
 [0 0 0 0; 0 0 0 0; 0 1 1 1; 1 0 0 0]

Facets

Let the tuple $(\mathbf{G},\gamma) \in \mathcal{F}_d^{X \to Y}$ designate a facet of $\mathcal{C}_d^{X \to Y}$ where $\mathbf{G}\in \mathbb{R}^{Y\times X}$ and $\gamma\in \mathbb{R}$. The half-space inequality is then expressed as

\[\gamma \geq \langle \mathbf{G}, \mathbf{P}\rangle = \sum_{x,y}G_{y,x}P(y|x)\]

where $\langle\mathbf{G},\mathbf{P}\rangle$ is the Euclidean inner product with some matrix $\mathbf{P}\in\mathcal{P}^{X\to Y}$. A facet $(\mathbf{G},\gamma)\in\mathcal{F}_d^{X \to Y}$ must satisfy:

• $\gamma \geq \langle \mathbf{G}, \mathbf{V} \rangle$ for all vertices $\mathbf{V} \in \mathcal{V}_d^{X \to Y}$.
• $\gamma = \langle \mathbf{G}, \mathbf{V} \rangle$ for at least $X(Y-1)$ affinely independent vertices $\mathcal{V}_d^{X \to Y}$.

A facet inequaliity $(\mathbf{G},\gamma)\in\mathcal{F}_d^{X \to Y}$ tightly bounds the signaling polytope $\mathcal{C}_d^{X\to Y}$, therefore, if $\gamma \ngeq \langle\mathbf{G},\mathbf{P}\rangle$, then $\mathbf{P}\notin\mathcal{C}_d^{X \to Y}$. Hence the inequalities $(\mathbf{G},\gamma)\in\mathcal{F}_d^{X \to Y}$ can verify whether a channel $\mathbf{P}\in\mathcal{P}^{X\to Y}$ is also contained by the signaling polytope $\mathcal{C}_d^{X \to Y}$. Within the context of Bell scenarios, these facets are referred to as tight Bell inequalities and are discussed in greater detail in the Bell Inequalities section.

Code Example: Complete Facet Enumeration

A facet inequality is represented by the BellScenario.BellGame type. Note however, that the polytope computation software represents mmatrix $\mathbf{G}$ with a column-major vectorization in the $"normalized"$ subspace.

using BellScenario

X = 3    # num inputs
Y = 3    # num outputs
d = 2    # dit signaling

scenario = LocalSignaling(X, Y, d)

# Compute vertices in the "normalized" subspace.
vertices = LocalPolytope.vertices(scenario)

# Compute complete set of facets in "normalized" subspace.
facets = LocalPolytope.facets(vertices)["facets"]

# Convert each facet into `BellGame` form.
bell_games = map( f -> convert(BellGame, f, scenario), facets)

# printing γ ≥ G for each bell game
for bg in bell_games
    println(bg.β, " ≥ ", bg.game)
end

1 ≥ [0 0 0; 1 0 0; 1 0 0]
1 ≥ [1 0 0; 0 0 0; 1 0 0]
1 ≥ [0 0 0; 0 1 0; 0 1 0]
1 ≥ [0 1 0; 0 0 0; 0 1 0]
1 ≥ [0 0 0; 0 0 1; 0 0 1]
1 ≥ [0 0 1; 0 0 0; 0 0 1]
1 ≥ [0 0 1; 0 0 1; 0 0 0]
1 ≥ [0 1 0; 0 1 0; 0 0 0]
1 ≥ [1 0 0; 1 0 0; 0 0 0]
2 ≥ [0 0 1; 0 1 0; 1 0 0]
2 ≥ [0 1 0; 0 0 1; 1 0 0]
2 ≥ [0 0 1; 1 0 0; 0 1 0]
2 ≥ [0 1 0; 1 0 0; 0 0 1]
2 ≥ [1 0 0; 0 0 1; 0 1 0]
2 ≥ [1 0 0; 0 1 0; 0 0 1]

Adjacency Decomposition

The values of input $x$ and output $y$ for a signaling scenario are merely labels. Rearranging these labels cannot change the structure of the signaling polytope. Hence the signaling polytope is invariant under permutations of inputs and outputs^[Rosset2014]. This permutation symmetry results in a transitivity of vertices and facets. That is, any permutation of a vertex (or facet) is also a vertex (or facet) of $\mathcal{C}_d^{X \to Y}$. Furthermore, we define a vertex class (facet class) as the set of all vertices (facets) generated by taking row/column permutations. Hence, there exists a canonical set of generator vertices and facets whose permutations describe the complete set of signaling polytope facets $\mathcal{F}_d^{X \to Y}$. Since the number of permutations scale as $(X!)$ and $(Y!)$, the set of generators is dramatically reduces in the total number vertices and facets needed to describe the polytope.

Given the permutation symmetry of singaling polytopes, the adjacency decomposition technique ^{[Christof2001]} is an effective algorithm for computing the generator facets of a convex polytope. Key advantages of the adjacency decomposition technique include:

• The complete set of facets does not need to be stored in memory, only the generator facets.
• If not run to completion, a partial list of generator facets is obtained.
• The computation can be widely parallelized.

Code Example: Adjacency Decomposition

The adjacency decomposition greatly reduces facet computation times and can be performed on signaling polytopes using the BellScenario.LocalPolytope.adjacency_decomposition method. Please refer to BellScenario.jl documentation for additional details on the arguments, outputs, and implementation of the adjacency decomposition algorithm.

using BellScenario

X = 6    # num inputs
Y = 4    # num outputs
d = 2    # dit signaling

scenario = LocalSignaling(X, Y, d)

# Compute vertices in the "normalized" subspace.
vertices = LocalPolytope.vertices(scenario)

# The adjacency decomposition requires a facet to seed the algorithm.
facet_seed = BellGame([1 0 0 0 0 0;0 1 0 0 0 0;0 0 1 0 0 0;0 0 0 1 0 0], 2)

# Compute the complete set of generator facets
adj_dict = LocalPolytope.adjacency_decomposition(vertices, facet_seed, scenario)

# The generator facets are the keys of returned dictionary
for bell_game in keys(adj_dict)
    println(bell_game.β, " ≥ ", bell_game.game, "\n")
end

5 ≥ [1 1 1 0 0 0; 1 0 0 1 1 0; 0 1 0 1 0 1; 0 0 1 0 1 1]

4 ≥ [2 0 0 0 0 0; 1 1 1 0 0 0; 0 2 0 0 0 0; 0 0 2 0 0 0]

4 ≥ [2 0 0 0 0 0; 1 1 1 0 0 0; 0 2 0 0 0 0; 0 0 1 1 0 0]

1 ≥ [1 0 0 0 0 0; 1 0 0 0 0 0; 1 0 0 0 0 0; 0 0 0 0 0 0]

2 ≥ [1 0 0 0 0 0; 1 0 0 0 0 0; 0 1 0 0 0 0; 0 0 1 0 0 0]

3 ≥ [1 1 0 0 0 0; 1 0 1 0 0 0; 0 1 1 0 0 0; 0 0 0 1 0 0]

2 ≥ [1 0 0 0 0 0; 0 1 0 0 0 0; 0 0 1 0 0 0; 0 0 0 1 0 0]

4 ≥ [2 0 0 0 0 0; 1 1 1 0 0 0; 0 1 0 1 0 0; 0 0 1 0 1 0]

4 ≥ [1 1 1 0 0 0; 1 0 0 1 0 0; 0 1 0 0 1 0; 0 0 1 0 0 1]

References