Barbeque ribs and AWPP forever
Lance has announced, completely unexpectedly, that he is ending his blog. In shock and sadness, I posted the following comment, which I thought I should share here as well.
No, Lance, no — tell me it isn’t true! Yours was the first blog I ever read. That familiar puke-green background was my rock, my North Star, in the vast and ever-shifting blogosphere. Your invitation to have me guest-blog gave me my first taste of being flamed by angry commenters — thereby leading directly to Shtetl-Optimized, where I get to repeat that same masochistic experience every single day.
The burden you’ve placed on my shoulders — and Luca’s, and Dave Bacon’s, etc. — is an extremely heavy one.
Lance, we will miss you (turn speakers on before clicking the link).
To honor Lance’s blog’s memory, the background of my own blog will temporarily be puke-green as well.
Follow
Comment #1 March 25th, 2007 at 5:37 pm
Will I always associate that color with the theory of computer science? Boy I hope not!
Comment #2 March 25th, 2007 at 6:37 pm
Make it stop, you awful, awful man.
Comment #3 March 25th, 2007 at 7:27 pm
I prefer to think guacamole or eco-friendly, rather than the smart-ass association made in the posting. I’ll miss Lance’s blog a lot.
Comment #4 March 26th, 2007 at 8:08 am
Scott, I cannot connect your title of the post to it’s content. Could you please throw some more light. Does one have to be non-vegetarian to get it?
Comment #5 March 26th, 2007 at 8:52 am
Good day, dear Mr. Aaronson
Don’t you know, could such a thing be possible that in addition to quantum computers there could be “string” computers which are more powerfull and there could be computers which are more powerfull than “string” computers and so on ad infinitum?
Here is a paper (http://arxiv.org/abs/hep-th/0008217) I smelled out, author says about a ladder of infinite quantization, but as I am ignorant I didn’t understand anything more.
Comment #6 March 26th, 2007 at 9:03 am
Nagesh,
I think Lance has posted about barbeque (e.g., the best barbeque places in Chicago) a few times.
Comment #7 March 26th, 2007 at 10:01 am
Nagesh, Almost Wide Probabilistic Polynomial-Time and ribs are two of Lance’s greatest pleasures in life.
Comment #8 March 26th, 2007 at 10:09 am
Snoopy, the short answer is that we don’t know whether string/M theory and other quantum gravity theories lead to models of computation more powerful than quantum computing. The main reason we don’t know is that physicists don’t even have the mathematical formulations of these theories yet! However, everything we know now is consistent with the possibility that quantum computing is the “end of the line,” i.e. that quantum computers are the most general type of computer allowed by the laws of physics. This is particularly true since most current proposals for quantum gravity would leave the Hilbert space structure of quantum mechanics intact.
For more info, see my survey paper NP-complete Problems and Physical Reality.
Hope that helps!
Comment #9 March 26th, 2007 at 11:29 am
As far as I know string theory currently needs no modifications of quantum mechanics at all. The problems with quantizing gravity are avoided by quantizing other degrees of freedom which are apparently more fundamental, getting gravity as a low energy phenomena only.
\
Alternative approaches, which by and large take the metric as the fundamental object to be quantized, have to deal with the well-known conceptual and technical problems of such program by (among other things) modifying quantum mechanics. It is interesting to find limits of such modifications (presumably) by setting limits on the enhancement of computational power this would entail.
\
(I am truly sorry if this comment brings about string wars to this serene thread, hopefully not)
Comment #10 March 26th, 2007 at 12:14 pm
Snoopy, the short answer is that we don’t know whether string/M theory and other quantum gravity theories lead to models of computation more powerful than quantum computing. The main reason we don’t know is that physicists don’t even have the mathematical formulations of these theories yet!
Well, string theory has a mathematical formulation, and string theorists strongly believe that a mathematical formulation of M-theory is waiting to be found. Since M-theory is supposed to be consistent with string theory, some of its main features are known.
Working mostly from inferential properties quantum gravity (such as Hawking radiation), but properties that are in some cases supported by string theory, the wisdom that I have heard is that quantum gravity does not extend computational power, rather it limits it. For instance, the string theorists believe in holography, which says that the information capacity of a region in space is bounded by its surface area rather than its volume.
Comment #11 March 26th, 2007 at 4:38 pm
Greg, John Preskill speculated in a lecture some years ago that since M-theory seems to be highly nonlocal, even if it’s completely unitary, it might let you apply unitary operations that couldn’t be applied in polynomial time in the gate model. When I asked Maldacena about this idea at IAS, he said that even if M-theory is nonlocal in one description, there’s still expected to be a dual description where it’s local, so presumably one could use the dual description to simulate the theory efficiently.
So yes, I do tend to agree with you that the main computer-science implication of quantum gravity seems likely to be the holographic entropy bound. On the other hand, until we have an actual theory to define a complexity class around (BQGP?), I’m not going to make any dogmatic pronouncements!
Comment #12 March 26th, 2007 at 5:36 pm
Oh! This makes sense now:) Thanks Andris and Scott.
Comment #13 March 26th, 2007 at 6:21 pm
On the other hand, until we have an actual theory to define a complexity class around (BQGP?), I’m not going to make any dogmatic pronouncements!
Even if there were an actual theory, I might not be qualified to characterize it.
But I did once query the best available wetware oracle: Ed Witten. Witten said that he didn’t see any new computational power in quantum gravity, then cited the holographic bound. He also asked if I was in cahoots with Leonard Schulman, who had recently asked him almost the same question.
Comment #14 March 27th, 2007 at 8:38 am
Scott said: However, everything we know now is consistent with the possibility that quantum computing is the “end of the line,” i.e. that quantum computers are the most general type of computer allowed by the laws of physics.
For more info, see my survey paper “NP-complete Problems and Physical Reality.”
Hope that helps!
Thank you very much, it is cool thing I can ask real researchers.
The title of another your paper “Is P Versus NP Formally Independent?” attracted my attention, I don’t know why. May be because it is somehow connected to such a thought: Imagine that there are universes in which this ladder of more powerfull computers exists with different number (or even infinite number!) of footsteps. (Unlucky those guys in the universe without quantum computers 🙂 How can we determine what is the number of footsteps in our Universe? We need some kind of experiment to measure something?
I like this creepy thought about infinite ladder. Ooohhh!