# 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?

## Comments

1. #1 Blake Stacey
February 23, 2007

Quantum Groups” at Yidun Wan’s Road to Unification?

2. #2 Coin
February 23, 2007

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:

( (A NAND B) NAND (D NAND E) ) NAND ( (F NAND G) NAND (H NAND I ) )

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.)

New comments have been temporarily disabled. Please check back soon.