The Quantum Pontiff

Having some glitches publishing, so am trying to split up the posts.

Continuing on the quantum information theory beat:

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 found 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."

Ashley Montanaro (speaker) and Tobias Osbourne "Quantum Boolean functions"

Relevant paper arXiv:0810.2435. Much is known about good old Boolean functions. A Boolean function is a map from n bits, {0,1}ⁿ, to a single bit {0,1}. What is the quantum equivalent of a Boolean function. Ashley and Tobias define the quantum equivalent as a unitary on n qubit whose eigenvalues are all +1 or -1. In this talk Ashley described how using this definition of a quantum Boolean function one can obtain a bunch of interesting results related to what is known about classical Boolean functions.

One problem they attack is a method to test whether a given quantum Boolean function is close to a tensor product of Pauli matrices or not. This, they call quantum property testing and is a generalization of similar property testings in the classical case.

Another part of this work is the "Quantum Goldreich-Levin algorithm" which gives a way to approximately learn quantum dynamics. Upon hearing this a fellow conference attendee leaned back and said "best named algorithm ever." For the reason why see arXiv:quant-ph/0507242.

Yi-Kai Liu, "Quantum algorithms using the curvelet transform"

Paper here: arXiv:0810.4968. Yi-Kai talked about using the curvlet transform in quantum algorithms (wait, wasn't that just the title, doh.) In particular he talked about two problems. One was, given a uniform quantum distribution over a sphere in Rⁿ find the center of this sphere to within a constant fraction of the radius. Yi-Kai showed how to do this using a single quantum queries (with an efficient quantum algorithm) but how the equivalent classical problem (where one is allowed to sample once from a classical distribution) succeeds only with exponentially small probability. The second problem he showed how to solve was given oracle access to a function that is radial around some unknown point in Rⁿ, find the point to within D in time poly(log(1/D)) assuming that f doesn't "fluctuate" too much.

Dave Bacon, Wim van Dam (speaker), and Alexander Russell, "Analyzing quantum circuits using the least action principle"

Wim told us that this talk was subtitled: "Physicists getting lucky...once again." Draft of the paper is available here.