1. principles
  2. Inscrutable Science Update

Inscrutable Science Update

By drorzel on February 23, 2007.

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?

Tags
Physics
Science
String Theory
Categories
Free Thought

More like this

Peter Woit, Not Even Wrong
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 (…
Nordita Workshop for Science Writers, aka "Quantum Boot Camp"
Since this part of the trip is actually work-like, I might as well dust off the blog and post some actual physics content. Not coincidentally, this also provides a way to put off fretting about my talk tomorrow... I'm at the Nordita Workshop for Science Writers on quantum theory, which a couple of…
Teaching Generalizations of Probability
Hoisted from the comments, Robin asks: So, with that in mind, here's a question. What do you think about teaching quantum mechanics as noncommutative probability theory? In other words, by starting with probability theory and alluding to probabilistic mechanics (e.g., distributions on phase space…
Shor Calculations (Quantum Wonkish)
Over at Emergent Chaos I found an article which throws down the gauntlet over quantum computers. And there isn't anything I cherish more than gauntlets thrown down! Note: I should preface this by saying that I don't consider myself a over the top hyper of quantum computers in the sense attacked…

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