Certifying Signaling Dimension
Formally, certifying the signaling dimension requires that a channel $\mathbf{P}\in\mathcal{P}^{X \to Y}$ is checked against all tight Bell inequalities bounding the signaling polytopes. In general cases, it is difficult derive these Bell inequalities and test them all. Despite this challenge, the signaling dimension can be bounded. We now provide methods that efficiently compute upper and lower bounds on the signaling dimension. For more details please refer to our work Certifying the Classical Simulation Cost of a Quantum Channel.
Bounds
In most cases, it is not feasible to compute the exact signaling of a channel, however, loose lower and upper bounds can be determined with efficiency.
Lower Bounds
SignalingDimension.maximum_likelihood_lower_bound
— Functionmaximum_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.
SignalingDimension.ambiguous_lower_bound
— Functionambiguous_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 inP
).
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)]
.
Upper Bounds
SignalingDimension.trivial_upper_bound
— Functiontrivial_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\}.\]
SignalingDimension.attains_trivial_upper_bound
— Functionattains_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.
SignalingDimension.upper_bound
— Functionupper_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.
Quantum Channel Certification
The signaling dimension is a device-independent metric which can be applied to quantum and classical channels alike. To certify a quantum channel, the signaling correlations must first be obtained. This can be done by selecting a set of input states $\Psi := \{\rho_x\}_{x\in\mathcal{X}}$ and using semi-definite programming to optimize the POVM. The objective function of the optimization is expressed as a BellScenario.BellGame
.
The BellScenario.Nonlocality
module performs the POVM optimization.
Code Example: Optimizing Quantum Measurements Against Maximum Likelihood Game
using BellScenario
using QBase
X = 3 # num inputs
Y = 3 # num outputs
d = 2 # qudit
scenario = LocalSignaling(X, Y, d)
# maximum likelihood game for the scenario
facet = BellGame([1 0 0;0 1 0;0 0 1], 2)
Ψ = States.trine_qubits
# performing semi-definite programming to find optimal POVM
optimization_dict = Nonlocality.optimize_measurement(scenario, facet, Ψ)
Dict{String,Any} with 5 entries: "scenario" => LocalSignaling(3, 3, 2) "game" => [1 0 0; 0 1 0; 0 0 1] "violation" => -1.54039e-8 "povm" => Array{Complex{Float64},2}[[0.666667+0.0im -4.63e-8+0.0im; -5.2… "states" => QBase.States.Qubit[[1.0+0.0im 0.0+0.0im; 0.0+0.0im 0.0+0.0im],…
The output dictionary contains useful information regarding the optimization. The POVM can then be used to construct the quantum signaling correlations.
Π = Observables.POVM(optimization_dict["povm"])
quantum_strategy(Π, Ψ)
3×3 Strategy: 0.666667 0.166667 0.166667 0.166667 0.666667 0.166667 0.166667 0.166667 0.666667