QIP 2009 Day 1 Liveblogging

QIP 2009 started today in Santa Fe, NM. Since the conference organizers have seen it wise to include wireless access, what better excuse for a bit of liveblogging.

Andrew Landahl gave us a nice introduction to QIP and explained the New Mexico State question (I’m thinking of starting a movement in California to have a state answer. If you’ve ever lived in California, you’d understand.) He mentioned that New Mexico has a spaceport, but forgot to ask if anyone arrived yesterday via the spaceport. Anyone? Rosewell?
Then….let the talks begin!

Matt “Michael Phelps” Hastings, “A counterexample to additivity”

Matt gave a talk (one of two at QIP, hence the nickname) based upon his recent result showing that Holevo capacity is not additive. Here is the paper arXiv:0809.3972, also see this blog post. Matt put up a quote from J. Pierce who wrote in 1973 (From “The early days of information theory” Pierce, J., IEEE Transactions on Information Theory, 19, p3, 1973):

I wish that physicists would stop talking about reformulating information theory and would give us a general expression for the capacity of a channel with quantum effects taken into account rather than a number of special cases

Matt’s main result is that the Holevo capacity is not additive. This implies that, in some strong sense, physicists (and computer scientists, and information theorists…we’re all in this together, right?) have not satisfied Pierce’s criticism. Amusingly, Matt left off the first part of that quote

I think that I have never met a physicist who understood information theory.

I guess this is understandable, given the company, which consists of a number of physicists who damn well understand information theory!
Matt gave a good overview of his counterexample. He also interestingly suggested that, while explicitly giving an experiment which shows this counterexample is, um, experimentally a stretch, that it would be interesting to test for violations of the p-norm multiplicativity conjecture experimentally (which is the work that helped set the basis for Matt’s counterexample. See here for a lead into this work.)
Matt also conjectured that “operational non-additivity held.” Basically this is that the regularlized capacities are not additive, and would be a step beyond what has been shown.

Patrick Hayden and Andreas “straight up the mountain” Winter (speaker) ” The fidelity alternative and quantum measurement simulation”

Andreas talked about a process he called quantum identification. Unfortunately my eyes are now about to fall out of my head due to the fact that the slides were hand written and don’t show up too well on the monster screen here at the Santa Fe Convention center. Quantum identification is: Alice has her quantum state sends it through a channel to Bob, who then performs a restricted class of measurements. These measurements are “identifying measurements:” binary measurements which represent a projection onto a state and a projection onto the orthogonal subspace. The idea here is that you would then like to simulate this scenario, not, for example full measurements or say measurements in a computational basis, etc. Or at least I thought this was what was going on! Andreas related this to something he called the fidelity alternative and also discussed the optimal rate that quantum states can be identified through a noisy quantum channel.

Sergey Bravyi (speaker) and Barbara Terhal “A no-go theorem for a two-dimensional self-correcting quantum memory based on stabilizer codes”

A talk near and dear to my heart. Portions of this work are described in arXiv:0810.1983.
A self-correcting quantum memory is, roughly, a quantum system where error correction is performed naturally. One way to imagine doing this is by having an many-body quantum system where the energy eigenstates are quantum error correcting codewords and where the energy of an error grows like the perimeter of the erred region. Sergey and Terhal have shown certain constraints on how this can be achieved in different spatial dimensions under different assumptions about the way that this is achieved.
One of the main theorems Sergey discussed was the following

Theorem: Any stabilizer code with r-local generators on a lattice of dimension D has at least one logical operator whose support can be covered by a D-dimensional box of size r times L^{D-1}

This means, for example, that at least one logical operator in a one dimensional system, must is constant size. For two dimensions, the logical operator is of dimension one (a string.) And for three dimensions, the logical operator is of dimension two. In other words, if one is going to construct a self-correcting system using a Hamiltonian made up of stabilizer elements (a la the toric code) one needs to work in spatial dimension at least three. No such setup is known, however. Finding an example or proving that it is not possible is an important open question. (Bets anyone?) The paper linked above contains the details of the proof of this. Bounds for subsystem codes and their distance are also derived, but these don’t lead to bounds on subsystem code based Hamiltonians, because the energy gap in these systems is not as easy to understand.
In the second half of the talk Sergey talked about new constructions (no paper yet) they have for building good classical codes in two spatial dimensions using cellular automata based construction. In particular Sergey showed a classical code of with 3-local check operators which was a [L²,L,L^log₂3] code. Further examples boost the exponent in the distance closer to two as a function of increasing the size of the check operators. They conjecture that they can obtain [L²,L,L^2-x] for any constant x. Notice that this is much better than that achieved by the two dimensional repetition code as embodied by the two dimensional Ising model.

Dmitry Gavinsky, “Predictive quantum learning”

Dmitry discussed his results in predictive quantum learning which appear in arXiv:0812.3429 To quote the abstract

We give an example of a relational concept class that is efficiently learnable in certain quantum analogue of the PAC model, while in any classical model exponential number of examples would be required.

Unfortunately I was too busy liveblogging to get all of the details of Dmitry’s results, and damn that sucks because these sound interesting.

Lunch

mmmm. Oh, and I forgot to mention. All the QIP talks will be online at some point. Yeah for modern technology!

Graeme Smith “Quantum communication with zero-capacity channels”

Graeme described his work with Jon Yard showing how two zero-capacity quantum channels can be used in tandem to yield a non-zero-capacity quantum channel. Dude, this year has not been good for additivies 🙂 Paper: arXiv:0807.4935. Old blog post: here. Note that no puppies were harmed during Graeme’s talk, but he said he would harm a particular puppy for a complete characterization of the quantum capacity. Graeme and Jon’s work is, of course,

John Smolin (speaker) and Graeme Smith, “Can non-private channels transmit quantum information?”

John began by explaining the stages of grief and how this relates to the demolishing of the two additivity questions (described above.) He also showed a picture of a certain interesting way to achieve computer privacy…similar to those fond here:
The work John talked about is described in arXiv:0810.0276. The private channel capacity is the capacity of a quantum channel to transmit classical information in the setting where the eavesdropper learns arbitrarily little about the information being transmitted. One would think that if a channel has a small private capacity, then it wouldn’t be good for transmitting quantum information. In this talk John gave evidence that this isn’t true: that there are channels which have large quantum capacities when used together but have very small private channel capacities used individually or there is a monster violation of Holevo additivy (what Matt talked about earlier.) Worrying about this John paraphrased Charlie Bennett as saying “Maybe if you prove one of two different things are interesting, then you haven’t really shown anything interesting at all.”