My recent post on thermodynamics and computation reminded me of a very nice article by Geoffrey Grinstein that I read a while back.
Suppose we are trying to store digital information into some macroscopic degree of freedom of some large system. Because we desire to store digital information, our system should have differing phases corresponding to the differing values of the information. For example, consider the Ising model in two or greater dimensions. In this case the macroscopic degree of freedom over which we wish to store our information is the total magentization. In order to store information, we desire that the magnetization come in, say, two phases, one corresponding to the system with positive total magnetization and the other corresponding to negative total magnetization.
Assume, now that the system is in thermal equilbrium. Suppose further that there are some other external variables for the system which you can adjust. For the example of the Ising model, one of these variables could be the applied external magnetic field. Since the system is in thermal equilbrium, each of the phases will have a free energy. Now, since we want our information to be stored in some sort of robust manner, we don’t want either of the phases to have a lower free energy, since if it did, the system would always revert to the phase with the lowest free energy and this would destroy our stored information. Since we require the free energy of all information storing phases to be equal, this means that we can always solve these equality equations for some of the external variables. This means that if we plot out the phases as a function of the external variables, we will always end up with coexisting phases along surfaces of dimension less than the number of external variables. For our example of the Ising model in an external magnetic field, what happens is that the two phases (positive and negative total magnetization) only coexist where the magnetic field equals zero. If you have any magnetic field in the positive magnetic direction, then the thermodynamical phase which exists in equibrium is the phase with the postivie total magnetization. So coexistence of phases, and in particular of information storing phases, in the external variable space, is always given by a surface of dimension less than the number of external variables
What is interesting, and why this gets connected with my previous post, is Toom’s rule. Toom’s rule is two dimensional cellular automata rule which exhibits some very interesting properties. Imgaine that you have a two dimensional square lattice of sites with classical spins (i.e. +1 and -1) on each of the lattice sites. Toom’s rule says that the next state of one of these spins is specified by the state of the spin, its neighbor to the north, and its neighbor to the east. The rule is that the new state is the majority vote of these three spins (i.e. if the site has spin +1, north has spin -1, and east has spin -1, the new state will be spin -1.)
Toom’s rule is interesting because it exhibits robustness to noise. Suppose that at each time step, the cellular automata instead of performing the correct update, with some probability the site gets randomized. What Toom was able to show was that for the Toom update rule, if this probability of noise is small enough, then if we start our system with a positive magnetization (just like the Ising model, we define this as the sum of all the spin values) then our system will remain with a postive magnetization and if we start our system with a negative magnetization it will similarly retain its magnetization. Thus Toom showed that the cellular automata can serve, like the two dimensional Ising model at zero applied field, as a robust memory.
But what is nice about Toom’s rule is that it gives an even stronger form of robustness. Remember I said that the noise model was to randomize a single site. Here I meant that the site is restored to the +1 state with 50% probability and the -1 state with 50% probability. But what if there is a bias in this restoration. From the Ising model point of view, this actually corresponds to applying an external magnetic field. And here is what is interesting: for Toom’s rule the region where the two phases which store information can coexist is not just at the (effectively) external magnetic field equal zero point, but instead is a region of external magnetic field between some positive and negative value (set by the probability of noise.) So it seems that Toom’s rule violates the laws of thermodynamics!
The solution to this problem is to realize that the probability distribution produced by Toom’s rule is not given by a thermodynamic Boltzman distribution! Toom’s rule is an example of a probabilistic cellular automata whose steady state is not described by classical thermodynamics. This is exactly one of the models I have in mind when arguing that I do not know whether the eventual state of the universe is going to be in Gibbs-Boltzman thermodynamic equibrium.
Along these lines, Charlie Bennett and Geoffrey Grinstein, have, however, shown that while the steady state of Toom’s rule is not given by a Gibbs-Boltzman thermodyanmic distribution, if one considers the histories of the state of the cellular automata, instead of the state itself, then Toom’s rule is given by a Boltzman distribution over the histories of the cellular automata. It’s at this point that my brain just sort of explodes. That a system’s histories are in equibrium is very strange: normally we think about equibria being generated in time, but here we’ve already used up our time variable! I suspect that the answer to this puzzle can be achieved by refering to the Jaynes approach to entropy, but I’ve never seen this done.
Back!
Posting has been nonexistent because I’ve been traveling. I’m now back from giving a lecture at the 4th biannual SQuInT student retreat, held at USC and organized by Todd Brun. I’ve been lucky enough to attend all four such retreats, once as a student, and three times as a lecturer (once as a graduate student, once as a postdoc, and once as whatever it is I am now 😉 .) This year I got the opportunity to lecture on quantum algorithms. I’ve put the contents of my slides online here.
The student retreat was a lot of fun, including a trip to the King Tut exhibit at LACMA. Unfortunately, my enjoyment was tempered by the nasty nasty cold I’ve come down with. I can’t hear anything out of my right ear. Bah!
SQuInT, by the way, stands for Soutwest Quantum Information and Technology Network. Yeah, someone must have been smoking something when they thought that one up 😉
A Trivia Puzzle
Lately I’ve been playing trivia at a local pub (which I highly recommend.) One of the categories they often use is a “decade” category. The answer to all of the clues are years in a particular decade (say, for example, the 80s.) Each year is used exactly one time and there are ten clues. Suppose you randomly fill in the years as answers to the ten clues, respecting the condition that every year must be used exactly once. What is the expected number of clues you will get correct?
Running Into a Comet
This movie (in Quicktime format) of Deep Impact’s journey to smashing into comet is pretty fun. And then I sit and ponder and think: I just witness my small species sending a probe into outer space to smash into a comet. Awesome.
Revolution!
We hold these truths to be self-evident, that all men are created equal, that they are endowed by their Creator with certain unalienable Rights, that among these are Life, Liberty and the pursuit of Happiness. –That to secure these rights, Governments are instituted among Men, deriving their just powers from the consent of the governed, –That whenever any Form of Government becomes destructive of these ends, it is the Right of the People to alter or to abolish it, and to institute new Government, laying its foundation on such principles and organizing its powers in such form, as to them shall seem most likely to effect their Safety and Happiness. Prudence, indeed, will dictate that Governments long established should not be changed for light and transient causes; and accordingly all experience hath shewn, that mankind are more disposed to suffer, while evils are sufferable, than to right themselves by abolishing the forms to which they are accustomed. But when a long train of abuses and usurpations, pursuing invariably the same Object evinces a design to reduce them under absolute Despotism, it is their right, it is their duty, to throw off such Government, and to provide new Guards for their future security.
Can you even imagine revolting against your government today? Or are we in an era of Prudence, with evils sufferable?
100 Years Ago, Time Got An Upgrade
Happy 100th birthday special relativity! Let’s all go out and celebrate by running around with poles in our hands and see if they fit in any barns. Or better yet, celebrate by explaining special relativity to someone whose never understood the theory and blow their mind.
I'm Doing It All Wrong
Stop the Myth
From an article in the New York Times about the separation of Church at State (not to be confused with NOFX’s separation of Church and Skate)
The United States has always been home to striking religious diversity — diversity that has by fits and starts expanded over the last 230 years.
Um. The United States is 77 percent Christian (down from 86 percent in 1990.) The world is approximately 33 percent Christian, 21 percent Islamic, 14 percent Hindu, 16 percent non-religious, 6 percent Buddhist, 6 percent Confucianist, etc. I think the correct statement is “the United States has always been home to striking Christian religious diversity.”
For an interesting graphic, check out this geographic picture of religious adherence in the United States. It would be cool to run this through the cartegram software of Michael Gastner, Cosma Shalizi, and Mark Newman.
FOCS 2005 Papers
The list of 2005 FOCS (46th Annual IEEE Symposium on Foundations of Computer Science ) accepted papers has been posted here. I see four quantum papers (out of 62, one to be announce). They are
“The Symmetric Group Defies Strong Fourier Sampling,” Cristopher Moore, Alexander Russell, and Leonard J. Schulman
“Cryptography in the Bounded Quantum-Storage Model,” Ivan Damgaard, Serge Fehr, Louis Salvail and Christian Schaffner
“Quantum Information and the PCP Theorem,” Ran Raz
“From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups,” Dave Bacon,Andrew M. Childs and Wim van Dam
I guess I can now officially call myself a “theoretical computer scientist.” Does this mean if someone says to me “Hermitian matrix” I cannot immediately follow with the words “diagonalize it”?
Thermodynamics is Tricky Business
Thermodynamics is one the most important tools we have for understanding the behavior of large physical systems. However, it is very important to realize when thermodynamics is applicable and when it is not applicable. For example, try to apply thermodynamics to the Intel processor inside the laptop I am writing this entry on. Certainly the silicon crystal is in thermal equilbrium, but then how am I able to make this system compute: if states are occupied with probabilities proportional to a Boltzman factor, then how can my computer operate with all sorts of internal states corresponding to, say, it’s memory? Let’s say that all of these internal states, states of my computing machine, are all energetically about the same energy (which is, to a decent approximation, true.) Then, according to thermodynamics, each of these states should be occupied with the same probability. But the last time I checked, the sentence I am typing is not white noise (some of you may object, 😉 )
Today, Robert Alicki, Daniel Lidar, and Paolo Zanardi have posted a paper in which they question the threshold theorem for fault-tolerant quantum computation and claim that the normal assumptions for this theorem cannot be fullfilled by physical systems. I have a lot of objections to the objections in this paper, but let me focus on one line of dispute.
The main argument put forth in this paper is that if we want to have a quantum computer with Markovian noise as is assumed in many (but not all) of the threshold calculations, then this leads to the following contradictions. If the system has fast gates, as required by the theorem, then the bath must be hot and this contradicts the condition that we need cold ancillas. If, on the other hand, the bath is cold, then the gates can be shown to be necessarily slow in order to get a valid Markovian approximation. Both of these conditions come from standard derivations of Markovian dynamics. The authors make the bold claim:
These conclusions are unavoidable if one accepts thermodyanmics…We take here the reasonable position that fault tolerant [quantum computing] cannot be in violation of thermodynamics.
Pretty strong words, no?
Well, reading the first paragraph of this post, you must surely know what my objection to this argument is going to be. Thermodyanmics is a very touchy subject and cannot and should not be applied adhoc to physical systems.
So lets imagine running the above argument through a quantum computer operating fault-tolerantly. Let’s say we do have a hot environment. We also have our quantum system, which we want to make behave like a quantum computer. Also we have cold ancilla qubits. Now what do we do when we are performing quantum error correction? We bring the cold ancillas into contact with the quantum computer interact the two and throw away the cold ancillas. Now we can ask the question, is the combined state of the cold anicllas and the hot environment in thermal equilbrium? Well, yes, both are in thermal equibrium before we start this process, but they will be in thermal equilbrium with two different temperatures. OK, so now we have an interaction between the system and the cold ancillas. So let’s do this. Now these two systems, the quantum computer and the ancillas clearly couple to the hot bath. Therefore we can assume that the Markovian assumption holds and further that the gate speed for the combined system-ancilla system is fast. No problem there, right. OK, now we throw away the cold ancillas. So we’ve done a cycle of the quantum error correction without violating the conditions set forth by the authors. How did we do this?
We did this by being careful about what we called the “system.” (Or, more directly we have to be careful what we call the “bath.” But really these are symmetric, no?) We started out the cycle with the system being the quantum computer. Then we brought in the cold ancillas. Our system now includes both the quantum computer and the ancillas. Since we are now enacting operations on this combined system, our enviornment is the original bath, which is hot (which may now couple to the ancillas.) We can perform fast gates on this combined system and then we may discard the ancillas.
In order for the authors argument to work, they have to assume that the “system” is always just the quantum computer. But then clearly the assumption of the environment being in thermal equilibrium is violated at the beginning of the error correcting cycle: the ancillas are cold but the bath is hot. Both are independently in thermal equibrium, but the combined system is not in thermal equilbrium at the same temperature. The interactions with the hot bath do imply that we can perform fast gates. The interactions with the cold ancilla do imply that we will have slow gates. But when we bring the cold ancillas and quantum computer together, we can also have fast gates: because our system now consists of the computer plus the ancillas and the remaining environment it hot. The ancillas are not part of the thermal bath which is causes problems for our quantum computer. Certainly the authors are not objecting to the fact that we can prepare cold ancilla states? So I see no contradiction in this paper with the threshold theorem. (A further note is that there is also a threshold for fault-tolerance when the noise is non-Markovian. I’m still trying to parse what the authors have to say about these theorems. I’m not sure I understand their arguments yet.)
Thermodynamics is, basically, a method for reasoning about large collections of physical systems when certain assumptions are made about this system. Often we cannot make these assumptions. (A classical case of this, which is not relevant to our discussion, but which is interesting is the case of the thermodynamics of a system of many point particles interacting via gravity: here thermodynamics can fail spectacularly, and indeed, things like the internal energy of the system are no long extensive quantities!) In the above argument, we cannot talk about two systems being at the same temperature: we have two separate systems with different tempatures. Certainly if we bring them together and they interact, under certain conditions, the two will equilibriate. But this is explicitly what doesn’t happen in the fault-tolerant constructions. This is, indeed, exactly what we mean by cold ancillas!
Understanding the limits of the threshold for fault-tolerant quantum computation is one of the most interesting areas of quantum information science. I’ve bashed my head up against the theorem many times trying to find a hole in it. I think that this process, of attempting to poke holes in the theorem, is extremely valuable. Because even if the theorem still holds, what we learn by bashing our heads against it is well worth the effort.
Updated Update: Daniel Lidar, Robert Alicki and other have posted responses and comments below. I highly recommend that you read them if you found this entry interesting!