A rare event occurred today here in Seattle. And I’m not just talking about the 20 minutes of partly sunny skies we got at lunchtime. No, this was something rarer still: a quantumista condensate.

What precipitated this joint gathering of the decohered and the coherent? Michael Nielsen was visiting the University of Washington to deliver a distinguished lecture on the topic of his new book: open science. Having seen Michael talk about this subject 3 years ago at QIP Santa Fe, I can say that he has significantly focused his ideas and his message. He makes a very compelling case for open science and in particular open *data*. He has thought very hard about what makes online collaborative science projects successful at focusing and amplifying our collective intelligence, why such projects sometimes fail, and which steps we need to take to get to the promised land from where we are currently.

The talk was recorded, and as soon as the video becomes available I’ll put a link here. I highly recommend watching it.

**Update (12/12):** Here is the link to Michael’s talk.

You might be wondering, what is the optimizer doing there? He is in town to give the colloquium to the computer science department. And given all the excitement, Dave Bacon, aka Pontiff++, couldn’t help but sneak over from Google to check things out. He is the one you can blame for coining the horrible phrase “quantumista condensate”, but you probably already guessed that.

## Dial M for Matter

It was just recently announced that Institute for Quantum Information at Caltech will be adding an extra letter to its name. The former IQI will now be the Institute for Quantum Information and Matter, or IQIM. But it isn’t the name change that is of real significance, but rather the $12.6 million of funding over the next five years that comes with it!

In fact, the IQIM is an NSF funded Physics Frontier Center, which means the competition was stiff, to say the least. New PFCs are only funded by the NSF every three years, and are chosen based on “their potential for transformational advances in the most promising research areas at the intellectual frontiers of physics.”

In practice, the new center means that the Caltech quantum info effort will continue to grow and, importantly, it will better integrate and expand on experimental efforts there. It looks like an exciting new chapter for quantum information science at Caltech, even if the new name is harder to pronounce. Anyone who wants to become a part of it should check out the open postdoc positions that are now available at the IQIM.

## Markus Greiner named MacArthur Fellow

Markus Greiner from Harvard was just named a 2011 MacArthur Fellow. For the experimentalists, Markus needs no introduction, but there might be a few theorists out there who still don’t know his name. Markus’ work probes the behavior of ultracold atoms in optical lattices.

When I saw Markus speak at SQuInT in February, I was tremendously impressed with his work. He spoke about his invention of a quantum gas microscope, a device which is capable of getting high fidelity images of individual atoms in optical lattices. He and his group have already used this tool to study the physics of the bosonic and fermionic Bose-Hubbard model that is (presumably) a good description of the physics in these systems. The image below is worth a thousand words.

Yep, those are individual atoms, resolved to within the spacing of the lattice. The ultimate goal is to obtain individual control of each atom separately within the lattice. Even with Markus’ breakthroughs, we are still a long way from having a quantum computer in an optical lattice. But I don’t think it is a stretch to say that his work is bringing us to the cusp of having a truly useful quantum simulator, one which is not universal for quantum computing but which nonetheless helps us answer certain physics questions faster than our best available classical algorithms and hardware. Congratulations to Markus!

## Stability of Topological Order at Zero Temperature

From today’s quant-ph arXiv listing we find the following paper:

### Stability of Frustration-Free Hamiltonians, by S. Michalakis & J. Pytel

This is a substantial generalization of one of my favorite results from last year’s QIP, the two papers by Bravyi, Hastings & Michalakis and Bravyi & Hastings.

In this new paper, Michalakis and Pytel show that any local gapped frustration-free Hamiltonian which is topologically ordered is stable under quasi-local perturbations. Whoa, that’s a mouthful… let’s try to break it down a bit.

Recall that a local Hamiltonian for a system of n spins is one which is a sum of polynomially many terms, each of which acts nontrivially on at most k spins for some constant k. Although this definition only enforces *algebraic* locality, let’s go ahead and require *geometric* locality as well by assuming that the spins all live on a lattice in d dimensions and all the interactions are localized to a ball of radius 1 on that lattice.

Why should we restrict to the case of geometric locality? There are at least two reasons. First, spins on a lattice is an incredibly important special case. Second, we have very few tools for analyzing quantum Hamiltonians which are k-local on a general hypergraph. Actually, few means something closer to none. (If you know any, please mention them in the comments!) On cubic lattices, we have many powerful techniques such Lieb-Robinson bounds, which the above results make heavy use of [1].

We say a Hamiltonian is *frustration-free* if the ground space is composed of states which are also ground states of *each term separately.* Thus, these Hamiltonians are “quantum satisfiable”, as a computer scientist would say. This too is an important requirement, since it is one of the most general classes of Hamiltonians about which we have any decent understanding. There are several key features of frustration-free Hamiltonians, but perhaps chief among them is the *consistency* of the ground space. The ground states on a local patch of spins are always globally consistent with the ground space of the full Hamiltonian, a fact which isn’t true for frustrated models.

We further insist that the Hamiltonian is gapped, which in this context means that there is some constant γ>0 independent of the system size which lower bounds the energy of any eigenstate orthogonal to the ground space. The gap assumption is extremely important since it is again closely related to the notion of locality. The spectral gap sets an energy scale and hence also a length scale, the correlation length. For two disjoint regions of spins separated by a length L in the lattice, the connected correlation function for any pair or local operators decays exponentially in L.

The last property, topological order, can be tricky to define. One of the key insights of this paper is a new definition of a sufficient condition for topological stability that the authors call *local topological order*. Roughly speaking, this new condition says that ground states of the *local* Hamiltonian are not distinguishable by any (sufficiently) local operator, except up to small effects that vanish rapidly in a neighborhood of the support of the local operator. Thus, the ground space can be used to encode quantum information which is insensitive to local operators! Since nature presumably acts locally and hence can’t corrupt the (nonlocally encoded) quantum information, systems with topological order would seem to be great candidates for quantum memories. Indeed, this was exactly the motivation when Kitaev originally defined the toric code.

Phew, that was a lot of background. So what exactly did Michalakis and Pytel prove, and why is it important? They proved that if a Hamiltonian satisfying the above criteria is subject to a sufficiently weak but *arbitrary* quasi-local perturbation then two things are stable: the spectral gap and the ground state degeneracy. (Quasi-local just means that strength of the perturbation decays sufficiently fast with respect to the size of the supporting region.) A bit more precisely, the spectral gap remains bounded from below by a constant independent of the system size, and the ground state degeneracy splits by an amount which is at most exponentially small in the size of the system.

There are several reasons why these stability results are important. First of all, the new result is very general: generic frustration-free Hamiltonians are a substantial extension of frustration-free commuting Hamiltonians (where the BHM and BH papers already show similar results). It means that the results potentially apply to models of topological quantum memory based on subsystem codes, such as that proposed by Bombin, where the syndrome measurements are only two-body. Second, the splitting of the ground state degeneracy determines the dephasing (T2) time for any qubits encoded in that ground space. Hence, for a long-lived quantum memory, the smaller the splitting the better. These stability results promise that even imperfectly engineered Hamiltonians should have an acceptably small splitting of the ground state degeneracy. Finally, a constant spectral gap means that when the temperature of the system is such that kT<<γ, thermal excitations are suppressed exponentially by a Boltzmann factor. The stability results show that the cooling requirements for the quantum memory do not increase with the system size.

Ah, but now we have opened a can of worms by mentioning temperature… The stability (or lack there of) of topological quantum phases at finite temperature is a fascinating topic which is the focus of much ongoing research, and perhaps it will be the subject of a future post. But for now, congratulations to Michalakis and Pytel on their interesting new paper.

##### [1] Of course, Lieb-Robinson bounds continue to hold on arbitrary graphs, it’s just that the bounds don’t seem to be very useful.

## My Favorite D-Wave Future

As many of you know, D-Wave has a nice paper out about some experiments on one of their eight qubit systems. In addition they have sold one of their systems to the military industrial complex, a.k.a. Lockheed Martin.

One of the interesting things about the devices they are building is that no one really knows whether it will provide computational speedup over classical computers. In addition to the questions of whether adiabatic quantum algorithms will provide speedups for useful problems, there is also the question of how this speedup will be affected when working at finite temperature. If I were an investor this would worry me, but as a scientist I find the question fascinating and hope they can continue to push their system in interesting directions. Of course if I were an investor I’d probably be some multimillionaire who probably has an odd risk aversion profile 🙂

A fun question to ponder, at least for me, is what will eventually happen to D-wave, in, say, ten years. Of course there are the most obvious futures. They could run out of funding and close their doors as a device maker and sell their patent porfolio. They could succeed and build machines that do outperform classical computers on relevant hard combinatorial problems. Those two are obvious. BORING.

But my favorite scenario is as follows. D-wave continues to build larger and larger devices. At the same time they perform even more exhaustive testing of their system. And in the process they discover that there are “noise” sources that they hadn’t really expected. Not noise sources that violate quantum theory or anything, but instead noise sources that end up turning their stoquastic Hamiltonian into a non-stoquastic Hamilotnian. While no one knows how to use the Hamiltonian of D-wave’s machine to build a universal quantum computer, it is entirely possible that such a machine, plus some crazy extra unwanted terms could end up being universal. So while the company is squarely behind the dream of a combinatorial optimizer, it’s not at all impossible that their machine could accidentally be useful for universal adiabatic quantum computation (and of course whether this can be made fault-tolerant is still a major open question, at least for the models with non-degenerate ground states.) Wouldn’t it be hilarious if the noise which most people believe will destroy D-wave’s computational advantage actually turns their machine into a universal quantum computer? Ha!

So which will it be? And what odds will you give me on each of these possible futures?

## dabacon.job = "Software Engineer";

Some news for the remaining five readers of this blog (hi mom!) After over a decade of time practicing the fine art of quantum computing theorizing, I will be leaving my position in the ivory (okay, you caught me, really it’s brick!) tower of the University of Washington, to take a position as a software engineer at Google starting in the middle of June. That’s right…the Quantum Pontiff has decohered! **groan** Worst quantum to classical joke ever!

Of course this is a major change, and not one that I have made lightly. There are many things I will miss about quantum computing, and among them are all of the people in the extended quantum computing community who I consider not just colleagues, but also my good friends. I’ve certainly had a blast, and the only things I regret in this first career are things like, oh, not finding an efficient quantum algorithm for graph isomorphism. But hey, who doesn’t wake up every morning regretting not making progress on graph isomorphism? Who!?!? More seriously, for anyone who is considering joining quantum computing, please know that quantum computing is an extremely positive field with funny, amazingly brilliant, and just plain fun people everywhere you look. It is only a matter of time before a large quantum computer is built, and who knows, maybe I’ll see all of you quantum computing people again in a decade when you need to hire a classical to quantum software engineer!

Of course, I’m also completely and totally stoked for the new opportunity that working at Google will provide (and no, I won’t be doing quantum computing work in my new job.) There will definitely be much learning and hard work ahead for me, but it is exactly those things that I’m looking forward to. Google has had a tremendous impact on the world, and I am very much looking forward to being involved in Google’s great forward march of technology.

So, onwards and upwards my friends! And thanks for all of the fish!

## TEDxCaltech Videos

Coming online now: http://tedxcaltech.com/. See the Optimizer pontificate about P versus NP (now who can verify the Feynman quote at the beginning?)

and two prestigious professors goof around:

## US Quantum Computing Theory CS Hires?

I’m trying to put together a list of people who have been hired in the United States universities in CS departments who do theoretical quantum computing over the last decade. So the requirements I’m looking for are (a) hired into a tenure track position in a US university with at least fifty percent of their appointment in CS, (b) hired after 2001, and (c) they would say their main area of research is quantum information science theory.

Here is my current list:

- Scott Aaronson (MIT)
- P. Oscar Boykin (University of Florida, Computer Engineering)
- Amit Chakrabarti (Dartmouth)
- Vicky Choi (Virginia Tech)
- Hang Dinh (Indiana University South Bend)
- Sean Hallgren (Penn State)
- Alexei Kitaev (Caltech)
- Andreas Klappernecker (Texas A&M)
- Igor Markov (Michigan)
- Yaoyun Shi (Michigan)
- Wim van Dam (UCSB)
- Pawel Wocjan (UCF)

Apologies to anyone I’ve missed! So who have I missed? Please comment!

**Update:** Steve asks for a similar list in physics departments. Here is my first stab at such a list…though it’s a bit harder because the line between quantum computing theorist, and say, AMO theorist who studies systems that might be quantum computing is difficult.

Physicists, quantum computing theory,

- Lorenza Viola (Dartmouth)
- Stephen van Enk (Oregon)
- Alexei Kitaev (Caltech)
- Paolo Zanardi (USC)
- Mark Byrd (Southern Illinois University)
- Luming Duan (Michigan)
- Kurt Jacobs (UMass Boston)
- Peter Love (Haverford)
- Jon Dowling (LSU)

I’m sure I missed a lot hear, please help me fill it in.

## Mythical Man 26 Years

This morning I was re-reading David Deutsch’s classic paper “Quantum Theory, the Church-Turing Principle and the Universal Quantum Computer”, Proc. of the Roy. Soc. London A, 400, 97-117 (1985) This is the paper where he explicitly shows an example of a quantum speedup over what classical computers can do, the first time an explicit example of this effect had been pointed out. Amusingly his algorithm is not the one most people call Deutsch’s algorithm. But what I found funny was that I had forgotten about the last line of the article:

From what I have said, programs exist that would (in order of increasing difficulty) test the Bell inequality, test the linearity of quantum dynamics, and test the Everett interpretation. I leave it to the reader to write them.

I guess we are still waiting on a program for that last problem?

## QIP 2011 Open Thread

So what’s going on at QIP 2011? Anyone? Bueller? Bueller?

**update:** It looks like pdfs of the talk slides are available. Were the talks videotaped (err, I guess I’m showing my age: were the talks recorded in video format?)

**more update:** John Baez has a post on a few talks.