Certifying Signaling Dimension

maximum_likelihood_lower_bound( P :: BellScenario.AbstractStrategy ) :: Int64

Uses maximum likelihood estimation to efficiently compute the lower bound of the signaling dimension. For a channel $\mathbf{P}\in\mathcal{P}^{X \to Y}$, the maximum likelihood lower bound on the signaling dimension is expressed,

\[\kappa(\mathbf{P}) \geq \sum_{y\in[Y]} \max_{x\in[X]} P(y|x).\]

Since the maximum_likelihood_facet is present on all signaling polytopes, a lower bound can always be found with efficiency.

ambiguous_lower_bound( P :: BellScenario.AbstractStrategy ) :: Int64

Returns the lower bound on the signaling dimension as witnessed by family of ambiguous_guessing_game Bell inequalities. The intersection of the family of ambiguous guessing games forms the ambiguous polytope $\mathcal{A}_{k,d}^{X\to Y}$ where a violation to this polytope means that $\kappa(\mathbf{P}) \geq d$. Hence this method computes the smallest $d$ such that $\mathbf{P}\in\mathcal{A}_{k,d}^{X\to Y}$ for all $k$. Formally, the following equality is violated if $\mathbf{P}\notin\mathcal{A}_{k,d}^{X \to Y}$

\[d \geq \max_{k\in[Y]}\max_{\sigma\in \Omega_{Y}} \sum_{y=1}^{k} \max_{x\in[X]} P(\sigma(y)|x) + \frac{1}{X - d + 1}\sum_{y=k+1}^{Y}\sum_{x\in [n]} P(\sigma(y)|x)\]

where $\Omega_{Y}$ is the set of all permutations of $[Y]$.

!!! "note" Note: Considering all permutations of $k$ guessing rows can be costly. This performance is greatly improved by sorting the rows of $\mathbf{P}$ by their difference max(row...) - sum(row)/(X - d + 1) in non-increasing order.

In general, it may not be necessary to consider the entire range of $k$. For more specialized cases we provide the following methods:

ambiguous_lower_bound(
    P :: BellScenario.AbstractStrategy,
    k :: Int64
) :: Int64

Finds the ambiguous lower bound on $\kappa(\mathbf{P})$ for fixed $k$.

• P - Channel $\mathbf{P}\in\mathcal{P}^{X\to Y}$, a column stochastic matrix.
• k - The number of guessing rows.

A DomainError is thrown if:

• k < 1
• k > size(P)[1] (number of rows in P).

ambiguous_lower_bound(P :: BellScenario.Strategy, k_range :: UnitRange{Int64}) :: Int64

Returns the smallest integer d such that P is contained by all ambiguous polytopes with k in k_range.

A DomainError is thrown if k_range is not contained by the range [1:size(P,1)].

trivial_upper_bound( P :: BellScenario.AbstractStrategy ) :: Int64

The signaling dimension of channel cannot exceed the number of inputs or outputs. Therefore, the trivial upper bound for the signaling dimension of a channel $\mathbf{P}\in\mathcal{P}^{X \to Y}$ is simply,

\[\kappa(\mathbf{P}) \leq \min\{X,Y\}.\]

attains_trivial_upper_bound( P :: BellScenario.Strategy ) :: Bool

Returns true if the channel P attains the trivial_upper_bound. This method relies on the fact:

• When $d = X - 1$, the signaling polytope $\mathcal{C}_d^{X \to Y}$ is only bound by maximum likelihood facets.
• When $d = Y - 1$, the signaling polytope $\mathcal{C}_d^{X \to Y}$ is only bound by maximum likelihood and ambiguous facets.

upper_bound( P :: BellScenario.AbstractStrategy ) :: Int64

Returns an upper bound for the signaling dimension of a channel P. If attains_trivial_upper_bound returns true, then this upper bound is tight and designates the signaling dimension. Otherwise, a loose upper bound is provided. A lower bound can be found with the maximum_likelihood_lower_bound or ambiguous_lower_bound methods.