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.
O brave new quantum world!
Jon, not John. — John
I don’t even want to try to read what I’m writing. Jon fixed, thanks John.
There is much similarity between encoding a qubit in the j=0 space of four spin-(1/2) particles and encoding a qubit in the charge-0 space of four nonabelian anyons. However, while in the former case we can think of the space as an error-detecting code (in the sense that a Pauli error acting on one of the four qubits can be detected by making an appropriate collective measurement on the four qubits), in the later case we don’t have quite the same interpretation, because there is no such thing as an error acting on a single anyon.
Back to the similarities… For “Fibonacci anyons” (for example), there is a trivial charge that we assign the label “0” and a nontrivial charge that we assign the label “1”. When two 1s are fused, we can get either a total charge of 0 or 1: 1 X 1 -> 0 + 1. This is like a truncated version of adding two spin-1 representations of SU(2): 1 X 1 -> 0 + 1+ 2 in that case but for the anyons there is no label “2”. So there are two distinguishable ways to fuse four anyons to get total charge 0 — the first two anyons can fuse to either charge 0 or charge 1. That’s the encoded qubit.
Here too exchanging the particles has a nontrivial effect on the encoded qubit, but we get a much richer structure for anyons than for the case of SU(2). For the anyons, there is a difference between a clockwise and a counterclockwise exchange, and furthermore (if we give the four anyons the names ABCD) the one-qubit gate induced by the exchange of particles A and B does not commute with the one-qubit gate induced by the exchange of particle B and C. And in fact, the unitaries generated by these two gates are dense in SU(2). So for anyons any unitary transformation acting on the encoded qubit can be approximated to arbitrary accuracy by a sequence of exchanges of the particles.
I’m not sure that this answered your question, but it’s interesting anyhow.
I guess what I was thinking about is suppose that you are simulating the anyon model on a standard quantum computer using k qubits. For each element of the braid group (say of size 4) there is a unitary operation on your k qubits. Is it true that this unitary representation respects in any way locality on your k qubits? (i.e. if the braid group element which exchanges the first two anyons in the two different directions act on the same subset of k qubits….and braid group elements which share braids exchanged share common subsets of qubits, etc.) If this is true, then on subspace of k qubits is the braid group irrep an error detecting or correcting code.
I guess you are really asking whether simulating a topological quantum computation using ordinary qubits endows the simulation with intrinsic fault-tolerant features. No, not as far as I know for standard encodings (like what Jon was presumably describing in his talk), but the answer will depend on precisely how the anyons are encoded by the qubits.
Live blogging and live proofreading… what a system!
I feel that “Fibonacci anyons” are just pulling a rabbit out of a hat.
For the beaver-challenged, John Preskill is the John D. MacArthur Professor of Theoretical Physics, Division of Physics, Mathematics, and Astronomy California Institute of Technology.
Hmmm. John Preskill superposed with John D. MacArthur has something to do with the late John-John Kennedy?
For the celebrity-challenged [cut&pasting from wikipedia], John Fitzgerald Kennedy, Jr. (November 25, 1960 – July 16, 1999), often referred to as John F. Kennedy, Jr., JFK Jr., John Jr., John Kennedy or John-John, was an American lawyer, journalist, socialite and publisher. He was the son of President John F. Kennedy and Jacqueline Kennedy Onassis, and the younger brother of Caroline Kennedy (as well as the older brother of the deceased Patrick Bouvier Kennedy)…. The nickname “John-John” came from a reporter mishearing his father calling him (“John” spoken twice in quick succession).
Of course, because “John” is a root of unity (EE writes “j” where Mathematicians and Physicists write “i”), so that “John John” = (John)^2 = John. Or has to be rotated 720 degrees to get back where he strated.
Jason Amini talked about the latest and greatest advances in the NIST Boulder ion-trapping experiments. In addition to the standard Boulder fare (i.e. superhuman experimental progress since their last talk), they have achieved extremely high readout fidelities by making use of a quantum nondemolition measurement. Pauli measurements in trapped ion QIS are implemented by shining laser light on the ion qubit of interest. Quantum information is stored in the ion in such a way that only one qubit state interacts with the laser. Pauli measurements can then be performed by detecting light scattered off of the ion. The technical challenge here is that only a fraction of the scattered light can be collected and imaged onto a detector. LImited detector quantum efficiency and false detector output (dark counts, stray light, etc) limit the fidelity of the measurement. Amini described a procedure where they perform a Pauli measurement on an ionic qubit by coupling the target qubit to a different ion that can be selectively addressed (because it’s a different atomic species and can be spectrally addressed). Essentially, they perform a sequence of CNOTs between the target and a collection of measurement qubits. This has the form of QND measurement, making it possible to combine the information from the different measurment qubits to obtain a combined readout fidelity > 99% in about 10 ms. They call this “quantum enabled readout.”
I am not sure I totally agree with John on the one anyon error. You can imagine that there are “environmental anyons” that are moving around and causing errors. One of the thing such an anyon could do is to fuse with one of the 4 anyons from the code. I believe (although I haven’t checked the details) that in that case the encoding would act just like an error detection code. You could detect this error by measuring the total charge of the 4 anyons in the code (just like you would do in SU(2)) If you get 0, than the fusion did not create any error but if you get 1, there is a error.
Dave, before the part where you recap the question you asked after my talk, I think you mean to say that you start with the k=0 irrep and tensor with k=1 four times, obtaining irreps k=0,2,4. Anyway, I would be surprised if a good code could be achieved for the encoding of the Jones representation into qubits that I described in my talk. The encoding is such that the state of qubit i tells you whether the i’th tensoring with 1 increased or decreased the irrep label. The braiding is not really local in this basis, as you need some extra qubits to to store the label of the irrep that you’re in at step i. These can be computed coherently, after which the braiding is local as long as you act on these systems as well. Anyway, this is very different from the encoding you mention in your post, where a logical qubit is encoded nonlocally in the spin-0 subspace of four spin-1/2 systems.
To put it in the context of the Schur transform, you can imagine the qubits in the encoding I talked about as having a subspace of legal paths which are analogous to the register in the Schur transform holding the S_n irreps. Then there’s the extra systems which hold the irrep labels – the last one that holds the final irrep tells you which irrep the paths correspond to. Now, it’s not exactly like the Schur transform because nothing is being transformed, but if something were, it would be a tensor power of the defining irrep of U_q sl_2, the “quantized universal enveloping algebra” of sl_2. But that’s another story.
If you’re instead interested in encoding qubits into groups of anyons, as the encoding I talked about will also achieve, I think that David is right in saying that a global charge measurement of four anyons would detect a physical error on an anyon – whatever that could be. For the encoding I mentioned (which was also given by Kitaev in his long anyon paper from the physical perspective we’re now talking about), every computational state is such that all groups of anyons 1, 2, 3, 4 (mod 4) will have zero charge (total irrep label 0). A similar situation will occur for the original encoding given by Freedman Larsen and Wang, which encodes a qubit into 3 anyons, and for which blocks of 6 anyons will have trivial total charge.
On the other hand, I think it might be much more likely to have an anyon and its antiparticle appear out of the vaccuum, only to wind around one of our anyons, then to fuse back together, effectively measuring the charge (irrep label) of the anyon in question. I don’t think that this would be detectable by measuring any sort of global charge, but it could indeed collapse the internal state of the four anyons. However, I think there are others who understand much better than I do about the types of errors we could expect to happen in an anyon-based quantum computer. John, I’m wondering if you would mind elaborating on your statement that there’s no such thing as an error on an anyon. I presume you mean that no local operator can affect the underlying state.
One last point is an interesting paper by Franko, Rowell and Wang that discuss how extraspecial 2-groups are essentially the Jones representations of the braid groups at a 4th root of unity. I forget the details, but I know that extraspecial 2-groups are almost the same thing as the Pauli groups on n qubits, so maybe there’s some deep theory of quantum error correction at other roots of unity waiting to be discovered…
In my second comment, what I meant is: if (for example) we represent anyons using qubits as in Freedman-Kitaev-Wang then the qubits directly encode the fusion spaces of the anyons; damaging a single qubit could change the encoded fusion space, causing a logical error.
I’m backing away from my first comment, though. Here is what I was thinking, and why I am not reconsidering it (after reading David Poulin’s comment): When we speak of an error-detecting code, we mean that there are detectable errors that in some sense have “lower weight” than the logical errors. Now consider a “local operator” that might act on a single anyon or collectively on several anyons. A local operator that acts on a single anyon cannot change the anyon’s charge, and therefore has no effect on topologically encoded information. That is what I meant when I said (in my first comment) that “there is no such thing as an error acting on a single anyon.”
A local operator acting on a set of two or more anyons cannot change the total charge of that set of anyons, nor can it change how the charge of that set of anyons fuses with another disjoint set of anyons. But it can change how the charges are distributed among the anyons in the set upon which it acts, and it can change how a *subset* of that set of anyons fuses with other anyons; it can also alter the relative phases of the different charge sectors. So of course, if a single qubit is encoded in a set of four Fibonacci anyons with total charge zero as described in my earlier comment, a “local” operator that acts collectively on the four anyons can manipulate the qubit, i.e. cause a logical error. Somewhat less trivially, a local operator that acts collectively on the two qubits BC can act on (or flip) the charge of AB and of CD (while of course preserving the charge of ABCD). This too is a logical error, and since its weight (two) is the minimum weight for any local operator that has any discernible effect on the topologically encoded information (where by “weight” we mean the number of anyons acted upon by a local operator), I claimed that the encoding is not “error detecting.”
So why am I changing my mind now? Because the “local operator” description may be too narrow a way of thinking about modeling errors acting on the anyons. Poulin invites us to consider errors that change the total charge of a set of four anyons; such errors are detectable. As an alternative to Poulin’s fusion model, I suggest a different error model: a “weight-one” error occurs if an unseen pair of anyons with trivial total charge is created, one of the anyons in the pair winds around one of the anyons in the code block ABCD, and as a result the total charge of the unseen pair of anyons becomes nontrivial. This weight-one error changes the total charge of the code block, so it is detectable. However a “weight-two” error, in which the unseen anyons winds around a pair of the anyons ABCD, can be an undetectable logical error.
So if we think that an error in which an “environmental anyon” winds around two of our computational anyons should be regarded as “higher weight” than an error in which the environmental anyon winds around one of our computational anyons, then I agree with Poulin that we can say that the encoding is “error detecting.” Furthermore, this way of thinking about the weight of the errors might be reasonable if the anyons ABCD are kept far apart from one another.
Sorry, when I said “I am not reconsidering it” I really meant “I am now reconsidering it”. That was then, this is now. As of now, I am not reconsidering what I said then.