Given the title of this blog, you can be sure that the moment I saw the article The Curious Case Of The Quantum Cardinal by Rupert Goodwins, I couldn’t resist reading it. I must say that, while I liked the title, the article did make me cringe more than a few times in it’s description of quantum theory and quantum computing, but, as I’ve mentioned before, I have this reaction to a lot of popular science writing these days. What I did find interesting, however, was the claim that quantum computing is a direct challenge to the dogma of the Roman Catholic church. Whah? Quantum information scientists are the Galileo’s of our modern times?
But of course, this should have been obvious. Suppose, just for fun, that you are a believer in the many worlds interpretation of quantum theory (caveat: I’m giving a rather flippant version of the interpretation here. This is not meant to offend, but only as an exercise in a certain form of reasoning which I can only describe as “newspaper article writer reasoning.”) In the many worlds interpretation, one believes that the different components of a quantum superposition are actually different universes, and that while sometimes these universes can merge back together (when quantum interference occurs, for example) most of the time these universe branch and then are totally inaccessible to us for the rest of time. (OK, I agree this sounds really strange, and well, all I can only say: “yep, pretty strange.”) Now think about this from a theological perspective. Certainly one would expect that there are many universes out there in which Jesus did not lead the life he lead as described in the New Testament. One would even expect that there are many universes out there in which Jesus did not even exist. This may or may not trouble Catholic theologians, but I can at least see that it must at least cause a bit of consternation. Somehow this whole thing reminds me of this webpage.
Can Good News Cure a Cold?
First the bad news. The bad news is that I am fighting a really nasty cold. I can hear a little more out of my right ear than yesterday, but I’m still pretty plugged up. Anyone who knows any home remedies that don’t involve a hot potato, feel free to advise 😉
The good news is that today we recieved notification that a NSF grant which I had applied for with Mark Oskin has been officially awarded. This is the first grant I’ve applied for, and I’m just going to sit here and enjoy the feeling of batting one thousand, because I know I’m lucky and I know that the long hard slog for grants is destined to smash my ego multiple times in the future. As many of you may know, I have been extremely lucky to find a position here at the University of Washington, during a time when my family has been undergoing quite a lot of, how shall I put it, difficult transitions. In many ways, the computer science and engineering department here was taking quite a gamble on me, and I can only begin to express how appreciative I am for what they have done for me. The awarding of this grant is, then, I hope, the beginning of their gamble paying off. It will certainly mean that I have a more certain future. Now if only this good news could cure my cold.
Toom's Rule, Thermodynamics, and Equilbrium of Histories
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.