Decoupling by Local Random Unitaries without Simultaneous Smoothing, and Applications to Multi-user Quantum Information Tasks

Multi-user information theory is intrinsically difficult, with several of the classic transmission problems remaining unsolved despite decades of research, including the bidirectional channel [1], the broadcast channel [2], and the interference channel [3] (except in particular cases), cf. [4]. Even models such as the multiple-access channel (MAC) that have been solved early on [5, 6] have recently exhibited unexpected additional complexity: indeed, while the capacity region of a general MAC has a finitary single-letter expression, its computation (or even approximation) in terms of the channel parameters turns out to be NP-hard, and with entanglement-assistance it is even uncomputable [7].

The foundational tool of joint typicality (a multipartite probability distribution being typical in several of its marginals simultaneously) is frequently employed in classical multi-user settings to define and analyze codes and decoders, and serves as a single conceptual integrator of many constructions (even if it does not always yield the best possible performance) [4, 8]. The analogous problems in quantum information theory have added difficulty at an even more fundamental level because this basic tool is simply not available in the required generality for multipartite quantum states, although it has been conjectured both in a form suited to i.i.d systems [9, Conj. 3.2.7] and in a general form for min-entropies [10], also known as the simultaneous smoothing conjecture. In the absence of a general solution to this conjecture (either in its one-shot or the asymptotic version), researchers have developed workarounds of varying complexity and applicability. For small numbers of parties (two or three) and specific problems, it can be avoided altogether [10]; and for classical information transmission tasks over quantum channels with multiple senders and receivers, a “simultaneous hypothesis testing” technique combining a modification of the state with hypothesis testing [11, 12] overcomes this technical barrier.

However, there are at least two types of tasks that require a different primitive and therefore remain hindered by the simultaneous smoothing conjecture: cryptographic privacy amplification and randomness concentration on the one hand, and simultaneous quantum information transmission between multiple parties on the other (including channel coding, as well as channel simulation). All these impaired tasks can be based on the decoupling of one part of a correlated state from another, via the concatenation of a unitary (typically random) and a fixed irreversible quantum channel. This primitive is well-developed in the case of a single system to decouple and well-understood to be governed by min-entropies [13,14,15,16,17,18,19,20,21,22,23].

Here, we develop a solution for simultaneous decoupling, extending the “generalised decoupling” approach of Dupuis et al. [24] to multiple systems undergoing local random unitaries followed by a CPTP map (see Fig. 1). We are able to do so without addressing the simultaneous smoothing conjecture by leveraging contractivity properties of random channels and multiplicativity of contraction under tensor products.

Generalised multipartite decoupling via local random unitary transformations \(\mathcal {U}_i\) acting locally on each system \(A_i\), followed by a fixed CPTP map \(\mathcal {T}_{A_1\dots A_k\rightarrow B}\)

Full size image

We illustrate the reach of our method by proving multi-party generalised decoupling theorems in terms of both Rényi and smooth min-entropies. As applications, we show how we obtain one-shot and asymptotic i.i.d. coding theorems for four quantum information tasks.

The rest of the paper is structured as follows: we start with some notation and preliminary material in Sect. 2. Then we present the problem setting and main results in Sect. 3, followed by the core technical lemmas in Sect. 4. The main decoupling theorems are proved in Sect. 5. In Sect. 6, we apply the decoupling theorems to the problems of randomness extraction [25, 26], entanglement of assistance [9, 16, 17, 27], quantum state merging (also known as quantum Slepian-Wolf problem), and quantum multiple access coding [28]; these are developed in the fully general one-shot form, and then applied to the i.i.d. asymptotics as well as to the so-called compound setting of an only partially known i.i.d. source or channel. The resulting one-shot and compound rate formulas had long been conjectured but are here proved for the first time. We conclude in Sect. 7, including a comparison with previous approaches.

We denote the Hilbert spaces associated with finite-dimensional quantum systems by capital letters, A, B, etc., and by \(|{A}|\) the dimension of A. The composition of two systems is facilitated by the tensor product of the Hilbert spaces, \(AB=A\otimes B\). Multipartite operators \(\rho _{AB}\) acting on this tensor product space have their corresponding reduced operator denoted as \(\rho _A=\text {Tr}_B \rho _{AB}\). The set of normalized quantum states (non-negative operators \(\rho \) on A with \(\text {Tr}\rho =1\)) is denoted as \(\mathcal {S}(A)\).

We use the abbreviation CP to denote completely positive maps \(\mathcal {T}_{A\rightarrow B}\) (and CPTP if they are additionally trace-preserving maps), and \(\tau _{AB}=\left( \mathbbm {1}_A\otimes \mathcal {T}_{A'\rightarrow B}\right) \left( {|{\Phi }\rangle }\!{\langle {\Phi }|}{\Phi }_{AA'}\right) \) is their corresponding Choi operator, where \({|{\Phi }\rangle }_{AA'}=\frac{1}{\sqrt{|{A}|}}\sum _{i=1}^{|{A}|}{|{i}\rangle }_A\otimes {|{i}\rangle }_{A'}\) is the maximally entangled state.

The basic metric on quantum states is given by the trace norm distance, \(\Vert \rho -\sigma \Vert _1\). Recall the definition of the trace norm of an operator M: \(\Vert M\Vert _1=\text {Tr}\sqrt{M^\dagger M}\). This quantity is lower bounded by 0 (when \(\rho =\sigma \)) and upper bounded by 2 due to the triangle inequality \(\Vert \rho -\sigma \Vert _1\le \Vert \rho \Vert _1+\Vert \sigma \Vert _1=2\). We shall mostly use the normalized trace distance defined as

We will also come across the Hilbert-Schmidt norm \(\Vert M\Vert _2=\sqrt{\text {Tr}M^\dagger M}\). Actually, it is useful to define the Schatten p-norms as a generalisation of the previous. Given a real number \(p\ge 1\) and a linear operator M, the Schatten p-norm is given by

Likewise, we have to define the diamond norm of a linear map \(\Theta :A\rightarrow B\), which is the trace norm of the output of a trivial extension of \(\Theta \) maximized over all possible input operators \(M\in A'A\) with \(\Vert M\Vert _1\le 1\), that is \(\displaystyle \Vert \Theta \Vert _\diamond =\max _{M \text { s.t. } \Vert M\Vert _1\le 1}\Vert ({\text {id}}_{A'}\otimes \Theta )M\Vert _1\) [29, 30].

Our technical results are small upper bounds on the trace distance between states, proving that they are almost equal. These bounds are presented in terms of conditional entropy measures. Let us recall the following standard definitions. The von Neumann entropy of a state \(\rho _A\in \mathcal {S}(A)\) is defined as \(S(A)_\rho = S(\rho _A) = -\text {Tr}\rho \log \rho \), and the conditional von Neumann entropy of A given B for the bipartite state \(\rho _{AB}\) is \(S(A|B)_\rho =S(AB)_\rho -S(B)_\rho \). Also, for \(\rho _{AB}\in \mathcal {S}(AB)\) and \(\sigma _B\in \mathcal {S}(B)\), we define the sandwiched conditional Rényi entropy of order \(\alpha \in [\frac{1}{2},1)\cup (1,\infty )\) given \(\sigma _B\) [31, 32] as

The maximisation of the sandwiched conditional Rényi entropy given \(\sigma _B\in \mathcal {S}(B)\) over all possible states \(\sigma _B\) gives the conditional Rényi entropy of \(\rho _{AB}\), denoted \(\widetilde{H}_\alpha (A|B)_\rho \). This quantity is monotone non-increasing in \(\alpha \) [33], and if we take the limit \(\alpha \rightarrow 1\) we recover the conditional von Neumann entropy \(S(A|B)_\rho \). Furthermore, the limit of the Rényi entropy when \(\alpha \rightarrow \infty \) makes sense and is called min-entropy:

where the maximum is taken over all states \(\sigma _B\in \mathcal {S}(B)\). Similarly, for \(\alpha = \frac{1}{2}\) we find the max-entropy:

The max- and min-entropies are related by the fundamental duality relation \(H_{\min }(A|B)_\psi =-H_{\max }(A|C)_\psi \) for any pure tripartite state \(\psi _{ABC}\). Notice also that for \(\alpha =2\) we find the collision entropy, which is the quantity that shows up in the original proofs of the variously general decoupling theorems [19, 24]:

This quantity, however, usually gives unreliable or loose bounds due to its rough responsiveness to small variations in the state \(\rho _{AB}\) over which it is computed. This is why it is commonly substituted by the min-entropy, which is more reliable, and robust and a lower bound on the collision entropy due to the monotonicity of Rényi entropies under \(\alpha \). In one-shot settings, it is also useful to \(\epsilon \)-smooth the min and max-entropies. I.e., computing them on the best state \(\omega \) in an \(\epsilon \)-ball around \(\rho \) with respect to the purified distance \(P(\rho ,\omega )=\sqrt{1-\Vert \sqrt{\rho }\sqrt{\omega }\Vert _1^2}\):

Smoothing allows us to discard atypical behaviour in the states. In multi-party settings, it makes sense to wish for simultaneous smoothing of all the marginals of the given state: that is, we want to modify the global state so that its marginals appear smoothed. More formally, for any number m of parties we would like to find functions \(g_m(\epsilon )\) and \(h_m(\epsilon )\) with \({\lim _{\epsilon \rightarrow 0} g_m(\epsilon )=0}\) and \(h_m(\epsilon )\) finite for any m and \(\epsilon >0\), such that for every state \(\rho _{A_1\dots A_mB}\) on an \((m+1)\)-party system \(A_1\ldots A_mB\) there exists another state \(\sigma \) with \(P(\rho ,\sigma ) \le g_m(\epsilon )\) that satisfies

This has been stated as a conjecture [10, 34] (without the additive \(h_m(\epsilon )\) term, which however seems very natural to us), but remains unproven in general, in particular for \(m>2\). It has also been used to conjecture rate regions in several multi-party quantum information tasks. Here, we find local decoupling theorems without simultaneous smoothing and apply them to finally prove the anticipated achievable rate regions for several multi-party quantum information tasks.

The purified distance between two arbitrary states \(\rho \) and \(\sigma \) is a function of the fidelity \(F(\rho ,\sigma )=\Vert \sqrt{\rho }\sqrt{\sigma }\Vert _1^2\), indeed \(P(\rho ,\sigma )=\sqrt{1-F(\rho ,\sigma )}\). These quantities are related to the normalized trace distance through the Fuchs-van de Graaf inequalities [35]:

The first two are the original inequalities. We took the liberty of adding the third one by noticing \( P(\rho ,\sigma )^2=1-F(\rho ,\sigma )\le 1-\left[ 1-D(\rho ,\sigma )\right] ^2=D(\rho ,\sigma )\left[ 2-D(\rho ,\sigma )\right] \).

We consider random CP maps \(\mathcal {R}^x:A\rightarrow B\), where x is distributed on a given set according to a certain well-defined probability law. If there are systems \(A_1\), \(A_2\), ..., \(A_k\), we consider independently random maps \(\mathcal {R}^{x_i}:A_i\rightarrow B_i\) for \(i\in \{1,\ldots ,k\} =: [k]\). Two particular channels are of special interest to us. The the constant channel (or state preparation channel) \(\mathcal {P}^\sigma :A\rightarrow B\), acting as \(\mathcal {P}^{\sigma }(\rho ) = {\sigma _{B}}{\text {Tr}_{A}}\rho \), that outputs a state \(\sigma \) (or more generally a positive semidefinite operator) on B regardless of the input \(\rho \), and the fully depolarizing channel \(\mathcal {D}:A\rightarrow A\), which can be seen as the particular instance of the constant channel that prepares the maximally mixed state \(\mathcal {D}(\rho )=\frac{\mathbbm {1}_A}{|A|} \text {Tr}_A\rho \). We use superscripts to identify different objects, potentially acting on the same or other spaces, such as \(\mathcal {R}^{x_i}\) and \(\mathcal {R}^{x_j}\), and subscripts on states and channels to record on which systems they act.

We shall only consider random CP maps \(\mathcal {R}^x\) with the property that the average map \(\mathbb {E}_x \mathcal {R}^x\) is a constant map \(\mathcal {P}^\sigma \). Let us also introduce the difference \(\Delta ^x:=\mathcal {R}^x-\mathcal {P}^\sigma \).

Definition 3.1

We call a random Hermitian-preserving map \(\Delta ^x\) \(\lambda \)-expected-contractive if for any system E and any matrix \(\rho _{AE}\),

Dupuis [36] equivalently calls \(\mathcal {R}^x\) \(\lambda \)-randomizing, although he considers this concept only for the preparation maximally mixed state \(\sigma =\frac{1}{|B|}\mathbbm {1}_B\).

Let the systems \(A_1\), \(A_2\), ..., \(A_k\) and E share a state \(\rho _{A_{[k]}E}\), and consider a fixed quantum channel (CPTP map) \(\mathcal {T}:A_{[k]}\rightarrow B\) with Choi state \(\tau _{A_{[k]}B}\). On each system \(A_i\) (\(i\in [k]\)) we define random unitaries \(U_i\) distributed according to a unitary 2-design, so that the average \(\mathbb {E}_{U_i} \mathcal {U}_i = \mathcal {D}_{A_i}\) is the completely depolarizing channel, where we denote the associated unitary channel \(\mathcal {U}_i(\alpha )=U_i\alpha U_i^\dagger \). Then we have random maps \(\mathcal {R}^{U_{[k]}} = \mathcal {T}\circ (\mathcal {U}_1\otimes \cdots \otimes \mathcal {U}_k)\).

Decoupling is about the question: How far from \(\tau _B = \mathcal {T}\left( {\mathbbm {1}_{A_{[k]}}}/{|A_{[k]}|}\right) \) is the output of the channel \(\mathcal {R}^{U_{[k]}}\) typically? To answer it, we aim to give an upper bound on

The crucial insight for everything that follows is that we can rewrite the difference of maps inside the norm as

where \(\Theta _{A_i}:= \mathcal {U}_i-\mathcal {D}_{A_i}\), hence \(\Theta _{A_I}=\bigotimes _{i\in I}(\mathcal {U}_i-\mathcal {D}_{A_i})\), and \(\mathcal {D}_{A_{I^c}}=\bigotimes _{i\not \in I}\mathcal {D}_i\). Therefore, we have \(\mathcal {U}_i = \Theta _{A_i} + \mathcal {D}_{A_i}\) and we can use the distributive law to get the above expansion. Hence,

with \(\mathcal {T}_I:A_I\rightarrow B\) acting as \(\mathcal {T}_I(\rho _{A_I}) = \mathcal {T}\left( \rho _{A_I}\otimes \frac{\mathbbm {1}_{A_{I^c}}}{|A_{I^c}|}\right) \). The first step in our upper bound is the application of the triangle inequality,

This allows us to simply deal with each term \(\emptyset \ne I\subseteq [k]\) separately in the remainder of the argument.

The main technical results of the present work are formulated in the following theorems and their corollary.

Theorem 3.2

Assume \(\mathcal {T}_{A_{[k]} \rightarrow B}\) to be a CPTP map with Choi state, and consider the random channels \(\mathcal {R}^{U_{[k]}}\) as above. Then, for any state \(\rho _{A_{[k]}E}\),

where \(D_I = 2^{|{I}|-1}\prod _{i\in I} \left( 1-\frac{1}{|{A_i}|^2}\right) ^{-\frac{1}{2}}\), \(\tau _B = \mathcal {T}\left( {\mathbbm {1}_{A_{[k]}}}/{|A_{[k]}|}\right) \), the \(\zeta _E^I\) are arbitrary states on E, \(\sigma _B^I\) are arbitrary states on B, and \(\exp _2\) denotes the exponential function to base 2.

Theorem 3.3

Assume \(\mathcal {T}:A_{[k]} \rightarrow B\) to be a CPTP map with \(\mathcal {T}(\mathbbm {1}/|A_{[k]}|)=\mathbbm {1}/|B|\), and consider the random channels \(\mathcal {R}^{U_{[k]}}\) as above. Then, for any state \(\rho _{A_{[k]}E}\),

where \(D_I = 2^{|{I}|-1}\prod _{i\in I} \left( 1-\frac{1}{|{A_i}|^2}\right) ^{-\frac{1}{2}}\) as before, \(\alpha _I\in (1;2]\) are arbitrary real number numbers and \(\zeta _E^I\) are arbitrary states on E.

Corollary 3.4

Under the same conditions of Theorems 3.2 and 3.3, and in the special case that the CP map is a tensor product, \(\mathcal {T}= \mathcal {T}_1\otimes \cdots \otimes \mathcal {T}_k\) with \(\mathcal {T}_i:A_i\rightarrow B_i\) (see Fig. 2) and \(B=B_1\dots B_k\), then Equations (3.4) and (3.5) hold with \(D_I=\prod _{i\in I}\sqrt{1-\frac{1}{|{A_i}|^2}}\).

Multi-party decoupling via local random unitary transformations \(\mathcal {U}_i\) followed by a fixed local CPTP map \(\mathcal {T}_{A_i\rightarrow B_i}\) on each of the systems \(A_i\)

Full size image

Remark 3.5

In Theorem 3.2, we will almost always use the lower bound \(\widetilde{H}_2^{\epsilon _I}(A_I|E)_{\rho |\zeta _E^I} \ge H_{\min }^{\epsilon _I}(A_I|E)_{\rho |\zeta _E^I}\), and optimize \(\zeta _E^I\) for the min-entropy, so that the first term in the exponential of Equation (3.4) becomes \(H_{\min }^{\epsilon _I}(A_I|E)_{\rho }\).

Remark 3.6

For \(k=1\), both the above theorems, or more precisely their versions from Corollary 3.4, reproduce well-known predecessors: Theorem 3.2 is essentially the general decoupling theorem from [24], albeit without the smoothing of the channel Choi matrix \(\tau _{AB}\) (which in practice seems less critical than that of the state). Theorem 3.3 is a restatement of the main result of [36]; see also the precursor [37].

Remark 3.7

Hao-Chung Cheng, Li Gao, and Mario Berta, in concurrent and independent work [38], have discovered the same telescoping trick to obtain similar decoupling bounds, and in fact a multipartite version of the convex-split lemma. In their work, they apply the latter to the simulation of broadcast channels.

4.1 Technical ingredients for the proofs

In this subsection, we collect some well-known technical lemmas that will be used throughout the paper. Their proofs can be found in [24].

Lemma 4.1

Let M be a linear operator on A and \(\sigma \) a positive defined operator. Then

If M is Hermitian this can be simplified to

Lemma 4.2

Let M and N be two linear operators on \(A^{\otimes 2}\), and let \(F_A\) swap the two copies of the A system: \(F_A\left( \sum _{ij}m_{ij}{|{i}\rangle }{|{j}\rangle }\right) =\sum _{ij}m_{ij}{|{j}\rangle }{|{i}\rangle }\). Then, \(\text {Tr}(M\otimes N)F_A = \text {Tr}MN\).

Lemma 4.3

Let M be a linear operator acting on the Hilbert space \(A^{\otimes 2}\). Then, for a random unitary U distributed according to a 2-design (a set of unitaries that collectively approximates the statistical behavior of the entire unitary group up to second-degree polynomials [39]),

where \(\alpha \) and \(\beta \) are such that \(\text {Tr}M = \alpha |{A}|^2+\beta |{A}|\) and \(\text {Tr}MF = \alpha |{A}|+\beta |{A}|^2\).

We can easily generalise this lemma to a multipartite version:

Corollary 4.4

Let M be a linear operator acting on \(A_1^{\otimes 2}\otimes \cdots \otimes A_k^{\otimes 2}\). Then, for \(U_{[k]} = U_1 \otimes \cdots \otimes U_k\) the tensor product of independent unitaries distributed according to 2-designs,

where \(L^c=[k] \setminus L\) is the set complement of L, and the coefficients \(c_L\) are determined by the relations

Lemma 4.5

Let \(\omega _{AB}\) be a non-negative operator acting on AB. Then,

Lemma 4.6

The normalized trace distance \(D(\rho ,\sigma )\) between two quantum states \(\rho ,\sigma \in \mathcal {S}(A)\) is equal to the largest probability difference that the two states could give to the same measurement outcome \(\Lambda \):

Theorem 4.7

(Uhlmann’s theorem for the purified distance). Let \(\rho ,\sigma \in \mathcal {S}(A)\) and \({|{\psi }\rangle }\in A\otimes A'\) be a purification of \(\rho \), with \(A'\cong A\). Then, there exists a purification \({|{\phi }\rangle }\in A\otimes A'\) of \(\sigma \) such that \(P(\rho ,\sigma )=P(\psi ,\phi )\).

4.2 Central lemmas

The proofs of the main theorems (which we will present in the next section) rely on a series of new lemmas listed and proved in this section.

Lemma 4.8

Given any general CP map \(\mathcal {T}_I:A_{I}\rightarrow B\) with \(I\subset [k]\), \(\mathcal {T}_I\circ \Theta _{A_I}\) is \(\lambda _I\)-expected-contractive with

Proof

Recall that \(\mathcal {T}_I\circ \Theta _{A_I}\) is \(\lambda _I\)-expected-contractive if \(\mathbb {E}_{U_I}\Vert \left( \mathcal {T}_I\circ \Theta _{A_I}\right) \rho _{A_IE}\Vert _2\le \lambda _I\Vert \rho _{A_IE}\Vert _2\) for arbitrary \(\rho _{AE}\), where \(\mathbb {E}_{U_I}\) is the expectation value over each \({U_i}\) with \(i\in I\). We will start by assuming \(\rho =\rho ^\dagger \) to be Hermitian. Using Jensen’s inequality, we find \((\mathbb {E}_{U_I}\Vert \left( \mathcal {T}_I\circ \Theta _{A_I}\right) \rho _{A_IE}\Vert _2)^2\le \mathbb {E}_{U_I}\Vert \left( \mathcal {T}_I\circ \Theta _{A_I}\right) \rho _{A_IE}\Vert _2^2\). Now we can expand the square of the Hilbert-Schmidt norm as a trace without carrying the root throughout the demonstration:

where we have used the linearity of the trace in the second equality, and we are imposing for simplicity the additional restriction that the matrices \(\rho _{A_IE}\) are Hermitian, and will prove in the end that the results can be generalised to any matrix. Defining a subset \(J\subseteq I\) and its complement \(J^c=I{\setminus } J\) we can write the expectation value as follows:

We prove this claim by induction on the cardinality of I. For \(|{I}|=1\) (that is \(A_I=A\)) we have \( \mathbb {E}_U\left[ (\mathcal {T}\circ \Theta _A)\rho _{AE}\right] ^2=\mathbb {E}_U[(\mathcal {R}^U-\mathcal {T}\circ \mathcal {D}_{A})\rho _{AE}]^2\). Expanding the binomial and remembering our condition \(\mathbb {E}_U\mathcal {U}(\rho _{AE})=\mathcal {D}_A(\rho _{AE})\) we find:

because \(|{J}| \in \{0,1\}\). We continue the induction by assuming that Equation (4.8) is true for some I, and we want to pass to a bigger set \(I'=I{\mathop {\cup }\limits ^{.}}\{i_0\}\) (with \({\mathop {\cup }\limits ^{.}}\) the disjoint union) to compute the expectation value \(\mathbb {E}_{U_{I'}}[(\mathcal {T}_{I'}\circ \Theta _{A_{I'}})\rho _{A_{I'}E}]^2\) on \(A_{I'}=A_I\otimes A_{i_0}\). Similarly let us define \(J'=J{\mathop {\cup }\limits ^{.}}\{i_0\}\) for a subset \(J\subseteq I\), that is \(A_{J'}=A_J\otimes A_{i_0}\). Then, expanding \(\Theta _{A_i}:=\mathcal {U}_i-\mathcal {D}_{A_i}\) and \(\Theta _{A_I}=\bigotimes _{i\in I}(\mathcal {U}_i-\mathcal {D}_{A_i})\), and rearranging the terms (recall \(\mathcal {D}_{A_{I^c}}=\bigotimes _{i\not \in I}\mathcal {D}_i\)), we can re-write:

By expanding the square (just as we did at the beginning of the induction) we can write \(\mathbb {E}_{U_{i_0}}\left[ \mathcal {T}_{I'}\circ (\mathcal {U}_{{i_0}}-\mathcal {D}_{A_{i_0}})\rho _{A_{I'}E}\right] ^2=\mathbb {E}_{U_{i_0}}\left[ (\mathcal {T}_{I'}\circ \mathcal {U}_{{i_0}})\rho _{A_{I'}E}\right] ^2-\left[ (\mathcal {T}_{I'}\circ \mathcal {D}_{A_{i_0}})\rho _{A_{I'}E}\right] ^2\). This allows us to write

This completes the proof by induction. Now we perform the trace:

using the abbreviation \(\sigma _J:= \rho _{A_JE}\otimes \frac{\mathbbm {1}_{A_{J^c}}}{|{A_{J^c}}|}\) for \({J\subseteq I}\). Now we use the swap trick (as in [24]) to simplify this expression:

where we have used Corollary 4.4 in the third equality. Notice that for a fixed L we have \(2^|{L}|\) possible values for \(\text {Tr}[\rho _{A_{[J\cap L]} E}^2]\prod _{i\subseteq [J^c\cap L]}\frac{1}{|{A_i}|}\). If we expand the sum, we find \(2^{|{I}|-|{L}|}\) elements for each of the \(2^|{L}|\) possible values of the trace and product. Notice also that \(2^{|{I}|-|{L}|-1}\) of this elements are positive and \(2^{|{I}|-|{L}|-1}\) of them are negative. This implies that \(\forall L\ne I\) the sum cancels. We just have to compute the case where L is the whole I. We find:

To compute \(c_I\) we follow the steps in [40], let us define a new auxiliary subset \(P\subseteq I\):

thus

We can find an upper bound for Equation (4.9) by keeping only the positive terms of the sum, these are the terms such that \(|{J^c}|\) is even. And then transforming each partial trace \(\text {Tr}[\rho _{A_JE}^2]\) with \(J\subseteq I\) to \(\text {Tr}[\rho _{A_IE}^2]\), using Lemma 4.5 we find:

and similarly

where we have used that any set I has \(2^{|{I}|-1}\) subsets with an even number of elements, and the same number of subsets with an odd number of elements. With the same method we can bound \(c_I\) from Equation (4.10) and find

Putting together these bounds we obtain

which allows us to identify \(\lambda _I^2\ge \left( 4^{|{I}|-1}/\prod _{i\in I}1-\frac{1}{|{A_i}|^2}\right) \Vert \tau _{A_IB}\Vert _2^2\), under the restriction that \(\rho _{A_IE}\) is Hermitian.

It only remains to show how this result can be generalised from Hermitian to arbitrary matrices. To start, any matrix \(\eta =\eta _{AE}\) can be decomposed into a Hermitian component \(\eta _R\) and an anti-Hermitian component \(i\eta _I\) (with \(\eta _I\) Hermitian): \(\eta =\eta _R+i\eta _I\). Now, applying the definition of the 2-norm we have

where we have used the decomposition of \(\eta \) (and \(\eta ^\dagger =\eta _R-i\eta _I\)) in the second inequality, and the Hermitian preserving property of \(\Delta ^U=\mathcal {R}^U-\mathcal {P}^{\tau _B}\) and the distributive law in the last. With the linearity of the trace and the definition of the 2-norm it follows that \( \left\| \Delta ^U(\eta )\right\| _2^2 = \left\| \Delta ^U(\eta _R)\right\| _2^2 + \left\| \Delta ^U(\eta _I)\right\| _2^2. \) Now, notice that both \(\eta _R\) and \(\eta _I\) are Hermitian so we can employ Equation (4.11) to obtain the following bound:

where we have used \(\Vert \eta \Vert _2^2 = \Vert \eta _R\Vert _2^2+\Vert \eta _I\Vert _2^2\) in the last step. This proves that the property \(\mathbb {E}_U\Vert \Delta ^U(\rho )\Vert _2^2\le \lambda ^2\Vert \rho \Vert _2^2\) for Hermitian matrices extends to general matrices. So the inequality (4.11) holds for any matrix \(\rho _{A_IE}\), and we can take the square root of this inequality to find \(\mathbb {E}_{U_I} \left\| \left( \mathcal {T}_I\circ \Theta _{A_I}\right) \rho _{A_IE}\right\| _2\le \lambda _I\Vert \rho _{A_IE}\Vert _2 \), concluding the proof. \(\square \)

Lemma 4.9

Consider a CP map \(\mathcal {T}:A\rightarrow B\) with Choi operator \(\tau _{AB} = ({\text {id}}\otimes \mathcal {T})\Phi _{AA'}\). Define a random CP map \(\mathcal {R}^U:= \mathcal {T}(U\cdot U^\dagger )\), where U is distributed according to a probability law p on SU(A) that is a 2-design, for example, the Haar measure.

Then, the family \(\mathcal {R}^U\) is \(\lambda \)-randomizing (equivalently, \(\Delta ^U=\mathcal {R}^U-\mathcal {P}^{\tau _B}\) is \(\lambda \)-expected-contractive) for any \(\lambda \ge \sqrt{1-\frac{1}{|{A}|^2}} \Vert \tau _{AB}\Vert _2\).

Proof

Notice that this is actually nothing else than a simple particular case of Lemma 4.8 with \(|{I}|=1\), this is \(A_I=A\). We will just find a tighter bound on the constant \(\lambda \). Let us again develop the argument first for Hermitian matrices. From Equations (4.9) and (4.10) we observe:

We upper bound the parameter c with the help of Lemma 4.5. Notice \(-|{A}|\text {Tr}\tau _B^2 \le -\text {Tr}\tau _{AB}^2\), therefore \(c\le \text {Tr}\tau _{AB}^2\). Similarly, \(-|{A}|\text {Tr}\rho _B^2 \le -\text {Tr}\rho _{AB}^2\). We thus find

Now, using Jensen’s inequality we have

Repeating the argument that concluded the proof of Lemma 4.8 we can directly generalise this results to any matrix (not necessarily Hermitian) \(\rho _{AE}\). This implies that \(\mathcal {T}\circ \Theta \) is \(\lambda \)-expected contractive for any \(\lambda \ge \sqrt{1-\frac{1}{|{A}|^2}}\Vert \tau _{AB}\Vert _2\). \(\square \)

Lemma 4.10

Let \(\Delta ^{x_i}:A_i\rightarrow B_i\) be \(\lambda _i\)-expected-contractive maps, for \(i\in I\), where I is a finite index set and the \(x_i\) are independent random variables. Then, the family

where \(x_I=(x_i:i\in I)\), is \(\lambda _I\)-expected-contractive with \(\lambda _I = \prod _{i\in I} \lambda _i\).

Proof

It is enough to prove the claim for \(I=\{1,2\}\), as then the general case follows by induction on the cardinality of I.

Indeed, if \(\Delta ^{x_I}=\Delta ^{x_A}\otimes \Delta ^{x_B}\), then \(\mathbb {E}_{x_I} \Vert \Delta ^{x_I}(\rho _{ABE})\Vert _2 = \mathbb {E}_{x^{AB}} \Vert (\Delta ^{x_A}\otimes \Delta ^{x_B})(\rho _{ABE})\Vert _2\). If we define \(\eta _{ABE}^{x_B}:= (\mathbbm {1}_A\otimes \Delta ^{x_B})(\rho _{ABE})\) we can bound

and we are done. \(\square \)

We can join Lemmas 4.8 and 4.10 in a single statement by making a distinction between the most general scenario where any general CP map \(\mathcal {T}_I:A_I\rightarrow B\) is applied, and the particular case where the map has a tensor product structure \(\mathcal {T}_I=\bigotimes _{i\in I}\mathcal {T}_i\) such that \(\mathcal {T}_i:A_i\rightarrow B_i\), \(B=\bigotimes _{i\in I} B_i\). In this second case, we can tighten the bound. We redact such a general statement in the following corollary.

Corollary 4.11

Given a CP map \(\mathcal {T}:A_I\rightarrow B\) with \(I\subset \left[ k\right] \), \(\mathcal {T}_I\circ \Theta _{A_I}\) is \(\lambda _I\)-expected-contractive with \(\lambda _I=D_I\Vert \tau _{A_IB}\Vert _2\), where

Proof

The first statement is actually Lemma 4.8, so it has already been proved. The second statement follows from Lemmas 4.9 and 4.10. Notice that if the CP map has the commented tensor product structure, we can extract from Lemma 4.9 that \(\mathcal {T}_i\circ \Theta _{A_i}\) is \(\lambda _i\)-expected contractive with \(\lambda _i=\sqrt{1-\frac{1}{|{A_i}|^2}} \Vert \tau _{A_iB_i}\Vert _2\) for each system \(A_i\). Now, from Lemma 4.10 we can calculate \(\lambda _I=\prod _{i\in I}\lambda _i=\prod _{i\in I} \left( \sqrt{1-\frac{1}{|{A_i}|^2}}\Vert \tau _{A_iB_i}\Vert _2\right) = \left( \prod _{i\in I}\sqrt{1-\frac{1}{|{A_i}|^2}} \right) \Vert \tau _{A_IB}\Vert _2\). \(\square \)

Lemma 4.12

Consider a \(\lambda \)-randomizing family of channels \(\mathcal {R}^U:=\mathcal {T}(U\cdot U^\dagger )\), where \(\mathcal {T}:A\rightarrow B\) is a CPTP map such that \(\mathcal {T}(\mathbbm {1}_A/|A|)=\mathbbm {1}_B/|B|\) with Choi operator \(\tau _{AB}=({\text {id}}\otimes \mathcal {T})\Phi _{AA'}\), U is distributed according to a probability law on SU(A) that is a 2-design, and let us choose \(\lambda ^2=\text {Tr}\tau _{AB}^2 \ge \left( 1-\frac{1}{|A|}\right) \Vert \tau _{AB}\Vert _2^2\) from Lemma 4.9. Then,

where \(\tau _B=\text {Tr}_A \tau _{AB} = \mathbbm {1}_B/|{B}|\) is the maximally mixed state. Furthermore, for any \(\mathcal {T}_I: A_I\rightarrow B_I\), with \(\mathcal {T}_I\left( \frac{\mathbbm {1}_{A_I}}{|A_I|}\right) =\frac{\mathbbm {1}_{B_I}}{|B_I|}\), and \(D_I\) given in Corollary 4.11 we have

Proof

Applying the definition of the Rényi entropies we have

where we have applied Lemma 4.9 in the last equality. Similarly, following Corollary 4.11 for a CP map \(\mathcal {T}:A_I\rightarrow B\) we find

concluding the proof. \(\square \)

In Sect. 3 we have found the bound

which allows us to treat each term of the sum on the right-hand side independently.

Proof of Theorem 3.2

Let us define the modified objects \((\zeta _E^I)^{-\frac{1}{4}}\rho _{A_IE}(\zeta _E^I)^{-\frac{1}{4}}:=\tilde{\rho }_{A_IE}\) and \((\sigma _B^I)^{-\frac{1}{4}}(\mathcal {T}_I\circ \Theta _{A_I})(\cdot )(\sigma _B^I)^{-\frac{1}{4}}:=(\tilde{\mathcal {T}}_I\circ \Theta _{A_I})(\cdot )\), with a pair of states \(\sigma _B^I\) and \(\zeta _E^I\) chosen for each term \(\emptyset \ne I\subseteq [k]\). Using Lemma 4.1 we can bound

Hence, the expected values are bounded as \(\mathbb {E}_{U_I}\!\left\| \left( \mathcal {T}_I\circ \Theta _{A_I}\right) (\rho _{A_IE}) \right\| _1 \le \mathbb {E}_{U_I}\left\| (\tilde{\mathcal {T}}_I\circ \Theta _{A_I})\tilde{\rho }_{A_IE} \right\| _2\). We extract from Corollary 4.11 that \(\tilde{\mathcal {T}}_I\circ \Theta _{A_I}\) is \(\lambda _I\)-expected-contractive with \(\lambda _I=D_I\Vert \tilde{\tau }_{A_IB}\Vert _2\). Therefore, \(\mathbb {E}_{U_I} \left\| (\tilde{\mathcal {T}}_I\circ \Theta _{A_I})\tilde{\rho }_{A_IE} \right\| _2\le D_I\left\| \tilde{\tau }_{A_IB}\right\| _2 \left\| \tilde{\rho }_{A_IE}\right\| _2\), with \(D_I=2^{|{I}|-1}\prod _{i\in I}\left( 1-\frac{1}{|{A_i}|^2}\right) ^{-\frac{1}{2}}\) in the most general scenario. Now we unpack our tilde-modified operators to the original ones:

Notice that we can always express sandwiched conditional Rényi entropies by means of Schatten-\(\alpha \) norms as \(2^{\frac{1-\alpha }{\alpha }\widetilde{H}_\alpha (A|B)_{\rho |\zeta }} = \left\| \zeta _E^{\frac{1-\alpha }{2\alpha }}\rho _{AE}\zeta _E^{\frac{1-\alpha }{2\alpha }}\right\| _\alpha \). Thus,

Now we can \(\epsilon _I\)-smooth each term \(\emptyset \ne I\subseteq [k]\). That is, we consider states \(\rho _{A_IE}'\) such that \(\frac{1}{2}\Vert \rho _{A_IE}-\rho _{A_IE}'\Vert _1\le \epsilon _I\). Thus, we can bound

because \(\Vert \Theta _{A_i}\Vert _\diamond \le 2\) and so \(\Vert \Theta _{A_I}\Vert _\diamond \le 2^|{I}|\) due to the multiplicativity of the diamond norm under tensor products. Now using the triangle inequality we have

where \(\widetilde{H}_{2}^{\epsilon _I}\) is the smooth version of the sandwiched collision entropy, i.e. it is optimized over all possible states inside a \(\epsilon _I\)-ball around \(\rho \) (a lower bound). This finally gives us:

Proving Theorem 3.2 and Corollary 3.4 by changing the value of the constant \(D_I\) according to the structure of the CP map as shown in Corollary 4.11.

Notice that the above bound can also be expressed in terms of min-entropies by lower-bounding \(\widetilde{H}_2(A_I|E)_{\rho '|\zeta _E^I}^{\epsilon _I}\ge H_\text {min}^{\epsilon _I}(A_I|E)_\rho \) (see Remark 3.5) on the last inequality of Equation (5.2).

Dupuis [36] gave a bound on single-system decoupling using Rényi entropies; see also [37]. The main technical result in that paper states

for any family of CPTP maps \(\mathcal {N}^U:A\rightarrow B\) that is a \(\lambda \)-expected contractive [36, Lemma 7 & Thm. 8]. Defining \(\mathcal {N}^U:=\mathcal {R}^U-\mathcal {D}_A\), he finds

which we have rewritten using Lemma 4.12 in a more compact and recognisable form. The general case is a straightforward generalisation of this, as we have done all the heavy lifting before.

Proof of Theorem 3.3

We start once again with

Just as in the previous proof, we can treat each term of the sum independently. Now, by defining \(\mathcal {N}^U:=\mathcal {T}_I\circ \Theta _{A_I}:A_I\rightarrow B_I\), we know from Lemma 4.8 that this family of maps is \(\lambda _I\)-expected contractive. Thus, by Equation (5.4),

where \(\alpha _I\in (1,2]\). Furthermore, from Lemma 4.8 and more generally Corollary 4.11 we know the value of \(\lambda _I\), and actually we can identify \(\log |B_I|+2\log \lambda _I=2\log D_I-\widetilde{H}_2(A_I|B)_{\tau |\tau _{B_I}}\) using Lemma 4.12. Therefore we can finally write:

concluding the proof of Theorem 3.3 and Corollary 3.4.\(\square \)

To illustrate the power of our decoupling results, we shall discuss and solve four example problems in multi-user quantum information theory that have until now been hampered by the absence of the simultaneous smoothing technique. These are, in order: local randomness extraction from a given multipartite state in Subsection 6.1; concentration of multipartite pure entanglement in the hands of two designated users by LOCC, aka entanglement of assistance in Subsection 6.2; quantum state merging, aka quantum Slepian-Wolf problem in Subsection 6.3; and finally quantum communication via quantum multiple access channels (MAC) in Subsection 6.4.

For all of them, we first show how our decoupling bound yields a flexible one-shot achievability result, which in turn implies asymptotic rates in the i.i.d. setting that in some cases had only been conjectured so far, or were known to rely on much more complicated proofs. We demonstrate furthermore the versatility of the one-shot bounds by generalising the i.i.d. asymptotic rates to the case that the single-system state/channel is only partially known (compound source/channel setting).

In order to take this step from one-shot to i.i.d. settings we make use of the quantum asymptotic equipartition property (AEP) [41], which we state below along with a couple of other lemmas needed in the subsequent subsections.

Theorem 6.1

[AEP]. Let \(\rho _{AB}\) be a bipartite state acting on \(A\otimes B\), so that for an integer n, \(\rho _{AB}^{\otimes n}\) is a state on \((A\otimes B)^{\otimes n}\). Then, for any \(0<\epsilon <1\),

\(\square \)

Lemma 6.2

(State space \(\epsilon \)-net [42]). For \(\epsilon >0\) and an integer d, there exists a set \(\mathcal {S}_0\) of states on \(\mathcal {S}(\mathbb {C}^d)\) with \(M=|\mathcal {S}_0| \le \left( \frac{5}{\epsilon }\right) ^{2d^2}\), such that for every \(\rho \in \mathcal {S}(\mathbb {C}^d)\) there exists a \(\rho _0\in \mathcal {S}_0\) with \(\frac{1}{2}\Vert \rho -\rho _0\Vert _1 \le \epsilon \). \(\square \)

Lemma 6.3

(Duality of Rényi entropies [31, 43], see also [44]). If \(\alpha ,\beta \in \left[ \frac{1}{2},\infty \right] \) such that \(\frac{1}{\alpha }+\frac{1}{\beta }=2\), then for any pure tripartite state \(\psi _{ABC}\): \( \widetilde{H}_\alpha (A|B)_\psi = -\widetilde{H}_\beta (A|C)_\psi \). \(\square \)

Lemma 6.4

(Classical conditioning [31, Prop. 9]). For a cq-state \(\rho _{ABY} = \sum _y \rho _{AB} \otimes p_y{|{y}\rangle }\!{\langle {y}|}_Y\) and any \(\alpha >0\),

\(\square \)

Lemma 6.5

For any convex combination of N states on AB, \(\overline{\rho } = \sum _{i=1}^N p_i \rho _i\), and \(0< \beta \le \infty \),

Proof

We show the bound only for \(0<\beta <1\), for \(\beta >1\) it is analogous, and for \(\beta =1\) it follows from taking a limit (the case \(\beta =\infty \) had been observed in [45]). Our starting point is the relation [46, Prop. 2.9]

for the sandwiched Rényi relative entropy and the quantity appearing inside the logarithm:

We use the right-hand inequality and upper bound successively

the rightmost inequality by the concavity of the function \(x^\beta \). Thus,

so finally for our conditional Rényi entropy, \(\widetilde{H}_\beta (A|B)_\rho = \max _{\sigma _B} -\widetilde{D}_\beta \left( \rho _{AB}\Vert \mathbbm {1}_A\otimes \sigma _B\right) \),

and we are done. \(\square \)

6.1 Local randomness extraction

Randomness extraction aims to convert weak randomness into (almost) uniform random bits. If we hold some side information E about the random variable A, we want our output to be perfectly random even with respect to the side information. That is to say, we want it not only to be uniform but also uncorrelated from E.

Measuring a state is a source of weak randomness, and each possible measure gives us a different probability distribution of the outcomes. We would like to bind the amount of randomness that can be extracted from an arbitrary state \(\rho _A\) over all possible measurements. Even more, if we allow some side party E to hold side quantum correlations, we want our output to be uniform and independent from it. This means that the processing \(\mathcal {N}_{A\rightarrow X}\) of the overall state should result in \(\mathcal {N}_{A\rightarrow X}(\rho _{AE})=\frac{\mathbbm {1}_{X}}{|{X}|}\otimes \rho _E\). From this, it is quite clear that there must be a connection between this problem and decoupling.

We want to go beyond this single-user scenario and study multipartite randomness extraction. This has been developed in [26] in the i.i.d. asymptotic setting for \(k=2\). Here we consider a state \(\rho _{A_1\ldots A_k E}\) of k cooperating users \(A_i\) and an eavesdropper E. The objective of the \(A_i\) parties is to each make a destructive projective measurement \(\{\Pi _{x_i}^{(i)}\}_{x_i\in [t_i]}:A_i\rightarrow X_i\) so that all random variables \(X_i\) are jointly uniformly distributed and independent from E. We assume \(t_i\le |A_i|\) and identify the outcomes \(x_i\) with basis states \({|{x_i}\rangle }\) of a \(t_i\)-dimensional Hilbert space \(X_i\). After the application of the POVM, we want the output state \(\sigma _{X_{[k]} E}\) to satisfy

The trace distance

is called the error of the protocol.

In the base case \(k=1\), this problem has been comprehensively studied in [25], where it was shown that \(\log |X_1|\) can be as large as \(\log |A_1| + (H_{\min }^\epsilon (A_1|E)_\rho )_- + O(\log \epsilon )\) while the error is \(O(\epsilon )\), where \(\left( x\right) _- = \min \{0,x\}\) is defined as the negative part of the real number x; furthermore, it was shown that this is essentially optimal. Looking at a subset \(I\subseteq [k]\) of players and treating them as a single one, the optimality part of the result from [25] shows that a protocol of error \(\epsilon \) necessarily satisfies \(\sum _{i\in I} \log |X_i| \le \sum _{i\in I} \log |A_i| + (H_{\min }^\epsilon (A_I|E)_\rho )_-\) for all \(I\subseteq [k]\). We will show that this can essentially be achieved.

Theorem 6.6

Consider the randomness extraction setting above. If the \(t_i\) satisfy the following set of inequalities,

then there exists a one-shot local randomness extraction protocol with rates \(\log t_i\) and error \(\delta \le (3^k+2^{k-1})\epsilon \)

Corollary 6.7

Consider the i.i.d. asymptotics of the state \(\rho _{A_1\ldots A_k E}^{\otimes n}\). The optimal rate region of the randomness rates \(R_i=\frac{1}{n}\log t_i\) of bits per copy of the state in the limit of block length \(n\rightarrow \infty \) and error \(\delta \rightarrow 0\) is given by the set of inequalities

Proof

We prove here both Theorem 6.6 and Corollary 6.7. To achieve our goal, we let each party i perform a random unitary \(U_i\) on \(A_i\) followed by a qc-channel \(\mathcal {T}_i(\alpha ) = \sum _{x_i=1}^{t_i} {|{x_i}\rangle }\!{\langle {x_i}|} \text {Tr}\alpha P_{x_i}^{(i)}\) (which fulfills \(\widetilde{H}_2(A_i|X_i)_{\tau _i} \ge \log \frac{|A_i|}{t_i}\)), where \(P_{x_i}^{(i)}\) are the projectors corresponding to each \(x_i\in [t_i]\) possible outcome, therefore \(\mathbbm {1}_{A_i} = \sum _{x=1}^{t_i} P_x^{(i)}\). We impose an additional property on these projectors, they must have similar ranks. Actually, we do not let any pair of projectors differ in more than one unit in rank. This condition can be expressed as \(\left\lfloor \frac{|A_i|}{t_i}\right\rfloor \le {\text {rank}} P_x^{(i)} \le \Big \lceil \frac{|A_i|}{t_i}\Big \rceil \). For concreteness, let us sort them the greater first and the smaller after \({\text {rank}} P_x^{(i)} = \Big \lceil \frac{|A_i|}{t_i}\Big \rceil \) for \(x=1,\ldots ,|A_i|\!\mod t_i\) and \({\text {rank}} P_x^{(i)} = \left\lfloor \frac{|A_i|}{t_i}\right\rfloor \) for \(x=(|A_i|\!\mod t_i) + 1,\ldots ,t_i\).

Now we can invoke Theorem 3.2 with Corollary 3.4 (cf. Corollary 4.11), finding that there exist unitaries \(U_i\) on \(A_i\) (found with high probability by sampling from a 2-design) such that

satisfies

where we have chosen all \(\epsilon _I=\epsilon \) to be equal and bounded \(D_I\le 1\) in the first inequality, we have calculated \(\sum _{\emptyset \ne I\subseteq [k]} 2^{|I|}\epsilon =(3^k-1)\epsilon \le 3^k\epsilon \), and bounded the conditional entropies using the arguments discussed at the beginning of the section. Finally, we can bound \( \delta \le (3^k+2^{k-1})\epsilon \) if the following system of linear equations is satisfied:

Since all \(t_i\le |A_i|\), the above inequality is trivially true unless \(H_{\min }^\epsilon (A_I|E)_\rho \) is negative. So we might as well replace the min-entropy by its negative part \((H_{\min }^\epsilon (A_I|E)_\rho )_-\), resulting in the achievability of the region (6.1). Together with the outer bound derived from [25] this region is thus shown to be essentially optimal. This answers the question from [26] about a one-shot version of the basic protocol and achievable rates from that paper, for all \(k\ge 2\); and completes the proof of Theorem 6.6.

From this bound we also obtain easily a proof for Corollary 6.7. Namely, invoking the asymptotic equipartition property for the min-entropy (Theorem 6.1), a tuple of rates \(R_i=\frac{1}{n}\log t_i\ge 0\) is achievable as \(n\rightarrow \infty \) if and only if

which concludes the proof, since the necessity of these bounds has been argued before [26]. \(\square \)

This reproduces the core result of [26] for \(k=2\), albeit with a much simpler protocol than there, and proves the conjectured rate region for all numbers k of users.

To illustrate the benefit of being able to address each point in the achievable rate region directly, and via one-shot techniques, we consider the case that the i.i.d. source state is only partially known, i.e. it is \(\rho _{A_{[k]}E}^{\otimes n}\) with \(\rho \in \mathcal {S}\subset \mathcal {S}(A_1\ldots A_kE)\). The objective in this so-called compound source setting is to design a protocol that extracts randomness universally with the same figures of merit for all \(\rho ^{\otimes n}\), \(\rho \in \mathcal {S}\). The following theorem also demonstrates the power of the Rényi entropic decoupling Theorem 3.3.

Theorem 6.8

In the i.i.d. limit of \(n\rightarrow \infty \) and \(\delta \rightarrow 0\), the achievable region of the rates \(R_i = \frac{\log t_i}{n}\) for a compound source \(\left( \rho ^{\otimes n}: \rho \in \mathcal {S}\right) \), is given by

Proof

The optimality of the bounds follows from Corollary 6.7, since for a given subset \(I\subseteq [k]\) and any \(\rho \in \mathcal {S}\) the bound \(\sum _{i\in I} R_i \le \sum _{i\in I} \log |A_i| + (S(A_I|E)_\rho )_-\) applies. It remains to prove the achievability. To this end, for block length n, we choose an \(\frac{\eta }{n}\)-net \(\mathcal {S}_0 \subset \mathcal {S}\) to approximate elements of \(\mathcal {S}\) in trace norm. By adapting the proof of Lemma 6.2, we find \(N:= |\mathcal {S}_0| \le \left( \frac{5n}{\eta }\right) ^{2|A_{[k]}|^2|E|^2}\). We number the elements of the net, \(\mathcal {S}_0 = \{ \rho ^{(y)}: y=1,\ldots ,N \}\) and define the cq-state

The plan is to construct a protocol for this state, argue that hence it works well on each \(\rho _{A_{[k]}E}^{(y)\otimes n}\), and finally that it also works on every \(\rho ^{\otimes n}\), \(\rho \in \mathcal {S}\) by the net property. We could do this directly using Theorem 6.6, except that we would have to make the smoothing parameter \(\epsilon \) in the min-entropies dependent on n, which makes the argument awkward. Instead, we opt to use the Rényi decoupling from Theorem 3.3 (Corollary 3.4), following otherwise the proof of Theorem 6.6. This means that there, the error Equation (6.3) is modified to

where we have chosen all \(\alpha _I=\alpha >1\) equal. Now, the right-hand side of this bound is \(\le \delta \) if

for some \(\delta \ge 0\). However, we can lower-bound the conditional Rényi entropy here as follows:

where in the first line we have used Lemma 6.4 and the additivity of the conditional sandwiched Rényi entropy, in the second line that \(\mathcal {S}_0\subset \mathcal {S}\), and finally in the third the uniform convergence of \(\widetilde{H}_\alpha (A_I|E)\) to \(S(A_I|E)\) as functions on state space. To explain the latter, \(\widetilde{H}_\alpha (A_I|E)_\rho \rightarrow S(A_I|E)_\rho \) point-wise as \(\alpha \rightarrow 1\), and all \(\widetilde{H}_\alpha (A_I|E)\) and the limit \(S(A_I|E)\) are continuous, hence uniformly continuous, functions on the compact state space. This implies that there exists \(\Delta (\alpha )>0\) (converging to 0 as \(\alpha \rightarrow 1\)) such that for all I and all states \(\rho \), \(S(A_I|E)_\rho \ge \widetilde{H}_\alpha (A_I|E)_\rho \ge S(A_I|E)_\rho - \Delta (\alpha )\). With the rates \(nR_i=\log t_i\), this implies that if

then the right hand side of the bound (6.5) is \(\le \delta \). This means that the error of the same protocol on any one of the \(\rho ^{(y)\otimes n}\) is \(\le N\delta \). Hence, by applying the triangle inequality twice, on any \(\rho ^{\otimes n}\), \(\rho \in \mathcal {S}\), the error is \(\le N\delta +2\eta \). Letting \(\delta = \frac{\eta }{N}\), the error (\(\le 3\eta \)) can be made arbitrarily small, while the rates are bounded as

For \(n\rightarrow \infty \) and \(\alpha \rightarrow 1\), this proves the claim. \(\square \)

6.2 Multi-party entanglement of assistance and assisted distillation

Consider a pure state \(\psi _{ABC_1\ldots C_m}\) of two parties A and B who are helped by m other parties \(C_i\) with the aim to obtain approximately a maximally entangled state \(\Phi _d\) of Schmidt rank d by using arbitrary local operations and classical communication (LOCC). Namely, if the overall CPTP map implemented by the LOCC protocol is denoted \(\Lambda :ABC_1\ldots C_m \rightarrow A'B'\), with \(|A'|=|B'|=d\), we aim to find

where \({|{\Phi _d}\rangle }\) is the standard maximally entangled state of Schmidt rank d. The trace distance

is called the error of the protocol.

It is worth pausing for the simplest case, \(m=0\), so that \(\psi _{AB}\) is already a pure state between A and B. Then the objective is merely to concentrate the entanglement by LOCC into maximal entanglement, and we find the essentially optimal \(\log d \ge H_{\min }^\delta (\psi _A)\) [47]. For \(m>0\), consider any bipartition of the helpers by choosing a subset \(I\subseteq [m]\) and its complement \(I^c=[m]\setminus I\), and simulate any \((m+2)\)-party LOCC protocol by a bipartite LOCC protocol between the systems \(AC_I\) and \(BC_{I^c}\). Thus, from the preceding entanglement concentration considerations, we get the upper bound

We can show that this bound is essentially achievable, up to an additive offset depending only on \(\delta \) and m, and a technical condition.

Theorem 6.9

Given the setting above, multi-party entanglement of assistance has an achievable rate \(\log d\) with error \(\delta \le 4\cdot 3^{m/2}\sqrt{\epsilon }\) if

Corollary 6.10

In the i.i.d. limit of \(n\rightarrow \infty \), the maximum asymptotic entanglement rate \(R=\frac{1}{n}\log d\) from \(\psi ^{\otimes n}\) is

where \(S(\rho )\) is the von Neumann entropy of the state \(\rho \).

Proof

We prove both Theorem 6.9 and Corollary 6.10. To start with the former, our strategy will consist in making a local random complete basis measurement onto each \(C_i\), and a random projective measurement of rank-d projectors onto A; after that, B will only have to perform a unitary. Let us fix orthonormal computational bases \(\left\{ {|{j^{(i)}}\rangle }\right\} \) for each \(C_i\) with \(i=1,\ldots ,m\) and define a complete measurement in these bases as \(\mathcal {T}_i(\gamma ):= \sum _{j^{(i)}=1}^{|C_i|} {|{j^{(i)}}\rangle }\!{\langle {j^{(i)}}|} \gamma {|{j^{(i)}}\rangle }\!{\langle {j^{(i)}}|}\). We also fix rank-d projectors \(P_{j^{(0)}}\) (we may assume w.l.o.g. that d divides the dimension |A| by trivially enlarging A if necessary), then \(\mathcal {T}_0(\alpha ) = \sum _{j^{(0)}=1}^{|A|/d} P_{j^{(0)}} \alpha P_{j^{(0)}}\) is defined as the projective measurement of rank d on A. Using that the Rényi entropies of the Choi states are \(\widetilde{H}_2(C_i'|C_i)_{\tau _i} = 0\) (\(\forall i\in [m]\)) and \(\widetilde{H}_2(A'|A)_{\tau _0} = - \log d\) [24], Theorem 3.2 with Corollary 3.4 shows that there exist unitaries \(U_0\) on A and \(U_i\) on \(C_i\) (\(i\in [m]\)), found with high probability by sampling from a 2-design, such that

satisfies

choosing all \(\epsilon _I=\epsilon \) equal. The right hand side of this last bound is \(\le \eta := (3^{m+1}+2^m)\epsilon \) if the following conditions are satisfied:

Let \({j} = j^{(0)}j^{(1)}\ldots j^{(m)}\) be a set of possible measurement outcomes corresponding to the general POVM element \(\Lambda _{{j}}=P_{j^{(0)}}\otimes {|{j^{(1)}}\rangle }\!{\langle {j^{(1)}}|}\otimes \cdots \otimes {|{j^{(m)}}\rangle }\!{\langle {j^{(m)}}|}\). The probability of getting this specific outcomes when measuring \(\sigma _{AC_1\ldots C_m}\) is

and the probability of obtaining the outcomes \({j}\) after measuring the maximally mixed is given by

We can bound the total variational distance between the two probability distributions using Lemma 4.6:

As \(\sigma _{AC_{[m]}}\) and the maximally mixed state in the above trace distance are both direct sums over operators in the orthogonal subspaces given by the support of \(\Lambda _{{j}}\), we can rewrite the trace distance in question as

Using the triangle inequality \(\Vert \rho -\sigma \Vert _1\le \Vert \rho -\tau \Vert _1+\Vert \tau -\sigma \Vert _1\) and the bound on the total variation distance between p and \(p'\) we can thus obtain

Let us now introduce the unit vectors

so that we can define \(\eta ({j}) = \frac{1}{2}\left\| \text {Tr}_B \psi ({j})_{AB} - \frac{P_{j^{(0)}}}{d} \right\| _1\), such that \(\sum _{{j}} p({j})\eta ({j}) \le 2\eta \). We have a purification \(\psi ({j})_{AB}\), then by Uhlmann’s Theorem 4.7, there must exist a purification \(\phi \) of the projector \(\frac{P_j^{(0)}}{d}\) such that the purified distance is conserved. This is a maximally mixed state on its support, therefore any purification will be a maximally entangled state of rank d (the dimension of the support) that we can write as \({|{\Phi _d({j})}\rangle }_{AB} = \left( U({j})\otimes V({j})\right) {|{\Phi _d}\rangle }_{A'B'}\), where \(U({j})\) and \(V({j})\) are some isometries applied to the canonical maximally mixed state \({|{\Phi _d}\rangle }_{A'B'}\). Now, applying the Fuchs-van de Graaf inequalities (2.2), we find

With these elements and facts, we can finally describe the LOCC protocol to concentrate the entanglement in the hands of Alice and Bob: parties A and the \(C_i\) apply the local unitaries \(U_0\) and \(U_i\), followed by the projective measurements \((P_{j^{(0)}})\) and \(\left( {|{j^{(i)}}\rangle }\!{\langle {j^{(i)}}|}\right) \), respectively (in the case of the \(C_i\) they are destructive). The measurement outcomes are broadcast to A and B who apply the (partial) isometries \(U({j})^\dagger \) and \(V({j})^\dagger \), respectively (see Fig. 3). By the triangle inequality and the concavity of the square root, the resulting CPTP map \(\Lambda :ABC_1\ldots C_m \rightarrow A'B'\) satisfies

The achieved one-shot rate (Fig. 4), always assuming that the second condition in (6.9) is fulfilled, is therefore \(\log d \ge \min _{I\subseteq [m]} H_{\min }^\epsilon (AC_I)_\psi + 2\log \epsilon \). This concludes the proof of the theorem.

Diagram of the LOCC protocol that maximally concentrates the entanglement of an initial state \(\psi _{ABC_1\dots C_m}\) onto Alice’s and Bob’s subspaces of dimension \(|A'|=|B'|=d\)

Full size image

To prove the corollary, referring to the i.i.d. asymptotic limit of \(n\rightarrow \infty \) copies of \(\psi _{ABC_1\ldots C_m}\) and vanishing error \(\delta \rightarrow 0\), the AEP applies. This means that \(H_{\min }^\epsilon (A^nC_I^n)_{\psi ^{\otimes n}} \sim n S(\psi _{AC_I})\) and \(H_{\min }^\epsilon (C_I^n)_{\psi ^{\otimes n}} \sim n S(\psi _{C_I})\). By the above comment, we may assume w.l.o.g. that all these von Neumann entropies are positive; for otherwise if some \(S(\psi _{C_I})=0\) we can discard the corresponding parties, or if \(S(\psi _{AC_I})=0\) then A and B are not entangled and there is nothing to distill by LOCC. In the positive case, all exponential terms in the sum for \(\eta \) can be made exponentially or just sub-exponentially small in n, and defining the asymptotic rate via \(\log d = nR\), we achieve its optimal value \(R = \min _{I\subseteq [m]} S(\psi _{AC_I})\). For the optimality, the necessity of the inequalities \(R\le S(AC_I)\) can be argued by noting that any LOCC protocol between the \(m+2\) parties is at the same time an LOCC protocol for the bipartition \(AC_I:BC_{[m]\setminus I}\), and the optimal rate for bipartite entanglement concentration is the reduced state entropy [48]. \(\square \)

Corollary 6.10 is the result from [17], proved there by a much more complicated, iterative protocol that relied on the tensor product structure of \(\psi ^{\otimes n}\). The present procedure was previously analyzed by Dutil [9, Ch. 5] and shown to work assuming the simultaneous smoothing conjecture in the i.i.d. case. Here finally we achieve the same without any unproven conjectures. Note that in particular, no time sharing between different protocols is necessary.

The first of the conditions (6.6) is essentially necessary, making the achieved rate essentially optimal. The second condition looks like a technical artifact of the proof since we require that all the local measurement outcomes of the helpers \(C_i\) are close to being uniformly distributed. However, this is not necessary for the objective of entanglement of assistance, but at the same time it becomes difficult to achieve by random basis measurements if some reduced state \(\psi _{C_I}\) has rather small min-entropy. We can see that this is benign when \(\psi _{C_I}\) is actually pure, as then our state factorizes, \(\psi _{ABC_1\ldots C_m} = \psi _{ABC_{I^c}} \otimes \psi _{C_I}\), and we can simply leave the parties \(C_I\) out of the LOCC protocol without any loss. We have to leave the general case as an open question. In any case, we can observe that by providing a small amount of EPR states between any pair of players (in fact, the pairs B and \(C_j\) are sufficient), we can always ensure that the entropies \(H_{\min }^\epsilon (C_I)\) are sufficiently lower bounded.

Remark 6.11

Generalising [49], Cheng et al. [50] have considered a model of random multipartite pure state defined by starting with a multipartite pure states on a larger number or systems (original and auxiliary ones) and subjecting the auxiliary systems to local random measurements. This is more general than our objective of obtaining bipartite maximal entanglement, but in the bulk of the paper [50] also more specific because there, the main interest is in initial states given by network of partially entangled bipartite pure states. Interestingly, to describe the resulting random states, the authors of [50] manage to resolve the simultaneous smoothing in that special case. In the case of an arbitrary state, however, perhaps our current approach can help to gain insights into the high-probability properties of the resulting random states.

Looking at the proof of Theorem 6.9, we see that the attainability is essentially the same for an initial mixed state, as in the following theorem.

Theorem 6.12

Given a mixed state \(\rho _{ABC_1\ldots C_m} = \text {Tr}_E {|{\psi }\rangle }\!{\langle {\psi }|}_{ABC_1\ldots C_mE}\) in the above setting, multi-party assisted distillable entanglement has an achievable rate \(\log d\) with error \(\delta \le 4\cdot 3^{m/2}\sqrt{\epsilon }\) if

Proof

We trace the proof of Theorem 6.9, indicating only the necessary changes. To start, we use the same random unitaries \(U_j\) followed by the same \(\mathcal {T}_j\). Then Equation (6.8) is replaced by

with respect to the purification \(\psi \) of \(\rho \) on the right hand side and for

Then, if the conditions (6.11) are satisfied, the right hand side of Equation (6.12) becomes \(\le \left( 2^m+3^{m+1}\right) \epsilon =: \eta \), and we can continue as before until Equation (6.10), which is replaced by

The rest of the proof is almost unchanged, except that the purification \({|{\phi }\rangle }_{\widetilde{E}E}\) of \(\psi _E\) comes in: with

we have \(\eta ({j}) = \frac{1}{2}\left\| \text {Tr}_B \psi ({j})_{ABE} - \frac{P_{j^{(0)}}}{d}\otimes \psi _E \right\| _1\), such that \(\sum _{{j}} p({j})\eta ({j}) \le 2\eta \). Once again, through Uhlmann’s theorem, gives us isometries \(U({j}):A'\hookrightarrow A\) and \(V({j}):B'\widetilde{E} \hookrightarrow B\) such that

and the proof concludes exactly as before. Finally note that \(H_{\min }^\epsilon (AC_I|E) = -H_{\max }^\epsilon (AC_I|BC_{I^c})\) by the duality relation between min- and max-entropies (cf. [41]). \(\square \)

Unlike the pure-state case we do not have any clear statement of optimality of the rate achieved in this theorem. In fact, due to properties of the coherent information one should optimise the expressions in (6.11) over preprocessing channels \(\mathcal {T}_j:C_j\rightarrow C_j'\) (\(j=1,\ldots ,m\)) and \(cT_0:A\rightarrow A'\), and also consider swapping the roles of A and B. Even then, we are limited by the specific protocol we are considering (rather than a general LOCC procedure); furthermore, in the i.i.d. asymptotic limit regularisation might be required. Nevertheless we can state the following result.

Corollary 6.13

(Cf. Dutil [9, Thm. 5.4.4]) Given asymptotically many copies of a state \(\rho _{ABC_{[m]}}\) (\(n\gg 1\)) and o(n) EPR states between any pair of players, the following rate is achievable for EPR distillation between A and B by LOCC assisted by the players \(C_j\):

where the supremum is over channels \(\mathcal {T}_j:C_j\rightarrow C_j'\) (\(j=1,\ldots ,m\)) and \(\mathcal {T}_0:A\rightarrow A'\), and

\(\square \)

To demonstrate a case where the one-shot result are relevant, we consider the problem of i.i.d. entanglement of assistance when the source is only partially known, meaning \(\psi \in \mathcal {S}\subseteq \mathcal {S}(ABC_{[m]})\), and we would like to design protocols as above for every n that are universal for all \({|{\psi }\rangle }^{\otimes n}\in A^nB^nC_{[m]}^n\) with \(\psi \in \mathcal {S}\) (i.e. a compound source).

Theorem 6.14

In the i.i.d. limit of \(n\rightarrow \infty \) and error \(\delta \rightarrow 0\), the maximum entanglement rate \(R=\frac{1}{n}\log d\) for a compound source \((\psi ^{\otimes n}:\psi \in \mathcal {S})\), when o(n) EPR states are available for free between any pair or players, is

Proof

Even when the state \(\psi ^{\otimes }\) is fixed and known, Corollary 6.10 upper-bounds the rate by \(\min _{I\subseteq [m]} S(AC_I)_\psi \), hence the infimum of this quantity over \(\psi \in \mathcal {S}\) provides an upper bound on the optimal rate R.

Regarding the achievability, for block length n choose an \(\frac{\eta }{n}\)-net \(\mathcal {S}_0\subset \mathcal {S}\) of states for \(\mathcal {S}\) (i.e. a net to approximate elements of \(\mathcal {S}\)). By adapting the proof of Lemma 6.2, we find that \(N:= |\mathcal {S}_0| \le \left( \frac{5n}{\eta }\right) ^{2|A||B||C_{[m]}|}\). We number the elements of the net, \(\mathcal {S}_0 = \{\rho _s: s=1,\ldots ,N\}\). The plan is to construct a one-shot assisted entanglement distillation protocol for the averaged state plus sublinear entanglement,

where \(\Phi _{b_jc_j}\) is a maximally entangled state between systems \(b_j\) (with Bob) and \(c_j\) (with helper j) of dimensions \(|b_j|=|c_j|=d_0\), \(\log d_0=o(n)\), \(\widetilde{A}=A^n\), \(\widetilde{B}=B^nb_{[m]}\) and \(\widetilde{C}_j=C_j^nc_j\). Then to argue that the protocol performs well on all \(\psi _s^{\otimes n}\) (plus the sublinear entanglement), and finally that it must perform well on all \(\psi ^{\otimes n}\) with \(\psi \in \mathcal {S}\), we could do this directly using Theorem 6.12, except that for that to work we have to make the smoothing parameter \(\epsilon \) in the min-entropies dependent on n, which makes the argument awkward. Instead, we opt to use the Rényi decoupling from Theorem 3.3 (Corollary 3.4), following otherwise the proof of Theorem 6.12. This means that there, Equation (6.12) is replaced by

with respect to the purification \(\widetilde{\psi }\) of \(\widetilde{\rho }\) and for

with the maps \(\mathcal {U}_0\) and \(\mathcal {T}_0\) acting on \(A^n\), and \(\mathcal {U}_j\) and \(\mathcal {T}_j\) acting on \(\widetilde{C}_j\).

We upper-bound the right hand side of Equation (6.16) as follows: with \(\frac{1}{\alpha }+\frac{1}{\beta } = 2\),

and similarly,

in both chains of inequalities using Lemmas 6.3 (for the equalities) and 6.5 (for the inequalities in the fourth line) and the additivity of the conditional Rényi entropy, and in the second chain additionally that \(I\ne \emptyset \).

Thus, with the rate \(nR = \log d\), the right hand side of the bound (6.16) is \(\le \delta \) if

Since \(\widetilde{H}_\alpha (AC_I)_{\rho }\) converges to \(S(AC_I)_{\rho }\) as \(\alpha \rightarrow 1\), and the converging as well as the limit functions are continuous on the compact set of all states, hence uniformly continuous, also the convergence \(\widetilde{H}_\alpha (AC_I) \rightarrow S(AC_I)\) of the functions on state space is uniform. Thus, there exists a \(\Delta (\alpha )>0\) (converging to 0 as \(\alpha \rightarrow 1\)) such that for all \(I\subseteq [m]\),

And so the trace norm in Equation (6.16) is guaranteed to be \(\le \delta \) if

Continuing the reasoning of the proof of Theorem 6.12, we obtain an assisted distillation protocol for \(\widetilde{\rho }\) that has error \(\le 2\sqrt{\delta }\), hence it has error \(\le 2N\sqrt{\delta }\) on each of the \(\psi _s^{\otimes n}\), and so finally it has error \(\le 2N\sqrt{\delta }+\eta \) on each source \(\psi ^{\otimes n}\) such that \(\psi \in \mathcal {S}\). Choosing \(\delta =\frac{\eta }{N^2}\) and \(\log d_0 = \frac{3\alpha }{\alpha -1}(\log N - \log \eta +m+1)\), we get an error guarantee of \(\le 3\eta \) across the set \(\mathcal {S}\), while the rate achieved is

which for \(n\rightarrow \infty \) and \(\alpha \rightarrow 1\) proves the claim. \(\square \)

6.3 Multi-party quantum Slepian-Wolf coding: state merging

In terms of decoupling strategy and objectives, this task could be considered a generalisation of the previous, entanglement of assistance, except that we are interested in both entanglement yield and entanglement consumption and their net difference. Namely, the setting is described by a pure state \(\psi _{A_1\ldots A_kBR}\) of \(k+2\) parties, k senders (Alice-i) holding \(A_i\), one receiver (Bob) holding B and a reference system R, whose only role is to hold the purification. Additionally the parties share maximally entangled states \(\Phi _{A_i'B_i'}\) between Alice-i and Bob of Schmidt rank \(c_i\), so that the overall initial state is

A one-way LOCC state merging protocol consists first of k compression (encoding) instruments \(\left( \mathcal {E}_i^{(x)}:A_iA_i' \rightarrow A_i'': x\in [\ell _i]\right) \), with the individual maps acting as \(\mathcal {E}_i^{(x)}(\alpha ) = V_i^{(x)\dagger } \alpha V_i^{(x)}\). Here, the \(V_i^{(x)}:A_i''\rightarrow A_iA_i'\) are isometries, i.e. \(V_i^{(x)\dagger }V_i^{(x)}=\mathbbm {1}_{A_i''}\), such that the projectors \(\Pi _i^{(x)} = V_i^{(x)}V_i^{(x)\dagger }\) form a projective measurement, i.e. \(\sum _{x=1}^{\ell _i} \Pi _i^{(x)} = \mathbbm {1}_{A_iA_i'}\). We denote \(|A_i''|=d_i\), \(|X_i|=\ell _i\), hence \(|A_i|c_i=d_i\ell _i\), which might necessitate to increase \(A_i\) by isometric embedding. Secondly, of a collection of decompression (decoding) CPTP maps \(\mathcal {D}^{(x_{[k]})}:BB_1'\ldots B_k' \rightarrow \widehat{A}_1\ldots \widehat{A}_k\widehat{B}B_1''\ldots B_k''\), one for each tuple \(x_{[k]}=x_1\ldots x_k\) of outcomes (where \(\hat{A}_i\cong A_i\) and \(\hat{B}\cong B\)). The idea is that Alice-i performs the instrument \(\mathcal {E}_i\), obtaining outcome \(x_i\) which is communicated to Bob, who collects the outcome tuple \(x_{[k]}\) and applies \(\mathcal {D}^{x_{[k]}}\). The result is a one-way LOCC operation \(\Lambda :A_1\ldots A_k A_1'\ldots A_k' BB_1'\ldots B_k' \rightarrow \widehat{A}_1\ldots \widehat{A}_k\widehat{B} A_1''\ldots A_k'' B_1''\ldots B_k''\) that can be written as

The objective is that at the end, after application of \(\Lambda \), the Alices and Bob share approximately the state \(\psi _{\widehat{A}_1\ldots \widehat{A}_k\widehat{B}R} \otimes (\Phi _{d_1})_{A_1'B_1'} \otimes \cdots \otimes (\Phi _{d_k})_{A_k'B_k'}\), where now \(\widehat{A}_1\ldots \widehat{A}_k\widehat{B}\) are held by Bob, and Alice-i shares with Bob maximally entangled state of Schmidt rank \(d_i\):

The trace distance

is called the error of the protocol.

Let us define the numbers \(r_i:= \log c_i - \log d_i\) as the net one-shot rates of entanglement cost for Alice-i, and the task is to characterize the possible tuples of these rates with corresponding state merging protocols. This problem has been introduced and solved in [16, 17] in the asymptotic setting of both single and multiple senders, and in [20] in the one-shot setting of a single sender. Dutil [9] has investigated the case of multiple senders in the one-shot setting as well as in the i.i.d. asymptotics, and made the connection to the question of simultaneous smoothing of collision entropies and min-entropies [51].

Theorem 6.15

Given the setting above, quantum state merging can be achieved with error \(\eta \le 4\cdot 3^{k/2}\sqrt{\epsilon }\) if

with the above net one-shot rates of entanglement consumption \(r_i=\log c_i-\log d_i\).

One-shot achievable rate region of a two-senders quantum Slepian-Wolf coding. Notice that the region is open towards the northeast

Full size image

Corollary 6.16

In the i.i.d. limit of \(n\rightarrow \infty \), the region of achievable rates \(R_i=\frac{1}{n} r_i\) for successful quantum state merging of \(\psi ^{\otimes n}\) is given precisely by

Proof

To describe our protocol, we fix unitaries \(V_i:A_iA_i'\rightarrow X_iA_i''\) and then can write the instrument as a CPTP map \(\mathcal {T}_i(\alpha ) = \sum _{x=1}^{\ell _i} ({|{x}\rangle }\!{\langle {x}|}\otimes \mathbbm {1}_{A_i''})V_i\alpha V_i^\dagger ({|{x}\rangle }\!{\langle {x}|}\otimes \mathbbm {1}_{A_i''})\). Its Choi state \(\tau ^{(i)}_{A_iA_i':X_iA_i''}\) has conditional Rényi entropy \(\widetilde{H}_2(A_iA_i'|X_iA_i'')_{\tau ^{(i)}} = -\log d_i\) [24]. We can thus apply Theorem 3.2 with Corollary 3.4, which tell us that there exist local unitaries \(U_i\) on \(A_i\) such that

satisfies

choosing all \(\epsilon _I=\epsilon \) equal. The right hand side of this bound is \(\le \delta := (3^k+2^{k-1})\epsilon \) if Equation (6.17) is fulfilled. In that case, the total variational distance between \(p(x_{[k]})\) and the uniform distribution on \(X^k\) is upper bounded by \(\delta \), too, and so by the triangle inequality we get

Notice that \(\sigma ^{(x_{[k]})}_{A_{[k]}''R} = \text {Tr}_B {|{\psi ^{(x_{[k]})}}\rangle }\!{\langle {\psi ^{(x_{[k]})}}|}_{A_{[k]}''BB_{[k]}'R}\), with

while

Then, just as before, we can conclude using Uhlmann’s Theorem 4.7 and the Fuchs-van de Graaf inequalities (2.2), that for each \(x_{[k]}\) there exists an isometry \(W^{(x_{[k]})}:BB_{[k]}' \rightarrow \widehat{A}_{[k]}\widehat{B}B_{[k]}''\) such that

This means that defining \(\mathcal {E}^{(x_i)}(\alpha ) = {\langle {x_i}|} V_iU_i\alpha U_i^\dagger V_i^\dagger {|{x_i}\rangle }\) and \(\mathcal {D}^{(x_{k})}(\beta ) = W^{(x_{[k]})}\beta W^{(x_{[k]})\dagger }\) as the encoding and decoding maps, this will satisfy the requirement for state merging with error

With the one-shot achievability in hand, we can now once again use the AEP Theorem 6.1 for the min-entropy to get the optimal rate region for the i.i.d. asymptotics of a source \(\psi ^{\otimes n}\) as \(n\rightarrow \infty \) and \(\delta \rightarrow 0\). Namely, rates \(R_i\), defined as the limits of \(\frac{r_i}{n}\), are achievable if and only if for all \(I\subseteq [k]\), \(\sum _{i\in I} R_i \ge S(A_I|A_{I^c}B)_\psi \). This completes the proof of Theorem 6.15 and Corollary 6.16, since the converse (necessity of the asymptotic inequalities) was argued in [17]. \(\square \)

To be sure, the achievability of (6.18) was shown in [17], already, by finding the extreme points of the region and noting that they can be solved by iteration of the single-sender merging protocol, and then time-sharing (convex hull) for the remaining region. The present protocol (removing the need for time-sharing) was first proposed in the multiple-sender setting by Dutil and Hayden [51], where however the proof of its functioning is incomplete. In Dutil’s PhD thesis [9, Ch. 4], the role of simultaneous smoothing is fully analysed. Indeed, a decoupling bound of the form (6.19) was conjectured there [9, Conj. 4.1.3], and the simultaneous smoothing problem was highlighted. It could be solved only in the i.i.d. asymptotics of \(k=2\) senders.

To demonstrate a case where the direct attainability of points in the above rate region, and also the one-shot result are relevant, we consider the problem of i.i.d. state merging for a compound source, i.e. the source is only partially known, meaning \(\rho = \text {Tr}_R \psi \in \mathcal {S}\subseteq \mathcal {S}(A_{[k]}B)\), and we would like to design protocols as above for every n that are universal for all \({|{\psi }\rangle }^{\otimes n}\in A_{[k]}^nB^nR^n\) with \(\text {Tr}_R\psi \in \mathcal {S}\).

Theorem 6.17

In the i.i.d. limit of \(n\rightarrow \infty \), the region of achievable rates \(R_i=\frac{1}{n} r_i\) for a compound source \(\left( \psi ^{\otimes n}:\text {Tr}_R\psi \in \mathcal {S}\right) \) is given by

Proof

Even when the source \(\rho \in \mathcal {S}\) is fixed, necessarily \(\sum _{i\in I} R_i \ge S(A_I|A_{I^c}B)_\rho \) [17], thus \(\sum _{i\in I} R_i \ge \sup _{\rho \in \mathcal {S}} S(A_I|A_{I^c}B)_\rho \) for all subsets I. This takes care of the converse bound in Equation (6.20), and it remains to prove the achievability.

To this end, for block length n we choose an \(\frac{\eta }{n}\)-net \(\mathcal {S}_0 \subset \mathcal {S}\) of states for \(\mathcal {S}\) (i.e. a net to approximate elements of \(\mathcal {S}\)). By adapting the proof of Lemma 6.2, we find that \(N:= |\mathcal {S}_0| \le \left( \frac{5n}{\eta }\right) ^{2|A_{[k]}|^2|B|^2}\). We number the elements of the net, \(\mathcal {S}_0 = \{\rho _s: s=1,\ldots ,N\}\) and choose purifications \({|{\psi }\rangle }_s \in A_{[k]}BR\) of \(\rho _s\). As previously deployed, the plan is to construct a one-shot protocol for the averaged source

then argue that the protocol performs well on all \(\psi _s^{\otimes n}\), and finally that it must perform well on all \(\psi ^{\otimes n}\) with \(\text {Tr}_R \psi \in \mathcal {S}\). We could do this directly using Theorem 6.15, except that for that to work we have to make the smoothing parameter \(\epsilon \) in the min-entropies dependent on n, which makes the argument awkward. Instead, we opt to use the Rényi decoupling from Theorem 3.3 (Corollary 3.4), following otherwise the proof of Theorem 6.15. This means that there, Equation (6.19) is replaced by

choosing all \(\alpha _I=\alpha \in (1,2]\) equal. With the net rates \(nR_i = \log c_i - \log d_i\), the right hand side of the last bound is \(\le \delta \) if

where we have used the Rényi entropy duality (Lemma 6.3) with \(\frac{1}{\beta }+\frac{1}{\alpha }=2\). In fact, we can simplify this condition using Lemma 6.5 which tells us

Thus, the trace norm in Equation (6.21) is \(\le \delta \) if

Since \(\widetilde{H}_\beta (A_I|A_{I^c}B)_{\rho }\) converges to \(S(A_I|A_{I^c}B)_{\rho }\) as \(\beta \rightarrow 1\), and the converging as well as the limit functions are continuous on the compact set of all states, hence uniformly continuous, also the convergence \(\widetilde{H}_\beta (A_I|A_{I^c}B) \rightarrow S(A_I|A_{I^c}B)\) of the functions on state space is uniform. Thus, there exists a \(\Delta (\beta )>0\) (converging to 0 as \(\beta \rightarrow 1\)) such that for all \(I\subseteq [k]\),

And so the trace norm in Equation (6.21) is guaranteed to be \(\le \delta \) if

Continuing the reasoning of the proof of Theorem 6.15, we obtain a merging protocol for \(\widetilde{\psi }\) that has error \(\le 2\sqrt{\delta }\), hence it has error \(\le 2N\sqrt{\delta }\) on each of the \(\psi _s^{\otimes n}\), and so finally error \(\le 2N\sqrt{\delta }+2\eta \) on each of source \(\psi ^{\otimes n}\) such that \(\text {Tr}_R\psi \in \mathcal {S}\). Choosing \(\delta =\frac{\eta ^2}{N^2}\) we get an error guarantee of \(\le 4\eta \) across the set \(\mathcal {S}\), while the rates are bounded

which for \(n\rightarrow \infty \) and \(\beta \rightarrow 1\) proves the claim. \(\square \)

6.4 Quantum communication via quantum multiple access channels

A quantum multiple access channel is a CPTP map \(\mathcal {N}:A_1\ldots A_k \rightarrow B\) from k senders \(A_i\) to a single receiver B. For later use, let us introduce the Stinespring dilation \(\mathcal {N}(\rho ) = \text {Tr}_E V \rho V^\dagger \), with \(V:A_1\ldots A_k \rightarrow BE\) an isometry. Let each user i hold independent quantum messages (quantum systems) \(M_i\) of dimension \(s_i=|M_i|\). Then, a code for such a channel consists of a set of encoding CPTP maps \(\mathcal {E}_i:M'_i\rightarrow A'_i\) and a single decoding CPTP map \(\mathcal {D}:B\rightarrow \widehat{M}_1\ldots \widehat{M}_k\) where \(\widehat{M}_i \simeq M_i\). And the numbers \(\log s_i\) are the one-shot rates. In this setting, we say that the code has error \(\delta \) if

where \(\Phi _{M_i'M_i}\) and \(\Phi _{\widehat{M}_i M_i}\) are standard maximally entangled states of Schmidt rank \(s_i\). The problem here is now to characterize, for a given error \(\delta \), the set of achievable one-shot rate tuples \((\log s_1, \ldots , \log s_k)\). Likewise, in the i.i.d. asymptotic limit \(\mathcal {N}^{\otimes n}\), when \(n\rightarrow \infty \) and \(\delta \rightarrow 0\), we introduce the asymptotic rates \(R_i = \frac{1}{n} \log s_i\) and ask for a description of the achievable rate tuples \((R_1,\ldots ,R_k)\). By general principles this is a convex corner, i.e. a closed convex set in the positive orthant, containing the origin and stable under reducing any coordinate towards 0. See Fig. 5 for the one-shot tripartite rate region and Fig. 6 for the i.i.d. bipartite rate region.

Theorem 6.18

Given the quantum MAC \(\mathcal {N}:A_{[k]} \rightarrow B\) and its Stinespring isometry \(V:A_{[k]} \rightarrow BE\), as well as pure states \(\varphi ^{(i)}_{A_iA_i'}\) with \(A_i' \simeq A_i\) (\(i\in [k]\)), define

where we let V act on \(A_{[k]}'\). Then there exists a code for the channel with error \(\delta \le (k+1)2^{k+1}\sqrt{\epsilon }\) if the one-shot rate tuples satisfy

One-shot achievable rate region for a MAC with three senders \(A_1\), \(A_2\) and \(A_3\)

Full size image

Corollary 6.19

In the i.i.d. asymptotic limit \(n\rightarrow \infty \) and \(\delta \rightarrow 0\), the rates \(R_i=\frac{1}{n}\log s_i\) are achievable for transmission over \(\mathcal {N}^{\otimes n}\) if

where \(I(A_I\rangle BA_{I^c})_\psi = - S(A_I|BA_{I^c})_\psi \) is the coherent information. More generally, for an ensemble \(\{q(u),{|{\psi _u}\rangle }\}\) of states as in Equation (6.23), \(u\in \mathcal {U}\) ranging over a discrete alphabet, the rates \(R_i\) are achievable if

the latter coherent information evaluated on the cq-state \(\overline{\psi } = \sum _u q(u){|{u}\rangle }\!{\langle {u}|}_U \otimes \psi _u\).

Proof

We prove both Theorem 6.18 and Corollary 6.19. To describe good codes, fix projective measurements \((P_{j^{(i)}})\) on \(A_i\), where each of the \(P_{j^{(i)}}\) has rank \(s_i\) (by enlarging \(A_i\) if necessary, we may assume w.l.o.g. that \(s_i\) divides the dimension \(|A_i|\)), and let the corresponding CPTP map be \(\mathcal {T}_i(\alpha ) = \sum _{j^{(i)}=1}^{|A_i|/s_i} P_{j^{(i)}} \alpha P_{j^{(i)}}\). Its Choi state \(\tau ^{(i)}_{A_i'A_i}\) has conditional Rényi entropy \(\widetilde{H}_2(A_i'|A_i)_{\tau ^{(i)}} = -\log s_i\) [24]. We can thus apply Theorem 3.2 with Corollary 3.4 that tell us that there exist local unitaries \(U_i\) on \(A_i\) such that

satisfies

choosing all \(\epsilon _I=\epsilon \) equal, the right-hand side is \(\le \eta := (3^k+2^{k-1})\epsilon \) if Equation (6.24) is fulfilled. In that case, there must exist measurement outcomes \(j^{(i)}\) for the POVM on \(A_i\) such that, with the outcome probability \(p({j}) = \text {Tr}(U_1\otimes \cdots \otimes U_k)\psi _{A_1\ldots A_k}(U_1\otimes \cdots \otimes U_k)^\dagger \left( P_{j^{(1)}}\otimes \cdots \otimes P_{j^{(k)}}\right) \):

Unpacking the definition of \(\psi \), this means that for each i there are unit vectors of Schmidt rank \(s_i\), \({|{\widetilde{\varphi }^{(i)}}\rangle }_{A_i'A_i} \propto (P_{j^{(i)}}U_i\otimes \mathbbm {1}){|{\varphi ^{(i)}}\rangle }\), such that for all \({j}\)

The previous trace norm estimate shows that each of the \(\widetilde{\varphi }^{(i)}_{A_i}\) is nearly maximally mixed on its support \(M_i\), up to trace distance \(\le 2\eta \). So using Uhlmann’s theorem 4.7 and the inequalities (2.2) once again we conclude that there must exist maximally entangled states \(\Phi _{M_i'M_i}\) of Schmidt rank \(s_i\) and isometries \(W_i: M_i' \rightarrow A_i'\), such that \(P\left( (W_i\otimes \mathbbm {1}_{M_i})\Phi _{M_i'M_i}(W_i\otimes \mathbbm {1}_{M_i})^\dagger , \widetilde{\varphi }^{(i)} \right) \le 2\sqrt{\eta }\). Putting these last bounds together, using the triangle inequality for the purified distance and its non-increase under CPTP maps, we get

As the second argument in the purified distance has purification \(\Phi _{\widehat{M_1}}\otimes \cdots \otimes \Phi _{\widehat{M_k}M_k}\otimes \psi _{A_{[k]}BE}\), by Uhlmann’s theorem there exists an isometry \(\widehat{W}:B\rightarrow \widehat{M}_1\otimes \cdots \otimes \widehat{M}_k\otimes A_{[k]}B\) such that

In other words, defining the encoders \(\mathcal {E}_i(\alpha ) = W_i\alpha W_i^\dagger \) and the decoder as \(\mathcal {D}(\beta ) = \text {Tr}_{A_{[k]}B} \widehat{W}\beta \widehat{W}^\dagger \), yields a code for the quantum MAC with one-shot rates \(s_i\) [subject to the conditions (6.24)] and error \(\delta = 2(k+1)\sqrt{\eta } \le (k+1)2^{k+1}\sqrt{\epsilon }\). This form of a one-shot achievability region had been conjectured for a long time, with the best previous result reported by Chakraborty, Nema, and Sen [40, 52], who used rate-splitting and a multipartite decoupling with a modified smooth collision entropy. Using the encoder and decoder defined above, we can attain any point in the one-shot capacity region in (6.24).

As in the previous example applications, we can directly apply the AEP Theorem 6.1 for the min-entropy [41] to obtain an achievable rate region for the i.i.d. quantum multiple-access channel: \(H_{\min }^\epsilon (A_I^n|E^n)_{\psi ^{\otimes n}} \sim n S(A_I|E)_\psi = -n S(A_I|BA_{I^c})_\psi = n I(A_I\rangle BA_{I^c})_\psi \), the latter quantity being the coherent information. Then, rates \(R_i = \frac{1}{n}\log s_i\) are achievable in the limit \(n\rightarrow \infty \) and \(\delta \rightarrow 0\) if Equation (6.25) is satisfied. The more general statement with the distribution q over u is obtained by applying the AEP to the tensor product \(\bigotimes _{u\in \mathcal {U}} \psi _u^{n_u}\), where \(n_u\) are non-negative integers with \(\sum _u n_u = n\) and \(\sum _u \left| \frac{n_u}{n}-q(u) \right| \rightarrow 0\). This completes the proof. \(\square \)

Achievable rate region of a MAC with two senders \(A_1\) and \(A_2\) in the i.i.d. limit

Full size image

This rate region inner bound goes back to Yard, Devetak and Hayden [28], where it was obtained by determining the extremal points of the above region, attaining these by successive decoders and the rest of the region by time-sharing (convex combination of rates). In the two-sender case (see Fig. 6) these extremal points are \(T=[I(A_1\rangle B)_\psi ,I(A_2\rangle A_1B)_\psi ]\) and \(S=[I(A_1\rangle A_2B)_\psi ,I(A_2\rangle B)_\psi ]\). In the present proof we can achieve for the first time each point of the region directly by a quantum simultaneous decoder, and without needing to appeal to the simultaneous smoothing conjecture (cf. [40]).

As an illustration of a situation where it is essential to reach each point in the convex hull of the corner directly and without time-sharing, we solve the problem of communication via a compound channel, which is given by a subset \(\mathfrak {C} \subset \text {CPTP}(A_{[k]}\rightarrow B)\) of the quantum channels mapping the \(A_i\) to B. A code of block length n for the compound channel is defined as above, but the error is the supremum over the error when applying the code to \(\mathcal {N}^{\otimes n}\), \(\mathcal {N}\in \mathfrak {C}\).

Inspired by Mosonyi’s approach to the single-sender case of classical communication [46], using the Rényi decoupling bound (Theorem 3.3 and Corollary 3.4), we can prove the following general achievability result.

Theorem 6.20

Given the compound channel \(\mathfrak {C} \subset \text {CPTP}(A_{[k]}\rightarrow B)\), a probability distribution q(u) over a discrete alphabet and reference states \({|{\varphi _u^{(i)}}\rangle } \in A_iA_i'\) (\(i\in [k]\)), define the states

where we let \(\mathcal {N}\in \mathfrak {C}\) act on \(A_{[k]}'\). Then the asymptotic rates \(R_i\) are achievable if

the latter coherent information evaluated on the cq-state \(\overline{\rho }(\mathcal {N}) = \sum _u q(u){|{u}\rangle }\!{\langle {u}|}_U \otimes \rho _u(\mathcal {N})\).

The proof combines the ideas of Theorem 6.18 and Corollary 6.19 applied to the uniform mixture channel \(\widetilde{\mathcal {N}} = \frac{1}{N} \sum _{t=1}^N \mathcal {N}_t^{\otimes n}\) over a net for the set \(\mathfrak {C}\) (with respect to the diamond norm), and proceeds like the analogous proof of Theorem 6.17 in the previous subsection on compound quantum state merging, and we thus omit the details.

Decoupling is a fundamental primitive in the design of quantum transmission codes, quantum Slepian-Wolf coding, cryptographic communication, and channel simulation, but has so far been largely limited to single-user settings. Here we have shown how to leverage tensorisation properties of expected-contractive maps, to extend the basic toolbox to simultaneous decoupling in a multipartite setting where each party applies their own random unitary. We have managed to find achievability bounds for general multipartite decoupling in terms of smooth conditional min-entropies as usual in one-shot scenarios (Theorem 3.2); and in terms of conditional Rényi entropies (Theorem 3.3).

Our approach should be contrasted with the “standard” one of passing to a Hilbert-Schmidt norm bound already in the first line of Equation (3.1), seeing that we can evaluate quadratic averages not only of single random unitaries but also their tensor products. This has been done in [9, 51] and [40], and perhaps by other authors who have found themselves then at the same impasse. For simplicity, consider a tripartite quantum state \(\rho _{A_1A_2E}\) (i.e. \(k=2\)) and the usual setup of the composition of local unitary operations (\(U_1\) on \(A_1\) and \(U_2\) on \(A_2\)) followed by a fixed CPTP map \(\mathcal {T}_{A_1A_2\rightarrow B}\) with Choi matrix \(\tau _{A_1A_2B}\). We can use Lemma 4.1 to bound

for two auxiliary states \(\sigma _B\) and \(\zeta _E\). At this point we have passed already to the trace of a square, and following the method in [24] and used above (see also [40]), we define \(\widetilde{\mathcal {T}}_{A_1A_2\rightarrow B}(\cdot )=\sigma ^{-1/4}\mathcal {T}_{A_1A_2\rightarrow B}(\cdot )\sigma ^{-1/4}\), \(\tilde{\rho }_{A_1A_2E}=\zeta _E^{-1/4}\rho _{A_1A_2E}\zeta _E^{-1/4}\) and also \(\tilde{\tau }_{A_1A_2B}=\sigma _B^{-1/4}\tau _{A_1A_2B}\sigma _B^{-1/4}\). Then, after expanding the square, evaluating the expectations using \(\int {\textrm{d}}U\, UXU^{\dagger } = (\text {Tr}X)\frac{\mathbbm {1}}{d}\) and Corollary 4.4, and after optimizing \(\sigma _B\) and \(\zeta _E\) we finally get

where in the last line we have lower bounded the collision entropies by min-entropies, and \(D\!=\!2\left( 1-\frac{1}{|{A_1^2}|}\right) ^{-1}\!\!\left( 1-\frac{1}{|{A_2^2}|}\right) ^{-1}\) is a constant like the ones encountered in Theorems 3.2 and 3.3.

The resulting bound thus has the characteristic sum of exponential terms, one for each subset of parties, and the exponents feature conditional min- and collision entropies of the state and of the fixed channel Choi matrix, respectively, recalling the structure of [24]. So in some sense, this is a one-shot decoupling theorem. The technical problem is that we have left the realm of trace distances in the very first step, and so the min-entropies in the final expression all refer to the same state.

If now we want to move to smooth min-entropies to optimize the attainable rates we need to smooth the global state so as to approximate all reduced states’ smooth min-entropies simultaneously. The long-standing simultaneous smoothing conjecture [10] states that this is possible in some way, but remains unsolved. In [40] it is partially addressed to lead to an improved one-shot decoupling bound, but in the application to an i.i.d. coding problem one still has to appeal to the asymptotic version of the simultaneous smoothing conjecture, which remains open, too. Instead, the innocent-looking step of passing to the second line in Equation (3.1) gains us a sum of tensor product random maps, which we can split up using the triangle inequality so that each term can be dealt with via its own quadratic average bound; at the end, we can then apply smoothing separately to each of the exponential terms corresponding to the subsets of parties. We thus prove the conjectured form of simultaneous local decoupling, while not having to address the simultaneous smoothing conjecture.

We have shown the power of these results by presenting a series of relevant applications in multi-user quantum information tasks. We have found one-shot, finite block length, and asymptotic achievability results in local randomness extraction, multipartite entanglement distillation, and quantum communication via quantum multiple access channels.

• In particular, we have found a one-shot version of local randomness extraction and achievability rates for an arbitrary number k of cooperating users, as well as the optimal rate region in the i.i.d asymptotics. The latter result reproduces the core insight of [26] for \(k=2\) collaborating parties, albeit with a much simpler protocol, and proves the conjectured rate region for an arbitrary number k of users.

• Concerning multi-party entanglement of assistance, we have also found a one-shot and i.i.d. optimal rates, reproducing the asymptotic results from [17] with a much simpler approach. Actually, the used procedure was previously analyzed in [9] and shown to work assuming the simultaneous smoothing conjecture. With the application of our theorems, we do not require the use of this unproven conjecture.

• Likewise, we solve the quantum version of the Slepian-Wolf data compression of correlated sources, which reduces to the task of quantum state merging, in the one-shot setting, as suggested by [9, 51], as well as the i.i.d. setting, reproducing the asymptotically optimal rate region of [16, 17] and proving the conjectured one-shot achievable region, by achieving each point of the respective regions directly, without the need of time-sharing and without the simultaneous smoothing conjecture.

• Finally, we have found a one-shot achievability region for quantum communication via quantum multiple access channels that had been conjectured for a long time. In a similar fashion to the previous applications, we obtained an achievable rate region for the i.i.d. quantum MAC, reproducing the result of [28]. For the first time, we can achieve each point of that region directly by a quantum simultaneous decoder, without the need of time-sharing, and without the simultaneous smoothing conjecture.

To illustrate the utility of the one-shot results we showed that they also solve the compound source/channel versions of all four problems. These are conceptually important results since they prove that attainable rates are in some sense robust and do not require perfect knowledge of the source/channel. Indeed, consider the important case that the set \(\mathcal {S}\) (\(\mathfrak {C}\)) is a small trace-norm (diamond-norm) ball around an “ideal” state (channel). Then Theorems 6.8, 6.14, 6.17 and 6.20 in particular imply that the optimal rates of the ideal state/channel can be almost achieved by a protocol that works uniformly well in the whole neighbourhood of the ideal.

An important future problem will be to extend the multipartite randomness extraction model to the cryptographic setting, where typically only lower bounds on the min-entropies \(H_{\min }^{\epsilon }(A_I|E)_\rho \) are available. In that case, an extractor needs a seed of randomness to start with. For example, Theorem 6.6 (and Theorem 3.2 on which it is based), requires only a unitary 2-design to give security guarantees with high probability. That is to say, each local user could use a random element of the Clifford group as a seed. However, schemes with much smaller seeds are known in single-user settings [25, 53, 54], and it will be interesting to adapt these to the multi-user case.