Unions, intersections and a one-shot quantum joint typicality lemma

A fundamental tool to prove inner bounds in classical network information theory is the so-called ‘conditional joint typicality lemma’. In addition to the lemma, one often uses unions and intersections of typical sets in the inner bound arguments without so much as giving them a second thought. These arguments do not work in the quantum setting. This bottleneck shows up in the fact that so-called ‘simultaneous decoders’, as opposed to ‘successive cancellation decoders’, are known for very few channels in quantum network information theory. Another manifestation of this bottleneck is the lack of so-called ‘simultaneous smoothing’ theorems for quantum states. In this paper, we overcome the bottleneck by proving for the first time a one-shot quantum joint typicality lemma with robust union and intersection properties. To do so we develop two novel tools in quantum information theory, which may be of independent interest. The first tool is a simple geometric idea called tilting, which increases the angles between a family of subspaces in orthogonal directions. The second tool, called smoothing and augmentation, is a way of perturbing a multipartite quantum state such that the partial trace over any subset of registers does not increase the operator norm much. Our joint typicality lemma allows us to construct simultaneous quantum decoders for many multiterminal quantum channels. It provides a powerful tool to extend many results in classical network information theory to the one-shot quantum setting.

I profusely thank Mark Wilde for pointing out the need for a simultaneous decoder for the quantum MAC many years back while I was visiting McGill, and underscoring its importance for quantum network information theory. He also provided pointers to several important references. Patrick Hayden, David Ding and Hrant Gharibyan took great pains in reading a preliminary draft of this paper and provided useful feedback. I thank Rahul Jain for encouraging me to write up this result in the face of a long delay. I thank an anonymous referee for suggesting to give a full self contained solution for the pathological example of failure of ‘union by span’ in the introduction, and more detailed intuition behind smoothing and augmentation. I am grateful to three anonymous referees for suggesting giving a self-contained proof of the ‘baby case’ of ‘intersection’ of two-projector/two- sender cq-MAC. I thank Naqueeb Warsi for pointing me to his paper on the entanglement-assisted compound quantum channel and suggesting a possible application of tilted span of projectors to that problem. Finally, I thank an anonymous referee who pointed out a possible application of our tilted span to the ‘quantum OR bound’ of Harrow, Lin and Montanaro and asked whether our notion of intersection of projectors can lead to the proof of a chain rule for one-shot mutual information quantities.

Authors and Affiliations

1. School of Technology and Computer Science, Tata Institute of Fundamental Research, Mumbai, 400005, India

   Pranab Sen

Corresponding author

Correspondence to Pranab Sen.

Appendix I. Proof of Proposition 4

We prove Proposition 4 in this section. We first show how to construct the objects whose existence is promised by the proposition. We then proceed to prove its claims. All the while, we use the notation of the proposition: \({\mathbf{x}} \), \({\mathbf{l}} \) will denote, respectively, computational basis vectors of \({\mathcal {X}}^{\otimes [c]}\), , \(0 \le \delta \le 1\), and \(0 \le \epsilon _{{\mathbf{x}} , (S_1, \ldots , S_l)} \le 1\).

In Appendix I.1, we show how to construct the perturbed state \((\rho ')_{{\mathbf{x}} ,{\mathbf{l}} ,\delta }^{A''_{[k]}}\) by tilting the original state \(\rho _{\mathbf{x} }^{A_{[k]}}\) appropriately. In Appendix I.2, we construct the ‘intersection’ projector \((\Pi ')_{{\mathbf{x}} ,{\mathbf{l}} ,\delta }^{A''_{[k]}}\) using the technique of matrix-tilted span. In Appendix I.3 we define two complex numbers and a tilting map, and in Appendix I.4 we define two operators required for the statement of Proposition 4 using the combinatorial and algebraic framework of matrix tilting. In Appendix I.5, we prove Claim 1 of Proposition 4 using simple operator inequalities. In Appendix I.6, we prove Claim 2 using the geometry behind the smoothing and augmentation technique described earlier. In Appendix I.7 we prove Claim 3, and in Appendix I.8 we prove Claim 4 using combinatorial properties of the tilting operator. In Appendix I.9, we observe that Claim 5 has already been proven in Appendix I.4 earlier. In Appendix I.10, we prove Claim 6 by invoking the results of Appendix I.2 regarding the geometry of the ‘intersection’ projector.

1.1 Appendix I.1 Constructing \((\rho ')_{{\mathbf{x}} ,{\mathbf{l}} ,\delta }^{A''_{[k]}}\)

Let , \(S \cap [k] \ne \{\}\). Define . Let \({\mathbf{l}} _S\) be a computational basis vector of \({\mathcal {L}}^{\otimes S}\). We define an isometric embedding \({\mathcal {T}}_{S, {\mathbf{l}} _S}\) of \(({\mathcal {H}}\otimes {\mathbb {C}}^2)^{\otimes (S \cap [k])}\) into \( (({\mathcal {H}}\otimes {\mathbb {C}}^2) \otimes {\mathcal {L}}^{\otimes |S|})^{\otimes (S \cap [k])} \) as follows:

where \(s \in S \cap [k]\), \({\mathbf{h}} _{S \cap [k]}\) is a computational basis vector of \(({\mathcal {H}}\otimes {\mathbb {C}}^2)^{\otimes (S \cap [k])}\), and \({\mathbf{h}} _s\), \(({\mathcal {T}}_{S, {\mathbf{l}} _S}({\mathbf{h}} _{S \cap [k]}))_s\) are the entries in the sth coordinate of \({\mathbf{h}} _{S \cap [k]}\), \({\mathcal {T}}_{S, {\mathbf{l}} _S}({\mathbf{h}} _{S \cap [k]})\). Observe that \({\mathcal {T}}_{S, {\mathbf{l}} _S}\) maps computational basis vectors of \(({\mathcal {H}}\otimes {\mathbb {C}}^2)^{\otimes (S \cap [k])}\) to computational basis vectors of \( (({\mathcal {H}}\otimes {\mathbb {C}}^2) \otimes {\mathcal {L}}^{\otimes |S|})^{\otimes (S \cap [k])}. \) Thus \({\mathcal {T}}_{S, {\mathbf{l}} _S}\) is an isometric embedding of \(({\mathcal {H}}\otimes {\mathbb {C}}^2)^{\otimes (S \cap [k])}\) into \( (({\mathcal {H}}\otimes {\mathbb {C}}^2) \otimes {\mathcal {L}}^{\otimes |S|})^{\otimes (S \cap [k])} \), which further embeds into \(A''_{S \cap [k]}\) in the natural fashion. Let \({\mathbb {1}}^{({\mathcal {H}}\otimes {\mathbb {C}}^2)^{\otimes (S \cap [k])}}\) denote the identity embedding of \(({\mathcal {H}}\otimes {\mathbb {C}}^2)^{\otimes (S \cap [k])}\) into \(A''_{(S \cap [k])}\). Observe that the range spaces of \( {\mathcal {T}}_{S, {\mathbf{l}} _S} \otimes {\mathbb {1}}^{({\mathcal {H}}\otimes {\mathbb {C}}^2)^{ \otimes (\bar{S} \cap [k]) }}, \) as S ranges over subsets of intersecting [k] non-trivially, embed orthogonally into \(A''_{[k]}\) under the natural embedding. Also, for a fixed , \(S \cap [k] \ne \{\}\) the range spaces of \({\mathcal {T}}_{S, {\mathbf{l}} _S}\), as \({\mathbf{l}} _S\) ranges over computational basis vectors of \({\mathcal {L}}^{\otimes S}\), embed orthogonally into \(A''_{S \cap [k]}\) under the natural embedding.

We now define an isometric embedding \({\mathcal {T}}_{S, {\mathbf{l}} _S, \delta }\) of \(({\mathcal {H}}\otimes {\mathbb {C}}^2)^{\otimes (S \cap [k])}\) into \(A''_{S \cap [k]}\) as follows:

where the normalisation factor \(N(S, \delta )\) is put in to make the embedding preserve length of vectors. Observe that \(N(S, \delta )\) is independent of the vector in \(({\mathcal {H}}\otimes {\mathbb {C}}^2)^{\otimes (S \cap [k])}\) on which \({\mathcal {T}}_{S, {\mathbf{l}} _S, \delta }\) acts since the terms in this summation have orthogonal range spaces. It can be estimated as follows:

It is clear that \(N(S,\delta ) \ge 1\) and \(N(T_1, \delta ) \cdots N(T_m, \delta ) \le N(S, \delta )\) if \((T_1, \ldots , T_m) \vdash \vdash S\).

The map \({\mathcal {T}}_{S, {\mathbf{l}} _S, \delta }\) extends to subspaces and density matrices in \(({\mathcal {H}}\otimes {\mathbb {C}}^2)^{\otimes (S \cap [k])}\) in the natural way. We now define the quantum state

(A3)

in \(A''_1 \cdots A''_k\), where \(\rho _{\mathbf{x}} ^{A_{[k]}} \otimes (|{0}\rangle \langle {0}|^{{\mathbb {C}}^2})^{\otimes k}\) can be thought of as a density matrix in \(({\mathcal {H}}\otimes {\mathbb {C}}^2)^{\otimes [k]}\) in the natural fashion.

1.2 Appendix I.2 Constructing \((\Pi ')_{{\mathbf{x}} ,{\mathbf{l}} ,\delta }^{A''_{[k]}}\)

For each \({\mathbf{x}} \), , \(l > 0\), let \(\Pi ''_{{\mathbf{x}} , (S_1, \ldots , S_l)}\) be the POVM element in \(A_1 \cdots A_k\) with the property that

By Fact 2, there exists an orthogonal projection \(\Pi _{{\mathbf{x}} , (S_1, \ldots , S_l)}\) in \( (A_1 \cdots A_k) \otimes ({\mathbb {C}}^2)^{\otimes k} \cong ({\mathcal {H}}\otimes {\mathbb {C}}^2)^{\otimes [k]} \) such that

Let \(Y_{{\mathbf{x}} , (S_1, \ldots , S_l)}\) denote the orthogonal complement of the support of \(\Pi _{{\mathbf{x}} , (S_1, \ldots , S_l)}\) in \(({\mathcal {H}}\otimes {\mathbb {C}}^2)^{\otimes [k]}\). Identify \(({\mathcal {H}}\otimes {\mathbb {C}}^2)^{\otimes [k]}\) with the Hilbert space \({\mathcal {H}}\) of Proposition 3. Arrange all the non-empty pseudosubpartitions , \(m > 0\) into a linear order extending the refinement partial order \(\preceq \). Define the tilting matrix A, whose rows and columns are indexed by non-empty pseudosubpartitions of that intersect [k] non-trivially, as follows:

Observe that A is upper triangular, diagonal dominated, and substochastic. The diagonal-dominated property of A follows from the fact that \( N(T_1, \delta ) \cdots N(T_m, \delta ) \le N(W_1, \delta ) \cdots N(W_n, \delta ) \) if \((T_1, \ldots , T_m) \preceq (W_1, \ldots , W_n)\). The reason A is substochastic in general, and not stochastic, is because the empty pseudosubpartition is not included amongst the rows and columns of A. More precisely

For , \(l > 0\) define an isometric embedding \({\mathcal {T}}_{(S_1, \ldots , S_l), {\mathbf{l}} , \delta }\) of \(({\mathcal {H}}\otimes {\mathbb {C}}^2)^{\otimes [k]}\) into \(A''_{[k]}\) as follows:

Observe that the A-tilt of \(Y_{{\mathbf{x}} , (S_1, \ldots , S_l)}\) along the \((S_1, \ldots , S_l)\)th direction is nothing but the action of the isometric embedding \({\mathcal {T}}_{(S_1, \ldots , S_l), {\mathbf{l}} , \delta }\):

Define the A-tilted span

(A8)

View \(Y'_{{\mathbf{x}} , {\mathbf{l}} , \delta }\) as a subspace of \(A''_1 \ldots A''_k\). Let \((\Pi ')^{A''_{[k]}}_{Y'_{{\mathbf{x}} , {\mathbf{l}} , \delta }}\) denote the orthogonal projection in \(A''_1 \ldots A''_k\) onto \(Y'_{{\mathbf{x}} , {\mathbf{l}} , \delta }\).

Let \((\Pi ')^{A''_{[k]}}_{({\mathcal {H}}\otimes {\mathbb {C}}^2)^{\otimes [k]}}\) denote the orthogonal projection in \(A''_1 \ldots A''_k\) onto \(({\mathcal {H}}\otimes {\mathbb {C}}^2)^{\otimes [k]}\). We finally define the POVM element \((\Pi ')^{A''_{[k]}}_{{\mathbf{x}} ,{\mathbf{l}} ,\delta }\) in \(A''_1 \ldots A''_k\) to be

1.3 Appendix I.3 Defining \(\alpha _{(S_1, \ldots , S_l), \delta }\), \(\beta _{(S_1, \ldots , S_l), \delta }\), \({\mathcal {T}}_{(S_1, \ldots , S_l), {\mathbf{l}} , \delta }\)

Recall that the isometric embedding \({\mathcal {T}}_{(S_1, \ldots , S_l), {\mathbf{l}} , \delta }\) of \(({\mathcal {H}}\otimes {\mathbb {C}}^2)^{\otimes [k]}\) into \(A''_{[k]}\) has already been defined in Equation (A6). Also define

Since

for any , \(\{\} \ne S \cap [k] \subset [k]\),

It follows that \(0 \le \alpha _{(S_1, \ldots , S_l), \delta }, \beta _{(S_1, \ldots , S_l), \delta } \le 1\).

1.4 Appendix I.4 Constructing \(M_{(S_1, \ldots , S_l), {\mathbf{l}} , \delta }^{A''_{[k]}}\), \(N_{(S_1, \ldots , S_l), {\mathbf{l}} , \delta }^{A''_{[k]}}\)

Let , \(\{\} \ne S \cap [k] \subset [k]\). Define . For a subset , \(T \cap [k] \ne \{\}\) we say that T crosses S if \(T \cap S \cap [k] \ne \{\}\) and \(T \cap \bar{S} \cap [k] \ne \{\}\). We define a pseudosubpartition to cross S if there exists an \(i \in [l]\) such that \(T_i\) crosses S. We use the notation \((T_1, \ldots , T_l) \models _{\times } S\) to denote that pseudosubpartition \((T_1, \ldots , T_l)\) crosses S. We define the S-signature of a pseudosubpartition \((T_1, \ldots , T_l)\) to be the pseudosubpartition \((T_1, \ldots , T_{l'})\) where \(l' \le l\) and \(T_1, \ldots , T_{l'}\) are the subsets that actually cross S. We shall denote pseudosubpartitions , where for all \(i \in [l]\ T_i\) crosses S, by the notation \((T_1, \ldots , T_{l}) \models _{\times \times } S\). If pseudosubpartition \((T_1, \ldots , T_l)\) has S-signature \((T_1, \ldots , T_{l'})\), we shall denote it by \((T_1, \ldots , T_l) \rightthreetimes _S (T_1, \ldots , T_{l'})\). Observe that \((T_1, \ldots , T_{l'}) \models _{\times \times } S\).

From Equation (A1), we observe that

(A10)

We will denote the second term of the summation here by \({\mathcal {T}}_{\models _{\times } S, {\mathbf{l}} , \delta }\). Observe that \({\mathcal {T}}_{\models _{\times } S, {\mathbf{l}} , \delta }\) is a scaled isometric embedding of \(({\mathcal {H}}\otimes {\mathbb {C}}^2)^{\otimes [k]}\) into \(A''_{[k]}\).

Let \(|{h}\rangle \) be a unit length vector in \(({\mathcal {H}}\otimes {\mathbb {C}}^2)^{\otimes [k]}\). Let the Schmidt decomposition of \(|{h}\rangle \) with respect to \((S \cap [k], \bar{S} \cap [k])\) be

where \(\sum _i p_i = 1\). Let the Schmidt decomposition of \({\mathcal {T}}_{\models _{\times } S, {\mathbf{l}} , \delta }(|{h}\rangle )\) with respect to \((S \cap [k], \bar{S} \cap [k])\) be

where \( \sum _{ (T_1, \ldots , T_{l'}) \models _{\times \times } S } \sum _{j_{(T_1, \ldots , T_{l'})}} q_{j_{(T_1, \ldots , T_{l'})}} \) may be less than 1, reflecting the fact that the length of \({\mathcal {T}}_{\models _{\times } S, {\mathbf{l}} , \delta }(|{h}\rangle )\) may be less than 1. For a pseudosubpartition \((T_1, \ldots , T_{l'}) \models _{\times \times } S\), the expression \( \sum _{j_{(T_1, \ldots , T_{l'})}} \sqrt{q_{j_{(T_1, \ldots , T_{l'})}}} |{\gamma _{j_{(T_1, \ldots , T_{l'})}}}\rangle ^{A''_{S \cap [k]}} \otimes |{\delta _{j_{(T_1, \ldots , T_{l'})}}}\rangle ^{A''_{\bar{S} \cap [k]}} \) is the Schmidt decomposition of

with respect to \((S \cap [k], \bar{S} \cap [k])\). We observe that the span of the vectors \( \{|{\gamma _{j_{(T_1, \ldots , T_{l'})}}}\rangle ^{A''_{S \cap [k]}}\}_{ j_{(T_1, \ldots , T_{l'})} } \) is orthogonal to the span of the vectors \( \{|{\gamma _{j_{(S_1, \ldots , S_{m'})}}}\rangle ^{A''_{S \cap [k]}}\}_{ j_{(S_1, \ldots , S_{m'})} } \) for different pseudosubpartitions \( (T_1, \ldots , T_{l'}), (S_1, \ldots , S_{m'}) \models _{\times \times } S. \) Similarly, the span of \( \{|{\delta _{j_{(T_1, \ldots , T_{l'})}}}\rangle ^{A''_{\bar{S} \cap [k]}}\}_{ j_{(T_1, \ldots , T_{l'})} } \) is orthogonal to the span of \( \{|{\delta _{j_{(S_1, \ldots , S_{m'})}}}\rangle ^{A''_{\bar{S} \cap [k]}}\}_{ j_{(S_1, \ldots , S_{m'})} }. \) Thus, Equation (A11) is indeed a valid Schmidt decomposition for \({\mathcal {T}}_{\models _{\times } S, {\mathbf{l}} , \delta }(|{h}\rangle )\).

Now

Observe that this is a Schmidt decomposition of , that is, for all i, \((T_1, \ldots , T_{l'}) \models _{\times \times } S\), \(j_{(T_1, \ldots , T_{l'})}\)

and \( {\mathcal {T}}_{\bar{S} \cup [c], {\mathbf{l}} _{\bar{S} \cup [c]}, \delta }(|{\beta _i}\rangle ) \perp |{\delta _{j_{(T_1, \ldots , T_{l'})}}}\rangle \).

Thus

Express \(\rho _{\mathbf{x}} ^{A_{[k]}} \otimes (|{0}\rangle \langle {0}|^{{\mathbb {C}}^2})^{\otimes k}\) in terms of its eigenbasis

where \(\sum _i s_i = 1\). Let \(|{\gamma _{j_{(T_1, \ldots , T_{l'})}}(i)}\rangle \), \(q_{j_{(T_1, \ldots , T_{l'})}}(i)\) be the appropriate vectors and coefficients for \(|{(h(i))}\rangle \) as defined in Equation (A11). Then, using Equation (A3), we get

where \((M'')_{S, {\mathbf{x}} , {\mathbf{l}} , \delta }^{A''_{S \cap [k]}}\) is defined to be the second term in the summation in the first equality here. Note that \((M'')_{S, {\mathbf{x}} , {\mathbf{l}} , \delta }^{A''_{S \cap [k]}}\) is a positive semidefinite matrix with support orthogonal to the support of the first matrix in the summation here.

We say that a pseudosubpartition \((T_1, \ldots , T_l) \vdash \vdash S \cup [c]\) leaks out of S if there exists an \(i \in [l]\) such that \(T_i \cap \bar{S} \cap [c] \ne \{\}\). We use the notation \((T_1, \ldots , T_l) \models _{\rightsquigarrow } S\) to denote that pseudosubpartition \((T_1, \ldots , T_l)\) leaks out of S. Observe that

We use \({\mathcal {T}}_{\models _{\rightsquigarrow } S, {\mathbf{l}} _{S \cup [c]}, \delta }\) to denote the second term in the sum here. The map \({\mathcal {T}}_{\models _{\rightsquigarrow } S, {\mathbf{l}} _{S \cup [c]}, \delta }\) is a scaled isometric embedding of \(({\mathcal {H}}\otimes {\mathbb {C}}^2)^{\otimes (S \cap [k])}\) into \(A''_{S \cap [k]}\). Let \(|{h}\rangle \in ({\mathcal {H}}\otimes {\mathbb {C}}^2)^{\otimes (S \cap [k])}\) be a unit length vector. Define the Hermitian matrix

Then

Looking at Equation (A12), we define the Hermitian matrix

Note that \((N''_{S, {\mathbf{x}} , {\mathbf{l}} , \delta })^{A''_{S \cap [k]}} = 0\) if \(c = 0\). Thus

and

Observe that \((M''_{S, {\mathbf{x}} , {\mathbf{l}} , \delta })^{A''_{S \cap [k]}}\) has support orthogonal to the sum of the first two terms in this equation and

Also note that the sum of the first two terms is a positive semidefinite matrix.

Now define

(A15)

Obviously, \((M')_{S, {\mathbf{x}} _{S \cap [c]}, {\mathbf{l}} _S, \delta }^{A''_{S \cap [k]}}\) is a positive semidefinite matrix and \((N')_{S, {\mathbf{x}} _{S \cap [c]}, {\mathbf{l}} _S, \delta }^{A''_{S \cap [k]}}\) is a Hermitian matrix. Moreover, \((N')_{S, {\mathbf{x}} _{S \cap [c]}, {\mathbf{l}} _S, \delta }^{A''_{S \cap [k]}} = 0\) if \(c = 0\). Recalling the definition of \((\rho ')_{{\mathbf{x}} _{S \cap [c]}, {\mathbf{l}} _{S}, \delta }^{A''_{S \cap [k]}}\) in Claim 5 of Proposition 4, we see that

Observe that \((M')_{S, {\mathbf{x}} _{S \cap [c]}, {\mathbf{l}} _S, \delta }^{A''_{S \cap [k]}}\) has support orthogonal to that of the sum of the first two terms in this equation and . Also note that the sum of the first two terms is a positive semidefinite matrix.

Now recalling the definition of \((\rho ')_{{\mathbf{x}} , {\mathbf{l}} ,(S_1, \ldots , S_l),\delta }^{A''_{S \cap [k]}}\) from Claim 5 of Proposition 4, we see that

(A16)

Here, the notation “Other Terms II” denotes a \((2^l - 1)\)-fold sum of tensor products of \((l+1)\) matrices where one multiplicand is \(\sigma _{\mathbf{x}} ^{A_{[k] {\setminus } (S_1 \cup \cdots \cup S_l)}} \otimes (|{0}\rangle \langle {0}|)^{({\mathbb {C}}^2)^{\otimes |[k] {\setminus } (S_1 \cup \cdots \cup S_l)|}}, \) at least one multiplicand is of the form \( (M')^{A''_{S_i \cap [k]}}_{ S_i, {\mathbf{x}} _{S_i \cap [c]}, {\mathbf{l}} _{S_i}, \delta }, \) and the remaining multiplicands are of the form

having \(\ell _1\)-norm at most 1. We use \((M')^{A''_{[k]}}_{(S_1, \ldots , S_l),{\mathbf{x}} ,{\mathbf{l}} ,\delta }\) to denote the “Other Terms II”. It is clear that \( (M')^{A''_{[k]}}_{(S_1, \ldots , S_l),{\mathbf{x}} ,{\mathbf{l}} ,\delta } \) is a positive semidefinite matrix with trace \( 1 - \alpha _{(S_1, \ldots , S_l), \delta } - \beta _{(S_1, \ldots , S_l), \delta }. \) Define

It is now clear that \(M^{A''_{[k]}}_{(S_1, \ldots , S_l),{\mathbf{x}} ,{\mathbf{l}} ,\delta }\) is a positive semidefinite matrix with unit trace with support orthogonal to that of the sum of the first two terms in Equation (A16). The notation “Other Terms I” denotes a \((2^l - 1)\)-fold sum of tensor products of \((l+1)\) matrices where one multiplicand is \(\sigma _{\mathbf{x}} ^{A_{[k] {\setminus } (S_1 \cup \cdots \cup S_l)}} \otimes (|{0}\rangle \langle {0}|)^{({\mathbb {C}}^2)^{\otimes |[k] {\setminus } (S_1 \cup \cdots \cup S_l)|}},\) at least one multiplicand is of the form \((N')^{A''_{S_i \cap [k]}}_{ S_i, {\mathbf{x}} _{S_i \cap [c]}, {\mathbf{l}} _{S_i}, \delta },\) and the remaining multiplicands are of the form

with \(\ell _1\)-norm at most one. We use \((N')^{A''_{[k]}}_{(S_1, \ldots , S_l),{\mathbf{x}} ,{\mathbf{l}} ,\delta }\) to denote the “Other Terms I”. It is clear that \( (N')^{A''_{[k]}}_{(S_1, \ldots , S_l),{\mathbf{x}} ,{\mathbf{l}} ,\delta } \) is a Hermitian matrix with trace \(\beta _{(S_1, \ldots , S_l), \delta }. \) Define

It is now clear that \(N^{A''_{[k]}}_{(S_1, \ldots , S_l),{\mathbf{x}} ,{\mathbf{l}} ,\delta }\) is a Hermitian matrix with unit trace. Also, \(\beta _{(S_1, \ldots , S_l), \delta } = 0\) if \(c = 0\).

Thus

1.5 Appendix I.5 Proving Claim 1

Using Equation (A9), we have

where we use the fact that \( \left\| { ( {\mathbb {1}}^{A''_{[k]}} -(\Pi ')^{A''_{[k]}}_{Y'_{{\mathbf{x}} ,{\mathbf{l}} , \delta }} ) }\right\| _\infty \le 1 \) as \(({\mathbb {1}}^{A''_{[k]}} - (\Pi ')^{A''_{[k]}}_{Y'_{{\mathbf{x}} ,{\mathbf{l}} , \delta }})\) is the orthogonal projection onto the complement of the subspace \(Y'_{{\mathbf{x}} ,{\mathbf{l}} , \delta }\).

1.6 Appendix I.6 Proving Claim 2

Let , \(\{\} \ne S \cap [k] \ne [k]\). Let \(|{h_{\mathbf{x}} (i)}\rangle \in ({\mathcal {H}}\otimes {\mathbb {C}}^2)^{\otimes k}\) be the ith eigenvector of \(\rho _{\mathbf{x}} ^{A_{[k]}} \otimes (|{0}\rangle \langle {0}|^{{\mathbb {C}}^2})^{\otimes k}\). Fix a subpartition \((T_1, \ldots , T_{l'}) \models _{\times \times } S\) and an index \(j_{(T_1, \ldots , T_{l'})}\) in the Schmidt decomposition of \({\mathcal {T}}_{\models _\times S, {\mathbf{l}} , \delta }(|{h_{\mathbf{x}} (i)}\rangle )\) with respect to \((S \cap [k], \bar{S} \cap [k])\) given in Equation (A11). Define

where we write \(|{\gamma _{j_{(T_1, \ldots , T_{l'})}, {\mathbf{x}} ,{\mathbf{l}} _S {\mathbf{l}} '_{\bar{S}}}(i)}\rangle \) in order to emphasise the dependence on \({\mathbf{x}} \) and \({\mathbf{l}} := {\mathbf{l}} _S {\mathbf{l}} '_{\bar{S}}\).

From the definition of \((M')_{S, {\mathbf{x}} _{S \cap [c]}, {\mathbf{l}} _S, \delta }^{A''_{S \cap [k]}}\) in Equation (A15), it is easy to see that proving

for all subpartitions \((T_1,\ldots ,T_{l'}) \vdash _{\times \times } S\), indices \(j_{(T_1, \ldots , T_{l'})}\), and i suffices to show that

Now it is easy to see using Equations (A16), (A17) that this implies that

It only remains to show \(\left\| {(M')^{A''_{S \cap [k]}}_{S,{\mathbf{x}} , {\mathbf{l}} _S,\delta ,(T_1,\ldots ,T_{l'}),j_{(T_1, \ldots , T_{l'})} }(i) }\right\| _\infty \le \frac{1}{|{\mathcal {L}}|} \) for any subpartition \((T_1,\ldots ,T_{l'}) \vdash _{\times \times } S\), index \(j_{(T_1, \ldots , T_{l'})}\), and i. In fact, we will prove the stronger statement that

Since \((T_1 \cup \cdots \cup T_{l'}) \cap \bar{S} \ne \{\}\), this would complete the proof of the first part of Claim 2 of Proposition 4.

By triangle inequality, we have

where we use the fact that

for \({\mathbf{l}} '_{\bar{S} \cap (T_1 \cup \cdots T_{l'})} \ne {\mathbf{l}} ''_{\bar{S} \cap (T_1 \cup \cdots T_{l'})}\) in this equality. This follows from the observation that for distinct computational basis vectors \({\mathbf{l}} '_{\bar{S} \cap (T_1 \cup \cdots T_{l'})},\) \({\mathbf{l}} ''_{\bar{S} \cap (T_1 \cup \cdots T_{l'})},\) there exists an \(i \in [l']\), a coordinate \(a \in \bar{S} \cap T_i\) such that \({\mathbf{l}} '_a \ne {\mathbf{l}} ''_a\), which implies that \( |{ \gamma _{ j_{(T_1, \ldots , T_l)}, {\mathbf{x}} , {\mathbf{l}} _S {\mathbf{l}} '_{\bar{S} {\setminus } (S_1 \cup \cdots \cup S_{l'})} {\mathbf{l}} '_{\bar{S} \cap (T_1 \cup \cdots T_{l'})} }(i)}\rangle \),

\(|{\gamma _{ j_{(T_1, \ldots , T_l)}, {\mathbf{x}} , {\mathbf{l}} _S {\mathbf{l}} '_{\bar{S} {\setminus } (S_1 \cup \cdots \cup S_{l'})} {\mathbf{l}} ''_{\bar{S} \cap (T_1 \cup \cdots T_{l'})} }(i) }\rangle \) lie in the orthogonal subspaces \( ( ({\mathcal {H}}\otimes {\mathbb {C}}^2) \otimes |{{\mathbf{l}} _{T_i \cap S} {\mathbf{l}} '_{T_i \cap \bar{S}}}\rangle )_b \otimes A''_{(S \cap [k]) {\setminus } \{b\}},\) \( ( ({\mathcal {H}}\otimes {\mathbb {C}}^2) \otimes |{{\mathbf{l}} _{T_i \cap S} {\mathbf{l}} ''_{T_i \cap \bar{S}}}\rangle )_b \otimes A''_{(S \cap [k]) {\setminus } \{b\}},\) \(b \in S \cap [k] \cap T_i,\) where the first multiplicands in the two tensor products are embedded into \(A''_b\).

This completes the proof of the first part of Claim 2 of Proposition 4.

Again, let , \(\{\} \ne S \cap [k] \ne [k]\). If \([c] \subset S\), then \( N''_{{\mathbf{l}} _{S \cup [c]}, \delta }(|{h}\rangle \langle {h}|) = 0. \) Suppose \(S \cap [c] \ne [c]\). Suppose one were to show that

for all unit length vectors \(|{h}\rangle \in ({\mathcal {H}}\otimes {\mathbb {C}^2})^{\otimes (S \cap [k])}\). From Equations (A14), (A15) and the triangle inequality, in either case, it will follow that

Now it is easy to see using Equations (A16), (A18) that this implies that

It only remains to show for \(S \cap [c] \ne [c]\) that

for any unit length vector \(|{h}\rangle \in ({\mathcal {H}}\otimes {\mathbb {C}}^2)^{\otimes (S \cap [k])}\). By Equation (A13), it suffices to show that

Since the range spaces of the summands in the definition of \({\mathcal {T}}_{\models _\rightsquigarrow S, {\mathbf{l}} _{S \cup [c]} , \delta }\) are orthogonal, it suffices to show, for any \((T_1, \ldots , T_l) \vdash \vdash S \cup [c]\), \((T_1, \ldots , T_l) \models _\rightsquigarrow S\), \({\mathbf{l}} _S\), \({\mathbf{l}} '_{[c] {\setminus } (S \cup T_1 \cup \cdots \cup T_l)}\) that

and

The last two equalities arise from the fact that for any two distinct computational basis vectors

the range spaces of

are orthogonal. This follows from the observation that there exists an \(i \in [l]\), a coordinate \(a \in [c] \cap \bar{S} \cap T_i\) such that \({\mathbf{l}} ''_a \ne {\mathbf{l}} '''_a\), which implies that the two range spaces embed into the orthogonal spaces \( ( ({\mathcal {H}}\otimes {\mathbb {C}}^2) \otimes |{ {\mathbf{l}} _{T_i \cap S} {\mathbf{l}} ''_{T_i \cap \bar{S} \cap [c]}}\rangle )_b \otimes A''_{(S \cap [k]) {\setminus } \{b\}}\), \((({\mathcal {H}}\otimes {\mathbb {C}}^2) \otimes |{ {\mathbf{l}} _{T_i \cap S} {\mathbf{l}} '''_{T_i \cap \bar{S} \cap [c]} }\rangle )_b \otimes A''_{(S \cap [k]) {\setminus } \{b\}}\), \(b \in S \cap [k] \cap T_i\), where the first multiplicands in the two tensor products are embedded into \(A''_b\).

This completes the proof of the second part of Claim 2 of Proposition 4.

1.7 Appendix I.7 Proving Claim 3

Let \(|{h}\rangle \) be a unit length vector in \(({\mathcal {H}}\otimes {\mathbb {C}}^2)^{\otimes k}\). From Equation (A1) and Inequality (A2), we get

Thus

where we used the fact that \(e^{-x} \ge 1 - x\) in the last inequality. Recalling Equation (A3) and applying the afore-mentioned inequality to the eigenvectors of \(\rho ^{A_{[k]}} \otimes (|{0}\rangle \langle {0}|^{{\mathbb {C}}^2})^{\otimes k}\) allows us to prove the desired Claim 3 of Proposition 4.

1.8 Appendix I.8 Proving Claim 4

Let \(|{h}\rangle \) be an eigenvector of \(\rho ^{A_{[k]}} \otimes (|{0}\rangle \langle {0}|^{{\mathbb {C}}^2})^{\otimes k}\). For a pseudosubpartition , define

where the subspace \(Y_{{\mathbf{x}} , (T_1, \ldots , T_m)} \le ({\mathcal {H}}\otimes {\mathbb {C}}^2)^{\otimes [k]}\) is defined just after Equation (A4). Recall that the subspace \(Y'_{{\mathbf{x}} , {\mathbf{l}} ,\delta }\) defined in Equation (A8) is the A-tilted span of where the tilting matrix A is defined in Equation (A5). Recall that A is upper triangular, substochastic, and diagonal dominated, and the diagonal entries of A satisfy

for all . By Proposition 3

Using Equation (A4) and applying this inequality to the eigenvectors of \(\rho ^{A_{[k]}} \otimes (|{0}\rangle \langle {0}|^{{\mathbb {C}}^2})^{\otimes k}\), we get

Finally, using Fact 3 and Equation (A9), we get

1.9 Appendix I.9 Proving Claim 5

This claim and the accompanying claims of orthogonality and vanishing of \(\beta _{(S_1, \ldots , S_l),\delta }\) are proved at the end of Appendix I.4.

1.10 Appendix I.10 Proving Claim 6

Using Equations (A9), (A8), (A7), and (A4), we get

In the second inequality here, we used the fact that

In the second equality here, we used the property that the support of \( {\mathcal {T}}_{S_1, \ldots S_l), {\mathbf{l}} , \delta } ( \rho _{{\mathbf{x}} , (S_1, \ldots , S_l)}^{A_{[k]}} \otimes (|{0}\rangle \langle {0}|^{{\mathbb {C}}^2})^{\otimes k} ) \) lies in the vector space \( {\mathcal {T}}_{(S_1,\ldots ,S_l),\mathbf{l} ,\delta }(({\mathcal {H}}\otimes {\mathbb {C}}^2)^{\otimes k}). \) We used the property that the map \( {\mathcal {T}}_{(S_1, \ldots S_l), {\mathbf{l}} , \delta } \) is an isometric embedding of \(({\mathcal {H}}\otimes {\mathbb {C}}^2)^{\otimes k})\) in the fourth and fifth equalities. Finally, we used the definition of \( Y_{{\mathbf{x}} ,(S_1, \ldots , \cup S_l)} \) given just after Equation (A4) for obtaining the last equality.

This completes the proof of Claim 6 of Proposition 4 and thus finishes the proof of Proposition 4.

Appendix II. Proof of Equation (2)

The probability of incorrectly decoding the sent message pair \((m_1,m_2)\), for a given codebook \({\mathcal {C}}\), is upper bounded by

The expectation, over the choice of the random codebook \({\mathcal {C}}\), of the decoding error is then upper bounded by

Here, we use the property that

for all triples (x, y, z) in Step (a), and Equation (1) in Step (b).

Reprints and permissions