Inscrutable Science Update

It's a good day for people posting about science I don't understand...

Peter Woit points to the Non-Commutative Geometry blog, at which Alain Connes, the godfather of non-commutative geometry, is posting. It's not the most polished blog, but if you can understand what they're talking about, it's probably interesting.

Scott Aaronson is excited about new results in quantum computing, where somebody has "announced a quantum algorithm for evaluating NAND trees in O(âN) time." I'm not quite sure what he's talking about either, but it has something to do with ants, sugar cubes, and teaching computers to play chess even better than they do now. Given that I haven't been able to beat a computer chess program since about 1988, I'm not sure what the point is, but I'm not really the target audience.

Finally, Steinn talks about string theory and The Trouble With Physics.

Any other suggestions of physics-related posts to make me feel a little slow this morning?


More like this

The two most talked-about books in physics this year are probably a pair of anti-sting-theory books, Lee Smolin's The Trouble With Physics, and Peter Woit's Not Even Wrong, which shares a name with Jacques Distler's favorite weblog. I got review copies of both, but Not Even Wrong arrived first (…
Fifty years ago today, the first tiny step was taken off planet. We may be more introspective nowadays, but we sure know how to Have Fun 2.0 Here is a selection of finds from the blogosphere, trawled up over the last few weeks. Some of these were sent in, some I picked as good examples of blog…
There's a piece by Michael Dine in Physics Today this month with the ambitious title "String theory in the era of the Large Hadron Collider, thus combining two of my very favorite topics... I was going to give it a pass, but I was surprised to discover that it's freely available-- most of their…
Via Twitter, Michael Barton is looking for some good books about physics. I was Twitter-less for a few days around the period of his request, and this is a more-than-140-characters topic if ever there was one, so I'm turning it into a blog post. The reason for the request is that he's going to be…

The NAND thing is actually maybe easier to understand if you just don't bother with the ant metaphor or the AI tie-in. This is actually just about boolean algebra.

NAND ("not and") is a simple operator in boolean algebra, such that (A NAND B) is equal to NOT(A AND B)-- that is, A NAND B is true whereever both A and B are false.

The problem the algorithm is trying to solve is, let's say you've got some boolean expression where the only operators are NANDs, and you want to know if the expression is true or false:


So the question becomes, how quickly can we solve this boolean algebra problem? And using these guys' algorithm, if N is the number you get when you count up the number of symbols plus the number of NANDs in the expression, then you can solve the problem in squareroot(N) units of time, where a unit is basically however long it takes you to do a single NAND operation.

There's some little complications due to the fact that this is a quantum algorithm and not a normal one, but that's basically it.

The reason why we might care so much about expressions made out of NANDS is that while this problem is very simple, there are a lot of seemingly harder problems that can be simplified to this one. (NAND and NOR, incidentally are special among boolean algebra's operators in that any boolean expression can be rewritten using only NANDs or only NORs.)