When I read articles by creation scientists and there ilk I’m often filled with a feeling of “how the heck can you believe that, surely you’ve heard about this, this, and this.” Invariably they have none read of the “this”‘s. Yesterday I gave a talk at the Santa Fe Institute’s Complex Systems Summer School on quantum computation. And after the talk, I was having a discussion with someone about quantum computing. And they said they still thought quantum computers are not a valid model of computation. And I was thinking to myself, “But surely you’ve read this, this, this, this, this, and this? Just to name a few.” Never thought I’d be having these thoughts around another scientist.
Hyperbole Wednesdays
Two posts over at Quantum Algorithms, one on D-Wave Systems and another one on a supposed algorithm for solving NP-complete problems efficiently on a quantum computer.
When I was a graduate student at Berkeley, when a paper came out claiming that quantum computers could solve NP-complete problems, we would all race to see who could figure out where the problem in the paper was. I usually don’t like to write blog articles about papers like the one commented upon in Quantum Algorithms (for the preprint, see here), but I’m not about to get a blogger username to just comment on the site cus I’m lazy, so I thought I’d just stick my comments here. As far as I can tell the paper is incorrect. In particular if you examine Figure 3, the circuit described does not perform as described. If I understand correctly, the state after the oracle gate is [tex]${1 over 2^n} sum_{x,y=0}^{2^n-1}(-1)^{f(x)}|y>|x>$[/tex]. The author then applies a unitary gate between the y and x registers and then a measurement of the qubits. This is supposed to allow one to identify a place where [tex]$f(x)=1$[/tex], but as far as I can tell, one only gets an exponentially small information about such a location if there is only one marked item.
The other article on Quantum Algorithms points to an article in the MIT Technology Review about the Vancouver based D-Wave systems. Here the hyperbole is even more mysterious:
Vancouver startup D-Wave Systems, however, aims to build a quantum computer within three years. It won’t be a fully functional quantum computer of the sort long envisioned; but D-Wave is on track to produce a special-purpose, “noisy” piece of quantum hardware that could solve many of the physical-simulation problems that stump today’s computers, says David Meyer, a mathematician working on quantum algorithms at the University of California, San Diego.
The difference between D-Wave’s system and other quantum computer designs is the particular properties of quantum mechanics that they exploit. Other systems rely on a property called entanglement, which says that any two particles that have interacted in the past, even if now spatially separated, may still influence each other’s states. But that interdependence is easily disrupted by the particles’ interactions with their environment. In contrast, D-Wave’s design takes advantage of the far more robust property of quantum physics known as quantum tunneling, which allows particles to “magically” hop from one location to another.
It sounds to me, from the article, that the proposal is a quantum computer which implements a quantum adiabatic algorithm. The question of whether adiabatic quantum algorithms can be more efficient than classical algorithm is, from what I know, fairly controversial (see, for example, here.) I would have a hard time telling a venture capitalist to put money in something quite so controversial, but hey, what do I know, I’m just a lowsy academic nerd and a chicken. If they can sell solutions to hard problem instances and actually succeed, then what do I know! And they will be rich!
Update: Suresh says I’m lazy. And I am. So looking again at quant-ph/0506137, the main problem is already apparent in equation (5). There the author has miscontrued the tensor product. If we take the output of this circuit seriously, the initial state [tex]$|00rangle$[/tex] is transformed into [tex]$0$[/tex]. Not the state zero. The amplitude for the first qubit in this formula is zero.
Starwarsomicon
Neal Stephenson has an op-ed article in the New York Times about Star Wars. Someday we can all be so lucky as to write an op-ed piece on a Science Fiction movie and get it published in the Times. A choice paragraph:
Scientists and technologists have the same uneasy status in our society as the Jedi in the Galactic Republic. They are scorned by the cultural left and the cultural right, and young people avoid science and math classes in hordes. The tedious particulars of keeping ourselves alive, comfortable and free are being taken offline to countries where people are happy to sweat the details, as long as we have some foreign exchange left to send their way. Nothing is more seductive than to think that we, like the Jedi, could be masters of the most advanced technologies while living simple lives: to have a geek standard of living and spend our copious leisure time vegging out.
If the “Star Wars” movies are remembered a century from now, it’ll be because they are such exact parables for this state of affairs. Young people in other countries will watch them in classrooms as an answer to the question: Whatever became of that big rich country that used to buy the stuff we make? The answer: It went the way of the old Republic.
From One of Quantum Computation's Founders
David Deutsch’s contribution to the UFO debate here.
Special Cases of the Abelian Grape Joke
Via Three-Toed Sloth, via Notional Slurr, via Ernie’s 3D Pancakes come the The Additional Publications of Jeremy L. Martin.
Bashing Hashing
Recently there has been a lot of exciting work in cryptographic hash functions. Hash functions are functions which take some large (possibly infinite) domain, and map it to a smaller (usually of fixed size) range. Cryptographic hash functions are hash functions which are one-way and also collision free. One-way means that if H is the hash function, then, given H(x) it is computationally infeasible to determine x. Collision free means that if we are given H(x), then it is computationally infeasible to find a y not equal to x such that H(x)=H(y). Actually this is called weakly collision free. Stronly collision free is if it is computationally infeasible to find any two x and y not equal to each other such that H(x)=H(y). You may notice that there exist many collisions when the domain is larger than the range, but for a strongly collision free hash function, finding even a single collision is difficult.
One common use for cryptographic hash functions is in digital signatures. Instead of digitally signing the entire document, one almost always uses a hash function on this document and then digitally signs the resulting value. So if it is possible to construction documents which have the same hash value, then this whole scheme gets into trouble.
Recently two widely used cryptographic hash functions, MD5 and SHA, have been under attack. Work by a whole host of people, including papers by Wang and Yu, and Biham, Chen, Joux, Carribault, Lemuet, and Jalby has shown that it is possible to find collisions for these hash functions in computationally feasible times. But wait, you say, finding collisions doesn’t necessarily mean that we can’t use these attacks for the digital signature schemes we described above. You would think this because the results on breaking the cryptographic hash functions provide basically random collisions. For the specific task of creating a forged document with the same hash function, you might think these attacks don’t work. But you would be wrong! In fact, you can use these attacks to create forged documents with the same hash function. Magnus Duam and Stefan Lucks have a wonderful discussion and demonstration of this here. What is very cool is that they have two postscript files which both produce the same value after applying the MD5 hash function (a25f7f0b 29ee0b39 68c86073 8533a4b9, heh.) (Previously Kaminski and Mikle have also shown such capabilities.)
So…do you really trust MD5? I don’t.
Update: As Aram points out in the comments, this page has a cool list of hash functions and those that have been broken. Not a pretty picture.
Bend It Like Feynman
Next week I begin teaching. This is really the first course that I’ve fully taught-I’ve given plenty of summer school lectures, and guest lectures, and I was a teaching assistant through most of my years at Berkeley-but this is the first class that I’ve really been in total control of the class. The class is “Quantum Computing” and is in the professional masters program here in the Computer Science and Engineering department at UW. You can check out the course webpage here. But there’s not much there but a syllabus yet. The cool thing is that I get to teach this course the way I think it should be taught. On the other hand, this means that there are “no excuses”-the quality of the class rests squarely on my shoulders
Since this is the first time that I’ve actually had to lecture for an entire course (as opposed to being a TA, in which you aren’t the first person to tell the students about the material) I’ve been spending a bit of time contemplating what makes a good lecturer. One way I did this was to go back and read the “Feynman Lectures on Gravitation.” Something I’ve noticed about a large number of the good speakers and lecturers, including Feynman, is that while their actual vocabulary might be limitted, they almost universal express themselves in ways which are very unique. Reading Feynman’s lectures, there aren’t many sections which are just ordinary drolling on. Saying the ordinary in extraordinary manner appears to be vital to keeping a lecture going. And certainly this also adds to Feynman’s humor. Perhaps by expressing his thoughts in such strange manners, he is just naturally led to funny sentences such as
There are 10^11 stars in the galaxy. That used to be a huge number. But it’s only a hundred billion. It’s less than the national deficit! We used to call them astronomical numbers. Now we should call them economical numbers.
Indeed, if you read Gordon Watts blog, he put up a list one of his students had kept during his teaching of all the crazy things he said during the term. And you can tell, just by reading this list, that Gordon would make an excellent teacher. Now I just wonder if I need to tone up or tone down my crazy speak habits…
The Web Ate My Brain
I’ve started using the Greasemonkey script Webolodeon. This cool little script pops up a little screen every five minutes when you are surfing the web and asks you to justify why you are still surfing the web. Pretty cool and useful, I must say.
Hell Froze
Roger Waters to reunite with Floyd for Live8 concert. David Gilmour:
Like most people I want to do everything I can to persuade the G8 leaders to make huge commitments to the relief of poverty and increased aid to the third world. It’s crazy that America gives such a paltry percentage of its GNP to the starving nations. Any squabbles Roger and the band have had in the past are so petty in this context, and if re-forming for this concert will help focus attention then it’s got to be worthwhile.
And in other news, pigs can fly,
Approximating Zone
A new sign for outside my office:
