Sweet, sweet, NW weather news. But remember, even with this good news, it is important for everyone to continue to perform a snow dance every few days or so.
Superpositions of Worms Going In and Out
Over at Fact and Fiction there is an interesting post about an article in New Scientist called Attack of the Quantum Worms.
Having not read the article, I thought I’d be an idiot and comment on what one could possibly mean by the statement that quantum computers are more susceptible to malicious attacks. I’m an even bigger idiot because I know very little about computer software security. But life’s about saying silly things and then getting chewed out by all you smart people, know?
The first thing one might mean is that quantum data cannot be backed up due to the no cloning theorem. OK, suppose I’m a hacker who wants to attack your quantum computer. Surely if I write some code which is executed by the computer and it damages the quantum state of the system, then, because I can’t back up the state of the quantum computer, I’m in big trouble. So it seems that one cannot prevent crashing a quantum computation by backing the state of the system up. But this isn’t quite right, is it? I mean suppose we have a classical computation and we make two backups of the state of the computation at any time. Then we can use this to test whether one of these states has been corrupted by majority voting. But we’ve learned that we can do exactly the same thing for quantum computers: we can detect if the quantum state of one of our copies has been corrupted by encoding into a quantum computer. Now we need to use more than three qubits per bit, but still, this doesn’t seem like such a big deal (from a theorist perspective 😉 ) Now I’d also like to say that I don’t think this is even the way classical computers protect themselves versus malicious software.
So what about attacking the “quantum software?” Well in a standard circuit model of quantum computation, the software is just a list of classical expressions. There is nothing quantum about the data describing a quantum computing program. So it seems that there can’t be any difference here between the quantum and classical world.
Oh well, I really should get a copy of the New Scientist and figure out if any of this rambling has anything to do with the article (on a similar note, I don’t understand the second part of the post at Fact and Fiction. I just don’t see the relevance of copying in a fixed basis: this is something which we almost always avoid in quantum computing because it destroys the coherence properties of the subsystem being so copied.)
Boo!
Happy Halloween!
Posting has been low because I’ve been visiting Isaac Chuang at MIT. There seems to be a very popular costume here at MIT for Halloween: everyone is dressed up as a science geek 😉
Signaling and Information
One basic concept which has emerged in classical physics (and then moved on to the quantum world) is that it doesn’t appear possible to send information faster than the speed of light. What I find fascinating about this is that it seems to be, like Landaur’s principle, a statement which connects physics (special relativity, local field theory, quantum field theory, etc.) with, essentially, information theory (the concept of a signal, the concept of information capacity).
But now suppose, as I have argued before, that what makes a physical system a “storage” device is very much a matter of the physics of the device. Thus, for instance, I could try to encode information into the position of a particle on a line. Is this a good way to encode information? Well, certainly we could try to do this, but in the real world it will be very hard to achieve many orders of magnitude precision on this measurement because the system will interact with the rest of the world. While isolated we can talk about such an encoding, but as we crank up the real world meter, we find that there are limits on this encoding. Or to put it another way, the ability of the system to store information is a function of how it interacts with the rest of the world, a function of the physics of the system.
And if the ability of a system to store information is a function of the physics of the system, why isn’t the no-faster-than-light rule, a rule which is essentially about information transmission in physical systems, also a function of the physics of the system?
Performance Enhanced Theorems
Among sports fans there is a lot of controversy about the use of performance enhancing drugs by athletes. Of course what exactly an performance enhancing drug is, is often left pretty vague. But most sports fans argue against the use of such drugs because they are, in some form, cheating.
So what do we do, for example, with Erdos. Paul Erdos was, for those who don’t know, one of the twentieth centuries great mathematicians. He was the author, amazingly, of over 1,500 different papers. It was well known, also, that Erdos used amphetamines. There is a famous story that his friends were so worried about his amphetamine use that they bet him that he couldn’t stay off the drugs for a month. Of course Erdos took the bet and successfully stayed off the drugs for the required amount of time. When he went to collect the bet, he reportedly said “You set Mathematics back one month!” (OK, this story is off the top of my head, the details may or may not be correct!) So, in a real sense, Erdos’ productivity was increased in large part by his use of a performance enhancing drug. So, was Erdos cheating? Should we think of his “records” his “theorems” as somehow being “less proved by Erdos” because of his use of amphetamines? Well I certainly would argue against this.
At FOCS this year I was having this conversation, and it came up that perhaps we shouldn’t penalize the result, because the outcome, i.e. the mathematical proofs isn’t really a competitive sport. But what about those who are competing for tenure? Now of course I’m disregarding the legality of the performance enhancing drugs. But disregarding this issue (which may just invalidate the whole argument, but bear with me) should there be drug testing of tenure track professors to make sure they aren’t using amphetamines to increase their productivity?
The Gospel of Theoretical Computer Science
I’m in Pittsburgh this weekend for FOCS 2005. This is the first FOCS I’ve attended.
This evening there was a panel discussion at the business meeting (free beer!) on “Exciting the public about (theoretical) Computer Science.” (Update: for a detailed description of the business meeting see Rocco Servedio’s guest post at Lance Fortnow’s blog and for a real computer scientist’s comments see here and for a nice collection comments head over to Geomblog. For a fare and balanced counter, see Pit of Bable) It was very interested to hear about the severity of the public image crisis the field of theoretical computer science currently finds itself facing. It is true that even within the broader computer science community, theory is oftentimes seen as not very important. But beyond this, the public’s perception of the theory of computation is very limited and a lot of the panel discussion focused on how to fix this. I mean, if I ask random people if they know anything in theoretical computer science, what are the chances that they will know anything? At best you might be very lucky and meet someone who has heard of the P versus NP question. On the other hand, mention physics to people, and they immediately think nuclear bombs, black holes, perhaps lasers and string theory, quantum mechanics, and atoms with electrons zipping around a nucleus (well I’m not saying any of these things are correct physics 😉 ) So how can theoretical computer science convey the excitement of the field to the general public?
Concrete suggestions like “publish in Science and Nature” and “get IEEE and ACM to hire someone to do PR” were offered up, and probably deserve serious consideration. It was interesting, to me, originally(?) a physicist, to hear how physics and astronomy were held up as prime examples of doing a good job conveying to the public the excitement of their research. It is true that physics and astronomy do a good job of conveying the excitement of the field, and there are various reasons for this.
But I’d like to focus on why theoretical physics has done a good job at exciting the public. Why? Because this is much closer to the theory of computation. Because lets face it: CS theory doesn’t have things dug up from the ground (dinosaurs, early primates, archeology), nor beautiful pictures of alien environments (planetary science, all of astronomy). And theoretical physics, like CS theory is hard. I mean really hard. And also, I would claim, theoretical physicis and CS theory share a very fundamental similarity in that they are both essentially about advanced creative problem solving.
So let’s look at theoretical physics. How is the excitement of theoretical physics conveyed? Well, the first things that probably pops into most peoples minds that is related to theoretical physics are Stephen Hawking’s “A Brief History of Time” or maybe Brian Green’s “The Elegant Universe.” Or maybe the recent NOVA program on “E=mc^2.” Now clearly neither of these books or the TV show is explaining to the public the “real” story of the theoretical physics. But what they do a good job of is convincing the audience that they, the audience, actually understand what is going on. As was mentioned on the panel tonight, people will hear about gravitons and think that they actually understand the physics of gravitons. But really, of course they don’t. Do they even know why exchange of particles can give rise to attractive forces or the connection of whether these forces are attractive or repulsive to the spin of the exchanged particle. I seriously doubt it. Yet, the authors of these books and TV shows have successfully given the audience the feeling that they do understand the field.
There are stories I have been told about Richard Feynman (OK, yeah, I just can’t resist another Feynman story) which said that when you went to one of his lectures, while you were listening to the lecture you would think “Yeah! This is great! Everything makes total sense now!” But when you left the lecture and tried to recall the reasoning and what Feynman was teaching, you couldn’t reproduce the results. I maintain that what was happening here is the same thing which good popular expositions on theoretical physics do: they convince the reader that they understand what is going on even though they most certainly do not. What is funny about the Feynman stories, of course, is that these are real physicists who themselves probably should understand the subject, and yet Feynman was able to convince them they understood what was going on, even though they really didn’t. Kind of scary.
So what lesson do I draw for this for the theory of CS? Well they need a Richard Feynman and a Stephen Hawking! But seriously, they need to attempt to convey their results in a way which, while not toally faithful to the science, gives the reader a reason to believe that they understand what is going on. This, of course, is much hard to do as a computer scientist than as a theoretical physicist because in the former rigor is held in higher esteme than in physics where hand-wavy arguments hold a much greater standing. But certainly even theoretical physicists (except the best) have to distort their understandings to meet the general public. So my advice to the theoretical computer science community is to let the rigor go but convey the spirit in a way that convince the public they understand what is going on.
Now one might argue that this is dishonest. And to the brighter readers it certainly is. But remember, it’s not the bright readers which are the main concern: they don’t consitute the public (if they did I wouldn’t be writing this post nor would FOCS be having this panel discussion. Nor would their be trials about whether intelligent design should be taught in science courses at the beginning of the twenty first century.)
Another interesting perspective coming from physics is that theoretical physics has conveyed to the public that it is really pursuing something fundamental. The two big fundamentals are “learning the laws of nature” and “understanding the origin of our universe.” CS theory hasn’t, in my opinion, exploited the fact that it is studying a fundamental question: the fundamental limits of computation. This fundamental research direction, to me, is as deep as understanding what the laws of nature are (and if you catch my on some days I might even say that one is deeper than the other. Which is deeper depends on the day. And perhaps the last time I’ve had a conversation with Scott Aaronson.) Certainly this is one of the reasons people get interested in the theory of computer science. I myself have very fond memories of reading “The Turing Omnibus” which introduced me at an early age to ideas of P versus NP, error correcting codes, the von Neuman architecture, the theory of computablity, etc. This excitement is as exciting as thinking about string theory, or supersymmetry, or solutions to Einstein’s equations. And it certainly, is a fundamental question, about our universe (I began my thesis at Berkeley with the sentence “Our generous universe comes equiped with the ability to compute.” Heh. Pretty cheesy, no?)
I think I could go on about this subject ad nauseum. So I’ll stop. And, of course, I’m more of an outsider than an insider here. This is my first FOCS. On the other hand, when one of the panelists asked how many had publised in Science or Nature, I was one of about four who got to raise their hand. And the paper even had some computer science (about universal quantum computers) in it! And remember, if you publish in Nature or Science, there is the possibility of being sucked into their press cabul and there will be articles about your work appearing simultaneously around the world’s newspapers.
Lies, Damn Lies, and Chemistry
Geoknitting points to a very interesting site which I can highly recommend visiting: The re-Discovery Institute.
A New Kind of Disclaimer
Cosma Shalizi has posted a review of Stephen Wolfram’s “A New Kind of Science.” It’s not often that you find a review which begins
Attention conservation notice: Once, I was one of the authors of a paper on cellular automata. Lawyers for Wolfram Research Inc. threatened to sue me, my co-authors and our employer, because one of our citations referred to a certain mathematical proof, and they claimed the existence of this proof was a trade secret of Wolfram Research. I am sorry to say that our employer knuckled under, and so did we, and we replaced that version of the paper with another, without the offending citation. I think my judgments on Wolfram and his works are accurate, but they’re not disinterested.
or a review that ends (well almost) with
This brings me to the core of what I dislike about Wolfram’s book. It is going to set the field back by years. On the one hand, scientists in other fields are going to think we’re all crackpots like him. On the other hand, we’re going to be deluged, again, with people who fall for this kind of nonsense. I expect to have to waste a lot of time in the next few years de-programming students who’ll have read A New Kind of Science before knowing any better.
My Printer Turned Me In
Via Hogg’s Universe, this is freaky:
It sounds like a conspiracy theory, but it isn’t. The pages coming out of your color printer may contain hidden information that could be used to track you down if you ever cross the U.S. government.
Last year, an article in PC World magazine pointed out that printouts from many color laser printers contained yellow dots scattered across the page, viewable only with a special kind of flashlight. The article quoted a senior researcher at Xerox Corp. as saying the dots contain information useful to law-enforcement authorities, a secret digital “license tag” for tracking down criminals.
The content of the coded information was supposed to be a secret, available only to agencies looking for counterfeiters who use color printers.
Now, the secret is out.
Yesterday, the Electronic Frontier Foundation, a San Francisco consumer privacy group, said it had cracked the code used in a widely used line of Xerox printers, an invisible bar code of sorts that contains the serial number of the printer as well as the date and time a document was printed.
Holy conspiracy theory, batman!
When my uncle worked for IBM, he told me one of the intelligence agencies used to visit from time to time and “suggest” that they use a particular cryptosystem. He said the experts at IBM would look it over and were always very suspicious of the system proposed by the agency, so they never used them. This always seemed like a silly approach to me. Much better would be to get one of your supersmart mathematicians hired at IBM and then use this insider to convince the company to use this cryptosystem. Well maybe you would need more than one supersmart mathematician, but still…
s, p, d, f
From Nature Physics, f-wave Superconductors?:
NaxCoO2yH2O must be hydrated to superconduct1, and its triangular CoO2 layers provide an intriguing contrast with the square CuO2 layers of the high-temperature superconductors. Its superconductivity is often assumed to be unconventional in that the Cooper pairs are not in a spin singlet state with s-wave symmetry, as with conventional superconductors. According to the Pauli exclusion principle, pairs with a singlet (triplet) spin part have a corresponding even (odd) spatial part, designated as s-, p-, d- or f-wave pairing in accordance with the pair angular momentum. However, in NaxCoO2yH2O, experimental reports are often contradictory2, 3, 4, 5, 6 and solid evidence for any particular pairing state remains lacking. This has led to an unprecedented number of proposals2, 3, 5, 7, 8, 9, 10, 11, 12, 13 for the pairing symmetry (perhaps the greatest number ever for a single compound), each in agreement with some subset of the available data. Here we test each of the 25 symmetry-allowed pairing states14 against firmly established properties of the compound. Surprisingly, this eliminates most possible pairings. The two remaining states both have f-wave symmetry, suggesting that NaxCoO2yH2O may be the most exotic superconductor discovered so far. We discuss expected features of these states and suggest experiments to distinguish between them.