Proof. Let \(\mathcal{S}^{(n)}\) be the superchannel constructed in Proposition 2. Then, for any channel \(\Phi_{A\to B}\), the Choi operator \(J^{\mathcal{S}^{(n)}[\Phi^{\otimes n}]}_{(A'BE)^n}\) of \(\mathcal{S}^{(n)}[\Phi^{\otimes n}]\) can be written in terms of the Choi operator \(J^{\Phi^{\otimes n}}_{(A'B)^n}=(J^{\Phi}_{A'B})^{\otimes n}\) of \(\Phi^{\otimes n}\), where \(J^{\Phi}_{A'B} \relax\Phi_{A\to B}(\Gamma_{AA'})\), as \[\begin{align}\label{eq:10} J^{\mathcal{S}^{(n)}[\Phi^{\otimes n}]}_{(A'BE)^n} &= \mathcal{S}^{(n)}_\ast\big(J^{\Phi^{\otimes n}}_{(A'B)^n}\big)\\ &= \Lambda^{(n)}_{\rm purify}\left((J^{\Phi}_{A'B})^{\otimes n}\right)\\ &= \Lambda^{(n)}_{\rm purify}\left(\mathop{\mathrm{Tr}}_{E^n}\!\left[V_{A\to BE}^{\otimes n}\Gamma_{A'A}^{\otimes n}V_{A\to BE}^{\dagger\, \otimes n}\right]\right)\\ &\stackrel{\mathclap{\scriptsize (i)}}{=}\underset{\scaleobj{.8}{U_E}}{\mathbb{E}\,}\left[\big((\mathbb{1}_B\otimes U_E)V_{A\to BE}\big)^{\otimes n} \Gamma_{A'A}^{\otimes n} \big(V_{A\to BE}^\dagger(\mathbb{1}_B\otimes U_E^\dagger)\big)^{\otimes n}\right], \end{align}\tag{4}\] where \(\mathcal{S}_\ast^{(n)}\) was introduced in ?? , and \(V_{A\to BE}\) is any arbitrary Stinespring representation of \(\Phi_{A\to B}\). In (i) we have observed that \(V_{A\to BE}\ket{\Gamma}_{A'A}\) is a legitimate purification of \(J^{\Phi}_{A'B}\). The last identity follows from 1 . Now, by Choi’s theorem, 4 immediately implies that, for any \(\rho_{A^n}\in \mathcal{L}(\mathcal{H}_{A^n})\), \[\begin{align} \mathcal{S}^{(n)}[\Phi^{\otimes n}](\rho_{A^n}) &= \mathop{\mathrm{Tr}}_{{A'}^n}\!\left[\big(\rho_{{A'}^n}^{\intercal}\otimes\mathbb{1}_{B^nE^n}\big)\, J^{\mathcal{S}[\Phi^{\otimes n}]}_{(A'BE)^n} \right] \\ &\stackrel{\mathclap{\scriptsize (ii)}}{=} \underset{\scaleobj{.8}{U_E}}{\mathbb{E}\,} \mathop{\mathrm{Tr}}_{{A'}^n}\!\left[\big((\mathbb{1}_B\otimes U_E)V_{A\to BE}\big)^{\otimes n}\big(\mathbb{1}_{{A'}^n} \otimes \rho_{A^n} \big) \Gamma_{A'A}^{\otimes n} \big(V_{A\to BE}^\dagger(\mathbb{1}_B\otimes U_E^\dagger)\big)^{\otimes n}\right] \\ &\stackrel{\mathclap{\scriptsize (iii)}}{=} \underset{\scaleobj{.8}{U_E}}{\mathbb{E}\,}\left[\big((\mathbb{1}_B\otimes U_E)V_{A\to BE}\big)^{\otimes n}\rho_{A^n} \big(V_{A\to BE}^\dagger(\mathbb{1}_B\otimes U_E^\dagger)\big)^{\otimes n}\right], \end{align}\] where in (ii) we have commuted \(\rho_{{A'}^n}^\intercal\) past the isometry and transferred its action on \(A^n\) using the transpose trick, while in (iii) we have observed that \(\mathop{\mathrm{Tr}}_{A'}\Gamma_{A'A} = \mathbb{1}_A\).

Since \(\mathcal{S}\) is a superchannel, according to Lemma 1 it can be implemented by means of an encoder, a decoder and a memory. Hence ?? holds true, and this concludes the proof. ◻

Proof of Proposition 2.. The map \(\mathcal{S}^{(n)}_\ast\) is manifestly completely positive, as \(\Lambda^{(n)}_{\rm purify}\) is completely positive. Now, let \(X_{(AB)^n}\) be an operator on \(\mathcal{H}_{A^n}\otimes \mathcal{H}_{B^n}\) such that \(\mathop{\mathrm{Tr}}_{B^n} X_{(AB)^n} = \kappa \mathbb{1}_{A^n}\). Then, \[\begin{align} \mathop{\mathrm{Tr}}_{B^nE^n} \mathcal{S}_\ast^{(n)}(X_{(AB)^n}) &\stackrel{\mathclap{\scriptsize (i)}}{=}\mathop{\mathrm{Tr}}_{B^n}\mathop{\mathrm{Tr}}_{E^n}\Lambda^{(n)}_{\rm purify}\left(\mathcal{P}_{AB}^{(n)}\big(X_{(AB)^n}\big)\right)\\ &\stackrel{\mathclap{\scriptsize (ii)}}{=}\mathop{\mathrm{Tr}}_{B^n}\left[\mathcal{P}_{AB}^{(n)}\big(X_{(AB)^n}\big)\right]\\ &=\mathcal{P}_{A}^{(n)}\left(\mathop{\mathrm{Tr}}_{B^n}\!\left[X_{(AB)^n}\right]\right)\\ &\stackrel{\mathclap{\scriptsize (iii)}}{=}\kappa\mathbb{1}_{A^n}, \end{align}\] where we have called \(\mathcal{P}_{AB}^{(n)}\) and \(\mathcal{P}_{A}^{(n)}\) the unital channels \[\begin{align} \mathcal{P}_{AB}^{(n)}(\,\cdot\,)&\relax\frac{1}{n!}\sum_{\pi \in S_n} \big(P^{A^n}_{\pi}\otimes P^{B^n}_{\pi}\big) (\,\cdot\,) \big(P^{A^n}_{\pi}\otimes P^{B^n}_{\pi}\big)^\dagger,\\ \mathcal{P}_{A}^{(n)}(\,\cdot\,)&\relax\frac{1}{n!}\sum_{\pi \in S_n} P^{A^n}_{\pi} (\,\cdot\,) P^{A^n\, ^\dagger}_{\pi}, \end{align}\] respectively. In (i) we have used that the random purification channel symmetrises the input, in (ii) we have recalled that, for permutation invariant inputs, the output of the random purification reduces to the original state when tracing out the auxiliary system \(E^n\), and in (iii) we have noticed that the unital channel \(\mathcal{P}_{A}^{(n)}\) acts on \(\mathop{\mathrm{Tr}}_{B^n}\left[X_{(AB)^n}\right]=\kappa\mathbb{1}_{A^n}\). This concludes the proof. ◻

Proof. Without loss of generality, it is sufficient to verify 11 for pure states as inputs. Using 7 , we have \[\label{eq:firststep} \Omega(\ket{\psi}\!\!\bra{\psi})=\sum_{\sigma,\tau\in S_n} \mathrm{Wg}(\sigma^{-1}\tau)\mathop{\mathrm{Tr}}_{E^n}[(\mathbb{1}_{B^n}\otimes U_{\sigma}^{\dagger})V^{\otimes n}\left(\ket{\psi}\!\!\bra{\psi}\right) V^{\dagger}{}^{\otimes n}]\otimes U_{\tau}.\tag{12}\] Now, we note that \[\begin{align} (\mathbb{1}_{B^n}\otimes U_{\sigma}^{\dagger})V^{\otimes n}\ket{\psi}&=(U_{\sigma}\otimes \mathbb{1}_{E^n})(U_{\sigma}^{\dagger}\otimes U_{\sigma}^{\dagger})V^{\otimes n}\ket{\psi} \\ &=(U_{\sigma}\otimes \mathbb{1}_{E^n})V^{\otimes n}(U_{\sigma}^{\dagger}\ket{\psi}) \,, \end{align}\] where we used that \(V_{A\to BE}^{\otimes n}(U_{\sigma}^{\dagger}\ket{\psi}_{A^n})=(U_{\sigma}^{\dagger}\otimes U_{\sigma}^{\dagger})V_{A\to BE}^{\otimes n}\ket{\psi}_{A^n}\). Inserting this into 12 , we have \[\begin{align}\label{eq:secondstep} \Omega(\ket{\psi}\!\!\bra{\psi}) &= \sum_{\sigma,\tau\in S_n} \mathrm{Wg}(\sigma^{-1}\tau) \mathop{\mathrm{Tr}}_{E^n}\!\left[(U_{\sigma}\otimes \mathbb{1}_{E^n})V^{\otimes n}\left(U_{\sigma}^{\dagger}\ket{\psi}\!\!\bra{\psi}\right) V^{\dagger}{}^{\otimes n}\right]\otimes U_{\tau}\\ &= \sum_{\sigma,\tau\in S_n} \mathrm{Wg}(\sigma^{-1}\tau) \left( U_{\sigma}\Phi^{\otimes n}(U_{\sigma}^{\dagger}\ket{\psi}\!\!\bra{\psi})\right)\otimes U_{\tau}\\ &\stackrel{\mathclap{\scriptsize (i)}}{=} \sum_{\sigma,\tau\in S_n}\frac{1}{(n!)^2}\sum_{\lambda\vdash n,\, l(\lambda)\leq r}\frac{\mathrm{dim}^2[\lambda]}{\mathrm{dim}[\mathcal{U}_{r,\lambda}]}\, \chi_{\lambda}(\sigma^{-1}\tau) \left(U_{\sigma}\Phi^{\otimes n}(U_{\sigma}^{\dagger}\ket{\psi}\!\!\bra{\psi})\right)\otimes U_{\tau}\\ &\stackrel{\mathclap{\scriptsize (ii)}}{=} \sum_{\sigma,\tau'\in S_n}\frac{1}{(n!)^2}\sum_{\lambda\vdash n,\, l(\lambda)\leq r}\frac{\mathrm{dim}^2[\lambda]}{\mathrm{dim}[\mathcal{U}_{r,\lambda}]}\,\chi_{\lambda}(\tau') \left(U_{\sigma}\Phi^{\otimes n}(U_{\sigma}^{\dagger}\ket{\psi}\!\!\bra{\psi})\right)\otimes \left(U_{\sigma}U_{\tau'}\right)\\ &\stackrel{\mathclap{\scriptsize (iii)}}{=} \sum_{\sigma\in S_n}\frac{1}{n!}\sum_{\lambda\vdash n,\, l(\lambda)\leq r}\frac{\mathrm{dim}[\lambda]}{\mathrm{dim}[\mathcal{U}_{r,\lambda}]}\left( U_{\sigma}\Phi^{\otimes n}(U_{\sigma}^{\dagger}\ket{\psi}\!\!\bra{\psi})\right)\otimes \left(U_{\sigma}\Pi_{\lambda}\right)\,. \end{align}\tag{13}\] where in (i) we used 8 , in (ii) we have changed variable \(\tau \to \tau'=\sigma^{-1}\tau\), which is a one-to-one mapping, and in (iii) we used 6 . ◻

Proof. It suffices to prove that \[\mathcal{C}(\ket{\psi}\!\!\bra{\psi})=\Omega(\ket{\psi}\!\!\bra{\psi})\,\qquad\forall \ket{\psi}\in \mathcal{H}_{A}^{\otimes n}\,.\] Let us first compute the left-hand side: \[\begin{align} \mathcal{E}(\ket{\psi}\!\!\bra{\psi})=\frac{1}{n!}\sum_{\sigma,\tau\in S_n}\ket{\sigma}\!\!\bra{\tau}\otimes U_{\sigma}\ket{\psi}\!\!\bra{\psi}U^{\dagger}_{\tau}\,. \end{align}\] Then, applying \(\Phi^{\otimes n}\) on the register \(A^n\), we obtain \[\begin{align} \big(\mathrm{Id}_{\widehat{S_n}}\otimes\Phi^{\otimes n}\big) \circ \mathcal{E}(\ket{\psi}\!\!\bra{\psi})&=\frac{1}{n!}\sum_{\sigma,\tau\in S_n}\ket{\sigma}\!\!\bra{\tau}\otimes \Phi^{\otimes n}(U_{\sigma}\ket{\psi}\!\!\bra{\psi}U^{\dagger}_{\tau})\\ &=\frac{1}{n!}\sum_{\sigma,\tau\in S_n}\ket{\sigma}\!\!\bra{\tau}\otimes U_{\tau}\Phi^{\otimes n}(U_{\tau^{-1}\sigma}\ket{\psi}\!\!\bra{\psi})U^{\dagger}_{\tau}\,\,, \end{align}\] where in the last line we exploited that \(\Phi^{\otimes n} (\,\cdot\,)=U_\tau\Phi^{\otimes n}(\,U_\tau^\dagger (\,\cdot\,)U_\tau)U_\tau^\dagger\). Going forward, let us now apply \(\mathcal{D}\): \[\begin{align} &\mathcal{D}\circ \big(\mathrm{Id}_{\widehat{S_n}}\otimes \Phi^{\otimes n}\big)\circ \mathcal{E}(\ket{\psi}\!\!\bra{\psi})\\ &\qquad =\frac{1}{n!}\sum_{\sigma,\tau\in S_n}\sum_{\lambda,\lambda',i,j,k,l}\frac{\sqrt{\mathrm{dim}[\lambda]\mathrm{dim}[\lambda']}}{n!}\!\! && R_{\lambda}(\sigma)_{i,j}\ket{\lambda,i,j}\!\!\bra{\lambda',k,l}R_{\lambda'}(\tau)_{k,l} \,\otimes \\[-0.6em] & && \quad\otimes U_{\sigma^{-1}\tau}\Phi^{\otimes n}(U_{\tau^{-1}\sigma}\ket{\psi}\!\!\bra{\psi})\,, \end{align}\] where we used 9 and the fact that representation matrices \(R_{\lambda}(\sigma)\) are real-valued.

Now, we would like to apply the channel \(\mathcal{T}\) to the auxiliary register \(\widehat{S_n}\). Recall that \(\mathcal{T}\), defined in Eq. 14 , acts differently depending on whether the associated Young diagram \(\lambda\) satisfies \(l(\lambda)\le r\) or not. In order to simplify the analysis, we first observe that only the terms with \(l(\lambda)\le r\) give a nonzero contribution. Indeed, note that \[\begin{align} \sum_{\sigma,\tau\in S_n}&\sum_{\lambda,i,j,l}\frac{\mathrm{dim}[\lambda]}{n!^2}R_{\lambda}(\sigma)_{i,j}R_{\lambda}(\tau)_{i,l}\ket{\lambda,j}\!\!\bra{\lambda,l}\otimes U_{\sigma^{-1}\tau}\Phi^{\otimes n}(U_{\tau^{-1}\sigma}\ket{\psi}\!\!\bra{\psi})\\ &\stackrel{\mathclap{\scriptsize (v)}}{=}\sum_{\sigma,\tau\in S_n}\sum_{\lambda,i,j,l}\frac{\mathrm{dim}[\lambda]}{n!^2}R_{\lambda}(\sigma^{-1})_{j,i}R_{\lambda}(\tau)_{i,l}\ket{\lambda,j}\!\!\bra{\lambda,l}\otimes U_{\sigma^{-1}\tau}\Phi^{\otimes n}(U_{\tau^{-1}\sigma}\ket{\psi}\!\!\bra{\psi})\\ &\stackrel{\mathclap{\scriptsize (vi)}}{=}\sum_{\sigma\in S_n}\sum_{\lambda,j,l}\frac{\mathrm{dim}[\lambda]}{n!}R_{\lambda}(\sigma)_{j,l}\ket{\lambda,j}\!\!\bra{\lambda,l}\otimes U_{\sigma}\Phi^{\otimes n}(U_{\sigma^{-1}}\ket{\psi}\!\!\bra{\psi})\\ &\stackrel{\mathclap{\scriptsize (vii)}}{=}\sum_{\sigma\in S_n}\sum_{\lambda,j,l}\frac{\mathrm{dim}[\lambda]}{n!}R_{\lambda}(\sigma)_{j,l}\ket{\lambda,j}\!\!\bra{\lambda,l}\otimes U_{\sigma}\mathop{\mathrm{Tr}}_{E^n}[V^{\otimes n}(U_{\sigma^{-1}}\ket{\psi}\!\!\bra{\psi})V^{\dagger}{}^{\otimes n}]\\ &\stackrel{\mathclap{\scriptsize (viii)}}{=}\sum_{\sigma\in S_n}\sum_{\lambda,j,l}\frac{\mathrm{dim}[\lambda]}{n!}R_{\lambda}(\sigma)_{j,l}\ket{\lambda,j}\!\!\bra{\lambda,l}\otimes \mathop{\mathrm{Tr}}_{E^n}[(\mathbb{1}_{B^n}\otimes U_{\sigma^{-1}}) V^{\otimes n}(\ket{\psi}\!\!\bra{\psi})V^{\dagger}{}^{\otimes n}], \end{align}\] where in (v) we used that the \(R_{\lambda}(\sigma)^{\dagger}=R_{\lambda}(\sigma)^{\intercal}=R_{\lambda}(\sigma^{-1})\) are real, and in (vi) we contracted the two representation matrices \(R_{\lambda}\) and changed variable, in (vii) we wrote \(\Phi\) in terms of its dilation, and in (viii) we used the permutation covariance of \(V^{\otimes n}\). By using that the dimension of the Stinespring environment \(E\) is \(r\), we can now insert the resolution of the identity in the \(E^n\) space \[\begin{align} \mathbb{1}_{E^n}=\sum_{\lambda'\vdash n, l(\lambda')\leq r}\Pi_{\lambda'}=\sum_{\lambda'\vdash n, l(\lambda')\leq r}\frac{\mathrm{dim}[\lambda']}{n!}\sum_{\pi\in S_n}\chi_{\lambda'}(\pi)U_{\pi}\,, \end{align}\] and use the invariance of the measure on the group to obtain \[\begin{align} &\sum_{\sigma\in S_n}\sum_{\lambda,j,l}R_{\lambda}(\sigma)_{j,l}\ket{\lambda,j}\!\!\bra{\lambda,l}\otimes \mathop{\mathrm{Tr}}_{E^n}[(\mathbb{1}_{B^n}\otimes U_{\sigma^{-1}}) V^{\otimes n}(\ket{\psi}\!\!\bra{\psi})V^{\dagger}{}^{\otimes n}]\\ &\qquad \stackrel{\mathclap{\scriptsize (ix)}}{=}\sum_{\lambda'\vdash n,\, l(\lambda')\leq r}\sum_{\sigma,\pi\in S_n}\sum_{\lambda,j,l}\frac{\mathrm{dim}[\lambda']}{n!}\chi_{\lambda'}(\pi)R_{\lambda}(\sigma)_{j,l}\ket{\lambda,j}\!\!\bra{\lambda,l}\\&\qquad\otimes \mathop{\mathrm{Tr}}_{E^n}[(\mathbb{1}_{B^n}\otimes U_{\sigma^{-1}}U_{\pi}) V^{\otimes n}(\ket{\psi}\!\!\bra{\psi})V^{\dagger}{}^{\otimes n}]\\ &\qquad \stackrel{\mathclap{\scriptsize (x)}}{=}\sum_{\lambda'\vdash n,\, l(\lambda')\leq r}\sum_{\sigma,\pi\in S_n}\sum_{\lambda,j,l}\frac{\mathrm{dim}[\lambda']}{n!}\chi_{\lambda'}(\pi)R_{\lambda}(\sigma\pi)_{j,l}\ket{\lambda,j}\!\!\bra{\lambda,l}\\&\qquad\otimes \mathop{\mathrm{Tr}}_{E^n}[(\mathbb{1}_{B^n}\otimes U_{\sigma^{-1}}) V^{\otimes n}(\ket{\psi}\!\!\bra{\psi})V^{\dagger}{}^{\otimes n}]\\ &\qquad \stackrel{\mathclap{\scriptsize (xi)}}{=}\sum_{\lambda'\vdash n,\, l(\lambda')\leq r}\sum_{\sigma\in S_n}\sum_{\lambda,j,l}R_{\lambda}(\sigma)_{j,l}\Pi_{\lambda'}^{\widehat{S}_n}\ket{\lambda,j}\!\!\bra{\lambda,l}\otimes \mathop{\mathrm{Tr}}_{E^n}[(\mathbb{1}_{B^n}\otimes U_{\sigma^{-1}}) V^{\otimes n}(\ket{\psi}\!\!\bra{\psi})V^{\dagger}{}^{\otimes n}]\\ &\qquad \stackrel{\mathclap{\scriptsize (xii)}}{=}\sum_{\lambda\vdash n,\, l(\lambda)\leq r}\sum_{\sigma\in S_n}\sum_{j,l}R_{\lambda}(\sigma)_{j,l}\ket{\lambda,j}\!\!\bra{\lambda,l}\otimes \mathop{\mathrm{Tr}}_{E^n}[(\mathbb{1}_{B^n}\otimes U_{\sigma^{-1}}) V^{\otimes n}(\ket{\psi}\!\!\bra{\psi})V^{\dagger}{}^{\otimes n}]\\ &\qquad=\sum_{\lambda\vdash n,\, l(\lambda)\leq r}\sum_{\sigma\in S_n}\sum_{j,l}R_{\lambda}(\sigma)_{j,l}\ket{\lambda,j}\!\!\bra{\lambda,l}\otimes U_{\sigma}\Phi^{\otimes n}(U_{\sigma^{-1}}\ket{\psi}\!\!\bra{\psi})\,, \end{align}\] where in (ix) we inserted the resolution of the identity in terms of \(\Pi_{\lambda}\) and their expression as linear combinations of permutations, in (x) we used the invariance of the measure on the group, in (xi) we recollected the isotypical projector \(\Pi_{\lambda'}^{\widehat{S}_n}\) in the representation space \(\bigoplus_{\lambda \vdash n}[\lambda]\) and in (xii) we used that \(\Pi_{\lambda'}^{\widehat{S}_n}\ket{\lambda,i}=\delta_{\lambda,\lambda'}\ket{\lambda,i}\). This means that when \(V\) is defined with an environment of dimension at most \(r\), we can restrict the sum over Young diagrams with length at most \(r\).

Then, applying \(\mathcal{T}\) to the register \(\widehat{S_n}\), we obtain: \[\begin{align} &(\mathcal{T}\otimes \mathrm{Id}_{B^n})\circ \mathcal{D} \circ \big(\mathrm{Id}_{\widehat{S_n}}\otimes \Phi^{\otimes n}\big) \circ \mathcal{E}(\ket{\psi}\!\!\bra{\psi}) \\ &\qquad=\sum_{\sigma\in S_n}\sum_{\lambda\vdash n,\, l(\lambda)\leq r}\frac{\mathrm{dim}[\lambda]}{n!\mathrm{dim}[\mathcal{U}_{r,\lambda}]}\sum_{j,l}R_{\lambda}(\sigma)_{j,l}\ket{\lambda,j}\!\!\bra{\lambda,l}\otimes\mathbb{1}_{\mathcal{U}_{r,\lambda}} \otimes U_{\sigma}\Phi^{\otimes n}(U_{\sigma}^{\dagger}\ket{\psi}\!\!\bra{\psi}) \end{align}\] As a consequence, we conclude that \[\begin{align} \mathcal{C}(\ket{\psi}\!\!\bra{\psi})&= \sum_{\sigma\in S_n}\sum_{\lambda\vdash n,\, l(\lambda)\leq r}\frac{\mathrm{dim}[\lambda]}{n!\mathrm{dim}[\mathcal{U}_{r,\lambda}]}\, \Pi_{\lambda}U_{\sigma}\otimes U_{\sigma}\Phi^{\otimes n}(U_{\sigma}^{\dagger}\ket{\psi}\!\!\bra{\psi})\,, \end{align}\] where we used the Schur–Weyl duality in 5 to write that \[\begin{align} U_{\mathrm{Schur}}^{\dagger}\Pi_{\lambda}U_{\sigma}U_{\mathrm{Schur}}= \sum_{j,l}R_{\lambda}(\sigma)_{j,l}\ket{\lambda,j}\!\!\bra{\lambda,l} \otimes \mathbb{1}_{\mathcal{U}_{r,\lambda}}\,. \end{align}\] Comparing with 11 (with the appropriate identification of the subsystems in the tensor product), we obtain the claim. ◻

Proof of Theorem 1. The existence of encoding maps, a memory system, and decoding maps satisfying ?? follows directly from Theorem 4. Furthermore, the efficiency of the circuit implementing the random Stinespring superchannel is established by Remark 5. ◻

Proof. Let \(J_{(A'B)^n}\) be the Choi operator of the channel \(\underset{\scaleobj{.8}{\Lambda\sim \nu}}{\mathbb{E}\,}\Lambda^{\otimes n}\), and let \(H_{d,n}^{\rm sym}\) be the real vector space of permutationally symmetric Hermitian operators on \(\mathcal{H}_{A'B}^{\otimes n}\); then, \[\begin{align}\label{eq:convex} J_{(A'B)^n} = \underset{\scaleobj{.8}{\Lambda\sim \nu}}{\mathbb{E}\,}\big[\Lambda^{\otimes n}_{A\to B}(\Gamma_{A'A}^{\otimes n})\big]= \underset{\scaleobj{.8}{\Lambda\sim \nu}}{\mathbb{E}\,}\big[(J^{\Lambda}_{A'B})^{\otimes n}\big]\in H_{d,n}^{\rm sym} . \end{align}\tag{19}\] By Schur–Weyl duality, \(H_{d,n}^{\rm sym}\) has the form \[\begin{align} H_{d,n}^{\rm sym}=\bigoplus_{\lambda\in\pazocal{Y}_n^d} \mathbb{1}_{[\lambda]}\otimes H(\pazocal{U}_\lambda), \label{eq:space95perm95symm95operators} \end{align}\tag{20}\] where \(\lambda\) ranges on the set \(\pazocal{Y}_d^n\) of Young diagrams with size \(n\) and depth at most \(d\), \(\pazocal{U}_\lambda\) and \([\lambda]\) are irreducible representations of the special unitary group \({\rm SU}(d)\) and of the symmetric group \(S_n\), respectively, and \(H(\pazocal{U}_\lambda)\) is the space of Hermitian operators on \(\pazocal{U}_\lambda\). Leveraging the fact that \(\dim \pazocal{U}_\lambda\leq (n+1)^{d(d-1)/2}\) and \(|\pazocal{Y}_n^d|\leq (n+1)^{d-1}\) [@Hayashi2016_grouptheoretic], we can upper bound \(\dim H_{d,n}^{\rm sym}\leq (n+1)^{d^2-1}\). As a consequence, since \(J_{(A'B)^n}\in H_{d,n}^{\rm sym}\) belongs to the convex hull of \(\big\{(J^{\Lambda}_{A'B})^{\otimes n}: \Lambda\in{\rm supp}(\nu) \big\}\), by Carathéodory’s theorem we can write it as a convex combination of at most \(N=(n+1)^{d^2-1} +1\) Choi operators \((J_{A'B}^{\Lambda_i})^{\otimes n}\) for suitable channels \(\Lambda_i\in{\rm supp}(\nu)\): \[\begin{align} J_{(A'B)^n}=\sum_{i=1}^Np_i(J_{A'B}^{\Lambda_i})^{\otimes n}, \end{align}\] hence \[\begin{align} \underset{\scaleobj{.8}{\Lambda\sim \nu}}{\mathbb{E}\,}\Lambda^{\otimes n}=\sum_{i=1}^Np_i \Lambda_i^{\otimes n}. \end{align}\] Then, \[\begin{align} \mathbb{D}\left(\underset{\scaleobj{.8}{\Lambda\sim \nu}}{\mathbb{E}\,}\Lambda^{\otimes n}\,\middle\|\,\Gamma^{(n)}\right) &=\sup_{\rho_{RA^n}}\mathbb{D}\left(\sum_{i=1}^Np_i\Lambda_i^{\otimes n}(\rho)\,\middle\|\,\Gamma^{(n)}(\rho)\right)\\ &\geq \sup_{\rho_{RA^n}} \min_{1\leq i\leq N} \mathbb{D}\left(\Lambda_i^{\otimes n}(\rho)\,\middle\|\,\Gamma^{(n)}(\rho)\right)-\log {\rm poly}_{d}\Big(n,\,\big|\mathrm{spec}\big(\Gamma^{(n)}(\rho)\big)\big|\Big) \\ &\geq \sup_{\rho_{RA^n}} \min_{\Lambda\in\mathop{\mathrm{supp}}(\nu)} \mathbb{D}\left(\Lambda^{\otimes n}(\rho)\,\middle\|\,\Gamma^{(n)}(\rho)\right)-\log {\rm poly}_{d}\Big(n,\,\big|\mathrm{spec}\big(\Gamma^{(n)}(\rho)\big)\big|\Big), \end{align}\] where in the first inequality we have used the weak quasi-concavity of \(\mathbb{D}\) and the fact that \(N={\rm poly}_{d}(n)\). This concludes the proof. ◻

Proof. Let \(V^{\pazocal{M}}_{A\to BE}:\mathcal{H}_A\to \mathcal{H}_{BE}\) be the isometry such that \(\pazocal{V}^{\pazocal{M}}_{A\to BE}(\,\cdot\,) = V^{\pazocal{M}}_{A\to BE} (\,\cdot\,) \big(V^{\pazocal{M}}_{A\to BE}\big)^\dagger\), and let \(W^{ \begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\pazocal{M}} \endgroup }_{A\to BFG}:\mathcal{H}_A\to \mathcal{H}_{BFG}\) be the isometry corresponding to a Stinespring dilation of \(\begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\pazocal{M}} \endgroup _{A\to BF}\), i.e.such that \[\begin{align} \begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\pazocal{M}} \endgroup _{A\to BF}(\,\cdot\,) = \mathop{\mathrm{Tr}}_G \Big[ W^{ \begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\pazocal{M}} \endgroup }_{A\to BFG} (\,\cdot\,) \big(W^{ \begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\pazocal{M}} \endgroup }_{A\to BFG}\big)^\dagger \Big] . \end{align}\] Since \[\begin{align} \dim \mathcal{H}_{FG} = (\dim \mathcal{H}_F) (\dim \mathcal{H}_G) \geq \dim \mathcal{H}_F \geq \dim \mathcal{H}_E , \end{align}\] elementary linear algebra considerations ensure that we can construct an isometry \(Z_{E\to FG}:\mathcal{H}_E\to \mathcal{H}_{FG}\) with the property that \[\begin{align} Z_{E\to FG} \circ V^{\pazocal{M}}_{A\to BE} = W^{ \begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\pazocal{M}} \endgroup }_{A\to BFG} . \end{align}\] Defining \(\Lambda_{E\to F}(\,\cdot\,) \relax\mathop{\mathrm{Tr}}_G \big[ Z_{E\to FG}^{\vphantom{\dagger}} (\,\cdot\,) Z_{E\to FG}^\dagger\big]\), we see that \[\begin{align} \begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\pazocal{M}} \endgroup _{A\to BF}(\,\cdot\,) &= \mathop{\mathrm{Tr}}_G \Big[ W^{ \begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\pazocal{M}} \endgroup }_{A\to BFG} (\,\cdot\,) \big(W^{ \begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\pazocal{M}} \endgroup }_{A\to BFG}\big)^\dagger \Big] \\ &= \mathop{\mathrm{Tr}}_G \Big[ \big(Z_{E\to FG} \circ V^{\pazocal{M}}_{A\to BE}\big) (\,\cdot\,) \big(Z_{E\to FG} \circ V^{\pazocal{M}}_{A\to BE}\big)^\dagger \Big] \\ &= \big(\Lambda_{E\to F}\circ \pazocal{V}^{\pazocal{M}}_{A\to BE}\big)(\,\cdot\,) , \end{align}\] which concludes the proof. ◻

Proof. As in the proof of Lemma 3, applying Carathéodory’s theorem to the Choi state of the channel \(\underset{\scaleobj{.8}{\pazocal{V}\sim \nu}}{\mathbb{E}\,}\pazocal{V}^{\otimes n}_{A\to B}\), which belongs to the real vector space of Hermitian permutationally symmetric operators on \(\mathcal{H}_{A'B}^{\otimes n}\), we can write \[\begin{align} \underset{\scaleobj{.8}{\pazocal{V}\sim \nu}}{\mathbb{E}\,} \pazocal{V}^{\otimes n}_{A\to B} = \sum_{i=1}^N p_i \pazocal{V}^{\otimes n}_{i}\, , \label{lemma:bound95spec95proof95eq1} \end{align}\tag{21}\] for some choice of isometries \(\pazocal{V}_{i}:\mathcal{H}_A\to \mathcal{H}_B\), \(i=1,\ldots,N\), and \[\begin{align} N=(n+1)^{(d_A d_B)^2-1} + 1 \leq (n+1)^{d_B^4-1} + 1\, . \end{align}\] Applying 21 to \(\psi_{A^nR}\) and noticing that \(\big|\mathrm{spec}\big(\sum\nolimits_{i=1}^N p_i \Psi_i \big)\big| \leq N+1\) directly shows the claim. ◻

Proof. The inequality \(\mathbb{D}^{\infty}(\pazocal{M}\|\pazocal{N})\leq \mathbb{D}^\infty\big( \begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\pazocal{M}} \endgroup _{A\to BE}\,\big\|\,\mathcal{C}_{A\to BE}^{\pazocal{N}}\big)\) immediately follows from the data-processing inequality for \(\mathbb{D}\), by applying the channel \({\rm Id}_{B^n}\otimes\mathop{\mathrm{Tr}}_{E^n}[\,\cdot\,]\) in the very definition of the right-hand-side of ?? for any \(n\geq 1\).

Let us now prove the converse inequality. First, it suffices to consider the case where the \(E\)-dilation \[\begin{align} \begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\pazocal{M}} \endgroup _{A\to BE}(\,\cdot\,) = \pazocal{V}^{\pazocal{M}}_{A\to BE}(\,\cdot\,)\relax V^{\pazocal{M}}_{A\to BE}\,\cdot\,V^{\pazocal{M}\; \dagger}_{A\to BE} \end{align}\] of \(\pazocal{M}_{A\to B}\) is an isometry. Indeed, by Lemma 4, any other \(E\)-dilation \(\begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\pazocal{M}} \endgroup '_{A\to BE}\) can be obtained by applying a suitable quantum channel \(\Lambda_{E\to E}\) to the auxiliary system: \[\begin{align} \begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\pazocal{M}} \endgroup '_{A\to BE} =({\rm Id}_B\otimes \Lambda_{E\to E})\circ \pazocal{V}^{\pazocal{M}}_{A\to BE}. \end{align}\] Hence, \[\begin{align} \inf_{ \begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\pazocal{N}} \endgroup \in \pazocal{C}_{n}^{\pazocal{N}}} \mathbb{D}\Big( \begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\pazocal{M}} \endgroup '^{\,\otimes n}_{A\to BE}\,\Big\|\, \begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\pazocal{N}} \endgroup _{A^n\to B^nE^n}\Big) &\leq \inf_{\widetilde{\pazocal{N}}\in \pazocal{C}_{n}^{\pazocal{N}}} \mathbb{D}\Big(\Lambda_{E\to E'}^{\otimes n}\circ \pazocal{V}^{\pazocal{M}\;\otimes n}_{A\to BE}\,\Big\|\,\Lambda_{E\to E'}^{\otimes n}\circ \widetilde{\pazocal{N}}_{A^n\to B^nE^n}\Big) \\ &\leq \inf_{\widetilde{\pazocal{N}}\in \pazocal{C}_{n}^{\pazocal{N}}} \mathbb{D}\Big(\pazocal{V}^{\pazocal{M}\;\otimes n}_{A\to BE}\,\Big\|\,\widetilde{\pazocal{N}}_{A^n\to B^nE^n}\Big)\, . \end{align}\] Here, the first inequality holds by taking as ansatzes all \(E\)-dilations of \(\pazocal{N}_{A\to B}\) of the form \(\Lambda_{E\to E'}^{\otimes n}\circ \widetilde{\pazocal{N}}_{A^n\to B^nE^n}\), where \(\widetilde{\pazocal{N}}_{A^n\to B^nE^n} \in \pazocal{C}^{\pazocal{N}}_n \relax\pazocal{C}^{\pazocal{N}^{\otimes n}}_{A^n\to B^nE^n}\); the second inequality, instead, is simply data-processing. Now we are going to show that the right-hand-side of the above equation is upper bounded by \(n\mathbb{D}^\infty(\pazocal{M}\|\pazocal{N})\) up to terms that are sublinear in \(n\); this will complete the proof. To this end, we lower bound \[\begin{align} \label{eq:inequalities} \frac{1}{n}\mathbb{D}\left(\pazocal{M}_{A\to B}^{\otimes n}\middle\|\pazocal{N}_{A\to B}^{\otimes n}\right) &= \sup_{\rho_{A^nR}}\frac{1}{n}\mathbb{D}\left(\pazocal{M}_{A\to B}^{\otimes n}(\rho_{A^nR})\middle\|\pazocal{N}_{A\to B}^{\otimes n}(\rho_{A^nR})\right)\\ \nonumber& \stackrel{\mathclap{\scriptsize (i)}}{\geq} \sup_{\tilde{\rho}_{A^nR'}}\frac{1}{n}\mathbb{D}\left((\pazocal{M}_{A\to B}^{\otimes n}\circ \pazocal{E}_{A^n\to A^nM})(\tilde{\rho}_{A^nR'}) \middle\|(\pazocal{N}_{A\to B}^{\otimes n}\circ \pazocal{E}_{A^n\to A^nM})(\tilde{\rho}_{A^nR'})\right)\\ \nonumber&\stackrel{\mathclap{\scriptsize (ii)}}{\geq}\sup_{\tilde{\rho}_{A^nR'}}\frac{1}{n}\mathbb{D}\left(\underset{\scaleobj{.8}{\pazocal{V}^{\pazocal{M}}}}{\mathbb{E}\,}\Big[\pazocal{V}^{\pazocal{M}\;\otimes n}_{A\to BE}(\tilde{\rho}_{A^nR'})\Big]\,\middle\|\, \underset{\scaleobj{.8}{\pazocal{V}^{\pazocal{N}}}}{\mathbb{E}\,}\Big[\pazocal{V}^{\pazocal{N}\;\otimes n}_{A\to BE}(\tilde{\rho}_{A^nR'})\Big]\right)\\[4pt] \nonumber&\stackrel{\mathclap{\scriptsize (iii)}}{\geq}\sup_{\tilde{\rho}_{A^nR'}}\frac{1}{n}\min_{\pazocal{V}^{\pazocal{M}}}\mathbb{D}\left(\pazocal{V}^{\pazocal{M}\;\otimes n}_{A\to BE}(\tilde{\rho}_{A^nR'})\,\middle\|\, \underset{\scaleobj{.8}{\pazocal{V}^{\pazocal{N}}}}{\mathbb{E}\,}\Big[\pazocal{V}^{\pazocal{N}\;\otimes n}_{A\to BE}(\tilde{\rho}_{A^nR'})\Big]\right)-\tfrac{\log{\rm poly }(n)}{n}\\[4pt] \nonumber& \stackrel{\mathclap{\scriptsize (iv)}}{=}\frac{1}{n}\mathbb{D}\left( \begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\pazocal{V}} \endgroup ^{\pazocal{M}\;\otimes n}_{A\to BE}\,\middle\|\, \underset{\scaleobj{.8}{\pazocal{V}^{\pazocal{N}}}}{\mathbb{E}\,}\Big[\pazocal{V}^{\pazocal{N}\;\otimes n}_{A\to BE}\Big]\right)-\tfrac{\log{\rm poly }(n)}{n}\\[4pt] \nonumber&\stackrel{\mathclap{\scriptsize (v)}}{\geq}\frac{1}{n}\inf_{\tilde{\pazocal{N}}\in\pazocal{C}_n^{\pazocal{N}}}\mathbb{D}\left( \begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\pazocal{V}} \endgroup ^{\pazocal{M}\;\otimes n}_{A\to BE}\,\middle\|\, \tilde{\pazocal{N}}\right)-\tfrac{\log{\rm poly }(n)}{n}, \end{align}\tag{22}\] where \(\pazocal{C}^{\pazocal{N}}_n \relax\pazocal{C}^{\pazocal{N}^{\otimes n}}_{A^n\to B^nE^n}\), as before, and \[\begin{align} \underset{\scaleobj{.8}{\pazocal{V}^{\pazocal{M}}}}{\mathbb{E}\,}\Big[\pazocal{V}^{\pazocal{M}\;\otimes n}_{A\to BE}(\tilde{\rho}_{A^nR'})\Big]\relax\underset{\scaleobj{.8}{U_E}}{\mathbb{E}\,}\!\left[ \big((\mathbb{1}_B\otimes U_E)V^{\pazocal{M}}_{A\to BE}\big)^{\otimes n} (\tilde{\rho}_{A^nR'}) \big(V_{A\to BE}^{\pazocal{M}\;\dagger}(\mathbb{1}_B\otimes U_E^\dagger)\big)^{\otimes n} \right]; \end{align}\] in particular,

• in (i) we have chosen the auxiliary system \(R\) to be of the form \(R=MR'\), with \(R'\) arbitrary and \(M\) being the memory system appearing in Theorem 1, and we have restricted the supremum to states \(\rho_{A^nR}\) of the form \((\pazocal{E}_{A^n\to A^n M}\otimes {\rm Id}_{R'})(\tilde{\rho}_{A^nR'})\), where \(\tilde{\rho}_{A^nR'}\) is arbitrary and \(\pazocal{E}_{A^n\to A^nM}\) is the encoder introduced in Theorem 1;

• the lower bound in (ii) is the data-processing inequality when applying the decoding channel \(\pazocal{D}_{B^nM\to B^nE^n}\) of Theorem 1 to both arguments of the divergence \(\mathbb{D}\); as a result, by ?? , we get \(n\) copies of the random Stinespring dilations \(\pazocal{V}^{\pazocal{M}}_{A\to BE}\) of \(\pazocal{M}\) and \(\pazocal{V}^{\pazocal{N}}_{A\to BE}\) of \(\pazocal{N}\), respectively;

• in (iii) we have leveraged Lemmas 3 and 5, noting that the supremum can be restricted to pure states due to joint convexity of \(\mathbb{D}\);

• in (iv) we have noticed that the function of \(\pazocal{V}^{\pazocal{M}}_{A\to BE}\) to be minimised actually is independent of \(\pazocal{V}^{\pazocal{M}}_{A\to BE}\), therefore we can choose any arbitrary fixed dilation \(\begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\pazocal{V}} \endgroup ^{\pazocal{M}}_{A\to BE}\); indeed, for any fixed Stinespring dilation \(\pazocal{V}^{\pazocal{M}}_{A\to BE}\), we can apply a local unitary channel \(\pazocal{U}_E\) on the system \(E\) to get \(\begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\pazocal{V}} \endgroup ^{\pazocal{M}}_{A\to BE}\); in particular, by the unitary invariance of \(\mathbb{D}\) — which follows from the data-processing inequality — and by the left-invariance of the Haar measure, we have \[\begin{align} &\mathbb{D}\left(\pazocal{V}^{\pazocal{M}\;\otimes n}_{A\to BE}(\rho_{A^nR'})\middle\| \;\underset{\scaleobj{.8}{\pazocal{V}^{\pazocal{N}}}}{\mathbb{E}\,}\Big[\pazocal{V}^{\pazocal{N}\;\otimes n}_{A\to BE}(\rho_{A^nR'})\Big]\right)\\ &\qquad =\mathbb{D}\left(\big(\pazocal{U}_{E}\circ\pazocal{V}^{\pazocal{M}}_{A\to BE}\big)^{\otimes n}(\rho_{A^nR'})\middle\| \,\underset{\scaleobj{.8}{\pazocal{V}^{\pazocal{N}}}}{\mathbb{E}\,}\Big[\big(\pazocal{U}_E\circ\pazocal{V}^{\pazocal{N}}_{A\to BE}\big)^{\otimes n}(\rho_{A^nR'})\Big]\right)\\ &\qquad=\mathbb{D}\left( \begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\pazocal{V}} \endgroup ^{\pazocal{M}\;\otimes n}_{A\to BE}(\rho_{A^nR'})\middle\| \;\underset{\scaleobj{.8}{\pazocal{V}^{\pazocal{N}}}}{\mathbb{E}\,}\Big[\pazocal{V}^{\pazocal{N}\;\otimes n}_{A\to BE}(\rho_{A^nR'})\Big]\right); \end{align}\]

• finally, in (v) we have noticed that \(\underset{\scaleobj{.8}{\pazocal{V}^{\pazocal{N}}}}{\mathbb{E}\,}\Big[\pazocal{V}^{\pazocal{N}\;\otimes n}_{A\to BE}\Big]\in \pazocal{C}_{A^n\to B^n E^n}^{\pazocal{N}^{\otimes n}}\).

Taking the limit \(n\to\infty\) in 22 , we get \[\begin{align} \mathbb{D}^{\infty}(\pazocal{M}\|\pazocal{N}) \geq \liminf_{n\rightarrow\infty}\frac{1}{n}\inf_{\tilde{\pazocal{N}}\in\pazocal{C}_n^{\pazocal{N}}}\mathbb{D}\left( \begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\pazocal{V}} \endgroup ^{\pazocal{M}\;\otimes n}_{A\to BE}\,\middle\|\, \tilde{\pazocal{N}}\right) =\mathbb{D}^\infty\big( \begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\pazocal{M}} \endgroup _{A\to BE}\,\big\|\,\mathcal{C}_{A\to BE}^{\pazocal{N}}\big). \end{align}\] In particular, this proof implies that the sequence \(\big( \begingroup \def\mathaccent##1##2{ \kern 0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern 0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax 111{\pazocal{N}} \endgroup _{A^n\to B^nE^n}\big)_n\in \mathcal{C}^{\pazocal{N}}_{A\to BE}\) given by ?? achieves the right-hand side of ?? . ◻

Proof. The proof generalises the polynomial method developed in [@beals2001quantum; @huang2021information]. The key idea is to exploit the linearity of quantum mechanics, which implies that the measurement probability of any quantum algorithm that makes \(n\) queries to a channel must be a polynomial of the channel parameters with degree determined by \(n\). But the degree cannot be too small in order to distinguish many channels. This gives a lower bound on the query complexity \(n\).

Suppose that there is a quantum algorithm that makes \(n\) queries to the channel \(\Phi_x\) and produces an outcome \(\hat{X}\in [M]\) that has correct probability \(\Pr[\hat{X}=x|\Phi_x]>1/2\) for any \(x\in [M]\). We consider the confusion matrix \(P \in \mathbb{R}^{M\times M}\) of this quantum algorithm. It is an \(M\times M\) matrix with matrix elements \(P_{\hat{x}x}, \hat{x}, x\in [M]\) representing the probability that the quantum algorithm predicts \(\hat{x}\) when the quantum channel that it truly queries is \(\Phi_x\). We have \(\sum_{\hat{x}=1}^M P_{\hat{x}x}=1\) for all \(x\in [M]\). The guarantee of correct probability implies that \(P_{xx}>1/2\) for any \(x\in [M]\). Therefore, \[\sum_{\hat{x}\neq x}P_{\hat{x}x}=1-P_{xx}< \frac{1}{2}< P_{xx}, \quad \forall x\in [M],\] meaning that the confusion matrix \(P\) is strictly diagonally dominant. This implies that \(P\) has full rank: \[\mathrm{rank}(P)=M.\] On the other hand, all these matrix elements are measurement probabilities of a quantum algorithm querying the channel \(\Phi_x\). Let \[\Phi_x(\rho)=\sum_{i=1}^{r} K^x_i(\rho)K^{x\dagger}_i\] be the Kraus operator representation of the quantum channel \(\Phi_x\). We use a complex vector \(z^x\in \mathbb{C}^{rd_Ad_B}\) to collect all the parameters in the Kraus operators: \[z^x_{i\cdot d_Ad_B+j\cdot d_A+k} = (K^x_i)_{jk}.\] Then the matrix elements of the output of the quantum channel \(\Phi_x\) can be regarded as a polynomial of \(z^x\) and its complex conjugate \(\bar{z}^x\): \[(\Phi_x(\rho))_{ij} = \sum_{a,b=1}^{rd_Ad_B} w_{ij,ab}z^x_a \bar{z}^x_b, \quad \forall i,j \in [d_B],\] where the coefficients \(w_{ij,ab}\in \mathbb{C}\) are determined by the input state \(\rho\).

We generalise this polynomial representation to the measurement probability of an arbitrary quantum algorithm (possibly with indefinite causal order) querying the channel \(\Phi_x\). The most general form of the measurement probability \(P_{\hat{x}x}\) is represented as the contraction of a general algorithm tensor \((T_{\hat{x}})_{i_1i'_1o_1o'_1\ldots i_ni'_no_no'_n}, i_1, \ldots, i_n, i'_1, \ldots, i'_n\in [d_A], o_1, \ldots, o_n, o'_1, \ldots, o'_n\in [d_B]\) with \(n\) copies of the channel tensor \((\Phi_x)_{ii'oo'}, i,i'\in [d_A], o,o'\in [d_B]\): \[P_{\hat{x}x} = \sum_{\substack{i_1, \ldots, i_n, i'_1, \ldots, i'_n\in [d_A]\\ o_1, \ldots, o_n, o'_1, \ldots, o'_n\in [d_B]}} (T_{\hat{x}})_{i_1i'_1o_1o'_1\ldots i_ni'_no_no'_n} (\Phi_x)_{i_1i'_1o_1o'_1}\cdots (\Phi_x)_{i_ni'_no_no'_n}.\] Here, for each \(j\in [n]\), the indices \(i_ji'_jo_jo'_j\) of the tensor \(T_{\hat{x}}\) are contracted with the \(n\)-th copy of the channel \(\Phi_x\). Note that the tensor \(T_{\hat{x}}\) must satisfy certain conditions to ensure that the outcome is a proper probability (e.g.\(P_{\hat{x}x}\in [0, 1], \sum_{\hat{x}}P_{\hat{x}x}=1\)), but for our purposes we do not use those conditions. Plugging in the \(z^x, \bar{z}^x\) parameterisation of the channel \(\Phi_x\), we have \[P_{\hat{x}x} = \sum_{\substack{a_1, \ldots, a_n\in [rd_A d_B]\\ b_1, \ldots, b_n\in [rd_A d_B]}} w^{\hat{x}}_{a_1\ldots a_n b_1\ldots b_n} z^x_{a_1}\cdots z^x_{a_n} \bar{z}^x_{b_1}\cdots \bar{z}^x_{b_n},\] where the coefficients \(w^{\hat{x}}_{a_1\ldots a_n b_1\ldots b_n}\) are determined by the algorithm tensor \(T_{\hat{x}}\) and the terms \(z^x_{a_j} \bar{z}^x_{b_j}\) that are contributed by the \(j\)-th copy of the channel tensor \(\Phi_x\).

We note that this way of organising coefficients has redundancy, because the \(n\) copies of \(z\)’s (and \(\bar{z}\)’s) are symmetric to each other. For example, the terms \(z_1z_2\) and \(z_2z_1\) are the same and can be grouped together to share one coefficient. In other words, the order in the indices \((a_1, \ldots, a_n)\) and \((b_1, \ldots, b_n)\) does not matter. We use \(\mathrm{Sym}(rd_Ad_B, n)\) to denote the set of such unordered indices and use \(Z^x_\alpha, \bar{Z}^x_\beta \in \mathbb{C}, \alpha, \beta\in \mathrm{Sym}(rd_Ad_B, n)\) to denote the terms \(z^x_{a_1}\cdots z^x_{a_n}, \bar{z}^x_{b_1}\cdots \bar{z}^x_{b_n}\) corresponding to the unordered indices \(\alpha, \beta\). Then we have the following polynomial representation of the probability \[P_{\hat{x}x} = \sum_{\alpha, \beta\in \mathrm{Sym}(rd_Ad_B, n)} W^{\hat{x}}_{\alpha\beta} Z^x_{\alpha} \bar{Z}^x_\beta,\] where the coefficients \(W^{\hat{x}}_{\alpha\beta}\) are the sum of all \(w^{\hat{x}}_{a_1\ldots a_n b_1\ldots b_n}\) with \((a_1, \ldots, a_n), (b_1, \ldots, b_n)\) corresponding to \(\alpha, \beta\). To count the size of \(\mathrm{Sym}(rd_Ad_B, n)\), we note that each \(\alpha \in \mathrm{Sym}(rd_Ad_B, n)\) can be labeled by the number of times \(n_a\) each symbol \(a\in [rd_Ad_B]\) appears in the unordered indices \(\alpha\). They satisfy \[\sum_{a=1}^{rd_Ad_B}n_a=n, \quad n_a\geq 0, \quad \forall a\in [rd_Ad_B].\] Standard combinatorial counting yields \[|\mathrm{Sym}(rd_Ad_B, n)| = \binom{n+rd_Ad_B-1}{n}.\] The polynomial representation gives us a matrix decomposition of the confusion matrix \(P\): \[P = \mathcal{W}\mathcal{Z},\] where the matrices \[\mathcal{W}\in \mathbb{C}^{M\times |\mathrm{Sym}(rd_Ad_B, n)|^2}, \quad \mathcal{Z}\in \mathbb{C}^{|\mathrm{Sym}(rd_Ad_B, n)|^2\times M},\] are given by the coefficients \(W^{\hat{x}}_{\alpha\beta}\) and monomials \(Z^x_{\alpha}\bar{Z}^x_{\beta}\): for each \(x, \hat{x}\in [M]\), the \(\hat{x}\)-th row of \(\mathcal{W}\) is the row vector \((W^{\hat{x}}_{\alpha\beta})_{\alpha, \beta \in \mathrm{Sym}(rd_Ad_B, n)}\) and the \(x\)-th column of \(\mathcal{Z}\) is the column vector \(((Z^x_{\alpha}\bar{Z}^x_{\beta})_{\alpha, \beta \in \mathrm{Sym}(rd_Ad_B, n)})^T\). In other words, \[P_{\hat{x}x} = \sum_{\gamma=1}^{|\mathrm{Sym}(rd_Ad_B, n)|^2}\mathcal{W}_{\hat{x},\gamma}\mathcal{Z}_{\gamma, x}.\] Therefore, the rank of the confusion matrix satisfies \[M=\mathrm{rank}(P)\leq |\mathrm{Sym}(rd_Ad_B, n)|^2 = \binom{n+rd_Ad_B-1}{n}^2.\] Taking the logarithm, we arrive at the desired result \[\log M \leq 2 \log \binom{n+rd_Ad_B-1}{n}.\]

When we are allowed to query the inverse and controlled versions of \(\Phi_x\) if they exist, the contracted channel tensor is the same as that of \(\Phi_x\) itself with \(z^x\) and \(\bar{z}^x\) swapped or padded with fixed numbers that represent the control pattern. This does not change the polynomial representation and the counting. Therefore, we still have \[\log M \leq 2 \log \binom{n+rd_Ad_B-1}{n}.\] This completes the proof of Theorem 12. ◻

Proof. The proof of Lemma 4 in [@barthel2018fundamental] (see also Lemma 10 in [@zhao2024learning]), combined with Lemma 7, shows that \(\mathcal{M}(\mathcal{C}_{d_A, d_B, r}, \|\cdot \|_\diamond, \varepsilon)\) is asymptotically bounded from both sides by the packing number of \(\mathcal{V}_{d_A\to rd_B}\) in \(\|\cdot \|\) divided by the packing number of \(\mathcal{V}_{r\to r}\) in \(\|\cdot \|\) up to a quadratic difference in \(\varepsilon\). When we take the logarithm, the division becomes subtraction. Using Lemma 6, we have \[\begin{align} \log\mathcal{M}(\mathcal{C}_{d_A, d_B, r}, \|\cdot \|_\diamond, \varepsilon) &= \Theta((2rd_Ad_B-d_A^2)\log(1/\varepsilon)) - \Theta(r^2\log(1/\varepsilon))\\ &=\Theta((2rd_Ad_B-d_A^2-r^2)\log(1/\varepsilon)) \end{align}\] Further note that \(2rd_Ad_B-d_A^2 - r^2\leq 2rd_Ad_B\) and \[\begin{align} 2rd_Ad_B-d_A^2 - r^2 &= rd_Ad_B \left( 2 - \frac{1}{d_B}\left(\frac{d_A}{r} + \frac{r}{d_A}\right) \right) \\ &\geq rd_Ad_B \left( 2 - \frac{1}{d_B}\left(d_B + \frac{1}{d_B}\right) \right) \\ &=rd_Ad_B\left( 1-\frac{1}{d_B^2} \right) \\ &\geq \frac{3}{4}rd_Ad_B, \end{align}\] when \(d_B\geq 2\). Here, we used the fact that \(r\leq d_Ad_B\) and \(rd_B\geq d_A\), and that the function \(f(x)=x+1/x\) is convex and hence its maximum on \(d_A/r\in [1/d_B, d_B]\) must be attained at the endpoints. This means that \(2rd_Ad_B-d_A^2 - r^2 = \Theta(rd_Ad_B)\) and therefore \[\log\mathcal{M}(\mathcal{C}_{d_A, d_B, r}, \|\cdot \|_\diamond, \varepsilon) = \Theta\left(rd_A d_B \log(1/\varepsilon)\right).\] ◻

Proof. When \(d=1\), the lemma clearly holds. When \(d\geq 2\), we begin by relating the log binomial coefficient to the binary entropy function \(H_2(p) \relax-p\log p-(1-p)\log(1-p)\). Note that \[\begin{align} 1 &= \left(\frac{d-1}{n+d-1}+1-\frac{d-1}{n+d-1}\right)^{n+d-1}\\ &=\sum_{i=0}^{n+d-1}\binom{n+d-1}{i}\left(\frac{d-1}{n+d-1}\right)^{i}\left(1-\frac{d-1}{n+d-1}\right)^{(n+d-1)-i}\\ &\geq \binom{n+d-1}{d-1} \left(\frac{d-1}{n+d-1}\right)^{d-1}\left(1-\frac{d-1}{n+d-1}\right)^{(n+d-1)-(d-1)}\\ &=\binom{n+d-1}{d-1} 2^{-(n+d-1)H_2\left(\frac{d-1}{n+d-1}\right)}. \end{align}\] Thus, \[c(d-1)\leq \log\binom{n+d-1}{n} = \log\binom{n+d-1}{d-1} \leq (n+d-1)H_2\left(\frac{d-1}{n+d-1}\right).\] Let \(x=\frac{n}{d-1}>0\). We have \[g(x) = (1+x)H_2\left(\frac{1}{1+x}\right)\geq c.\] Note that the bosonic entropy function \(g(x)\) is monotonically increasing, since it has derivative \(\log(1+1/x)>0\) for all \(x>0\). Therefore, we have \(x\geq g^{-1}(c)\) and \[n\geq g^{-1}(c)(d-1).\] This concludes the proof. ◻

Proof of the lower bound in Theorem 11. Consider any quantum algorithm that learns \(\Phi\) to \(\varepsilon=\Theta(1)\) error with success probability at least \(2/3\) using \(n\) queries. It is allowed to query \(\Phi\) in an arbitrary way (e.g.query the inverse and controlled versions of \(\Phi\) if they exist, or with indefinite causal order), as in Theorem 12. We take a maximal \(3\varepsilon\)-packing net \(\mathcal{M}=\{\Phi_x\}_{x=1}^{|\mathcal{M}|}\) in diamond norm over the set of channels with input dimension \(d_A\), output dimension \(d_B\), and rank \(r\). Lemma 8 asserts that the cardinality of this net satisfies \[\log|\mathcal{M}|= \Theta(rd_Ad_B\log(1/\varepsilon)).\] Now we construct a channel distinguishing algorithm that identifies elements of the net \(\mathcal{M}\). Specifically, we run the channel learning algorithm that makes \(n\) queries to any \(\Phi_x\in \mathcal{M}\) and outputs a classical description of a channel \(\hat{\Phi}\). The learning guarantee implies that with probability at least \(2/3\), we have \(\|\hat{\Phi}-\Phi_x\|_\diamond\leq \varepsilon\). Triangle inequality then asserts that for any \(x'\in [|\mathcal{M}|], x'\neq x\), we have \[\|\hat{\Phi}-\Phi_{x'}\|_\diamond\geq \|\Phi_{x}-\Phi_{x'}\|_\diamond-\|\hat{\Phi}-\Phi_{x}\|_\diamond \geq 3\varepsilon-\varepsilon=2\varepsilon> \varepsilon= \|\hat{\Phi}-\Phi_{x}\|_\diamond.\] This means that the channel in the net that is closest to the estimate \(\hat{\Phi}\) is unique and exactly \(\Phi_x\) itself. We can find this closest channel by brute force enumerating all elements of the net. This gives a channel distinguishing algorithm with success probability at least \(2/3\). The channel distinguishing bound Theorem 12 immediately implies that \[\Theta(rd_Ad_B\log(1/\varepsilon))=\frac{1}{2}\log|\mathcal{M}|\leq \log\binom{n+rd_Ad_B-1}{n}.\] Using Lemma 9, we arrive at \[n\geq \Omega(rd_Ad_B),\] as desired. This completes the proof of Theorem 11. ◻