Yes we work on Saturdays. Okay work may be the wrong word. Updated as the day goes along and my brain doesn’t fill up (plus I’m chairing a session, so is it ethical to chair and blog at the same time?)
The first talk of the morning was by Edward Farhi. Farhi talked about the NAND tree algorithm (see the Optimizer along with quant-ph/0702144 and its plethora of follow up works.) This was only the second computer talk Farhi has given. That’s right, hell has frozen over, and MIT physic professors have given up transparencies and are now using computers. I feel like an era has come to pass.
Many of you have probably seen or heard Farhi talk about the NAND tree algorithm. Of course one issue that always comes up is “why the hell does this thing work!” and “how did they find this algorithm.” The answer to the later was that they were just looking at quantum walks on trees and noticed the recurrences which are at the heart of the NAND tree algorithm. When I think about why this algorithm works these days, I think the paper of Reichardt and Spalek, 0710.2630 goes a long long way to understanding why the simple binary tree structure gives rise to the NAND tree algorithm.
The next speaker was Jon Yard who talked about quantum algorithms for knot and link polynomials. Now most people probably zone out when they see a talk about knot and link polynomials, but I always feel like I know just enough to hope I will make it through the talk. Luckily for me, for Jon’s talk this was true. Jon talked about the Jones, HOMFLYPT, and Kaffman polynomials with trace and platt closures and quantum algorithms to approximate these polynomials. The question I asked Jon was kind of in left field, but was something I hadn’t thought about before. I’ll reproduce it after the coffee break.
Mmm coffee. Okay the question. Now I’ve spent a lot of time with SU(d) and the symmetric group. So here is something I know about these groups, actually I’ll just stick to SU(2). Irreducible irreps of SU(2) are label by a non-negative integer (which physicist call twice the total angular momentum.) If you take an irrep of SU(2) labeled by k and an irrep of SU(2) with integer label 1, and look at the diagonal action of these irreps, then this representation of SU(2) breaks down into two irreps, one with label k+1 and one with k-1. (If k=0, then you get just one irrep and it is labeled by 1.) We might write this as k times 1=(k+1) + (k-1) Now suppose that you start with k=1 irrep and perform this action four times. Then you’ll find that the possible irrep labels are 0,2,4,6. Lets focus on that lowest irrep label. There were two ways to obtain this value. One took 1 times 1 and produced 0, then took 0 times 1 and produced 1, and then took 1 times 1 and produced 0. The other took 1 times 1 and produced 2, then took 2 times 1 and produced 1, and finally took 1 times 1 and produced 0. What this means is that the 0 irrep appears on these four qubit twice, i.e. the irrep is two fold degenerate. Now one interesting proprety of this subspace (which is two dimensional) is that it is an error detecting code. Further this subspace is acted upon nontrivially by the action of exchanging qubits.
Okay so here is what I asked Jon. When dealing with, say, the unitary representations of the braid group that appear in the Jones polynomial, then you have a similar structure for the irreps but now for a truncated version of SU(2) (i.e. there is a total angular momentum upone which you cannot go any higher than.) In quantum algorithms for evaluating the Jones polynomial, one has a way to take a bunch of qubits, and upon them enact unitaries which give irreducible representations of the braid group. So, for example, if you talk about four particles, there is a way to take a bunch of qubits and enact unitaries which act as irreps of the braid group over a two dimesional subspace. My question was then, does this subspace, similar to the SU(2)/symmetric group case act as an error detecting code?
Following Jons talk (and me fixing my spelling of his name on the blog) David Meyer talked about when a single quantum query doesn’t give you any advantage over a single classical query.
Okay, now this is embarassing. I was looking forward to the next two experimental results by Raymond Simmonds and Jason Amini. But Cris Moore asked me a question, and then we saw Howard Barnum and pretty soon a group of us thought we knew how to efficiently solve graph isomorphism. A full lunch time later, the idea had been shot down, but for a few hours there was hope. So unfortunately I don’t know what Simmonds or Amini talked about which is too bad because I was really looking forward to these talks. Anyone attending care to comment?
Robert Raussendorf spoke in the afternoon measurement based computing on the toric code states. Robert showed (in joint work with Sergey Bravyi) that measurements on the toric code state can be effeciently simulated classically. The way he did this was by a nice map to the planar Ising model with no magentic field.
Barry Sanders talked about implementing a quantum random walk on a circle in phase space via a superconducing qubit. This walk is on phase space,in other words you could think about this state as being a coherent state and the walk is on a circle in phase space of a lattice of coherent states. The proposed system for this quantum walk is a superconducting qubit coupled to a microwave cavity (i.e. circuit QED.) The walk is on the phase space of the microwave cavity field and the atom serves as the coin for the walk.
The first talk for the session I chaired was by Mark Wilde who talked quantum convolution codes with entanglement assistance. Mark showed a method for turning any classical convolution code into an entanglement assisted quantum convolution code. Then Ognyan Oreshkov talked about fault-tolerance in holonomic quantum computation.