Definitions for Limitations on device independent key secure against non signaling adversary via the squashed non-locality

QAlgorithms.Papers.Independent.Intakethird100.P22.CDArray

For arbitrary types $C,E,Z$, this abbreviates the type of all functions $p:Z\times C\times E\to\mathbb R$, written $p(z,c,e)$. No finiteness, nonemptiness, nonnegativity, or normalization is required.

QAlgorithms.Papers.Independent.Intakethird100.P22.CDObservation.apply

For finite types $C,E,Z$, an observation $g$ with a positive output size $m$, nonnegative input weights $u(c,z)$ summing to $1$ over $z$ for every $c$, and nonnegative output weights $v(c,z,e,j)$ summing to $1$ over $j$ for every $c,z,e$, an arbitrary array $p:Z\times C\times E\to\mathbb R$, and an output index $0\le j<m$, this defines

$$g[p](j)=\sum_{c\in C}\sum_{z\in Z}\sum_{e\in E} u(c,z)\,p(z,c,e)\,v(c,z,e,j).$$

The array $p$ need not satisfy any positivity, normalization, or marginal condition. If any summation index type is empty, the sum is zero.

QAlgorithms.Papers.Independent.Intakethird100.P22.CDObservation

For arbitrary types $C,E$ and a finite type $Z$, an observation consists of a natural number $m>0$, an input function $u:C\times Z\to\mathbb R$, and an output function $v:C\times Z\times E\times\{0,\ldots,m-1\}\to\mathbb R$, satisfying

$$u(c,z)\ge0,\qquad \sum_{z\in Z}u(c,z)=1 \quad\text{for every }c,$$

and

$$v(c,z,e,j)\ge0,\qquad \sum_{j=0}^{m-1}v(c,z,e,j)=1 \quad\text{for every }c,z,e.$$

No finiteness or nonemptiness of $C,E$, or nonemptiness of $Z$, is assumed. If $C$ is nonempty and $Z$ is empty, no such observation exists.

QAlgorithms.Papers.Independent.Intakethird100.P22.CompleteExtension

For input types $X,Y$, finite output types $A,B$, and a real array $p(x,y,a,b)$, a complete extension consists of positive natural numbers $u,v$ and, for each $z\in\{0,\ldots,u-1\}$, weights $w_{zi}$ and arrays $p_{zi}$, indexed by $i\in\{0,\ldots,v-1\}$. The array $p$ and every $p_{zi}$ must be nonnegative, sum to $1$ over $a,b$ for each $x,y$, and be nonsignaling: summing over $a$ gives a result independent of $x$, and summing over $b$ gives a result independent of $y$. Each weight family is nonnegative and sums to $1$, and $p=\sum_i w_{zi}p_{zi}$ pointwise. Every member with positive weight must be an extreme point of the set of such valid arrays: if it is a mixture $\lambda q+(1-\lambda)r$ of valid arrays with $0<\lambda<1$, then both $q$ and $r$ equal it. Furthermore, no finite decomposition of $p$ into valid arrays may have positive-weight support strictly contained in $\{p_{zi}:w_{zi}>0\}$. Finally, for every natural number $n$ and every decomposition $d$ of $p$ into $n$ valid arrays satisfying these same minimality conditions, there is exactly one $z<u$ such that, for every array $r$, the total weight assigned to $r$ by the $z$-th decomposition equals the total weight assigned to $r$ by $d$. Repeated members and zero weights are allowed; uniqueness concerns the input index matching all aggregate weights. The quantifier includes $n=0$, although its required weight sum cannot equal $1$.

QAlgorithms.Papers.Independent.Intakethird100.P22.CompleteExtension.measured

Given a real array $p$ and a complete extension $c$, whose positive input and output counts are $u$ and $v$, write its $z$-th decomposition as $p=\sum_{i<v}w_{zi}p_{zi}$. Here $p$ and the members are normalized, nonnegative nonsignaling arrays, each weight family is a probability law, each positive-weight member is an extreme valid array, no decomposition has strictly smaller positive support, and every finite minimal decomposition is matched in aggregate member weights by exactly one input $z$. For any function $d:\{0,\ldots,u-1\}\to\mathbb R$ and inputs $x\in X,y\in Y$, the measured function on $A\times B\times(\{0,\ldots,u-1\}\times\{0,\ldots,v-1\})$ is defined by

$$P(a,b,z,i)=d(z)\,w_{zi}\,p_{zi}(x,y,a,b).$$

There is no assumption here that $d$ is nonnegative or sums to $1$, so this definition does not itself require $P$ to be a probability law.

QAlgorithms.Papers.Independent.Intakethird100.P22.DeviceEnsemble.IsMinimal

For input types $X,Y$, finite output types $A,B$, a function $p$, a natural number $n$, and an ensemble $d=((w_i,p_i))_{i<n}$ of $p$, minimality means that every member with positive weight is a vertex and that, for every natural number $m$ and every ensemble $d'$ of $p$ with $m$ entries, the support of $d'$ is not a proper subset of the support of $d$. An ensemble has nonnegative weights summing to one, nonnegative normalized members with both no-signaling marginal identities, and pointwise weighted sum $p$; its support consists exactly of members having positive weight. A vertex is such a valid member whose expression as $tq+(1-t)r$, for valid $q,r$ and $0<t<1$, forces $q=r$ to equal that member. The comparison includes every competing ensemble, without requiring its members to be vertices. Zero-weight members of $d$ need not be vertices, repeated members are allowed, and the case $m=0$ supplies no competitor because no zero-entry ensemble exists.

QAlgorithms.Papers.Independent.Intakethird100.P22.DeviceEnsemble.massAt

For input types $X,Y$, finite output types $A,B$, a function $p$, a natural number $n$, an ensemble $d=((w_i,p_i))_{i<n}$ of $p$, and any function $v:X\times Y\times A\times B\to\mathbb R$, the mass at $v$ is

$$\sum_{i=0}^{n-1} \begin{cases} w_i,&p_i=v,\\ 0,&p_i\ne v. \end{cases}$$

An ensemble here has nonnegative weights summing to one, each member is nonnegative and normalized with both no-signaling marginal identities, and its weighted sum is $p$ pointwise. Equality $p_i=v$ means equality of the entire functions. All repeated occurrences of $v$ contribute their weights; absent members and zero-weight occurrences contribute zero. The ensemble hypotheses exclude $n=0$.

QAlgorithms.Papers.Independent.Intakethird100.P22.DeviceEnsemble

For input types $X,Y$, finite output types $A,B$, any function $p:X\times Y\times A\times B\to\mathbb R$, and any natural number $n$, an ensemble of $p$ with $n$ entries consists of real weights $w_i$ and functions $p_i:X\times Y\times A\times B\to\mathbb R$, indexed by $0\le i<n$, such that $w_i\ge0$, $\sum_iw_i=1$, every $p_i$ has nonnegative entries and sums to one over $A\times B$ at each input pair, both of its output marginals are independent of the other party’s input, and

$$p(x,y,a,b)=\sum_{i=0}^{n-1}w_i p_i(x,y,a,b)$$

for every $x,y,a,b$. Entries with zero weight must still satisfy all those validity conditions, and repeated members are allowed. Although $n=0$ is admitted as a parameter, no such ensemble exists then, because its empty weight sum would have to equal one.

QAlgorithms.Papers.Independent.Intakethird100.P22.DeviceEnsemble.support

For input types $X,Y$, finite output types $A,B$, a function $p$, a natural number $n$, and an ensemble $d=((w_i,p_i))_{i<n}$ of $p$, its support is the set

$$\{v:X\times Y\times A\times B\to\mathbb R\mid \exists i<n,\ w_i>0\ \text{and}\ p_i=v\}.$$

Here being an ensemble means that the weights are nonnegative and sum to one, each member is nonnegative, normalized, and has both no-signaling marginal identities, and their weighted sum is $p$ pointwise. Zero-weight entries do not contribute to the support, and repeated positive-weight members contribute only one element because the support is a set. An ensemble cannot have $n=0$.

QAlgorithms.Papers.Independent.Intakethird100.P22.EveChannel.apply

Let $A,B$ be arbitrary types, let $E$ be a finite type, and let $k$ consist of a positive integer $m$ and a real kernel $k(e,j)$ satisfying $k(e,j)\ge0$ and $\sum_{j=0}^{m-1}k(e,j)=1$ for every $e\in E$. For every real function $p:A\times B\times E\to\mathbb R$, applying $k$ produces the real function on $A\times B\times\{0,\ldots,m-1\}$ given by

$$(kp)(a,b,j)=\sum_{e\in E}p(a,b,e)\,k(e,j).$$

No probability assumptions are imposed on $p$, and $A,B$ need not be finite or nonempty. If $E$ is empty, the resulting function is identically zero.

QAlgorithms.Papers.Independent.Intakethird100.P22.EveChannel

For an arbitrary type $E$, an Eve channel consists of a natural number $m>0$ and a real kernel $k:E\times\{0,\ldots,m-1\}\to\mathbb R$ such that, for every $e\in E$,

$$k(e,j)\ge0\quad\text{for every }j,\qquad \sum_{j=0}^{m-1}k(e,j)=1.$$

There is no finiteness or nonemptiness assumption on $E$. When $E$ is empty, the kernel conditions are vacuous, while $m>0$ remains required.

QAlgorithms.Papers.Independent.Intakethird100.P22.GeneralLocalMap.apply

For types $X,Y,A,B,X_o,Y_o,A_o,B_o,L,M$, with $X,Y,A,B,A_o,B_o,L,M$ finite, let $g$ contain probability laws $\mu$ on $L$, $\nu$ on $M$, input probability laws $\alpha(l,x_o,\cdot)$ on $X$ and $\beta(l,y_o,\cdot)$ on $Y$, and output probability laws $\gamma(m,a,x,\cdot)$ on $A_o$ and $\delta(m,b,y,\cdot)$ on $B_o$, each normalized and nonnegative for every conditioning index. Given any real-valued box $p(x,y,a,b)$, this definition produces the box

$$(gp)(x_o,y_o,a_o,b_o)= \sum_{l,m,x,y,a,b} \mu(l)\nu(m)\alpha(l,x_o,x)\beta(l,y_o,y) p(x,y,a,b)\gamma(m,a,x,a_o)\delta(m,b,y,b_o).$$

The two latent weights occur as the product $\mu(l)\nu(m)$. No validity, normalization, or no-signaling hypothesis on $p$ is required; $X_o,Y_o$ need not be finite, and any empty summation index set gives a zero sum.

QAlgorithms.Papers.Independent.Intakethird100.P22.GeneralLocalMap

For types $X,Y,A,B,X_o,Y_o,A_o,B_o,L,M$, with $X,Y,A_o,B_o,L,M$ finite, this structure consists of two real probability laws $\mu:L\to\mathbb R$ and $\nu:M\to\mathbb R$; input kernels $\alpha:L\times X_o\times X\to\mathbb R$ and $\beta:L\times Y_o\times Y\to\mathbb R$; and output kernels $\gamma:M\times A\times X\times A_o\to\mathbb R$ and $\delta:M\times B\times Y\times B_o\to\mathbb R$. Every probability law here means pointwise nonnegative values summing to $1$. Thus $\alpha(l,x_o,\cdot)$ and $\beta(l,y_o,\cdot)$ must be probability laws for every $l,x_o,y_o$, while $\gamma(m,a,x,\cdot)$ and $\delta(m,b,y,\cdot)$ must be probability laws for every $m,a,b,x,y$, including indices assigned zero weight by $\mu$ or $\nu$. No finiteness assumption on $A,B,X_o,Y_o$, or nonemptiness assumption on any type, is explicitly required by this structure declaration; the normalization requirements themselves exclude empty target types whenever the corresponding law is required.

QAlgorithms.Papers.Independent.Intakethird100.P22.IsCD

For finite types $C,E$, an arbitrary type $Z$, and a real array $p:Z\times C\times E\to\mathbb R$, this predicate means that $p(z,c,e)\ge0$ for every $z,c,e$, that

$$\sum_{c\in C}\sum_{e\in E}p(z,c,e)=1 \quad\text{for every }z\in Z,$$

and that

$$\sum_{e\in E}p(z,c,e)=\sum_{e\in E}p(z',c,e) \quad\text{for every }z,z'\in Z,\ c\in C.$$

Thus the $C$-marginal is independent of $z$. The type $Z$ may be empty, in which case all requirements are vacuous; if $Z$ is nonempty and either $C$ or $E$ is empty, the normalization requirement cannot hold.

QAlgorithms.Papers.Independent.Intakethird100.P22.IsVertex

For input types $X,Y$, finite output types $A,B$, and a real function $p$ on $X\times Y\times A\times B$, being a vertex means first that $p$ is nonnegative, normalized over $A\times B$ at every input pair, and has each output marginal independent of the other party’s input; second, for every two functions $q,r$ satisfying those same conditions and every real $t$ with $0<t<1$,

$$p(x,y,a,b)=tq(x,y,a,b)+(1-t)r(x,y,a,b) \quad\text{for all }x,y,a,b$$

implies $q=p$ and $r=p$. The implication concerns only strictly interior mixing coefficients; $t=0$ and $t=1$ impose no additional condition.

QAlgorithms.Papers.Independent.Intakethird100.P22.KeyOutput

For finite types $K,T,E$ and an arbitrary type $Z$, a key output consists of a real number $r_{\mathrm{abort}}\in[0,1]$ and two real arrays $P_z(a,b,t,e)$ and $Q_z(a,b,t,e)$, called the pass and abort arrays, where $z\in Z$, $a,b\in K$, $t\in T$, and $e\in E$. Each array $R\in\{P,Q\}$ satisfies

$$R_z(a,b,t,e)\ge0,\qquad \sum_{a,b,t,e}R_z(a,b,t,e)=1,\qquad \sum_eR_z(a,b,t,e)=\sum_eR_{z'}(a,b,t,e)$$

for every $z,z'\in Z$ and $a,b,t$. There is no further relation required between the pass and abort arrays. The endpoint abort probabilities $0$ and $1$ are allowed. The types are not assumed nonempty: if $Z$ is empty, all array conditions are vacuous; if $Z$ is nonempty, normalization rules out an empty $K,T$, or $E$.

QAlgorithms.Papers.Independent.Intakethird100.P22.UnaryExtension

For finite input alphabets $X,Y$, finite output alphabets $A,B$, any real array $p(x,y,a,b)$, and any natural number $n$, a unary extension is an array $d(x,y,a,b,e)\in\mathbb R$, indexed by $e\in\{0,\ldots,n-1\}$, satisfying all of

$$\begin{aligned} &d(x,y,a,b,e)\ge0,\\ &\sum_e d(x,y,a,b,e)=p(x,y,a,b),\\ &\sum_{a,b}d(x,y,a,b,e)=\sum_{a,b}d(x',y',a,b,e),\\ &\sum_a d(x,y,a,b,e)=\sum_a d(x',y,a,b,e),\\ &\sum_b d(x,y,a,b,e)=\sum_b d(x,y',a,b,e), \end{aligned}$$

for every choice of the displayed indices. Thus the $e$-marginal is independent of both inputs, the $(b,e)$-marginal is independent of $x$, and the $(a,e)$-marginal is independent of $y$. No normalization or validity assumption on $p$ is imposed by this structure. The case $n=0$ is included: its marginal condition requires $p$ to be identically zero, while the conditions quantified over $e$ are vacuous.

QAlgorithms.Papers.Independent.Intakethird100.P22.ValidDevice

For input types $X,Y$, finite output types $A,B$, and a function $p:X\times Y\times A\times B\to\mathbb R$, validity means that all entries are nonnegative, that $\sum_a\sum_b p(x,y,a,b)=1$ for every $x,y$, and that

$$\sum_a p(x,y,a,b)=\sum_a p(z,y,a,b),\qquad \sum_b p(x,y,a,b)=\sum_b p(x,z,a,b)$$

for every appropriately typed choice of variables. Thus Bob’s marginal is independent of Alice’s input, and Alice’s marginal is independent of Bob’s input. Conditions quantified over absent inputs are vacuous; if both input types are inhabited and either output type is empty, normalization cannot hold.

QAlgorithms.Papers.Independent.Intakethird100.P22.aliceMarginal

For a finite type $K$, arbitrary types $T,E,Z$, and an arbitrary real array $p:Z\times(K\times K\times T)\times E\to\mathbb R$, this defines the array on $Z\times(K\times T)\times E$ given by

$$p_A(z,(a,t),e)=\sum_{b\in K}p(z,(a,b,t),e).$$

No positivity or normalization is assumed. The type $K$ may be empty, in which case the resulting array has no arguments $(a,t)$.

QAlgorithms.Papers.Independent.Intakethird100.P22.aliceSupport

For finite alphabets $X,A,B$, an input alphabet $Y$, any real array $p(x,y,a,b)$, and a specified $y\in Y$, the defined natural number is

$$\operatorname{aliceSupport}(p,y) =\max_{x\in X}\left|\left\{a\in A:\sum_{b\in B}p(x,y,a,b)>0\right\}\right|.$$

The comparison is strictly positive, so zero and negative marginal values are excluded. No nonnegativity, normalization, or no-signaling condition on $p$ is assumed. The finite supremum is $0$ when $X$ is empty; empty output sums are also $0$.

QAlgorithms.Papers.Independent.Intakethird100.P22.ampAtInput

For finite input and output alphabets $X,Y,A,B$, any real array $p(x,y,a,b)$, and specified inputs $x\in X,y\in Y$, the defined real number is the infimum over all positive integers $n$ and decompositions $p=\sum_{i<n}w_iv_i$, where $w_i\ge0$, $\sum_iw_i=1$, and each $v_i$ is nonnegative, normalized at each input, and has both no-signaling marginals, of

$$\inf_{\substack{m>0\\K(i,j)\ge0,\ \sum_{j<m}K(i,j)=1}} \left[H(r_{AJ})+H(r_{BJ})-H(r_J)-H(r)\right], \qquad r(a,b,j)=\sum_{i<n}w_i\,v_i(x,y,a,b)\,K(i,j).$$

Thus the inner infimum permits every finite positive output size $m$ and every stochastic map from the ensemble index $i$ to $j<m$. Marginals are obtained by summing omitted coordinates, and $H(s)=-\sum_us_u\log_2s_u$. Ensemble weights may vanish; components need not be distinct or extreme. There is no validity hypothesis on $p$, and an empty outer set of candidate values has real infimum $0$.

QAlgorithms.Papers.Independent.Intakethird100.P22.bobSupport

For finite alphabets $Y,A,B$, an input alphabet $X$, any real array $p(x,y,a,b)$, and a specified $x\in X$, the defined natural number is

$$\operatorname{bobSupport}(p,x) =\max_{y\in Y}\left|\left\{b\in B:\sum_{a\in A}p(x,y,a,b)>0\right\}\right|.$$

The comparison is strictly positive, so zero and negative marginal values are excluded. No nonnegativity, normalization, or no-signaling condition on $p$ is assumed. The finite supremum is $0$ when $Y$ is empty; empty output sums are also $0$.

QAlgorithms.Papers.Independent.Intakethird100.P22.cdDistance

For finite types $C,E,Z$ and arbitrary real arrays $p,q:Z\times C\times E\to\mathbb R$, this defines

$$d(p,q)= \sup_{m,u,v}\frac12\sum_{j=0}^{m-1} \left| \sum_{c,z,e}u(c,z)p(z,c,e)v(c,z,e,j) - \sum_{c,z,e}u(c,z)q(z,c,e)v(c,z,e,j) \right|,$$

where $m$ ranges over positive natural numbers, $u(c,z)\ge0$ with $\sum_z u(c,z)=1$ for every $c$, and $v(c,z,e,j)\ge0$ with $\sum_jv(c,z,e,j)=1$ for every $c,z,e$. Neither array is required to be nonnegative or normalized. Empty index types are allowed; in particular, if $C$ is nonempty and $Z$ is empty, there are no admissible observations, and the real supremum of the empty set used here is zero.

QAlgorithms.Papers.Independent.Intakethird100.P22.cdSecrecyError

Let $K,T,E,Z$ be finite types and let $r$ consist of $\alpha\in[0,1]$ and pass and abort arrays $P,Q$, each nonnegative and normalized over $a,b,t,e$ for every $z$, with $\sum_eR_z(a,b,t,e)$ independent of $z$. Set

$$P^A_z(a,t,e)=\sum_bP_z(a,b,t,e),\qquad I_z(a,b,t,e)= \begin{cases} |K|^{-1}\displaystyle\sum_{u,v\in K}P_z(u,v,t,e),&a=b,\\ 0,&a\ne b, \end{cases} \qquad I^A_z(a,t,e)=\sum_bI_z(a,b,t,e).$$

For arrays $R,S$ indexed by $z\in Z,c\in C,e\in E$, define

$$d(R,S)= \sup_{\substack{m\ge1,\ u,v}} \frac12\sum_{j=0}^{m-1} \left|\sum_{c,z,e}u(c,z)\bigl(R_z(c,e)-S_z(c,e)\bigr)v(c,z,e,j)\right|,$$

where $u(c,z)\ge0$, $\sum_z u(c,z)=1$ for every $c$, and $v(c,z,e,j)\ge0$, $\sum_jv(c,z,e,j)=1$ for every $c,z,e$. The secrecy error is $\operatorname{Sec}(r)=(1-\alpha)d(P^A,I^A)$, using $C=K\times T$. No nonemptiness assumptions are imposed; division by zero in the displayed ideal array is interpreted as zero, and if the observation family defining the real supremum is empty, that supremum is zero.

QAlgorithms.Papers.Independent.Intakethird100.P22.chshLoss

For any function $p:\{0,1\}^{4}\to\mathbb R$, with $0$ and $1$ denoting false and true, respectively, this defines

$$\operatorname{chshLoss}(p)=\frac14\sum_{x,y,a,b\in\{0,1\}} \begin{cases} 0,&a\oplus b=xy,\\ p(x,y,a,b),&a\oplus b\ne xy, \end{cases}$$

where $\oplus$ is Boolean exclusive OR and $xy$ is Boolean AND. No nonnegativity, normalization, or no-signaling assumption is imposed on $p$; the definition applies to every real-valued function of these four Boolean arguments.

QAlgorithms.Papers.Independent.Intakethird100.P22.correctnessError

Let $K,T,E$ be finite types, let $Z$ be any type, and let $r$ consist of an abort probability $\alpha\in[0,1]$ and pass and abort arrays $P,Q$. Both arrays are nonnegative, sum to $1$ over $a,b\in K,t\in T,e\in E$ for each $z\in Z$, and have $\sum_eR_z(a,b,t,e)$ independent of $z$. For any supplied $z\in Z$, the correctness error is the real number

$$\operatorname{Cor}(r,z) =(1-\alpha)\sum_{\substack{a,b\in K\\a\ne b}}\sum_{t\in T}\sum_{e\in E}P_z(a,b,t,e).$$

Thus it uses only the pass array and the abort probability. In particular, it is zero when $\alpha=1$. Although no nonemptiness assumptions are explicitly imposed on $K,T,E$, the existence of $r$ and the supplied $z$ forces these types to be nonempty.

QAlgorithms.Papers.Independent.Intakethird100.P22.deterministicBox

For any four Boolean parameters $\alpha,\beta,\gamma,\sigma$, the defined real array on Boolean inputs $x,y$ and Boolean outputs $a,b$ is

$$p(x,y,a,b)= \begin{cases} 1,&a=(\alpha\land x)\oplus\beta \ \text{and}\ b=(\gamma\land y)\oplus\sigma,\\ 0,&\text{otherwise}, \end{cases}$$

where $\land$ is Boolean conjunction and $\oplus$ is exclusive-or. All choices of the parameters and arguments, including false values, are included.

QAlgorithms.Papers.Independent.Intakethird100.P22.deviceCMI

For arbitrary finite types $A,B,E$ and any real function $p:A\times B\times E\to\mathbb R$, define $H(q)=-\sum_iq_i\log_2q_i$ for a real function on a finite index type. The declared quantity is

$$\begin{aligned} \operatorname{CMI}(p) ={}&H\!\left((a,e)\mapsto\sum_b p(a,b,e)\right) +H\!\left((b,e)\mapsto\sum_a p(a,b,e)\right)\\ &-H\!\left(e\mapsto\sum_{a,b}p(a,b,e)\right)-H(p). \end{aligned}$$

No nonnegativity or normalization assumption is imposed on $p$, and the types may be empty. The logarithm is the total real base-two logarithm used in the definition, including its value at zero, so the expression is defined even for such inputs.

QAlgorithms.Papers.Independent.Intakethird100.P22.ensembleForm

For finite nonempty input alphabets $X,Y$, finite output alphabets $A,B$, and any real array $p(x,y,a,b)$, the defined real number is

$$\max_{x\in X,\ y\in Y}\ \inf_{\substack{n>0,\ w_i\ge0,\ \sum_iw_i=1\\ v_i\text{ valid},\ \sum_iw_iv_i=p}} \sum_{i=0}^{n-1}w_i \left[H((v_i^{xy})_A)+H((v_i^{xy})_B)-H(v_i^{xy})\right], \qquad v_i^{xy}(a,b)=v_i(x,y,a,b).$$

A valid box $v_i$ has nonnegative entries, satisfies $\sum_{a,b}v_i(x,y,a,b)=1$ at every input, has $\sum_a v_i(x,y,a,b)$ independent of $x$, and has $\sum_b v_i(x,y,a,b)$ independent of $y$. The reconstruction equality is pointwise at every input and output. Here $H(r)=-\sum_jr_j\log_2r_j$; weights may vanish, and the component boxes need not be vertices or distinct. No validity hypothesis is imposed on $p$; if no such finite decomposition exists, the real infimum in the definition is $0$.

QAlgorithms.Papers.Independent.Intakethird100.P22.extensionForm

For finite nonempty input alphabets $X,Y$, finite output alphabets $A,B$, and any real array $p(x,y,a,b)$, the defined real number is

$$\max_{x\in X,\ y\in Y}\ \inf_{\substack{n\in\mathbb N,\ n>0\\d\text{ as below}}} \left[H((d^{xy})_{AE})+H((d^{xy})_{BE})-H((d^{xy})_E)-H(d^{xy})\right], \qquad d^{xy}(a,b,e)=d(x,y,a,b,e).$$

Here $e<n$; $d$ is nonnegative; $\sum_e d(x,y,a,b,e)=p(x,y,a,b)$; its $(b,e)$-marginal is independent of $x$, its $(a,e)$-marginal is independent of $y$, and its $e$-marginal is independent of both inputs. Subscripts denote summation over omitted coordinates, and $H(r)=-\sum_i r_i\log_2r_i$. No normalization or no-signaling hypothesis on $p$ is required. Only positive extension sizes are considered; if there is no such extension, the real infimum used here is $0$. The real logarithm and infimum are total operations, so the definition also applies when its arrays are not probability distributions.

QAlgorithms.Papers.Independent.Intakethird100.P22.finiteMax

For any finite, nonempty type $I$ and function $f:I\to\mathbb R$, this defines

$$\operatorname{finiteMax}(f)=\sup\{f(i):i\in I\},$$

the largest value attained by $f$.

QAlgorithms.Papers.Independent.Intakethird100.P22.hrwBox

For arbitrary real parameters $\delta,\eta$, this definition assigns to Boolean inputs $x,y$ and Boolean outputs $a,b$ the real value

$$p_{\delta,\eta}(x,y,a,b)= \begin{cases} (1-\delta)/2,&x=y=\mathrm{false}\ \text{and }a=b,\\ \delta/2,&x=y=\mathrm{false}\ \text{and }a\ne b,\\ 3/8-\eta/2,&(x,y)\ne(\mathrm{false},\mathrm{false}) \ \text{and }a\mathbin{\oplus}b=x\mathbin{\land}y,\\ 1/8+\eta/2,&(x,y)\ne(\mathrm{false},\mathrm{false}) \ \text{and }a\mathbin{\oplus}b\ne x\mathbin{\land}y. \end{cases}$$

Here $\oplus$ is exclusive-or and $\land$ is Boolean conjunction. No restrictions on $\delta,\eta$, or assertion of nonnegativity, normalization, or no signaling, accompany the definition.

QAlgorithms.Papers.Independent.Intakethird100.P22.idealCDKey

For a finite type $K$, arbitrary types $T,E,Z$, and an arbitrary real array $p:Z\times(K\times K\times T)\times E\to\mathbb R$, this defines an array on the same types by

$$p_{\mathrm{ideal}}(z,(a,b,t),e)= \begin{cases} \displaystyle\frac{\sum_{a'\in K}\sum_{b'\in K}p(z,(a',b',t),e)}{|K|}, & a=b,\\[6pt] 0,&a\ne b. \end{cases}$$

No positivity or normalization of $p$ is assumed. The type $K$ may be empty, in which case the resulting array has no arguments $(a,b,t)$; real division by zero is defined as zero.

QAlgorithms.Papers.Independent.Intakethird100.P22.intermediateKey

For a finite type $K$, arbitrary types $T,E,Z$, and an arbitrary real array $p:Z\times(K\times K\times T)\times E\to\mathbb R$, this defines

$$p_{\mathrm{int}}(z,(a,b,t),e)= \begin{cases} \displaystyle\sum_{b'\in K}p(z,(a,b',t),e),&a=b,\\[4pt] 0,&a\ne b. \end{cases}$$

No positivity or normalization is required, and $K$ may be empty, in which case the resulting array has no arguments $(a,b,t)$.

QAlgorithms.Papers.Independent.Intakethird100.P22.intrinsicInformation

For finite types $A,B,E$ and any function $p:A\times B\times E\to\mathbb R$, define its intrinsic information as follows. For every positive integer $k$, consider every kernel $K:E\times\{0,\ldots,k-1\}\to\mathbb R$ satisfying $K(e,j)\ge0$ and $\sum_jK(e,j)=1$ for each $e$, and put $q_K(a,b,j)=\sum_e p(a,b,e)K(e,j)$. The intrinsic information is

$$\inf_{k>0,\ K}\bigl[H((q_K)_{AJ})+H((q_K)_{BJ})-H((q_K)_J)-H(q_K)\bigr],$$

where the subscripts denote marginals obtained by summation and $H(q)=-\sum_u q(u)\log_2 q(u)$. Here the real logarithm is totalized: its value at zero is zero, and at a negative argument it is the logarithm of the absolute value. No nonnegativity or normalization assumption is imposed on $p$, and the finite types may be empty. The infimum is taken in $\mathbb R$, whose totalized infimum is zero for an empty set or a set unbounded below.

QAlgorithms.Papers.Independent.Intakethird100.P22.nonlocalityCost

For a real-valued box $p$ on finite input and output sets and specified inputs $x\in X,y\in Y$, this definition is

$$F(p)\log_2\!\left( \min\left\{ \max_{x'\in X}\#\left\{a\in A:\sum_bp(x',y,a,b)>0\right\}, \max_{y'\in Y}\#\left\{b\in B:\sum_ap(x,y',a,b)>0\right\} \right\}\right).$$

Here $F(p)$ is the real infimum of $t\in[0,1]$ such that $p=tv+(1-t)l$, with $v$ a nonlocal extreme valid box and $l$ a local box. Valid means nonnegative normalized output laws and no signaling in either direction; extreme means that a convex decomposition with coefficient in $(0,1)$ into valid boxes forces both components to equal the box. Local means that the box has nonnegative normalized output laws and admits a representation $\sum_\lambda\mu(\lambda)\alpha_\lambda(a\mid x)\beta_\lambda(b\mid y)$, with a probability mass function $\mu$ on an arbitrary latent type and normalized nonnegative response laws for every latent value and input. Both witness boxes remain required at $t=0,1$, and $F(p)=0$ if its defining set is empty. The support counts use strictly positive marginal sums, with no validity assumption on $p$. The logarithm is the total real base-$2$ logarithm, so a zero minimum gives logarithm $0$.

QAlgorithms.Papers.Independent.Intakethird100.P22.nonlocalityFraction

For a real-valued box $p(x,y,a,b)$, this definition is the real infimum of all $t\in[0,1]$ for which there exist boxes $v,l$ satisfying $p=tv+(1-t)l$, where $v$ is a valid extreme box without a local model and $l$ has a local model. A valid box has nonnegative normalized output laws, with each party’s marginal independent of the other party’s input; extremality means that whenever $v=sq+(1-s)r$ for valid boxes $q,r$ and $0<s<1$, both $q$ and $r$ equal $v$. A box $q$ has a local model precisely when it has nonnegative normalized output laws and there exist a type $\Lambda$, a probability mass function $\mu$ on $\Lambda$, and nonnegative normalized response laws $\alpha_\lambda(a\mid x)$, $\beta_\lambda(b\mid y)$, for every $\lambda,x,y$, such that

$$q(x,y,a,b)=\sum_{\lambda\in\Lambda} \mu(\lambda)\alpha_\lambda(a\mid x)\beta_\lambda(b\mid y).$$

The series is the total infinite sum used in the definition. The endpoints $t=0,1$ are allowed, but both witness boxes and the nonlocal extreme-box condition are still required there. No validity or representability assumption on $p$ is imposed; if there are no admissible $t$, the real infimum is $0$.

QAlgorithms.Papers.Independent.Intakethird100.P22.prVariant

For any Boolean parameters $r,s,t$, the defined real array on Boolean inputs $x,y$ and Boolean outputs $a,b$ is

$$p(x,y,a,b)= \begin{cases} \frac12,&a\oplus b=(x\land y)\oplus(r\land x)\oplus(s\land y)\oplus t,\\ 0,&\text{otherwise}, \end{cases}$$

where $\land$ is Boolean conjunction and $\oplus$ is exclusive-or. The definition includes every Boolean choice of parameters, inputs and outputs.

QAlgorithms.Papers.Independent.Intakethird100.P22.securityError

Let $K,T,E,Z$ be finite types and let $r$ consist of an abort probability $\alpha\in[0,1]$ and pass and abort arrays $P,Q$, each nonnegative and normalized over $a,b\in K,t\in T,e\in E$ for every $z$, with its marginal $\sum_eR_z(a,b,t,e)$ independent of $z$. Define the ideal pass array by

$$I_z(a,b,t,e)= \begin{cases} |K|^{-1}\displaystyle\sum_{u,v\in K}P_z(u,v,t,e),&a=b,\\ 0,&a\ne b. \end{cases}$$

For arrays $R,S$ on $Z\times C\times E$, let

$$d(R,S)= \sup_{\substack{m\ge1,\ u,v}} \frac12\sum_{j=0}^{m-1} \left|\sum_{c,z,e}u(c,z)\bigl(R_z(c,e)-S_z(c,e)\bigr)v(c,z,e,j)\right|,$$

where $u(c,\cdot)$ is a nonnegative real function summing to $1$ on $Z$ for each $c$, and $v(c,z,e,\cdot)$ is a nonnegative real function summing to $1$ on $\{0,\ldots,m-1\}$ for each $c,z,e$. The security error is $\operatorname{Err}(r)=(1-\alpha)d(P,I)$, with $C=K\times K\times T$. Empty types are allowed; division by zero is zero, and an empty observation family has real supremum zero.

QAlgorithms.Papers.Independent.Intakethird100.P22.singleDeviceEnsemble

Given input sets $X,Y$, finite output sets $A,B$, and a box $p:X\times Y\times A\times B\to\mathbb R$ that is valid, this definition constructs an ensemble indexed by the singleton set $\{0\}$: its sole weight is $1$, and its sole member is $p$. Validity means that $p(x,y,a,b)\ge0$, that $\sum_a\sum_bp(x,y,a,b)=1$ for every $x,y$, that $\sum_ap(x,y,a,b)$ is independent of $x$, and that $\sum_bp(x,y,a,b)$ is independent of $y$. Thus the weight is a probability law, the member is valid, and the weighted reconstruction is $p$ at every input and output tuple; the definition supplies no minimality or extremality condition.

QAlgorithms.Papers.Independent.Intakethird100.P22.squashSecrecy

For finite nonempty input types $X,Y$, finite output types $A,B$, a box $p$, and a complete extension $c$ with positive counts $u,v$, write its decompositions as $p=\sum_{i<v}w_{zi}p_{zi}$: the arrays are normalized, nonnegative and nonsignaling, the weights are probability laws, the positive-weight members are extreme valid arrays, their supports admit no strictly smaller decomposition support, and every finite minimal decomposition is matched in aggregate weights by exactly one input $z<u$. For any real-valued functional $m$ on real arrays indexed by $A\times B\times(\{0,\ldots,u-1\}\times\{0,\ldots,v-1\})$, the defined value is

$$\sup_{(x,y)\in X\times Y} \inf\left\{ m\bigl((a,b,z,i)\mapsto d(z)w_{zi}p_{zi}(x,y,a,b)\bigr): d(z)\ge0\ \text{for all }z,\ \sum_{z<u}d(z)=1 \right\}.$$

No continuity, boundedness or other condition is imposed on $m$, and no attainment of either optimization is asserted. Both operations use real infima and suprema; in particular, an inner set unbounded below has the totalized real infimum $0$, rather than an extended-real value of $-\infty$.

QAlgorithms.Papers.Independent.Intakethird100.P22.squashedCMI

For finite nonempty input alphabets $X,Y$ and output alphabets $A,B$, let $p:X\times Y\times A\times B\to\mathbb R$, and let $c$ be a complete extension of $p$. Such an extension consists of positive integers $m,\ell$, probability weights $w_{ze}$ for each $z<m$, and boxes $v_e$ with nonnegative entries, unit total mass at each input, and both no-signaling marginal conditions, such that $\sum_e w_{ze}v_e=p$. For each $z$, the boxes with positive weight are vertices—boxes admitting no nontrivial convex decomposition into distinct valid boxes—and their support has no proper subset that supports another finite valid decomposition of $p$. Every decomposition with these properties has exactly one index $z$ giving the same total weight to every box. For a probability vector $d=(d_z)_{z<m}$, put $r_d^{xy}(a,b,e)=\sum_z d_z w_{ze}v_e(x,y,a,b)$. Then the defined real number is

$$\operatorname{squashedCMI}(c) =\max_{x\in X,\ y\in Y}\ \inf_{\substack{d_z\ge0\\\sum_zd_z=1}} \left[H((r_d^{xy})_{AE})+H((r_d^{xy})_{BE})-H((r_d^{xy})_E)-H(r_d^{xy})\right],$$

where subscripts mean summing out the omitted coordinates and $H(r)=-\sum_i r_i\log_2 r_i$, with zero terms contributing zero. Zero weights are allowed in both $w$ and $d$.

QAlgorithms.Papers.Independent.Intakethird100.P22.squashedLowerHull

For a real-valued box $p(x,y,a,b)$ on finite nonempty sets $X,Y,A,B$, this definition gives the real infimum

$$\inf_{\substack{n\ge1,\ p=\sum_{i<n}w_ip_i\\ c_i\text{ a complete extension of }p_i}} \sum_{i<n}w_i\min\{S_{\mathrm{MI}}(c_i),S_{\mathrm{CMI}}(c_i)\}.$$

The decomposition uses nonnegative weights summing to $1$ and valid member boxes: each member has normalized nonnegative output laws and marginals independent of the other party’s input. A complete extension $c_i$ consists of positive finite input and label counts, and a minimal ensemble of $p_i$ at each extension input, with fixed member labels across those inputs. Its indexed ensembles enumerate all minimal ensembles uniquely by their total mass at every box. Here minimal means that the positive-weight members are extreme valid boxes and that no ensemble of $p_i$ has support properly contained in that positive-weight support; an extreme box admits no convex decomposition with coefficient in $(0,1)$ except into itself. If a complete extension $c$ has ensembles $(w_{ze},q_{ze})$, define

$$r^{x,y,d}(a,b,e)=\sum_zd_zw_{ze}q_{ze}(x,y,a,b),$$

where $d_z\ge0$ and $\sum_zd_z=1$. Then $S_{\mathrm{MI}}(c)=\max_{x,y}\inf_d I_{r^{x,y,d}_{AB}}(A:B)$ and $S_{\mathrm{CMI}}(c)=\max_{x,y}\inf_d I_{r^{x,y,d}}(A:B\mid E)$, using $H(q)=-\sum_uq(u)\log_2q(u)$, $I(A:B)=H(A)+H(B)-H(AB)$, and $I(A:B\mid E)=H(AE)+H(BE)-H(E)-H(ABE)$. Complete extensions are required even for zero-weight members of the outer ensemble. No validity assumption on $p$, or existence of an admissible decomposition, is part of this definition; an empty defining set has real infimum $0$.

QAlgorithms.Papers.Independent.Intakethird100.P22.squashedMI

For finite types $X,Y,A,B$, with $X\times Y$ nonempty, a function $p$, and a complete extension $c$ of $p$, squashed mutual information is

$$\max_{(x,y)\in X\times Y} \inf_{\substack{d_z\ge0\\\sum_{z<u}d_z=1}} \bigl[H(s_A)+H(s_B)-H(s)\bigr], \qquad s(a,b)=\sum_{e<v}\sum_{z<u}d_z w_{z,e}p_{z,e}(x,y,a,b),$$

where $s_A(a)=\sum_bs(a,b)$, $s_B(b)=\sum_as(a,b)$, and $H(s)=-\sum_i s_i\log_2s_i$, with the total real logarithm taking value zero at zero. The complete extension supplies positive integers $u,v$, probability weight rows reconstructing $p$, and valid member functions that are independent of the row at each fixed position $e$; validity means nonnegativity, normalization at every input pair, and both no-signaling marginal identities. Every row’s positive-weight members are vertices and no ensemble of $p$ has properly smaller positive-weight support, while every ensemble satisfying these two requirements matches all aggregated member masses of exactly one row. An ensemble is any finite probability-weighted decomposition into valid functions, and a vertex has only constant decompositions into valid functions with mixing coefficient strictly between zero and one. The infimum is a real infimum, totalized to zero for an empty or unbounded-below value set, and no minimizing choice of $d$ is asserted.

QAlgorithms.Papers.Independent.Intakethird100.P22.squashedNonlocality

For finite types $X,Y,A,B$, with $X\times Y$ nonempty, a function $p$, and a complete extension $c$ of $p$, squashed nonlocality is

$$\max_{(x,y)\in X\times Y} \inf_{\substack{d_z\ge0\\\sum_zd_z=1}} \left[ \inf_{\substack{k>0,\ K(e,j)\ge0\\\sum_{j<k}K(e,j)=1}} \bigl(H(r_{AJ})+H(r_{BJ})-H(r_J)-H(r)\bigr) \right],$$

where $q(a,b,e)=\sum_{z<u}d_z w_{z,e}p_{z,e}(x,y,a,b)$, $r(a,b,j)=\sum_{e<v}q(a,b,e)K(e,j)$, and subscripts denote marginals. Here $H(s)=-\sum_i s_i\log_2s_i$, with the total real logarithm taking value zero at zero. The complete extension has $u,v>0$, valid nonnegative normalized members satisfying both no-signaling marginal identities, probability weight rows reconstructing $p$, and row-independent member labels at each position $e$. Each row has only vertices in its positive-weight support and admits no ensemble of $p$ with properly smaller support; every ensemble with these properties matches the aggregated member masses of exactly one row. An ensemble is a finite probability-weighted decomposition into valid functions, and a vertex has only constant strictly interior convex decompositions into valid functions. Both displayed infima are real infima, using zero if the relevant value set is empty or unbounded below; their attainment is not part of the definition.

QAlgorithms.Papers.Independent.Intakethird100.P22.withAbort

For arbitrary types $C,E,Z$, any real number $r$, and any two real arrays $p_{\mathrm{abort}},p_{\mathrm{pass}}:Z\times C\times E\to\mathbb R$, this defines

$$p_{\mathrm{combined}}(z,c,e) =r\,p_{\mathrm{abort}}(z,c,e)+(1-r)\,p_{\mathrm{pass}}(z,c,e).$$

There is no restriction $0\le r\le1$, and neither array is required to be nonnegative, normalized, or to satisfy a marginal condition.