Definitions for Quantum Channel Simulation and the Channel's Smooth Max-Information

QAlgorithms.Papers.Independent.Intakethird100.P65.AllowedSimulationCode

For finite index types $A,B,C,D$, with decidable equality, an assistance label $o\in\{\mathrm{ns},\mathrm{nsPpt},\mathrm{ent}\}$, and an arbitrary matrix map $P:A\times C\to B\times D$, this predicate is defined by the following three alternatives. For $o=\mathrm{ns}$, $P$ must be a channel, and there must exist channels $F:A\to B$ and $G:C\to D$ such that, for every matrix $X$, $\operatorname{Tr}_D P(X)=F(\operatorname{Tr}_C X)$ and $\operatorname{Tr}_B P(X)=G(\operatorname{Tr}_A X)$. For $o=\mathrm{nsPpt}$, these same conditions must hold and $X\mapsto\Gamma_D(P(\Gamma_C X))$ must also be a channel, where partial transposition on the second factor means $(\Gamma X)_{(a,c),(a',c')}=X_{(a,c'),(a',c)}$. For $o=\mathrm{ent}$, there must exist positive integers $e,f$, a positive semidefinite trace-one matrix $\eta$ on $\mathrm{Fin}(e)\times\mathrm{Fin}(f)$, and channels $E:A\times\mathrm{Fin}(e)\to B$, $F:C\times\mathrm{Fin}(f)\to D$, such that

$$P(X)_{(b,d),(b',d')} =\sum_{\substack{i,j\in A,\ u,v\in C\\a,c<e,\ s,t<f}} X_{(i,u),(j,v)}\eta_{(a,s),(c,t)} E(|i,a\rangle\langle j,c|)_{b,b'} F(|u,s\rangle\langle v,t|)_{d,d'}$$

for all $X,b,d,b',d'$. In every alternative, “channel” means a finite Kraus map whose Kraus operators satisfy $\sum_\ell K_\ell^\dagger K_\ell=I$.

QAlgorithms.Papers.Independent.Intakethird100.P65.BipartiteNSOperation

For finite types $A,B,C,D$ with decidable equality and a function $P$ from complex matrices on $A\times C$ to complex matrices on $B\times D$, this predicate requires that $P$ be a finite Kraus channel and that there exist finite Kraus channels $F$ from matrices on $A$ to matrices on $B$ and $G$ from matrices on $C$ to matrices on $D$ such that, for every complex matrix $X$ on $A\times C$,

$$\operatorname{Tr}_{D}(P(X))=F(\operatorname{Tr}_{C}X), \qquad \operatorname{Tr}_{B}(P(X))=G(\operatorname{Tr}_{A}X).$$

A finite Kraus channel $H$ means that for some natural number $r$ and matrices $K_j$ from its input register to its output register, $\sum_{j<r}K_j^\dagger K_j=1$ and $H(Y)=\sum_{j<r}K_jYK_j^\dagger$ for every $Y$. Partial traces mean summing matching indices of the discarded register; for example, $(\operatorname{Tr}_C X)_{a,a'}=\sum_cX((a,c),(a',c))$. The two identities apply to all matrices, and empty register types and zero-length Kraus families are included whenever the equations permit them.

QAlgorithms.Papers.Independent.Intakethird100.P65.CommunicationRate

For finite index types $A,B$, with decidable equality, an assistance label $o$, an arbitrary matrix map $N:A\to B$, and a real number $r$, this predicate requires $r\ge0$ and states that, for every $e>0$ and every slack $s>0$, there exists a natural number $n_0$ such that every positive integer $n\ge n_0$ admits a positive integer $m$ satisfying

$$\varepsilon_o(N^{[n]},\operatorname{id}_m)\le e, \qquad (r-s)n\le\log_2 m.$$

The coordinatewise map is defined by $N^{[n]}(Y)_{y,y'}=\sum_{x,x'}Y_{x,x'}\prod_{i<n}N(|x_i\rangle\langle x_i'|)_{y_i,y_i'}$. The error $\varepsilon_o(N^{[n]},\operatorname{id}_m)$ is the real infimum over allowed maps $P:\mathrm{Fin}(m)\times B^n\to A^n\times\mathrm{Fin}(m)$ of

$$\frac12\sup_{\|X\|_1\le1} \left\|(\operatorname{id}_m\otimes(\mathcal W_{N^{[n]}}(P)-\operatorname{id}_m))(X)\right\|_1,$$

where $X$ ranges over all matrices on $\mathrm{Fin}(m)\times\mathrm{Fin}(m)$, amplification is blockwise, and $\mathcal W_S(P)(Y)_{b,d}=\sum_{a,c,u,v}S(|a\rangle\langle c|)_{u,v}P(Y\otimes|u\rangle\langle v|)_{(a,b),(c,d)}$. Here $\|Z\|_1=\operatorname{Re}\operatorname{tr}\sqrt{Z^\dagger Z}$. Allowed maps are channels with both marginal nonsignalling conditions for $\mathrm{ns}$, such channels whose second-factor partial-transpose conjugates are also channels for $\mathrm{nsPpt}$, or maps implemented by separate local channels using a shared finite-dimensional density matrix for $\mathrm{ent}$; channels have finite complete Kraus representations. The error infimum need not be attained and equals $0$ if empty. No channel assumption is imposed on $N$; zero block length is excluded, and slack larger than $r$ is included.

QAlgorithms.Papers.Independent.Intakethird100.P65.Constant

For finite index types $A,B$ with decidable equality and an arbitrary function $M$ from complex matrices indexed by $A$ to complex matrices indexed by $B$, this property means that there exists a positive semidefinite matrix $\sigma$ indexed by $B$ with complex trace exactly $1$ such that, for every complex matrix $X$ indexed by $A$, $M(X)=\operatorname{tr}(X)\sigma$. There is no separate assumption that $M$ is a channel. Empty index types are not excluded: if $B$ is empty, no such trace-one $\sigma$ exists.

QAlgorithms.Papers.Independent.Intakethird100.P65.EntCode

For finite index types $A,B,C,D$, with decidable equality, and an arbitrary map $P$ from complex matrices on $A\times C$ to complex matrices on $B\times D$, this predicate means that there exist positive natural numbers $e,f$, a positive semidefinite matrix $\eta$ on $\{0,\ldots,e-1\}\times\{0,\ldots,f-1\}$ with trace $1$, and channels $E:A\times\{0,\ldots,e-1\}\to B$ and $F:C\times\{0,\ldots,f-1\}\to D$, such that, for every complex matrix $X$ on $A\times C$ and every pair of output indices $(b_B,b_D),(d_B,d_D)$,

$$P(X)_{(b_B,b_D),(d_B,d_D)} = \sum_{\substack{i,j\in A,\ u,v\in C\\a,c<e,\ s,t<f}} X_{(i,u),(j,v)}\eta_{(a,s),(c,t)} E\!\left(|i,a\rangle\langle j,c|\right)_{b_B,d_B} F\!\left(|u,s\rangle\langle v,t|\right)_{b_D,d_D}.$$

Here a channel is a map admitting a finite Kraus representation $X\mapsto\sum_\ell K_\ell X K_\ell^\dagger$ with $\sum_\ell K_\ell^\dagger K_\ell=I$, and $|x\rangle\langle y|$ denotes the matrix with its only nonzero entry equal to $1$ at $(x,y)$. The state $\eta$ may be entangled or separable; the identity is required for all matrices $X$, without positivity or normalization restrictions.

QAlgorithms.Papers.Independent.Intakethird100.P65.IteratedLimit

For a function $f:\mathbb R\times\mathbb N\to\mathbb R$ and a real number $v$, this property means that there exists a function $L:\mathbb R\to\mathbb R$ such that, for every real $e$ with $0<e<1$, the sequence $f(e,n+1)$ converges to $L(e)$ as $n\to\infty$, and $L(e)$ converges to $v$ as $e\to0$ through strictly positive real values. The sequence starts with $f(e,1)$; no condition is imposed on $f(e,0)$, on $f(e,n)$ for $e\notin(0,1)$, or on the value $L(0)$.

QAlgorithms.Papers.Independent.Intakethird100.P65.NSChoi

For finite index types $A,B,C,D$ with decidable equality and a complex matrix $Z$ indexed by $(A\times C)\times(B\times D)$, this property requires that $Z$ be positive semidefinite and that all three following identities hold:

$$\begin{aligned} \sum_{a\in B}\sum_{b\in D} Z_{((i,u),(a,b)),\,((j,v),(a,b))} &=\begin{cases}1&i=j\text{ and }u=v,\\0&\text{otherwise},\end{cases}\\ \sum_{a\in B} Z_{((i,u),(a,b)),\,((j,v),(a,d))} &=\begin{cases} |A|^{-1}\displaystyle\sum_{k\in A}\sum_{a\in B} Z_{((k,u),(a,b)),\,((k,v),(a,d))}&i=j,\\ 0&i\ne j, \end{cases}\\ \sum_{b\in D} Z_{((i,u),(a,b)),\,((j,v),(c,b))} &=\begin{cases} |C|^{-1}\displaystyle\sum_{w\in C}\sum_{b\in D} Z_{((i,w),(a,b)),\,((j,w),(c,b))}&u=v,\\ 0&u\ne v. \end{cases} \end{aligned}$$

The first identity is required for every $i,j\in A$ and $u,v\in C$; the second additionally for every $b,d\in D$; and the third additionally for every $a,c\in B$. The cardinalities and their inverses are interpreted in $\mathbb C$. No index type is assumed nonempty: empty sums are $0$, the inverse of $0$ is $0$, and universally quantified identities with an empty variable domain are vacuous.

QAlgorithms.Papers.Independent.Intakethird100.P65.PPTCode

For finite types $A,B,C,D$ with decidable equality and an arbitrary function $P$ from complex matrices on $A\times C$ to complex matrices on $B\times D$, let $T_C$ and $T_D$ transpose the second register:

$$(T_CX)((a,c),(a',c'))=X((a,c'),(a',c)), \qquad (T_DY)((b,d),(b',d'))=Y((b,d'),(b',d)).$$

This predicate says that $X\mapsto T_D(P(T_CX))$ is a finite Kraus channel: there exist a natural number $r$ and matrices $K_j\in\mathbb C^{(B\times D)\times(A\times C)}$ such that

$$\sum_{j<r}K_j^\dagger K_j=1, \qquad T_D(P(T_CX))=\sum_{j<r}K_jXK_j^\dagger \quad\text{for every }X.$$

There is no separate requirement here that $P$ itself be a channel. Empty register types and $r=0$ are included whenever these equations hold.

QAlgorithms.Papers.Independent.Intakethird100.P65.PermutationCovariantChannel

For finite register types $A,B$ with decidable equality, a natural number $n$, and a function $T$ from complex matrices on $A^n$ to complex matrices on $B^n$, this predicate means that $T$ has a finite Kraus representation

$$T(X)=\sum_{j=0}^{m-1}K_jXK_j^\dagger, \qquad \sum_{j=0}^{m-1}K_j^\dagger K_j=I_{A^n},$$

for some natural number $m$ and matrices $K_j:B^n\times A^n\to\mathbb C$, and that for every permutation $\pi$ of the $n$ coordinates and every complex matrix $X$,

$$T(P_\pi X)=P_\pi(T(X)), \qquad (P_\pi X)(x,y)=X(x\circ\pi,y\circ\pi),$$

where the latter operation uses the appropriate input or output register. The covariance condition applies to all matrices, not just density matrices. No nonemptiness assumption on $A,B$ or positivity assumption on $n$ is included; for $n=0$, the covariance condition is automatic.

QAlgorithms.Papers.Independent.Intakethird100.P65.SimulationAssistance

This declares a type with exactly three distinct values, named $\mathrm{ns}$, $\mathrm{nsPpt}$, and $\mathrm{ent}$, and supplies a decision procedure for equality between its values. This declaration itself imposes no mathematical conditions on maps or states.

QAlgorithms.Papers.Independent.Intakethird100.P65.SimulationRate

For finite index types $A,B$, with decidable equality, an assistance label $o$, an arbitrary matrix map $N:A\to B$, and a real number $r$, this predicate requires $r\ge0$ and states that, for every error tolerance $e>0$ and every slack $s>0$, there exists a natural number $n_0$ such that every positive integer $n\ge n_0$ admits a positive integer $m$ with

$$\varepsilon_o(\operatorname{id}_m,N^{[n]})\le e, \qquad \log_2 m\le(r+s)n.$$

Here $N^{[n]}$ is the map on $n$-coordinate registers defined entrywise by

$$N^{[n]}(Y)_{y,y'} =\sum_{x,x'}Y_{x,x'}\prod_{i=0}^{n-1} N(|x_i\rangle\langle x_i'|)_{y_i,y_i'},$$

and $\varepsilon_o(\operatorname{id}_m,N^{[n]})$ is the real infimum, over allowed $P:A^n\times\mathrm{Fin}(m)\to\mathrm{Fin}(m)\times B^n$, of one half the trace-norm supremum of the blockwise amplification of $\mathcal L_m(P)-N^{[n]}$ on all matrices of trace norm at most $1$, with reference register $A^n$, where $\mathcal L_m(P)(Y)_{b,b'}=\sum_{u,v<m}P(Y\otimes|u\rangle\langle v|)_{(u,b),(v,b')}$. Allowed maps are channels with both marginal nonsignalling conditions for $\mathrm{ns}$; additionally their second-factor partial-transpose conjugates are channels for $\mathrm{nsPpt}$; or they arise from a shared finite-dimensional density matrix and separate local channels for $\mathrm{ent}$. Channels admit finite complete Kraus representations, and $\|Z\|_1=\operatorname{Re}\operatorname{tr}\sqrt{Z^\dagger Z}$. The error infimum need not be attained and has value $0$ if empty. The threshold may depend on $e,s$; $n=0$ is excluded, while $m=1$ is permitted.

QAlgorithms.Papers.Independent.Intakethird100.P65.StateBall

For a finite type $A$ with decidable equality, complex matrices $\rho,\sigma$ indexed by $A$, and any real $e$, this predicate means that $\sigma$ is positive semidefinite, $\operatorname{Re}\operatorname{Tr}\sigma\le1$, and

$$\sqrt{1-\left(F(\rho,\sigma)+ \sqrt{(1-\operatorname{Re}\operatorname{Tr}\rho)(1-\operatorname{Re}\operatorname{Tr}\sigma)}\right)^2}\le e, \qquad F(\rho,\sigma)=\operatorname{Re}\operatorname{Tr} S\!\left(S(\rho)\sigma S(\rho)\right),$$

where $S(X)$ denotes applying the real square-root function to $X$ by continuous functional calculus. There is no positivity or normalization assumption on $\rho$; $\sigma=0$ is permitted. Every real square root uses the convention that the square root of a negative number is zero. In particular, a negative $e$ makes the predicate false.

QAlgorithms.Papers.Independent.Intakethird100.P65.ZeroErrorWitnessPair

For finite types $A,B$ with decidable equality, a map $N:\mathbb C^{A\times A}\to\mathbb C^{B\times B}$, a matrix $V\in\mathbb C^{B\times B}$, and a matrix $X\in\mathbb C^{(A\times B)\times(A\times B)}$, this predicate asserts the following six conditions. Define the unnormalized Choi matrix by $J_N((a,b),(a',b'))=N(E_{aa'})(b,b')$, where $E_{aa'}$ has a single entry $1$ at $(a,a')$, and define

$$z(N)=\inf\left\{\operatorname{Re}\operatorname{tr}W: W=W^\dagger,\quad I_A\otimes W-J_N\succeq0\right\}.$$

Then the required conditions are

$$V=V^\dagger,\qquad I_A\otimes V-J_N\succeq0,\qquad X\succeq0,\qquad I_B-\operatorname{tr}_A X\succeq0,\qquad \operatorname{Re}\operatorname{tr}V=z(N),\qquad \operatorname{Re}\operatorname{tr}(J_NX)=z(N),$$

where $(\operatorname{tr}_A X)(b,b')=\sum_{a\in A}X((a,b),(a,b'))$. No channel assumption on $N$, positivity assumption on $V$, or normalization assumption on $X$ is separately required. Empty finite types are not excluded; empty sums and identity matrices have their usual zero-dimensional meanings. The infimum is the total real-valued infimum used in the declaration, which is $0$ for an empty set or a set unbounded below.

QAlgorithms.Papers.Independent.Intakethird100.P65.basisDepolarizing

For every finite type $A$ with decidable equality and every real $p$, this defines a map on complex square matrices indexed by $A$ by

$$X\longmapsto (1-p)X+\frac{p\,\operatorname{Tr}X}{|A|}I_A.$$

The input $X$ is arbitrary, and $p$ is not restricted to $[0,1]$. The type $A$ may be empty; division by its zero cardinality then has the total-field value zero.

QAlgorithms.Papers.Independent.Intakethird100.P65.channelInfo

For finite types $A,B$ with decidable equality and any function $N:\mathbb C^{A\times A}\to\mathbb C^{B\times B}$, write $d=|A|$ and define a matrix $R$ indexed by $A\times B$ through

$$R((a,b),(a',b'))= N(d^{-1}E_{a,a'})_{b,b'},$$

where $E_{a,a'}$ has entry $1$ at $(a,a')$ and zero elsewhere, and $d^{-1}$ is interpreted in $\mathbb C$. Let $R_A(a,a')=\sum_bR((a,b),(a',b))$. The returned real number is the real conversion of

$$\inf\left\{\ell\in\mathbb R\ \middle|\ \exists\sigma\in\mathbb C^{B\times B},\ \sigma\succeq0,\ \operatorname{Tr}\sigma=1,\ 2^\ell(R_A\otimes\sigma)-R\succeq0 \right\}.$$

This infimum is taken in the extended reals, and either infinite value converts to zero. No linearity or channel assumption is imposed on $N$, and empty types are included.

QAlgorithms.Papers.Independent.Intakethird100.P65.channelMutualInfo

For finite index types $A,B$, with decidable equality, and an arbitrary matrix map $N:A\to B$, this defines the real supremum

$$\sup_{\rho\ge0,\ \operatorname{tr}\rho=1} \left[S(\operatorname{Tr}_B\Omega_\rho) +S(\operatorname{Tr}_A\Omega_\rho)-S(\Omega_\rho)\right],$$

where $v_\rho(a,a')=(\sqrt{\rho})_{a,a'}$, the matrix used as a purification has entries $\Pi_\rho(x,y)=v_\rho(x)\overline{v_\rho(y)}$, and $\Omega_\rho=(\operatorname{id}_A\otimes N)(\Pi_\rho)$, meaning $(\Omega_\rho)_{(a,b),(a',b')}=N((\Pi_\rho)_{(a,\cdot),(a',\cdot)})_{b,b'}$. The entropy appearing here is literally $S(Z)=-\operatorname{Re}\operatorname{tr}(\mathrm{cfc}[x\mapsto x\log_2x](Z))$, and both partial traces sum over the discarded index. No channel, linearity, or positivity assumption is imposed on $N$, so $\Omega_\rho$ need not be a density matrix; the displayed total functional-calculus expression is still what is evaluated. The supremum need not be attained. It is taken in the real numbers, where an empty or unbounded-above defining set has supremum $0$; in particular, an empty input index type admits no trace-one $\rho$.

QAlgorithms.Papers.Independent.Intakethird100.P65.classicalFeasible

For an index type $A$, a finite index type $B$, arbitrary real functions $W,Y,T:A\times B\to\mathbb R$ and $V:B\to\mathbb R$, and any real $e$, this predicate means

$$\forall x\in A,\ y\in B:\quad T(x,y)-W(x,y)\le Y(x,y),\quad 0\le Y(x,y),\quad 0\le T(x,y)\le V(y),$$

together with

$$\forall x\in A:\qquad \sum_{y\in B}T(x,y)=1,\qquad \sum_{y\in B}Y(x,y)\le e.$$

There is no separate assumption on $W$ or on the sign of $e$. If $A$ is empty all these conditions are vacuous, including any restriction on $V$; if $A$ is nonempty and $B$ is empty, the required row sum $0=1$ makes the predicate impossible.

QAlgorithms.Papers.Independent.Intakethird100.P65.classicalMap

For index types $A,B$, with $A$ finite, and any real function $W:A\times B\to\mathbb R$, this defines a map from complex square matrices on $A$ to complex square matrices on $B$ by

$$\Phi_W(X)_{y,y'}= \begin{cases} \displaystyle\sum_{x\in A}W(x,y)X_{x,x},&y=y',\\ 0,&y\ne y'. \end{cases}$$

Thus only diagonal entries of $X$ enter the formula. No nonnegativity or sum condition is imposed on $W$, and $X$ is arbitrary. Empty index types are allowed; an empty sum is zero.

QAlgorithms.Papers.Independent.Intakethird100.P65.classicalValue

For an index type $A$, a finite index type $B$, any real function $W:A\times B\to\mathbb R$, and any real $e$, this defines the real infimum of $\sum_{y\in B}V(y)$ over real functions $Y,T:A\times B\to\mathbb R$ and $V:B\to\mathbb R$ satisfying, for every $x,y$,

$$T(x,y)-W(x,y)\le Y(x,y),\qquad Y(x,y)\ge0,\qquad 0\le T(x,y)\le V(y),$$

and, for every $x$,

$$\sum_yT(x,y)=1,\qquad \sum_yY(x,y)\le e.$$

No stochasticity assumption on $W$, sign assumption on $e$, or attainment claim is included. The real infimum defaults to zero for an empty feasible-value set or one unbounded below. In particular, the definition includes empty index types: the constraints are vacuous when $A$ is empty, whereas they are impossible when $A$ is nonempty and $B$ is empty.

QAlgorithms.Papers.Independent.Intakethird100.P65.codeBobTranspose

For arbitrary index types $A,B,C,D$ and a complex square matrix $Z$ indexed by $(A\times C)\times(B\times D)$, this defines a matrix $Z^{\Gamma_{CD}}$ on the same index set by

$$(Z^{\Gamma_{CD}})_{((a,c),(b,d)),\,((a',c'),(b',d'))} = Z_{((a,c'),(b,d')),\,((a',c),(b',d))}.$$

Thus it transposes the $C$ and $D$ coordinates together, leaving the $A$ and $B$ coordinates in place. No positivity, Hermiticity, normalization, or nonemptiness is required.

QAlgorithms.Papers.Independent.Intakethird100.P65.constantChannelRobustness

For finite index types $A,B$ with decidable equality and an arbitrary function $N$ from complex $A$-indexed matrices to complex $B$-indexed matrices, this is the real infimum of all real $t\ge0$ for which there exist a channel $M$ and a positive semidefinite $B$-indexed matrix $\sigma$ with $\operatorname{tr}\sigma=1$ such that, for every complex $A$-indexed matrix $X$,

$$\frac{N(X)+tM(X)}{1+t}=\operatorname{tr}(X)\sigma.$$

Here $M$ being a channel means that, for some natural number $r$ and matrices $K_j\in\mathbb C^{B\times A}$, $\sum_{j<r}K_j^\dagger K_j=I_A$ and $M(X)=\sum_{j<r}K_jXK_j^\dagger$ for every $X$. No channel assumption is imposed on $N$. The value $t=0$ is included, but even then a channel $M$ must exist; the denominator $1+t$ is positive on the feasible set. Empty index types are not excluded. This is a real-valued infimum, whose value on an empty feasible set is $0$, and it does not assert attainment.

QAlgorithms.Papers.Independent.Intakethird100.P65.constantMaxRadius

For finite index types $A,B$ with decidable equality, an arbitrary function $N:A\text{-matrices}\to B\text{-matrices}$, and any real $e$, this is the extended-real infimum

$$\inf_{\substack{\sigma\succeq0\\\operatorname{tr}\sigma=1}} \ \inf_{\substack{T\text{ a channel}\\\Delta(T,N)\le e}} \ \inf\{\ell\in\mathbb R:2^\ell J_{R_\sigma}-J_T\succeq0\}, \qquad R_\sigma(X)=\operatorname{tr}(X)\sigma.$$

A channel $T$ admits a finite representation $T(X)=\sum_{j<r}K_jXK_j^\dagger$ with $K_j\in\mathbb C^{B\times A}$ and $\sum_{j<r}K_j^\dagger K_j=I_A$. For any function $F$, its matrix $J_F$ has entries $(J_F)_{(a,b),(a',b')}=[F(E_{a,a'})]_{b,b'}$, where $E_{a,a'}$ is the matrix unit. The distance is $\Delta(T,N)=\tfrac12\sup_{\|X\|_1\le1}\|(\mathrm{id}_A\otimes(T-N))(X)\|_1$, with $X$ an arbitrary complex matrix indexed by $A\times A$, $\|Y\|_1=\operatorname{Re}\operatorname{tr}\sqrt{Y^\dagger Y}$, and amplification applying the function to each reference-indexed block. Neither $N$ being a channel nor $e\ge0$ is assumed, and empty index types are allowed. Each displayed infimum is interpreted in the extended reals, so an empty feasible set gives $+\infty$; no attainment is asserted.

QAlgorithms.Papers.Independent.Intakethird100.P65.constantRelativeRadius

For finite index types $A,B$ with decidable equality and an arbitrary function $N:A\text{-matrices}\to B\text{-matrices}$, this is the extended-real infimum

$$\inf_{\substack{\sigma\succeq0\\\operatorname{tr}\sigma=1}} \ \sup_{\substack{\psi\in\mathbb C^{A\times A}\\\|\psi\|_2=1}} D\!\left((\mathrm{id}_A\otimes N)(|\psi\rangle\langle\psi|), (\mathrm{id}_A\otimes R_\sigma)(|\psi\rangle\langle\psi|)\right), \qquad R_\sigma(X)=\operatorname{tr}(X)\sigma.$$

Here $|\psi\rangle\langle\psi|$ has entries $\psi_i\overline{\psi_j}$, and amplification applies a function separately to each matrix block indexed by the reference coordinates in $A$. The quantity $D(R,S)$ equals $+\infty$ unless both $R,S$ are positive semidefinite with complex trace $1$ and $\ker S\subseteq\ker R$; when these conditions hold, it is

$$D(R,S)= \frac{\max\!\left\{0,\operatorname{Re}\operatorname{tr} \bigl(f(R)-R\log S\bigr)\right\}}{\ln2}, \qquad f(x)=x\ln x,$$

where the matrix functions use continuous functional calculus and the real logarithm is total, with $\ln0=0$. The inner supremum and outer infimum are taken in the extended reals. No channel assumption is imposed on $N$; no nonemptiness assumption is imposed on $A$ or $B$. Thus an empty outer feasible set gives $+\infty$, while an empty set of unit vectors gives inner supremum $-\infty$.

QAlgorithms.Papers.Independent.Intakethird100.P65.dampingPrimalWitness

For every real number $r$, this definition returns the complex diagonal matrix on the Boolean index set, ordered as $(\mathrm{false},\mathrm{true})$,

$$\begin{pmatrix} 1+\sqrt{1-r}&0\\ 0&\sqrt{1-r}+1-r \end{pmatrix}.$$

The entries are real numbers embedded into $\mathbb C$. No restriction on $r$ is imposed; the real square root used here equals $0$ for negative arguments, so for $r>1$ the diagonal entries are $1$ and $1-r$.

QAlgorithms.Papers.Independent.Intakethird100.P65.deFinetti

For a finite type $A$ with decidable equality and a natural number $n$, this defines a complex matrix $D_n$ indexed by words $x,y\in(A\times A)^n$, with entries

$$D_n(x,y)= \frac{\#\{\pi\in\operatorname{Sym}(n):x=y\circ\pi\}} {n!\binom{\max(|A|^2+n-1,0)}n}.$$

The numerator counts every permutation satisfying the equality, including distinct permutations that act identically on a word with repeated coordinates. The subtraction in the binomial coefficient is natural-number subtraction, truncated at zero. No nonemptiness assumption on $A$ or positivity assumption on $n$ is imposed. For $n=0$, the matrix has one entry, equal to one; for empty $A$ and $n>0$, its index set is empty. Any division by zero in the defining formula is interpreted as zero.

QAlgorithms.Papers.Independent.Intakethird100.P65.deFinettiK1

For finite types $A,B$ with decidable equality, an arbitrary function $N$ from complex matrices on $A$ to complex matrices on $B$, a natural number $n$, and a real number $e$, this defines a set of matrices on $R_n\times B^n$, where $R_n=(A\times A)^n\times A^n$. Define

$$D_n(z,z')= \frac{\#\{\pi\in\operatorname{Sym}(n):z=z'\circ\pi\}} {n!\binom{\max(|A|^2+n-1,0)}n}, \quad v_n((z,a),b)=(\sqrt{D_n})\bigl(z,\ i\mapsto(a_i,b_i)\bigr), \quad W_n=|v_n\rangle\langle v_n|.$$

Here matrix square roots use continuous functional calculus. Define the matrix map

$$N_n(Y)(u,v)= \sum_{x,x'\in A^n}Y(x,x') \prod_{i=0}^{n-1}N(E_{x_i,x'_i})(u_i,v_i),$$

where $E_{a,a'}$ is the matrix with its sole nonzero entry, equal to one, at $(a,a')$, and let $\Omega_n=(\operatorname{id}_{R_n}\otimes N_n)(W_n)$, where the amplification applies $N_n$ separately to every block indexed by a pair of reference indices. The defined set consists precisely of matrices $\sigma$ satisfying

$$\sigma\succeq0,\qquad \operatorname{Tr}\sigma=1,\qquad P(\sigma,\Omega_n)\le e,\qquad \sum_{b\in B^n}\sigma((r,b),(r',b)) =\sum_{a\in A^n}W_n((r,a),(r',a)) \quad\text{for all }r,r',$$

where

$$F_0(X,Y)=\operatorname{ReTr}\sqrt{\sqrt X\,Y\sqrt X}, \qquad P(X,Y)= \sqrt{1-\left(F_0(X,Y)+ \sqrt{(1-\operatorname{ReTr}X)(1-\operatorname{ReTr}Y)}\right)^2}.$$

No channel assumption on $N$ is made. Real square roots and reciprocals are total, with square roots of negative numbers and reciprocals of zero equal to zero. Empty register types and $n=0$ are included; at $n=0$, the set is the singleton scalar density matrix $1$ if $e\ge0$, and is empty otherwise.

QAlgorithms.Papers.Independent.Intakethird100.P65.deFinettiK2

For finite types $A,B$ with decidable equality, an arbitrary matrix-valued function $N$ from matrices on $A$ to matrices on $B$, a natural number $n$, and a real number $e$, this defines a set of matrices on $R_n\times B^n$, with $R_n=(A\times A)^n\times A^n$. Set

$$D_n(z,z')= \frac{\#\{\pi\in\operatorname{Sym}(n):z=z'\circ\pi\}} {n!\binom{\max(|A|^2+n-1,0)}n}, \quad v_n((z,a),b)=(\sqrt{D_n})\bigl(z,\ i\mapsto(a_i,b_i)\bigr), \quad W_n=|v_n\rangle\langle v_n|,$$

using continuous functional calculus for matrix square roots, and define

$$N_n(Y)(u,v)= \sum_{x,x'\in A^n}Y(x,x') \prod_{i=0}^{n-1}N(E_{x_i,x'_i})(u_i,v_i), \qquad \Omega_n=(\operatorname{id}_{R_n}\otimes N_n)(W_n).$$

The set consists of matrices $\sigma$ for which there exists a map $T$ on matrices from $A^n$ to $B^n$ having a finite Kraus representation $T(X)=\sum_jK_jXK_j^\dagger$ with $\sum_jK_j^\dagger K_j=I$, satisfying

$$T(P_\pi X)=P_\pi(T(X)) \quad\text{for every }\pi\in\operatorname{Sym}(n)\text{ and every }X, \qquad \sigma=(\operatorname{id}_{R_n}\otimes T)(W_n), \qquad P(\sigma,\Omega_n)\le e,$$

where $P_\pi X(x,y)=X(x\circ\pi,y\circ\pi)$, amplifications act blockwise on the nonreference register, and

$$P(X,Y)= \sqrt{1-\left(\operatorname{ReTr}\sqrt{\sqrt X\,Y\sqrt X} +\sqrt{(1-\operatorname{ReTr}X)(1-\operatorname{ReTr}Y)}\right)^2}.$$

There is no channel assumption on $N$, and the definition does not separately require that $\sigma$ be a density matrix or separately impose a marginal equality. All natural subtractions are truncated, reciprocals of zero are zero, and real square roots of negative numbers are zero. Empty registers and $n=0$ are included; at $n=0$, the set is $\{1\}$ for $e\ge0$ and empty otherwise.

QAlgorithms.Papers.Independent.Intakethird100.P65.deFinettiPurification

For a finite type $A$ with decidable equality and a natural number $n$, let $D_n$ be the matrix on $(A\times A)^n$ given by

$$D_n(z,z')= \frac{\#\{\pi\in\operatorname{Sym}(n):z=z'\circ\pi\}} {n!\binom{\max(|A|^2+n-1,0)}n},$$

and let $S_n=\sqrt{D_n}$, with the square root defined by continuous functional calculus. This definition forms the vector

$$v_n((z,a),b)=S_n\bigl(z,\ i\mapsto(a_i,b_i)\bigr), \qquad z\in(A\times A)^n,\quad a,b\in A^n,$$

and returns the matrix $W_n$ with entries

$$W_n(x,y)=v_n(x)\overline{v_n(y)}.$$

Its index set is $\bigl((A\times A)^n\times A^n\bigr)\times A^n$. Empty $A$ and $n=0$ are included; at $n=0$, this is the one-entry matrix $1$. The formula itself imposes no separate normalization condition on $v_n$.

QAlgorithms.Papers.Independent.Intakethird100.P65.depolarizingFeasible

For natural numbers $d,n$, real numbers $p,e,s$, and real arrays $y=(y_0,\ldots,y_n)$ and $r=(r_0,\ldots,r_n)$, this predicate means that, on defining

$$w_k=\binom nk d^{-k}\left(d-\frac1d\right)^{n-k}, \qquad a_k=\left(d(1-p)+\frac pd\right)^k\left(\frac pd\right)^{n-k} \quad(0\le k\le n),$$

all the following hold:

$$y_k-r_k+a_k\ge0,\qquad y_k\ge0,\qquad 0\le r_k\le s \quad\text{for every }k, \qquad \sum_{k=0}^{n}w_kr_k=1, \qquad \sum_{k=0}^{n}w_ky_k\le e.$$

There are no additional bounds on $p,e,s$ or positivity assumption on $d$; reciprocals of zero are zero and $0^0=1$. For $d=0,n>0$, every $w_k$ is zero, so the normalization condition is impossible. For $n=0$, the predicate reduces to $r_0=1$, $s\ge1$, and $0\le y_0\le e$, independently of $d,p$.

QAlgorithms.Papers.Independent.Intakethird100.P65.depolarizingPrimalWitness

For every finite type $A$ with decidable equality and every real number $p$, writing $d=|A|$, this definition returns the scalar matrix

$$\left(d(1-p)+\frac pd\right)I_A,$$

with the real scalar embedded into $\mathbb C$. There is no restriction on $p$ and no nonemptiness assumption on $A$. If $A$ is empty, real division by $0$ is defined to be $0$, and the result is the unique matrix on the empty index type.

QAlgorithms.Papers.Independent.Intakethird100.P65.depolarizingSectorSum

For every finite type $A$ with decidable equality and all natural numbers $n,k$, this defines a complex square matrix on $A^n\times A^n$ as follows. Let $P$ be the matrix on $A\times A$ given by

$$P_{(a,b),(a',b')}= \begin{cases} |A|^{-1},&a=b\text{ and }a'=b',\\ 0,&\text{otherwise}. \end{cases}$$

For $x=(x_1,x_2)$ and $y=(y_1,y_2)$ in $A^n\times A^n$, the defined entry is

$$\sum_{\substack{S\subseteq\{0,\ldots,n-1\}\\|S|=k}} \prod_{i=0}^{n-1} \begin{cases} P_{(x_1(i),x_2(i)),(y_1(i),y_2(i))},&i\in S,\\ (I_{A\times A}-P)_{(x_1(i),x_2(i)),(y_1(i),y_2(i))},&i\notin S. \end{cases}$$

The sum is zero when $k>n$. When $n=0,k=0$, the empty product gives the one-entry matrix with entry one. Empty $A$ is allowed, with $|A|^{-1}=0$ when $|A|=0$.

QAlgorithms.Papers.Independent.Intakethird100.P65.depolarizingValue

For natural numbers $d,n$ and real numbers $p,e$, this defines the real infimum

$$\inf\left\{d^ns:\ s\in\mathbb R,\ y,r\in\mathbb R^{n+1},\ \begin{array}{l} y_k-r_k+a_k\ge0,\ y_k\ge0,\ 0\le r_k\le s\quad(0\le k\le n),\\ \sum_{k=0}^{n}w_kr_k=1,\quad \sum_{k=0}^{n}w_ky_k\le e \end{array}\right\},$$

where

$$w_k=\binom nk\left(\frac1d\right)^k\left(d-\frac1d\right)^{n-k}, \qquad a_k=\left(d(1-p)+\frac pd\right)^k\left(\frac pd\right)^{n-k}.$$

Division by zero is zero and $0^0=1$; no restriction on $p,e$ or positivity assumption on $d$ is imposed. This is a real-valued infimum, whose value is defined to be zero if the set is empty or unbounded below. In particular, feasibility is impossible for $d=0,n>0$, giving value zero; for $n=0$, the value is one when $e\ge0$ and zero when $e<0$.

QAlgorithms.Papers.Independent.Intakethird100.P65.fixedSmoothInfo

For finite types $A,B$ with decidable equality, any complex matrix $\rho$ indexed by $A\times B$, and any real $e$, this is the extended-real infimum

$$\inf\left\{\ell\in\mathbb R\ \middle|\ \exists\tau,\sigma,\ \tau\succeq0,\ \operatorname{Re}\operatorname{Tr}\tau\le1,\ P(\rho,\tau)\le e,\ \tau_A=\rho_A,\ \sigma\succeq0,\ \operatorname{Tr}\sigma=1,\ 2^\ell(\tau_A\otimes\sigma)-\tau\succeq0 \right\},$$

where $\tau$ is indexed by $A\times B$, $\sigma$ by $B$, and $X_A(a,a')=\sum_bX((a,b),(a',b))$. Here, with $S(X)$ denoting continuous functional calculus with the real square-root function,

$$P(X,Y)=\sqrt{1-\left(\operatorname{Re}\operatorname{Tr}S(S(X)YS(X)) +\sqrt{(1-\operatorname{Re}\operatorname{Tr}X)(1-\operatorname{Re}\operatorname{Tr}Y)}\right)^2}.$$

No state assumption is imposed on $\rho$; the displayed equality requires the entire $A$-marginal to be preserved. Zero $\tau$ is permitted when it satisfies these conditions. Real square roots of negative arguments are zero; an empty feasible set gives $+\infty$, including for $e<0$, and an unbounded-below feasible set gives $-\infty$.

QAlgorithms.Papers.Independent.Intakethird100.P65.flaggedErasureChannel

For every finite type $A$ and every real $p$, this defines a map from complex square matrices on $A$ to complex square matrices on $A\sqcup\{\bot\}$, where $\bot$ is a new distinguished index, by

$$\Phi_p(X)_{a,b}=(1-p)X_{a,b}\quad(a,b\in A),\qquad \Phi_p(X)_{\bot,\bot}=p\,\operatorname{Tr}X,\qquad \Phi_p(X)_{a,\bot}=\Phi_p(X)_{\bot,a}=0.$$

No positivity or normalization is required of $X$, and $p$ may be any real number. If $A$ is empty, the output is the zero matrix on the single index $\bot$.

QAlgorithms.Papers.Independent.Intakethird100.P65.generalErrorFeasible

For finite index types $A,B,C,D$, with decidable equality, a Boolean flag $\mathrm{ppt}$, arbitrary maps $N:\operatorname{Mat}(B)\to\operatorname{Mat}(C)$ and $M:\operatorname{Mat}(A)\to\operatorname{Mat}(D)$, and any real $g$, this predicate asserts the existence of complex square matrices $Y$ on $A\times D$ and $Z$ on $(A\times C)\times(B\times D)$ satisfying the following conditions. Write $E_{ij}$ for the matrix unit, $I_A$ for the identity, and $X\succeq0$ for positive semidefiniteness. The matrix $Z$ is positive semidefinite and, for all appropriate indices, obeys

$$\begin{aligned} \sum_{b,d}Z_{((a,c),(b,d)),((a',c'),(b,d))} &=\delta_{aa'}\delta_{cc'},\\ \sum_b Z_{((a,c),(b,d)),((a',c'),(b,d'))} &=\frac{\delta_{aa'}}{|A|} \sum_{r\in A,b}Z_{((r,c),(b,d)),((r,c'),(b,d'))},\\ \sum_d Z_{((a,c),(b,d)),((a',c'),(b',d))} &=\frac{\delta_{cc'}}{|C|} \sum_{s\in C,d}Z_{((a,s),(b,d)),((a',s),(b',d))}. \end{aligned}$$

Define matrices on $A\times D$ by

$$H_{(a,d),(a',d')} =\sum_{b,b',c,c'}N(E_{bb'})_{c,c'}\, Z_{((a,c),(b,d)),((a',c'),(b',d'))}, \qquad J_M{}_{(a,d),(a',d')}=M(E_{aa'})_{d,d'}.$$

The remaining conditions are

$$Y\succeq0,\qquad gI_A-\operatorname{Tr}_D Y\succeq0,\qquad Y-H+J_M\succeq0,$$

where $(\operatorname{Tr}_D Y)_{a,a'}=\sum_dY_{(a,d),(a',d)}$; additionally, if $\mathrm{ppt}=\mathrm{true}$, the matrix with entries $Z_{((a,c'),(b,d')),((a',c),(b',d))}$ is positive semidefinite. When the flag is false this additional requirement is absent. Neither map is assumed to be a channel or linear; $g$ is not assumed nonnegative, and empty index types are included, with empty sums equal to zero and division by zero interpreted as zero.

QAlgorithms.Papers.Independent.Intakethird100.P65.halfDiamondDistance

For finite types $A,B$ with decidable equality and arbitrary functions $N,M:\mathbb C^{A\times A}\to\mathbb C^{B\times B}$, this defines

$$\frac12\sup\left\{\|\Delta_X\|_1\ \middle|\ X\in\mathbb C^{(A\times A)\times(A\times A)},\ \|X\|_1\le1 \right\},$$

where $X^{a,a'}_{i,j}=X((a,i),(a',j))$ and

$$\Delta_X((a,b),(a',b'))= N(X^{a,a'})_{b,b'}-M(X^{a,a'})_{b,b'}.$$

Here $\|Y\|_1=\operatorname{Re}\operatorname{Tr}\bigl(\operatorname{cfc}(\sqrt{\cdot})(Y^\dagger Y)\bigr)$. The test matrices $X$ need not be positive or normalized. Neither map is assumed linear or a channel. The supremum is the real-number supremum, which takes the default value zero if the set is unbounded above.

QAlgorithms.Papers.Independent.Intakethird100.P65.infoOnSet

For finite types $A,B$ with decidable equality and an arbitrary set $S$ of complex matrices on $A\times B$, this defines the extended-real infimum

$$\inf_{\sigma\in S}\ \inf_{\substack{\omega\succeq0\\ \operatorname{Tr}\omega=1}} D_{\max}\!\left(\sigma\ \middle\|\ \sigma_A\otimes\omega\right), \qquad \sigma_A(a,a')=\sum_{b\in B}\sigma((a,b),(a',b)),$$

where $\omega$ is a matrix on $B$ and

$$D_{\max}(X\|Y)= \inf\{\lambda\in\mathbb R:2^\lambda Y-X\succeq0\},$$

with this last infimum taken in the extended reals by embedding each admissible real $\lambda$. The set $S$ is not required to contain only density matrices or positive matrices. Empty register types and empty $S$ are allowed; an infimum over an empty set is $+\infty$, while an admissible set of exponents unbounded below has infimum $-\infty$.

QAlgorithms.Papers.Independent.Intakethird100.P65.linkChoi

For finite index types $A,B,C,D$, a complex matrix $J$ indexed by $B\times C$, and a complex matrix $Z$ indexed by $(A\times C)\times(B\times D)$, this defines a complex matrix indexed by $A\times D$ by

$$[\operatorname{link}(J,Z)]_{(i,d),(j,d')} = \sum_{a,c\in B}\ \sum_{u,v\in C} J_{(a,u),(c,v)} Z_{((i,u),(a,d)),\,((j,v),(c,d'))}$$

for every $i,j\in A$ and $d,d'\in D$. There are no positivity, normalization, or channel hypotheses on either matrix. Empty index types are included, and a sum over an empty index type is $0$.

QAlgorithms.Papers.Independent.Intakethird100.P65.maxEntangledInput

For every finite type $A$ equipped with decidable equality, this defines a complex matrix $J$ indexed by $A\times A$. Writing $d=|A|$, its entries are

$$J((a,b),(a',b'))= \begin{cases} d^{-1},&a=b\ \text{and}\ a'=b',\\ 0,&\text{otherwise}. \end{cases}$$

For $d>0$, this is the outer product of $d^{-1/2}\sum_{a\in A}|a,a\rangle$ with itself. The definition also includes empty $A$: then $J$ is the unique empty matrix, and the scalar inverse of zero is defined to be zero.

QAlgorithms.Papers.Independent.Intakethird100.P65.maxInfo

For finite types $A,B$ with decidable equality and any complex matrix $\rho$ indexed by $A\times B$, define its $A$-marginal by $\rho_A(a,a')=\sum_{b\in B}\rho((a,b),(a',b))$. This definition returns the following infimum in the extended real numbers:

$$\inf\left\{\ell\in\mathbb R\ \middle|\ \exists\sigma\in\mathbb C^{B\times B},\ \sigma\succeq0,\ \operatorname{Tr}\sigma=1,\ 2^\ell(\rho_A\otimes\sigma)-\rho\succeq0 \right\}.$$

Here $(\rho_A\otimes\sigma)((a,b),(a',b'))=\rho_A(a,a')\sigma(b,b')$. No positivity, nonzero, or trace assumption is imposed on $\rho$. An empty feasible set gives $+\infty$, and a feasible set unbounded below gives $-\infty$; in particular, if $B$ is empty, there is no trace-one $\sigma$.

QAlgorithms.Papers.Independent.Intakethird100.P65.minimumError

For finite index types $A,B,C,D$, with decidable equality, an assistance label $o$, and arbitrary matrix maps $N:B\to C$ and $M:A\to D$, this defines the real infimum

$$\inf_P\frac12\sup_{\|X\|_1\le1} \left\|(\operatorname{id}_A\otimes(\mathcal W_N(P)-M))(X)\right\|_1,$$

where $X$ ranges over all complex matrices on $A\times A$, not merely density matrices, $\|Z\|_1=\operatorname{Re}\operatorname{tr}\sqrt{Z^\dagger Z}$, amplification applies the map separately to each block indexed by the first factor, and

$$\mathcal W_N(P)(Y)_{b,d} =\sum_{a,c\in B}\sum_{u,v\in C} N(|a\rangle\langle c|)_{u,v} P(Y\otimes|u\rangle\langle v|)_{(a,b),(c,d)}.$$

The infimum ranges over maps $P:A\times C\to B\times D$ satisfying the rule selected by $o$: for $\mathrm{ns}$, $P$ is a channel and its two output marginals depend only on the corresponding input marginals through channels; for $\mathrm{nsPpt}$, additionally $\Gamma_D\circ P\circ\Gamma_C$ is a channel, with $\Gamma$ transposing the second tensor factor; for $\mathrm{ent}$, $P$ is obtained by adjoining a shared positive semidefinite trace-one state of finite positive local dimensions and applying a channel separately to each party’s input and share, with no communication between those local maps. A channel here has a finite Kraus representation with $\sum_\ell K_\ell^\dagger K_\ell=I$. Both extrema are taken in the real numbers, and no attainment is asserted; in particular, an empty infimum is assigned the real value $0$.

QAlgorithms.Papers.Independent.Intakethird100.P65.oneUseSimulationCost

For finite index types $A,B$, with decidable equality, an assistance label $o$, an arbitrary matrix map $N:A\to B$, and any real tolerance $e$, this defines the real infimum of $\log_2 m$ over positive integers $m$ satisfying

$$\inf_{P\ \mathrm{allowed}}\frac12 \sup_{\|X\|_1\le1} \left\|(\operatorname{id}_A\otimes(\mathcal L_m(P)-N))(X)\right\|_1\le e, \qquad \mathcal L_m(P)(Y)_{b,b'} =\sum_{u,v<m}P(Y\otimes|u\rangle\langle v|)_{(u,b),(v,b')}.$$

Here $P:A\times\mathrm{Fin}(m)\to\mathrm{Fin}(m)\times B$, $X$ ranges over all matrices on $A\times A$, $\|Z\|_1=\operatorname{Re}\operatorname{tr}\sqrt{Z^\dagger Z}$, and amplification applies the map blockwise. “Allowed” means: for $\mathrm{ns}$, $P$ is a channel whose two output marginals are channels of the corresponding input marginals; for $\mathrm{nsPpt}$, also its conjugation by partial transposition on the second input and second output factors is a channel; for $\mathrm{ent}$, $P$ results from a shared finite-dimensional density matrix and separate local channels on each input and its share. Channels are finite Kraus maps with Kraus completeness $\sum_\ell K_\ell^\dagger K_\ell=I$. There is no assumption that $N$ is a channel or that $e\ge0$, and the inner infimum need not be attained. The outer infimum is real-valued and equals $0$ if its defining set is empty.

QAlgorithms.Papers.Independent.Intakethird100.P65.purify

For a finite type $A$ with decidable equality and any complex matrix $\rho$ indexed by $A$, let $S(\rho)$ be continuous functional calculus applied to $\rho$ with the real square-root function, and form the vector $v$ indexed by $A\times A$ with $v(a,b)=S(\rho)_{a,b}$. This definition returns the matrix

$$\operatorname{purify}(\rho)((a,b),(a',b')) =S(\rho)_{a,b}\,\overline{S(\rho)_{a',b'}}.$$

No positivity, normalization, or nonzero assumption is made on $\rho$; the vector is not normalized by the definition. Empty $A$ is included.

QAlgorithms.Papers.Independent.Intakethird100.P65.reducedErrorFeasible

For finite index types $A,B$, with decidable equality, a Boolean flag $\mathrm{ppt}$, an arbitrary map $N:\operatorname{Mat}(A)\to\operatorname{Mat}(B)$, a natural number $m$, and a real $g$, this predicate asserts that there exist complex square matrices $Y,J$ on $A\times B$ and a Hermitian matrix $V$ on $B$ such that, writing $C_N{}_{(a,b),(a',b')}=N(E_{aa'})_{b,b'}$,

$$\begin{gathered} Y\succeq0,\qquad J\succeq0,\qquad gI_A-\operatorname{Tr}_B Y\succeq0,\qquad Y-J+C_N\succeq0,\\ \operatorname{Tr}_B J=I_A,\qquad I_A\otimes V-J\succeq0,\qquad \operatorname{Re}\operatorname{Tr}V=m^2. \end{gathered}$$

Here $E_{aa'}$ is a matrix unit, $\succeq0$ means positive semidefinite, and $(\operatorname{Tr}_B X)_{a,a'}=\sum_bX_{(a,b),(a',b)}$. If $\mathrm{ppt}=\mathrm{true}$, it also requires

$$-I_A\otimes V^{\mathsf T}\preceq mJ^{\Gamma_B} \preceq I_A\otimes V^{\mathsf T}, \qquad (J^{\Gamma_B})_{(a,b),(a',b')}=J_{(a,b'),(a',b)},$$

where $X\preceq Y$ means $Y-X\succeq0$; for a false flag these extra inequalities impose no condition. The definition allows $m=0$, arbitrary $g$, and empty index types, and does not assume that $N$ is a channel or linear.

QAlgorithms.Papers.Independent.Intakethird100.P65.referenceSmoothInfo

For finite types $A,B$ with decidable equality, any complex matrix $\rho$ indexed by $A\times B$, and any real $e$, this is the extended-real infimum

$$\inf\left\{\ell\in\mathbb R\ \middle|\ \exists\tau,\sigma,\ \tau\succeq0,\ \operatorname{Re}\operatorname{Tr}\tau\le1,\ P(\rho,\tau)\le e,\ \sigma\succeq0,\ \operatorname{Tr}\sigma=1,\ 2^\ell(\rho_A\otimes\sigma)-\tau\succeq0 \right\},$$

where $\tau$ is indexed by $A\times B$, $\sigma$ by $B$, and $\rho_A(a,a')=\sum_b\rho((a,b),(a',b))$. With $S(X)$ denoting continuous functional calculus with the real square-root function, the distance expression is

$$P(X,Y)=\sqrt{1-\left(\operatorname{Re}\operatorname{Tr}S(S(X)YS(X)) +\sqrt{(1-\operatorname{Re}\operatorname{Tr}X)(1-\operatorname{Re}\operatorname{Tr}Y)}\right)^2}.$$

There is no requirement that $\tau_A=\rho_A$, and no positivity or normalization assumption on $\rho$. Zero $\tau$ is allowed. Real square roots of negative arguments are zero; empty feasibility gives $+\infty$, including for $e<0$, while unboundedness below gives $-\infty$.

QAlgorithms.Papers.Independent.Intakethird100.P65.roundedInfoCost

For every real $x$, this defines the real number $\log_2\!\left(\lceil2^{x/2}\rceil_{\mathbb N}\right)$, where the ceiling is the least natural number at least its argument, subsequently regarded as a real number. Since $2^{x/2}>0$, this ceiling is always at least $1$; in particular, the value is $0$ for every $x\le0$.

QAlgorithms.Papers.Independent.Intakethird100.P65.roundedTraceCost

For every real $t$, this defines $\log_2\!\left(\lceil\sqrt t\rceil_{\mathbb N}\right)$, with the natural-number ceiling subsequently regarded as a real number. The real square root and logarithm are total: $\sqrt t=0$ when $t\le0$, and $\log_2 0=0$. Consequently this definition gives $0$ for every $t\le1$, including negative $t$ and $t=0$.

QAlgorithms.Papers.Independent.Intakethird100.P65.roundingCorrection

For every real $x$, this defines $\log_2\!\left(\lceil2^{x/2}\rceil_{\mathbb N}\right)-x/2$, where the ceiling is taken in the natural numbers and then converted to a real number. All real $x$ are included; for $x\le0$, the ceiling is $1$ and this value is $-x/2$.

QAlgorithms.Papers.Independent.Intakethird100.P65.sectorEigenvalue

For arbitrary natural numbers $d,n,k$ and an arbitrary real number $p$, this defines

$$\left(d(1-p)+\frac pd\right)^k \left(\frac pd\right)^{\max(n-k,0)}.$$

There is no assumption that $d>0$, $k\le n$, or $p\in[0,1]$. The exponent subtraction is truncated at zero, division by zero is zero, and $0^0=1$. In particular, for $k>n$ the second factor is one, and for $n=k=0$ the entire expression is one.

QAlgorithms.Papers.Independent.Intakethird100.P65.sectorMatrix

For a finite type $A$ with decidable equality, a natural number $n$, and arbitrary real coefficients $r_0,\ldots,r_n$, this defines a complex matrix on $A^n\times A^n$ by

$$\sum_{k=0}^{n}r_k \sum_{\substack{S\subseteq\{0,\ldots,n-1\}\\ |S|=k}} \bigotimes_{i=0}^{n-1} \begin{cases} Q_A,&i\in S,\\ I-Q_A,&i\notin S, \end{cases}$$

where $A^n$ denotes the functions from $\{0,\ldots,n-1\}$ to $A$, tensor factors are grouped into the two $A^n$ registers, and

$$Q_A((a,b),(a',b'))= \begin{cases} |A|^{-1},&a=b\text{ and }a'=b',\\ 0,&\text{otherwise}. \end{cases}$$

Explicitly, an entry of each tensor product is the product of its factors’ corresponding entries. The coefficients need not be nonnegative or sum to one. The type $A$ may be empty, and $n=0$ is included: the empty tensor product is the scalar matrix $1$, so the result is the scalar matrix $r_0$.

QAlgorithms.Papers.Independent.Intakethird100.P65.sectorWeight

For arbitrary natural numbers $d,n,k$, this defines the real number

$$\binom nk\left(\frac1d\right)^k \left(d-\frac1d\right)^{\max(n-k,0)}.$$

The subtraction in the exponent is truncated natural-number subtraction. No positivity assumption on $d$, or restriction $k\le n$, is imposed. Division by zero has value zero, and every zeroth power, including $0^0$, is one. Thus the value is zero when $k>n$; when $d=0$ and $n>0$, it is zero for every $k$; and at $n=k=0$, it is one for every $d$.

QAlgorithms.Papers.Independent.Intakethird100.P65.smoothChannelDmax

For finite index types $A,B$ with decidable equality, arbitrary matrix-valued functions $N,M:A\text{-matrices}\to B\text{-matrices}$, and any real $e$, this is the infimum in $[-\infty,+\infty]$ of the values $D_{\max}(J_T,J_M)$ over all channels $T$ satisfying $\Delta(T,N)\le e$. Here a channel $T$ means that there exist a natural number $r$ and matrices $K_j\in\mathbb C^{B\times A}$, $0\le j<r$, such that $\sum_jK_j^\dagger K_j=I_A$ and $T(X)=\sum_jK_jXK_j^\dagger$ for every $X$; $J_T$ is the matrix with entries $(J_T)_{(a,b),(a',b')}=[T(E_{a,a'})]_{b,b'}$, where $E_{a,a'}$ has its sole nonzero entry $1$ at $(a,a')$; and

$$D_{\max}(R,S)=\inf\{\ell\in\mathbb R:2^\ell S-R\text{ is positive semidefinite}\}, \qquad \Delta(T,N)=\frac12\sup_{\|X\|_1\le1} \|(\mathrm{id}_A\otimes(T-N))(X)\|_1.$$

The first infimum is taken in the extended reals. In the supremum, $X$ ranges over all complex matrices indexed by $A\times A$, $\|Y\|_1=\operatorname{Re}\operatorname{tr}\sqrt{Y^\dagger Y}$, and the amplification acts on each block by $[(\mathrm{id}_A\otimes F)(X)]_{(a,b),(a',b')}=[F(X_{(a,\cdot),(a',\cdot)})]_{b,b'}$. Neither $N$ nor $M$ is assumed to be a channel, $e$ need not be nonnegative, and empty index types are allowed. An empty feasible set for either extended-real infimum gives $+\infty$; attainment is not part of this definition.

QAlgorithms.Papers.Independent.Intakethird100.P65.smoothChannelInfo

For finite types $A,B$ with decidable equality, an arbitrary function $N:\mathbb C^{A\times A}\to\mathbb C^{B\times B}$, and any real $e$, this defines the real infimum of $I(M)$ over all finite Kraus channels $M$ whose half-distance from $N$ is at most $e$. Such a channel has, for some natural number $r$, matrices $K_j\in\mathbb C^{B\times A}$ satisfying $\sum_{j<r}K_j^\dagger K_j=1$ and $M(X)=\sum_{j<r}K_jXK_j^\dagger$ for every matrix $X$. Its half-distance is

$$\frac12\sup_{\|X\|_1\le1}\|\Delta_X\|_1, \quad \Delta_X((a,b),(a',b'))= M(X^{a,a'})_{b,b'}-N(X^{a,a'})_{b,b'}, \quad X^{a,a'}_{i,j}=X((a,i),(a',j)),$$

with $\|Y\|_1=\operatorname{Re}\operatorname{Tr}\operatorname{cfc}(\sqrt{\cdot})(Y^\dagger Y)$ and a real supremum. To define $I(M)$, set $R((a,b),(a',b'))=M(|A|^{-1}E_{a,a'})_{b,b'}$, $R_A(a,a')=\sum_bR((a,b),(a',b))$, and take the extended-real infimum of all real $\ell$ for which some positive semidefinite trace-one matrix $\sigma$ on $B$ satisfies $2^\ell(R_A\otimes\sigma)-R\succeq0$; $I(M)$ is its real conversion, sending either infinity to zero. No channel assumption is made on $N$. The outer real infimum is zero for an empty feasible set or one unbounded below, and empty register types are included.

QAlgorithms.Papers.Independent.Intakethird100.P65.smoothInfo

For finite types $A,B$ with decidable equality, any complex matrix $\rho$ indexed by $A\times B$, and any real $e$, this is the extended-real infimum

$$\inf\left\{\ell\in\mathbb R\ \middle|\ \exists\tau,\sigma,\ \tau\succeq0,\ \operatorname{Re}\operatorname{Tr}\tau\le1,\ P(\rho,\tau)\le e,\ \sigma\succeq0,\ \operatorname{Tr}\sigma=1,\ 2^\ell(\tau_A\otimes\sigma)-\tau\succeq0 \right\},$$

where $\tau$ is indexed by $A\times B$, $\sigma$ by $B$, and $\tau_A(a,a')=\sum_b\tau((a,b),(a',b))$. Explicitly, writing $S(X)$ for continuous functional calculus with the real square-root function,

$$P(X,Y)=\sqrt{1-\left(\operatorname{Re}\operatorname{Tr}S(S(X)YS(X)) +\sqrt{(1-\operatorname{Re}\operatorname{Tr}X)(1-\operatorname{Re}\operatorname{Tr}Y)}\right)^2}.$$

The matrix $\rho$ need not be positive or normalized, and $\tau=0$ is allowed. Real square roots of negative arguments are zero. Empty feasibility gives $+\infty$, including when $e<0$, while unboundedness below gives $-\infty$.

QAlgorithms.Papers.Independent.Intakethird100.P65.smoothRobustness

For finite index types $A,B$ with decidable equality, an arbitrary matrix-valued function $N:A\text{-matrices}\to B\text{-matrices}$, and any real $e$, this is the real infimum of $R(T)$ over all channels $T$ satisfying $\Delta(T,N)\le e$, where

$$R(T)=\inf\left\{t\ge0: \begin{array}{l} \text{there exist a channel }M\text{ and }\sigma\succeq0,\ \operatorname{tr}\sigma=1,\\ \displaystyle\frac{T(X)+tM(X)}{1+t} =\operatorname{tr}(X)\sigma\quad\text{for every }X \end{array}\right\}.$$

Both infima here are real infima. A channel $F$ means a function admitting a finite representation $F(X)=\sum_{j<r}K_jXK_j^\dagger$ with $\sum_{j<r}K_j^\dagger K_j=I_A$. The distance is

$$\Delta(T,N)=\frac12\sup_{\substack{X\in\mathbb C^{(A\times A)\times(A\times A)}\\ \|X\|_1\le1}} \|(\mathrm{id}_A\otimes(T-N))(X)\|_1, \qquad \|Y\|_1=\operatorname{Re}\operatorname{tr}\sqrt{Y^\dagger Y},$$

with amplification applying the function to each block indexed by the reference coordinates in $A$. There is no channel assumption on $N$ and no nonnegativity assumption on $e$; empty index types are included. Either real infimum equals $0$ if its feasible set is empty, and no minimizing channel is asserted to exist.

QAlgorithms.Papers.Independent.Intakethird100.P65.traceFeasible

For finite index types $A,B$, with decidable equality, an arbitrary map $N:\operatorname{Mat}(A)\to\operatorname{Mat}(B)$, a real $e$, complex square matrices $Y,J$ on $A\times B$, and a complex square matrix $V$ on $B$, this predicate means precisely

$$V=V^\dagger,\qquad Y\succeq0,\qquad J\succeq0,\qquad eI_A-\operatorname{Tr}_B Y\succeq0,\qquad Y-J+C_N\succeq0,\qquad \operatorname{Tr}_B J=I_A,\qquad I_A\otimes V-J\succeq0.$$

Here $C_N{}_{(a,b),(a',b')}=N(E_{aa'})_{b,b'}$, $E_{aa'}$ is a matrix unit, $(\operatorname{Tr}_B X)_{a,a'}=\sum_bX_{(a,b),(a',b)}$, and $\succeq0$ denotes positive semidefiniteness. There is no trace constraint on $V$, no assumption that $e\ge0$, and no channel or linearity assumption on $N$; empty index types are included.

QAlgorithms.Papers.Independent.Intakethird100.P65.traceValue

For finite index types $A,B$, with decidable equality, an arbitrary map $N:\operatorname{Mat}(A)\to\operatorname{Mat}(B)$, and any real $e$, this defines the real infimum of $\operatorname{Re}\operatorname{Tr}V$ over all complex matrices $Y,J$ on $A\times B$ and $V$ on $B$ satisfying

$$V=V^\dagger,\quad Y\succeq0,\quad J\succeq0,\quad eI_A-\operatorname{Tr}_B Y\succeq0,\quad Y-J+C_N\succeq0,\quad \operatorname{Tr}_B J=I_A,\quad I_A\otimes V-J\succeq0,$$

where $C_N{}_{(a,b),(a',b')}=N(E_{aa'})_{b,b'}$, $E_{aa'}$ is a matrix unit, and $(\operatorname{Tr}_B X)_{a,a'}=\sum_bX_{(a,b),(a',b)}$. Positive semidefiniteness is denoted by $\succeq0$. The definition asserts neither feasibility nor attainment, allows negative $e$ and empty index types, and imposes no channel or linearity assumption on $N$. This is a total real-valued infimum: an empty feasible-value set, or one unbounded below, yields zero.

QAlgorithms.Papers.Independent.Intakethird100.P65.vanishingErrorQuantumCapacity

For finite index types $A,B$, with decidable equality, an assistance label $o$, and an arbitrary matrix map $N:A\to B$, this defines the extended-real supremum over real numbers $r\ge0$ such that, for every $e>0$ and $s>0$, all sufficiently large positive integers $n$ admit a positive integer $m$ satisfying $(r-s)n\le\log_2m$ and an infimum error at most $e$ for simulating the identity on $m\times m$ matrices using $N^{[n]}$. Here $N^{[n]}(Y)_{y,y'}=\sum_{x,x'}Y_{x,x'}\prod_{i<n}N(|x_i\rangle\langle x_i'|)_{y_i,y_i'}$; the error is the real infimum over allowed $P:\mathrm{Fin}(m)\times B^n\to A^n\times\mathrm{Fin}(m)$ of

$$\frac12\sup_{\|X\|_1\le1} \left\|(\operatorname{id}_m\otimes(\mathcal W_{N^{[n]}}(P)-\operatorname{id}_m))(X)\right\|_1,$$

where $\mathcal W_S(P)(Y)_{b,d}=\sum_{a,c,u,v}S(|a\rangle\langle c|)_{u,v}P(Y\otimes|u\rangle\langle v|)_{(a,b),(c,d)}$, the supremum ranges over all matrices $X$ on $\mathrm{Fin}(m)\times\mathrm{Fin}(m)$, amplification is blockwise, and $\|Z\|_1=\operatorname{Re}\operatorname{tr}\sqrt{Z^\dagger Z}$. Allowed maps are channels with both marginal nonsignalling conditions for $\mathrm{ns}$; additionally their second-factor partial-transpose conjugates are channels for $\mathrm{nsPpt}$; or they use a shared finite-dimensional density matrix and separate local channels for $\mathrm{ent}$. Channels have finite complete Kraus representations. The inner real infimum need not be attained and equals $0$ if empty. The outer supremum is $-\infty$ if its rate set is empty and $+\infty$ if that set is unbounded above.

QAlgorithms.Papers.Independent.Intakethird100.P65.vanishingErrorSimulationCost

For finite index types $A,B$, with decidable equality, an assistance label $o$, and an arbitrary matrix map $N:A\to B$, this defines an extended-real infimum over real numbers $r\ge0$ with the following property: for every $e>0$ and $s>0$, all sufficiently large positive integers $n$ admit a positive integer $m$ such that $\log_2m\le(r+s)n$ and the infimum simulation error from the identity map on $m\times m$ matrices to $N^{[n]}$ is at most $e$. Explicitly, $N^{[n]}(Y)_{y,y'}=\sum_{x,x'}Y_{x,x'}\prod_{i<n}N(|x_i\rangle\langle x_i'|)_{y_i,y_i'}$, and that error is the real infimum over allowed $P:A^n\times\mathrm{Fin}(m)\to\mathrm{Fin}(m)\times B^n$ of

$$\frac12\sup_{\|X\|_1\le1} \left\|(\operatorname{id}_{A^n}\otimes(\mathcal L_m(P)-N^{[n]}))(X)\right\|_1, \quad \mathcal L_m(P)(Y)_{b,b'}=\sum_{u,v<m}P(Y\otimes|u\rangle\langle v|)_{(u,b),(v,b')}.$$

The supremum uses all matrices $X$ on $A^n\times A^n$; amplification is blockwise and $\|Z\|_1=\operatorname{Re}\operatorname{tr}\sqrt{Z^\dagger Z}$. Allowed maps are channels with both marginal nonsignalling conditions for $\mathrm{ns}$; additionally their second-factor partial-transpose conjugates are channels for $\mathrm{nsPpt}$; or they are implemented by separate local channels with a shared finite-dimensional density matrix for $\mathrm{ent}$. Channels have finite complete Kraus representations. Inner error infima are real and need not be attained, with empty infimum $0$; the outer infimum is in the extended reals and is $+\infty$ if no such rate exists.

QAlgorithms.Papers.Independent.Intakethird100.P65.wire

For finite index types $A,B,C,D$, with decidable equality, and arbitrary matrix maps $N:B\to C$ and $P:A\times C\to B\times D$, this defines a matrix map $\mathcal W_N(P):A\to D$ by

$$\mathcal W_N(P)(X)_{b,d} = \sum_{a,c\in B}\sum_{u,v\in C} N(|a\rangle\langle c|)_{u,v}\, P\!\left(X\otimes|u\rangle\langle v|\right)_{(a,b),(c,d)}$$

for every complex matrix $X$ on $A$ and every $b,d\in D$. Matrix units have a single entry $1$, and the tensor product has entries $(X\otimes Y)_{(i,u),(j,v)}=X_{i,j}Y_{u,v}$. Neither $N$ nor $P$ is assumed linear, positive, or trace preserving. Empty index sets are included, with empty sums equal to zero.

QAlgorithms.Papers.Independent.Intakethird100.P65.zeroErrorCost

For finite index types $A,B$, with decidable equality, and an arbitrary matrix map $N:A\to B$, this defines the real infimum of all real numbers $r$ such that, for every slack $s>0$, all sufficiently large positive integers $n$ satisfy $C_n/n\le r+s$, where

$$C_n=\inf\left\{\log_2m:\ m\ge1,\ \inf_{P\ \mathrm{nonsignalling}} \frac12\sup_{\|X\|_1\le1} \left\|(\operatorname{id}_{A^n}\otimes(\mathcal L_m(P)-N^{[n]}))(X)\right\|_1 \le0\right\}.$$

Here $N^{[n]}(Y)_{y,y'}=\sum_{x,x'}Y_{x,x'}\prod_{i<n}N(|x_i\rangle\langle x_i'|)_{y_i,y_i'}$, $P:A^n\times\mathrm{Fin}(m)\to\mathrm{Fin}(m)\times B^n$, and $\mathcal L_m(P)(Y)_{b,b'}=\sum_{u,v<m}P(Y\otimes|u\rangle\langle v|)_{(u,b),(v,b')}$. Such a $P$ must be a channel for which each output marginal is obtained from the corresponding input marginal by a channel, for every matrix input; channels are finite Kraus maps with $\sum_\ell K_\ell^\dagger K_\ell=I$. The supremum uses all matrices $X$ on $A^n\times A^n$ with trace norm at most $1$, amplification is blockwise, and $\|Z\|_1=\operatorname{Re}\operatorname{tr}\sqrt{Z^\dagger Z}$. The zero-tolerance condition concerns an infimum and does not assert that an exactly error-free map attains it. All infima here are real-valued, with empty infimum $0$; no nonnegativity condition is imposed on $r$, and division by $n=0$ is excluded by the quantifier.

QAlgorithms.Papers.Independent.Intakethird100.P65.zeroTraceValue

For finite index types $A,B$, with decidable equality, and any map $N:\operatorname{Mat}(A)\to\operatorname{Mat}(B)$, this defines

$$\inf\left\{\operatorname{Re}\operatorname{Tr}V: V\in\operatorname{Mat}(B),\quad V=V^\dagger,\quad I_A\otimes V-C_N\succeq0\right\}, \qquad C_N{}_{(a,b),(a',b')}=N(E_{aa'})_{b,b'}.$$

Here $E_{aa'}$ is a matrix unit and $\succeq0$ denotes positive semidefiniteness. No separate positivity condition on $V$, channel or linearity condition on $N$, or nonemptiness condition on the index types is imposed. The definition asserts neither existence nor attainment of a feasible value; its real infimum is zero for an empty set or a set unbounded below.