I’m visiting the KITP in Santa Barbara because they are having a term long workshop on Topological Phases and Quantum Computation (directed by Sander Bais, Chetan Nayak, and John Preskill.) Unfortunately I won’t be able to stay for the entire workshop. But this isn’t as huge of a blow as it would have been years ago, because, the KITP records all of the talks and puts them online. They can be found here.
Yesterday, T. Sentil gave a talk in which he almost made it through his introduction! Anyway one point which he emphasized is something I have always found fascinating. And that is that topological phases (a loose term which I won’t even try to define) might actually be much more common than is widely thought, but the problem is that we don’t have the tools to see them! From the perspective of quantum error correcting codes, this seems fairly natural. In a quantum error correcting code, local probes without at least a global analysis, can not reveal the information encoded into a quantum error correcting code. Indeed if local probes without global analysis could get at our quantum data, then so too could an environment get to this data. Another way to state this is to say that the order parameter for quantum error correcting codes is a big complicated beast whose measurement cannot be done with the simple tools we currently have in our lab.
As a concrete example of this, consider single-molecule molecules. These are crazy molecules which can achieve permanent magnetization through a single molecule effect (usually at fairly low temperatures.) Basically these molecule have a high spin ground state and a high zero-field splitting such that there is a substantial barrier to leaving the high spin ground state. This effect is the result of a collection of interactions among the lower spin systems. What is interesting is the following observation. Take four spin one-half systems and couple them together anti-ferromagnetically with equal couplings between all four systems (mmm, tetrahedrons.) Such a system will have a spin zero ground state which is two fold degenerate. And this two-fold degenerate ground state is actually a single error quantum error detecting code (see quant-ph/0012018)! But why in the world, if you were a chemist, would you go looking for a spin zero molecule. This is the exact opposite of what you would like to find. Further, you won’t be able to see that there is a quantum error detecting code without a knob which allows you to split the degeneracy of this ground state. And doing this is not a trivial task. In short, exactly since we don’t have the tools to observe this effect, we won’t really be interested in it. You need a crazy theorist to tell you that maybe you should think about trying to engineer such a knob onto your system. What use is a crazy theorist except to tell you crazy stories.
Of course, thinking like this, that there might be hidden orders which we are not smart enough to discover is a good way to make yourself paranoid. What might we be hiding from because our glasses are so opaque? Certainly the role of instrumentation in science is one I find fascinating and, I must admit, a bit scary.
So I'll Just Introduce Him As…
An amusing anecdote from Fischer Black and the Revolutionary Idea of Finance
…in October 1968 Samuelson was slated to give the inaugural lecture for the new MIT-Harvard Joint Seminar in Mathematical Economics. It was to be a big event, held in a special room in Holyoke Center at harvard, and Samuelson’s name was the featured draw on all the publicity notices. All the big Harvard names would be there-Kenneth Arrow, Wassily Leontief, Zvi Griliches, Robert Dorfman, Hendrink Houthakker-and important faculty would be visiting from other areas universities as well. As a further mark of the event’s special status, no students would be allowed to attend-no sgudents, that is, except for Robert Merton, who Samuelson arranged to give the talk in his place, but without telling the organizers.
When the moment came, after the requisite ceremony and introduction, Samuelson stood up at one end of the long conference table and spoke. “This is a joint paper, and my co-author will present it. I’d like to introduce him as a professor, but he is not a professor. I’d like to introduce him as as Doctor, but he has no Ph.D. So I’ll just introduce him as Mr. Robert Merton.”
Dance Ions! Dance!
A reliable source (heh, that’s funny isn’t it) tells me that the ion trap dance I discussed here was the “Open Box Salsa.” Because, you know, I’m sure you all really wanted to know that.
(Which of course reminds of a story. So an old teaching technique for those who have trouble spelling (like me) is to learn to visualize the world you are trying to spell while looking, say, to the up and right. You know, that introspective thing you do when you are searching for some bit of knowledge. The idea is to leverage that to help your spelling. Well a few years back I decided that what was more important than remembering things was to forget things. Indeed, like the above information, I’ll bet you were better off without it. So I started training myself to look down when I am trying to forget something. Not sure if it ever really worked. Or at least I don’t remember if it’s worked.)
What Are the Assumptions of Classical Fault-Tolerance?
Oftentimes when we encounter the threshold theorem for quantum computation, it is pointed out that there are two assumptions which are necessary for fault-tolerant quantum computation. These two assumptions are
1. A supply of refreshable pure or nearly pure ancillas into which the entropy generated by quantum errors can be dumped throughout the error correction procedure.
2. Parallel operations.
For point 1, an important reference is Aharonov, Ben-Or, Impagliazzo and Nisan, quant-ph/9611028, and for point 2, an important reference is Aharonov and Ben-Or, quant-ph/9611029. These two assumptions are provably necessary. Usually when I see these two points presented, they are presented as if they are something unique to quantum computation. But is this really true? Well certainly not for the first case. In fact quant-ph/9611028 is first about computation in a noisy model of classical reversible computation and second about a noisy model of quantum computation! What about point 2? Well I can’t find a reference showing this, but it seems that the arguments presented in quant-ph/9611029 can be extended to reversible noisy classical computation.
Of course many of you will, by now, be grumbling that I haven’t included the other assumptions usually stated for the threshold theorem for fault-tolerant quantum computation. Okay, so I’ll put it in:
3. A noisy model in relation to control of your system which is not too ridiculous.
Well, okay, usually it is not stated this way, but that’s because I don’t have an easy way to encapsulate the noise models which lead to provable lack of ability to compute fault tolerantly. But certainly there are similar noise constaints for classical computation which are provably necessary for fault-tolerant classical computation.
So what are the difference between the assumptions for fault-tolerant quantum and fault-tolerant classical computation? I strongly believe that the only differences here are difference arising simply going from a theory of probabilities in classical computation to a theory of amplitudes in quantum computation. Of course this short changes the sweet and tears which is necessary to build the theory of fault-tolerant quantum computation, and I don’t want to disparage this in any way. I just want to suggest that the more we learn about the theory of fault-tolerant quantum computation, the more we recognize its similarity to probablistic classical computation. I call this general view of the world the “principal of the ubiquitous factor of two in quantum computing.” The idea being mostly that quantum theory differs from probablistic theory only in the necessity to deal with phase as well as amplitude errors, or more generally, to deal with going from probabilities to amplitudes. This point of view is certainly not even heuristic, but it seems at least that this is the direction we are heading towards.
Of course the above view is speculative, not rigorous, and open to grand debate over beers or the within the battleground of an academic seminar. But it certainly is one of the reasons why I’m optimistic about quantum computing, and why, when I talk to a researcher in higher dimensional black holes (for example) and they express pessimism, I find it hard to put myself in their shoes. To summarize that last sentence, I’m betting we have quantum computers before higher dimensional black holes are discovered 🙂
Startup Pages
For many years I have used a simple customized startup webpage for all of the quick links I need. For many years I have wanted to write some code to allow me to customize this startup page. But, now I don’t have to do this because I’ve discovvered: Protopage. I’ve just started using it, but so far, so good.
Where Are the Borg?
(Warning: partially valid arguments ahead, but at some points reality takes a hit and runs for the hills and then returns to make some sort of point.)
What I love about the threshold theorem for computation (classical or quantum) is that it is essentially a theorem about immortality. Whah? Immortality? Indeed. (For those unfamiliar with the ideas of the threshold theorem see a quantum discussion in quant-ph/0507174 by Daniel Gottesman.)
Well first of all, let me rephrase that. The thresholds theorems of computation are about immortality. We should pluralize the “theorem” since there are many different versions of the theorem applicable under many different assumptions. We should pluralize the “threshold” since there are many different parameters which describe the different assumptions.
Now given the assumptions of the thresholds theorems, we can ask the question about whether these assumptions are satisfied in the real world. If they are, then the particular theorem you are concerned with states that it is possible to design a computer whose rate of failing can be made arbitrarily small by building bigger computers out of the faulty components (and this size overhead scales in such a way that changing the rate of failure by k orders of magnitude only incures an overhead of increasing the size by a polynomial in k.) So, in essence, the theorem states that you can make your computer effectively immortal. Say you want it to live for a billion years, then you can build such a device. Say you want it to live for trillion years, then you can build a bigger device. Etc. etc. onward to effectively immortality. (Okay, so there are those of you who might object to me calling a computer a living thing and personifying it with the atributes of life and death, but I have too little time to spend arguing against mythical beasts in the machine for which we have no evidence of and which somehow make biology an independent branch of the laws of the universe 😉 )
So given that the threshold theorems somehow “prove” that we can make immortal machines, the question is obviously whether the universe actually obeys the conditions of one of the threholds theorems. I would certainly be inclined to believe that the answer to this question is that no, there is no thresholds theorem which actually holds in our universe. The threshold is zero. Why do I say this? Well, let’s just think of the most common forms of the quantum therhold theorems. One thing that these models don’t consider is a form of error in which the entire quantum computer is blown up by, to put it in a modern context, terrorists (you see, it all makes sense, because quantum computers can be used to hack the codes that these terrorists use to plot their evil deads. To misquote a famous 19th century author: A useless consistency is the hobgoblin of a creative but bored mind.) Now this form of error can certainly happen. There is certainly a probability that it will happen (at which point we might begin to worry whether it was a Republican or Democrat who calculated this probability.) And I am equally certain that the current threshold theorems do not apply to this form of error. Thus I can at least argue that today’s theorems do not have assumptions which are satisfied in the real world.
Of course the lack of a current theorem which is not satisfied by how the real world works, does not imply that there isn’t some thresholds theorem which is satisfied in the real world. So can we put our arguments on more rigorous (snicker) grounds? Well I would maintain that the lack of the Borg is quiet evidence that there is no threshold theorem for immortality in our universe. Huh? Well suppose that we try to extend our threshold theorem for quantum computation to the type of errors I described above (so-called “t-errors.”) Certainly I can imagine a way to do this (okay maybe not so realistic!) but at the cost of designing a large computer. Indeed I suspect that there are turtles all the way up, and that if we keep pressing higher into the heirarchy of errors we wish to be robust against, we will always be making larger and large computers. And certainly even with our current constructions to truely obtain immortality, we need larger and larger machines. This argument suggests that if there is such a theorem, then to achieve immortality we must construct larger and larger computers whose size, eventually must engulf the entire universe (okay I’m way out on a limb here, but I am currently in California where this is only a little more flakey than your average citizen’s view of the world.) So, since when I look around I do not see such a construction, and I believe that (in this case alien) technology will always expand to fill the void of what is possible (over the edge 😉 ) this implies to me that there the threshold for computation in the universe is zero. Of course I have discounted the possibility that just because I do not see the construction, that the construction does not exist. Indeed we ourselves may be this construction (quoteth Philip K. Dick “the Empire never ended.”) So, no Borg, no threshold. 🙂
Now you might think that believing the thresholds for computation are zero might lead me to choose another field than quantum computation. In fact you might even go so far as to say that maybe we should trash the classical computer revolution, since certainly, there are no fault-tolerant classical computers. But of course, this, like my argument above, is absurd. The thresholds theorems are meant to only be a step in the direction of establishing the possibility of a technology whose use and capacities are not infinite, but are indeed only designed to achieve as much as is possible given the assumptions of the theorems. The thresholds theorems is never about taking the limit of the theorems, by nailing our probability of failure to zero. The thresholds theorems is always about figuring out what you can do with the resources you have. Thus we shouldn’t view the thresholds theorems as a magic potion on the path towards building a quantum computer, but instead as a way to most optimize our construction of a computer.
More importantly for the field of quantum computation, the question of relevance is whether large quantum computers can be build which outperform classical computers. But this always has the context of what classical computer we are talking about. So really the thresholds theorems for quantum computation are more about whether we will be able to build a quantum computer which outperforms a classical computer. Now because we believe that quantum computers have exponentially benefits over classical computers for some tasks, this means that for these tasks, once you get a modern technology where quantum computers outperform classical computers, for the relevant task, building better classical computers becomes an exponential waste over building a better quantum computer. For me, this is the real threshold for quantum computation: the day we cross over from classical computers to quantum computers which outperform these classical computers. The thresholds theorems are just ways of stating that we don’t see any theoretical obstacles towards such a day.
Everything's Best in the West
Via Dynamics of Cats via Bitch PhD, states I’ve visited:
create your own visited states map
Seems I’m geographically bigoted.
Research Blues
Writers have writer’s block while researchers have the research blues. Lately I’ve been struggling with perhaps the worst case of research blues I’ve had in a long time. Usually I am full of all sorts of crazy ideas that, while they never lead anywhere, are at least crazy and thus keep my spirits high. Lately, however, the well from which I’ve drawn my crazy ideas seems to have dried up. I’m not sure of the reasons for this: maybe I’m getting old and conservative and so I take a more pesimistic view of anything I dream about (but not pesimistic enough to start proving lower bounds :).) Maybe I’m getting dumber. Maybe I’ve just been unlucky. Maybe the time I’ve spent teaching last term has kept me from spending enough continuous time thinking about new research. Certainly I’m sure many of you have noticed a lack of anything “interesting” on this blog, and you can probably attribute this to the fact that I have been clinging to any half-baked idea I have like it is the last drop of water on a globally warmed future earth. Instead of posting dozens of half-baked muffins, I’ve only been posting half-baked crumbs.
The real question, of course, is how to pull oneself out of the research blues. I think there are many ways to approach this, and I’m pretty sure every researcher has their own methods. In the past, one way I’ve done this is to try to learn an entirely new subject area. Nothing like bashing your neurons up against a new set of problems to loosen them up and make them fire in crazy random ways again. Luckily for the next two weeks, I’m at the KITP in Santa Barbara, where I have plenty of time to try to get the neurons loose again. Unfortunately the black holes in higher dimensions program at KITP is soon closing up. Which is too bad because I certainly know nothing about the results in this field, and would love to bash my brains against what they are working on.
The research blues are a real part of being a researcher. They are rarely, however, discussed. Certainly in theoretical physics, a field in which stature seems to be assigned by being the last to blink, there are zero incentives to admit any struggles. Certainly this is one of the reasons I so like the book “Good Benito” by Alan Lightman since it does a superb job describing what it’s really like to do theory research. I’ve certainly seen my share of students and colleagues crushed under the weight of the load of research blues (will it crush me, I do not know? How can I know?) So the question I’d like to ask is what we should tell students who are just begining to consider their research careers. Too often I find it easier to just encourage the students forward, saying nice beautiful things about doing research. But lately, in my bout of pesimism, I’ve begun to think that we owe it to ourselves to tell those who are considering research in theory of the pitfalls of research. Tell them that one hazard of theory research is that you will undoubtably suffer from severe bouts of research blues (well at least those of us who can relate to the lyrics “I’m no Reykjavik pixie, no British genius who will rise and rise again…”) Certainly everyone has to judge for themselves whether they can stand the brutal beating of research blues, but pretending that all is hunky dorey seems to me a way to end up distorting your psychie into a twisted ball of frustration.
Oh well, again, not a very interesting post. See how it runs on and on without any point or interesting insight? But I’d thought at leasted I’d explain why the post was not interesting instead of just putting more tripe onto the blogosphere. At least this tripe has warning.
On the Road Again
Last week I was in Boulder for a workshop on ion trap quantum computing. Basically nearly everyone who is working on ion trap architectures for quantum computing was there, which was pretty incredible. A highlight of the workshop, besides the excellent experimental results, was that I got to see one of the participants describe how the ions will be shuttled around using his feet and then turning this description into a dance step. The ion trap boogie, or something like that. Won’t it be great to see the actual boogie in the ion traps?
Hang On Dust Mite, Hang On!
What a ride!