## Abstract

Information processing protocols are typically built out of simpler parts, called primitives, and two of the most important such primitives are privacy amplification (PA) and data compression. The former extracts the truly secret part of some classical data, while the latter squeezes it into the smallest possible form. We show these tasks are dual in the setting of quantum information processing. Specifically, the tasks of PA of classical information against quantum adversaries and classical data compression with quantum side information are dual in the sense that the ability to perform one implies the ability to perform the other. The duality arises because the two protocols are connected by complementarity and the uncertainty principle in the quantum setting. Applications include a new uncertainty principle formulated in terms of smooth min- and max-entropies, which are useful in the study of one-shot protocols, as well as new conditions for approximate quantum error correction.

## 1. Introduction

Two of the most fundamental primitives in information theory are privacy amplification (PA) and data compression with side information, both of which involve manipulating the correlations between two random variables *Z* and *Y* . Privacy amplification is the art of extracting that part of *Z* which is uncorrelated from *Y* . In particular, the goal is to extract uniform randomness, in the form of a random variable *U*, from an input *Z* in such a way that *U* is completely uncorrelated with *Y* . In a cryptographic setting, *Z* might refer to a partially random and partially private key string, while *Y* refers to knowledge held by an adversary. Meanwhile, the goal of data compression with side information is essentially the opposite, to determine that part of *Z* which is not correlated with *Y* and to make this part available as the compressed version of *Z*. More specifically, an encoder would like to compress *Z* into a smaller random variable *C* such that a decoder can reconstruct *Z* given both *C* and the side information *Y* .

These two tasks have direct, purely quantum analogues in quantum information theory. Data compression with side information translates into distillation of entanglement between two quantum systems *A* and *B* using only classical communication (the analogue of *C*). The quantum version of PA is the removal of all correlations (both quantum and classical) between *A* and *B* by actions taken only on *A*, such that the density matrix for system *A* is also transformed into a completely mixed state (the analogue of *U*).

Moreover, in the purely quantum realm, the two quantum tasks are dual to one another, a feature, which has been fruitfully exploited to construct a whole family of quantum information processing protocols (Abeyesinghe *et al.* 2009). The duality holds for complementary quantum systems, in the sense that if it is possible to maximally entangle two systems *A* and *B* such that *A* itself is maximally mixed, then it is possible to completely decouple a maximally mixed *A* from the complementary system *R* of *B*, and vice versa (Schumacher & Westmoreland 2002). Two systems *B* and *R* are complementary, relative to system *A*, when the joint quantum state of *ABR* is a pure state, a state which always exists in principle. That is, two systems *B* and *R* are complementary relative to *A* when each one is the purifying system for the other and *A*^{1} .

In this paper, we show that this duality also extends to the hybrid classical-quantum tasks of classical PA against quantum adversaries and classical data compression with quantum side information: the ability to perform one of the tasks implies the ability to perform the other. Here, we are interested in manipulating the correlations between a classical random variable *Z* and a quantum random variable, i.e. a quantum system *B*. Despite, the hybrid nature of the resources, the analysis is still within the realm of quantum information theory, as we can and do imagine that *Z* is produced by measurement of the quantum system *A*.

Complementary quantum systems still constitute an important part of the duality, and compression of *Z* given side information *B* implies PA against *R* and vice versa, just as in the purely quantum case. However, the duality takes on an additional complementary character, as the compression task is not dual to PA of *Z* against *R*, but rather it is dual to PA of a complementary random variable, which we will call *X*, against *R*. Complementary random variables correspond to outcomes of measuring complementary observables, observables like position and momentum for which complete certainty in the outcome of one observable implies complete uncertainty in the outcome of the other. In the present context, if the random variable *Z* is the result of measuring an observable *Z*^{A} on system *A*, then *X* is the result of measuring a complementary observable *X*^{A} on *A*. In what follows we ignore the difference between an observable and a random variable and simply call both *Z*^{A} (or *X*^{A}).

Of course, one of the pillars of quantum mechanics is that both measurements cannot be performed simultaneously. Because analysis of such complementary measurements can quickly become a maze of counterfactuals, let us describe the duality more precisely. We start with a pure quantum state *ψ*^{ABR} describing the three quantum systems *A*, *B* and *R*. Then, we imagine a *hypothetical* *Z*^{A} measurement, say, and then design a protocol for data compression of the resulting classical random variable *Z*^{A} given side information *B*. The protocol itself is real enough, and the duality then states that if we instead perform the *X*^{A} measurement, it is possible to repurpose the compression protocol to perform PA of the classical random variable *X*^{A} against system *R*. The same is true in the reverse direction (modulo the caveats discussed below). We stress that only one of the two conjugate measurements *Z*^{A} or *X*^{A} is ever performed on *ψ*^{A}; we merely contemplate what would be possible had the other measurement been performed.

There are two caveats regarding the duality that should be emphasized. First, we can only establish a duality between protocols in which the PA function or data compression function is linear. This requirement stems from the need to interpret functions applied to *X*^{A} as operations on *Z*^{A} and vice versa. In general, doing so is problematic, as *X*^{A} and *Z*^{A} are complementary observables and, therefore, actions taken on one have unavoidable back actions on the other, but linear functions will offer a way around this problem.

Secondly, the duality does not hold in both directions for arbitrary states of *ABR*. As we shall see, the ability to perform data compression with side information (CSI) implies the ability to perform PA. However, we can only show the converse when *ψ*^{ABR} has one of two simple forms, either *R* is completely correlated with (a hypothetical measurement of) *Z*^{A} or *B* is completely correlated with (a hypothetical measurement of) *X*^{A}. These restrictions and the asymmetry of the duality can be traced back to a recently proven form of the uncertainty principle (Renes & Boileau 2009; Berta *et al.* 2010) and the fact that the uncertainty principle only sets a *lower* limit on uncertainty of complementary observables. Going from PA to data compression implicitly requires an *upper* limit, which we deal with by considering the equality conditions of the uncertainty principle, and these are shown to be exactly the two conditions named above.

The remainder of the paper is devoted to elucidating the duality. In §2, we provide background on the two tasks, how protocols can be constructed using universal hashing, as well as the details of one-shot protocols handling arbitrary inputs and rates that can be achieved in the case of asymptotically many identical inputs. Then in §3, we examine the ‘perfect’ cases, that is, when *Z*^{A} is perfectly recoverable from *B* or *R* is completely uncorrelated with a uniformly random *X*^{A}, and shows that the duality immediately follows from a recently discovered form of the uncertainty principle. The use of the uncertainty principle helps to explain the duality in a simplified setting and to understand the reason for the second caveat above.

As perfect correlation or uncorrelation is difficult to achieve in practice, we are ultimately more interested in the approximate case. In §4, we investigate the duality in the approximate case and show that *R* is approximately uncorrelated with *X*^{A} if *Z*^{A} is approximately recoverable from *B*, and vice versa. This analysis serves as a stepping stone to studying full-fledged CSI and PA protocols, as taken up in §5. Therein we show how CSI protocols using linear hashing can be used to construct, and can be constructed from, linear-hashing-based PA protocols. In the case of protocols designed for inputs consisting of asymptotically many copies of a fixed resource state, the uncertainty principle of Renes & Boileau (2009) and Berta *et al.* (2010) implies that the duality preserves optimality of protocols in that optimal CSI protocols can be transformed into optimal PA protocols, and vice versa. Combined with recent results on one-shot CSI (Renes & Renner 2010), this construction implies a new uncertainty principle formulated in terms of smooth min- and max-entropies, which we discuss in §6 along with additional applications and relations to other work.

## 2. Background

### (a) Classical-quantum states

In order to describe protocols involving hybrid classical-quantum (cq) systems, it is convenient to work within the formalism of quantum mechanics. In this language, a classical random variable *Z*^{A} and quantum side information *S* can be described by the cq state
2.1where *z* are the possible values the random variable *Z*^{A} can take, with alphabet size *d*, *p*_{z} is the probability that *Z*^{A}=*z*, and is the quantum state of *S* conditioned on the value of *z*. The *A* system is effectively classical in the sense that an unconditional measurement in the |*z*〉 basis has no effect on the state; essentially it has already been measured. The measurement defines the *Z*^{A} observable, up to specifying the values of the possible outcomes, i.e. the position of the position observable. In the present context, these values are irrelevant, as we are content with simply enumerating them. The subscript, here *Z*, indicates a cq state and which observable defines the classical basis.

The entropy of the classical random variable *Z*^{A} given the quantum side information *S* is defined by
2.2where is the von Neumann entropy (measured in bits) and is the partial trace over the *A* system.

In general, *ψ*^{AS} can be thought of as the marginal of the pure state |*ψ*〉^{AST}, where
2.3System *T* consists of two parts, *T*_{2} which purifies *S* for each value of *z* and *T*_{1} which purifies *AST*_{2}. Here, we name the systems *S* and *T* instead of *B* and *R* as in §1 because in the subsequent sections *B* and *R* will take on both roles in different contexts.

From the pure state, we can still define the entropy of the classical random variable *Z*^{A} given *S* by first converting back to a cq state. We will make use of the following definition: , and often omit the sub- and superscripts on the state.

### (b) Privacy amplification against quantum adversaries (PA)

Privacy amplification is the art of extracting a truly secret random variable, a secret key, from one partially known to an eavesdropper holding some side information *S*. Functions performing PA are usually called *extractors*, the goal being to produce as much secret key as possible. Privacy amplification against adversaries holding classical information was introduced in Bennett *et al.* (1986, 1988), and was extended to the case of quantum side information in Devetak & Winter (2005), König *et al.* (2005) and Renner & König (2005).

Using equation (2.1), the ideal output of PA would be a state for which *p*_{z}=1/*d* and the are all independent of *z* and equal to one another. This last property implies that for all *z*. Renner & König (2005) introduced an approximate notion of security and uniformity of *Z*^{A}, which is universally composable, meaning that *Z*^{A} can safely be input into any other composable protocol, and the overall protocol is certain to be secure by the virtue of its constituent parts being secure. This definition says that *Z*^{A} is approximately secure if the trace distance to the ideal case is small, where . We will say that *Z*^{A} is *ϵ*-secure if
2.4Use of the trace distance means that the actual *ϵ*-secure *Z*^{A} can only be distinguished from the ideal, a perfect key, with probability at most *ϵ*.

Renner & König (2005) show that PA can produce an *ϵ*-secure key of length (number of bits) ℓ^{ϵ}_{PA}(*Z*^{A}|*S*)_{ψ} given in terms of the smooth min-entropy (Renner 2005):
2.5where *ϵ*=*ϵ*_{1}+*ϵ*_{2}. For a precise definition of the smooth min-entropy, see appendix B.

The upper bound applies to any conceivable PA protocol, and stems from properties of the min-entropy itself. In particular, as remarked in Renner (2005), a secure key has smooth min-entropy roughly equal to its length, and applying the PA function cannot decrease the smooth min-entropy of a variable *Z*^{A}.

Meanwhile, the lower bound is established by constructing an extractor based on *universal hashing*. In this scheme, the approximate key is created by applying a randomly chosen hash function *f* to *Z*^{A}. The function is chosen from a universal family *F* of hash functions, each mapping a size *d* input alphabet to a size *m* output alphabet, such that for any pair of inputs *z*_{1} and *z*_{2}, the probability of a collision of the outputs is no greater than if the function was chosen at random from all functions:
More properly, such a family is called a two-universal family, since the outputs exhibit a weaker form of pairwise independence. Hash families whose outputs are truly pairwise independent are called strongly two-universal, a notion that can be easily extended to *k*-wise independence. In the present context, we shall focus on using linear hash functions, and since the family of all linear hash functions is universal, we can immediately apply the results of Renner & König (2005).

In the asymptotic i.i.d. case of copies of , the min-entropy tends to the more well-known von Neumann entropy, (Tomamichel *et al.* 2009*b*), which implies that in this case, universal hashing can produce approximate keys at the rate
2.6and furthermore, the rate is optimal. These results nicely conform with the intuitive understanding of and *H*(*Z*^{A}|*S*) as uncertainties of *Z*^{A} given the side information *S*; the part of *Z*^{A} unknown to *S* should be roughly of this size, so it is sensible that this amount can in fact be extracted by PA.

### (c) Data compression with quantum side information (CSI)

The problem of data compression with side information, also known as information-reconciliation, is to compress a random variable *Z*^{A} in such a way that it can later be recovered by the compressed version *Z*′ together with the side information *S*. Unlike PA, this protocol has two components, a compressor and a decompressor, the goal of course being to compress the input to as few bits as possible. The case of classical side information was first solved in the asymptotic i.i.d. scenario by Slepian & Wolf (1973), and a one-shot version was given by Renner & Wolf (2004, 2005). The quantum i.i.d. version was studied by Winter (1999) and Devetak & Winter (2003), and recently extended to the one-shot scenario by the present author and Renner (Renes & Renner 2010).

Ideally, compression is not necessary at all and *Z*^{A} can already be recovered from *S*. This situation is represented by a cq state in which the are perfectly distinguishable from one another, and a corresponding measurement of *S* can perfectly reconstruct *z*. A suitable approximate notion is that there should exist some measurement for which the probability *p*_{guess}(*Z*^{A}|*B*)_{ψ} of successfully identifying *z* is large. When there does, we say *z* is *ϵ*-recoverable from *B* in the sense that
2.7

Generally, however, compression is necessary. Bounds on the minimum number of required bits in the one-shot case can be formulated in terms of the dual quantity to the min-entropy, the max-entropy, defined in appendix B. In particular, the minimum number of bits needed to compress *Z*^{A} such that it is *ϵ*-recoverable from *S* and the compressed version is bounded by (Renes & Renner 2010):
2.8again for *ϵ*=*ϵ*_{1}+*ϵ*_{2}. The upper bound is found by constructing a compressor using universal hashing and a decompressor using the so-called ‘pretty good measurement’, while the lower bound follows from properties of the max-entropy. Specifically, if *Z*^{A} is recoverable from *Z*′ and *B*, the conditional smooth max-entropy must be small, and using a chain rule it can nevertheless be shown to be larger than the conditional smooth max-entropy given *B* alone, minus the (logarithm of the) size of *Z*′.

Like the min-entropy, the max-entropy also tends to the von Neumann entropy in the limit of i.i.d. inputs. Defining the rate as in PA, we obtain
2.9which reproduces the results of Devetak & Winter for the asymptotic i.i.d. case. Again this result conforms to the intuitive understanding of the conditional entropies. Since and *H*(*Z*^{A}|*S*)_{ψ} are in some sense *S*’s uncertainty of *Z*^{A}, it is sensible that the compressor would have to augment the decompressor’s information by this amount.

## 3. Duality from the uncertainty principle in the perfect case

We now show that the ideal cases that either *B* is already perfectly correlated with *Z*^{A} or *R* is perfectly uncorrelated with *X*^{A} are already dual by using a recently derived version of the uncertainty principle. Although using the uncertainty principle in this way will ultimately prove insufficient in the approximate case and when attempting to construct one protocol from the other, the analysis here serves to introduce the nature of the duality in a simplified setting, as well as understand the reasons behind the second caveat.

As remarked in §1, the duality between PA and CSI exists for complementary observables *Z*^{A} and *X*^{A}. Let us be more specific and define these observables to be the Weyl–Heisenberg operators and . Since they are not Hermitian, these operators are not observables in the usual sense since the values they can take on are not real numbers. However, they each specify a basis of system *A*, enough to specify two measurements, which is all we need here. The two are related by Fourier transform, since the eigenstates of *X* are simply , where a tilde is used to denote states in the complementary basis. From this relation it is clear that the observables are complementary, as the result of *Z*^{A} measurement on an *X*^{A} eigenstate is completely random, and vice versa.

Now consider a recently discovered form of the uncertainty principle (Renes & Boileau 2009; Berta *et al.* 2010), which quantifies uncertainty by entropy and includes the case of quantum side information,
3.1This holds for arbitrary states *ψ*^{ABR}, pure or mixed. Loosely speaking, it states that the entropy *R* has about the result of measuring *X*^{A}, plus the entropy *B* has about the result of measuring *Z*^{A}, cannot be less than . Note that it is not possible to perform both of these measurements simultaneously, since the associated observables do not commute. Nevertheless, the uncertainty principle constrains what systems *B* and *R* can simultaneously ‘know’ about the results of either measurement.

Let us see how the uncertainty principle can be used to show that perfect *Z*^{A} recovery from *B* implies perfect *X*^{A} security from *R*. Consider an arbitrary pure state |*ψ*〉^{ABR}, which we can write
using the *Z*^{A} basis |*z*〉^{A} or the *X*^{A} basis . In the ideal case, the states are perfectly distinguishable, and therefore *H*(*Z*^{A}|*B*)_{ψ}=0, or equivalently, *p*_{guess}(*Z*^{A}|*B*)_{ψ}=1. By equation (3.1), this implies , which can only occur if all the marginal states are identical. Hence *R* is completely uncorrelated with *X*^{A}. Furthermore, *H*(*Z*^{A}|*B*)_{ψ}=0 also implies that *X*^{A} is uniformly distributed. Since the uncertainty principle holds for any state, we can also apply it to *ψ*^{AB}. This yields , meaning *X*^{A} is uniformly distributed. Thus, *X*^{A} is an ideal key, uniformly distributed and completely uncorrelated with *R*: *p*_{secure}(*X*^{A}|*R*)_{ψ}=0.

We cannot directly make use of the uncertainty principle for the converse, *X*^{A} security from *R* implies *Z*^{A} recoverability from *B*. Assuming the former, we have . But this does not imply *p*_{guess}(*Z*^{A}|*B*)_{ψ}=1 via *H*(*Z*^{A}|*B*)_{ψ}=0 unless the uncertainty principle is tight. As an example, consider the state with *d* = 2, for which *H*(*Z*^{A}|*B*)_{ψ} = *H*(*X*^{A}|*R*)_{ψ} = 1. On the other hand, if the uncertainty principle is tight, then it is immediate that *p*_{secure}(*X*^{A}|*R*)_{ψ}=0 implies *p*_{guess}(*Z*^{A}|*B*)_{ψ}=1.

Thus, we are interested in the equality conditions for equation (3.1). The only currently known conditions are that (at least) one of *H*(*X*^{A}|*R*)_{ψ}, *H*(*X*^{A}|*B*)_{ψ}, *H*(*Z*^{A}|*R*)_{ψ} or *H*(*Z*^{A}|*B*)_{ψ} is zero (Renes & Boileau 2009). Alternately, we can express the equality condition by saying that between the two observers *B* and *R* and the two observables *Z*^{A} and *X*^{A}, one of the guessing probabilities must be unity.

For completeness, we briefly recapitulate the argument here. Consider the case that *H*(*Z*^{A}|*B*)_{ψ}=0, which immediately implies . Since is also an upper bound to the conditional entropy, it must be that and the equality conditions are met. The same argument can be made starting from *H*(*X*^{A}|*R*)_{ψ}=0. The remaining two quantities *H*(*X*^{A}|*B*)_{ψ} and *H*(*Z*^{A}|*R*)_{ψ} are related by the complementary form of the uncertainty principle, obtained by interchanging either the complementary observables *X*^{A} and *Z*^{A} or the complementary systems *B* and *R*. The derivation in Renes & Boileau (2009) simultaneously produces both forms of the uncertainty principle, meaning that satisfying the equality conditions for one implies the same for the other. Thus, the conditions *H*(*X*^{A}|*B*)_{ψ}=0 and *H*(*Z*^{A}|*R*)_{ψ}=0 also lead to equality in equation (3.1).

Observe that in the former case of *H*(*X*^{A}|*B*)_{ψ}=0 and we end up with *H*(*X*^{A}|*B*)_{ψ}=*H*(*Z*^{A}|*B*)_{ψ}=0, which is a sufficient condition to have maximal entanglement between *A* and *B*, as discussed in Renes & Boileau (2008). In the other case, we end up with *H*(*Z*^{A}|*B*)_{ψ}=*H*(*Z*^{A}|*R*)_{ψ}=0 and , a situation exemplified by the *d*=2 GHZ state .

## 4. Duality in the approximate case

In this section, we examine the duality when *Z*^{A} is approximately recoverable from *B* or *R* is approximately independent of a nearly uniform *X*^{A}. Unfortunately, the arguments using the uncertainty principle in the previous section cannot easily be modified to work in the approximate case, so here we present a more algebraic treatment. We start with *Z*^{A} recovery implies *X*^{A} security.

### Theorem 4.1

*For an arbitrary pure state |ψ〉*^{ABR}*, suppose p*_{guess}*(Z*^{A}*|B)*_{ψ}*≥1−ϵ. Then* *.*

### Proof.

Start by performing the measurement coherently with a partial isometry and an ancillary system *M*. This transforms the state according to
The ideal output would be
and computing the fidelity between the two we find
Here, we have used the fact that for . Now rewrite *ξ* using the complementary basis in anticipation of measuring *X*^{A}. The result is
In the last line we have implicitly defined the state |*ψ*〉^{MBR}, which is just |*ψ*〉^{ABR} with *A* replaced by *M*. It is easy to work out that the result of measuring *X*^{A} and marginalizing over *BM* is the ideal output of PA of *X*^{A} against *R*, namely
Since |*ψ*〉^{ABR} and |*ψ*′〉^{ABMR} are related by the isometry , measuring *X*^{A} and tracing out *BM* results in the same output for both input states. And because the fidelity cannot decrease under such a quantum operation (see appendix A), this implies
Finally, from equation (A7) we have . ■

As discussed in §3, there are two routes from *ϵ*-security of *X*^{A} against *R* to *ϵ*-recovery of *Z*^{A} from *B*. The first case, *p*_{guess}(*X*^{A}|*B*)_{ψ}=1, was implicitly used by Devetak & Winter (2005) in their construction of an entanglement distillation protocol achieving the so-called hashing bound. The second case, *p*_{guess}(*Z*^{A}|*R*)_{ψ}=1 has not, to our knowledge, been previously studied, but is more natural in the data compression scenario as it enforces the cq nature of the *AB* state.

### Theorem 4.2

*If |ψ〉*^{ABR} *is such that p*_{secure}*(X*^{A}*|R)*_{ψ}*≤ϵ and either (a) p*_{guess}*(X*^{A}*|B)*_{ψ}*=1 or (b) p*_{guess}*(Z*^{A}*|R)*_{ψ}*=1, then* *.*

### Proof.

Start with case (a), whose condition implies that |*ψ*〉^{ABR} takes the form
where *B*=*B*_{1}*B*_{2}. Tracing out *B* gives the cq state , and the condition *p*_{secure}(*X*^{A}|*R*)_{ψ}≤*ϵ* implies by equation (A7). Observe that
using the definition of fidelity and the cq (block-diagonal) form of the states for the first equation and Uhlmann’s theorem, with corresponding isometries for each state , for the second. The state |*ψ*〉^{MB′R} is the same as |*ψ*〉^{ABR} with *A* replaced by *M* and *B* by *B*′. Now define
and observe that . Hence, *F*(|*ξ*〉^{ABR},|*ψ*〉^{ABR})≥1−*ϵ*, and converting to trace distance, we find .

Applying the conditional isometry
to |*ξ*〉^{ABR} yields , and converting the result back to the |*z*〉 basis gives , where arithmetic inside the state vector is modulo *d*. Thus, the measurement
enables perfect recovery of *z* from *B* for the state *ξ*^{ABR}. But the measurement is a quantum operation, which cannot increase the trace distance, and the trace distance after a measurement is simply the variational distance of the resulting probability distributions. Therefore, we can infer that
Working out the left-hand side of this equation, we find that .

Now consider case (b), whose condition implies |*ψ*〉^{ABR} can be written
Using the complementary basis for *A* gives the alternate form
4.1where in the last line we have implicitly defined the state |*θ*〉^{BR}. Observe that *ψ*^{R} is invariant under the action of (*Z*^{x})^{R1}, since . Next, compute the fidelity of with , using the definition :
The first equality follows from the cq form of the states, while to get to the last line we have used the unitary equivalence of the fidelity. Again *p*_{secure}(*X*|*R*)_{ψ}≤*ϵ* implies . Since we now have *F*(*θ*^{R},*ψ*^{R})≥1−*ϵ*, it follows by Uhlmann’s theorem that there exists an isometry such that . Now consider the state
from which *z* can obviously be recovered by measuring *M*. The overlap of this state with is just *F*(*θ*^{R},*ψ*^{R}), so we should expect *p*_{guess}(*Z*|*B*)_{ψ} to be large when using the measurement
Indeed, converting the fidelity to trace distance and working out the variational distance just as before yields . ■

## 5. Duality for protocols

Having worked out the duality for states displaying approximate recoverability or secrecy, we can now begin investigating how the duality works for protocols designed to transform arbitrary input states into such a form. Since the duality concerns transforming operations on *X*^{A} into operations on *Z*^{A} and vice versa, we first face the problem that operations on one necessarily affect the other in some way. By confining our analysis to PA and CSI protocols in which the outputs are linear functions of the inputs, we may avail ourselves of the stabilizer formalism, and this will enable us to ensure the back action from *X*^{A} operations is consistent with the *Z*^{A} transformation we wish to implement, and vice versa. A short description of those aspects of the stabilizer formalism needed here is given in appendix C. We begin with the case of repurposing data compression into PA, as it is more straightforward.

### Theorem 5.1

*Let* *be a protocol for compressing of Z*^{A} *to a string C of* *bits via a linear compression encoding map* *. If Z*^{A} *is ϵ-recoverable by the decoding map* *, then the encoder can be repurposed to extract* *-secure bits from X*^{A} *which are uncorrelated with R.*

### Proof.

First we embed system *A* into an integer number of qubits. Then, using the encoding map *f* we can define a subsystem decomposition using as detailed in appendix C. This enables us to write the input state |*Ψ*〉^{ABR} as

Since **z** is *ϵ*-recoverable from the combined system by definition of the protocol, theorem 4.1 applies. Therefore, , the result of measuring encoded operators on is *ϵ*-secure against *R*. But , for *g*_{⊥} related to *f* as in appendix C, so *g*_{⊥} defines a key extraction function. As *f* outputs a -bit string, the output of *g*_{⊥} must be a string of bits. ■

Now we take up the converse. Again case (a), like that of theorem 4.2, is similar to results found by Devetak & Winter (2005), though, because they do not use linear functions, they cannot directly interpret their use of PA as data compression of an independently defined complementary observable. We shall return to this issue at the end of this section. Reiterating the statement made prior to theorem 4.2, case (b) is more naturally suited to the data compression with side information scenario, whose input is the cq state by assumption.

### Theorem 5.2

*Let* *be a protocol for PA of X*^{A} *against R consisting of a linear extraction map* *and let the input be a pure state ψ*^{ABR} *such that either (a) p*_{guess}*(X*^{A}*|B)*_{ψ}*=1 or (b) p*_{guess}*(Z*^{A}*|R)*_{ψ}*=1. If* *produces ℓ*^{ϵ}_{PA} *ϵ-secure bits, then the extraction map can then be used to define a compressor and corresponding decoding map which together can be used to compress Z*^{A} *to* *bits such that Z*^{A} *is* *-recoverable from the side information B and compressed version C.*

### Proof.

Start with case (a). Again we embed system *A* into bits for simplicity. The input state has the form
5.1where we have used the subsystem decomposition from and suppressed the dependence of **x** on . By assumption is *ϵ*-secure against *R*. Thus, theorem 4.2 applies to the division , and there exists a measurement such that is -recoverable from .

Since is not directly available to the decoder, we must break the measurement down into a compressor with classical output and subsequent measurement of *B* alone, conditional on the output. To do this, suppose is measured in the *Z* basis, producing , which results in the state
with probability 1/(*d*^{A}−ℓ^{ϵ}_{PA}). All dependence drops out when tracing out the *B* systems, so the marginal states of *R* conditional on are the same as in equation (5.1). Therefore, theorem 4.2 implies is *ϵ*-recoverable from *B* alone for each value of . Since the pair fixes the value of **z**, is a suitable compression map enabling *ϵ*-recovery of **z** from *B* and *C*=*f*_{⊥}(*Z*^{A}).

Now consider case (b), whose input state is of the form 5.2

Here, we have converted to the alternate form in the second equation, following equation (4.1), with . For the third equation, we again use the subsystem decomposition for as well as . By assumption, is *ϵ*-secure against *R*, so just as for case (a) theorem 4.2 applies to the division and implies there exists a measurement such that is -recoverable from .

This measurement can be broken down into a compression map with classical output followed by measurement of *B* alone following the technique used in the previous case. This time, we model the measurement quantum-mechanically, as the transformation . However, from equation (5.2) it is clear that the same effect can be achieved by the transformation followed by . In other words, there is no need to distribute to *R*, since *R* already has a copy. Thus, the effect of the measurement is simply to transfer to *C*. Using the function as the compressor, therefore, ensures that , and hence **z**, is *ϵ*-recoverable from (*B*,*C*).

In both cases *f*_{⊥}, outputs bits when *g* outputs , completing the proof. ■

## 6. Discussion and applications

The reasons for restricting attention to linear hashing techniques in this analysis should now be more understandable. Since the duality between PA and CSI is meant to hold for complementary observables, it is not a priori clear that, e.g. a given PA function applied to *X*^{A} has a well-defined action on *Z*^{A}, let alone the desired one. However, the use of linear hashing to deal with this problem is only shown here to be sufficient, not necessary, and it would be nice to understand more precisely under what circumstances the duality holds.

This issue is somewhat subtle, and deserves further comment. By the results in §4, once, say, PA of *X*^{A} against *R* has been performed, it is certainly possible to define an appropriate complementary observable *Z*^{A} so that it is recoverable from *B*. However, this observable generally has nothing whatsoever to do with a complementary observable that we might have defined for the input to the PA procedure, and in particular, the two need not commute so as to be simultaneously well defined. For instance, in Devetak & Winter (2005), PA is used as the second step of an entanglement distillation protocol. Since the output is entangled, both *X*^{A} and *Z*^{A} complementary observables are recoverable from *B*. But these observables have nothing to do with complementary observables one would have defined for the *input* to the protocol, so one cannot say the PA procedure performs CSI. Thus, while *ϵ*-security of *X*^{A} and *ϵ*-recovery of *Z*^{A} always go hand in hand, it does not follow from that alone that PA and CSI protocols necessarily do, too. On the other hand, in many situations in quantum information processing, such as in Devetak & Winter (2005), this distinction is not important.

Perhaps, the most direct application of our results is a general entropic uncertainty relation formulated in terms of the smooth conditional min- and max-entropies^{2} . Using the upper bound of equation (2.8), theorem 4.1, and the upper bound of equation (2.5) for an input system whose dimension *d* is a power of two, we immediately obtain
6.1for *ϵ*=*ϵ*_{1}+*ϵ*_{2}. From the definition of the smoothed conditional max-entropy it follows that for *ϵ*′≥*ϵ*, so if we choose *ϵ*_{1}=*ϵ*_{2}=*ϵ*/2 and *ϵ*=*δ*^{4}/8, the above expression can be transformed into the more appealing form
6.2This extends the recent work on uncertainty principles valid in the presence of quantum memory (Renes & Boileau 2009; Berta *et al.* 2010) to the smooth min- and max-entropy. Owing to the operational interpretations of these quantities (König *et al.* 2009), this relation should be useful in the analysis of quantum information processing protocols.

Another application of this work is to a new approximate quantum error-correcting condition. This will be explored more fully in a future publication, but we can already give a brief overview here. Essentially, the quantum decoupling condition of Schumacher & Westmoreland (2002) mentioned in §1 can be broken down into two classical pieces. This condition states that *AB* is maximally entangled when *A* is completely uncorrelated with the purification system *R*, and it is in a completely random state. Approximate quantum error-correcting procedures can then be constructed by approximately decoupling *R*. The entanglement distillation procedure of Devetak & Winter (2005) implicitly gives a different characterization, saying that *AB* is maximally entangled if *Z*^{A} is recoverable from *B* and secure from *R*. Using the duality of these recoverability and security notions, there are, in principle, two other equivalent characterizations of approximate entanglement, from which approximate quantum error-correcting procedures can likewise be constructed. The first one states that *AB* is maximally entangled if both *X*^{A} and *Z*^{A} are recoverable from *B*, a condition which was implicitly explored in Renes & Boileau (2008). The second is the classical decomposition of the quantum decoupling condition, that *AB* is entangled if both *X*^{A} and *Z*^{A} are secure from *R*, with the additional proviso that one of them, say *X*^{A}, is secure not just from *R*, but from *R* together with a copy of *Z*^{A}.

## Acknowledgements

J.M.R. acknowledges useful discussions with and careful reading of the manuscript by Mark M. Wilde and Matthias Christandl. Financial support was provided by the Center for Advanced Security Research Darmstadt (www.cased.de).

## Appendix A. Fidelity and trace distance

Here, we recount some facts about the trace distance and fidelity. Proofs can be found in, e.g. (Nielsen & Chuang 2000). The trace distance *D*(*ρ*,*σ*) between two quantum states *ρ* and *σ* is defined by
A 1where . It is invariant under unitary operations on the inputs and cannot increase under trace-preserving quantum operations. In particular, if a measurement *Λ*_{k} yields outcome *k* with probability *r*_{k} for *ρ* and *s*_{k} for *σ*, then the trace distance bounds the variational distance of the two distributions
A 2Moreover, the trace distance is the largest probability difference the two states *ρ* and *σ* could assign to the same measurement outcome *Λ*,
A 3Therefore, if the trace distance between *ρ* and *σ* is small, they behave nearly identically under all measurements.

Meanwhile, the fidelity *F*(*ρ*,*σ*) is defined by
A 4and it, too, is invariant under unitary operations on the inputs and monotonic under trace-preserving quantum operations, in this case increasing. By Uhlmann’s theorem, the fidelity of two mixed states is related to the fidelity of their purifications. If |*ψ*〉^{QR} is a purification of *ρ*^{Q} and likewise |*φ*〉^{QR} is a purification of *σ*^{Q}, then
A 5and
A 6for *U*^{R} a unitary on the purifying system *R*. If this purifying system is different for the two states, say |*ψ*〉^{QR1} and |*φ*〉^{QR2}, then the maximization is instead over partial isometries taking *R*_{2} to *R*_{1}.

The trace distance and fidelity are essentially equivalent measures of closeness of two quantum states, via A 7

## Appendix B. Smooth entropies

The smooth min- and max-entropies were first introduced by Renner & Wolf (2004, 2005) for the classical case in order to characterize information processing protocols beyond the usual asymptotic i.i.d. scenario to cases where the input random variables or channels are essentially structureless. They were subsequently extended to the quantum case by Renner (2005) and Renner & König (2005), and have undergone several additional refinements. Here, we follow the definitions given in Tomamichel *et al.* (2009*a*).

First, the conditional min-entropy for a state *ρ*^{AB} is defined by
B 1with . Dual to the conditional min-entropy is the conditional max-entropy, defined by
B 2The two are dual in the sense that, for *ρ*^{ABC} a pure state, (König *et al.* 2009).

Each of these entropies can be *smoothed* by considering states in the *ϵ*-neighbourhood of *ρ*^{AB}, defined using the purification distance ,
B 3

Note that the purification distance is essentially equivalent to the trace distance, owing to the bounds , which are just a reformulation of equation A7. The smoothed entropies are then given by
B 4and
B 5Furthermore, the dual of is , so that taking the dual and smoothing can be performed in either order (Tomamichel *et al.* 2009*a*).

## Appendix C. CSS stabilizer formalism

The stabilizer formalism developed by Gottesman (1997) in the context of quantum error-correction is perfectly suited to describing the effects of applying linear functions to the complementary observables *X*^{A} and *Z*^{A}. In fact, here, we will only need a subset of these results, for so-called Calderbank–Shor–Steane (CSS) stabilizers. Here, we give an exceedingly brief overview; for more details see Nielsen & Chuang (2000).

For simplicity, fix *d*=2; the resulting statements actually apply for any *d* which is a power of a prime number. Starting with a collection *A* of *n* two-dimensional quantum systems *A*_{1},…*A*_{n}, suppose we would like to apply a linear function to the result **z** of measuring each system *A*_{i} in the *Z* basis. Since the function is linear, each output bit is the result of computing the inner product of **z** with a fixed binary string **h**_{j}, *f*(**z**)_{j}=**z**⋅**h**_{j}. But then the *j*th output bit is nothing other than the result of measuring the operator , where *h*_{j,k} is the *k*th component of the vector **h**_{j}. As much holds for *X* by Fourier symmetry.

It can be shown that given *m* linearly independent vectors **h**_{j}, the resulting (commuting) operators *stabilize* a subspace of dimension 2^{k}, with *k*=*n*−*m*, meaning that there exist 2^{k} linearly independent common eigenvectors of the set. Therefore, a basis for the space translates into a basis for the space and the operators form a complete set of commuting observables, to use language more familiar in quantum mechanics. Any basis will do, and indeed the usual decomposition of as *n* copies of just corresponds to the basis of vectors defined by components *e*_{j,k}=*δ*_{j,k}.

Moreover, the algebra of carries over into the commutation relations between *X*-type stabilizers and *Z*-type stabilizers. Since *XZ*=−*ZX*, it follows immediately that
C 1This condition can be used to define encoded qubits and corresponding anticommuting encoded *X* and *Z* operators. The *X* and *Z* operators of the physical qubits are such that each anticommutes with just one of the , namely *j*=*k*, and commutes with all the others. This can be extended to an arbitrary basis **h**_{j} by finding its dual basis **g**_{k} for which **g**_{j}⋅**h**_{k}=*δ*_{j,k}. Each pair (**g**_{j},**h**_{j}) then corresponds to a pair of encoded (*X*,*Z*) operators.

Suppose *f*(**z**) is a linear function for which the corresponding set of vectors is linearly independent. This set we can take as defining a basis for the corresponding subspace in , and this basis can be completed by finding a basis of *n*−*m* vectors for the complementary subspace. The complementary basis defines its own function, *f*_{⊥}. Since together *f* and *f*_{⊥} make up an invertible function (the associated matrix is invertible), a string **z** can just as well be characterized by the pair (*f*(**z**),*f*_{⊥}(**z**)). Calling these outputs and , respectively, we can regard **z** as a function of the pair .

The stabilizer construction allows us to apply this transformation to the state vectors of the *n* qubits as well, meaning that we can relabel the basis states . That is, using the stabilizers we can perform arithmetic inside the kets in a meaningful way. And it respects the tensor product as well, meaning for a system *A* of *n* qubits we can use the collection of encoded operators for *f* to define a subsystem and those for *f*_{⊥} to define a subsystem , so that together . Or, more compactly, .

Finally, we can now see that this formalism controls the back action from applying *f* on *Z*^{A} to the complementary operators *X*^{A}. In the above decomposition of *A* into and , we are still free to switch to the complementary basis in either subsystem, and in doing so we go from *f* (*f*_{⊥}) to *g* (*g*_{⊥}). If we convert to the *X* basis, then the resulting basis describes the possible simultaneous *f*(**z**) and *g*_{⊥}(**x**) outputs, even though **x** and **z** do not exist simultaneously.

## Footnotes

↵1 In the communication scenario complementary systems become complementary channels. An arbitrary channel taking

*A*to*B*can be thought of as an isometry taking*A*to*BR*by the Stinespring dilation, and considering only the*R*portion of the output defines the complementary channel to .↵2 That such a consequence ought to hold was pointed out by Matthias Christandl.

- Received August 24, 2010.
- Accepted November 19, 2010.

- This journal is © 2010 The Royal Society