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
— FunctionThe $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 outputsd
- The signaling dimensionk
- The number of unit elements in each column. Must satisfyY ≥ 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)
.
SignalingDimension.ambiguous_guessing_game
— FunctionAmbiguous 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 inputsY
- The number of outputsd
- The signaling dimensionk
- Th number of guessing rows. Must satisfyY ≥ 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
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.
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
— FunctionThe 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
SignalingDimension.ambiguous_guessing_facet
— Functionambiguous_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) where
Y = 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
SignalingDimension.anti_guessing_facet
— Functionanti_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
SignalingDimension.k_guessing_facet
— Functionk_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
SignalingDimension.coarse_grained_input_ambiguous_guessing_facet
— Functioncoarse_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
SignalingDimension.non_negativity_facet
— FunctionA 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.
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
— Functionverify_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
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.
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.
SignalingDimension.aff_ind_maximum_likelihood_vertices
— Functionaff_ind_maximum_likelihood_vertices( N :: Int64, d :: Int64 ) :: Vector{Matrix{Int64}}
Enumerates an affinely independent set of vertices that maximize the maximum_likelihood_facet
.
A DomainError
is thrown if N > d > 1
is not satisfied.
SignalingDimension.aff_ind_non_negativity_vertices
— Functionaff_ind_non_negativity_vertices(
X :: Int64,
Y :: Int64
) :: Vector{Matrix{Int64}}
Enumerates an affinely independent set of deterministic, vertices that maximize the non_negativity_facet
A DomainError
is thrown if the inputs do not satisfy X > 1
and Y > 1
.
SignalingDimension.aff_ind_ambiguous_guessing_vertices
— Functionaff_ind_ambiguous_guessing_vertices(
Y :: Int64,
d :: Int64
) :: Vector{Matrix{Int64}}
Enumerates an affinely independent set of vertices that maximize the ambiguous_guessing_facet
.
A DomainError
is thrown if the inputs don't satisfy the following requirements:
Y ≥ 4
(Y - 2) ≥ d ≥ 2
SignalingDimension.aff_ind_coarse_grained_input_ambiguous_guessing_vertices
— Functionaff_ind_coarse_grained_input_ambiguous_guessing_vertices(
Y :: Int64,
d :: Int64
) :: Vector{Matrix{Int64}}
Enumerates an affinely independent set of vertices for the coarse_grained_input_ambiguous_guessing_facet
.
A DomainError
is thrown if the inputs don't satisfy the following requirements:
Y ≥ 4
(Y - 2) ≥ d ≥ 2
SignalingDimension.aff_ind_anti_guessing_vertices
— Functionaff_ind_anti_guessing_vertices(N :: Int64, d :: Int64, ε :: Int64) :: Vector{Matrix{Int64}}
Enumerates an affinely independent set of vertices for the anti_guessing_facet
.
Valid inputs are N ≥ 4
, (N - 1) > d > 1
, and (N - d + 1) ≥ ε ≥ 3
.
SignalingDimension.aff_ind_k_guessing_vertices
— Functionaff_ind_k_guessing_vertices(
Y :: Int64, d :: Int64, k :: Int64
) :: Vector{Matrix{Int64}}
Enumerates an affinely independent set of vertices for the k_guessing_facet
.
A DomainError
is thrown if the inputs do not satisfy Y ≥ 4
, d ≥ 2
and k ≥ 2
.
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.