Definitions for Polar codes for private classical communication

QAlgorithms.Papers.Independent.Intakethird100.P74.EveDegradable

For the finite index types $B,E,S_1,S_2$, with the equality decisions required by the constructions, let $d=(V,\psi)$ be data consisting of a matrix $V:\mathbb C^2\to\mathbb C^{B\times E\times S_2}$ and two vectors $\psi_z\in\mathbb C^{\{0,1\}\times S_1}$. The proposition says that there exists a function $D$ from complex $B\times B$ matrices to complex $E\times E$ matrices having a finite Kraus representation: for some natural number $r$ and matrices $K_j:\mathbb C^B\to\mathbb C^E$, $0\le j<r$,

$$\sum_{j<r}K_j^*K_j=I_B,\qquad D(X)=\sum_{j<r}K_jXK_j^*\quad\text{for every complex }B\times B\text{ matrix }X.$$

It must satisfy, for every complex $2\times2$ matrix $\rho$,

$$D\!\left(\operatorname{Tr}_{E\times S_2}(V\rho V^*)\right) = \left[\sum_{b\in B}\sum_{s\in S_2} (V\rho V^*)_{(b,e,s),(b,f,s)}\right]_{e,f\in E}.$$

The universal quantifier over $\rho$ includes matrices that are not density matrices. No validity condition on $d$ is imposed, and its vectors $\psi_z$ do not enter this proposition.

QAlgorithms.Papers.Independent.Intakethird100.P74.IsSuccessiveCancellation

For finite types $B,E,S_1,S_2$, with decidable equality as required, arbitrary data $d=(V,\psi)$, $\beta\in\mathbb R$, $n\in\mathbb N$, and a matrix family $M(k,m)$ on $B^N$, where $N=2^n$, define

$$\Psi_z(b,e,s,t)=\sum_aV_{(b,e,t),a}\psi_z(a,s), \qquad W(z)_{b,b'}=\sum_{e,s,t}\Psi_z(b,e,s,t)\overline{\Psi_z(b',e,s,t)}.$$

Here $a,z$ are bits. Let $G_{rj}=1$ exactly when every $1$ in binary position $k<n$ of $j$ implies a $1$ in position $n-1-k$ of $r$, and otherwise let it be $0$, and set $c(u)_j=\sum_r u_rG_{rj}\pmod2$. For $v,w$ assigning bits to indices preceding $i$, define

$$S_i(b)_{(v,y),(w,y')}= \begin{cases} 2^{-(N-1)} \displaystyle\sum_{\substack{u_i=b\\u_j=v_j\ (j<i)}}\prod_{r<N}W(c(u)_r)_{y_r,y'_r},&v=w,\\ 0,&v\ne w, \end{cases} \qquad D=\left\{i:\operatorname{Re}\operatorname{tr} \sqrt{\sqrt{S_i(0)}S_i(1)\sqrt{S_i(0)}}<2^{-N^\beta}\right\},$$

where the sum runs over all length-$N$ bit strings satisfying the displayed conditions and square roots use continuous functional calculus. The arguments $k,m$ of $M$ range over bit assignments on $D^c,D$, respectively. The predicate says that there exists a family $T(k,i,v)$ of matrices on $B^N$, defined for every such $k$, every $i<N$, and every assignment $v$ on $\{j:j<i\}$, such that $T(k,i,v)$ and $I-T(k,i,v)$ are positive semidefinite and $T(k,i,v)^2=T(k,i,v)$. For every $k,m$, combine them into $u$ by $u_i=m_i$ on $D$ and $u_i=k_i$ on $D^c$, and set

$$P_i= \begin{cases} T(k,i,u|_{\{j:j<i\}}),&i\in D,\ u_i=0,\\ I-T(k,i,u|_{\{j:j<i\}}),&i\in D,\ u_i=1,\\ I,&i\notin D. \end{cases}$$

It requires precisely

$$M(k,m)=K^\dagger K,\qquad K=P_{N-1}\cdots P_1P_0.$$

The conditions on $T$ also apply at indices outside $D$, although those matrices are replaced by $I$ in the product. No validity assumption on $d$ is included; $n=0$ gives a one-factor product, and empty assignment domains carry their unique assignment.

QAlgorithms.Papers.Independent.Intakethird100.P74.PolarDecoderEffects

For finite types $B,E,S_1,S_2$, with decidable equality as required, arbitrary data $d=(V,\psi)$, any $\beta\in\mathbb R$, and any $n\in\mathbb N$, put $N=2^n$. Define

$$\Psi_z(b,e,s,t)=\sum_{a\in\{0,1\}}V_{(b,e,t),a}\psi_z(a,s), \qquad W(z)_{b,b'}=\sum_{e,s,t}\Psi_z(b,e,s,t)\overline{\Psi_z(b',e,s,t)}.$$

Let $G_{rj}=1$ exactly when every binary digit $k<n$ of $j$ equal to $1$ forces digit $n-1-k$ of $r$ to equal $1$, and otherwise let $G_{rj}=0$; write $c(u)_j=\sum_r u_rG_{rj}\pmod2$. For assignments $v,w$ on $\{j:j<i\}$ and strings $y,y'\in B^N$, set

$$S_i(b)_{(v,y),(w,y')}= \begin{cases} 2^{-(N-1)} \displaystyle\sum_{\substack{u\in\{0,1\}^N\\u_i=b,\ u|_{\{j:j<i\}}=v}} \prod_{r<N}W(c(u)_r)_{y_r,y'_r},&v=w,\\ 0,&v\ne w. \end{cases}$$

Using matrix square roots from continuous functional calculus, let

$$D=\left\{i: \operatorname{Re}\operatorname{tr} \sqrt{\sqrt{S_i(0)}\,S_i(1)\,\sqrt{S_i(0)}} <2^{-N^\beta}\right\}.$$

The abbreviation denotes the type of all functions assigning a complex matrix on $B^N$ to each pair consisting of a bit assignment $k$ on $D^c=\{0,\ldots,N-1\}\setminus D$ and a bit assignment $m$ on $D$. It imposes no positivity, normalization, or measurement condition on these matrices. Empty assignment domains have their unique empty assignment, and $n=0$, hence $N=1$, is included.

QAlgorithms.Papers.Independent.Intakethird100.P74.WiretapData.Valid

For a datum $d=(V,\psi)$ on finite index types $B,E,S_1,S_2$, validity means exactly that $V^\dagger V=I$ and $\|\psi_z\|_2=1$ for every Boolean $z$; explicitly, for all Booleans $a,a'$,

$$\sum_{b\in B}\sum_{e\in E}\sum_{s_2\in S_2} \overline{V_{(b,e,s_2),a}}V_{(b,e,s_2),a'} =\begin{cases}1&a=a',\\0&a\ne a',\end{cases} \qquad \sum_{a}\sum_{s_1\in S_1}|\psi_z(a,s_1)|^2=1.$$

These conditions cannot hold if any of $B,E,S_1,S_2$ is empty.

QAlgorithms.Papers.Independent.Intakethird100.P74.WiretapData

For arbitrary types $B,E,S_1,S_2$, a wiretap datum consists of a complex matrix $V$, whose rows are indexed by $B\times E\times S_2$ and columns by $\{\mathrm{false},\mathrm{true}\}$, and two complex vectors $\psi_z$, one for each Boolean $z$, with coordinates indexed by $\{\mathrm{false},\mathrm{true}\}\times S_1$. The structure itself imposes no isometry, normalization, positivity, finiteness, or nonemptiness requirements.

QAlgorithms.Papers.Independent.Intakethird100.P74.actualPhaseSplit

For arbitrary data $d=(V,\psi)$ on types $B,E,S_1,S_2$, with $E$ finite for the partial trace, any $n\in\mathbb N$, an index $0\le i<N=2^n$, and a bit $b$, let $J_i=\{j:i<j<N\}$. The definition gives a matrix indexed by pairs $(v,y)$, where $v:J_i\to\{0,1\}$ and $y_r=(z_r,b_r,s_r,t_r)\in\{0,1\}\times B\times S_1\times S_2$. Define $G_{rj}=1$ exactly when every $1$ in binary position $k<n$ of $j$ implies a $1$ in position $n-1-k$ of $r$, and otherwise let it be $0$; put $c_j(z)=\sum_r z_rG_{rj}\pmod2$ and

$$\Psi_a(b,e,s,t)=\sum_{\alpha\in\{0,1\}}V_{(b,e,t),\alpha}\psi_a(\alpha,s).$$

For each bit string $x$, define

$$R_x(y,y') = 2^{-N}(-1)^{\sum_{r<N}x_r(z_r+z'_r)} \sum_{e\in E^N}\prod_{r<N} \Psi_{c_r(z)}(b_r,e_r,s_r,t_r) \overline{\Psi_{c_r(z')}(b'_r,e_r,s'_r,t'_r)}.$$

The defined matrix has entries

$$A_{(v,y),(w,y')}= \begin{cases} 2^{-(N-1)} \displaystyle\sum_{\substack{x\in\{0,1\}^N\\x_i=b,\ x|_{J_i}=v}}R_x(y,y'),&v=w,\\ 0,&v\ne w. \end{cases}$$

The prefactor is $2^{-(N-1)}$, regardless of the number of later indices. No validity or normalization condition on $d$ is assumed. For $n=0$, there is one bit and no later index, the prefactor is $1$, and the sum contains the single string $x_0=b$.

QAlgorithms.Papers.Independent.Intakethird100.P74.amplitudeBob

For index types $B,E,S_1,S_2$, with $E,S_1,S_2$ finite, a datum $d=(V,\psi)$, and a Boolean $z$, this definition gives the complex $B$-indexed matrix with entries

$$(\rho^B_z)_{b,b'} =\sum_{e\in E}\sum_{s_2\in S_2}\sum_{s_1\in S_1} \sum_{a,a'\in\{\mathrm{false},\mathrm{true}\}} V_{(b,e,s_2),a}\psi_z(a,s_1) \overline{\psi_z(a',s_1)} \overline{V_{(b',e,s_2),a'}}.$$

Thus the Boolean input matrix has entries $\sum_{s_1}\psi_z(a,s_1)\overline{\psi_z(a',s_1)}$, is conjugated by $V$, and is then summed over matching $E$ and $S_2$ coordinates. No validity assumption is imposed; empty summed index types give zero.

QAlgorithms.Papers.Independent.Intakethird100.P74.amplitudeEve

For index types $B,E,S_1,S_2$, with $B,S_1,S_2$ finite, a datum $d=(V,\psi)$, and a Boolean $z$, this definition gives the complex $E$-indexed matrix with entries

$$(\rho^E_z)_{e,f} =\sum_{b\in B}\sum_{s_2\in S_2}\sum_{s_1\in S_1} \sum_{a,a'\in\{\mathrm{false},\mathrm{true}\}} V_{(b,e,s_2),a}\psi_z(a,s_1) \overline{\psi_z(a',s_1)} \overline{V_{(b,f,s_2),a'}}.$$

Thus the Boolean input matrix has entries $\sum_{s_1}\psi_z(a,s_1)\overline{\psi_z(a',s_1)}$, is conjugated by $V$, and is then summed over matching $B$ and $S_2$ coordinates. No validity assumption is imposed; empty summed index types give zero.

QAlgorithms.Papers.Independent.Intakethird100.P74.binaryPhaseBellVector

For every Boolean value $x$, this defines a vector indexed by pairs of Boolean values by

$$|\Phi_x\rangle =\frac{|\mathrm{false},\mathrm{false}\rangle +(-1)^{x_{\mathrm{nat}}}|\mathrm{true},\mathrm{true}\rangle}{\sqrt2},$$

where $x_{\mathrm{nat}}=0$ for false and $1$ for true, and each ket is the corresponding coordinate vector. Equivalently, its amplitude is zero at unequal Boolean pairs, $1/\sqrt2$ at $(\mathrm{false},\mathrm{false})$, and either $1/\sqrt2$ or $-1/\sqrt2$ at $(\mathrm{true},\mathrm{true})$ according as $x$ is false or true.

QAlgorithms.Papers.Independent.Intakethird100.P74.bitSign

For a Boolean $b$, this definition gives the complex number $-1$ when $b=\mathrm{true}$, and $1$ when $b=\mathrm{false}$.

QAlgorithms.Papers.Independent.Intakethird100.P74.bobMap

For index types $B,E,S_1,S_2$, with $E,S_2$ finite, and a datum $d=(V,\psi)$, this definition gives a function from complex Boolean-indexed square matrices $\rho$ to complex $B$-indexed square matrices, defined for all $b,b'\in B$ by

$$\mathcal B_d(\rho)_{b,b'} =\sum_{e\in E}\sum_{s_2\in S_2} (V\rho V^\dagger)_{(b,e,s_2),(b',e,s_2)} =\sum_{e,s_2}\sum_{a,a'} V_{(b,e,s_2),a}\rho_{a,a'} \overline{V_{(b',e,s_2),a'}}.$$

Here $a,a'$ range over the two Booleans. The vector family $\psi$ is unused; neither validity of $d$ nor a density-matrix condition on $\rho$ is assumed. An empty summed index type makes the output zero.

QAlgorithms.Papers.Independent.Intakethird100.P74.bscOutput

For every real number $p$ and Boolean value $x$, this defines a complex matrix with Boolean row and column indices by

$$W_p(x)_{y,z}= \begin{cases} 1-p,&y=z=x,\\ p,&y=z\ne x,\\ 0,&y\ne z. \end{cases}$$

Thus, in the order $(\mathrm{false},\mathrm{true})$, $W_p(\mathrm{false})=\operatorname{diag}(1-p,p)$ and $W_p(\mathrm{true})=\operatorname{diag}(p,1-p)$. The definition imposes no restriction on $p$.

QAlgorithms.Papers.Independent.Intakethird100.P74.bscProbability

For every real number $p$ and Boolean values $x,y$, the real-valued function is defined by

$$\operatorname{bscProbability}(p,x,y)= \begin{cases} 1-p,&x=y,\\ p,&x\ne y. \end{cases}$$

There is no assumption that $p\in[0,1]$, so the definition also includes values outside the probability range.

QAlgorithms.Papers.Independent.Intakethird100.P74.cbIndex

For a pair of Boolean values $p$, this defines an index $c(p)\in\{0,1,2,3\}$ by

$$c(\mathrm{false},\mathrm{false})=0,\qquad c(\mathrm{false},\mathrm{true})=1,\qquad c(\mathrm{true},\mathrm{false})=2,\qquad c(\mathrm{true},\mathrm{true})=3.$$

QAlgorithms.Papers.Independent.Intakethird100.P74.classicalDilation

For arbitrary types $X,Y,Z$ and any function $p:X\times Y\times Z\to\mathbb R$, this defines a complex matrix $V_p$ with rows indexed by $(Y\times Z)\times(X\times Y\times Z)$ and columns indexed by $X$, by

$$(V_p)_{((y',z'),(x,y,z)),a}= \begin{cases} \sqrt{p(x,y,z)},&(y',z')=(y,z)\ \text{and }a=x,\\ 0,&\text{otherwise}. \end{cases}$$

The square root is the real square root, embedded into $\mathbb C$, so negative values of $p$ give zero in the indicated entry. There are no finiteness or probability assumptions, and the definition itself imposes no isometry condition.

QAlgorithms.Papers.Independent.Intakethird100.P74.classicalEmbedding

For any finite types $X,Y,Z$ and any real-valued function $p:X\times Y\times Z\to\mathbb R$, this defines a function $\Phi_p$ from complex $X\times X$ matrices to complex $(Y\times Z)\times(Y\times Z)$ matrices by

$$[\Phi_p(\rho)]_{(y,z),(y',z')}= \begin{cases} \displaystyle\sum_{x\in X}\rho_{x,x}\,p(x,y,z),&(y,z)=(y',z'),\\ 0,&(y,z)\ne(y',z'). \end{cases}$$

The real coefficients are regarded as complex scalars. There is no assumption that $p$ is nonnegative or normalized, or that $\rho$ is a density matrix, and no assertion here that $\Phi_p$ is a channel. Empty finite types are allowed; in particular, an empty input index type gives an empty sum and hence zero output entries.

QAlgorithms.Papers.Independent.Intakethird100.P74.classicalKraus

For arbitrary types $X,Y,Z$, any function $p:X\times Y\times Z\to\mathbb R$, and any triple $s=(x,y,z)\in X\times Y\times Z$, this defines a complex matrix $K_s$ with rows indexed by $Y\times Z$ and columns indexed by $X$, with entries

$$(K_{(x,y,z)})_{(y',z'),a}= \begin{cases} \sqrt{p(x,y,z)},&(y',z')=(y,z)\ \text{and }a=x,\\ 0,&\text{otherwise}. \end{cases}$$

The square root is the real square root, embedded into $\mathbb C$, and equals zero when its real argument is negative. No finiteness, nonnegativity, normalization, or Kraus-completeness hypothesis is part of this definition.

QAlgorithms.Papers.Independent.Intakethird100.P74.dampingAmplitude

For every real number $\eta$ and Boolean value $z$, let $|z\rangle$ be the Boolean coordinate vector, and define

$$\rho_{\eta,z} =K_0|z\rangle\langle z|K_0^\dagger +K_1|z\rangle\langle z|K_1^\dagger, \qquad K_0=\operatorname{diag}(1,\sqrt{\eta}),\quad K_1=\sqrt{1-\eta}\,|\mathrm{false}\rangle\langle\mathrm{true}|.$$

This is the matrix defined by dampingAmplitude. There is no hypothesis restricting $\eta$; real square roots of negative arguments are zero.

QAlgorithms.Papers.Independent.Intakethird100.P74.dampingMap

For every real number $\eta$, this defines a function from complex Boolean-indexed matrices to matrices of the same size by

$$\mathcal D_\eta(X)=K_0XK_0^\dagger+K_1XK_1^\dagger, \qquad K_0=\begin{pmatrix}1&0\\0&\sqrt{\eta}\end{pmatrix}, \qquad K_1=\begin{pmatrix}0&\sqrt{1-\eta}\\0&0\end{pmatrix},$$

with Boolean indices ordered as $(\mathrm{false},\mathrm{true})$. The argument $X$ is arbitrary and need not be a density matrix. No restriction on $\eta$ is imposed; the real square roots are zero when their inputs are negative.

QAlgorithms.Papers.Independent.Intakethird100.P74.dampingPhaseMatrix

For every real number $\eta$ and Boolean value $x$, let $s_x=1$ if $x=\mathrm{false}$ and $s_x=-1$ if $x=\mathrm{true}$. This defines the complex matrix, with rows and columns indexed in the order $0,1,2,3$, by

$$M_{\eta,x}= \begin{pmatrix} \frac12&0&0&\frac{s_x\sqrt{\eta}}2\\ 0&0&0&0\\ 0&0&\frac{1-\eta}2&0\\ \frac{s_x\sqrt{\eta}}2&0&0&\frac{\eta}2 \end{pmatrix}.$$

There is no restriction on $\eta$ in this definition; the real square root used here is zero when $\eta<0$.

QAlgorithms.Papers.Independent.Intakethird100.P74.dampingPhaseOutput

For every real number $\eta$ and Boolean value $x$, define $|\Phi_x\rangle=(|\mathrm{false},\mathrm{false}\rangle+(-1)^{x_{\mathrm{nat}}}|\mathrm{true},\mathrm{true}\rangle)/\sqrt2$, where $x_{\mathrm{nat}}$ is $0$ or $1$ according as $x$ is false or true. This declaration defines the complex matrix

$$\sum_{j=0}^1 (I\otimes K_j)|\Phi_x\rangle\langle\Phi_x| (I\otimes K_j)^\dagger, \qquad K_0=\operatorname{diag}(1,\sqrt\eta),\quad K_1=\sqrt{1-\eta}\,|\mathrm{false}\rangle\langle\mathrm{true}|,$$

so the matrix transformation acts on the second Boolean factor and leaves the first factor unchanged. No restriction on $\eta$ is imposed; real square roots of negative arguments are zero.

QAlgorithms.Papers.Independent.Intakethird100.P74.decayHalf

For every real $\beta$ and every natural number $n$, this defines the real number

$$2^{-\frac{(2^n)^\beta}{2}},$$

where both powers with real exponents are real powers. There is no restriction on $\beta$, and $n=0$ is included, giving $2^{-1/2}$ for every $\beta$.

QAlgorithms.Papers.Independent.Intakethird100.P74.decodedIndices

Let $B,E,S_1,S_2$ be finite types, with decidable equality on $B$, and let $d$ consist of an arbitrary complex matrix $V$ with rows indexed by $B\times E\times S_2$ and columns by Booleans, together with arbitrary vectors $\psi_z\in\mathbb C^{\{\text{false},\text{true}\}\times S_1}$ for Boolean $z$. For every real $\beta$ and natural number $n$, put $N=2^n$, define

$$f_z(b,e,s,t)=\sum_{a\in\{\text{false},\text{true}\}}V_{(b,e,t),a}\psi_z(a,s), \qquad W_z(b,b')=\sum_{e,s,t}f_z(b,e,s,t)\overline{f_z(b',e,s,t)},$$

and, for each $i<N$, let $S_i=\{j:j<i\}$ and define

$$\Sigma_i^b\bigl((s,y),(s',y')\bigr) =\mathbf1_{\{s=s'\}}\,2^{-(N-1)} \sum_{\substack{u\in\{\text{false},\text{true}\}^N\\u_i=b,\ u|_{S_i}=s}} \prod_{a=0}^{N-1}W_{v(u)_a}(y_a,y'_a),$$

with $y,y'\in B^N$. Here $v(u)_a$ is the parity of $\sum_hu_ht_{ha}$, where $t_{ha}=1$ exactly when each set bit $k<n$ of $a$ implies a set bit $n-1-k$ of $h$. This declaration defines the set of $i<N$ satisfying

$$\operatorname{Re}\operatorname{tr} \sqrt{\sqrt{\Sigma_i^{\text{false}}}\Sigma_i^{\text{true}}\sqrt{\Sigma_i^{\text{false}}}} <2^{-N^\beta},$$

using continuous functional calculus for the matrix roots. It imposes no isometry condition on $V$, no normalization condition on $\psi_z$, and no restriction on $\beta$; $n=0$ and empty index types are included.

QAlgorithms.Papers.Independent.Intakethird100.P74.decoderError

For finite types $B,E,S_1,S_2$, with decidable equality as required, arbitrary data $d=(V,\psi)$, any $\beta\in\mathbb R$, $n\in\mathbb N$, and a matrix family $M$, put $N=2^n$, define

$$\Psi_z(b,e,s,t)=\sum_{a\in\{0,1\}}V_{(b,e,t),a}\psi_z(a,s), \qquad W(z)_{b,b'}=\sum_{e,s,t}\Psi_z(b,e,s,t)\overline{\Psi_z(b',e,s,t)},$$

and let $G_{rj}=1$ exactly when every $1$ in binary position $k<n$ of $j$ forces a $1$ in position $n-1-k$ of $r$, taking $G_{rj}=0$ otherwise. Write $c(u)_j=\sum_r u_rG_{rj}\pmod2$ and

$$W^{(N)}(u)_{y,y'}=\prod_{r<N}W(c(u)_r)_{y_r,y'_r}.$$

For preceding-bit assignments $v,w$, define $S_i(b)_{(v,y),(w,y')}=0$ when $v\ne w$, and otherwise define it as $2^{-(N-1)}\sum_{u_i=b,\ u|_{\{j:j<i\}}=v}W^{(N)}(u)_{y,y'}$. Let

$$D=\left\{i: \operatorname{Re}\operatorname{tr} \sqrt{\sqrt{S_i(0)}S_i(1)\sqrt{S_i(0)}}<2^{-N^\beta}\right\},$$

with matrix square roots interpreted by continuous functional calculus, and take $M(k,m)$ to be an arbitrary complex matrix on $B^N$ for each bit assignment $k$ on $D^c$ and $m$ on $D$. The definition returns

$$2^{-N}\sum_{u\in\{0,1\}^N} \left[ 1-\operatorname{Re}\operatorname{tr} \left(M(u|_{D^c},u|_D)\,W^{(N)}(u)\right) \right].$$

Neither validity of $d$ nor any effect or successive-cancellation condition on $M$ is assumed, so this definition alone does not constrain the result to $[0,1]$. The case $n=0$ averages over the two one-bit strings, and restrictions to empty index sets are the unique empty assignments.

QAlgorithms.Papers.Independent.Intakethird100.P74.dotParity

For every natural number $n$ and Boolean vectors $x,z$ of length $2^n$, this defines a Boolean that is true exactly when

$$\sum_{i=0}^{2^n-1}\mathbf1_{\{x_i=\text{true}\}}\mathbf1_{\{z_i=\text{true}\}}$$

is odd. Thus it records the parity of the number of coordinates at which both vectors are true. The case $n=0$ has one coordinate, rather than an empty vector, and the result is true exactly when both values at that coordinate are true.

QAlgorithms.Papers.Independent.Intakethird100.P74.encodedPhaseOutput

For wiretap data $d=(V,\psi)$ on types $B,E,S_1,S_2$, with $E$ finite for the partial trace, any $n\in\mathbb N$, and any Boolean string $x$ of length $N=2^n$, this defines a matrix indexed by strings $y_i=(z_i,b_i,s_i,t_i)\in\{0,1\}\times B\times S_1\times S_2$. Let $G_{rj}=1$ exactly when every $1$ in binary position $k<n$ of $j$ is accompanied by a $1$ in position $n-1-k$ of $r$, and let it be $0$ otherwise; set $c_i(z)=\sum_r z_rG_{ri}\pmod2$ and

$$\Psi_c(b,e,s,t)=\sum_{a\in\{0,1\}}V_{(b,e,t),a}\psi_c(a,s).$$

Then the matrix entries are

$$R_x(y,y') = 2^{-N}(-1)^{\sum_{i<N}x_i(z_i+z'_i)} \sum_{e\in E^N} \prod_{i<N} \Psi_{c_i(z)}(b_i,e_i,s_i,t_i)\, \overline{\Psi_{c_i(z')}(b'_i,e_i,s'_i,t'_i)}.$$

Equivalently, it forms the outer product $\Phi_x\Phi_x^\dagger$ of the vector with coordinates $2^{-N/2}(-1)^{\sum_i x_i z_i}\prod_i\Psi_{c_i(z)}(b_i,e_i,s_i,t_i)$, then sums over the same $E^N$ index on its two sides. No validity or normalization assumption on $d$ is included, so trace $1$ is not asserted. The definition includes $n=0$, when the strings have length $1$, and an empty $E$ makes the displayed sum empty.

QAlgorithms.Papers.Independent.Intakethird100.P74.encodedPhaseVector

For types $B,E,S_1,S_2$, arbitrary data $d=(V,\psi)$, any $n\in\mathbb N$, and any Boolean string $x$ of length $N=2^n$, this defines a complex Euclidean vector indexed by pairs $(y,e)$, where $y_i=(z_i,b_i,s_i,t_i)\in\{0,1\}\times B\times S_1\times S_2$ and $e_i\in E$. Define $G_{rj}=1$ exactly when every binary position $k<n$ at which $j$ has digit $1$ has digit $1$ at position $n-1-k$ of $r$; otherwise $G_{rj}=0$. Writing

$$c_j=\sum_{r<N}z_rG_{rj}\pmod2, \qquad \Psi_c(b,e,s,t)=\sum_{a\in\{0,1\}}V_{(b,e,t),a}\psi_c(a,s),$$

the coordinate of the defined vector is

$$\Phi_x(y,e) = 2^{-N/2}(-1)^{\sum_{i<N}x_i z_i} \prod_{i<N}\Psi_{c_i}(b_i,e_i,s_i,t_i).$$

The sign is $1$ for even parity and $-1$ for odd parity of the indicated sum. Neither $V^\dagger V=I$ nor unit norm of either $\psi_c$ is assumed, so the definition itself imposes no unit-norm condition on $\Phi_x$. It includes $n=0$, for which $N=1$, the condition defining $G_{00}$ is vacuous, $c_0=z_0$, and the prefactor is $1/\sqrt2$.

QAlgorithms.Papers.Independent.Intakethird100.P74.erasureData

For every real number $\varepsilon$, this defines data consisting of a complex matrix $V$ from a Boolean input index to output indices $(b,e,s_2)\in\{0,1,2\}\times\{0,1,2\}\times\{\ast\}$, and two vectors $\psi_z$ indexed by $\mathrm{Bool}\times\{\ast\}$. Identifying false and true with $0$ and $1$, respectively, and writing $|i\rangle$ for the coordinate vector at $i$, these are

$$V|a\rangle =\sqrt{1-\varepsilon}\,|a,2,\ast\rangle +\sqrt{\varepsilon}\,|2,a,\ast\rangle, \qquad \psi_z=|z,\ast\rangle.$$

All other matrix entries are zero. No restriction on $\varepsilon$ or assertion of validity accompanies the definition; real square roots of negative inputs are defined to be zero.

QAlgorithms.Papers.Independent.Intakethird100.P74.eveMap

For index types $B,E,S_1,S_2$, with $B,S_2$ finite, and a datum $d=(V,\psi)$, this definition gives a function from complex Boolean-indexed square matrices $\rho$ to complex $E$-indexed square matrices, defined for all $e,f\in E$ by

$$\mathcal E_d(\rho)_{e,f} =\sum_{b\in B}\sum_{s_2\in S_2} (V\rho V^\dagger)_{(b,e,s_2),(b,f,s_2)} =\sum_{b,s_2}\sum_{a,a'} V_{(b,e,s_2),a}\rho_{a,a'} \overline{V_{(b,f,s_2),a'}}.$$

Here $a,a'$ range over the two Booleans. The vector family $\psi$ is unused; neither validity of $d$ nor a density-matrix condition on $\rho$ is assumed. An empty summed index type makes the output zero.

QAlgorithms.Papers.Independent.Intakethird100.P74.frozenIndices

For finite types $B,E,S_1,S_2$, with decidable equality on $B,S_1,S_2$, arbitrary matrix $V\in\mathbb C^{(B\times E\times S_2)\times\{\text{false},\text{true}\}}$, arbitrary vectors $\psi_z\in\mathbb C^{\{\text{false},\text{true}\}\times S_1}$, real $\beta$, and natural $n$, let $N=2^n$, define $f_z(b,e,s,t)=\sum_aV_{(b,e,t),a}\psi_z(a,s)$ with Boolean $a$, and put

$$W_z^{A}(b,b')=\sum_{e,s,t}f_z(b,e,s,t)\overline{f_z(b',e,s,t)},\qquad W_x^{P}((z,b,s,t),(z',b',s',t')) =\frac{\chi(x,z)\chi(x,z')}{2} \sum_e f_z(b,e,s,t)\overline{f_{z'}(b',e,s',t')},$$

where $\chi(x,z)$ equals $-1$ if both arguments are true and $1$ otherwise. For $r=A,P$, set $S_i^A=\{j:j<i\}$, $S_i^P=\{j:i<j<N\}$, and

$$\Sigma_{r,i}^{b}\bigl((s,y),(s',y')\bigr) =\mathbf1_{\{s=s'\}}\,2^{-(N-1)} \sum_{\substack{u\in\{\text{false},\text{true}\}^N\\u_i=b,\ u|_{S_i^r}=s}} \prod_{a=0}^{N-1}W^r_{v^r(u)_a}(y_a,y'_a).$$

The sequences $y,y'$ take values in $B$ for $A$, and in $\{\text{false},\text{true}\}\times B\times S_1\times S_2$ for $P$. Define $t_{ab}=1$ exactly when each set bit $k<n$ of $b$ implies a set bit $n-1-k$ of $a$; the Boolean $v^A(u)_a$ is the parity of $\sum_hu_ht_{ha}$, and $v^P(u)_a$ is the parity of $\sum_hu_ht_{ah}$. Finally, with continuous-functional-calculus roots, put

$$F_{r,i}=\operatorname{Re}\operatorname{tr} \sqrt{\sqrt{\Sigma_{r,i}^{\text{false}}}\Sigma_{r,i}^{\text{true}}\sqrt{\Sigma_{r,i}^{\text{false}}}}.$$

The defined set contains exactly those $i<N$ satisfying $F_{P,i}<2^{-N^\beta}$ and $2^{-N^\beta}\le F_{A,i}$. No isometry or normalization hypothesis is imposed on $V,\psi$, $\beta$ is unrestricted, and both $n=0$ and empty finite index types are included.

QAlgorithms.Papers.Independent.Intakethird100.P74.goodIndices

For any finite type $O$ with decidable equality, natural number $n$, Boolean $r$, arbitrary matrices $W_b\in\mathbb C^{O\times O}$ for Boolean $b$, and arbitrary real $\beta$, this defines the finite set of indices $0\le i<N=2^n$ for which

$$\operatorname{Re}\operatorname{tr} \sqrt{\sqrt{\Sigma_i^{r,\text{false}}}\, \Sigma_i^{r,\text{true}}\, \sqrt{\Sigma_i^{r,\text{false}}}} <2^{-N^\beta},$$

where each matrix square root is formed using continuous functional calculus. Here $S_i^r$ consists of indices strictly greater than $i$ when $r$ is true and strictly less than $i$ otherwise, and

$$\Sigma_i^{r,b}\bigl((s,y),(s',y')\bigr) =\mathbf1_{\{s=s'\}}\,2^{-(N-1)} \sum_{\substack{u\in\{\text{false},\text{true}\}^N\\u_i=b,\ u|_{S_i^r}=s}} \prod_{a=0}^{N-1}W_{v^r(u)_a}(y_a,y'_a).$$

The row and column indices have $s,s'\in\{\text{false},\text{true}\}^{S_i^r}$ and $y,y'\in O^N$. To define $v^r$, put $t_{ab}=1$ exactly when every set bit $k<n$ of $b$ implies a set bit $n-1-k$ of $a$; then $v^r(u)_a$ is the parity of $\sum_hu_ht_{ah}$ when $r$ is true and of $\sum_hu_ht_{ha}$ otherwise. No density-matrix hypothesis on $W$, nonemptiness hypothesis on $O$, or restriction on $\beta$ is imposed. The case $n=0$, hence $N=1$, is included, and the displayed comparison is strict.

QAlgorithms.Papers.Independent.Intakethird100.P74.independentBsc

For all real numbers $p_B,p_E$ and Boolean values $x,y,z$, this defines

$$\operatorname{independentBsc}(p_B,p_E,x,y,z) = \begin{cases}1-p_B,&x=y,\\p_B,&x\ne y\end{cases} \;\cdot\; \begin{cases}1-p_E,&x=z,\\p_E,&x\ne z.\end{cases}$$

Neither real parameter is required to lie in $[0,1]$.

QAlgorithms.Papers.Independent.Intakethird100.P74.keyIndices

For finite types $B,E,S_1,S_2$, with decidable equality on $B,S_1,S_2$, arbitrary $V\in\mathbb C^{(B\times E\times S_2)\times\{\text{false},\text{true}\}}$, arbitrary vectors $\psi_z\in\mathbb C^{\{\text{false},\text{true}\}\times S_1}$, real $\beta$, and natural $n$, put $N=2^n$, $f_z(b,e,s,t)=\sum_aV_{(b,e,t),a}\psi_z(a,s)$, and

$$W_z^{A}(b,b')=\sum_{e,s,t}f_z(b,e,s,t)\overline{f_z(b',e,s,t)},\qquad W_x^{P}((z,b,s,t),(z',b',s',t')) =\frac{\chi(x,z)\chi(x,z')}{2} \sum_e f_z(b,e,s,t)\overline{f_{z'}(b',e,s',t')},$$

where $a$ ranges over Booleans and $\chi(x,z)$ is $-1$ when both arguments are true and $1$ otherwise. For $r=A,P$, set $S_i^A=\{j:j<i\}$, $S_i^P=\{j:i<j<N\}$, and

$$\Sigma_{r,i}^{b}\bigl((s,y),(s',y')\bigr) =\mathbf1_{\{s=s'\}}\,2^{-(N-1)} \sum_{\substack{u\in\{\text{false},\text{true}\}^N\\u_i=b,\ u|_{S_i^r}=s}} \prod_{a=0}^{N-1}W^r_{v^r(u)_a}(y_a,y'_a).$$

The output indices $y$ lie in $B^N$ for $A$, and in $(\{\text{false},\text{true}\}\times B\times S_1\times S_2)^N$ for $P$. Define $t_{ab}=1$ exactly when every set bit $k<n$ of $b$ implies a set bit $n-1-k$ of $a$; then $v^A(u)_a$ is the parity of $\sum_hu_ht_{ha}$, and $v^P(u)_a$ is the parity of $\sum_hu_ht_{ah}$. With

$$F_{r,i}=\operatorname{Re}\operatorname{tr} \sqrt{\sqrt{\Sigma_{r,i}^{\text{false}}}\Sigma_{r,i}^{\text{true}}\sqrt{\Sigma_{r,i}^{\text{false}}}},$$

where roots use continuous functional calculus, the defined set consists exactly of indices $i<N$ satisfying both $2^{-N^\beta}\le F_{A,i}$ and $2^{-N^\beta}\le F_{P,i}$; equality with the threshold is included. No isometry or normalization condition on the data is imposed, $\beta$ is arbitrary, $n=0$ is included, and the finite types may be empty.

QAlgorithms.Papers.Independent.Intakethird100.P74.keyRate

For finite types $B,E,S_1,S_2$, with decidable equality as required, arbitrary data $d=(V,\psi)$, any $\beta\in\mathbb R$, and any $n\in\mathbb N$, let $N=2^n$, represent Boolean values by $0,1$, and define

$$\Psi_z(b,e,s,t)=\sum_{a\in\{0,1\}}V_{(b,e,t),a}\psi_z(a,s), \qquad W_B(z)_{b,b'}=\sum_{e,s,t}\Psi_z(b,e,s,t)\overline{\Psi_z(b',e,s,t)},$$ $$W_P(x)_{(z,b,s,t),(z',b',s',t')} =\frac{(-1)^{x(z+z')}}2 \sum_e\Psi_z(b,e,s,t)\overline{\Psi_{z'}(b',e,s',t')}.$$

The latter matrices are indexed by $\{0,1\}\times B\times S_1\times S_2$. Let $G_{rj}=1$ exactly when, for every $k<n$, a $1$ in binary position $k$ of $j$ implies a $1$ in position $n-1-k$ of $r$, and otherwise let $G_{rj}=0$. Set $E_0(u)_j=\sum_r u_rG_{rj}\pmod2$ and $E_1(u)_j=\sum_r u_rG_{jr}\pmod2$. For $J_i^0=\{j:j<i\}$ and $J_i^1=\{j:i<j\}$, define

$$S_i^\varepsilon(W,b)_{(v,y),(w,y')} = \begin{cases} 2^{-(N-1)} \displaystyle\sum_{\substack{u\in\{0,1\}^N\\u_i=b,\ u|_{J_i^\varepsilon}=v}} \prod_{j<N}W(E_\varepsilon(u)_j)_{y_j,y'_j},&v=w,\\ 0,&v\ne w, \end{cases}$$

where $v,w$ assign bits to $J_i^\varepsilon$, and $y,y'$ are output strings of $W$. With

$$F(A,B)=\operatorname{Re}\operatorname{tr}\sqrt{\sqrt A\,B\,\sqrt A}, \quad D=\{i:F(S_i^0(W_B,0),S_i^0(W_B,1))<2^{-N^\beta}\}, \quad P=\{i:F(S_i^1(W_P,0),S_i^1(W_P,1))<2^{-N^\beta}\},$$

using continuous functional calculus for matrix square roots, the definition returns

$$\frac{|\{0,\ldots,N-1\}\setminus(D\cup P)|}{N}.$$

No validity assumption on $V,\psi$, or restriction on $\beta$, is part of this definition. The case $n=0$ is included: there is one index, no side bits, and denominator $1$. An empty set in the numerator gives rate $0$.

QAlgorithms.Papers.Independent.Intakethird100.P74.netRate

For finite types $B,E,S_1,S_2$, with decidable equality as required, arbitrary wiretap data $d=(V,\psi)$, any $\beta\in\mathbb R$, and any $n\in\mathbb N$, put $N=2^n$ and identify Boolean values with $0,1$. Here $V$ has entries $V_{(b,e,t),a}$, and $\psi_z$ has entries $\psi_z(a,s)$; no isometry or normalization assumption is imposed on these data. Define

$$\Psi_z(b,e,s,t)=\sum_{a\in\{0,1\}}V_{(b,e,t),a}\psi_z(a,s), \qquad W_B(z)_{b,b'}=\sum_{e,s,t}\Psi_z(b,e,s,t)\overline{\Psi_z(b',e,s,t)}.$$

On the alphabet $O=\{0,1\}\times B\times S_1\times S_2$, define

$$W_P(x)_{(z,b,s,t),(z',b',s',t')} =\frac{(-1)^{x(z+z')}}2 \sum_e\Psi_z(b,e,s,t)\overline{\Psi_{z'}(b',e,s',t')}.$$

Let $G_{rj}\in\{0,1\}$, for $0\le r,j<N$, equal $1$ exactly when every binary digit $k<n$ of $j$ that equals $1$ has the binary digit $n-1-k$ of $r$ equal to $1$. For a bit string $u$, set $E_0(u)_j=\sum_r u_rG_{rj}\pmod2$ and $E_1(u)_j=\sum_r u_rG_{jr}\pmod2$. For either $\varepsilon=0,1$, let $J_i^0=\{j:j<i\}$, $J_i^1=\{j:i<j\}$, and define the matrices

$$S_i^\varepsilon(W,b)_{(v,y),(w,y')} = \begin{cases} 2^{-(N-1)} \displaystyle\sum_{\substack{u\in\{0,1\}^N\\u_i=b,\ u|_{J_i^\varepsilon}=v}} \prod_{j<N}W(E_\varepsilon(u)_j)_{y_j,y'_j},&v=w,\\ 0,&v\ne w. \end{cases}$$

Here $v,w$ are assignments on $J_i^\varepsilon$, and $y,y'$ are $N$-tuples of output symbols of $W$. Write

$$F(A,B)=\operatorname{Re}\operatorname{tr} \sqrt{\sqrt A\,B\,\sqrt A},$$

where matrix square roots use continuous functional calculus. Define

$$D=\{i:F(S_i^0(W_B,0),S_i^0(W_B,1))<2^{-N^\beta}\}, \qquad P=\{i:F(S_i^1(W_P,0),S_i^1(W_P,1))<2^{-N^\beta}\}.$$

The definition returns

$$\frac{|D\cap P|-|\{0,\ldots,N-1\}\setminus(D\cup P)|}{N}.$$

Thus the numerator subtracts the number of indices failing both strict tests from the number passing both. The definition includes $n=0$, when $N=1$, all side-index sets are empty, and the denominator is $1$; the returned real number is not required to be nonnegative.

QAlgorithms.Papers.Independent.Intakethird100.P74.phaseBob

For index types $B,E,S_1,S_2$, with $E$ finite, a datum $d=(V,\psi)$, and a Boolean $x$, this definition gives a complex square matrix indexed by $\{\mathrm{false},\mathrm{true}\}\times B\times S_1\times S_2$. For $r=(z,b,s_1,s_2)$ and $r'=(z',b',s'_1,s'_2)$, its entries are

$$(\rho^{\mathrm{phase}}_x)_{r,r'} =\frac{\sigma(x,z)\sigma(x,z')}{2} \sum_{e\in E}\sum_{a,a'\in\{\mathrm{false},\mathrm{true}\}} V_{(b,e,s_2),a}\psi_z(a,s_1) \overline{V_{(b',e,s'_2),a'}\psi_{z'}(a',s'_1)},$$

where $\sigma(x,z)=-1$ exactly when both Booleans are true, and is $1$ otherwise. No validity assumption is required; if $E$ is empty, the matrix is zero.

QAlgorithms.Papers.Independent.Intakethird100.P74.phaseGoodIndices

Let $B,E,S_1,S_2$ be finite types, with decidable equality on $B,S_1,S_2$, and let $d$ consist of an arbitrary matrix $V\in\mathbb C^{(B\times E\times S_2)\times\{\text{false},\text{true}\}}$ and arbitrary vectors $\psi_z\in\mathbb C^{\{\text{false},\text{true}\}\times S_1}$. For real $\beta$ and natural $n$, put $N=2^n$, $O=\{\text{false},\text{true}\}\times B\times S_1\times S_2$, and

$$f_z(b,e,s,t)=\sum_aV_{(b,e,t),a}\psi_z(a,s),\qquad W_x((z,b,s,t),(z',b',s',t')) =\frac{\chi(x,z)\chi(x,z')}{2} \sum_e f_z(b,e,s,t)\overline{f_{z'}(b',e,s',t')},$$

where the sum over $a$ is over Booleans and $\chi(x,z)=-1$ if both $x,z$ are true, and $1$ otherwise. For $i<N$, set $S_i=\{j:i<j<N\}$ and

$$\Sigma_i^b\bigl((s,y),(s',y')\bigr) =\mathbf1_{\{s=s'\}}\,2^{-(N-1)} \sum_{\substack{u\in\{\text{false},\text{true}\}^N\\u_i=b,\ u|_{S_i}=s}} \prod_{a=0}^{N-1}W_{v(u)_a}(y_a,y'_a),$$

where $y,y'\in O^N$, and $v(u)_a$ is the parity of $\sum_hu_ht_{ah}$, with $t_{ah}=1$ exactly when every set bit $k<n$ of $h$ implies a set bit $n-1-k$ of $a$. The defined set consists of precisely those $i<N$ for which

$$\operatorname{Re}\operatorname{tr} \sqrt{\sqrt{\Sigma_i^{\text{false}}}\Sigma_i^{\text{true}}\sqrt{\Sigma_i^{\text{false}}}} <2^{-N^\beta},$$

with matrix roots interpreted by continuous functional calculus. No isometry or normalization condition on $d$ is assumed; $\beta$ is unrestricted, $n=0$ is allowed, and the finite types need not be nonempty.

QAlgorithms.Papers.Independent.Intakethird100.P74.phaseVector

For arbitrary index types $B,E,S_1,S_2$, a datum $d=(V,\psi)$, and a Boolean $x$, this definition gives a complex vector indexed by $(\{\mathrm{false},\mathrm{true}\}\times B\times S_1\times S_2)\times E$, with coordinate

$$F_x((z,b,s_1,s_2),e) =\frac{\sigma(x,z)}{\sqrt2} \sum_{a\in\{\mathrm{false},\mathrm{true}\}} V_{(b,e,s_2),a}\psi_z(a,s_1), \qquad \sigma(x,z)= \begin{cases}-1&x=z=\mathrm{true},\\1&\text{otherwise}.\end{cases}$$

No validity or normalization assumption on $d$ is required.

QAlgorithms.Papers.Independent.Intakethird100.P74.polarEncode

For every natural number $n$, Boolean $r$, and Boolean vector $u$ of length $N=2^n$, this defines a Boolean vector $v$ of length $N$. For $0\le a,b<N$, let $t_{ab}\in\{0,1\}$ equal $1$ exactly when every set bit in position $k<n$ of $b$ corresponds to a set bit in position $n-1-k$ of $a$. Interpreting false and true as $0$ and $1$, respectively, the output is specified by

$$v_j=\text{true} \quad\Longleftrightarrow\quad \begin{cases} \displaystyle\sum_{i=0}^{N-1}u_i\,t_{ji}\equiv1\pmod2,&r=\text{true},\\[2mm] \displaystyle\sum_{i=0}^{N-1}u_i\,t_{ij}\equiv1\pmod2,&r=\text{false}. \end{cases}$$

Both choices of $r$ are allowed. When $n=0$, $N=1$, the bit condition defining $t_{00}$ is vacuous, and the output equals the one-coordinate input.

QAlgorithms.Papers.Independent.Intakethird100.P74.polarEntry

For every natural number $n$ and integers $0\le i,j<2^n$, this defines a Boolean that is true exactly when, for every $k\in\{0,\ldots,n-1\}$, a set bit in position $k$ of $j$ implies a set bit in position $n-1-k$ of $i$, where bit position $0$ is the least significant position. The subtraction is natural-number subtraction; these bounds on $k$ ensure that $n-1-k$ is the indicated reflected position. When $n=0$, the only possible indices are $i=j=0$, the condition has no instances, and the result is true.

QAlgorithms.Papers.Independent.Intakethird100.P74.polarSideIndices

For every natural number $n$, Boolean $r$, and index $0\le i<2^n$, this defines the type of indices $j\in\{0,\ldots,2^n-1\}$ satisfying $i<j$ when $r=\text{true}$, and satisfying $j<i$ when $r=\text{false}$. The inequalities are strict, so $i$ itself is excluded. This type is empty when $r=\text{false}$ and $i=0$, or when $r=\text{true}$ and $i=2^n-1$; in particular it is empty for both choices when $n=0$.

QAlgorithms.Papers.Independent.Intakethird100.P74.privateIndices

For finite types $B,E,S_1,S_2$, with decidable equality on $B,S_1,S_2$, arbitrary data $d=(V,\psi)$ consisting of $V\in\mathbb C^{(B\times E\times S_2)\times\{\text{false},\text{true}\}}$ and vectors $\psi_z\in\mathbb C^{\{\text{false},\text{true}\}\times S_1}$, real $\beta$, and natural $n$, put $N=2^n$ and define $f_z(b,e,s,t)=\sum_aV_{(b,e,t),a}\psi_z(a,s)$, summing over Boolean $a$. Define two matrix families by

$$W_z^{A}(b,b')=\sum_{e,s,t}f_z(b,e,s,t)\overline{f_z(b',e,s,t)},\qquad W_x^{P}((z,b,s,t),(z',b',s',t')) =\frac{\chi(x,z)\chi(x,z')}{2} \sum_e f_z(b,e,s,t)\overline{f_{z'}(b',e,s',t')},$$

where $\chi(x,z)=-1$ when both arguments are true and is $1$ otherwise. For $r\in\{A,P\}$, take $S_i^A=\{j:j<i\}$, $S_i^P=\{j:i<j<N\}$, and define matrices

$$\Sigma_{r,i}^{b}\bigl((s,y),(s',y')\bigr) =\mathbf1_{\{s=s'\}}\,2^{-(N-1)} \sum_{\substack{u\in\{\text{false},\text{true}\}^N\\u_i=b,\ u|_{S_i^r}=s}} \prod_{a=0}^{N-1}W^r_{v^r(u)_a}(y_a,y'_a).$$

Here $y$ ranges over $B^N$ for $r=A$ and over $(\{\text{false},\text{true}\}\times B\times S_1\times S_2)^N$ for $r=P$; writing $t_{ab}=1$ exactly when each set bit $k<n$ of $b$ implies a set bit $n-1-k$ of $a$, $v^A(u)_a$ is the parity of $\sum_hu_ht_{ha}$, and $v^P(u)_a$ is the parity of $\sum_hu_ht_{ah}$. Put

$$F_{r,i}=\operatorname{Re}\operatorname{tr} \sqrt{\sqrt{\Sigma_{r,i}^{\text{false}}}\Sigma_{r,i}^{\text{true}}\sqrt{\Sigma_{r,i}^{\text{false}}}},$$

using continuous functional calculus for roots. This declaration defines precisely the indices $i<N$ satisfying both $F_{A,i}<2^{-N^\beta}$ and $F_{P,i}<2^{-N^\beta}$. No validity condition on $d$, restriction on $\beta$, or positivity of $n$ is required; $n=0$ gives $N=1$, and empty index types are permitted.

QAlgorithms.Papers.Independent.Intakethird100.P74.privateMessageEveState

For finite types $B,E,S_1,S_2$, with decidable equality as required, arbitrary data $d=(V,\psi)$, any $\beta\in\mathbb R$, and $n\in\mathbb N$, put $N=2^n$ and define

$$\Psi_z(b,e,s,t)=\sum_{a\in\{0,1\}}V_{(b,e,t),a}\psi_z(a,s),$$ $$W_B(z)_{b,b'}=\sum_{e,s,t}\Psi_z(b,e,s,t)\overline{\Psi_z(b',e,s,t)}, \qquad W_E(z)_{e,e'}=\sum_{b,s,t}\Psi_z(b,e,s,t)\overline{\Psi_z(b,e',s,t)},$$ $$W_P(x)_{(z,b,s,t),(z',b',s',t')} =\frac{(-1)^{x(z+z')}}2 \sum_e\Psi_z(b,e,s,t)\overline{\Psi_{z'}(b',e,s',t')}.$$

Let $G_{rj}=1$ exactly when every binary position $k<n$ at which $j$ has digit $1$ has digit $1$ at position $n-1-k$ of $r$, and otherwise let it be $0$. Set $E_0(u)_j=\sum_r u_rG_{rj}\pmod2$, $E_1(u)_j=\sum_r u_rG_{jr}\pmod2$, $J_i^0=\{j:j<i\}$, and $J_i^1=\{j:i<j\}$. Define

$$S_i^\varepsilon(W,b)_{(v,y),(w,y')}= \begin{cases} 2^{-(N-1)} \displaystyle\sum_{\substack{u\in\{0,1\}^N\\u_i=b,\ u|_{J_i^\varepsilon}=v}} \prod_{j<N}W(E_\varepsilon(u)_j)_{y_j,y'_j},&v=w,\\ 0,&v\ne w, \end{cases}$$

where $v,w$ are assignments on the indicated side-index set and $y,y'$ are output strings of $W$. With $F(A,B)=\operatorname{Re}\operatorname{tr}\sqrt{\sqrt A\,B\,\sqrt A}$, using continuous functional calculus, let

$$D=\{i:F(S_i^0(W_B,0),S_i^0(W_B,1))<2^{-N^\beta}\}, \quad P=\{i:F(S_i^1(W_P,0),S_i^1(W_P,1))<2^{-N^\beta}\}, \quad I=D\cap P.$$

For every message $m:I\to\{0,1\}$, the definition gives a complex matrix on $E^N$ with entries

$$\rho_m(e,e') = 2^{|I|-N} \sum_{\substack{u\in\{0,1\}^N\\u|_I=m}} \prod_{j<N}W_E(E_0(u)_j)_{e_j,e'_j}.$$

No validity assumption on $d$ is imposed, so the declaration does not assert that this matrix has trace $1$. If $I$ is empty, there is one empty message and the formula averages over all $2^N$ strings; if $I$ contains every index, the sum has one term and prefactor $1$. The case $n=0$, when $N=1$, is included.

QAlgorithms.Papers.Independent.Intakethird100.P74.privateMessageLeakageBits

For finite index types $B,E,S_1,S_2$, with decidable equality as required by the constructions, let $d=(V,\psi)$ consist of a complex matrix $V$ with rows indexed by $B\times E\times S_2$ and columns indexed by $\{0,1\}$, and vectors $\psi_z\in\mathbb C^{\{0,1\}\times S_1}$ for $z\in\{0,1\}$. For any real $\beta$ and natural number $n$, put $N=2^n$ and $I=\{0,\ldots,N-1\}$. Identify Boolean values with $0,1$, and define the binary matrix $G$ by $G_{ij}=1$ precisely when, for every $k<n$, a $1$ in bit $k$ of $j$ implies a $1$ in bit $n-1-k$ of $i$. Define

$$e_-(u)_j=\sum_{i\in I}u_iG_{ij}\pmod2,\qquad e_+(u)_j=\sum_{i\in I}u_iG_{ji}\pmod2.$$

Set

$$s_z(b,e,s,t)=\sum_{a\in\{0,1\}}V_{(b,e,t),a}\psi_z(a,s),\qquad \varphi_x((z,b,s,t),e)=2^{-1/2}(-1)^{xz}s_z(b,e,s,t),$$

and let $W^A_z=\operatorname{Tr}_{E,S_1,S_2}(s_zs_z^*)$, $W^E_z=\operatorname{Tr}_{B,S_1,S_2}(s_zs_z^*)$, and $W^P_x=\operatorname{Tr}_E(\varphi_x\varphi_x^*)$. For a binary matrix-valued family $W$, define its split matrices $\Sigma^{W,\pm}_{i,b}$, whose indices are pairs $(h,y)$, by

$$[\Sigma^{W,\pm}_{i,b}]_{(h,y),(h',y')} = \begin{cases} 2^{-(N-1)} \displaystyle\sum_{\substack{u\in\{0,1\}^I\\u_i=b,\ u|_{J_i^\pm}=h}} \prod_{\ell\in I}W_{e_\pm(u)_\ell}(y_\ell,y'_\ell),&h=h',\\ 0,&h\ne h', \end{cases} \qquad J_i^-=\{j:j<i\},\quad J_i^+=\{j:i<j\}.$$

Here the minus sign uses $e_-$, and the plus sign uses $e_+$. Write $F(R,S)=\operatorname{Re}\operatorname{tr}\sqrt{\sqrt R\,S\sqrt R}$, with matrix square roots given by real square-root continuous functional calculus, and put

$$D=\{i:F(\Sigma^{W^A,-}_{i,0},\Sigma^{W^A,-}_{i,1})<2^{-N^\beta}\},\quad P=\{i:F(\Sigma^{W^P,+}_{i,0},\Sigma^{W^P,+}_{i,1})<2^{-N^\beta}\},\quad A=D\cap P.$$

For every assignment $m:A\to\{0,1\}$, define

$$\rho_m=2^{|A|-N} \sum_{\substack{u\in\{0,1\}^I\\u|_A=m}} \bigotimes_{\ell\in I}W^E_{e_-(u)_\ell}.$$

The declared real number is

$$S_2\!\left(2^{-|A|}\sum_m\rho_m\right) -2^{-|A|}\sum_m S_2(\rho_m), \qquad S_2(R)=-\operatorname{Re}\operatorname{tr} \bigl(\operatorname{cfc}[r\mapsto r\log_2 r](R)\bigr).$$

There is no validity assumption on $d$, no restriction on $\beta$, and $n=0$ is included. The set $A$ may be empty; then there is one assignment $m$, and this expression is zero.

QAlgorithms.Papers.Independent.Intakethird100.P74.purifiedWiretapSignal

For arbitrary index types $B,E,S_1,S_2$, a datum $d=(V,\psi)$, and a Boolean $z$, this definition gives the complex vector on $B\times E\times S_1\times S_2$ whose coordinate at $(b,e,s_1,s_2)$ is

$$\sum_{a\in\{\mathrm{false},\mathrm{true}\}} V_{(b,e,s_2),a}\,\psi_z(a,s_1).$$

No validity or normalization assumption on $d$ is required.

QAlgorithms.Papers.Independent.Intakethird100.P74.randomIndices

For finite types $B,E,S_1,S_2$, with decidable equality on $B,S_1,S_2$, arbitrary data $V\in\mathbb C^{(B\times E\times S_2)\times\{\text{false},\text{true}\}}$ and $\psi_z\in\mathbb C^{\{\text{false},\text{true}\}\times S_1}$, real $\beta$, and natural $n$, put $N=2^n$, $f_z(b,e,s,t)=\sum_aV_{(b,e,t),a}\psi_z(a,s)$, summing over Boolean $a$, and define

$$W_z^{A}(b,b')=\sum_{e,s,t}f_z(b,e,s,t)\overline{f_z(b',e,s,t)},\qquad W_x^{P}((z,b,s,t),(z',b',s',t')) =\frac{\chi(x,z)\chi(x,z')}{2} \sum_e f_z(b,e,s,t)\overline{f_{z'}(b',e,s',t')},$$

where $\chi(x,z)=-1$ if both arguments are true and $1$ otherwise. Set $S_i^A=\{j:j<i\}$, $S_i^P=\{j:i<j<N\}$, and, for $r=A,P$, define

$$\Sigma_{r,i}^{b}\bigl((s,y),(s',y')\bigr) =\mathbf1_{\{s=s'\}}\,2^{-(N-1)} \sum_{\substack{u\in\{\text{false},\text{true}\}^N\\u_i=b,\ u|_{S_i^r}=s}} \prod_{a=0}^{N-1}W^r_{v^r(u)_a}(y_a,y'_a).$$

Here $y\in B^N$ for $A$, while $y\in(\{\text{false},\text{true}\}\times B\times S_1\times S_2)^N$ for $P$. For $t_{ab}=1$ exactly when each set bit $k<n$ of $b$ implies a set bit $n-1-k$ of $a$, define $v^A(u)_a$ as the parity of $\sum_hu_ht_{ha}$ and $v^P(u)_a$ as the parity of $\sum_hu_ht_{ah}$. Write

$$F_{r,i}=\operatorname{Re}\operatorname{tr} \sqrt{\sqrt{\Sigma_{r,i}^{\text{false}}}\Sigma_{r,i}^{\text{true}}\sqrt{\Sigma_{r,i}^{\text{false}}}},$$

with matrix roots formed by continuous functional calculus. This defines exactly the indices $i<N$ for which $F_{A,i}<2^{-N^\beta}$ and $2^{-N^\beta}\le F_{P,i}$. There is no validity assumption on the data and no restriction on $\beta$; $n=0$, giving $N=1$, and empty finite index types are allowed.

QAlgorithms.Papers.Independent.Intakethird100.P74.referenceEncoder

For types $B,E,S_1,S_2$, any data $d:\mathrm{WiretapData}(B,E,S_1,S_2)$, and any $n\in\mathbb N$, put $N=2^n$. This defines a complex matrix whose row and column indices are strings in $(\{0,1\}\times B\times S_1\times S_2)^N$. Let $G_{rj}=1$ exactly when, for every $k<n$, a $1$ in binary position $k$ of $j$ implies a $1$ in position $n-1-k$ of $r$, and otherwise let $G_{rj}=0$. For row $y_i=(a_i,b_i,s_i,t_i)$ and column $z_i=(c_i,b'_i,s'_i,t'_i)$, the entry is

$$R_{y,z}= \begin{cases} 1,& (b_i,s_i,t_i)=(b'_i,s'_i,t'_i)\text{ for every }i, \quad a_j=\displaystyle\sum_{r<N}c_rG_{rj}\pmod2\text{ for every }j,\\ 0,&\text{otherwise}. \end{cases}$$

The entries of $V$ and $\psi$ in $d$, and the type $E$, do not enter this formula. No validity hypothesis on $d$ is required. For $n=0$, $N=1$ and $G_{00}=1$, so this is the identity matrix on the indicated one-coordinate strings.

QAlgorithms.Papers.Independent.Intakethird100.P74.reliabilityBound

For finite types $B,E,S_1,S_2$, with decidable equality as required, arbitrary data $d=(V,\psi)$, any $\beta\in\mathbb R$, and $n\in\mathbb N$, let $N=2^n$, and define

$$\Psi_z(b,e,s,t)=\sum_{a\in\{0,1\}}V_{(b,e,t),a}\psi_z(a,s), \qquad W(z)_{b,b'}=\sum_{e,s,t}\Psi_z(b,e,s,t)\overline{\Psi_z(b',e,s,t)}.$$

Let $G_{rj}=1$ exactly when every $1$ in binary position $k<n$ of $j$ implies a $1$ in position $n-1-k$ of $r$, taking $0$ otherwise, and put $c(u)_j=\sum_r u_rG_{rj}\pmod2$. For assignments $v,w$ on $\{j:j<i\}$ and $y,y'\in B^N$, define

$$S_i(b)_{(v,y),(w,y')}= \begin{cases} 2^{-(N-1)} \displaystyle\sum_{\substack{u\in\{0,1\}^N\\u_i=b,\ u|_{\{j:j<i\}}=v}} \prod_{r<N}W(c(u)_r)_{y_r,y'_r},&v=w,\\ 0,&v\ne w. \end{cases}$$

Writing $F_i=\operatorname{Re}\operatorname{tr}\sqrt{\sqrt{S_i(0)}S_i(1)\sqrt{S_i(0)}}$, with matrix square roots defined by continuous functional calculus, and $D=\{i:F_i<2^{-N^\beta}\}$, the definition returns

$$\sqrt{\,2\sum_{i\in D}F_i\,}.$$

This is a defined real number; the declaration itself states no inequality involving a decoder. No validity hypothesis on $d$ or restriction on $\beta$ is imposed. An empty $D$ gives $0$, and $n=0$ is included, with one index and no preceding bits. The outer square root is the total real square-root function, which returns $0$ on negative arguments.

QAlgorithms.Papers.Independent.Intakethird100.P74.splitOutput

For any finite type $O$ with decidable equality, natural number $n$, Boolean $r$, arbitrary family of complex matrices $W_b\in\mathbb C^{O\times O}$ indexed by Booleans $b$, index $0\le i<N=2^n$, and Boolean $b$, this defines a matrix indexed by pairs $(s,y)$, where $y\in O^N$ and $s$ is a Boolean assignment on $S_i^r=\{j:i<j<N\}$ if $r=\text{true}$, or $S_i^r=\{j:0\le j<i\}$ otherwise. Define $t_{ab}\in\{0,1\}$ to be $1$ exactly when every set bit $k<n$ of $b$ corresponds to a set bit $n-1-k$ of $a$, and define $v^r(u)_a$ as the parity of $\sum_hu_h t_{ah}$ for $r=\text{true}$, or $\sum_hu_h t_{ha}$ otherwise, interpreting Boolean values as $0,1$. Its entries are

$$\Sigma_i^{r,b}\bigl((s,y),(s',y')\bigr)= \begin{cases} \displaystyle 2^{-(N-1)} \sum_{\substack{u\in\{\text{false},\text{true}\}^N\\ u_i=b,\ u_j=s_j\ (j\in S_i^r)}} \prod_{a=0}^{N-1}W_{v^r(u)_a}(y_a,y'_a),&s=s',\\[3mm] 0,&s\ne s'. \end{cases}$$

There is no positivity, trace, or normalization hypothesis on $W$. When $n=0$, this reduces, under the unique empty side assignment and one-coordinate output indexing, to $W_b$. The type $O$ may be empty, in which case the matrix has an empty index type.

QAlgorithms.Papers.Independent.Intakethird100.P74.symmetricPrivateInformation

For finite index types $B,E,S_1,S_2$, with decidable equality on $B,E$, and a datum $d=(V,\psi)$, define, for each Boolean $z$,

$$R_z(a,a')=\sum_{s_1\in S_1}\psi_z(a,s_1)\overline{\psi_z(a',s_1)}, \qquad C_z=VR_zV^\dagger,$$

and define matrices $B_z,E_z$ by

$$B_z(b,b')=\sum_{e\in E}\sum_{s_2\in S_2}C_z((b,e,s_2),(b',e,s_2)), \qquad E_z(e,f)=\sum_{b\in B}\sum_{s_2\in S_2}C_z((b,e,s_2),(b,f,s_2)).$$

With $S(M)=-\operatorname{Re}\operatorname{tr}(\operatorname{cfc}[t\mapsto t\log_2 t](M))$, the definition gives

$$S\!\left(\frac{B_{\mathrm{false}}+B_{\mathrm{true}}}{2}\right) -\frac{S(B_{\mathrm{false}})+S(B_{\mathrm{true}})}2 -S\!\left(\frac{E_{\mathrm{false}}+E_{\mathrm{true}}}{2}\right) +\frac{S(E_{\mathrm{false}})+S(E_{\mathrm{true}})}2.$$

No validity assumption on $d$ is imposed; empty index types are permitted, with empty sums equal to zero.

QAlgorithms.Papers.Independent.Intakethird100.P74.uniformHolevo

For finite types $L,O$, with decidable equality on $O$, and any family $W_\ell$ of complex $O$-indexed square matrices, let

$$S(M)=-\operatorname{Re}\operatorname{tr} \!\left(\operatorname{cfc}[t\mapsto t\log_2 t](M)\right),$$

where $\operatorname{cfc}$ denotes continuous functional calculus. This definition gives the real number

$$S\!\left(|L|^{-1}\sum_{\ell\in L}W_\ell\right) -|L|^{-1}\sum_{\ell\in L}S(W_\ell).$$

No positivity, trace-one, or nonemptiness assumption is imposed. Inverses are total, so $0^{-1}=0$; the value is zero if $L$ or $O$ is empty.