---
author:
- Igor Devetak$^1$ and Jon Yard$^2$
bibliography:
- 'qcmi.bib'
title: The operational meaning of quantum conditional information
---

Information might be regarded as an answer to a question. To know if it is raining, one need only look outside. However, a person living in a desert would expect a different answer than one living in a climate where on average, it rains every other day. After looking outside, who gains “more" information? The answer to this question has nothing to do with weather – statistically, the desert dweller learns less, owing to the general predictability of desert rain patterns.

The statistical approach to quantifying information was taken by Claude Shannon [@shannon], who found that entropy plays a central role. By modeling the weather as a random variable $X$ which is equal to “rain" or “shine" with probabilities $p(x)$, the information gained by looking out the window (or rather, the *uncertainty* one has before looking) is the *Shannon entropy* $$H(X) = -\sum_x p(x)\log_2 p(x)$$ of $X$. Suppose that the weather on each day is independent of that on the previous day, and that the overal climate is the same each day. According to Shannon’s theory, the weather for $n$ days can be described by the answers to roughly $nH(X)$ yes-no questions, or $nH(X)$ *bits*, so that $H(X)$ is the *average* number of bits needed to describe the weather on any given day. The weather problem is an example of *data compression*. Shannon showed that, provided the average number of bits used to describe a source $X$ exceeds $H(X)$ by *any* amount, no matter how small, it is possible to reconstruct the source from that description with vanishing error. Otherwise, errors will be unavoidable. The only caveat is that to decrease the error, it is necessary to compress a larger set of data in a single block. Data compression gives Shannon entropy an *operational* meaning, or interpretation, as the minimum average number of bits required to faithfully represent $X$. Shannon further defined the *conditional entropy* as $$H(X|Y) = H(XY) - H(Y),$$ which is also equal to the average entropy of $X$ given $Y$. Conditional entropy measures the information someone knowing only $Y$ would have to learn in order to know $X$ as well. Its operational relevance was shown [@SW71] by Slepian and Wolf to be the minimum number of bits needed to represent $X$ for someone who knows $Y$. Shannon also introduced *mutual information* $$I(X;Y) = H(Y) - H(Y|X)$$ and *conditional mutual information* $$I(X;Y|Z) = H(Y|Z) - H(Y|XZ),$$ each of which is interpreted as the information shared by $X$ and $Y$, only the latter is measured from the perspective of someone knowing $Z$. Mutual information plays a fundamental role in characterizing the capacity for a noisy channel to transmit information [@shannon]. Its conditional counterpart arises in the answers to many problems, such as in rate distortion with side information at the decoder [@WZ76] and communication with side information at the encoder [@S58]. It also appears in the analysis of degraded broadcast channels [@C72]. All four of these quantities can easily be shown to be nonnegative.

In recent years, a quantum mechanical generalization [@BS98] of Shannon’s theory has been under development. Here, a random variable is replaced with a quantum system $C$ with density matrix $\rho^C$. The quantum analog of Shannon entropy is von Neumann entropy $H(C)_\rho = -\operatorname{Tr}\rho^C\log_2\rho^C$, which is the Shannon entropy of the eigenvalues of $\rho^C$. While von Neumann’s entropy preceded Shannon’s by almost twenty years, its operational interpretation was only found relatively recently by Schumacher [@Sch95], who showed that a large number $n$ of quantum systems, identically prepared in the state $\rho^C$, could be compressed into a space of roughly $nH(C)$ *qubits*, or two-level quantum systems. Here, a successful compression scheme is one which preserves the correlations $C$ shares with the rest of the world, modeled by a reference system $R$. The combined system is considered to be in any pure state $\ket{\psi}^{CR}$ satisfying $\rho^C = \operatorname{Tr}_R{\ket{\psi}\bra{\psi}}^{CR}$. We then say that Alice holds a *purification* of the reference $R$. Just as Shannon designated the abstract “bit of information", Schumacher provided the “qubit of quantum information" as a fundamental unit quantum information. Quantum information cannot be *known* per se, although classical information about the identity of the quantum state can be inferred by making measurements. Rather, quantum information is something one can *possess* by having control over a quantum mechanical system which embodies it. It has been known for some time that quantum information cannot be copied [@WZ82], so in contrast to the classical case, if Alice “knows" $C$ and would like to “tell" it to Bob, not only must she send him at least $H(C)$ qubits, she will lose possession of $C$ in the process.

The analogy can be continued, defining a quantum counterpart for each of Shannon’s quantities by replacing Shannon with von Neumann entropies. *Quantum mutual information* [@BSST99] $I(A;B)$ can be considered as a measure of correlations between $A$ and $B$. It plays a remarkably similar role as its classical counterpart, describing the classical capacity of a noisy quantum channel in the presence of free entanglement [@BSST99; @BSST02]. It also has a direct operational interpretation [@GPW05] as the smallest rate of classical randomness which erases all correlations between $A$ and $B$. On the other hand, *quantum conditional entropy* $H(A|B)$ and *quantum conditional mutual information* (QCMI) $I(A;B|C)$ are less like their classical counterparts, as they cannot generally be viewed as averages. Furthermore, $H(A|B)$ can be negative; $-H(A|B)$ is often referred to as the *coherent information* [@SN96], which plays a role in characterizing the capacity of a quantum channel for transmitting quantum information [@L96; @S02; @D05]. The operational task of *state merging* [@HOW05] gives meaning to $H(A|B)$ where, depending on its sign, it corresponds to the rate at which entanglement is either consumed or generated while transferring $A$ to someone already holding $B$. On the other hand, QCMI can be shown to be nonnegative. Unlike the classical case, this amounts to a theorem, known as *strong subadditivity* of quantum entropy, whose original proof [@LR73] relies on nontrivial tools from matrix analysis. More recently, operational proofs have been found [@HOW05; @GPW05], and we will see that our protocol leads to yet another such proof. Strong subadditivity is correspondingly powerful; it underlies virtually every known bound in quantum information theory. An early consequence of this result was a proof [@AL70] of the existence of the entropy density for translationally-invariant quantum statistical models. More recently, strong subadditivity has found applications to geometric entropy [@Cas04] and conformal field theory [@CH04]. Despite its central role, a direct operational interpretation of QCMI on an arbitrary state has been conspicuously absent, although it has arisen in operational interpretations for certain restricted classes of underlying states [@CW04]. It is our primary focus to give such a general interpretation.

![Quantum state redistribution.[]{data-label="figure:redistribute"}](qcmiFigure1nograd.eps)

The ability to send qubits from Alice to Bob is a resource, and Schumacher’s theorem tells how much of it is needed to transfer $C$. A weaker resource is entanglement, because it can be established by by sending qubits. A “standard unit" of entanglement is called an *ebit* and consists of a single EPR pair $\ket{\Psi_{\!+}} = \frac{1}{\sqrt{2}}\big(\ket{00} + \ket{11}\big)$ shared between Alice and Bob. By quantum teleportation [@BBCJPW93], an ebit can be used to send a qubit, provided that two classical bits are sent as well. In the absence of classical communication, ebits are not helpful for moving $C$ from Alice to Bob. They are helpful, however, in a variant of Schumacher’s scenario in which Alice and Bob have some side information. We model this with four systems in the state $\ket{\psi}^{ABCR}$, where Alice holds $AC$ and Bob has $B$, and ask Alice to give $C$ to Bob, as in Figure \[figure:redistribute\], by sending qubits and using entanglement. In particular, no classical communication is allowed, beyond what can be encoded in qubits. We allow the entanglement cost to be any real number, interpreting positive and negative values as in state merging. Our main result is that there exists a protocol – *quantum state redistribution* – allowing Alice to transfer $C$ to Bob at a cost of $Q$ qubits and $E$ ebits if and only if $$\begin{aligned}
Q &\geq& \12I(C;R|B) \\
Q + E &\geq& H(C|B).\end{aligned}$$ This gives the first direct operational interpretation of QCMI on an *arbitrary* state. Simultaneously minimizing $Q$ and $Q+E$ leads to the *optimal cost pair* $$\begin{aligned}
Q&=& \12 I(C;R|B) \label{redistpairQ}\\
E &=& \12 I(C;A) - \12 I(C;B). \label{redistpairE}\end{aligned}$$ This pair corresponds to the corner point of the region in Figure \[figure:region\]. As with Schumacher compression, this result is to be understood in the limit of many identical copies. Let us now point out some remarkable features of our result.

![Region of achievable cost pairs, together with the time-reversed optimal cost pair, assuming $I(C;A) > I(C;B)$.[]{data-label="figure:region"}](qcmiRateRegion.eps)

![Left: Unitary quantum state redistribution protocol in which Alice redistributes $C$ to Bob while *consuming* entanglement (assuming that $I(C;A) \geq I(C;B)$). Right: Corresponding time-reversed process where Bob redistributes $C$ to Alice, this time *generating* the same amount of entanglement.[]{data-label="figure:circuit"}](qcmiCircuit.eps)

#### Self-duality under time reversal: {#self-duality-under-time-reversal .unnumbered}

As illustrated in Figure \[figure:circuit\], our protocol can be implemented *unitarily* – if entanglement is consumed by the protocol, reversing those unitaries leads to a protocol which instead sends $C$ from Bob to Alice, while *generating* the same amount of entanglement. Perhaps surprisingly, this symmetry is also evident in the *optimal* cost pairs: switching $A$ and $B$ reflects the optimal cost pair about the $Q$-axis (see Figure \[figure:region\]). Thus, switching $A$ and $B$ changes the sign of $E$ in (\[redistpairE\]), but has no effect on the expression (\[redistpairQ\]) for $Q$ because the identity $I(C;R|B) = I(C;R|A)$ holds on every pure state $\ket{\psi}^{ABCR}$. In fact, our protocol can be considered as providing an explaination for why this identity should be true.

#### Perfect composability: {#perfect-composability .unnumbered}

Suppose that Alice wants to transfer a composite system $CD$ to Bob. An optimal strategy is for Alice to treat $CD$ as a single system, sending them both simultaneously using our protocol. The optimal cost pair for this is $$\begin{aligned}
Q&=&\12I(CD;R|B) \\ 
E &=& \12 I(CD;A) - \12I(CD;B).\end{aligned}$$ What if she sends the systems successively, as depicted in Figure \[figure:successive\]? The optimal cost for first transferring $D$ is $$\begin{aligned}
Q_D &=& \12I(D;R|B) \\
E_D &=&  \12I(D;AC) - \12I(D;B).\end{aligned}$$ Since Bob now has $D$, the remaining cost for sending $C$ is $$\begin{aligned}
Q_C &=&  \12 I(C;R|DB) \\
E_C  &=& \12 I(C;A) -\12 I(C;DB).\end{aligned}$$ Simple algebraic manipulations then show that $Q = Q_C + Q_D$ and $E = E_C + E_D$! This feature parallels successive refinement in classical rate-distortion theory [@CE91], only here the Markov condition is absent.

![Successive state redistribution.[]{data-label="figure:successive"}](qcmiFigure2nograd.eps)

#### Applications: {#applications .unnumbered}

Consider the following illustrative examples and applications of state redistribution:

*(1) Four-party cat state:* The optimal cost pair for the state $\frac{1}{\sqrt{2}}\big(\ket{0000} + \ket{1111}\big)$ we find that the optimal cost pair is $Q = E = 0$. To redistribute $C$ from Alice to Bob, Alice applies the local isometry$\ket{0}\bra{00}+ \ket{1}\bra{11}$, while Bob applies its inverse.

*(2) Four-party W state:* If the global state is $\frac{1}{2}\big(\ket{1000} + \ket{0100} + \ket{0010} + \ket{0001}\big),$ we obtain $Q\approx .38$ and $E=0$ for the optimal cost pair. For comparison, a compress-and-send strategy which ignores the side information requires roughly $.81$ qubits.

*(3) States saturating strong subadditivity:* The states which require a zero rate of communication to redistribute $C$ are precisely those which saturate strong subadditivity ($I(C;R|B) =0$), and are thus locally equivalent to a state of the form [@HJPW04] $$\sum_x \sqrt{p_x}\ket{x}^{A'}\ket{x}^{B'}\ket{\phi_x}^{A_CB_CC}\ket{\varphi_x}^{A_RB_RR}.$$ The entanglement cost for such states is $\sum_x p_x  \big(H(B_C)_{\phi_x} - H(A_C)_{\phi_x}\big).$ Another optimal strategy is thus to coherently concentrate [@BBPS96] the $A_CC\big|B_C$ entanglement while diluting [@LP99] the $A_C\big|CB_C$ entanglement in the individual states $\phi_x^{A_CB_CC}$.

*(4) State merging:* Our state redistribution protocol allows for a deeper understanding of state merging [@HOW05; @HOW05b]. By adding the additional resource of free classical communication, we recover their result that the cost, in ebits, for merging $C$ to $B$ is equal to $H(C|B)$. Accounting for transmitted bits as well, state merging considers $A$ to be part of the reference, requiring that $I(RA;C)$ bits be sent per copy of $C$ merged. By our result, the classical communication cost is reduced to $I(R;C|A)\leq I(RA;C)$, which can be shown to be optimal by an argument similar to the one we give for our protocol. Thus, QCMI can also be regarded as the classical communication cost for state transfer in the presence of unlimited entanglement.

*(5) Fully quantum Slepian-Wolf (FQSW):* A special case of our result is when Alice has no side information. An optimal strategy for this scenario has been found previously and called the *fully quantum Slepian-Wolf* protocol [@D05b; @ADHW06], which can transfer $C$ from Alice to Bob using $Q$ qubits and $E$ ebits if and only if $$\begin{aligned}
Q &\geq& \12 I(C;R) \\
Q + E &\geq& H(C|B).\end{aligned}$$ The optimal cost pair is $$Q=\12I(C;R),\,\,\,\, E = -\12 I(C;B).$$

*(6) Fully quantum reverse Shannon (FQRS):* If it is instead Bob who lacks side information, we obtain the previously studied [@D05b; @ADHW06] fully quantum reverse Shannon protocol as a special case of our result. Here, the required costs for transferring $C$ to Bob are given by $$\begin{aligned}
Q &\geq& \12 I(C;R) \\
Q+E &\geq& H(C).\end{aligned}$$ The optimal cost pair is dual to that of FQSW under time reversal [@D05b]: $$\begin{aligned}
Q=\12I(C;R),\,\,\,\, E = \12 I(C;A).\end{aligned}$$

#### The protocol: {#the-protocol .unnumbered}

Here we describe the proof that our protocol exists; a more detailed treatment (I.D. J.Y.) is forthcoming. First note that by the FQRS protocol, Alice can use $\12 I(C;RB)$ qubits and $\12 I(C;A)$ ebits to simulate the isometry which moves $C$ to Bob, while keeping $A$ to herself. In order to take advantage of Bob’s side information, Alice can use a modification of that protocol which also transmits $I(C;B)$ bits per copy of $C$ which is moved [@HHHLT01; @BSST02]. It is furthermore possible to make the classical communication *coherent* [@H04; @DHW04] in the following sense. We say that Alice sends a *coherent bit* [@H04] to Bob if she applies an isometry $\ket{x}^A \mapsto \ket{x}^A\ket{x}^B$ to a qubit in her possession, where Bob has $B$ and $x=0,1$. Asymptotically, two coherent bits can be used to send a qubit and to generate an ebit [@H04], so Alice can send an *additional* $\frac{1}{2}I(C;B)$ qubits, while generating the same number of ebits with Bob. This leads to a catalytic scenario, where extra ebits and qubits are needed to start the protocol, but are returned after completion. The dependence on the catalysts can be eliminated using methods in [@DHW05]. Subtracting the resources generated by the protocol from those which were invested yields the optimal cost pair. On the other hand, the optimality of our protocol is shown in [@LD06] to follow from that of FQSW by subtracting the optimal costs for Alice to send only $A$ from the costs for Alice to send $AC$.

#### Discussion: {#discussion .unnumbered}

For an arbitrary pure state $\ket{\psi}^{ABCR}$, we have determined the communication and entanglement resources which are necessary and sufficient for Alice and Bob, who respectively hold $A$ and $B$, to transfer $C$ between themselves while retaining the purity of the global state. The optimal communication cost gives the first operational interpretation of QCMI on an *arbitrary* state and also gives a natural interpretation to the pure state identity $I(C;R|A)=I(C;R|B)$: the correlations between $C$ and $R$ look the same from each of Alice’s and Bob’s perspectives. Because of this, the communication cost is symmetric under time-reversal. On the other hand, the optimal entanglement cost was shown to be *antisymmetric* under time-reversal, so that if ebits must be consumed to move $C$ one way, the same number can be generated while moving it back.

There is a formal time-reversal duality between FQSW and FQRS [@D05b]. We showed that our protocol is *self-dual* in the same sense, while incorporating both results as special cases. Interestingly, our coding theorem is based on a generalization of that from FQRS, while both the coding theorem and the converse from FQSW are used for our converse.

A corollary of our main result is a direct operational proof of strong subadditivity. Ours differs from other such operational proofs [@HOW05; @GPW05] because it does not even rely on the *subadditivity* of entropy, i.e. that $H(A)\geq H(A|B)$. Indeed, before removing the dependence on catalyst channels, our protocol cannot simulate more qubit identity channels than were initially provided so that positivity of the overall qubit cost (QCMI) is evident.

Our protocol is the first which involves an arbitrary four-partite pure state. As such, it can be applied as a fundamental primitive for all multi-party state redistribution problems. Indeed, whenever there is a sender (Alice) and a receiver (Bob), there are four natural subsystems: the system $A$ which stays with Alice, the system $B$ which Bob already has, the system $C$ which is being communicated, and the rest of the world $R$. Even if there are many more parties, each particular round of communication fits into our setting. For instance, suppose Alice holds $AC_A$, Bob has $BC_B$ and Charlie holds $C$, while all systems are purified into a reference system $R$. If the goal is to transfer $C_A$ and $C_B$ to Charlie, direct application of our result gives a four-dimensional region of achievable costs $(Q^{A\to C},Q^{B\to C},E^{AC},E^{BC})$, generated by two corner points, each corresponding to a different order in which Charlie receives the systems $C_A$ and $C_B$. It is likely that other strategies, such as where $C_A$ and $C_B$ are split into multiple subsystems and are sent to Charlie in various orders, would lead to even larger achievable regions. Furthermore, it is known [@ADHW06] that FQSW, when combined with teleportation [@BBCJPW93] and superdense coding [@BW92], recovers virtually every known quantum Shannon-theoretic protocol. We expect even more from state redistribution and are currently investigating its further implications for constructing more complex protocols and for understanding the structure of multipartite quantum states.

#### Acknowledgements: 

The authors are grateful to Toby Berger for urging them to find a quantum analogue of successive refinement, which partly inspired this result. They also thank Andrew Childs and Aram Harrow for comments on an earlier draft and and acknowledge funding from grants through the US National Science Foundation.
