Definitions for Numerical evidence for bound secrecy from two-way post-processing in quantum key distribution

QAlgorithms.Papers.Independent.Intakethird100.P30.BobExtendible

For finite index types $A,B$ and any complex matrix $P$ indexed by $A\times B$, this predicate means that there exists a positive semidefinite complex matrix $R$ indexed by $(A\times B)\times B$ such that, for every $a,a'\in A$ and $b,b'\in B$,

$$\sum_{c\in B}R_{((a,b),c),((a',b'),c)} =P_{(a,b),(a',b')}, \qquad \sum_{c\in B}R_{((a,c),b),((a',c),b')} =P_{(a,b),(a',b')}.$$

Neither trace-one normalization nor exchange symmetry of $R$ is required. If either index type is empty, such an $R$ exists.

QAlgorithms.Papers.Independent.Intakethird100.P30.CodeEquivalent

For types $I,J,K,L$ and functions $C:K\to(I\to\{\mathrm{false},\mathrm{true}\})$ and $D:L\to(J\to\{\mathrm{false},\mathrm{true}\})$, this proposition means that there exist bijections $p:I\to J$ and $e:K\to L$, and a function $t:I\to\{\mathrm{false},\mathrm{true}\}$, such that $C(k)(i)=D(e(k))(p(i))\oplus t(i)$ for every $k\in K$ and $i\in I$, where exclusive-or is true exactly when its two inputs differ. The bijections are required even when the coordinatewise equality is vacuous because $K$ or $I$ is empty; neither $C$ nor $D$ is required to be injective.

QAlgorithms.Papers.Independent.Intakethird100.P30.CodeLinear

For types $K$ and $I$ and a collection of Boolean words $C:K\to\{0,1\}^{I}$, this defines the property that for every pair of labels $k,l\in K$ there exists a label $r\in K$ such that, at every coordinate $i\in I$,

$$C(r)_i=C(k)_i\mathbin{\oplus}C(l)_i,$$

where $\oplus$ is Boolean exclusive-or. Thus the image is closed under coordinatewise exclusive-or; no injectivity or nonemptiness is required, and the property holds vacuously when $K$ is empty.

QAlgorithms.Papers.Independent.Intakethird100.P30.ComplementClosed

For every natural number $n$ and finite set $C$ of Boolean words of length $n$, this defines the property that whenever $w\in C$, the word whose bit at every coordinate $i$ is $\neg w_i$ also belongs to $C$. No nonemptiness assumption is imposed: the empty set satisfies the property. For $n=0$, complementation fixes the unique empty word, so every such $C$ satisfies it.

QAlgorithms.Papers.Independent.Intakethird100.P30.Equidistant

For a type $K$, a finite coordinate type $I$, a map $C:K\to\{0,1\}^I$, and a natural number $d$, the assertion that $C$ is equidistant with parameter $d$ means that every pair of distinct indices $k,l\in K$ satisfies

$$|\{i\in I:C(k)_i\ne C(l)_i\}|=d.$$

There is no separate injectivity requirement: when $d=0$, distinct indices must have identical strings. If $K$ has at most one element, the condition is vacuous.

QAlgorithms.Papers.Independent.Intakethird100.P30.FixedCoordinates

For types $I,K$ and a function $C:K\to(I\to\{\mathrm{false},\mathrm{true}\})$, this denotes the subtype of coordinates $i\in I$ satisfying $C(k)(i)=C(l)(i)$ for every $k,l\in K$. If $K$ is empty or has one element, every coordinate satisfies this condition.

QAlgorithms.Papers.Independent.Intakethird100.P30.IsBobCopyExtension

For finite index types $A,B$, a complex matrix $P$ indexed by $A\times B$, and a complex matrix $R$ indexed by $(A\times B)\times B$, this predicate means that $R$ is positive semidefinite and that, for every $a,a'\in A$ and $b,b'\in B$, both equalities

$$\sum_{c\in B}R_{((a,b),c),((a',b'),c)} =P_{(a,b),(a',b')}, \qquad \sum_{c\in B}R_{((a,c),b),((a',c),b')} =P_{(a,b),(a',b')}$$

hold. No trace-one condition or invariance under exchanging the two $B$ coordinates is included. If $A$ or $B$ is empty, the entry equalities are vacuous and the unique matrix $R$ is positive semidefinite.

QAlgorithms.Papers.Independent.Intakethird100.P30.MatrixEntryCompatible

For a code $C:K\to\{0,1\}^{I}$, Boolean strings $a,a_2:I\to\{0,1\}$, and labels $k,l\in K$, this defines compatibility to mean the conjunction

$$a\oplus C(k)=a_2\oplus C(l) \quad\text{and}\quad \forall i\in I,\ \neg\bigl((a_i\oplus C(k)_i)=1\ \land\ (a_i\oplus a_{2,i})=1\bigr).$$

In particular, the common XOR string must have no coordinate equal to $1$ at a coordinate where $a$ and $a_2$ differ. There is no requirement that the strings or labels be distinct, or that $C$ be injective. If $I$ is empty, compatibility holds for every pair of labels.

QAlgorithms.Papers.Independent.Intakethird100.P30.NoConstantColumns

For types $I,K$ and a function $C:K\to(I\to\{\mathrm{false},\mathrm{true}\})$, this proposition means that for every coordinate $i\in I$, there exist $k,l\in K$ with $C(k)(i)\ne C(l)(i)$. It holds vacuously when $I$ is empty; when $I$ is nonempty and $K$ has at most one element, it cannot hold.

QAlgorithms.Papers.Independent.Intakethird100.P30.SDPFeasible

For finite index types $A,B$, a complex matrix $P$ indexed by $A\times B$, a real number $t$, and a complex matrix $R$ indexed by $(A\times B)\times B$, this defines the conjunction that $R$ is Hermitian, $R+tI$ is positive semidefinite, where $I$ is the identity matrix on $(A\times B)\times B$, and for every $a,a'\in A$ and $b,b'\in B$,

$$\sum_{c\in B}R_{((a,b),c),((a',b'),c)} =P_{(a,b),(a',b')} \quad\text{and}\quad \sum_{c\in B}R_{((a,c),b),((a',c),b')} =P_{(a,b),(a',b')}.$$

There is no separate requirement that $t\ge0$, that $R$ itself be positive semidefinite, or that either matrix have trace $1$. If $A$ or $B$ is empty, the matrix index types are empty and these conditions hold for every real $t$.

QAlgorithms.Papers.Independent.Intakethird100.P30.SetNoConstantColumns

For every natural number $n$ and finite set $C\subseteq\{0,1\}^n$, this defines the proposition that for every coordinate $i\in\{0,\ldots,n-1\}$, there exist words $u,v\in C$ with $u_i\ne v_i$. The witnesses may depend on $i$. For $n=0$ the condition is vacuously true, including when $C$ is empty; for $n>0$, an empty set or a singleton cannot satisfy it.

QAlgorithms.Papers.Independent.Intakethird100.P30.VaryingCoordinates

For types $I,K$ and a function $C:K\to(I\to\{\mathrm{false},\mathrm{true}\})$, this denotes the subtype of coordinates $i\in I$ for which there exist $k,l\in K$ satisfying $C(k)(i)\ne C(l)(i)$. This subtype is empty if $I$ is empty or $K$ has at most one element.

QAlgorithms.Papers.Independent.Intakethird100.P30.acceptanceMass

For a finite coordinate type $I$, a finite label type $K$, a code $C:K\to\{0,1\}^{I}$, and any real $Q$, this defines the real number

$$A_C(Q)=\sum_{a\in\{0,1\}^{I}}\sum_{k\in K} \prod_{i\in I} \begin{cases} (1-Q)/2,&a_i=C(k)_i,\\ Q/2,&a_i\ne C(k)_i. \end{cases}$$

Thus it sums the real diagonal entries of the tensor product of the two-bit matrices $(1-2Q)|\Phi\rangle\langle\Phi|+(Q/2)I_4$, evaluated at $(a,C(k))$, where $|\Phi\rangle=(|00\rangle+|11\rangle)/\sqrt2$. There is no injectivity assumption on $C$ or restriction on $Q$. If $K$ is empty, the result is zero; if $I$ is empty, each product is $1$, so the result is $|K|$.

QAlgorithms.Papers.Independent.Intakethird100.P30.bobState

For a finite coordinate type $I$, a label type $K$, any map $C:K\to(I\to\{\mathrm{false},\mathrm{true}\})$, and any real $Q$, with decidable equality on the Boolean functions used as matrix indices, this defines a complex matrix $P_C(Q)$ indexed by $(I\to\{\mathrm{false},\mathrm{true}\})\times K$. Its entries are

$$P_C(Q)_{(a,k),(a',l)} =\prod_{i\in I} \left( \frac{1-2Q}{2}\,\mathbf1_{a(i)=C(k)(i)}\mathbf1_{a'(i)=C(l)(i)} +\frac Q2\,\mathbf1_{a(i)=a'(i)}\mathbf1_{C(k)(i)=C(l)(i)} \right).$$

Here $\mathbf1_E$ denotes the indicator of $E$. This is the matrix obtained by multiplying the coordinatewise product matrix of the displayed two-bit factors on the left by $I\otimes F_C$ and on the right by its conjugate transpose, where $(F_C)_{k,w}=\mathbf1_{w=C(k)}$. No injectivity, normalization, or restriction on $Q$ is required; if $I$ is empty, every existing entry is $1$, and if $K$ is empty the matrix has no entries.

QAlgorithms.Papers.Independent.Intakethird100.P30.bobThreshold

For finite coordinate and label types $I,K$, any map $C:K\to(I\to\{\mathrm{false},\mathrm{true}\})$, and the decidable equalities used for these matrix indices, put $X=I\to\{\mathrm{false},\mathrm{true}\}$ and define a matrix $P_C(q)$ on $X\times K$, for each real $q$, by

$$P_C(q)_{(a,k),(a',l)} =\prod_{i\in I} \left( \frac{1-2q}{2}\,\mathbf1_{a(i)=C(k)(i)}\mathbf1_{a'(i)=C(l)(i)} +\frac q2\,\mathbf1_{a(i)=a'(i)}\mathbf1_{C(k)(i)=C(l)(i)} \right).$$

The defined number is the supremum of $\{0\}$ together with all $q\in[0,\tfrac12]$ for which there is no positive semidefinite complex matrix $R$ on $(X\times K)\times K$ satisfying, for every $a,a'\in X$ and $k,l\in K$, both $\sum_{r\in K}R_{((a,k),r),((a',l),r)}=P_C(q)_{(a,k),(a',l)}$ and $\sum_{r\in K}R_{((a,r),k),((a',r),l)}=P_C(q)_{(a,k),(a',l)}$. Here $\mathbf1_E$ is the indicator of $E$; no injectivity assumption on $C$ or trace-one requirement on these matrices is imposed. Empty coordinate types are allowed, with empty products equal to $1$, and an empty $K$ gives value $0$. If no $q$ satisfies the stated nonexistence condition, the value is $0$.

QAlgorithms.Papers.Independent.Intakethird100.P30.bothState

For a finite coordinate type $I$, a label type $K$, any map $C:K\to(I\to\{\mathrm{false},\mathrm{true}\})$, and any real $Q$, with decidable equality on the Boolean functions used as matrix indices, this defines a complex matrix $P_C(Q)$ indexed by $K\times K$, whose entries are

$$P_C(Q)_{(k,l),(r,s)} =\prod_{i\in I} \left( \frac{1-2Q}{2}\,\mathbf1_{C(k)(i)=C(l)(i)}\mathbf1_{C(r)(i)=C(s)(i)} +\frac Q2\,\mathbf1_{C(k)(i)=C(r)(i)}\mathbf1_{C(l)(i)=C(s)(i)} \right).$$

Here $\mathbf1_E$ denotes the indicator of $E$. Equivalently, the definition multiplies the coordinatewise product matrix of these two-bit factors on the left by $F_C\otimes F_C$ and on the right by its conjugate transpose, where $(F_C)_{k,w}=\mathbf1_{w=C(k)}$. There is no injectivity or normalization requirement and no restriction on $Q$. If $I$ is empty, every existing entry is $1$; if $K$ is empty, the matrix has no entries.

QAlgorithms.Papers.Independent.Intakethird100.P30.bothThreshold

For finite coordinate and label types $I,K$, any map $C:K\to(I\to\{\mathrm{false},\mathrm{true}\})$, and the decidable equalities used for these matrix indices, define, for each real $q$, a complex matrix $P_C(q)$ on $K\times K$ by

$$P_C(q)_{(k,l),(r,s)} =\prod_{i\in I} \left( \frac{1-2q}{2}\,\mathbf1_{C(k)(i)=C(l)(i)}\mathbf1_{C(r)(i)=C(s)(i)} +\frac q2\,\mathbf1_{C(k)(i)=C(r)(i)}\mathbf1_{C(l)(i)=C(s)(i)} \right).$$

The defined number is the supremum of $\{0\}$ together with all $q\in[0,\tfrac12]$ for which there is no positive semidefinite complex matrix $R$ on $(K\times K)\times K$ satisfying, for every $k,l,r,s\in K$, both $\sum_{t\in K}R_{((k,l),t),((r,s),t)}=P_C(q)_{(k,l),(r,s)}$ and $\sum_{t\in K}R_{((k,t),l),((r,t),s)}=P_C(q)_{(k,l),(r,s)}$. Here $\mathbf1_E$ is the indicator of $E$; no injectivity assumption on $C$ or trace-one requirement on these matrices is imposed. Empty coordinate types are allowed, with empty products equal to $1$, and an empty $K$ gives value $0$. If no $q$ satisfies the stated nonexistence condition, the value is $0$.

QAlgorithms.Papers.Independent.Intakethird100.P30.candidateDegrader

For an index type $A$, a finite index type $B$, and any function $N$ sending complex matrices indexed by $A$ to complex matrices indexed by $B$, this defines a function sending a matrix $X$ indexed by $A\times B$ to

$$X\longmapsto N(Y),\qquad Y_{a,a'}=\sum_{b\in B}X_{(a,b),(a',b)}.$$

Thus its input to $N$ is the partial trace over $B$. No linearity, positivity, trace-preservation, or channel assumption is imposed on $N$. The sum is zero when $B$ is empty.

QAlgorithms.Papers.Independent.Intakethird100.P30.candidateExtension

For finite index types $A,B$ with decidable equality, any complex matrix $P$ indexed by $A\times B$, and any function $N$ from complex matrices indexed by $A$ to complex matrices indexed by $B$, let $S=f(P)$, with $f(t)=\sqrt t$ applied by the real continuous functional calculus. This defines a matrix $E$ indexed by $(A\times B)\times B$ as follows: for $x,y\in A\times B$, form the matrix $Y^{x,y}$ indexed by $A$ with entries

$$Y^{x,y}_{a,a'}=\sum_{c\in B}S_{x,(a,c)}\,\overline{S_{y,(a',c)}},$$

and set

$$E_{(x,b),(y,b')}=\bigl[N(Y^{x,y})\bigr]_{b,b'}.$$

This is the stated blockwise application of $N$ after a partial trace to the matrix $v_Pv_P^{*}$, where $v_P(u,v)=S_{u,v}$. No positivity or normalization hypothesis is imposed on $P$, and no channel or linearity hypothesis is imposed on $N$. For Hermitian $P$, the real square root sends negative eigenvalues to zero; for non-Hermitian $P$, $S=0$. Empty index types are allowed.

QAlgorithms.Papers.Independent.Intakethird100.P30.chau

This defines the real constant $\displaystyle \frac{5-\sqrt{5}}{10}$, where $\sqrt{5}$ is the nonnegative real square root.

QAlgorithms.Papers.Independent.Intakethird100.P30.codeClassCount

For any natural numbers $n,m$, consider all subsets $C\subseteq\{0,1\}^n$ with exactly $m$ elements such that, at each coordinate $i$, some two words in $C$ differ at $i$. For each such $C$, form

$$\mathcal O(C)= \left\{ \left\{\,\bigl(w_{p(i)}\mathbin{\oplus}t_i\bigr)_{i=0}^{n-1}:w\in C\,\right\} :\ p\text{ a coordinate permutation},\ t\in\{0,1\}^n \right\}.$$

The definition returns the number of distinct finite sets $\mathcal O(C)$ obtained this way, counting equal orbit sets only once. Here $\oplus$ is Boolean exclusive-or. The value is zero if $m>2^n$, or if $n>0$ and $m<2$. For $n=0$, the coordinate condition is vacuous, and the value is $1$ for $m=0$ or $m=1$, and $0$ otherwise.

QAlgorithms.Papers.Independent.Intakethird100.P30.codeKraus

For index types $K$ and $I$, with equality of Boolean functions on $I$ decidable, and any map $C:K\to(I\to\{\mathrm{false},\mathrm{true}\})$, this defines a complex matrix $F_C$ with rows indexed by $K$ and columns indexed by Boolean functions $w$ on $I$, by $(F_C)_{k,w}=1$ if $w=C(k)$, and $0$ otherwise. No injectivity assumption is imposed on $C$; distinct labels with the same image give identical rows. An empty $K$ gives a matrix with no rows.

QAlgorithms.Papers.Independent.Intakethird100.P30.codeOrbit

For every natural number $n$ and finite set $C\subseteq\{0,1\}^n$, this defines the finite set of finite sets

$$\left\{ \left\{\,\bigl(w_{p(i)}\mathbin{\oplus}t_i\bigr)_{i=0}^{n-1}:w\in C\,\right\} :\ p\text{ is a permutation of }\{0,\ldots,n-1\},\ t\in\{0,1\}^n \right\},$$

where $\oplus$ denotes Boolean exclusive-or. Equal resulting sets occur only once, even if several choices of $p,t$ produce them. This collection is nonempty and includes $C$; if $C=\varnothing$, it is $\{\varnothing\}$, and if $n=0$, it is $\{C\}$.

QAlgorithms.Papers.Independent.Intakethird100.P30.codeProduct

For types $I,J,K,L$ and functions $C:K\to(I\to\{\mathrm{false},\mathrm{true}\})$ and $D:L\to(J\to\{\mathrm{false},\mathrm{true}\})$, this defines a function indexed by $K\times L$, whose coordinates lie in the disjoint union $I\sqcup J$: the word indexed by $(k,l)$ has value $C(k)(i)$ at the copy of $i\in I$, and value $D(l)(j)$ at the copy of $j\in J$. Empty types are allowed, with $K\times L$ empty if either indexing type is empty.

QAlgorithms.Papers.Independent.Intakethird100.P30.codeSlack

For finite types $I$ and $K$ with decidable equality, any indexed collection of Boolean words $C:K\to\{0,1\}^{I}$, and any real $Q$, define the matrix $P$ indexed by $\{0,1\}^{I}\times K$ by

$$P_{(a,k),(a',l)} =\prod_{i\in I}\left[ \frac{1-2Q}{2}\,\mathbf1_{a_i=C(k)_i}\mathbf1_{a'_i=C(l)_i} +\frac Q2\,\mathbf1_{a_i=a'_i}\mathbf1_{C(k)_i=C(l)_i} \right],$$

where $\mathbf1_E$ is $1$ when $E$ holds and $0$ otherwise. This defines the code slack to be the infimum of all real $t$ admitting a Hermitian matrix $R$ indexed by $(\{0,1\}^{I}\times K)\times K$ such that $R+tI$ is positive semidefinite and both sums

$$\sum_{h\in K}R_{((a,k),h),((a',l),h)}, \qquad \sum_{h\in K}R_{((a,h),k),((a',h),l)}$$

equal $P_{(a,k),(a',l)}$ for every $a,a',k,l$. An empty or unbounded-below feasible set has real infimum $0$. No restriction on $Q$, injectivity of $C$, or nonemptiness of the index types is imposed; an empty coordinate product equals $1$.

QAlgorithms.Papers.Independent.Intakethird100.P30.codeWordXor

For any index type $I$ and functions $u,v:I\to\{\mathrm{false},\mathrm{true}\}$, this defines their coordinatewise exclusive-or: $(u\oplus v)(i)$ is true exactly when $u(i)\ne v(i)$. If $I$ is empty, the result is the unique function on the empty type.

QAlgorithms.Papers.Independent.Intakethird100.P30.columnOrbitCandidates

For arbitrary natural numbers $n,m$ and any collection $C$ of $m$ Boolean words of length $n$, this defines the finite set

$$\left\{\mathcal O\!\left(\{(v_k,C(k)):0\le k<m\}\right): v\in\{0,1\}^{m},\ \exists k,l\ (v_k\ne v_l)\right\},$$

where $(v_k,C(k))$ denotes prepending the bit $v_k$, and, for a finite set $D$ of length-$(n+1)$ words,

$$\mathcal O(D)= \left\{\left\{\,i\mapsto w_{p(i)}\mathbin{\oplus}t_i:w\in D\,\right\}: p\text{ is a permutation of the coordinates},\ t\in\{0,1\}^{n+1}\right\}.$$

The result is therefore a finite set of orbits, each orbit being a finite set of finite word sets. Repeated words and repeated orbits are discarded. No injectivity assumption on $C$ is imposed; when $m=0$ or $m=1$, there are no varying columns and the result is empty.

QAlgorithms.Papers.Independent.Intakethird100.P30.complementExtension

For every natural number $n$ and finite set $C$ of Boolean words of length $n$, this defines the finite set of length-$(n+1)$ words

$$\{(0,w):w\in C\}\ \cup\ \{(1,\neg w):w\in C\},$$

where the displayed first bit is prepended and $\neg w$ reverses every bit of $w$. The definition includes empty $C$, giving the empty set, and $n=0$, when $C$ is a subset of the singleton set consisting of the empty word.

QAlgorithms.Papers.Independent.Intakethird100.P30.complementaryOperator

For finite index types $A,B$ with decidable equality and any complex matrix $P$ indexed by $A\times B$, let $S=f(P)$, where $f(t)=\sqrt t$ is applied by the real continuous functional calculus. This defines a matrix $K_P$ indexed by $A\times(A\times B)$ through

$$(K_P)_{(a,x),(a',y)} =\sum_{b\in B}S_{(a,b),x}\,\overline{S_{(a',b),y}}, \qquad x,y\in A\times B.$$

Equivalently, the summands are entries of the matrix $v_Pv_P^{*}$, where $v_P(u,x)=S_{u,x}$. No positivity or normalization assumption is imposed on $P$; for Hermitian $P$, negative eigenvalues contribute zero under the real square root, and for non-Hermitian $P$, $S=0$. Empty index types are allowed, and an empty sum is zero.

QAlgorithms.Papers.Independent.Intakethird100.P30.cyclicBellVector

For every natural number $m$ and indices $k,l\in\{0,\ldots,m-1\}$, this defines a vector $v_{k,l}$ in the complex Euclidean space indexed by $\{0,\ldots,m-1\}^2$, with coordinates

$$v_{k,l}(a,b)= \begin{cases} \dfrac{1}{\sqrt m}\exp\!\left(\mathrm{i}\,\dfrac{2\pi a l}{m}\right), &b=(a+k)\bmod m,\\[4pt] 0,&\text{otherwise}. \end{cases}$$

The remainder is computed using natural numbers, while the division in the exponential is real division. The supplied indices force $m\ge1$; for $m=0$ there are no choices of $k,l$.

QAlgorithms.Papers.Independent.Intakethird100.P30.deleteConstants

For types $I,K$ and a function $C:K\to(I\to\{\mathrm{false},\mathrm{true}\})$, this defines a function with the same word index type $K$, restricted to coordinates $i\in I$ for which some $k,l\in K$ satisfy $C(k)(i)\ne C(l)(i)$: its value at word index $k$ and such a coordinate $i$ is $C(k)(i)$. If there are no such coordinates, every indexed word is the unique function on the empty coordinate type.

QAlgorithms.Papers.Independent.Intakethird100.P30.diagonalLaw

For finite index types $A,B$, any complex matrix $P$ with rows and columns indexed by $A\times B$, and elements $a\in A$, $b\in B$, this defines the real value $\displaystyle \frac{\operatorname{Re}P_{(a,b),(a,b)}}{\operatorname{Re}(\operatorname{tr}P)}$, where $\operatorname{tr}P=\sum_{(x,y)\in A\times B}P_{(x,y),(x,y)}$. No positivity or normalization condition on $P$ is imposed, and the value is $0$ whenever the real part of its trace is $0$, because real division by zero is defined to give $0$.

QAlgorithms.Papers.Independent.Intakethird100.P30.forgottenAnnouncement

For every natural number $n$, finite type $S$ with its specified finite enumeration, family of finite sets $\mathrm{cells}_s\subseteq\{0,1\}^n$, finite set $\mathrm{accepted}\subseteq S$, and real number $Q$, this defines a complex matrix indexed by $\{0,1\}^n\times\{0,1\}^n$. Its entry at row $(a,b)$ and column $(a',b')$ is

$$\sum_{s\in\mathrm{accepted}} \mathbf1_{\{b,b'\in\mathrm{cells}_s\}} \prod_{i=0}^{n-1} \left(\frac{1-2Q}{2}\mathbf1_{a_i=b_i}\mathbf1_{a'_i=b'_i} +\frac Q2\mathbf1_{a_i=a'_i}\mathbf1_{b_i=b'_i}\right).$$

No restriction on $Q$, partition condition, or nonemptiness condition is imposed. In particular, a pair $b,b'$ belonging to several accepted cells contributes once for each such cell. An empty accepted set gives zero, and for $n=0$ the product is the empty product $1$.

QAlgorithms.Papers.Independent.Intakethird100.P30.fourWordCode

For every natural number $n$, this defines a Boolean word for each pair $(b,c)$ of Boolean values on the disjoint union of a singleton coordinate set and an $n$-element coordinate set: its value on the singleton is $b$, and its value at each of the other $n$ coordinates is $c$. Equivalently, it is the word $(b,c,\ldots,c)$ with $n$ copies of $c$. This includes $n=0$, when the word has only the singleton coordinate and is independent of $c$.

QAlgorithms.Papers.Independent.Intakethird100.P30.multiCode

For any type $S$, coordinate types $D_s$ and label types $M_s$ depending on $s\in S$, and maps $C_s:M_s\to\{0,1\}^{D_s}$, this defines a code whose labels are dependent choices $k=(k_s)_{s\in S}$, with $k_s\in M_s$, and whose coordinates are pairs $(s,i)$ with $i\in D_s$, by

$$C_{\mathrm{multi}}(k)_{(s,i)}=C_s(k_s)_i.$$

No finiteness, nonemptiness, or injectivity assumptions are imposed. In particular, if $S$ is empty, both the label-assignment type and the Boolean-string type on the resulting empty coordinate type have a single element.

QAlgorithms.Papers.Independent.Intakethird100.P30.otherMarginal

For an index type $A$, a finite index type $B$, and any complex matrix $R$ indexed by $(A\times B)\times B$, this defines a matrix on $A\times B$ by

$$M_{(a,b),(a',b')} =\sum_{c\in B}R_{((a,c),b),((a',c),b')}.$$

Thus the sum uses the same value $c$ in the middle coordinate of the row and column. No positivity, Hermitian symmetry, or trace condition is assumed on $R$. If $B$ is empty, the resulting matrix has an empty index set.

QAlgorithms.Papers.Independent.Intakethird100.P30.prependCodeColumn

For arbitrary natural numbers $n,m$, a collection $C$ of $m$ Boolean words of length $n$, and a Boolean column $v$ indexed by the same $m$ labels, this defines the collection of length-$(n+1)$ words whose word at label $k$ has first bit $v_k$ and remaining bits equal to $C(k)$. Explicitly, its coordinate $0$ is $v_k$, and its coordinate $i+1$ is $C(k)_i$ for $0\le i<n$. No injectivity or variation condition is imposed; $m=0$ gives an empty indexed collection, and $n=0$ gives one-bit words.

QAlgorithms.Papers.Independent.Intakethird100.P30.publicAnnouncement

For every natural number $n$, finite type $S$ with its specified finite enumeration, family of finite sets $\mathrm{cells}_s\subseteq\{0,1\}^n$, finite set $\mathrm{accepted}\subseteq S$, and real number $Q$, this defines a complex matrix indexed by $(\{0,1\}^n\times S)\times(\{0,1\}^n\times S)$. Write

$$E_Q((a,b),(a',b'))= \frac{1-2Q}{2}\mathbf1_{a=b}\mathbf1_{a'=b'} +\frac Q2\mathbf1_{a=a'}\mathbf1_{b=b'}$$

for bits $a,b,a',b'$. Its entry at row $((a,s),(b,t))$ and column $((a',s'),(b',t'))$ is

$$\begin{cases} \displaystyle\prod_{i=0}^{n-1}E_Q((a_i,b_i),(a'_i,b'_i)), & s=t,\ s'=t',\ s=s',\ s\in\mathrm{accepted},\ b,b'\in\mathrm{cells}_s,\\ 0,&\text{otherwise}. \end{cases}$$

There are no assumptions on $Q$, on whether the cells are nonempty or form a partition, or on whether the accepted set is nonempty. An empty accepted set gives the zero matrix; when $n=0$, the displayed product is $1$; and when $S$ is empty, the matrix has an empty index type.

QAlgorithms.Papers.Independent.Intakethird100.P30.repetition

For any type $I$, this defines the function taking each Boolean $b$ to the constant word $I\to\{\mathrm{false},\mathrm{true}\}$ with value $b$ at every coordinate. If $I$ is empty, both Boolean inputs produce the same empty word.

QAlgorithms.Papers.Independent.Intakethird100.P30.repetitionApprox

For every natural number $n$, set $r=(1/4)^{1/n}$, using real exponentiation and real division, and set $a=4r+1$; this defines the real value $\displaystyle \frac{a-\sqrt{a^2-4ra}}{2a}$, where the square root is the real square-root function. The definition includes $n=0$: real division gives $1/0=0$, so $r=1$, $a=5$, and the resulting value is $(5-\sqrt5)/10$.

QAlgorithms.Papers.Independent.Intakethird100.P30.repetitionPolynomial

For every natural number $n$ and real number $q$, this defines the real value $4q^{2n}-4q^n(1-q)^n+(1-2q)^{2n}$. There is no restriction on $q$; $n=0$ is included and gives the value $1$ for every $q$, using the convention that every zeroth power, including $0^0$, is $1$.

QAlgorithms.Papers.Independent.Intakethird100.P30.sdpMinimum

For finite index types $A$ and $B$ with decidable equality and any complex matrix $P$ indexed by $A\times B$, this defines a real number as the infimum of all real $t$ for which there exists a Hermitian matrix $R$ indexed by $(A\times B)\times B$ such that $R+tI$ is positive semidefinite and, for every $a,a'\in A$ and $b,b'\in B$,

$$\sum_{c\in B}R_{((a,b),c),((a',b'),c)}=P_{(a,b),(a',b')}, \qquad \sum_{c\in B}R_{((a,c),b),((a',c),b')}=P_{(a,b),(a',b')}.$$

There is no positivity or normalization assumption on $P$, and no attainment assertion in this definition. The real infimum is interpreted as $0$ if its defining set is empty or unbounded below.

QAlgorithms.Papers.Independent.Intakethird100.P30.simplexA

For every triple of natural numbers $n,m,d$ and every real number $Q$, this defines

$$A_{n,m,d}(Q)= \frac{ \left(\frac{1-Q}{2}\right)^n+ (m-1)\dfrac{(1-2Q)^d(1-Q)^{\max(n-d,0)}}{2^n} }{ m\left(\frac{1-Q}{2}\right)^n+ m(m-1)\dfrac{Q^d(1-Q)^{\max(n-d,0)}}{2^n} }.$$

The coefficients use real subtraction $m-1$, and the exponent uses truncated natural-number subtraction. There are no restrictions on the parameters and no nonzero-denominator hypothesis: division by zero has value $0$, so in particular the value is $0$ when $m=0$. Zeroth powers, including $0^0$, are $1$.

QAlgorithms.Papers.Independent.Intakethird100.P30.simplexB

For every triple of natural numbers $n,m,d$ and every real number $Q$, this defines

$$B_{n,m,d}(Q)= \frac{ \left(\frac{1-Q}{2}\right)^n- \dfrac{(1-2Q)^d(1-Q)^{\max(n-d,0)}}{2^n} }{ m\left(\frac{1-Q}{2}\right)^n+ m(m-1)\dfrac{Q^d(1-Q)^{\max(n-d,0)}}{2^n} }.$$

The denominator's coefficients use real subtraction $m-1$, and the exponent uses truncated natural-number subtraction. There are no restrictions on the parameters and no nonzero-denominator hypothesis: division by zero has value $0$, so in particular the value is $0$ when $m=0$. Zeroth powers, including $0^0$, are $1$.

QAlgorithms.Papers.Independent.Intakethird100.P30.simplexS

For every natural number $n$ and every real number $Q$, this defines

$$S_n(Q)=\left(\frac{1-Q}{2}\right)^n.$$

There is no restriction on $Q$; when $n=0$, the value is $1$, including when the base is zero.

QAlgorithms.Papers.Independent.Intakethird100.P30.simplexU

For every pair of natural numbers $n,d$ and every real number $Q$, this defines

$$U_{n,d}(Q)=\frac{Q^d(1-Q)^{\max(n-d,0)}}{2^n}.$$

The subtraction in the exponent is natural-number subtraction, so the exponent is $0$ whenever $d\ge n$. No condition $d\le n$ or restriction on $Q$ is imposed, and every zeroth power, including $0^0$, is $1$.

QAlgorithms.Papers.Independent.Intakethird100.P30.simplexV

For every pair of natural numbers $n,d$ and every real number $Q$, this defines

$$V_{n,d}(Q)=\frac{(1-2Q)^d(1-Q)^{\max(n-d,0)}}{2^n}.$$

The subtraction in the exponent is natural-number subtraction, so the exponent is $0$ whenever $d\ge n$. No condition $d\le n$ or restriction on $Q$ is imposed, and every zeroth power, including $0^0$, is $1$.

QAlgorithms.Papers.Independent.Intakethird100.P30.simplexWeights

For natural numbers $n,m,d$, a real number $Q$, and indices $k,l\in\{0,\ldots,m-1\}$, put

$$s=\left(\frac{1-Q}{2}\right)^n,\qquad u=\frac{Q^d(1-Q)^{\max(n-d,0)}}{2^n},\qquad v=\frac{(1-2Q)^d(1-Q)^{\max(n-d,0)}}{2^n},\qquad z=ms+m(m-1)u.$$

The defined weight is

$$w_{k,l}= \begin{cases} \dfrac{s+(m-1)v}{z},&k=0,\ l=0,\\[4pt] \dfrac{s-v}{z},&k=0,\ l\ne0,\\[4pt] \dfrac{u}{z},&k\ne0. \end{cases}$$

Here $m-1$ in the coefficients is real subtraction, the exponent uses truncated natural-number subtraction, and zeroth powers are $1$, including $0^0$. No restriction on $Q$ or nonvanishing condition on $z$ is imposed; if $z=0$, all these quotients are $0$. When $m=0$, there are no indices $k,l$ at which to evaluate the function.

QAlgorithms.Papers.Independent.Intakethird100.P30.simplexZ

For every triple of natural numbers $n,m,d$ and every real number $Q$, this defines

$$Z_{n,m,d}(Q) = m\left(\frac{1-Q}{2}\right)^n + m(m-1)\frac{Q^d(1-Q)^{\max(n-d,0)}}{2^n},$$

where $m$ is regarded as a real number in the coefficients, so $m-1$ there is real subtraction, while the exponent uses truncated natural-number subtraction. No positivity or nonvanishing condition is imposed; in particular, $m=0$ gives $Z_{n,0,d}(Q)=0$. Zeroth powers are $1$, including $0^0$.

QAlgorithms.Papers.Independent.Intakethird100.P30.sixState

For every real number $Q$, this defines the complex matrix $S_Q$, with rows and columns indexed by pairs of Boolean values, by

$$(S_Q)_{(a,b),(c,d)} =\frac{1-2Q}{2}\,\mathbf1_{a=b}\mathbf1_{c=d} +\frac Q2\,\mathbf1_{a=c}\mathbf1_{b=d},$$

where $\mathbf1_E$ is $1$ when $E$ holds and $0$ otherwise. Equivalently, $S_Q=(1-2Q)vv^\ast+(Q/2)I_4$, where $v(a,b)=\mathbf1_{a=b}/\sqrt2$. The parameter $Q$ is unrestricted; in particular, the definition imposes no positivity condition on the resulting matrix.

QAlgorithms.Papers.Independent.Intakethird100.P30.sixStateBellPair

This defines a vector $v\in\mathbb C^{\{\mathrm{false},\mathrm{true}\}^2}$ by $v(a,b)=1/\sqrt2$ when $a=b$, and $v(a,b)=0$ otherwise. Thus $v=(|00\rangle+|11\rangle)/\sqrt2$, where $0$ denotes false, $1$ denotes true, and $|ab\rangle$ is the coordinate vector supported at $(a,b)$.

QAlgorithms.Papers.Independent.Intakethird100.P30.sixStateCopies

For every finite type $I$ and every real number $Q$, this defines a complex matrix indexed by pairs of Boolean functions on $I$. Its entry at row $(a,b)$ and column $(c,d)$, where $a,b,c,d:I\to\{\mathrm{false},\mathrm{true}\}$, is

$$\prod_{i\in I} \left( \frac{1-2Q}{2}\,\mathbf1_{a(i)=b(i)}\mathbf1_{c(i)=d(i)} +\frac Q2\,\mathbf1_{a(i)=c(i)}\mathbf1_{b(i)=d(i)} \right).$$

Here $\mathbf1_E$ denotes the indicator of $E$, and no restriction is placed on $Q$. If $I$ is empty, the product is $1$, so the resulting matrix has its sole entry equal to $1$.

QAlgorithms.Papers.Independent.Intakethird100.P30.slackValues

For finite index types $A,B$ and any complex matrix $P$ indexed by $A\times B$, this defines the set of all real numbers $t$ for which there exists a complex matrix $R$ indexed by $(A\times B)\times B$ such that $R$ is Hermitian, $R+tI$ is positive semidefinite, and, for every $a,a'\in A$ and $b,b'\in B$,

$$\sum_{c\in B}R_{((a,b),c),((a',b'),c)} =P_{(a,b),(a',b')} =\sum_{c\in B}R_{((a,c),b),((a',c),b')}.$$

Here $I$ is the identity matrix on the index type of $R$. The witness $R$ may depend on $t$; no nonnegativity restriction on $t$ or trace normalization is imposed. If $A$ or $B$ is empty, this set is all of $\mathbb R$.

QAlgorithms.Papers.Independent.Intakethird100.P30.tableEntries

This defines the following ordered list of triples of natural numbers:

$$\begin{aligned} [&(2,2,1),(2,3,1),\\ &(3,2,1),(3,3,2),(3,4,5),(3,5,3),(3,6,3),(3,7,1),\\ &(4,2,1),(4,3,3),(4,4,13),(4,5,24),(4,6,47),(4,7,55),\\ &(4,8,73),(4,9,56),(4,10,50),(4,11,27),(4,12,19),\\ &(4,13,6),(4,14,4),(4,15,1),\\ &(5,2,1),(5,3,4),(5,4,28),(5,5,104),(5,6,422),\\ &(6,2,1),(6,3,6),(6,4,56),\\ &(7,2,1),(7,3,7),(8,2,1),(8,3,9)]. \end{aligned}$$

QAlgorithms.Papers.Independent.Intakethird100.P30.threshold

For finite index types $A,B$ and any function $P$ assigning a complex matrix on $A\times B$ to each real number, this defines

$$\sup\!\left( \{0\}\cup \left\{q\in[0,\tfrac12]: \begin{array}{l} \text{there is no positive semidefinite matrix }R \text{ on }(A\times B)\times B\\ \text{such that, for all }a,a'\in A,\ b,b'\in B,\\ \displaystyle\sum_{c\in B}R_{((a,b),c),((a',b'),c)} =P(q)_{(a,b),(a',b')},\\ \displaystyle\sum_{c\in B}R_{((a,c),b),((a',c),b')} =P(q)_{(a,b),(a',b')} \end{array} \right\} \right).$$

No continuity, positivity, or normalization assumption is imposed on $P$. The inserted $0$ makes the set nonempty, and all its elements lie in $[0,\tfrac12]$; if there are no qualifying $q$, the value is $0$. In particular, it is $0$ when either $A$ or $B$ is empty.

QAlgorithms.Papers.Independent.Intakethird100.P30.transformCodeSet

For every natural number $n$, permutation $p$ of the coordinate set $\{0,\ldots,n-1\}$, word $t\in\{0,1\}^n$, and finite set $C\subseteq\{0,1\}^n$, this defines the finite set

$$\left\{\,\bigl(w_{p(i)}\mathbin{\oplus}t_i\bigr)_{i=0}^{n-1}:w\in C\,\right\},$$

where $\oplus$ is Boolean exclusive-or. This is a set image, so repeated image values are counted only once. The empty set maps to the empty set; for $n=0$, the transformation leaves every possible $C$ unchanged.

QAlgorithms.Papers.Independent.Intakethird100.P30.twistedExtension

For every natural number $n$, finite set $C$ of Boolean words of length $n$, coordinate permutation $p$ of $\{0,\ldots,n-1\}$, and Boolean word $t$ of length $n$, this defines the finite set

$$\{(0,w):w\in C\}\ \cup\ \{(1,u):\exists w\in C,\ \forall i,\ u_i=w_{p(i)}\mathbin{\oplus}t_i\}.$$

Thus the first part prepends $0$ to each original word, and the second prepends $1$ to each word obtained by the specified coordinate permutation and coordinatewise exclusive-or with $t$. Empty $C$ gives the empty set; for $n=0$, the permutation and Boolean offset are the unique empty ones.

QAlgorithms.Papers.Independent.Intakethird100.P30.vectorPurification

For finite index types $A,B$ with decidable equality and any complex matrix $P$ indexed by $A\times B$, this defines a vector $v_P\in\mathbb C^{(A\times B)\times(A\times B)}$ by

$$v_P(x,y)=\bigl[f(P)\bigr]_{x,y},\qquad f(t)=\sqrt t,$$

where $f(P)$ is obtained using the real continuous functional calculus. No positivity, Hermitian, trace, or normalization hypothesis is imposed on $P$. For Hermitian $P$, this applies the real square-root function to its eigenvalues, with $\sqrt t=0$ for $t<0$; for non-Hermitian $P$, this real functional calculus returns the zero matrix. Empty index types are allowed.

QAlgorithms.Papers.Independent.Intakethird100.P30.xorSectorBlock

For finite coordinate and label types $I,K$, a code $C:K\to\{0,1\}^{I}$, any real $Q$, and any Boolean string $\beta:I\to\{0,1\}$, this defines a complex matrix $H_{C,Q,\beta}$ indexed by $K$, with

$$(H_{C,Q,\beta})_{k,l} =\prod_{i\in I}s_Q\bigl(\beta_i\oplus C(k)_i,C(k)_i;\, \beta_i\oplus C(l)_i,C(l)_i\bigr),$$

where $\oplus$ is Boolean XOR and

$$s_Q(u,v;u',v') =\frac{1-2Q}{2}\mathbf1_{u=v}\mathbf1_{u'=v'} +\frac Q2\mathbf1_{u=u'}\mathbf1_{v=v'}.$$

Here $\mathbf1_P$ is $1$ when $P$ holds and $0$ otherwise, and these real entries are viewed as complex numbers. This is the restriction of the matrix obtained by applying the code-selection matrix on the second subsystem of the product of the two-bit states $(1-2Q)|\Phi\rangle\langle\Phi|+(Q/2)I_4$. No injectivity or range condition on $Q$ is imposed. An empty coordinate type gives every entry value $1$, and an empty label type gives an empty matrix.

QAlgorithms.Papers.Independent.Intakethird100.P30.xorSectorPermutation

For coordinate and label types $I,K$ and a code $C:K\to\{0,1\}^{I}$, this defines the complex matrix $P_C$, whose rows and columns are indexed by $\{0,1\}^{I}\times K$, by

$$(P_C)_{(a,k),(b,l)} = \begin{cases} 1,&a_i=b_i\oplus C(l)_i\text{ for every }i\in I,\ \text{and }k=l,\\ 0,&\text{otherwise}. \end{cases}$$

Thus its entry is $1$ precisely when the row index is obtained from the column index by XORing the Boolean string with the codeword indexed by its label and retaining that label. No injectivity assumption on $C$ is part of this definition; when $I$ is empty, the string condition is vacuous.

QAlgorithms.Papers.Independent.Intakethird100.P30.zeroTail

For every natural number $n$ and finite set $D$ of Boolean strings of length $n+1$, $\operatorname{zeroTail}(D)$ is the set of length-$n$ strings obtained by keeping exactly the strings in $D$ whose first bit is false and deleting that first bit:

$$\operatorname{zeroTail}(D)=\{(w_1,\ldots,w_n):w\in D,\ w_0=\mathrm{false}\}.$$

Repeated tails appear only once because the result is a set. This definition includes empty $D$ and $n=0$, where a tail is the unique empty string.