## Abstract

We give a simple, direct proof of the ‘mother’ protocol of quantum information theory. In this new formulation, it is easy to see that the mother, or rather her generalization to the fully quantum Slepian–Wolf protocol, simultaneously accomplishes two goals: quantum communication-assisted entanglement distillation and state transfer from the sender to the receiver. As a result, in addition to her other ‘children’, the mother protocol generates the state-merging primitive of Horodecki, Oppenheim and Winter, a fully quantum reverse Shannon theorem, and a new class of distributed compression protocols for correlated quantum sources which are optimal for sources described by separable density operators. Moreover, the mother protocol described here is easily transformed into the so-called ‘father’ protocol whose children provide the quantum capacity and the entanglement-assisted capacity of a quantum channel, demonstrating that the division of single-sender/single-receiver protocols into two families was unnecessary: all protocols in the family are children of the mother.

## 1. Introduction

One of the major goals of quantum information theory is to find the optimal ways to make use of noisy quantum states or channels for communication or establishing entanglement. Quantum Shannon theory attacks the problem in the limit of many copies of the state or channel in question, in which situation the answers often simplify to the point where they can be expressed by relatively compact formulae. The last 10 years have seen major advances in the area, including, among many other discoveries, the determination of the classical capacity of a quantum channel (Schumacher & Westmoreland 1997; Holevo 1998), the capacities of entanglement-assisted channels (Bennett *et al*. 1999, 2002), the quantum capacity of a quantum channel (Lloyd 1996; Shor 2002; Devetak 2005) and the best ways to use noisy entanglement to extract pure entanglement (Devetak & Winter 2005) or to help send classical information (Horodecki *et al*. 2001). Until recently, however, each new problem was solved essentially from scratch, and no higher-level structure connecting the different results was known. Harrow’s (2004) introduction of the *cobit* and its subsequent application to the construction of the so-called ‘mother’ and ‘father’ protocols provided that missing structure. Almost all the problems listed above were shown to fall into two families: first the mother and her descendants, and second the father and his (Devetak *et al*. 2004). Appending or prepending simple transformations such as teleportation and superdense coding are suffice to transform the parents into their children.

In this paper, we provide a direct proof of the mother protocol or, more precisely, of the existence of a protocol performing the same task as the mother. In contrast to most proofs in information theory, instead of showing how to establish perfect correlation of some kind between the sender (Alice) and the receiver (Bob), our proof proceeds by showing that the protocol *destroys* all correlation between the sender and a reference system. As destruction is a relatively indiscriminate goal, the resulting proof is correspondingly simple. This approach also makes it clear that the mother actually accomplishes more than originally thought. In particular, in addition to distilling entanglement between Alice and Bob, the protocol transfers all of Alice’s entanglement with a reference system to Bob. This side effect is very important in its own right and also the major focus of our paper. To start with, it places the state-merging protocol of Horodecki *et al.* (2005*a*, 2007) squarely within the mother’s brood. In addition, it makes it possible to use the mother as a building block for distributed compression. We analyse the resulting protocols, finding they are optimal for sources described by separable density operators as well as inner and outer bounds on the achievable rate region in general.

We also emphasize a further connection, first identified in Devetak (2006), that requires both the state transfer and entanglement-distillation capabilities of the mother: the entire protocol allows for a time-reversed interpretation as a quantum reverse Shannon theorem, i.e. an efficient simulation of a noisy quantum channel using a noiseless quantum channel along with entanglement.

Finally, the new approach to the mother solves a major problem left unanswered in the original family paper. There, no operational relationship between the mother and father protocols could be identified, but the two were nonetheless connected by a formal symmetry called *source-channel duality* (Devetak 2006). This new mother protocol can directly be transformed into the father, resolving the mystery of the two parents’ formal similarity and merging the two families into one.

The structure of the paper is as follows. After reviewing the family of quantum protocols in §2 and providing in §3 a high-level description of the improved mother, henceforth the fully quantum Slepian–Wolf (FQSW) protocol, we go straight to the statement and proof of the central result of this paper in §4: a one-shot version of FQSW. The middle section of the paper is devoted to a number of applications of one-shot FQSW. Sections 5 and 6 describe one-shot versions of the ‘father’ and the fully quantum ‘quantum reverse Shannon’ (FQRS) protocol, respectively. The one-shot theorems quickly yield memoryless forms for all three: FQSW in §7, the father in §8 and FQRS in §9. Then we turn to the other highlight of this paper, a treatment of the fully quantum version of the distributed compression problem, which we can solve completely for a large class of sources by providing general inner and outer bounds on the rate region, in §10. In §11, we point out that the FQSW protocol allows for efficient encoding via Clifford operations, after which we conclude. An appendix collects useful facts on typical subspaces.

**Notation:** For a quantum system *A*, let . For two quantum systems *A* and *A*′, let *F*^{A} be the operator that swaps the two systems. An operator acting on a subsystem is freely identified with its extension (via tensor product with the identity) to larger systems. denotes the projector onto the symmetric subspace of *A*⊗*A*′ and the projector onto the antisymmetric subspace of *A*⊗*A*′. Let be the unitary group on *A*. *H*(*A*)_{φ} is the von Neumann entropy of *φ*^{A}, *I*(*A*;*B*)_{φ}=*H*(*A*)_{φ}+*H*(*B*)_{φ}−*H*(*A**B*)_{φ} is the mutual information between the *A* and *B* parts of *φ* and *H*(*A*|*B*)_{φ}=*H*(*A**B*)_{φ}−*H*(*B*)_{φ} the conditional entropy. The symbol |*Φ*〉^{AB} will be used to represent a maximally entangled state between *A* and *B*. Logarithms are taken base 2 throughout.

## 2. The family of quantum protocols

The mother protocol is a transformation of a tensor power quantum state (|*φ*〉^{ABR})^{⊗n}. At the start, Alice holds the *A* shares and Bob the *B* shares. *R* is a reference system purifying the *A**B* systems and does not participate actively in the protocol. In the original formulation, the mother protocol accomplished a type of entanglement distillation between Alice and Bob in which the only communication permitted was the ability to send *qubits* from Alice to Bob. The transformation can be expressed concisely in the resource inequality formalism as
2.1
We will informally explain the resource inequalities used here, but the reader is directed to Devetak *et al*. (2008) for a rigorous treatment. Here represents one qubit of communication from Alice to Bob and [*q**q*] represents an ebit shared between them. In words, *n* copies of the state *φ* shared between Alice and Bob can be converted into *I*(*A*;*B*)_{φ} EPR pairs per copy, provided Alice is allowed to communicate with Bob by sending him qubits at the rate *I*(*A*;*R*)_{φ} per copy. Small imperfections in the final state are permitted provided they vanish as *n* goes to infinity.

In this paper, we prove a stronger resource inequality which we call the FQSW inequality. The justification for this name will become apparent in §10, where we study its applicability to distributed compression, solved classically by Slepian & Wolf (1971). The inequality states that starting from state (|*φ*〉^{ABR})^{⊗n} and using only quantum communication at the rate from Alice to Bob, the two parties can distill EPR pairs at the rate and produce a state approximating , where is held by Bob and *φ*^{R}=*ψ*^{R}. That is, Alice can *transfer* her entanglement with the reference system *R* to Bob, while simultaneously distilling ebits with him. A graphical depiction of this transformation is given in figure 1. The process can also be expressed as a resource inequality in the following way:
2.2
This inequality makes use of the concept of a relative resource. A resource of the form is a channel with input system *S* that is guaranteed to behave like the channel , provided the reduced density operator of the input state on *S* is *ρ*^{S}. In the inequality, is an isometry taking the system *S* to *A**B*. Thus, on the left-hand side of the inequality, a state is distributed to Alice and Bob, whereas on the right-hand side, that same state is given to Bob alone. Transforming the first situation into the second means that Alice transfers her portion of the state to Bob.

As the relationship of the mother to entanglement distillation and communication supplemented using noisy entanglement is explained at length in the original family paper, we will not describe the connections here. The FQSW inequality is stronger than the mother, however, and leads to more children. In particular, if the entanglement produced at the end of the protocol is then re-used to perform teleportation, we obtain the following resource inequality:
2.3
which is known as the *state-merging* primitive (Horodecki *et al*. 2005*a*). It is of note both because it is a useful building block for multiparty protocols (Horodecki *et al*. 2005*a*, 2007; Yard *et al*. 2007) and because it provides an operational interpretation of the conditional entropy *H*(*A*|*B*)_{φ} as the number of qubits Alice must send Bob in order to transfer her state to him, ignoring the classical communication cost.

On the other side of the family, there is the father protocol. In contrast to the mother, in which Alice and Bob share a mixed state (*φ*^{AB})^{⊗n}, for the father protocol they are connected by a noisy channel . Let be a Stinespring dilation of 𝒩 with environment system *E*, such that 𝒩(*ρ*)=Tr_{E} *U**ρ**U*^{†}, and define for a pure state |*φ*〉^{AA′}.

The resource inequality is
2.4
Thus, Alice and Bob use pre-existing shared entanglement and the noisy channel to produce noiseless quantum communication. Comparison of equation (2.4) to the mother, equation (2.1) reveals the two to be strikingly similar: to go from one to the other, it suffices to replace channels by states and vice versa, as well as replace the reference *R* by the environment *E*. This formal symmetry is known as source-channel duality (Devetak 2006). Just as the mother can be strengthened to the FQSW protocol, there is a fully coherent version of the father known as the *feedback father* (Devetak 2006).

The relationships between different protocols are sketched as a family tree in figure 2.

## 3. The fully quantum Slepian–Wolf protocol

The input to the FQSW protocol is a quantum state, (|*φ*〉^{RAB})^{⊗n}, and the output is also a quantum state, . *A*_{2} is a quantum system held by Alice, whereas both and are held by Bob. , therefore, represents a maximally entangled state shared between Alice and Bob. The size of the *A*_{2} system is *n**I*(*A*;*B*)_{φ}−*o*(*n*) qubits. The steps in the protocol that transform the input state to the output state are as follows:

Alice performs Schumacher compression on her system

*A*^{n}. The output space*A*_{S}factors into two subsystems*A*_{1}and*A*_{2}with .Alice applies a unitary transformation

*U*_{A}to*A*_{S}and then sends*A*_{1}to Bob.Bob applies an isometry

*V*_{B}taking*A*_{1}*B*^{n}to .

It remains to specify which transformations *U*_{A} and *V*_{B} Alice and Bob should apply, as well as a more precise bound on *d*_{A1}. Observe that each step in the protocol is essentially non-dissipative. As essentially no information is leaked to the environment at any step, Bob will hold a purification of the *A*_{2}*R*^{n} system after step (ii), regardless of the choice of *U*_{A}. Because all purifications are equivalent up to local isometric transformations of the purifying space, it therefore suffices to ensure that the reduced state on *A*_{2}*R*^{n} approximates *Φ*^{A2}⊗(*φ*^{R})^{⊗n} after step (ii). Bob’s isometry *V*_{B} will be the one taking the purification he holds upon receiving *A*_{2} to the one approximating .

From this perspective, the operation should be designed to *destroy* the correlation between *A*_{2} and *R*^{n}: the mother will succeed provided the state on *A*_{2}⊗*R*^{n} is a product state and *A*_{2} is maximally mixed. The operation *U*_{A} does not itself destroy the correlation, whereas the partial trace over *A*_{1} does that. *U*_{A} should therefore be chosen in order to ensure that tracing over *A*_{1} should be maximally effective. Because one qubit can carry at most two bits of information, tracing over a qubit can reduce mutual information by at most two bits. The starting state (*φ*^{AR})^{⊗n} has *n**I*(*A*;*R*)_{φ} bits of mutual information, which means that *A*_{1} must consist of at least *n*/2*I*(*A*;*R*)_{φ} qubits. We will see that by choosing *U*_{A} randomly according to the Haar measure, we will come close to achieving this rate.

The result is similar in spirit to a recent result of Groisman *et al*. (2005) that demonstrated that in order to destroy correlation in the state *φ* by discarding *classical* information instead of quantum, Alice must discard twice as large a system as she does here: *I*(*A*;*R*)_{φ} cbits per copy. In fact, it is clear that we can derive that result from ours: after Alice’s unitary, the state remaining between *A*_{2} and *R* is almost a product because Alice’s entanglement with the reference gets transferred to Bob, so Alice only needs to discard the system *A*_{1} of roughly *n*/2*I*(*A*;*R*) qubits, which she can do by erasing it entirely via random Pauli operations, at randomness cost amounting to *I*(*A*;*R*) cbits per copy.

## 4. Fully quantum Slepian–Wolf: one-shot version

Although the tensor power structure of (|*φ*〉^{ABR})^{⊗n} allows the FQSW inequality (2.2) to be expressed conveniently in terms of mutual information quantities, our approach allows us to treat arbitrary input states without such structure as well. In this section, we will prove a general ‘one-shot’ version of the FQSW result that leads quickly to inequality (2.2) in the special case where the input state is a tensor power.

For this section, we will therefore dispense with |*φ*〉^{⊗n} and instead study a general state |*ψ*〉^{ABR} shared between Alice, Bob and the reference system. We also eliminate the Schumacher compression step: assume that *A* has been decomposed into subsystems *A*_{1} and *A*_{2} satisfying *d*_{A}=*d*_{A1}*d*_{A2}.

The following inequality is the one-shot version of FQSW.

## Theorem 4.1 (One-shot, FQSW bound).

*There exist isometries* *and* *such that*
*where* *for some isometry W*.

The protocol corresponding to the above theorem consists of Alice performing *U*, sending the system *A*_{1} to Bob, and Bob performing *V* . The number of qubit channels used up is , whereas the number of ebits distilled is .

The main ingredient is the following decoupling theorem.

## Theorem 4.2 (Decoupling).

*Let σ*

^{A2R}(

*U*)=Tr

_{A1}[(

*U*⊗

*I*

^{R})

*ψ*

^{AR}(

*U*

^{†}⊗

*I*

^{R})]

*be the state remaining on A*

_{2}

*R after the unitary transformation U has been applied to A*=

*A*

_{1}

*A*

_{2}.

*Then*4.1

The theorem quantifies how distinguishable *σ*^{A2R}(*U*) will be from the completely decoupled state *I*^{A2}/*d*_{A2}⊗*σ*^{R}(*U*) if *U* is chosen at random according to the Haar measure. As a first observation, note that as *d*_{A1} grows, the two states become progressively more indistinguishable. Also, the upper bound on the right-hand side is expressed entirely in terms of the dimensions of the spaces involved and the purity Tr[(*ψ*^{AR})^{2}]. To assure good decoupling, it suffices that
4.2
In the tensor power source setting, both dimensions and purities can be tightly bounded by functions of the corresponding entropies. When that is the case, the expression on the right-hand side of equation (4.2) plays the role of the from the FQSW resource inequality (2.2).

According to the proof strategy outlined in the previous section, if *σ*^{A2R}(*U*) is close to *I*^{A2}(*U*)/*d*_{A2}⊗*σ*^{R}(*U*), then *σ*^{A2R}(*U*) has a purification that is itself close to a product state. This argument will be made quantitative in the proof of theorem 4.1.

The proof of theorem 4.2 is quite straightforward. We will evaluate the corresponding average over the unitary group exactly for the Hilbert–Schmidt norm and then use simple inequalities to extract inequality (4.1). The evaluations of the relevant averages are mechanical but slightly lengthy calculations.

Before starting in earnest, we perform a calculation whose result will allow us to evaluate all necessary averages over the unitary group. Recall from the notation summary from §1 that *F*^{A2R} is the operator that swaps the composite system *A*_{2}*R* with a duplicate composite system *A*_{2}′*R*′ and that is the projector onto the (anti-)symmetric subspace of *A**A*′.

## Lemma 4.3.

*For A*=*A*_{1}*A*_{2},
4.3
*where*
4.4

## Proof.

Let *X* be Hermitian. By Schur–Weyl duality,
4.5
with the coefficients . Recall that .
4.6
The second line uses the identity *F*^{A}=*F*^{A1}⊗*F*^{A2}. The third follows from *F*^{2}=*I* and the explicit inclusion of previously implicit identity operators to help in the evaluation of the trace in line four. The formula then follows after a little algebra, using that *F*^{A2R}=*F*^{A2}⊗*F*^{R} and . ▪

The decoupling theorem is a direct application of this formula.

## Proof of theorem 4.2.

First note that
4.7
As *σ*^{R}=*ψ*^{R}, the second term on the right-hand side is independent of *U* and it is sufficient to calculate
4.8
where *p* and *q* are defined as in equation (4.4). In the fourth line, we have used the result of lemma 4.3, and in the fifth the identity . But
4.9
holds for all *d*_{A1},*d*_{A2}≥1. Likewise, (*p*+*q*)/2≤1/*d*_{A2} under the same assumption. This when compared with equation (4.7) shows that we can drop the Tr[(*ψ*^{R})^{2}] term to obtain
4.10
The decoupling theorem then follows by the Cauchy–Schwarz inequality: . ▪

Theorem 4.1 is then an easy corollary exploiting the fact that a product mixed state has a product purification.

## Proof of theorem 4.1.

Observe that there exists a particular *U* such that is bounded as in equation (4.1). The final ingredient is Uhlmann’s theorem (Uhlmann 1976), in the version of lemma 2.2 of Devetak *et al*. (2008): If ∥*ρ*^{C}−*σ*^{C}∥_{1}≤*ε*, where *ρ*^{BC} is a purification of *ρ*^{C}, and *σ*^{DC} is a purification of *σ*^{C}, then there exists an isometry such that . As is a purification of *I*^{A2}/*d*_{A2}⊗*σ*^{R}, and *U**ψ*^{RAB}*U*^{†} is a purification of *σ*^{A2R}, there is an isometry such that the statement of the theorem holds. ▪

## 5. Father from FQSW: one-shot version

A few simple observations will allow us to transform the one-shot FQSW protocol into a one-shot father protocol. The father implements entanglement-assisted noiseless quantum communication over a noisy channel . The protocol consumes (maximal) entanglement initally shared between Alice and Bob, and in registers we will call *A*_{3} and *B*_{3}. Mathematically, we verify that the protocol implements noiseless quantum communication by applying it to one-half of a maximally entangled state, the other half of which is held by a reference system *R*. This is equivalent to verifying that after the application of , the reference system *R* is decoupled from the channel’s environment *E*. In the one-shot FQSW protocol, the objective was to decouple *R* and *A*_{2}.

Precisely, we apply the FQSW protocol to the following state:
5.1
for a Stinespring dilation of the noisy channel and some fixed isometry . (The latter will allow us to choose which part of the input system we want to use for encoding.) Note that as a product of two maximally entangled states, *Φ*_{0}^{RA0}⊗*Φ*_{3}^{B3A3} really is a single maximally entangled state between *B*_{3}*R* and *A*_{3}*A*_{0}.

Now we make the corresponding replacements in theorem 4.1:

Thus, there exist isometries and such that
where an appropriate unitary equivalence between and *B*_{3}*R**B* allows us to identify |*ψ*〉^{B3RBE} with .

As acts entirely on systems held by Bob, it could be performed by him as a decoding operation. The isometry , on the other hand, acts on the reference system, which is not allowed to participate actively in the protocol. The situation up to this point is depicted in figure 3. However, because *Φ*_{0}^{RA0}⊗*Φ*_{3}^{B3A3} is maximally entangled between *A*_{3}*A*_{0} and *B*_{3}*R*,
where ⊤ denotes transposition. Thus, the effect of *U* can be achieved by acting instead with *U*^{⊤} on *A*_{3}*A*_{0}, systems held by Alice. Defining , we obtain
5.2
This is precisely the setting of the father protocol, as illustrated in figure 4.

Alice needs to transfer the purification of some maximally mixed state *Φ*_{0}^{R} to Bob. The resources at their disposal are the channel and a maximally entangled state . Alice performs the encoding *W*_{2}, sends the resulting state through the channel 𝒩 and Bob decodes with *V* . The number of ebits used up is , whereas the number of qubits transmitted in the process is .

## 6. Fully quantum reverse Shannon theorem: one-shot version

The quantum reverse Shannon theorem was conceived of in Bennett *et al*. (1999, 2002), and is proved in full in Bennett *et al*. (in preparation). It asserts that in the presence of entanglement, a noisy quantum channel can be simulated by cbits of forward classical communication per copy of the channel, where *C*_{E} is the entanglement-assisted capacity of the channel.

Here, following Devetak (2006), we demonstrate how, by running the mother protocol backwards, one obtains a simple proof of a fully quantum version of this result (however, unlike Bennett *et al*. (in preparation) we do not obtain a simulation of the channel on arbitrary inputs, but only relative to a fixed source). The Stinespring dilation of is simulated in such a way that *E* ends up with Alice. For that reason, we say that the protocol simulates the *feedback channel* associated to .

Ultimately, in §9, we will show the FQRS resource inequality
6.1
where and |*φ*〉^{AA′} is a purification of *ρ*^{A′}. In this section, we will actually prove a one-shot version of this resource inequality, by a simple re-interpretation of the systems of the mother, and running her backwards in time. The task is to simulate with high fidelity the feedback channel on a source *ψ*^{AA′}, using some maximal entanglement *Φ*^{AσBσ} and quantum communication of a system *A*_{1} of dimension *d*_{A1}. From a mathematical point of view, the state has to be created from |*ψ*〉^{AA′}⊗|*Φ*〉^{AσBσ}, as illustrated in figure 5.

Recall that the one-shot FQSW protocol created a product state starting from an arbitrary pure tripartite entangled state, whereas here the goal is to do the reverse. Hence the need to run the protocol backwards in time. To help see the appropriate choice of relabellings, note that in the FQSW case, Bob holds purifications of the *R* and *A*_{2} systems, called and , respectively. In the present setting, Alice starts holding purifications *A*′ and of *A* and , respectively. Matching the corresponding systems suggests the following replacements in the one-shot mother:
A comparison of figure 5 with the FQRS analogue, figure 1 is also very helpful in clarifying the role of the substitutions. We can interpret theorem 4.1 as saying that there exist isometries and such that
In other words, Alice performs on her part of the system and sends *A*_{1} to Bob; she keeps *E* which will be the environment of the channel. (Note that *V*^{†} can be implemented as an isometry for this particular input state.) Bob can perform the isometry to obtain the channel output in *B*.

## 7. Fully quantum Slepian**−**Wolf: i.i.d. version

We now return to the setting where Alice, Bob and the reference system share the state |*ψ*′〉=(|*φ*〉^{ABR})^{⊗n}. This is often called the i.i.d. case because each copy of the state is identical and independently distributed. Combining the one-shot, FQSW result with Schumacher compression will lead to the FQSW resource inequality (2.2). In appendix A, we show the following: For any *ε*,*δ*>0 and sufficiently large *n*, we can define projectors *Π*_{A},*Π*_{B} and *Π*_{R} onto the *δ*-typical subspaces of the systems indicated by the subscripts such that the following properties hold for any subsystem *F*=*A*,*B*,*R*:

,

∥

*ψ*−*ψ*′∥_{1}≤*ε*,2

^{n[H(F)−δ]}≤rank*Π*_{F}≤2^{n[H(F)+δ]}, andTr[(

*ψ*^{F})^{2}]≤2^{−n[H(F)−δ]}.

Here is the Schumacher compression operation (one of whose Kraus elements is *Π*_{A}) and |*ψ*〉 the normalized version of the state
7.1

Although we are concerned with the output of the protocol when it is applied to the state |*ψ*′〉=(|*φ*〉^{ABR})^{⊗n}, by properties (i) and (ii), we can analyse its effect on the nearly indistinguishable |*ψ*〉 instead.

Thanks to the properties of the typical projectors, namely properties (iii) and (iv), the various quantities appearing in the upper bound of theorem 4.2 get replaced by entropic formulas in the i.i.d. case. For an arbitrary subsystem *F*, let *F*^{typ} denote the support of *Π*_{F} and assume *A*^{typ}=*A*_{1}⊗*A*_{2}. By theorem 4.1, there exist isometries and such that
7.2
Choosing , the bound of equation (7.2) becomes less than or equal to .

As *ψ*, and *ψ*′ are close, performing the protocol on the Schumacher compressed state will also do well. More precisely, a double application of the triangle inequality and properties (i) and (ii) give
The number of qubit channels used up is thus *n*[*I*(*A*;*R*)/2+2*δ*], whereas the number of ebits distilled is .

## 8. Father: i.i.d. version

In the i.i.d. father setting described by the resource inequality (2.4), Alice and Bob are given a channel of the form . Choose a Stinespring dilation such that and define . Let |*ψ*〉 and |*ψ*′〉 be as in the previous section, only with *R* replaced by *E*. Now define *Π*_{A}^{t} to be the projector onto a particular *typical* type *t* and define |*ψ*′_{t}〉 and |*ψ*_{t}〉 to be the normalized versions of the states *Π*_{A}^{t}|*ψ*′〉 and *Π*_{A}^{t}|*ψ*〉, respectively. In appendix A, it is shown that there exists a particular *Π*_{A}^{t} such that the following properties hold:

,

∥

*ψ*_{t}−*ψ*_{t}′∥_{1}≤*ε*,2

^{n[H(F)−δ]}≤rank*Π*_{F}≤2^{n[H(F)+δ]},, and

2

^{n[H(A)−δ]}≤rank*Π*_{A}^{t}≤2^{n[H(A)+δ]}.

Let *A*_{t} denote the support of *Π*_{A}^{t}. By property (i), |*ψ*′_{t}〉^{AtBE} is the result of sending a maximally entangled state proportional to through . Similarly, |*ψ*_{t}〉^{AtBtypEtyp} arises from the modified channel . Thus, |*ψ*_{t}〉^{AtBE} is of the form (5.1) and we can apply the results of §5. Proceeding as in the previous section and using the above properties, we conclude that there exist isometries and such that
The number of ebits used up is and the number of qubits transmitted is , leading to the asymptotic rates required by the father resource inequality.

## 9. Fully quantum reverse Shannon theorem: i.i.d. version

As in the previous two sections, we can consider the special case in which Alice and Bob want to simulate many realizations of the channel , or rather its feedback isometry , relative to a source *ρ*^{A}. The FQRS resource inequality (6.1) was described in §6. Just as in §7, the resource inequality is achieved by mentally truncating the state to its typical part, introducing small disturbances and then running the one-shot protocol on the truncated state. We omit the details.

## 10. Correlated source coding: distributed compression

One of the major applications of the state merging inequality (2.3) is to the problem of distributed compression with free forward (or indeed completely unrestricted) classical communication. For this problem, Horodecki, Oppenheim and Winter demonstrated that the resulting region of achievable rates has the same form as the classical Slepian–Wolf problem (Slepian and Wolf 1971; Horodecki *et al*. 2005*a*). In this section, we consider the application of the FQSW inequality to distributed compression without classical communication.

Because distributed compression studies multiple senders, it no longer fits into the resource inequality framework as laid out in Devetak *et al*. (2008). We therefore begin with some definitions describing the task to be performed. A source provides Alice and Bob with the *A* and *B* parts of a quantum state |*ψ*〉=(|*φ*〉^{ABR})^{⊗n} purified by a reference system *R*. They must independently compress their shares and transmit them to a receiver Charlie. That is, they will perform encoding operations *E*_{A} and *E*_{B} described by completely positive, trace-preserving (CPTP) maps with outputs on systems *C*_{A} and *C*_{B} of dimensions 2^{nQA} and 2^{nQB}, respectively. The receiver, Charlie, will then perform a decoding operation, again described by a CPTP map, this time with output systems and isomorphic to *A*^{n} and *B*^{n}. A rate pair (*Q*_{A},*Q*_{B}) will be said to be achievable if for all *ε*>0 there exists an *N*(*ε*)>0, such that for all *n*≥*N*(*ε*) there exists a corresponding (*E*_{A},*E*_{B},*D*) such that
10.1
The achievable rate region for a given |*φ*〉 is the closure of the set of achievable rates. By time-sharing, it is a convex set.

The FQSW inequality provides a natural class of protocols for this task. One party, say Bob, first Schumacher compresses his share and sends it to Charlie. This is possible provided *Q*_{B}>*H*(*B*)_{φ}. The other party, in this case Alice, then implements the FQSW protocol with Charlie playing the role of Bob. This is possible provided *Q*_{A}>*I*(*A*;*R*)/2. Looking at the total number of qubits required gives a curious symmetrical formula:
10.2
introducing a new symbol *J*(*A*;*B*) = *H*(*A*) + *H*(*B*) + *H*(*A**B*) for the characteristic rate sum above, a kind of quasi-mutual information with a plus sign instead of minus.

By switching the roles played by Alice and Bob and also time-sharing between the resulting two protocols, we find the following theorem.

## Theorem 10.1.

*The region defined by*
10.3
*is contained in the achievable rate region* .

In fact, the region of theorem 10.1 is in some cases *equal* to , as we will see by proving a general outer bound on the achievable rate region. Assume that . To begin, fix *n*>*N*(*ε*) and let *W*_{A} and *W*_{B} be the environments for the Stinespring dilations of the encoding operations *E*_{A} and *E*_{B}. We may, without loss of generality, assume that their dimensions *d*_{WA} and *d*_{WB} are bounded above by and , respectively, because every CPTP map from a space of dimension *d* to a space of dimension at most *d* can be written using at most *d*^{2} Kraus operators.

To bound *Q*_{A}, assume that Charlie has received both *C*_{B} and *W*_{B}, i.e. all of *B*^{n}. Let *W*_{C} be the environment for the dilation of Charlie’s *D*. Again, without loss of generality, we can assume that the Stinespring dilations are implemented by preparing the environment systems in pure unentangled states and then applying unitary transformations. Because at the end of the protocol Charlie must have essentially *A*^{n}*B*^{n}, which purifies *R*^{n}, the registers *W*_{A}*W*_{C} have to be in a pure state of their own, product with *R*^{n} and Charlie’s output . Of course, this is not exactly true, only with high fidelity, so we proceed to make these statements rigorous.

Let be the final state after the application of the Stinespring dilations of the encoding and decoding. By the fidelity condition, where denotes the maximum eigenvalue of . Therefore, has Schmidt decomposition 10.4 where , and consequently, So, as the above is the fidelity between states, by Fuchs & van de Graaf (1999), and with the contractivity of the trace distance, we now have 10.5 We can now apply the Fannes inequality (Fannes 1973) to yield 10.6 for , and using .

Now, using the subadditivity of the von Neumann entropy and the fact that the overall state is pure we have
Therefore,
Dividing by *n* and letting , we obtain
10.7
Switching the roles of Alice and Bob gives the corresponding inequality,
10.8
To bound *Q*_{A}+*Q*_{B} let us return to the situation where Alive and Bob perform their original encoding. Then,
10.9
The first equality follows from the fact that the environment system is initiated as a pure unentangled state and from the unitary invariance of the von Neumann entropy.

Combining with the analogous inequality for *B* leads to,
10.10
By similar arguments as before
10.11
for *ε* small enough. So,
Using the purity of the overall state, however, gives *H*(*R*^{n})=*n**H*(*A**B*), which combined with the bound *H*(*C*_{A}*C*_{B})≤*n*(*Q*_{A}+*Q*_{B}) leads to the inequality
10.12
Adding equations (10.10) and (10.12), we obtain
10.13
Thus,
10.14
Now, let be any CPTP map on *R*^{n}. Then we can bound the mutual information *I*(*W*_{A};*W*_{B}) as follows:
where we have used that *W*_{A}*W*_{B} is almost uncorrelated with (via the contractivity of the trace distance under CPTP maps):
followed by the Alicki–Fannes inequality (Alicki & Fannes 2004). The function *H*_{2}(*x*) is the binary entropy . Note that in this way the dimension of *R*′ does not enter, which is desirable as we do not wish to constrain it in any way.

In particular, for small *ε*,
10.15
where in the second line we have invoked the monotonicity of mutual information under local operations. Therefore,
By optimizing over the CPTP map *T*, we thus obtain
where *E*_{sq}(*φ*^{AB}) is the *squashed entanglement* of *φ*^{AB}, defined as the infimum of over extensions *φ*^{ABE} of *φ*^{AB} (Christandl & Winter 2004). We have used explicitly the fact, proved in the cited paper, that *E*_{sq}(*φ*^{⊗n})=*n**E*_{sq}(*φ*).

As *ε*>0 was arbitrary, we have therefore proved the following outer bound on the achievable rate region.

## Theorem 10.2.

*The rate region* *of fully quantum distributed compression of the source φ is contained in the set defined by the inequalities*
10.16

In the special case where *φ*^{AB} is separable, *E*_{sq}(*φ*)=0, which implies that the region defined by equation (10.3) is optimal. Under a certain technical assumption the same conclusion was found in Ahn *et al*. (2006): namely, there it was required that *φ*^{AB} is the density operator of an ensemble of product pure states satisfying a condition called irreducibility. That paper, however, was unable to show that the bound was achievable.

The appearance of the squashed entanglement in equation (10.16) may seem somewhat mysterious, but a slight modification of the protocols based on FQSW will lead to an inner bound on the achievable region that is of a similar form. Specifically, let *D*_{0}(*φ*^{AB}) be the amount of pure state entanglement that Alice and Bob can distill from *φ*^{AB} without engaging in any communication. As this pure state entanglement is decoupled from the reference system *R*, they could actually perform this distillation process and discard the resulting entanglement before beginning one of their FQSW-based compression protocols. Although neither *I*(*A*;*R*) nor *I*(*B*;*R*) would change, each of *H*(*A*) and *H*(*B*) would decrease by *D*_{0}(*φ*^{AB}). The corresponding inner bound on the achievable rate region would therefore be defined by the inequalities
10.17
The only gap between the inner and outer bounds, therefore, is a gap between different measures of entanglement.

We close this section by exhibiting a class of example sources for which we believe that the above inner bound is not tight. It is based on the observation that to arrive at equation (10.17), we considered a case where the structure of *W*_{C} was very simple. Although, in principle, *W*_{C} could harbour arbitrary tripartite entanglement with *W*_{A} and *W*_{B}, the decoding for equation (10.17), which is just the FQSW protocol’s decoding, is simply an isometry separating the entanglement with *R*^{n} from that with one, and only one, of *W*_{A} and *W*_{B}. Hence, we are motivated to try and construct a source that permits Alice and Bob to extract and discard some ‘waste’, such that later on Charlie can finish off by discarding exactly the purification of that waste. The purified source is one of the *twisted states* (Horodecki *et al*. 2005*b*) of the form
arbitrary unitaries *U*_{i} on the joint system *A*′′*B*′′. (It is understood that *A*=*A*′*A*′′ and *B*=*B*′*B*′′.)

Now let us assume that the reduced states are mutually orthogonal for *i*=1,…,*d*. Furthermore, we restrict to the case of *non-local* unitaries *U*_{i}, i.e. *U*_{i} is not a tensor product of local unitaries. We conjecture that *D*_{0}(*φ*^{AB})=0 or, more specifically, that because of the non-local ‘twist’, Alice and Bob cannot extract pure states from *φ*^{AB} by local operations alone. This would mean that our inner bound yields an achievable rate sum of
However, a better rate sum is attainable because neither Alice nor Bob need to send the *A*′ and *B*′ registers, respectively: if *A*′′ and *B*′′ are transmitted faithfully, Charlie can coherently measure *i*, use it to undo *U*_{i}, so that he is left with the state . He then has |*i*〉 in his waste register *W*_{C}, entangled only with the contents of Alice’s and Bob’s waste registers *W*_{A}=*A*′ and *W*_{B}=*B*′. He finishes off by discarding the waste register, creating afresh and using a controlled unitary to put back the twist *U*_{i} onto ϕ_{0}. Instead of the rates
they now use strictly less qubit resources,

## 11. On encoding complexity

Although the protocols described so far make use of a unitary transformation drawn at random according to the Haar measure, that is not essential. In fact, the only place the Haar measure was used was in the proof of lemma 4.3. Therefore, the full unitary group could be replaced by any subset yielding the same average as in the lemma. (We thank Debbie Leung for alerting us to this possibility.) In fact, DiVincenzo *et al.* (2002) have shown that
11.1
where *G*_{n} is the Clifford group on *n* qubits. They also demonstrate in that paper that choosing an element of *G*_{n} from the uniform distribution can be done in time polynomial in *n*. More specifically, they show that a random walk on a particular set of generators for *G*_{n} mixes in *O*(*n*^{8}) time, leading to an associated quantum circuit for the selected element that is of size *O*(*n*^{2}) gates.

As the Schumacher compression portion of the FQSW protocol can also be done in polynomial time (Cleve & DiVincenzo 1996), we conclude that the encoding portion of the mother can be done efficiently. As her immediate children, including entanglement distillation and state merging, are built by composing the mother with efficient protocols, namely superdense coding and teleportation, their encodings can also be found and implemented efficiently.

The transformation from FQSW to the father, however, included another non-constructive step, namely the choice of a good type class. As the number of type classes is polynomial in the number of qubits in the input, however, that step could also be implemented efficiently. The corresponding isometries mapping the shared maximally entangled state and the input space into *A*_{t} can also be performed efficiently (Cleve & DiVincenzo 1996). Finally, although the proof presented here implies that the transpose of a random Clifford group element can be used as the encoding operation, there is in fact no need for the transpose because the Clifford group is closed under transposition. Thus, the encoding for the father can be found and implemented in polynomial time, as can those of his children, entanglement-assisted classical communication and quantum communication over a noisy channel.

Finally, because the quantum reverse Shannon protocol consists of running FQSW backwards in time, it is Bob’s *decoding* that can be found and implemented efficiently instead of Alice’s encoding.

## 12. Discussion

We have shown that simple representation-theoretic reasoning, specifically some quadratic averages, are sufficient to derive the powerful mother protocol: a fully quantum version of entanglement distillation with state merging. The mother, in proper mythical fashion, not only generates her children in the family tree, but also the father protocol and his offspring, the quantum reverse Shannon theorem, plus an almost complete solution to the distributed quantum compression problem. We leave it as an open problem to determine the exact rate region, which we conjecture to be given by
with some functional *F*(*φ*_{AB}) of the source density operator. It is tempting to speculate that *F*, as in our inner and outer bounds on the rate region, is an entanglement monotone; note that for separable and for pure states, our inner and outer bounds coincide, giving 0 and the entropy of entanglement, respectively, in agreement with the idea that *F* should be an entanglement measure.

We also note that although we have not pursued the opportunity here, the one-shot versions of the FQSW, father and reverse Shannon theorem are natural starting points for developing versions of the theorem adapted to states or channels with some internal structure more complicated than i.i.d. It would be interesting to compare the results of such an effort with the insights of Bowen & Mancini (2004) and Kretschmann & Werner (2005).

We close by highlighting a peculiar feature of the FQSW protocol. Let |*ψ*〉 be a pure state and suppose that Alice–Bob and Alice–Rebecca both share *n* copies of |*ψ*〉, so that the global pure state is |*φ*〉^{⊗n}=(|*ψ*〉^{A1R}|*ψ*〉^{A2B})^{⊗n}. This is a ‘trivial’ situation for FQSW. Instead of using our protocol, Alice can simply transfer her entanglement with Rebecca to Bob by compressing and sending him her *A*_{1} registers, requiring a rate of *H*(*A*_{1})=*I*(*A*;*R*)/2. As Alice and Bob already share *H*(*A*_{2})=*I*(*A*;*B*)/2 ebits of pure state entanglement, that completes the FQSW protocol. Because of the symmetry of the situation, the roles of Rebecca and Bob could also be reversed. Thus, Alice could transfer her Bob entanglement to Rebecca by Schumacher compressing and sending *A*_{2} to her, requiring a rate *H*(*A*_{2})=*I*(*A*;*B*)/2. It is quite clear that Alice’s system decomposes into an *A*_{1} part, which contains her entanglement with Rebecca, and an *A*_{2}, which contains her entanglement with Bob. Note that the entanglement structure of the final state is very different in the two cases (figure 6). Here is the weirdness: if they use the general FQSW protocol instead, then because *H*(*A*_{1})=*H*(*A*_{2}), the *same* unitary will work in both cases with high probability. In other words, Alice could *first* apply the unitary and *then* decide whether to transfer her Rebecca entanglement to Bob or her Bob entanglement to Eve. The only difference in Alice’s part of the protocol is whether she sends the qubits (at rate arbitrarily small above *H*(*A*_{1})) to Bob or to Rebecca. Thus, the localization of the entanglement so evident in the trivial implementation of the protocol disappears in the general implementation. The same subsystem can be made to carry both forms of entanglement simultaneously, compatible with either recipient!

## Acknowledgements

The authors thank Debbie Leung for bringing to their attention the possibility of replacing Haar measure unitaries with random Clifford group elements. They also thank Isaac Chuang, Ignacio Cirac, Frédéric Dupuis, Renato Renner and Jürg Wullschleger for their helpful comments. A.A. appreciates the support of the US National Science Foundation through grant no. EIA-0086038. I.D. was partially supported by the NSF under grant no. CCF-0524811. P.H. was supported by the Canada Research Chairs program, the Canadian Institute for Advanced Research, and Canada’s NSERC. He is also grateful to the Benasque Centre for Science and CQC Cambridge for their hospitality. A.W. was supported by the UK Engineering and Physical Sciences Research Council’s ‘IRC QIP’, and by the EC projects RESQ (contract IST-2001-37759) and QAP (contract IST-2005-15848), as well as by a University of Bristol Research Fellowship.

## Appendix A. Properties of typical and type projectors

We present here a number of consequences of the method of type classes. Denote by *x*^{n} a sequence *x*_{1}*x*_{2}⋯*x*_{n}, where each *x*_{i} belongs to the finite set . Denote by the cardinality of . Denote by *N*(*x*|*x*^{n}) the number of occurrences of the symbol *x* in the sequence *x*^{n}. The *type**t*^{xn} of a sequence *x*^{n} is a probability vector with elements . Denote the set of sequences of type *t* by
For the probability distribution *p* on the set and *δ*>0, let . |τ_{δ}|=*a*. Define the set of *δ*-typical sequences of length *n* as ,
A 1

Define the probability distribution *p*^{n} on to be the *n*-fold product of *p*. The sequence *x*^{n} is drawn from *p*^{n} if and only if each letter *x*_{i} is drawn independently from *p*. Typical sequences enjoy many useful properties (Csiszar & Körner 1981; Cover & Thomas 1991). Let be the Shannon entropy of *p*. For any *ε*,*δ*>0, and all sufficiently large *n* for which
A 2
A 3
and
A 4
for some constant *c*. For *t*∈τ_{δ} and for sufficiently large *n*, the cardinality *D*_{t} of is bounded as (Winter 1999)
A 5
and the function as .

The above concepts generalize to the quantum setting by virtue of the spectral theorem. Let be the spectral decomposition of a given density matrix *ρ*. In other words, |*x*〉 is the eigenstate of *ρ* corresponding to eigenvalue *p*_{x}. The von Neumann entropy of the density matrix *ρ* is
The type projector is defined as
The typical subspace associated with the density matrix *ρ* is defined as
Properties analogous to equations (A 2)–(A 5) hold. For any *ε*,*δ*>0, and all sufficiently large *n* for which
A 6
A 7and
A 8
for some constant *c*. For *t*∈τ_{δ} and for sufficiently large *n*, the support dimension of the type projector *Π*_{t}^{n} is bounded as
A 9

Henceforth, we shall drop the *n* and *δ* indices. In dealing with a multiparty system such as |*ψ*′〉=(|*φ*〉^{ABR})^{⊗n}, we shall label the typical projectors corresponding to the various subsystems by *Π*_{A}, etc. A variant of the gentle measurement lemma (Winter 1999) states that if Tr *Π**ρ*≥1−*ε*, then , where and *σ*=*Π ρΠ*. Applying it together with (A 6) gives
The Schumacher compression operation projects onto

*Π*

_{A}with probability Tr

*ψ*′

*Π*

_{A}≥1−

*ε*. Thus, The triangle inequality now gives Define |

*ψ*〉 to be the normalized version of the state A 10 As

*Π*

_{R},

*Π*

_{A}and

*Π*

_{B}commute, they satisfy a sort of union bound, A 11 Combining this with the same variant of the gentle measurement lemma as before and (A 6) gives Observe Then, A 12 Combining with inequalities (A 7) and (A 8) gives Define and . By equations (A 7) and (A 9),

*P*′

_{t}≥2

^{−n[cδ+ι(δ)]}for all

*t*∈τ

_{δ}. Define |

*ψ*

_{t}′〉 and |

*ψ*

_{t}〉 to be the normalized versions of the states and , respectively. As and , we have A 13 We now claim that there exists a

*t*for which both A 14 First, by Cauchy–Schwarz, so that Thinking of

*P*′

_{t}as a probability distribution over

*t*, the probability that

*P*

_{t}′>3

*P*

_{t}is upper bounded by , as is the probability that |〈

*ψ*

_{t}|

*ψ*

_{t}′〉|≤1−18

*ε*. Hence, there exists a

*t*for which both events are false, yielding the claim. Choose

*t*to be one that satisfies the claim. Then From and , it follows that A similar bound holds for .

Thus we have shown properties (i)–(iv) of §7 and (i)–(v) of §8.

## Footnotes

- Received April 16, 2009.
- Accepted May 1, 2009.

- © 2009 The Royal Society