# A fistful of complementarity

New paper time! Today’s entry, arXiv:1003.0703 is a fistful of complementarity, even though it’s billed as showing that two fundamental quantum information processing tasks, privacy amplification and data compression with side information, are equivalent in the sense that being able to do one means that you can do the other, too.

First let me remind you what these two tasks are all about. In privacy amplification we start with a classical random variable X which is correlated in some way with a quantum system E, and the goal is to transform X into a uniform random variable U (i.e. extract randomness) while also decorrelating U from E. Thinking of E as held by an eavesdropper, this process makes X into a secret random string, and if X is shared by two parties Alice and Bob, then they end up with a secret key. Following the maxim that “all you need is love random hashing”, U can be generated by taking the output of a random hash function applied to X. In data compression with side information we start in the same place, though now we call the classical variable Z and the quantum system B (held by Bob). The goal here is to generate a compressed version of Z, call it C, such that Bob can recover Z from B and C together. The quantum system B functions as side information about Z, and reduces the minimum size of C. As you might suspect, it turns out that C can be generated from Z again by random hashing.

These tasks show up all over the place in classical and quantum information theory as building blocks for other protocols. And in the quantum setting they are essentially the same thing! For this to work, we have to somehow get the two tasks into the same scenario (i.e. derive their settings from a single quantum state), which we can do as follows. First, we let X be generated from quantum system A, held by Alice, by measuring in some basis. Then Z is generated by measuring in a complementary basis, complementary in the sense that the overlap^2 between the elements of the two bases is 1/d, for d the dimension of Alice’s system. Second, we let the global quantum state of ABE be a pure state, so that B and E are complementary systems, at least from Alice’s point of view: each one is the purification of the other+A. Now we get to the punchline. If Alice can perform privacy amplification of X against E, then by modifying the hash function appropriately, she can instead perform data compression of Z with B as side information, and vice versa! So if you go to all the trouble of constructing a protocol to do one of these tasks, you can make a few simple modifications and get a protocol for the other task, involving the complementary measurement and the complementary system.

There are, of course, a few caveats to worry about, all of which are covered in the paper. But I should point out one nice consequence of this result: a much simplified proof of the Holevo-Schumacher-Westmoreland theorem on the rate at which classical information can be transmitted over quantum channels. Without going into all the details, that task is the sort of “dynamic” analog to the “static” data compression with side information task — Alice now gets to choose the classical inputs to the channel, but the overall input-output state is described by the pair (Z,B). Therefore, instead of trying to construct this protocol directly, we could instead just construct a privacy amplification protocol for the appropriate complementary measurement and complementary system. This is considerably easier, since all we need to find is the right type of hash function. Most of the difficulty in the HSW theorem is coming up with a decent decoding operation Bob can use to get Z from B and C. But by the magic of something called Uhlmann’s theorem, given that the privacy amplification protocol works, such a decoder must exist. This spares us the trouble of actually having to get our hands dirty and construct it.