Edit on GitHub

Bell Inequalities

A linear inequality $\langle\mathbf{G},\mathbf{P}\rangle\leq \gamma$ is defined as a Bell inequality of a signaling polytope $\mathcal{C}_d^{X \to Y}$ if all channels $\mathbf{P}\in\mathcal{C}_d^{X \to Y}$ satisfy the Bell inequality, that is,

\[ \mathcal{C}_d^{X \to Y}\subset \{\mathbf{P}\in\mathcal{P}^{X \to Y}|\; \langle\mathbf{G},\mathbf{P}\rangle\leq \gamma \}.\]

A Bell inequality is denoted by the tuple $(\mathbf{G},\gamma)$ where $\mathbf{G}\in\mathbb{R}^{Y\times X}$ and $\gamma\in\mathbb{R}$ . It is useful to apply a game interpretation to a Bell inequality. In the case of local signaling scenarios, a Bell inequality can be interpreted as a cooperative guessing game played by Alice and Bob. In this interpretation, Alice is shown an input $x\in[X]$ and sends a message to Bob using a limited amount of communication. Bob then makes a guess $y\in[Y]$. The matrix $\mathbf{G}$ specifies the reward for outputting $y$ when given input $x$. The objective of the game is then to score higher than $\gamma$, that is, the objective is to violate the Bell inequality $(\mathbf{G}, \gammma)$. Hence Alice and Bob strategize their encoding and decoding schemes to maximize the reward. If they are able to score higher than $\gamma$, then Alice and Bob "win" the game.

We now discuss a subset of general Bell inequalities for signaling polytopes. Further details about these inequalities are provided in Certifying the Classical Simulation Cost of a Quantum Channel.

SignalingDimension.k_guessing_game — Function

The $k$-guessing game is a general family of Bell inequalities for signaling polytopes. For any integer $k\in[0,Y]$ a $k$-guessing game Bell inequality $(\mathbf{G}_{\text{K}},\gamma_{\text{K}})$ bounds the signaling polytope $\mathcal{C}_d^{\binom{Y}{k}\to Y }$. The columns of matrix $\mathbf{G}_{\text{K}}\in \mathbf{R}^{Y \times \binom{Y}{k}}$ consist of all $\binom{Y}{k}$ ways to arrange $k$ unit elements and $(Y-k)$ null elements. Hence each input $x\in[X]$ corresponds to a unique set of $k$ correct answers out of $Y$ possible answers. The upper bound is $\gamma_{\text{K}} = \binom{Y}{k} - \binom{Y-d}{k}$.

A $k$-guessing game Bell inequality is constructed with the k_guessing_game method,

k_guessing_game(Y :: Int64, d :: Int64, k :: Int64) :: BellGame

Parameters:

  • Y - The number of outputs
  • d - The signaling dimension
  • k - The number of unit elements in each column. Must satisfy Y ≥ k ≥ 0.

For example,

using SignalingDimension

G_K = k_guessing_game(6,2,3)

# output

6×20 BellScenario.BellGame:
 1  1  1  1  1  1  1  1  1  1  0  0  0  0  0  0  0  0  0  0
 1  1  1  1  0  0  0  0  0  0  1  1  1  1  1  1  0  0  0  0
 1  0  0  0  1  1  1  0  0  0  1  1  1  0  0  0  1  1  1  0
 0  1  0  0  1  0  0  1  1  0  1  0  0  1  1  0  1  1  0  1
 0  0  1  0  0  1  0  1  0  1  0  1  0  1  0  1  1  0  1  1
 0  0  0  1  0  0  1  0  1  1  0  0  1  0  1  1  0  1  1  1

The upper bound is then

G_K.β

# output

16

The k_guessing_game can alternatively take a BellScenario.LocalSignaling(X, Y, d) scenario as input.

k_guessing_game( scenario :: LocalSignaling, k :: Int64 ) :: BellGame

A DomainError is thrown if scenario.X != binomial(scenario.Y, k).

source
SignalingDimension.ambiguous_guessing_game — Function

Ambiguous guessing games are a family of Bell inequalities for signaling polytopes. An ambiguous guessing game, denoted by $(\mathbf{G}_{\text{Q}},\gamma_{\text{Q}})$, bounds the signaling polytope $\mathcal{C}_d^{X \to Y}$. The $Y \times X$ matrix $\mathbf{G}_{\text{Q}}$ is described as having two types of rows:

  • Guessing Rows: one column contains a non-zero element of value $(X - d + 1)$;
  • Ambiguous Rows: each column contains a $1$.

For any integer $k \in [0,Y]$ An ambiguous guessing game is defined to have $k$ guessing rows and $(Y-k)$ ammbiguous rows. The upper bound on the ambiguous guessing game Bell inequality is then $\gamma_{\text{Q}} = d(X-d+1)$.

The ambiguous_guessing_game method constructs an ambiguous guessing game Bell inequality with k guessing rows.

ambiguous_guessing_game(X::Int64, Y::Int64, d::Int64, k::Int64) :: BellGame

Parameters:

  • X - The number of inputs
  • Y - The number of outputs
  • d - The signaling dimension
  • k - Th number of guessing rows. Must satisfy Y ≥ k ≥ 0.

For example, the following constructed ambiguous guessing game has four guessing rows and 3 ambiguous rows.

using SignalingDimension

(X, Y, d) = (6, 7, 3)

k = 4        # num guessing rows

G_Q = ambiguous_guessing_game(X, Y, d, k)

# output

7×6 BellScenario.BellGame:
 4  0  0  0  0  0
 0  4  0  0  0  0
 0  0  4  0  0  0
 0  0  0  4  0  0
 1  1  1  1  1  1
 1  1  1  1  1  1
 1  1  1  1  1  1
G_Q.β

# output

12

Alternatively, the ambiguous_guessing_game can accept a BellScenario.LocalSignaling(X, Y, d) scenario.

ambiguous_guessing_game(scenario :: LocalSignaling, k :: Int64) :: BellGame
source

Tight Bell Inequalities

A signaling polytope Bell inequality $(\mathbf{G},\gamma)$ is said to be tight if it is a facet of the $\mathcal{C}_d^{X \to Y}$ signaling polytope see Facets section. Tight Bell inequalities of a signaling polytope $\mathcal{C}_d^{X \to Y}$ are important because their violation witnesses the use of more than $d$ dit classical communication. Hence if $\langle\mathbf{G},\mathbf{P}\rangle\nleq \gamma$, then $\mathbf{P}\notin \mathcal{C}_d^{X \to Y}$. The SignalingDimension.jl provides a catalog of tight Bell inequality which bound general signaling polytopes.

Computed Facets

Using the adjacency decomposition technique, we've computed a broad range of signaling polytope facets. Computed facets of the signaling polytope are found in the data/ directory.

Quick Adjacency Decompositions

In the data/quick_adjacency_decomposition/ directory, the adjacency decomposition algorithm is used to find the generating facets of the signaling polytope. The polytope computation scripts are found in the script/quick_adjacency_decomposition/ directory. They are intended to run quickly on a laptop computer.

Data is provided in two formats:

  • .txt files are human readable
  • .ieq file format readable by BellScenario.jl.
Note: Filenames

The scripts and produced data are named as X-d-Y.jl or X-d-Y.txt. Numbers replace X, Y, and d when particular signaling polytopes are considered. If the label X, Y, or d is used, then the script runs over a range of that parameter.

Theoretical Facets

The following list of Bell inequalities are proven to be tight in Certifying the Classical Simulation Cost of a Quantum Channel. Each of the following methods constructs a canonical facet for the signaling polytope $\mathcal{C}_d^{X \to Y}$. The constructed facet inequalities are represented using the BellScenario.BellGame type. All row and column permutations of facets are also facets of $\mathcal{C}_d^{X \to Y}$.

SignalingDimension.maximum_likelihood_facet — Function

The maximum likelihood facet $(\mathbf{G}_{\text{ML}},d)$ tightly bounds the $\mathcal{C}_d^{N \to N}$ signaling polytope for $N > d > 1$. The matrix $\mathbf{G}_{\text{ML}}$ is a $(k=1)$-guessing game (see k_guessing_game), hence, $\mathbf{G}_{\text{ML}}=\mathbb{I}_{N}$ the $N\times N$ identity matrix. The upper bound is $d \geq \langle \mathbf{G}_{\text{ML}}, \mathbf{P}\rangle$ for any channel $\mathbf{P}\in\mathcal{C}_d^{N \to N}$.

maximum_likelihood_facet( N :: Int64, d :: Int64 ) :: BellGame

Construct the maximum likelihood facet for the $\mathcal{C}_d^{N \to N}$ signaling polytope. Note that N specifies the number of inputs and outputs. For example,

using SignalingDimension

N = 4    # number of inputs and outputs
d = 2    # bit signaling

G_ML = maximum_likelihood_facet(N, d)

# output

4×4 BellScenario.BellGame:
 1  0  0  0
 0  1  0  0
 0  0  1  0
 0  0  0  1
G_ML.β   # the upper bound

# output

2

A DomainError is thrown if the following requirements aren't satisfied:

  • `N > 2
  • N > d > 1
source
SignalingDimension.ambiguous_guessing_facet — Function
ambiguous_guessing_facet( Y :: Int64, d :: Int64 ) :: BellGame

Constructs the ambiguous guessing facet for the `\mathcal{C}_d^{(Y-1)\to Y} polytope. This is a special case of the [ambiguousguessinggame](@ref) whereY = X - 1`. For example,

using SignalingDimension

Y = 5
d = 3

G_Q = ambiguous_guessing_facet(Y, d)

# output

5×4 BellScenario.BellGame:
 2  0  0  0
 0  2  0  0
 0  0  2  0
 0  0  0  2
 1  1  1  1
G_Q.β

# output

6

A DomainError is thrown if the inputs don't satisfy the following requirements:

  • Y ≥ 4
  • (Y - 2) ≥ d ≥ 2
source
SignalingDimension.anti_guessing_facet — Function
anti_guessing_facet( N :: Int64, d :: Int64, ε :: Int64 ) :: BellGame

Constructs the anti-guessing facet of the $\mathcal{C}_d^{N \to N}$ signaling polytope. Input ε sets the size of the $(k=N-1)$-guessing game block while the remaining unit elements are arranged along the diagonal. The upper bound of the anti-guessing game Bell inequality is $\gamma = \varepsilon + d - 2$. For example,

using SignalingDimension

N = 6    # number of inputs and outputs
d = 2    # dit signaling
ε = 4    # anti-guessing block size

G_A = anti_guessing_facet(N,d,ε)

# output

6×6 BellScenario.BellGame:
 0  1  1  1  0  0
 1  0  1  1  0  0
 1  1  0  1  0  0
 1  1  1  0  0  0
 0  0  0  0  1  0
 0  0  0  0  0  1
G_A.β    # upper bound

# output

4

Note in the above example that

A DomainError is thrown if the following requirements aren't satisfied:

  • N ≥ 4
  • (N - 2) ≥ d ≥ 2
  • (N - d + 1) ≥ ε ≥ 3
source
SignalingDimension.k_guessing_facet — Function
k_guessing_facet( Y :: Int64, d :: Int64, k :: Int64 ) :: BellGame

Constructs the $k$-guessing facet for the $\mathcal{C}_d^{\binom{Y}{k}\to Y}$ signaling polytope. A $k$-guessing game is tight when $Y = d + k$. Note that k is the number of unit elements in each column.

A DomainError is satisfied if the following requirements aren't satisfied:

  • Y == k + d
  • Y ≥ 3
source
SignalingDimension.coarse_grained_input_ambiguous_guessing_facet — Function
coarse_grained_input_ambiguous_guessing_facet(
    Y :: Int64,
    d :: Int64
) :: BellGame

Constructs a canonical form for a input coarse-grained ambiguous game. For example

using SignalingDimension

Y = 4
d = 2

G = coarse_grained_input_ambiguous_guessing_facet(Y, d)

# output

4×4 BellScenario.BellGame:
 2  0  0  0
 0  2  0  0
 0  0  1  1
 1  1  1  0

A DomainError is thrown if the inputs don't satisfy the following requirements:

  • Y ≥ 4
  • (Y - 2) ≥ d ≥ 2
source
SignalingDimension.non_negativity_facet — Function

A non-negativity facet reflects the fact that $P(y|x) \geq 0$. These facets bound all signaling polytopes.

non_negativity_facet( X :: Int64, Y :: Int64 ) :: BellGame

Constructs the non-negativity game for a channel with X inputs and Y outputs. For example

using SignalingDimension

G = non_negativity_facet(3, 4)

# output

4×3 BellScenario.BellGame:
 1  0  0
 1  0  0
 1  0  0
 0  0  0
G.β

# output

1

A DomainError is thrown if X or Y is not greater than 1.

source

Verification of Theoretical Facets

To verify the tightness of a Bell inequality, $X(Y-1)$ affinely independent vertices must be found to satisfy $\gamma = \langle \mathbf{G}, \mathbf{V} \rangle$. This procedure is facilitated by the following method.

SignalingDimension.verify_facet — Function
verify_facet(
    d :: Int64,
    facet :: BellScenario.BellGame,
    aff_ind_vertices :: Vector{Matrix{Int64}}
) :: Bool

Returns true if the affinely independent set of vertices aff_ind_vertices verifies that the facet is indeed a tight Bell inequality of the $\matcal{C}_d^{X \to Y}$ signaling polytope. Input d must align with the considered facet. This method checks that all provided vertices are:

  • extreme points of the $\mathcal{C}_d^{X \to Y}$ signaling polytope
  • satisfy the facet inequality with equality
  • affinely independent
Note

This method does not check that all signaling polytope vertices satisfy the facet inequality. For the cataloged Bell inequalities, this requirement can be analytically shown to hold in general. To verify the tightness of the Bell inequality, it therefore remains to find a sufficient number of affinely independent vertices that saturate the inequality.

source

To apply verify_facet, a Bell inequality and set of affinely independent vertices are required. For each cataloged signaling polytope facet, an enumeration of affinely independent vertices that saturate the Bell inequality is provided.

These enumerations are used to verify the tight Bell inequalities above over a broad range of signaling polytopes. These facet verifications are performed in the script/facet_verifications/ directory. Each verification runs as a script and prints the results to a .txt file or STDOUT. By default the scripts do not require arguments. The default parameter are set to run the test over several minutes. Arguments vary slightly for each script so refer to individual scripts for more details about their command line arguments and default parameters. For more details on how to run the scripts and interpret their results please refer to the Script Utilities section.