Comments on: Barbeque ribs and AWPP forever

By: Nosy Snoopy

Nosy Snoopy — Tue, 27 Mar 2007 16:38:17 +0000

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!

By: Greg Kuperberg

Greg Kuperberg — Tue, 27 Mar 2007 02:21:36 +0000

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.

By: Nagesh Adluru

Nagesh Adluru — Tue, 27 Mar 2007 01:36:05 +0000

Oh! This makes sense now:) Thanks Andris and Scott.

By: Scott

Scott — Tue, 27 Mar 2007 00:38:29 +0000

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!

By: Greg Kuperberg

Greg Kuperberg — Mon, 26 Mar 2007 20:14:52 +0000

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.

By: Moshe

Moshe — Mon, 26 Mar 2007 19:29:48 +0000

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)

By: Scott

Scott — Mon, 26 Mar 2007 18:09:33 +0000

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!

By: Scott

Scott — Mon, 26 Mar 2007 18:01:12 +0000

Nagesh, Almost Wide Probabilistic Polynomial-Time and ribs are two of Lance’s greatest pleasures in life.

By: Andris

Andris — Mon, 26 Mar 2007 17:03:55 +0000

Nagesh,

I think Lance has posted about barbeque (e.g., the best barbeque places in Chicago) a few times.

By: Nosy Snoopy

Nosy Snoopy — Mon, 26 Mar 2007 16:52:45 +0000

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.