Definitions for Polar codes for classical-quantum channels

QAlgorithms.Papers.Independent.Intakethird100.P14.BinaryAchievableRate

For any type $I$, any $W:\mathbb Z_2\to\mathbb C^{I\times I}$, and any nonnegative real $R$, this proposition means that for every real $e>0$ and every real $d>0$, there is a natural number $N_0>0$ such that for every natural $N\ge N_0$ there exist $M>0$, encoding words $c_m\in\mathbb Z_2^N$, and positive bounded operators $D_m$ on $\ell^2(I^N;\mathbb C)$ summing to the identity, for which

$$R-d\le\frac{\log_2 M}{N}, \qquad 1-\frac1M\sum_{m<M}\operatorname{Re} \sum'_{x\in I^N}(D_mO_{X_m}e_x)_x\le e, \quad (X_m)_{xy}=\prod_{t<N}W(c_m(t))_{x_t,y_t}.$$

Here $O_X$ is a chosen bounded complex linear operator having coefficient array $X$, if one exists, and zero otherwise; $e_x$ is the coordinate unit vector, and a nonsummable complex sum is assigned zero. Codes may depend on $e,d,N$, and their encoding functions need not be injective. No density or countability assumption on $W$ or $I$ is imposed. The quantifier over block lengths requires codes at every sufficiently large integer length, with no requirement at length zero.

QAlgorithms.Papers.Independent.Intakethird100.P14.BinaryBlockCode.error

For any type $I$, $N\in\mathbb N$, a block code with $M>0$ messages, binary words $c_m\in\mathbb Z_2^N$, and positive bounded decoding operators $D_m$ on $\ell^2(I^N;\mathbb C)$ summing to the identity, and any $W:\mathbb Z_2\to\mathbb C^{I\times I}$, this defines

$$1-\frac1M\sum_{m=0}^{M-1} \operatorname{Re}\sum'_{x\in I^N} \bigl(D_m O_{X_m}e_x\bigr)_x, \qquad (X_m)_{xy}=\prod_{t=0}^{N-1}W(c_m(t))_{x_t,y_t}.$$

For an array $X$, $O_X$ is a chosen bounded complex linear operator with $(O_Xe_y)_x=X_{xy}$, if such an operator exists, and is zero otherwise; $e_x$ is the coordinate unit vector in $\ell^2(I^N;\mathbb C)$. A nonsummable complex sum $\sum'$ has value zero. There is no assumption that $W$ consists of density arrays, and no assertion here that this real number lies in $[0,1]$. The case $N=0$ is included, with the product defining $X_m$ equal to one.

QAlgorithms.Papers.Independent.Intakethird100.P14.BinaryBlockCode

For any type $I$ and any $N\in\mathbb N$, a value of this structure consists of a natural number $M>0$, an encoding function assigning each message $m\in\{0,\ldots,M-1\}$ a word $c_m\in\mathbb Z_2^N$, and bounded complex linear operators $D_m$ on $\ell^2(I^N;\mathbb C)$, satisfying

$$D_m\ge0\quad\text{for every }m,\qquad \sum_{m=0}^{M-1}D_m=\mathrm{id}.$$

Here positivity is positivity of the bounded operator. The encoding function need not be injective. The structure imposes no channel or output-state data, and allows $N=0$ and arbitrary, possibly empty or uncountable, $I$; for $N=0$, the word types each have a single element.

QAlgorithms.Papers.Independent.Intakethird100.P14.Bit

$\mathrm{Bit}$ denotes the field $\mathbb Z/2\mathbb Z$, whose elements are $0$ and $1$.

QAlgorithms.Papers.Independent.Intakethird100.P14.EncodingGate.apply

For every $n\in\mathbb N$, an instruction $g$ of either kind described below, and a word $u:\{0,\ldots,2^n-1\}\to\mathbb Z/2\mathbb Z$, this defines the updated word. An XOR instruction with source $s$ and target $t$ replaces coordinate $t$ by $u_t+u_s$ and leaves all other coordinates unchanged. A swap instruction with indices $a,b$ first replaces coordinate $a$ by the original value $u_b$, then replaces coordinate $b$ by the original value $u_a$. Repeated indices are allowed: XOR with $s=t$ sets that coordinate to $0$, while swap with $a=b$ leaves the word unchanged. These rules also apply when $n=0$, when the word has one coordinate.

QAlgorithms.Papers.Independent.Intakethird100.P14.EncodingGate

For each $n\in\mathbb N$, this inductive type has two kinds of elements: an XOR instruction carrying a source and a target in $\{0,\ldots,2^n-1\}$, and a swap instruction carrying two indices in that same set. Neither constructor requires its two indices to be distinct. When $n=0$, the sole index is $0$, so both kinds of instruction still exist with both indices equal to $0$.

QAlgorithms.Papers.Independent.Intakethird100.P14.Frozen

For every natural number $n$ and finite subset $A$ of the $N=2^n$ indices $\{0,\ldots,N-1\}$, this denotes the type of all functions from the complement of $A$ among those indices to $\mathbb Z/2\mathbb Z$. Thus it assigns one binary value to each index outside $A$ and has $2^{N-|A|}$ elements. If $A$ contains all indices, it consists of the single empty function. When $n=0$, there is one available index.

QAlgorithms.Papers.Independent.Intakethird100.P14.InformationWord

For every natural number $n$ and finite subset $A$ of the $2^n$ indices $\{0,\ldots,2^n-1\}$, this denotes the type of all functions $A\to\mathbb Z/2\mathbb Z$: a word assigning one binary value to each index belonging to $A$. It has $2^{|A|}$ elements. In particular, if $A=\varnothing$, it contains exactly the empty function. The case $n=0$ is included, with one available index.

QAlgorithms.Papers.Independent.Intakethird100.P14.IsBinaryCqChannel

For any type $I$ and any map $W:\mathbb Z/2\mathbb Z\to\mathbb C^{I\times I}$, this predicate requires each array $X=W(b)$, for every $b\in\mathbb Z/2\mathbb Z$, to satisfy all of the following: there exist sequences $u_n,v_n\in\ell^2(I;\mathbb C)$ such that $\sum_n\|u_n\|\|v_n\|$ is summable and $X_{ij}=\sum_{n=0}^{\infty}u_n(i)\overline{v_n(j)}$ for every $i,j\in I$; for every finite subset $s\subseteq I$ and every function $z:I\to\mathbb C$, the number $\sum_{i\in s}\sum_{j\in s}\overline{z(i)}X_{ij}z(j)$ has imaginary part zero and nonnegative real part; and the family $(\operatorname{Re}X_{ii})_{i\in I}$ is summable with sum $1$. No countability or nonemptiness assumption on $I$ is supplied; when $I$ is empty, the required diagonal sum cannot equal $1$.

QAlgorithms.Papers.Independent.Intakethird100.P14.OutputCoefficients

For any type $I$, $\mathrm{OutputCoefficients}(I)$ is the space of all complex arrays $X=(X_{ij})_{i,j\in I}$. The index type may be empty or infinite; no boundedness, summability, positivity, or normalization condition is imposed.

QAlgorithms.Papers.Independent.Intakethird100.P14.PolarAchieves

For any type $I$, any $W:\mathbb Z_2\to\mathbb C^{I\times I}$, and any real $R$, this proposition asserts the existence, for every $n\in\mathbb N$, of a subset $A_n\subseteq\{0,\ldots,2^n-1\}$ with $|A_n|=\lfloor2^nR\rfloor_+$, such that every selected index has squared fidelity at most that of every unselected index, and the decoding error defined below is $o(2^{-\frac12(2^n)^\beta})$ as $n\to\infty$, for every real $\beta<\tfrac12$, including zero and negative $\beta$. To specify these quantities, put $N=2^n$, let $b_k(r)$ be bit $k$, set $\operatorname{rev}_n(r)=(\sum_{k<n}b_k(r)2^{n-1-k})\bmod N$, and define $G_{rt}=\prod_{k<n}K(b_k(\operatorname{rev}_n(r)),b_k(t))$ over $\mathbb Z_2$, with $K(a,0)=1,\ K(a,1)=a$. For $u\in\mathbb Z_2^N$, write $X_u(x,y)=\prod_{t<N}W((uG)_t)_{x_t,y_t}$. For index $i<N$, prefix $h\in\mathbb Z_2^i$, and bit $b$, let

$$F_i(h,b)=2^{-(N-i-1)} \sum_{\substack{u\in\mathbb Z_2^N\\u_{<i}=h,\ u_i=b}}X_u, \qquad V_i(b)_{(h,x),(h',y)} =\mathbf1_{\{h=h'\}}2^{-i}F_i(h,b)_{xy}.$$

For any array $X$, $O_X$ is a chosen bounded operator on the corresponding complex $\ell^2$ space with coefficients $X$, if one exists, and zero otherwise; $R(T)$ is a chosen positive bounded square root of $T$, if one exists, and zero otherwise; and $\operatorname{tr}_b(T)=\sum'_x(Te_x)_x$. The squared fidelity used for selection is

$$\mathcal F(V)= \left(\operatorname{Re}\operatorname{tr}_b R\!\left(R(O_{V(0)})O_{V(1)}R(O_{V(0)})\right)\right)^2.$$

For each $i,h$, let $P_i(h)$ be the orthogonal projection onto the closure of the complex span of all vectors $v$ satisfying

$$\bigl(R(O_{F_i(h,0)})-R(O_{F_i(h,1)})\bigr)v=av \quad\text{for some real }a<0.$$

For a full word $u$, define $Q_i(u)=1-P_i(u_{<i})$ when $i\in A_n,\ u_i=0$, $Q_i(u)=P_i(u_{<i})$ when $i\in A_n,\ u_i=1$, and $Q_i(u)=1$ otherwise. Put $K_u=Q_{N-1}(u)\cdots Q_0(u)$. The error in the little-$o$ assertion is

$$e_n=1-2^{-N}\sum_{u\in\mathbb Z_2^N} \operatorname{Re}\operatorname{tr}_b(K_u^*K_uO_{X_u}).$$

Thus the asymptotic condition means that for every $\beta<\tfrac12$ and every $c>0$, eventually $|e_n|\le c\,2^{-\frac12(2^n)^\beta}$. The natural-number floor $\lfloor\cdot\rfloor_+$ is zero for negative arguments, and no nonnegativity assumption on $R$, channel-validity assumption on $W$, or countability assumption on $I$ is included. The case $n=0$ and all zero-operator fallbacks are included; nonsummable complex sums defining $\operatorname{tr}_b$ are zero.

QAlgorithms.Papers.Independent.Intakethird100.P14.PolarRule

For any type $I$, arbitrary coefficient matrices $W(0),W(1)$ indexed by $I$, natural number $n$, real number $R$, and finite subset $A$ of the $N=2^n$ wire indices, this property means

$$|A|=\lfloor NR\rfloor_{\mathbb N} \quad\text{and}\quad \forall i\in A\ \forall j\notin A,\quad \mathcal F_i\le\mathcal F_j.$$

The natural-number floor is zero for a negative argument. The numbers $\mathcal F_i$ are defined as follows. With $F_{a,b}=1$ if $b=0$ and $F_{a,b}=a$ otherwise, set

$$G_{r,c}=\prod_{k=0}^{n-1}F_{\operatorname{bit}_k(\operatorname{rev}_n(r)),\,\operatorname{bit}_k(c)}, \qquad E(v)_c=\sum_rv_rG_{r,c}, \qquad \Gamma_v(x,y)=\prod_cW(E(v)_c)_{x_c,y_c},$$

where the transform uses arithmetic in $\mathbb Z/2\mathbb Z$, $\operatorname{rev}_n$ reverses $n$ binary digits, and digit indices start at the least significant digit. For a prefix $h$ of length $i$, bit $b$, and full word $v$, let $v^{i,h,b}$ use $h$ before $i$, $b$ at $i$, and $v$ after $i$, and put $V_{i,h,b}=2^{-N}\sum_v\Gamma_{v^{i,h,b}}$. Define two matrices on the label set

$$L_i=(\{0,\ldots,i-1\}\to\mathbb Z/2\mathbb Z) \times(\{0,\ldots,N-1\}\to I)$$

by

$$B_i(b)_{(h,x),(h',y)} =\begin{cases}2^{-i}V_{i,h,b}(x,y),&h=h',\\0,&h\ne h'.\end{cases}$$

For any matrix $X$, let $C(X)$ be a chosen bounded operator on the corresponding $\ell^2$ space realizing its coefficients if one exists, and zero otherwise; for a bounded operator $T$, let $R(T)$ be a chosen bounded positive square root if one exists, and zero otherwise. Writing $S_i=R(C(B_i(0)))$ and using standard coordinate vectors $e_\ell$, the value being compared is

$$\mathcal F_i= \left( \operatorname{Re}\sum_{\ell\in L_i} \bigl(R(S_i\,C(B_i(1))\,S_i)e_\ell\bigr)_\ell \right)^2.$$

The complex sum is totalized to zero if it is not summable. No density condition on $W$, countability condition on $I$, or range condition on $R$ is assumed. Ties in the comparison are allowed; its quantified part is vacuous when $A$ is empty or contains all wires. If $\lfloor NR\rfloor_{\mathbb N}>N$, the cardinality condition cannot hold. The case $n=0$ has one wire.

QAlgorithms.Papers.Independent.Intakethird100.P14.PolarWire

For every natural number $n$, this is the finite index type $\{0,1,\ldots,2^n-1\}$. In particular, when $n=0$, it contains the single index $0$.

QAlgorithms.Papers.Independent.Intakethird100.P14.PureOutputs

For any type $I$ and any function $W:\mathbb Z_2\to\mathbb C^{I\times I}$, this proposition means that for each $b\in\mathbb Z_2$ there exists $v\in\ell^2(I;\mathbb C)$ such that $\|v\|=1$ and

$$W(b)_{ij}=v_i\overline{v_j}\qquad(i,j\in I).$$

The vector may depend on $b$; it is not asserted to be unique. No countability or nonemptiness assumption on $I$ is supplied, although the required unit vectors cannot exist when $I$ is empty.

QAlgorithms.Papers.Independent.Intakethird100.P14.SplitLabel

For any type $I$, any $n\in\mathbb N$, and any index $0\le i<2^n$, this is an abbreviation for the set of pairs $(h,a)$, where $h:\{0,\ldots,i-1\}\to\mathbb F_2$ is a bit history and $a:\{0,\ldots,2^n-1\}\to I$ is an $I$-valued word. When $i=0$, the history has a unique empty value; when $n=0$, the index is necessarily $i=0$ and the $I$-valued word has length one. No finiteness, countability, or nonemptiness assumption is made on $I$.

QAlgorithms.Papers.Independent.Intakethird100.P14.basisKet

For any type $I$ and any $i\in I$, this defines the vector $e_i\in\ell^2(I;\mathbb C)$ whose coordinate at $i$ is $1$ and whose coordinates at every other index are $0$. Supplying $i$ requires an element of $I$; there is no such argument when $I$ is empty.

QAlgorithms.Papers.Independent.Intakethird100.P14.basisTrace

For any type $I$ and any bounded complex-linear operator $T$ on $\ell^2(I;\mathbb C)$, this defines the complex number $\sum_{i\in I}(Te_i)(i)$, where $e_i$ is $1$ at coordinate $i$ and $0$ elsewhere. This is the unconditional sum over $I$, with value $0$ when the family is not summable; summability is not assumed. For empty $I$, the sum is $0$.

QAlgorithms.Papers.Independent.Intakethird100.P14.binaryOperationalCapacity

For any type $I$ and any $W:\mathbb Z_2\to\mathbb C^{I\times I}$, this defines an extended nonnegative real number as the supremum of all nonnegative real $R$ satisfying the following condition: for every $e,d>0$, there exists $N_0\in\mathbb N$ with $N_0>0$ such that for every integer $N\ge N_0$ there are $M>0$, words $c_m\in\mathbb Z_2^N$, and positive bounded decoding operators $D_m$ on $\ell^2(I^N;\mathbb C)$ summing to the identity, such that

$$R-d\le\frac{\log_2M}{N}, \qquad 1-\frac1M\sum_{m<M}\operatorname{Re} \sum'_{x\in I^N}(D_mO_{X_m}e_x)_x\le e, \qquad (X_m)_{xy}=\prod_{t<N}W(c_m(t))_{x_t,y_t}.$$

Here $O_X$ is a chosen bounded complex linear operator with coefficient array $X$, if such an operator exists, and zero otherwise; $e_x$ is the coordinate unit vector, and a nonsummable complex sum is zero. The supremum is taken in $[0,\infty]$, so it is zero if no rate satisfies the condition and may be infinite. No density, countability, or nonemptiness assumption is imposed.

QAlgorithms.Papers.Independent.Intakethird100.P14.bitFiltration

For any type $\Omega$ equipped with a measurable space $m$, and any sequence of functions $B_k:\Omega\to\{\mathrm{false},\mathrm{true}\}$ that are each measurable for $m$ and the discrete measurable space on the Booleans, this constructs the filtration

$$\mathcal F_n=\sigma(B_0,\ldots,B_{n-1}).$$

Precisely, $\mathcal F_n$ is the supremum of the pullback measurable spaces along $B_k$, for $0\le k<n$. These measurable spaces increase with $n$ and are contained in $m$. In particular, $\mathcal F_0$ is the trivial measurable space. No probability measure or independence assumptions are included.

QAlgorithms.Papers.Independent.Intakethird100.P14.bitProjector

For any type $I$, any pair of complex matrices $W_b$ indexed by $I$, any $n\in\mathbb N$, index $0\le i<N=2^n$, history $h\in\mathbb F_2^i$, and bit $b\in\mathbb F_2$, this defines a bounded complex-linear operator on $\mathcal H=\ell^2(I^N;\mathbb C)$ as follows. For $d\in\mathbb F_2$ and $v\in\mathbb F_2^N$, let $x(d,v)_j=h_j$ for $j<i$, $x(d,v)_i=d$, and $x(d,v)_j=v_j$ for $j>i$; using binary digits $r_t$, set

$$\operatorname{rev}_n(r)= \left(\sum_{t=0}^{n-1}r_t2^{n-1-t}\right)\bmod N,\qquad E_n(x)_c= \sum_{\substack{0\le r<N\\ \forall t<n,\ c_t=1\Rightarrow(\operatorname{rev}_n(r))_t=1}}x_r \quad\text{in }\mathbb F_2,$$

and define matrices

$$A_d(a,a')=\frac1{2^N}\sum_{v\in\mathbb F_2^N} \prod_{c=0}^{N-1}W_{E_n(x(d,v))_c}(a_c,a'_c) \qquad(a,a'\in I^N).$$

For each $d$, choose a bounded complex-linear operator $T_d$ whose matrix coefficients in the coordinate basis are $A_d$, if such an operator exists, and otherwise set $T_d=0$. Choose a positive bounded operator $S_d$ satisfying $S_d^2=T_d$, if one exists, and otherwise set $S_d=0$. Let $P$ be the orthogonal projection onto the norm-closed complex span of all $v\in\mathcal H$ satisfying $(S_0-S_1)v=av$ for some real $a<0$. The defined operator is $1-P$ when $b=0$, and $P$ when $b=1$. No positivity or normalization assumptions are imposed on $W$, so the zero fallbacks are part of the definition. Empty $I$, empty histories at $i=0$, and $n=0$ are included; for $n=0$, the matrices $A_d$ reduce to $W_d$ under the identification of length-one words with their entries.

QAlgorithms.Papers.Independent.Intakethird100.P14.branchIndex

For any type $\Omega$, sequence of Boolean-valued functions $B:\mathbb N\to(\Omega\to\{\mathrm{false},\mathrm{true}\})$, natural number $n$, and point $w\in\Omega$, this defines an index in $\{0,\ldots,2^n-1\}$ with numerical value

$$\left(\sum_{k=0}^{n-1} \mathbf 1_{\{B_k(w)=\mathrm{true}\}}\,2^{n-1-k}\right)\bmod 2^n.$$

Thus $B_0(w)$ supplies the most significant of the $n$ binary digits and $B_{n-1}(w)$ the least significant. No measurability or probabilistic assumptions on $\Omega$ or $B$ are required. For $n=0$, the sum is empty and the result is the sole index $0$ in $\{0\}$.

QAlgorithms.Papers.Independent.Intakethird100.P14.channelMinus

For any type $I$ and any function $W$ assigning a complex matrix $W_b$ indexed by $I$ to each bit $b\in\mathbb F_2$, this defines a function assigning to $b$ a complex matrix indexed by $I\times I$. For row $(a_1,a_2)$ and column $(a'_1,a'_2)$, its entry is

$$W^-_b\bigl((a_1,a_2),(a'_1,a'_2)\bigr) =\frac12\sum_{c\in\mathbb F_2} W_{b+c}(a_1,a'_1)\,W_c(a_2,a'_2),$$

where $b+c$ is addition modulo two. No positivity or normalization assumptions are made on $W$, and $I$ may be empty.

QAlgorithms.Papers.Independent.Intakethird100.P14.channelPlus

For any type $I$ and any function $W$ assigning a complex matrix $W_b$ indexed by $I$ to each bit $b\in\mathbb F_2$, this defines a function assigning to an input bit $c$ a complex matrix indexed by $\mathbb F_2\times(I\times I)$. Its entries are

$$W^+_c\bigl((b,(a_1,a_2)),(b',(a'_1,a'_2))\bigr)= \begin{cases} \displaystyle\frac12W_{b+c}(a_1,a'_1)W_c(a_2,a'_2),&b=b',\\ 0,&b\ne b', \end{cases}$$

with bit addition taken modulo two. No positivity or normalization assumptions are imposed on $W$, and $I$ may be empty.

QAlgorithms.Papers.Independent.Intakethird100.P14.childIndex

For every $n\in\mathbb N$, every index $0\le i<2^n$, and every Boolean flag $\mathrm{good}$, this defines the index

$$\operatorname{childIndex}(i,\mathrm{good})= \begin{cases} 2i+1,&\mathrm{good}=\mathrm{true},\\ 2i,&\mathrm{good}=\mathrm{false}, \end{cases}$$

which lies in $\{0,\ldots,2^{n+1}-1\}$. The flag carries no additional hypothesis. The case $n=0$ is included: the parent index is $0$, and the child is $1$ or $0$, respectively.

QAlgorithms.Papers.Independent.Intakethird100.P14.coefficientOperator

For any type $I$ and any complex array $X=(X_{ij})_{i,j\in I}$, this defines an operator on $\ell^2(I;\mathbb C)$ as follows: if there exists a bounded complex-linear operator $T$ satisfying $(Te_j)(i)=X_{ij}$ for every $i,j\in I$, where $e_j$ has coordinate $1$ at $j$ and $0$ elsewhere, it returns a classically chosen such operator; otherwise it returns the zero operator. The input array is unrestricted, so the zero fallback applies whenever no bounded operator has the prescribed coefficients.

QAlgorithms.Papers.Independent.Intakethird100.P14.combinedOutput

For any type $I$, any function $W$ assigning a complex matrix $W_b=(W_b(a,a'))_{a,a'\in I}$ to each bit $b\in\mathbb F_2=\mathbb Z/2\mathbb Z$, any $n\in\mathbb N$, and any bit word $u$ of length $N=2^n$, this defines a complex matrix indexed by $I^N$. To describe its entries, let $r_t$ denote binary digit $t$ of a natural number $r$, define

$$\operatorname{rev}_n(r)= \left(\sum_{t=0}^{n-1}r_t\,2^{n-1-t}\right)\bmod N, \qquad E_n(u)_c= \sum_{\substack{0\le r<N\\ \forall t<n,\ c_t=1\Rightarrow(\operatorname{rev}_n(r))_t=1}}u_r \quad\text{in }\mathbb F_2.$$

Then, for $a,a'\in I^N$,

$$\operatorname{combinedOutput}(W,n,u)_{a,a'} =\prod_{c=0}^{N-1}W_{E_n(u)_c}(a_c,a'_c).$$

There is no positivity or normalization assumption on $W$, and $I$ may be empty. The case $n=0$ has $N=1$, empty binary-digit conditions, and $E_0(u)=u$.

QAlgorithms.Papers.Independent.Intakethird100.P14.cosetWord

For every natural number $n$, finite subset $A\subseteq\{0,\ldots,2^n-1\}$, assignment $m:A\to\mathbb Z/2\mathbb Z$, and assignment $f:A^{\mathrm c}\to\mathbb Z/2\mathbb Z$ on the complement within these indices, this defines the full word $u:\{0,\ldots,2^n-1\}\to\mathbb Z/2\mathbb Z$ by

$$u_i=\begin{cases}m_i,&i\in A,\\ f_i,&i\notin A.\end{cases}$$

If $A$ is empty, the result is $f$ on every index; if $A$ contains all indices, it is $m$ on every index. The definition includes $n=0$, when the full word has one position.

QAlgorithms.Papers.Independent.Intakethird100.P14.cqOperatorCoefficients

For any type $I$ and any bounded complex-linear operator $T:\ell^2(I;\mathbb C)\to\ell^2(I;\mathbb C)$, this defines the complex array with entries $X_{ij}=(Te_j)(i)$ for every $i,j\in I$, where $e_j$ is $1$ at coordinate $j$ and $0$ elsewhere. No positivity or trace condition on $T$ is required.

QAlgorithms.Papers.Independent.Intakethird100.P14.cqRelativeEntropyBits

For any type $I$ and any complex coefficient arrays $X,Y:I\times I\to\mathbb C$, let $H=\ell^2(I;\mathbb C)$. For an array $Z$, let $T_Z:H\to H$ be a chosen bounded complex-linear operator satisfying $(T_Z e_j)_i=Z_{ij}$ for every $i,j$, if such an operator exists, and let $T_Z=0$ otherwise; here $e_j$ is the coordinate unit vector. The definition takes the supremum over every natural number $n$, including $0$, and every orthonormal family $v_0,\ldots,v_{n-1}$ in $H$. For each such family, form the matrices $A_{ij}=\langle v_i,T_Xv_j\rangle$ and $B_{ij}=\langle v_i,T_Yv_j\rangle$. Its contribution is $+\infty$ if $\ker B\not\subseteq\ker A$; otherwise its contribution is the nonnegative part of

$$\frac{\operatorname{Re}\operatorname{tr}\!\left(f(A)-A\log(B)-A+B\right)}{\log 2}, \qquad f(t)=t\log t,$$

where $f(A)$ and $\log(B)$ use the library’s continuous functional calculus. The supremum lies in $[0,+\infty]$. No positivity, normalization, trace-class, countability, or nonemptiness assumption is imposed on $I,X,Y$; the operator-selection fallback and the total functional-calculus expressions therefore remain part of the definition. The $n=0$ contribution is $0$.

QAlgorithms.Papers.Independent.Intakethird100.P14.cqRootFidelity

For any type $I$ and any map $W:\mathbb Z/2\mathbb Z\to\mathbb C^{I\times I}$, let $A_b$ be a classically chosen bounded complex-linear operator on $\ell^2(I;\mathbb C)$ with coefficients $(A_be_j)(i)=W(b)_{ij}$ for all $i,j$, if such an operator exists, and set $A_b=0$ otherwise; here $e_j$ is the coordinate unit vector. Let $S$ be a classically chosen bounded positive square root of $A_0$, or $0$ if none exists, and let $R$ be a classically chosen bounded positive square root of $S\circ A_1\circ S$, or $0$ if none exists. The defined real number is $\operatorname{Re}\sum_{i\in I}(Re_i)(i)$, using the unconditional complex sum, which is $0$ if its terms are not summable. No assumption that either output of $W$ is a density array is imposed; empty $I$ gives value $0$.

QAlgorithms.Papers.Independent.Intakethird100.P14.decodingBranch

For any type $I$, natural number $n$, arbitrary assignment $W:\mathbb Z/2\mathbb Z\to\operatorname{Mat}_{I\times I}(\mathbb C)$, finite set $A\subseteq\{0,\ldots,N-1\}$ with $N=2^n$, and binary word $u$ on these $N$ indices, this defines a bounded complex linear operator $K$ on $\ell^2(\{0,\ldots,N-1\}\to I)$. Its construction is as follows. Let $\operatorname{rev}_n(r)$ be the integer obtained by reversing the $n$ binary digits of $r$, and set $F_{a,b}=1$ if $b=0$ and $F_{a,b}=a$ otherwise, for $a,b\in\mathbb Z/2\mathbb Z$. Define

$$G_{r,c}=\prod_{k=0}^{n-1}F_{\operatorname{bit}_k(\operatorname{rev}_n(r)),\,\operatorname{bit}_k(c)}, \qquad E(v)_c=\sum_{r=0}^{N-1}v_rG_{r,c}, \qquad \Gamma_v(x,y)=\prod_{c=0}^{N-1}W(E(v)_c)_{x_c,y_c},$$

where the bits are read from the least significant end and the sum defining $E$ is in $\mathbb Z/2\mathbb Z$. For a prefix $h$ of length $i$ and bit $b$, let $v^{i,h,b}$ agree with $h$ before $i$, equal $b$ at $i$, and agree with $v$ after $i$, and define

$$V_{i,h,b}=2^{-N}\sum_{v\in(\mathbb Z/2\mathbb Z)^N}\Gamma_{v^{i,h,b}}.$$

For a coefficient matrix $X$ on any label set, let $C(X)$ be a chosen bounded operator with matrix coefficients $X$ in the standard $\ell^2$ basis if such an operator exists, and zero otherwise. For a bounded operator $T$, let $R(T)$ be a chosen bounded positive operator $S$ satisfying $S^2=T$ if one exists, and zero otherwise. Let $P_{i,h}$ be the orthogonal projection onto the closed complex linear span of all vectors $v$ satisfying

$$\bigl(R(C(V_{i,h,0}))-R(C(V_{i,h,1}))\bigr)v=a v \quad\text{for some real }a<0.$$

Put $h=u|_{\{0,\ldots,i-1\}}$ and define $Q_i$ to be the identity if $i\notin A$, $1-P_{i,h}$ if $i\in A$ and $u_i=0$, and $P_{i,h}$ if $i\in A$ and $u_i=1$. The resulting operator is

$$K=Q_{N-1}\circ\cdots\circ Q_0,$$

so the factors are applied in increasing index order. No density or channel condition is assumed on $W$, and $I$ need not be finite or countable. If $A$ is empty, $K$ is the identity. The case $n=0$ has one wire and one factor.

QAlgorithms.Papers.Independent.Intakethird100.P14.decodingEffect

For any type $I$, arbitrary coefficient matrices $W(0),W(1)$ indexed by $I$, natural number $n$, finite set $A\subseteq\{0,\ldots,N-1\}$ where $N=2^n$, and word $u\in(\mathbb Z/2\mathbb Z)^N$, this defines the operator $K^*K$ on $\ell^2(\{0,\ldots,N-1\}\to I)$ by the following construction of $K$. With $F_{a,b}=1$ for $b=0$ and $F_{a,b}=a$ for $b=1$, define the binary transform and coefficient matrices by

$$G_{r,c}=\prod_{k=0}^{n-1}F_{\operatorname{bit}_k(\operatorname{rev}_n(r)),\,\operatorname{bit}_k(c)}, \qquad E(v)_c=\sum_r v_rG_{r,c}, \qquad \Gamma_v(x,y)=\prod_c W(E(v)_c)_{x_c,y_c},$$

where $\operatorname{rev}_n$ reverses the $n$ binary digits and $\operatorname{bit}_k$ reads the $k$th least significant bit. For each $i$, prefix $h$ of length $i$, and bit $b$, let $v^{i,h,b}$ use $h$ before $i$, $b$ at $i$, and $v$ after $i$, and put $V_{i,h,b}=2^{-N}\sum_v\Gamma_{v^{i,h,b}}$, the sum running over all $N$-bit words. Let $C(X)$ be a chosen bounded operator realizing the coefficients $X$, or zero if none exists, and let $R(T)$ be a chosen bounded positive square root of $T$, or zero if none exists. Let $P_{i,h}$ project onto the closed complex span of the eigenvectors of $R(C(V_{i,h,0}))-R(C(V_{i,h,1}))$ with strictly negative real eigenvalues. For $h=u|_{\{0,\ldots,i-1\}}$, set $Q_i=1$ when $i\notin A$, $Q_i=1-P_{i,h}$ when $i\in A$ and $u_i=0$, and $Q_i=P_{i,h}$ when $i\in A$ and $u_i=1$. Then

$$K=Q_{N-1}\circ\cdots\circ Q_0, \qquad \text{the defined effect}=K^*\circ K.$$

There are no normalization assumptions on $W$ or finiteness or countability assumptions on $I$. For $A=\varnothing$ this is the identity; $n=0$ is included and gives $N=1$.

QAlgorithms.Papers.Independent.Intakethird100.P14.decodingSuccess

For any type $I$, arbitrary matrices $W(0),W(1)$ indexed by $I$, natural number $n$, finite set $A$ of the $N=2^n$ wire indices, and word $u\in(\mathbb Z/2\mathbb Z)^N$, this defines the real number

$$\operatorname{Re}\sum_{x:\{0,\ldots,N-1\}\to I} \bigl(K_u^*K_u\,C(\Gamma_u)e_x\bigr)_x,$$

where $e_x$ is the standard unit coordinate vector in $\ell^2(\{0,\ldots,N-1\}\to I)$. Here, with $F_{a,b}=1$ if $b=0$ and $F_{a,b}=a$ otherwise,

$$G_{r,c}=\prod_{k=0}^{n-1}F_{\operatorname{bit}_k(\operatorname{rev}_n(r)),\,\operatorname{bit}_k(c)}, \qquad E(v)_c=\sum_r v_rG_{r,c}, \qquad \Gamma_v(x,y)=\prod_cW(E(v)_c)_{x_c,y_c}.$$

The map $\operatorname{rev}_n$ reverses $n$ binary digits, the digit indices are counted from the least significant end, and $E$ is computed over $\mathbb Z/2\mathbb Z$. For a prefix $h$ of length $i$, let $v^{i,h,b}$ equal $h$ before $i$, $b$ at $i$, and $v$ after $i$, and put $V_{i,h,b}=2^{-N}\sum_{v\in(\mathbb Z/2\mathbb Z)^N}\Gamma_{v^{i,h,b}}$. For any matrix $X$, $C(X)$ is a chosen bounded operator realizing its standard-basis coefficients if one exists, and zero otherwise; $R(T)$ is a chosen bounded positive square root of $T$ if one exists, and zero otherwise. Let $P_{i,h}$ be the orthogonal projection onto the closed complex span of the eigenvectors of $R(C(V_{i,h,0}))-R(C(V_{i,h,1}))$ having strictly negative real eigenvalues. Using $h=u|_{\{0,\ldots,i-1\}}$, put $Q_i=1$ if $i\notin A$, $Q_i=1-P_{i,h}$ if $i\in A$ and $u_i=0$, and $Q_i=P_{i,h}$ if $i\in A$ and $u_i=1$, and set $K_u=Q_{N-1}\circ\cdots\circ Q_0$. The displayed sum is the totalized complex sum, which is zero if the family is not summable. Neither density assumptions on $W$ nor a bound between zero and one are part of this definition. The type $I$ may be empty, finite, or uncountable, and $n=0$ gives one wire.

QAlgorithms.Papers.Independent.Intakethird100.P14.densitySqrt

For any type $I$ and any complex array $X=(X_{ij})_{i,j\in I}$, first let $A$ be a classically chosen bounded complex-linear operator on $\ell^2(I;\mathbb C)$ satisfying $(Ae_j)(i)=X_{ij}$ for every $i,j$, if one exists, and let $A=0$ otherwise, where $e_j$ is the coordinate unit vector. This definition then returns a classically chosen bounded positive operator $S$ with $S\circ S=A$, if one exists, and returns $0$ otherwise. No density, positivity, normalization, or summability hypothesis is required of $X$.

QAlgorithms.Papers.Independent.Intakethird100.P14.ensembleError

For any type $I$, arbitrary matrices $W(0),W(1)$ indexed by $I$, natural number $n$, and finite subset $A$ of the $N=2^n$ wire indices, this defines the real number

$$\frac{1}{2^{N-|A|}} \sum_{f:A^{\mathrm c}\to\mathbb Z/2\mathbb Z} \left(1-\frac{1}{2^{|A|}} \sum_{m:A\to\mathbb Z/2\mathbb Z}s(u^{m,f})\right), \qquad u^{m,f}_i=\begin{cases}m_i,&i\in A,\\f_i,&i\notin A.\end{cases}$$

Here

$$s(u)=\operatorname{Re}\sum_{x:\{0,\ldots,N-1\}\to I} \bigl(K_u^*K_u\,C(\Gamma_u)e_x\bigr)_x.$$

Its ingredients are specified as follows. Put $F_{a,b}=1$ when $b=0$ and $F_{a,b}=a$ otherwise, and set

$$G_{r,c}=\prod_{k=0}^{n-1}F_{\operatorname{bit}_k(\operatorname{rev}_n(r)),\,\operatorname{bit}_k(c)}, \qquad E(v)_c=\sum_r v_rG_{r,c}, \qquad \Gamma_v(x,y)=\prod_c W(E(v)_c)_{x_c,y_c},$$

where $E$ uses arithmetic in $\mathbb Z/2\mathbb Z$, $\operatorname{rev}_n$ reverses $n$ binary digits, and $\operatorname{bit}_k$ reads the $k$th least significant digit. For a prefix $h$ of length $i$ and bit $b$, let $v^{i,h,b}$ use $h$ before $i$, $b$ at $i$, and $v$ thereafter, and put $V_{i,h,b}=2^{-N}\sum_v\Gamma_{v^{i,h,b}}$, averaging over all $N$-bit words. Let $C(X)$ be a chosen bounded operator with coefficient matrix $X$ if one exists, and zero otherwise; let $R(T)$ be a chosen bounded positive square root of $T$ if one exists, and zero otherwise. Let $P_{i,h}$ project onto the closed complex span of the eigenvectors of $R(C(V_{i,h,0}))-R(C(V_{i,h,1}))$ with strictly negative real eigenvalues. For $h=u|_{\{0,\ldots,i-1\}}$, define $Q_i=1$ outside $A$, $Q_i=1-P_{i,h}$ at selected zero bits, and $Q_i=P_{i,h}$ at selected one bits, and let $K_u=Q_{N-1}\circ\cdots\circ Q_0$. The vectors $e_x$ are the standard basis of $\ell^2(\{0,\ldots,N-1\}\to I)$, and a nonsummable complex family in the displayed sum has totalized sum zero. Both averaging denominators are positive, including when either assignment domain is empty. No density or channel hypothesis on $W$ or range bound on the resulting real number is imposed. The case $n=0$ has one wire.

QAlgorithms.Papers.Independent.Intakethird100.P14.fidelityProcess

For arbitrary types $I,\Omega$, a function $W:\mathbb Z_2\to\mathbb C^{I\times I}$, Boolean functions $B_k:\Omega\to\{\mathrm{false},\mathrm{true}\}$, $n\in\mathbb N$, and $w\in\Omega$, this defines a real number as follows. Put $N=2^n$ and

$$i=\left(\sum_{k=0}^{n-1}\mathbf1_{\{B_k(w)=\mathrm{true}\}}2^{n-1-k}\right)\bmod N.$$

Write $b_k(r)\in\mathbb Z_2$ for bit $k$ of $r$, let $\operatorname{rev}_n(r)=(\sum_{k<n}b_k(r)2^{n-1-k})\bmod N$, and set $G_{rt}=\prod_{k<n}K(b_k(\operatorname{rev}_n(r)),b_k(t))$, where $K(a,0)=1$ and $K(a,1)=a$. The binary output array $V$, indexed by labels $(h,x)\in\mathbb Z_2^i\times I^N$, is

$$V(b)_{(h,x),(h',y)} =\begin{cases} 2^{-(N-1)} \displaystyle\sum_{\substack{u\in\mathbb Z_2^N\\u_{<i}=h,\ u_i=b}} \prod_{t<N}W((uG)_t)_{x_t,y_t},&h=h',\\ 0,&h\ne h', \end{cases}$$

where $uG$ is computed over $\mathbb Z_2$. For any coefficient array $X$ on a label type $L$, let $O_X$ be a chosen bounded complex linear operator on $\ell^2(L;\mathbb C)$ satisfying $(O_Xe_j)_a=X_{aj}$, if such an operator exists, and zero otherwise; $e_j$ is the coordinate unit vector. Let $R(T)$ be a chosen positive bounded operator satisfying $R(T)^2=T$, if one exists, and zero otherwise, and let $\operatorname{tr}_b(T)=\sum'_a(Te_a)_a$. The defined value is

$$\sqrt{\left(\operatorname{Re}\operatorname{tr}_b R\!\left(R(O_{V(0)})\,O_{V(1)}\,R(O_{V(0)})\right)\right)^2}.$$

The square root is the nonnegative real square root, so this is the absolute value of the displayed real trace. There are no density, countability, measurability, or randomness assumptions on $W,I,\Omega,B$. The case $n=0$ is included: $N=1$, the branch index is zero, and the products defining $G$ are empty products. The complex sum defining $\operatorname{tr}_b$ has value zero if it is not summable.

QAlgorithms.Papers.Independent.Intakethird100.P14.filledWord

For every $n\in\mathbb N$, put $N=2^n$. Given an index $0\le i<N$, a history $h:\{0,\ldots,i-1\}\to\mathbb F_2$, a bit $b\in\mathbb F_2$, and a word $v:\{0,\ldots,N-1\}\to\mathbb F_2$, this defines the word $x$ by

$$x_j= \begin{cases} h_j,&j<i,\\ b,&j=i,\\ v_j,&j>i. \end{cases}$$

Thus the coordinates of $v$ at indices at most $i$ do not affect the result. The history is empty when $i=0$, and no coordinates from $v$ are used when $i=N-1$. The case $n=0$ is included: then $N=1$, $i=0$, and the resulting word consists solely of $b$.

QAlgorithms.Papers.Independent.Intakethird100.P14.frozenError

For any type $I$, arbitrary matrices $W(0),W(1)$ indexed by $I$, natural number $n$, finite set $A\subseteq\{0,\ldots,N-1\}$ with $N=2^n$, and fixed assignment $f:A^{\mathrm c}\to\mathbb Z/2\mathbb Z$, this defines

$$1-\frac{1}{2^{|A|}}\sum_{m:A\to\mathbb Z/2\mathbb Z}s(u^{m,f}), \qquad u^{m,f}_i=\begin{cases}m_i,&i\in A,\\f_i,&i\notin A.\end{cases}$$

The number $s(u)$ is defined by

$$s(u)=\operatorname{Re}\sum_{x:\{0,\ldots,N-1\}\to I} \bigl(K_u^*K_u\,C(\Gamma_u)e_x\bigr)_x.$$

To specify its ingredients, let $F_{a,b}=1$ for $b=0$ and $F_{a,b}=a$ otherwise, and define

$$G_{r,c}=\prod_{k=0}^{n-1}F_{\operatorname{bit}_k(\operatorname{rev}_n(r)),\,\operatorname{bit}_k(c)}, \qquad E(v)_c=\sum_rv_rG_{r,c}, \qquad \Gamma_v(x,y)=\prod_cW(E(v)_c)_{x_c,y_c},$$

using arithmetic in $\mathbb Z/2\mathbb Z$, $n$-digit binary reversal, and digit indices counted from the least significant end. For a prefix $h$ of length $i$, form $v^{i,h,b}$ by replacing the coordinates before $i$ by $h$ and coordinate $i$ by $b$, retaining $v$ thereafter, and put $V_{i,h,b}=2^{-N}\sum_v\Gamma_{v^{i,h,b}}$, summing over all $N$-bit words. For any coefficient matrix $X$, $C(X)$ is a chosen bounded operator realizing $X$, or zero if none exists; $R(T)$ is a chosen bounded positive square root of $T$, or zero if none exists. Let $P_{i,h}$ project onto the closed complex span of the eigenvectors of $R(C(V_{i,h,0}))-R(C(V_{i,h,1}))$ having strictly negative real eigenvalues. With $h=u|_{\{0,\ldots,i-1\}}$, let $Q_i$ be $1$ outside $A$, $1-P_{i,h}$ for a selected zero bit, and $P_{i,h}$ for a selected one bit, and set $K_u=Q_{N-1}\circ\cdots\circ Q_0$. Here $e_x$ is the standard $\ell^2$ basis vector, and the complex sum defining $s$ is zero if it is not summable. The denominator $2^{|A|}$ is always positive; for $A=\varnothing$ the outer sum has one term. No density assumption on $W$ or restriction of this real value to $[0,1]$ is imposed, and $n=0$ is allowed.

QAlgorithms.Papers.Independent.Intakethird100.P14.futureAverage

For any type $I$, any pair of complex matrices $W_b$ indexed by $I$, with $b\in\mathbb F_2$, any $n\in\mathbb N$, index $0\le i<N=2^n$, history $h\in\mathbb F_2^i$, and bit $b$, this defines a complex matrix indexed by $I^N$. For each $v\in\mathbb F_2^N$, let $x(v)_j=h_j$ for $j<i$, $x(v)_i=b$, and $x(v)_j=v_j$ for $j>i$. Write $r_t$ for binary digit $t$, put

$$\operatorname{rev}_n(r)= \left(\sum_{t=0}^{n-1}r_t2^{n-1-t}\right)\bmod N, \qquad E_n(x)_c= \sum_{\substack{0\le r<N\\ \forall t<n,\ c_t=1\Rightarrow(\operatorname{rev}_n(r))_t=1}}x_r \quad\text{in }\mathbb F_2.$$

For $a,a'\in I^N$, the entry is

$$\operatorname{futureAverage}(W,n,i,h,b)_{a,a'} =\frac1{2^N}\sum_{v\in\mathbb F_2^N} \prod_{c=0}^{N-1}W_{E_n(x(v))_c}(a_c,a'_c).$$

The sum includes all coordinates of $v$, even though its first $i+1$ coordinates are overwritten. No density-matrix assumptions are imposed on $W$, and $I$ may be empty. When $n=0$, this is the matrix with entries $W_b(a_0,a'_0)$.

QAlgorithms.Papers.Independent.Intakethird100.P14.informationProcess

For arbitrary types $I,\Omega$, $W:\mathbb Z_2\to\mathbb C^{I\times I}$, Boolean functions $B_k:\Omega\to\{\mathrm{false},\mathrm{true}\}$, $n\in\mathbb N$, and $w\in\Omega$, put $N=2^n$ and $i=(\sum_{k<n}\mathbf1_{\{B_k(w)=\mathrm{true}\}}2^{n-1-k})\bmod N$. Define $G_{rt}=\prod_{k<n}K(b_k(\operatorname{rev}_n(r)),b_k(t))$ over $\mathbb Z_2$, where $b_k(r)$ is bit $k$, $\operatorname{rev}_n(r)=(\sum_{k<n}b_k(r)2^{n-1-k})\bmod N$, and $K(a,0)=1,\ K(a,1)=a$. Define arrays $V(b)$, with labels $(h,x)\in\mathbb Z_2^i\times I^N$, by

$$V(b)_{(h,x),(h',y)} =\begin{cases} 2^{-(N-1)} \displaystyle\sum_{\substack{u\in\mathbb Z_2^N\\u_{<i}=h,\ u_i=b}} \prod_{t<N}W((uG)_t)_{x_t,y_t},&h=h',\\ 0,&h\ne h'. \end{cases}$$

For an array $X$ on $L$, $O_X$ denotes a chosen bounded operator on $\ell^2(L;\mathbb C)$ with coefficients $X_{ab}=(O_Xe_b)_a$, if one exists, and zero otherwise. For arrays $X,Y$, define $D_2(X\Vert Y)\in[0,\infty]$ as the supremum over all $m\in\mathbb N$, including zero, and all orthonormal families $v_0,\ldots,v_{m-1}\in\ell^2(L;\mathbb C)$, of

$$\begin{cases} \displaystyle \max\!\left\{0,\frac{\operatorname{Re}\operatorname{tr} \bigl(f(A)-A\log C-A+C\bigr)}{\log2}\right\}, &\ker C\subseteq\ker A,\\ \infty,&\text{otherwise}, \end{cases}$$

where $A_{rs}=\langle v_r,O_Xv_s\rangle$, $C_{rs}=\langle v_r,O_Yv_s\rangle$, $f(t)=t\log t$, and matrix functions mean continuous functional calculus. With $\overline V=(V(0)+V(1))/2$, the defined value is the real conversion of

$$\mathcal I(V)=\frac{D_2(V(0)\Vert\overline V)+D_2(V(1)\Vert\overline V)}2.$$

Real conversion leaves finite values unchanged and sends $\infty$ to zero. No validity, countability, measurability, or probabilistic assumptions are imposed. The case $n=0$, and the zero-operator fallbacks in $O_X$, are included.

QAlgorithms.Papers.Independent.Intakethird100.P14.negativeCompactProjection

For any type $J$ and any bounded complex-linear operator $T:\ell^2(J;\mathbb C)\to\ell^2(J;\mathbb C)$, this defines the orthogonal projection onto

$$\overline{\operatorname{span}_{\mathbb C} \left\{v\in\ell^2(J;\mathbb C): \exists a\in\mathbb R,\ a<0\ \text{and}\ Tv=av\right\}}.$$

The closure is in the Hilbert-space norm. Neither compactness nor self-adjointness of $T$ is assumed. If there are no nonzero vectors satisfying the displayed condition, the resulting projection is zero. The type $J$ may be empty.

QAlgorithms.Papers.Independent.Intakethird100.P14.parentLabels

For any type $I$, any $n\in\mathbb N$, any index $0\le i<N=2^n$, and any Boolean flag $\mathrm{good}$, put $\delta=1$ if the flag is true and $\delta=0$ otherwise. Given a pair $p=(h,y)$, where $h\in\mathbb F_2^{\,2i+\delta}$ and $y\in I^{2N}$, this defines two pairs $((a,x),(b,z))\in(\mathbb F_2^i\times I^N)^2$ by

$$a_k=h_{2k}+h_{2k+1},\qquad b_k=h_{2k+1}\quad(0\le k<i), \qquad x_j=y_j,\qquad z_j=y_{N+j}\quad(0\le j<N),$$

where addition is modulo two. When the flag is true, the last history bit $h_{2i}$ is unused by this map. When $i=0$, both resulting histories are empty. The case $n=0$ and arbitrary, possibly empty, $I$ are included.

QAlgorithms.Papers.Independent.Intakethird100.P14.plusLabel

For any type $I$, any $n\in\mathbb N$, and any index $0\le i<N=2^n$, an input label is a pair $p=(h,y)$ with $h\in\mathbb F_2^{\,2i+1}$ and $y\in I^{2N}$. This defines the triple, grouped as one bit and a pair of labels,

$$\operatorname{plusLabel}(i,p)=\bigl(h_{2i},((a,x),(b,z))\bigr),$$

where

$$a_k=h_{2k}+h_{2k+1},\qquad b_k=h_{2k+1}\quad(0\le k<i), \qquad x_j=y_j,\qquad z_j=y_{N+j}\quad(0\le j<N),$$

and bit addition is modulo two. Thus each inner label belongs to $\mathbb F_2^i\times I^N$. When $i=0$, the inner histories are empty and the separate output bit is $h_0$; this includes $n=0$, for which $N=1$. No assumptions are imposed on $I$.

QAlgorithms.Papers.Independent.Intakethird100.P14.polarDecay

For arbitrary real numbers $\beta$ and $\mathrm{scale}$ and every natural number $n$, this defines the real value

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

where both powers with real exponents are real powers. There are no sign restrictions on $\beta$ or $\mathrm{scale}$. In particular, at $n=0$ the value is $2^{-\mathrm{scale}}$, and for $\mathrm{scale}=0$ it is $1$ for every $n$.

QAlgorithms.Papers.Independent.Intakethird100.P14.polarEncode

For every $n\in\mathbb N$ and every word $u:\{0,\ldots,2^n-1\}\to\mathbb Z/2\mathbb Z$, this returns the word whose coordinate $c$ is $\sum_{r=0}^{2^n-1}u_rP_{rc}$, with sums and products in $\mathbb Z/2\mathbb Z$. To specify $P$, write $b_k(j)$ for bit $k$ of $j$, counted from the least significant bit, and put $R_n(r)=\bigl(\sum_{k=0}^{n-1}b_k(r)2^{n-1-k}\bigr)\bmod2^n$; then $P_{rc}$ is the product over $k=0,\ldots,n-1$ of $1$ if $b_k(c)=0$, and $b_k(R_n(r))$ otherwise. When $n=0$, the word has one coordinate and is returned unchanged.

QAlgorithms.Papers.Independent.Intakethird100.P14.polarKernel

This is the matrix over $\mathbb Z/2\mathbb Z$, with rows and columns indexed by $\mathbb Z/2\mathbb Z$, whose entry at row $r$ and column $c$ is $1$ if $c=0$, and $r$ otherwise. With row and column order $0,1$, it is $\begin{pmatrix}1&0\\1&1\end{pmatrix}$.

QAlgorithms.Papers.Independent.Intakethird100.P14.polarMatrix

For every $n\in\mathbb N$, this defines a $2^n\times2^n$ matrix over $\mathbb Z/2\mathbb Z$. For row $r$ and column $c$ in $\{0,\ldots,2^n-1\}$, let $R_n(r)=\bigl(\sum_{k=0}^{n-1}b_k(r)2^{n-1-k}\bigr)\bmod2^n$, where $b_k(j)\in\{0,1\}$ is bit $k$ of $j$, counted from the least significant bit. The entry is the product, in $\mathbb Z/2\mathbb Z$, over $k=0,\ldots,n-1$ of $1$ when $b_k(c)=0$, and $b_k(R_n(r))$ when $b_k(c)=1$. For $n=0$, the product is empty, so the sole matrix entry is $1$.

QAlgorithms.Papers.Independent.Intakethird100.P14.positiveBoundedRoot

For any type $I$ and any bounded complex-linear operator $T$ on $\ell^2(I;\mathbb C)$, this returns a classically chosen bounded positive operator $S$ satisfying $S\circ S=T$, if such an operator exists, and returns the zero operator otherwise. Here positivity is positivity as an operator on the complex Hilbert space. No positivity assumption on $T$ is imposed.

QAlgorithms.Papers.Independent.Intakethird100.P14.previousBits

For every natural number $n$, let $N=2^n$ and identify the wire indices with $\{0,\ldots,N-1\}$. Given an index $i$ and a word $u:\{0,\ldots,N-1\}\to\mathbb Z/2\mathbb Z$, this defines the word of length $i$ whose value at $k<i$ is $u_k$. Thus it retains every bit strictly before $i$, regardless of any choice of information positions. For $i=0$ its domain is empty. The case $n=0$ is included: there is one wire, indexed by $0$, and its preceding word is empty.

QAlgorithms.Papers.Independent.Intakethird100.P14.recursivePolarEncoder

For every $n\in\mathbb N$, this defines a finite list of instructions on indices $\{0,\ldots,2^n-1\}$. Write $b_k(i)$ for bit $k$ of $i$, counted from the least significant bit, and $R_n(i)=\bigl(\sum_{k=0}^{n-1}b_k(i)2^{n-1-k}\bigr)\bmod2^n$. The list first contains one swap of $i$ and $R_n(i)$ for every index satisfying $i<R_n(i)$, in the enumeration order obtained by converting that filtered finite set to a list. It then concatenates stages for $k=0,1,\ldots,n-1$ in increasing order; stage $k$ contains, for every index $i$ with $b_k(i)=0$, an XOR instruction with source $(i\mathbin{\mathrm{xor}}2^k)\bmod2^n$ and target $i$, again in the enumeration order obtained from the filtered finite set. An XOR instruction adds the source value to the target value in $\mathbb Z/2\mathbb Z$, and a swap exchanges its two values. When $n=0$, both portions are empty, so the resulting list is empty.

QAlgorithms.Papers.Independent.Intakethird100.P14.reverseWire

For every $n\in\mathbb N$ and every index $i\in\{0,\ldots,2^n-1\}$, this returns the index whose value is

$$\left(\sum_{k=0}^{n-1}\mathbf 1_{\{\text{bit }k\text{ of }i\text{ is }1\}}\,2^{\,n-1-k}\right)\bmod 2^n,$$

where bit $0$ is the least significant bit. Thus the formula reverses the $n$ binary digits and explicitly reduces the result modulo $2^n$. The exponent subtraction is natural-number subtraction; for the displayed summation indices it does not truncate a negative value. When $n=0$, the sum is empty and the result is $0$.

QAlgorithms.Papers.Independent.Intakethird100.P14.runEncoder

For every $n\in\mathbb N$, every finite ordered list of instructions, and every word $u:\{0,\ldots,2^n-1\}\to\mathbb Z/2\mathbb Z$, this returns the result of applying the instructions successively from the beginning of the list to its end, starting with $u$. An XOR instruction from $s$ to $t$ replaces the current target value by the sum of the current target and source values in $\mathbb Z/2\mathbb Z$; a swap exchanges the current values at its two indices. Equal source and target are permitted and set that coordinate to $0$; equal swap indices have no effect. An empty list returns $u$, and $n=0$ is allowed, giving a one-coordinate word.

QAlgorithms.Papers.Independent.Intakethird100.P14.splitChannel

For any type $I$, any function assigning a complex matrix $W_b$ indexed by $I$ to each $b\in\mathbb F_2$, any $n\in\mathbb N$, and index $0\le i<N=2^n$, this defines a matrix-valued function of an input bit $b$, with rows and columns indexed by pairs $(h,a)\in\mathbb F_2^i\times I^N$. For a history $h$, let $x(h,b,v)_j=h_j$ when $j<i$, $b$ when $j=i$, and $v_j$ when $j>i$. Define

$$\operatorname{rev}_n(r)= \left(\sum_{t=0}^{n-1}r_t2^{n-1-t}\right)\bmod N, \qquad E_n(x)_c= \sum_{\substack{0\le r<N\\ \forall t<n,\ c_t=1\Rightarrow(\operatorname{rev}_n(r))_t=1}}x_r \quad\text{in }\mathbb F_2,$$

where subscripts $t$ denote binary digits. Its entries are

$$\operatorname{splitChannel}(W,n,i)_b\bigl((h,a),(h',a')\bigr)= \begin{cases} \displaystyle\frac1{2^i2^N}\sum_{v\in\mathbb F_2^N} \prod_{c=0}^{N-1}W_{E_n(x(h,b,v))_c}(a_c,a'_c), &h=h',\\[2mm] 0,&h\ne h'. \end{cases}$$

There are no positivity or normalization hypotheses on $W$, and $I$ may be empty. For $n=0$, the histories are empty and the entries reduce to $W_b(a_0,a'_0)$.

QAlgorithms.Papers.Independent.Intakethird100.P14.squaredCqFidelity

For any type $I$ and any map $W:\mathbb Z/2\mathbb Z\to\mathbb C^{I\times I}$, form $A_b$ by choosing a bounded complex-linear operator on $\ell^2(I;\mathbb C)$ satisfying $(A_be_j)(i)=W(b)_{ij}$ for every $i,j$, or taking $A_b=0$ if no such operator exists, where $e_j$ is the coordinate unit vector. Choose a bounded positive square root $S$ of $A_0$, taking $S=0$ if none exists, and choose a bounded positive square root $R$ of $S\circ A_1\circ S$, taking $R=0$ if none exists. This defines $\left(\operatorname{Re}\sum_{i\in I}(Re_i)(i)\right)^2$, where a nonsummable unconditional complex sum is assigned value $0$. No density or normalization assumption is required, and empty $I$ gives value $0$.

QAlgorithms.Papers.Independent.Intakethird100.P14.symmetricInformation

For any type $I$ and any pair of complex coefficient arrays $W_b:I\times I\to\mathbb C$, indexed by $b\in\mathbb Z/2\mathbb Z$, put $\overline W=(W_0+W_1)/2$. The definition is $\bigl(D(W_0,\overline W)+D(W_1,\overline W)\bigr)/2$, with arithmetic in $[0,+\infty]$. Here $D(X,Y)$ is defined as follows: on $H=\ell^2(I;\mathbb C)$, choose for each array $Z$ a bounded complex-linear operator $T_Z$ with coordinate matrix $Z$, or use $0$ if none exists; for every $n\in\mathbb N$ and every orthonormal family $v_0,\ldots,v_{n-1}$, form $A_{ij}=\langle v_i,T_Xv_j\rangle$ and $B_{ij}=\langle v_i,T_Yv_j\rangle$; take the supremum of $+\infty$ when $\ker B\not\subseteq\ker A$, and otherwise of the nonnegative part of $\operatorname{Re}\operatorname{tr}(f(A)-A\log(B)-A+B)/\log 2$, where $f(t)=t\log t$ and matrix functions use continuous functional calculus. The empty family $n=0$ contributes $0$. There is no assumption that either $W_b$ is a density array, and no countability or nonemptiness assumption on $I$.

QAlgorithms.Papers.Independent.Intakethird100.P14.toggleWire

For every $n\in\mathbb N$, every $k\in\{0,\ldots,n-1\}$, and every $i\in\{0,\ldots,2^n-1\}$, this returns the index with value $(i\mathbin{\mathrm{xor}}2^k)\bmod2^n$, where the XOR is bitwise XOR of natural numbers. This toggles bit $k$, counted from the least significant bit, and explicitly reduces modulo $2^n$. For $n=0$, there is no possible argument $k$.

QAlgorithms.Papers.Independent.Intakethird100.P14.uniformMixture

For any type $I$ and any map $W:\mathbb Z/2\mathbb Z\to\mathbb C^{I\times I}$, this defines the complex array with entries $\frac12\bigl(W(0)_{ij}+W(1)_{ij}\bigr)$ for every $i,j\in I$. No positivity, normalization, summability, or nonemptiness assumption is imposed.