Definitions for Polar codes for degradable quantum channels

QAlgorithms.Papers.Independent.Intakethird100.P10.BinaryCQ

For any type $H$, $\mathrm{BinaryCQ}(H)$ is the type of functions assigning a complex matrix indexed by $H\times H$ to each Boolean value. Thus an element is an arbitrary pair $(W_0,W_1)$ of such matrices, with $0$ denoting false and $1$ denoting true; this abbreviation imposes no finiteness, positivity, or normalization requirements.

QAlgorithms.Papers.Independent.Intakethird100.P10.IsBinaryCQ

For any finite type $H$ and any pair $W=(W_0,W_1)$ of complex $H\times H$ matrices, $\mathrm{IsBinaryCQ}(W)$ means that both $W_0$ and $W_1$ are positive semidefinite and have complex trace exactly $1$. If $H$ is empty, this condition cannot hold, since every matrix on $H$ has trace $0$.

QAlgorithms.Papers.Independent.Intakethird100.P10.PolarGate.apply

For every natural number $N$, every gate description $g$ consisting either of a controlled-NOT with distinct indices $c,t<N$ or a swap with arbitrary indices $a,b<N$, and every Boolean word $u$ of length $N$, this declaration defines the resulting word as follows. A controlled-NOT replaces $u_t$ by $u_c\mathbin{\oplus}u_t$ and leaves all other coordinates unchanged, where $\oplus$ is Boolean exclusive OR. A swap first replaces coordinate $a$ by the original $u_b$, then coordinate $b$ by the original $u_a$, leaving other coordinates unchanged. When $a=b$, this action is the identity. The parameter $N$ may be zero, although then no gate description exists.

QAlgorithms.Papers.Independent.Intakethird100.P10.PolarGate

For each natural number $N$, this declaration introduces a type of gate descriptions with exactly two forms: a controlled-NOT description carrying a control index $c$ and target index $t$ in $\{0,\ldots,N-1\}$, together with a proof that $c\ne t$; and a swap description carrying two indices $a,b$ in the same set, with no requirement that they differ. This declaration specifies the descriptions and their data, without assigning an action to them. For $N=0$ there are no such descriptions; for $N=1$, only the swap with both indices $0$ can be formed.

QAlgorithms.Papers.Independent.Intakethird100.P10.SplitRegister

For any type $H$, any natural number $n$, and any index $i\in\{0,\ldots,2^n-1\}$, the defined register type is

$$\{0,1\}^{\,i}\times H^{\,2^n}.$$

Its elements consist of a Boolean word of length $i$ and an $H$-valued word of length $2^n$. At $i=0$, the Boolean word is the unique empty word; $n=0$ forces $i=0$ and leaves one $H$-valued coordinate. No finiteness or nonemptiness assumption on $H$ is required.

QAlgorithms.Papers.Independent.Intakethird100.P10.Wiretap.bob

For finite types $B,E$ with decidable equality and any wiretap datum $V$, this defines the pair of $B$-indexed matrices

$$W_x^B(b,b')=\sum_{e\in E}\rho_x((b,e),(b',e)),\qquad x\in\{0,1\},$$

where $\rho_x=V.\mathrm{output}(x)$. Here the datum $V$ includes the requirements that both $\rho_x$ are positive semidefinite of trace $1$, that there is a map $D(X)=\sum_{j<r}K_jXK_j^\dagger$ for some finite family satisfying $\sum_jK_j^\dagger K_j=I_B$, that its application to each displayed $B$ marginal equals the corresponding $E$ marginal $\rho_x^E(e,e')=\sum_b\rho_x((b,e),(b,e'))$, and that the two $E$ marginals commute. The definition itself takes the partial trace over $E$ for each Boolean input.

QAlgorithms.Papers.Independent.Intakethird100.P10.Wiretap.eve

For finite types $B,E$ with decidable equality and any wiretap datum $V$, this defines the pair of $E$-indexed matrices

$$W_x^E(e,e')=\sum_{b\in B}\rho_x((b,e),(b,e')),\qquad x\in\{0,1\},$$

where $\rho_x=V.\mathrm{output}(x)$. The datum $V$ requires both $\rho_x$ to be positive semidefinite of trace $1$; it supplies a map $D(X)=\sum_{j<r}K_jXK_j^\dagger$ with $\sum_jK_j^\dagger K_j=I_B$, requires $W_x^E=D(W_x^B)$, where $W_x^B(b,b')=\sum_e\rho_x((b,e),(b',e))$, and requires $W_0^EW_1^E=W_1^EW_0^E$. The definition itself takes the partial trace over $B$ for each Boolean input.

QAlgorithms.Papers.Independent.Intakethird100.P10.Wiretap

For finite types $B,E$ with decidable equality, a value of this structure consists of two complex matrices $\rho_0,\rho_1$ indexed by $B\times E$, each positive semidefinite with trace $1$, together with a function $D$ from complex $B$-indexed square matrices to complex $E$-indexed square matrices that admits a finite Kraus representation: there exist a natural number $r$ and matrices $K_j$ with rows indexed by $E$ and columns by $B$ such that $\sum_{j<r}K_j^\dagger K_j=I_B$ and $D(X)=\sum_{j<r}K_jXK_j^\dagger$ for every matrix $X$. For each $x\in\{0,1\}$, the structure requires

$$\rho_x^E=D(\rho_x^B),\qquad \rho_x^B(b,b')=\sum_{e\in E}\rho_x((b,e),(b',e)),\qquad \rho_x^E(e,e')=\sum_{b\in B}\rho_x((b,e),(b,e')).$$

It also requires $\rho_0^E\rho_1^E=\rho_1^E\rho_0^E$. No nonemptiness assumptions on $B,E$ are explicitly supplied, but the required trace-one joint matrices cannot exist if either type is empty.

QAlgorithms.Papers.Independent.Intakethird100.P10.amplitudeComplement

For every real number $\gamma$, define a function on all complex $2\times2$ matrices, with rows and columns ordered as false, true, by

$$\mathcal A_\gamma(\rho)= \begin{pmatrix} \rho_{00}+(1-\gamma)\rho_{11}&\sqrt{\gamma}\,\rho_{01}\\ \sqrt{\gamma}\,\rho_{10}&\gamma\rho_{11} \end{pmatrix}.$$

No restriction on $\gamma$ or on the input matrix is imposed. The real square root is total and equals $0$ for negative $\gamma$.

QAlgorithms.Papers.Independent.Intakethird100.P10.assistanceSet

For finite types $B,E$ with decidable equality, a wiretap datum $V$, any natural number $n$, and any real $\beta$, this defines the set of indices $i<2^n$ satisfying

$$f(W_{n,i,0}^E,W_{n,i,1}^E)\le1-\tau \quad\text{and}\quad \tau\le f(W_{n,i,0}^B,W_{n,i,1}^B), \qquad \tau=2^{-(2^n)^\beta}.$$

Here $V$ supplies joint positive semidefinite trace-one matrices $\rho_x$, the marginals $W_x^B(b,b')=\sum_e\rho_x((b,e),(b',e))$ and $W_x^E(e,e')=\sum_b\rho_x((b,e),(b,e'))$, and a finite Kraus channel $D(X)=\sum_jK_jXK_j^\dagger$ with $\sum_jK_j^\dagger K_j=I_B$ and $W_x^E=D(W_x^B)$; its two $E$ marginals commute. For either pair $W$, put $N=2^n$ and define the synthesized matrices by

$$W_{n,i,x}((v,h),(v',h'))= \begin{cases} 2^{-(N-1)}\displaystyle\sum_{\substack{u\in\{0,1\}^N\\u_i=x,\ u_{<i}=v}} \prod_{k<N}W_{p(u)_k}(h_k,h'_k),&v=v',\\ 0,&v\ne v', \end{cases}$$

where $v$ has length $i$, $h$ has length $N$ over the marginal's index type, and $p(u)_k=\sum_j a_{jk}u_j\pmod2$, with $a_{jk}=1$ precisely when every $1$-bit of $k$ appears at a reversed $1$-bit position of $j$, using length-$n$ binary representations. The function $f(X,Y)$ is $\operatorname{Re}\operatorname{tr}\sqrt{\sqrt X\,Y\sqrt X}$. Both threshold equalities are included, and $n=0$ is included.

QAlgorithms.Papers.Independent.Intakethird100.P10.badSet

For any finite type $H$ with decidable equality, any pair $W=(W_0,W_1)$ of complex $H\times H$ matrices, any natural number $n$, and any real $\beta$, put $N=2^n$. The defined finite set consists exactly of indices $i\in\{0,\ldots,N-1\}$ satisfying

$$2^{-N^\beta} \le \operatorname{Re}\operatorname{tr} \sqrt{\sqrt{S_{i,0}}\,S_{i,1}\sqrt{S_{i,0}}}.$$

All matrix square roots mean the total real continuous functional calculus of $t\mapsto\sqrt t$, which returns zero on non-Hermitian matrices. The matrices $S_{i,x}$, indexed by Boolean prefixes $p,q$ of length $i$ and words $a,b\in H^N$, are zero when $p\ne q$, and otherwise have entries

$$S_{i,x}((p,a),(p,b)) = 2^{-(N-1)} \sum_{\substack{u\in\{0,1\}^{N}\\u_i=x\\u_j=p_j\ (j<i)}} \prod_{k=0}^{N-1}(W_{v_k})_{a_k,b_k}, \qquad v_k=\sum_{j=0}^{N-1}u_jc_n(j,k)\pmod2,$$

where $c_n(j,k)=1$ exactly when every nonzero bit $t$ of $k$'s length-$n$, most-significant-first binary representation corresponds to a nonzero bit $n-1-t$ of $j$'s representation. Equality with the threshold is included. No density-matrix assumption on $W$ or restriction on $\beta$ is imposed. At $n=0$, the sole index is included exactly when the root-fidelity expression for $W_0,W_1$ is at least $1/2$; if $H$ is empty, the set is empty.

QAlgorithms.Papers.Independent.Intakethird100.P10.basisColumn

For every finite index type $H$ with decidable equality, every unitary complex matrix $U$ indexed by $H$, and every $x\in H$, define the vector $v_x\in\mathbb C^H$ by $v_x(a)=U_{a,x}$ for every $a\in H$; thus $v_x$ is column $x$ of $U$, viewed with the Euclidean norm. No separate nonemptiness assumption is imposed, although specifying $x$ requires an element of $H$.

QAlgorithms.Papers.Independent.Intakethird100.P10.bellBobOutput

For arbitrary finite sets $B,E$, any complex matrix $U$ with rows indexed by $B\times E$ and Boolean columns, and any unitary $2\times2$ matrix $Q$, this declaration defines a matrix $\Omega$ indexed by $\{0,1\}\times B$, with entries

$$\Omega((x,b),(y,b')) =\frac12\sum_{e\in E} \left(\sum_{a\in\{0,1\}}U((b,e),a)Q(a,x)\right) \overline{\left(\sum_{a\in\{0,1\}}U((b',e),a)Q(a,y)\right)}.$$

No isometry assumption on $U$ or nonemptiness assumption on $B,E$ is made. An empty $E$ makes all entries zero.

QAlgorithms.Papers.Independent.Intakethird100.P10.circuitAction

For every natural number $N$, every finite list $C=[g_1,\ldots,g_\ell]$ of gate descriptions on indices $0,\ldots,N-1$, and every Boolean word $u$ of length $N$, this declaration defines the circuit action by starting with $u$ and applying the listed gates in order, from $g_1$ through $g_\ell$. Each controlled-NOT description has distinct control $c$ and target $t$, and replaces the current target bit by the exclusive OR of the current control and target bits; each swap exchanges its two current bits, allowing equal indices, in which case it leaves the word unchanged. The empty list acts as the identity. This includes $N=0$, where the list must be empty and the unique empty word is unchanged.

QAlgorithms.Papers.Independent.Intakethird100.P10.circuitOperator

For every natural number $N$, including $N=0$, and every finite list $C$ of gates on $N$ Boolean wires, define a complex matrix indexed by bit strings $u,v\in\{0,1\}^{N}$ by

$$(C_{\mathrm{op}})_{v,u}= \begin{cases} 1,&v=C(u),\\ 0,&\text{otherwise}. \end{cases}$$

Here $C(u)$ is obtained by applying the listed gates in order: a controlled-NOT has distinct control and target wires and replaces the target bit by its XOR with the control bit; a swap exchanges its two specified bits, which may be the same bit. An empty list acts as the identity.

QAlgorithms.Papers.Independent.Intakethird100.P10.cloningEnvironment

For every natural number $m$, every unitary complex $m\times m$ matrix $U$, and every Boolean $x$, let $u_j$ denote column $j$ of $U$. This defines

$$\rho_x=\sum_{i=0}^{m-1}\frac{i+1}{m(m+1)/2}\, u_{r_x(i)}u_{r_x(i)}^\dagger, \qquad r_{\mathrm{false}}(i)=i,\quad r_{\mathrm{true}}(i)=m-1-i.$$

Each outer product has entries $u_{r_x(i)}(a)\overline{u_{r_x(i)}(b)}$. The definition includes $m=0$, when the sum is empty and the resulting matrix is the zero matrix on the empty index set; real division by zero is defined to be zero.

QAlgorithms.Papers.Independent.Intakethird100.P10.cloningNormalization

For every natural number $m$, this defines the real number

$$c_m=\frac{m(m+1)}2.$$

In particular, $c_0=0$.

QAlgorithms.Papers.Independent.Intakethird100.P10.combinedOutput

For any type $H$, any pair $W=(W_0,W_1)$ of complex $H\times H$ matrices, any natural number $n$, and any Boolean word $u$ of length $N=2^n$, define a complex matrix indexed by functions $a,b:\{0,\ldots,N-1\}\to H$ by

$$C_{W,n,u}(a,b)=\prod_{k=0}^{N-1}(W_{v_k})_{a_k,b_k}.$$

Here $v_k=\sum_{j=0}^{N-1}u_jc_n(j,k)\pmod 2$, where $c_n(j,k)=1$ precisely when every nonzero bit $t$ of $k$'s length-$n$, most-significant-first binary representation corresponds to a nonzero bit $n-1-t$ of $j$'s representation. No finiteness assumption on $H$, and no positivity or normalization assumption on $W$, is imposed. When $n=0$, this matrix has entries $(W_{u_0})_{a_0,b_0}$.

QAlgorithms.Papers.Independent.Intakethird100.P10.dephasingComplement

For every real $p$ and every complex matrix $\sigma$ indexed by the two Boolean values, this defines a map $\mathcal C_{p,\sigma}$ on all complex matrices $\rho$ with those indices as follows: set $K_0=\sqrt{1-p}\,I$ and $K_1=\sqrt p\,\sigma$, with $0$ denoting false and $1$ denoting true; then

$$\bigl(\mathcal C_{p,\sigma}(\rho)\bigr)_{b,c} =\operatorname{tr}(K_b\rho K_c^\dagger) \qquad(b,c\in\{0,1\}).$$

No restriction on $p$, $\sigma$, or $\rho$ is imposed. The square roots are real square roots, which equal zero for negative arguments.

QAlgorithms.Papers.Independent.Intakethird100.P10.dephasingDiagonal

For every real $p$, this defines the complex matrix indexed in the order false, true by

$$D_p=\begin{pmatrix}1-p&0\\0&p\end{pmatrix}.$$

There is no assumption that $p$ lies between zero and one.

QAlgorithms.Papers.Independent.Intakethird100.P10.detectedJumpComplement

For every real number $\gamma$, define a function on all complex $2\times2$ matrices, with rows and columns ordered as false, true, by

$$\mathcal J_\gamma(\rho)= \begin{pmatrix} \operatorname{tr}\rho-\gamma\rho_{11}&0\\ 0&\gamma\rho_{11} \end{pmatrix}.$$

No restriction on $\gamma$ and no positivity or normalization assumption on $\rho$ is imposed.

QAlgorithms.Papers.Independent.Intakethird100.P10.dilationBob

For arbitrary finite sets $B,E$, any complex matrix $U$ with rows indexed by $B\times E$ and Boolean columns, and any unitary $2\times2$ matrix $Q$, this declaration defines a Boolean-indexed family of matrices on $B$. For $x\in\{0,1\}$ and $b,b'\in B$, its entries are

$$\operatorname{dilationBob}(U,Q)_x(b,b') =\sum_{e\in E} \left(\sum_{a\in\{0,1\}}U((b,e),a)Q(a,x)\right) \overline{\left(\sum_{a\in\{0,1\}}U((b',e),a)Q(a,x)\right)}.$$

There is no isometry or normalization assumption on $U$, and neither finite set is required to be nonempty. In particular, when $E$ is empty the sum is zero.

QAlgorithms.Papers.Independent.Intakethird100.P10.dilationEve

For arbitrary finite sets $B,E$, any complex matrix $U$ with rows indexed by $B\times E$ and Boolean columns, and any unitary $2\times2$ matrix $Q$, this declaration defines a Boolean-indexed family of matrices on $E$. For $x\in\{0,1\}$ and $e,e'\in E$, its entries are

$$\operatorname{dilationEve}(U,Q)_x(e,e') =\sum_{b\in B} \left(\sum_{a\in\{0,1\}}U((b,e),a)Q(a,x)\right) \overline{\left(\sum_{a\in\{0,1\}}U((b,e'),a)Q(a,x)\right)}.$$

No isometry or normalization assumption on $U$ is imposed, and $B,E$ may be empty. In particular, an empty $B$ makes this sum zero.

QAlgorithms.Papers.Independent.Intakethird100.P10.dilationLetter

For arbitrary finite sets $B,E$, any complex matrix $U$ with rows indexed by $B\times E$ and columns indexed by $\{0,1\}$, any unitary $2\times2$ matrix $Q$, and any Boolean value $x$, define $v_x(b,e)=\sum_{a\in\{0,1\}}U((b,e),a)Q(a,x)$. The declaration defines a matrix on $B\times E$ by

$$\operatorname{dilationLetter}(U,Q,x)((b,e),(b',e')) =v_x(b,e)\,\overline{v_x(b',e')}.$$

No isometry condition on $U$, normalization of $v_x$, or nonemptiness of $B,E$ is required; if either set is empty, this is a matrix on an empty index set.

QAlgorithms.Papers.Independent.Intakethird100.P10.erasureData

For every natural number $d$ and every complex matrix $\rho$ indexed by $\{0,\ldots,d-1\}$, this defines a matrix $\widetilde{\rho}$ indexed by those same indices together with an additional index $\varnothing$, with entries $\widetilde{\rho}_{a,b}=\rho_{a,b}$ for ordinary indices $a,b$, and zero whenever either index is $\varnothing$. No positivity or normalization is required of $\rho$. For $d=0$, the resulting matrix has only the additional index and is zero.

QAlgorithms.Papers.Independent.Intakethird100.P10.frozenSet

For finite types $B,E$ with decidable equality, a wiretap datum $V$, a natural number $n$, and a real $\beta$, this defines the set of indices $i<2^n$ satisfying

$$1-\tau<f(W_{n,i,0}^E,W_{n,i,1}^E) \quad\text{and}\quad \tau\le f(W_{n,i,0}^B,W_{n,i,1}^B), \qquad \tau=2^{-(2^n)^\beta}.$$

The datum $V$ consists of joint positive semidefinite trace-one matrices $\rho_x$, their marginals $W_x^B(b,b')=\sum_e\rho_x((b,e),(b',e))$ and $W_x^E(e,e')=\sum_b\rho_x((b,e),(b,e'))$, and a finite Kraus channel $D(X)=\sum_jK_jXK_j^\dagger$, $\sum_jK_j^\dagger K_j=I_B$, such that $W_x^E=D(W_x^B)$, with $W_0^E,W_1^E$ commuting. For either marginal pair $W$, set $N=2^n$; $W_{n,i,x}$ is indexed by $(v,h)$, where $v$ has $i$ Boolean entries and $h$ has $N$ entries in the marginal's index type, with

$$W_{n,i,x}((v,h),(v',h'))= \begin{cases} 2^{-(N-1)}\displaystyle\sum_{\substack{u\in\{0,1\}^N\\u_i=x,\ u_{<i}=v}} \prod_{k<N}W_{p(u)_k}(h_k,h'_k),&v=v',\\ 0,&v\ne v'. \end{cases}$$

Here $p(u)_k=\sum_j a_{jk}u_j\pmod2$, and $a_{jk}=1$ exactly when each $1$-bit of $k$'s length-$n$ binary representation occurs at a reversed $1$-bit position of $j$'s representation. The function $f$ is $\operatorname{Re}\operatorname{tr}\sqrt{\sqrt X\,Y\sqrt X}$. Equality at the $B$ threshold is included, equality at the $E$ threshold is excluded, and $n=0$ and arbitrary real $\beta$ are allowed.

QAlgorithms.Papers.Independent.Intakethird100.P10.goodSet

For any finite type $H$ with decidable equality, any pair $W=(W_0,W_1)$ of complex $H\times H$ matrices, any natural number $n$, and any real $\beta$, put $N=2^n$. The defined finite set consists exactly of indices $i\in\{0,\ldots,N-1\}$ for which

$$\operatorname{Re}\operatorname{tr} \sqrt{\sqrt{S_{i,0}}\,S_{i,1}\sqrt{S_{i,0}}} < 2^{-N^\beta}.$$

All matrix square roots here mean the total real continuous functional calculus of $t\mapsto\sqrt t$, which returns zero on non-Hermitian matrices. The matrices $S_{i,x}$, indexed by Boolean prefixes $p,q$ of length $i$ and words $a,b\in H^N$, are zero when $p\ne q$, and otherwise have entries

$$S_{i,x}((p,a),(p,b)) = 2^{-(N-1)} \sum_{\substack{u\in\{0,1\}^{N}\\u_i=x\\u_j=p_j\ (j<i)}} \prod_{k=0}^{N-1}(W_{v_k})_{a_k,b_k}, \qquad v_k=\sum_{j=0}^{N-1}u_jc_n(j,k)\pmod2,$$

where $c_n(j,k)=1$ exactly when every nonzero bit $t$ of $k$'s length-$n$, most-significant-first binary representation corresponds to a nonzero bit $n-1-t$ of $j$'s representation. No density-matrix assumption on $W$ or restriction on $\beta$ is imposed. At $n=0$, the sole index is included exactly when the same root-fidelity expression for $W_0,W_1$ is strictly below $1/2$; if $H$ is empty, every index is included.

QAlgorithms.Papers.Independent.Intakethird100.P10.informationSet

For finite types $B,E$ with decidable equality, a wiretap datum $V$, a natural number $n$, and a real $\beta$, this defines the set of indices $i<2^n$ satisfying both

$$1-\tau<f(W_{n,i,0}^E,W_{n,i,1}^E) \quad\text{and}\quad f(W_{n,i,0}^B,W_{n,i,1}^B)<\tau, \qquad \tau=2^{-(2^n)^\beta}.$$

Here $V$ supplies joint positive semidefinite trace-one matrices $\rho_x$, their marginals $W_x^B(b,b')=\sum_e\rho_x((b,e),(b',e))$ and $W_x^E(e,e')=\sum_b\rho_x((b,e),(b,e'))$, and a finite Kraus channel $D(X)=\sum_jK_jXK_j^\dagger$, $\sum_jK_j^\dagger K_j=I_B$, satisfying $W_x^E=D(W_x^B)$; the two $E$ marginals commute. For either marginal pair $W$, write $N=2^n$: its synthesized matrix has entries

$$W_{n,i,x}((v,h),(v',h'))= \begin{cases} 2^{-(N-1)}\displaystyle\sum_{\substack{u\in\{0,1\}^N\\u_i=x,\ u_{<i}=v}} \prod_{k<N}W_{p(u)_k}(h_k,h'_k),&v=v',\\ 0,&v\ne v', \end{cases}$$

where $v,v'$ have length $i$, $h,h'$ are length-$N$ words over the marginal's index type, and $p(u)_k=\sum_j a_{jk}u_j\pmod2$, with $a_{jk}=1$ exactly when every $1$-bit of the length-$n$ binary representation of $k$ is a $1$-bit at the reversed position in that of $j$. Finally $f(X,Y)=\operatorname{Re}\operatorname{tr}\sqrt{\sqrt X\,Y\sqrt X}$. Both inequalities are strict; $n=0$ and every real $\beta$ are included.

QAlgorithms.Papers.Independent.Intakethird100.P10.leafProbability

For every natural number $n$, including $n=0$, and every finite subset $S$ of $\{0,\ldots,2^n-1\}$, this defines the real number $|S|/2^n$. Thus the empty set has value $0$, the full set has value $1$, and the denominator is always positive; when $n=0$, the ambient index set has one element.

QAlgorithms.Papers.Independent.Intakethird100.P10.minusChannel

For any type $H$ and any Boolean-indexed family $W$ of complex matrices indexed by $H$, define a Boolean-indexed family $M$ of matrices indexed by $H\times H$ by

$$M(\mathrm{false})=\frac12\bigl(W(\mathrm{false})\otimes W(\mathrm{false}) +W(\mathrm{true})\otimes W(\mathrm{true})\bigr),\qquad M(\mathrm{true})=\frac12\bigl(W(\mathrm{false})\otimes W(\mathrm{true}) +W(\mathrm{true})\otimes W(\mathrm{false})\bigr).$$

The tensor product has entries $(A\otimes B)_{(a,c),(b,d)}=A_{a,b}B_{c,d}$. No positivity, trace, normalization, finiteness, or nonemptiness hypothesis is required.

QAlgorithms.Papers.Independent.Intakethird100.P10.polarCoefficient

For every natural number $n$, put $N=2^n$, and let $j,k\in\{0,\ldots,N-1\}$. Write $b_t(a)$ for bit $t$ of the length-$n$ binary representation of $a$, ordered from most significant to least significant, so that $a=\sum_{t=0}^{n-1}b_t(a)2^{n-1-t}$. The Boolean coefficient $c_n(j,k)$ is true exactly when

$$\forall t\in\{0,\ldots,n-1\},\qquad b_t(k)=1\ \Longrightarrow\ b_{n-1-t}(j)=1.$$

It is false otherwise. For $n=0$, the only indices are $j=k=0$, and the condition is vacuous, so the coefficient is true.

QAlgorithms.Papers.Independent.Intakethird100.P10.polarOperator

For every natural number $n$, define a complex matrix indexed by Boolean strings of length $2^n$ by

$$(P_n)_{v,u}= \begin{cases} 1,&v=T_n(u),\\ 0,&\text{otherwise}. \end{cases}$$

For indices $0\le j,k<2^n$, let $j_t,k_t$ denote their $n$-bit binary digits, with position $0$ the most significant digit, and set $a_{j,k}=1$ exactly when, for every $0\le t<n$, $k_t=1$ implies $j_{n-1-t}=1$. Then $T_n(u)_k$ is the parity of the number of indices $j$ for which $u_j=1$ and $a_{j,k}=1$. When $n=0$, the digit condition is vacuous, and this transformation is the identity on the single Boolean wire.

QAlgorithms.Papers.Independent.Intakethird100.P10.polarThreshold

For every natural number $n$ and every real number $\beta$, define

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

using real exponentiation for the powers with real exponents. There is no restriction on $\beta$. The threshold lies strictly between $0$ and $1$; for $n=0$, it equals $1/2$ for every $\beta$.

QAlgorithms.Papers.Independent.Intakethird100.P10.polarWord

For every natural number $n$, put $N=2^n$, and let $u:\{0,\ldots,N-1\}\to\{0,1\}$ be a Boolean word. Its defined transformed word $v$ has

$$v_k=\left(\sum_{j=0}^{N-1}u_j c_n(j,k)\right)\bmod 2,$$

where $c_n(j,k)=1$ exactly when every nonzero bit $t$ of $k$'s length-$n$, most-significant-first binary representation corresponds to a nonzero bit $n-1-t$ of $j$'s representation, and $c_n(j,k)=0$ otherwise. Equivalently, $v_k$ is true exactly when an odd number of indices $j$ have both $u_j$ true and this bit condition satisfied. For $n=0$, the word has one coordinate and the transformation is the identity.

QAlgorithms.Papers.Independent.Intakethird100.P10.poorSet

For any finite type $H$ with decidable equality, any pair $W_0,W_1$ of complex matrices indexed by $H$, any natural number $n$, and any real $\beta$, this defines the finite set

$$\left\{i\in\{0,\ldots,2^n-1\}:1-2^{-(2^n)^\beta}<f(W_{n,i,0},W_{n,i,1})\right\},$$

where $f(X,Y)=\operatorname{Re}\operatorname{tr}\sqrt{\sqrt X\,Y\sqrt X}$, with square roots interpreted through the continuous functional calculus using the real square-root function. To specify the synthesized matrices, put $N=2^n$, and let $b_t(j)$ be bit $t$ of the length-$n$, most-significant-bit-first binary representation of $j$. Define $a_{jk}=1$ exactly when $b_t(k)=1$ implies $b_{n-1-t}(j)=1$ for every $t<n$, and define $p(u)_k=\sum_j a_{jk}u_j\pmod 2$ for a Boolean word $u$ of length $N$. The matrix $W_{n,i,x}$ is indexed by pairs $(v,h)$, with $v$ a Boolean word of length $i$ and $h\in H^N$, and its entries are

$$W_{n,i,x}((v,h),(v',h'))= \begin{cases} 2^{-(N-1)}\displaystyle\sum_{\substack{u\in\{0,1\}^N\\u_i=x,\ u_{<i}=v}} \prod_{k=0}^{N-1}W_{p(u)_k}(h_k,h'_k),&v=v',\\ 0,&v\ne v'. \end{cases}$$

There is no density-matrix assumption on $W$ and no restriction on $\beta$. The case $n=0$ is included and has one possible index.

QAlgorithms.Papers.Independent.Intakethird100.P10.pureCQ

For any type $H$ and any two complex coordinate vectors $\psi_0,\psi_1$ indexed by $H$, define a Boolean-indexed family of complex matrices by

$$W(x)_{a,b}=\psi_x(a)\,\overline{\psi_x(b)}, \qquad \psi_{\mathrm{false}}=\psi_0,\quad \psi_{\mathrm{true}}=\psi_1.$$

No normalization, finiteness, or nonemptiness assumption on $H$ is imposed.

QAlgorithms.Papers.Independent.Intakethird100.P10.randomizationSet

For finite types $B,E$ with decidable equality, a wiretap datum $V$, any natural number $n$, and any real $\beta$, this defines the set of indices $i<2^n$ satisfying

$$f(W_{n,i,0}^E,W_{n,i,1}^E)\le1-\tau \quad\text{and}\quad f(W_{n,i,0}^B,W_{n,i,1}^B)<\tau, \qquad \tau=2^{-(2^n)^\beta}.$$

The datum $V$ includes joint positive semidefinite trace-one matrices $\rho_x$, marginals $W_x^B(b,b')=\sum_e\rho_x((b,e),(b',e))$ and $W_x^E(e,e')=\sum_b\rho_x((b,e),(b,e'))$, and a finite Kraus channel $D(X)=\sum_jK_jXK_j^\dagger$, $\sum_jK_j^\dagger K_j=I_B$, taking $W_x^B$ to $W_x^E$; the two $E$ marginals commute. For either marginal pair $W$, with $N=2^n$, its synthesized matrices are

$$W_{n,i,x}((v,h),(v',h'))= \begin{cases} 2^{-(N-1)}\displaystyle\sum_{\substack{u\in\{0,1\}^N\\u_i=x,\ u_{<i}=v}} \prod_{k<N}W_{p(u)_k}(h_k,h'_k),&v=v',\\ 0,&v\ne v', \end{cases}$$

where $v$ is a Boolean word of length $i$, $h$ is a length-$N$ word over the marginal's index type, and $p(u)_k=\sum_j a_{jk}u_j\pmod2$; $a_{jk}=1$ exactly when every $1$-bit of $k$'s length-$n$ binary representation is present at the reversed position in that of $j$. Here $f(X,Y)=\operatorname{Re}\operatorname{tr}\sqrt{\sqrt X\,Y\sqrt X}$. The $E$ threshold equality is included and the $B$ threshold equality is excluded; $n=0$ is allowed.

QAlgorithms.Papers.Independent.Intakethird100.P10.symmetricCoherentInformation

Let $B$ be a finite set with decidable equality and $E$ any finite set, let $U$ be a complex matrix with rows indexed by $B\times E$ and Boolean columns, and let $Q$ be a unitary $2\times2$ matrix. Define $v_x(b,e)=\sum_{a\in\{0,1\}}U((b,e),a)Q(a,x)$, and define a matrix on $\{0,1\}\times B$ by $\Omega((x,b),(y,b'))=\tfrac12\sum_e v_x(b,e)\overline{v_y(b',e)}$. Define its matrix on $B$ obtained by summing the Boolean diagonal blocks by $\Omega_B(b,b')=\sum_{x\in\{0,1\}}\Omega((x,b),(x,b'))$. Writing $S(X)=-\operatorname{Re}\operatorname{tr}(f(X))$, with $f(t)=t\log_2t$ applied by continuous functional calculus, the declaration defines

$$\operatorname{symmetricCoherentInformation}(U,Q)=S(\Omega_B)-S(\Omega).$$

Neither nonemptiness of $B,E$ nor an isometry or normalization condition on $U$ is required.

QAlgorithms.Papers.Independent.Intakethird100.P10.symmetricInformation

For any finite type $H$ with decidable equality and any pair $W=(W_0,W_1)$ of complex $H\times H$ matrices, define

$$I_{\mathrm{sym}}(W) = S\!\left(\frac{W_0+W_1}{2}\right) -\frac{S(W_0)+S(W_1)}{2}, \qquad S(M)=-\operatorname{Re}\operatorname{tr}\bigl(f[M]\bigr), \quad f(t)=t\log_2 t,$$

where $f[M]$ denotes the total real continuous functional calculus used for matrices. The real logarithm is total, with its value at zero defined as zero, and this functional calculus returns the zero matrix when its Hermitian applicability condition fails. No assumption that either $W_x$ is a density matrix is required. Empty $H$ is allowed, in which case the defined value is $0$.

QAlgorithms.Papers.Independent.Intakethird100.P10.synthesized

For any finite type $H$ with decidable equality, any pair $W=(W_0,W_1)$ of complex $H\times H$ matrices, any natural number $n$, and any $i\in\{0,\ldots,N-1\}$, where $N=2^n$, define a pair of matrices $S_0,S_1$ indexed by $\{0,1\}^{\,i}\times H^N$. For $x\in\{0,1\}$, prefixes $p,q\in\{0,1\}^{\,i}$, and $a,b\in H^N$, their entries are

$$S_x((p,a),(q,b)) = \begin{cases} \displaystyle 2^{-(N-1)} \sum_{\substack{u\in\{0,1\}^{N}\\u_i=x\\u_j=p_j\ (0\le j<i)}} \prod_{k=0}^{N-1}(W_{v_k})_{a_k,b_k}, & p=q,\\[6pt] 0,&p\ne q. \end{cases}$$

Here $v_k=\sum_{j=0}^{N-1}u_jc_n(j,k)\pmod 2$, and $c_n(j,k)=1$ exactly when every nonzero bit $t$ of $k$'s length-$n$, most-significant-first binary representation corresponds to a nonzero bit $n-1-t$ of $j$'s representation. The prefix condition is vacuous at $i=0$. No density-matrix hypothesis on $W$ is imposed. For $n=0$, $N=1$, $i=0$, and $S_x(((),a),((),b))=(W_x)_{a_0,b_0}$.

QAlgorithms.Papers.Independent.Intakethird100.P10.synthesizedDegrader

For any finite type $H$ with decidable equality, any type $K$, any function $D$ from complex $H\times H$ matrices to complex $K\times K$ matrices, any natural number $n$, and any $i\in\{0,\ldots,N-1\}$, where $N=2^n$, define a function $\widetilde D$ from matrices on $\{0,1\}^{\,i}\times H^N$ to matrices on $\{0,1\}^{\,i}\times K^N$ by

$$(\widetilde D X)((p,y),(q,y')) = \sum_{a\in H^N}\sum_{b\in H^N} X((p,a),(q,b)) \prod_{k=0}^{N-1} \bigl(D(E_{a_k,b_k})\bigr)_{y_k,y'_k},$$

where $p,q$ are Boolean prefixes of length $i$, $y,y'\in K^N$, and $E_{h,h'}$ has entry $1$ at $(h,h')$ and zero elsewhere. No linearity, positivity, or channel assumption on $D$, and no finiteness or decidable-equality assumption on $K$, is required. For $n=0$, the prefixes are empty and the product has one factor.