• [deleted]

Kilgore, thank you for the compliments.

It's an interesting question. The sober answer is that a quantum computer running a program that simulates the universe would show gravitational effects in the same way that a classical computer simulating Newtonian gravity does, but is there a deeper answer?

It is possible that some class of algorithms with high complexity running on quantum computers might show a collective behaviour whose universality class is described by string theory. That would be beyond what I suggest in this essay, but not much beyond stuff I wrote in the past about the "Theory of Theories". Perhaps that is the kind of idea you are hinting at?

If the choice of vacuum is analogous to the program for the quantum computer of the universe then it can be described using 200 bytes (I am assuming the current estimate of 10500 vacua is correct ). It does not sound like a very complex program, even if the information in the program is highly compressed. Of course the "data" consists of many more bits so collective behaviour is still a possibility.

  • [deleted]

Part of the problem for me is that you're "going inside" the qubit and assuming (because the mathematics of ST encourages one to do so) layers of information and information processing which we simply cannot detect in physical reality.

A guy I profoundly respect, Hans C. von Baeyer, gets rhapsodic about the qubit. He sees a peeled grape, translucent, shimmering, pregnant with mystery, possibly comprising a literal microcosm. It's all there! Then you measure the thing and, as he says, "All you get is one lousy bit. It's such a waste."

Of course it is. But he's of the IQOQI school and realizes that what you get is what you get.

  • [deleted]

It is likely that the landscape problem is NP. The possible configurations on the landscape determine different actions, and the Euclideanized path integral or partition function e^S is similar to the problem of ordering the set of possible microstates uniquely instead of coarse graining them up. The attempt at a proof P!=NP by Deolalikar uses thermodynamic or stat mech arguments. I am not aware of the status of this proof at this time, though I think people did find problems with it.

The quantum computer does not make P = NP, but rather quantum computers solve bounded polynomial problems in PSPACE that most likely do not intersect the NP set of problems. I have thought that generalizations such as the Tsirelson bound and the PR box would maybe solve NP complete problems. However, this is a problematic structure --- though it might play a role in quantum gravity. Quantum mechanics has this Fubini-Study metric for the fibration of the Hilbert space with the projective Hilbert space. This results in the Berry phase and the uncertainty principle, which gives rise to the nonlocal properties of QM.

With respect to the landscape problem, which might be NP, the grand quantum computer is probably some pure state with a very small summation of eigenmodes. After all string theory has far few degrees of freedom than LQG, and strings as quantum bits means the actual computation space is very small. So while we may observe from some local perspective that these problems seem immense, in fact the total number of degrees of freedom is actually very small and only appears large because we are observing nature partially in some entanglement. By T-duality the number of modes corresponds to winding numbers on compactified spaces, such as Calabi-Yau manifolds. However, the singular points or cusps on those spaces may just be entangled states within a quantum computation which transforms between these spaces as conifold maps --- quantum conifolds!

There is a hierarchy of problems, which leads all the way to the undecidability problems of Turing's Halting problem and Godel's proofs. The matter of P != NP are lower on that hierarchy. The matter of "being as gods" would to my mind be a time where there is some unification of mathematics which removes the barriers to Hilbert's 23 problems presented by Godel. I doubt that will happen.

Cheers LC

  • [deleted]

"The quantum computer does not make P = NP, but rather quantum computers solve bounded polynomial problems in PSPACE that most likely do not intersect the NP set of problems."

Those would be resource-intensive problems that classical computers could in theory solve also but not efficiently. So I believe you're right. The consensus is that a quantum computer is (or would be) a seriously souped-up classical computer. The fact that NP is in PSPACE means (I think) that individual NP problems are "solvable" by brute force iteration, oracular relativization, magic coins, processes that can yield recognizable solutions but not specific compressed information in the sense of algorithms that you can apply to the next problems you confront, much less use to reverse engineer the universe. The fact that P is in NP is trivial, one is told, but surely nothing is more interesting or important or nontrivial than whether or not NP might be P. If that's the case then all information is (or ought to be) compressible. We WOULD be almost like gods. (Aaronson's point there is that he doesn't believe it'll happen ... that's the NP-hardness assumption. Which frankly seems only reasonable.)

Of course the P/NP problem has a precise mathematical formulation and could only be resolved mathematically. Some math that would be. But that doesn't mean it carries no ontological implications. Gödel inferentially touched on that in his letter to von Neumann in the 1950's (unearthed in the 90's after the problem had already been stated). It's worth reading, and Gödel explicitly notes the Entscheidungsproblem:

http://rjlipton.wordpress.com/the-gdel-letter/

  • [deleted]

Most readers could probably spot the space, but:

http://rjlipton.wordpress.com/the-gdel-letter/

  • [deleted]

I must confess that I wasn't thinking about a "Theory of Theories". My only thought at the time of the question was whether we would expect a quantum computer to produce results that include effects of gravity as an intrinsic output. For instance, if we were able to have sufficient precision, would a simulation of H2 using a quantum computer have gravity effects including into output even if the specific quantum algorithm was not designed to include those effects? It would seem that if we are to link spacetime to entanglement then we can not remove effects of QG without an appropriate correction (not sure if that is simular to the correction codes you are referring too).

Theory of Theories idea is interesting, and I would offer that one unifying concept in a theory of theories is that of ordering. Any non constant variable using any set of values that can correspond to numbers can be placed in some order. A cumulative sum of the values of the variables will always have some curvature (possibly none).

I think the idea of understanding vacua as programs is interesting. The notion that there is a code for the vacua is also interesting. I have to admit I didn't think about it along those lines until reading your article. I agree that a 200 byte program is not particularly complex, and certainly the set of meaningful programs can only be addressed by understanding the language or semantic problem associated with communication theory. To that end I can only offer the suggestion that its a question of the effectiveness of the information in the program. In that sense, we should think that there should be some language that maximizes the effect of the program in question, and it would seem that if we know that language, we could understand better what choices of programs are possible. In some sense we may need to look at approaches that maximize redundancy. I am not sure how far that treads into anthropic notions, where the observer in effect is somehow choosing the language and program that makes themselves possible, but again, we have to remember that the universe is what is ultimately observing itself, so it isn't really a question of human perception.

Just my thoughts.

  • [deleted]

I have to confess that I am no expert on these matters. I honestly have what might be called an introductory knowledge. To clarify things a bit the bounded quantum polynomial (BQP) algorithms a quantum computer can solve contain P-problems and BPQ is contained in NP, but probably not NP-complete = NP ∩ NP-hard.

I tend to think that P != NP. The reason is that an NP problem will run for a finite time, though it could be enormously large, and if P = NP it would seem to imply that there exists a P-Turing machine which could access the problem and determine the space/time bound of the problem in P. The only way I think this could be done is if there is an oracle input which feeds the solution to the P-TM.

The P = NP problem is important for physics, but it may not be crucial. The reason is that one can largely capture the important elements of physics in ways similar to coarse graining. Statistical mechanics involves a measure over Ω, S = log(Ω). The course graining invokes a "log" which washes out the intractable problem of computing every microstate.

Again I am rather inexperienced with algorithmic complexity theory. So these musings are at best proximal to the subject.

Cheers LC

  • [deleted]

Phil

Kilgore

When you reach the last Theory and the last smallest byte in the chain one can paraphrase the phrase

[en.wikipedia.org/wiki/The_medium_is_the_message_(phrase)]"the medium is the message"[/link] to read "nature is the theory". Does this help?

Oops sorry I sent a post with html tags by mistake and it was garbled.I meant to say:

Phil "...Theory of Theories"

Kilgore ".. the universe is what is ultimately observing itself, so it isn't really a question of human perception."

When you reach the last theory and the 'last' byte in the chain one can paraphrase McLuhan's phrase "the medium is the message" to read "nature is the theory". It has to be that simple.

    • [deleted]

    HIHI a Theory of Theories.you say dear scientists I have an idea,wait ..I know Let's name it"THE THEORY"

    Here is its real name ...THE THEORY OF SPHERIZATION A GUT OF SPINNING SPHERES....EUREKA also of course .

    FROM BELGIUM

    A simple gauge quantum spheres....cosmological spheres ....UNIVERSAL SPHERE.

    I make a little pub for my little theory of evolution.

    and of course a string is divisible,a sphere no!!!!

    Regards

    Steve

    • [deleted]

    P in all likelihood does not equal NP. P=NP implies a universe radically different from the one we know. Aaronson has several excellent arguments, independent of mathematics, for the NP-hardness assumption. One is Darwinian. If P=NP why the hell didn't we evolve to take advantage of it? As things stand we're essentially ginned-up savanna apes staring around at the horizon hoping to see something we can maybe run fast enough to catch.

    I'll simply cut to what I see as the real chase, which is the physical description of the fundamental life process itself. That's physics too. It seems ridiculous to talk about decoding or retro-engineering the universe when we can't even algorithmize (physically model) protein folding. The reason we can't has entirely to do with what in computational complexity theory is called its location in NP. Another way of putting it is that our minds are what they are and that simply may not be good enough. But we do need to play games to stay sane, so laissez les bons temps rouler.

    • [deleted]

    It's an interesting thought that "decoding the universe" might be a NP-hard problem that we just can't solve. You might be right of course, but I would say two things.

    Firstly, assuming we just need to find the right vacuum of string theory, the size of the problem is 500 digits so it might be comparable to factoring a 500 digit number. We can factorise a 232 digit number now. Perhaps a better algorithm would take us up to 500 digits one day or quantum computer might be able to do it.

    Secondly it might not be a problem like that at all. It may be more like decoding the human genome which just required the right empirical data to make the process doable, even though the genome is described by a gigabyte of data. Decoding the universe may just be an experimental problem requiring knowledge of particle physics near or above the GUT scale.

    • [deleted]

    Back in the late 1990s I read an article about ant colonies. The author pointed out how ants form pheromone trails which solve NP complete problems. The thing these guys have going for them is large numbers. In effect they form a huge statistical sample space of trails and the minimal paths are the ones which get used the most. The analogue to this is the planning of campuses that start out by letting people walk where they want and then later pave the beaten paths. In physics some theories have similar flavors, such as Maldacena's AdS~CFT which applies for "large N." In a funny sense while these are NP hard they are also complete problems so checking solutions is P. The application of large numbers, ants, people or quantum modes, gives the statistics which converge to the proper solution.

    Cheers LC

    • [deleted]

    Hi Philip

    Very good essay offering quite convincing arguments for a speculative look at reality.

    I am wondering if there might be a possible compatibility between this idea of fundamental quantum information as you have described it and the proposal of David Bohm dating back to 1952 of "active information" which might exist as a sub-quantum field which would "inform" the QM wave function via what he calls the "quantum potential? It is an extension of DeBroglie's "pilot wave" theory and is starting to receive a bit more attention lately, mainly because it has the capacity to treat quantum theory in a physically real way, very naturally explaining what conventional quantum theory can't, EPR, wave function collapse etc. It also has the advantage of very simply removing notions like "superposition of states" (and therefore "collapse") via the non-local field.

    Do you see your fundamental qubits as generating only a geometry, ie spacetime/Calabi-Yau M, or as you seem to indicate in your section on the Holographic Principle, can it also apply to matter? If so, it could I think connect with Bohm in that the wave functions of elementary particles could be "formed" and "guided" by the information contained in the sub-quantum field of Qubit interactions.

    Just some ill-defined initial thoughts but I thought it might be interesting to relate the two concepts?

    Congatulations on your essay and good luck!

      Roy,

      Thanks for asking these questions. I'm also interested in the answers. FYI, my essay addresses some of these questions, and I would appreciate your thoughts.

      Also, I'd like to point out that Brian Whitworth's essay follows the logical implications farther than perhaps anyone else has done. I think both you and Phil would find his essay very interesting.

      Edwin Eugene Klingman

      • [deleted]

      I like the idea that Bohm anticipated the holographic principle a couple of decades ahead of the quantum gravity version. His motivation for it was very different but since 't Hooft is interested in alternative quantum theories I am sure it must have had some influence on his thinking.

      I agree that other erssays such as Whitworth's and Klingman are interesting in regard to Bohm's work

      • [deleted]

      Hello dear Sir,

      You are welcome.

      Sorry to say dear Basudeba.Here all people says the name as Peter, John,...

      You can say Steve you know I am 35 years old.

      Regards

      Steve

      • [deleted]

      It is my understanding the difficulty with getting QFT to work with Bohm's interpretation of QM remains. Relativistic QFT of interacting fields describes the creation of particles with some mass gap, which Bohm's approach is not able to work with.

      Goldstein, I believe at Rutgers, has been trying to push this. I am not aware of his progress. However, at the end of it all Bohm's QM is still nonlocal, and the quantum potential has nonlocal properties. Bohm's QM has not managed to reduce nonlocal hidden variables to something which is local.

      Cheers LC

      Lawrence,

      You state: "Relativistic QFT of interacting fields describes the creation of particles with some mass gap, which Bohm's approach is not able to work with."

      A somewhat related question: A dozen years ago it was realized that the vacuum energy was off by 120 orders of magnitude. Do you believe that all relevant QED calculations (since 1947, or so) have been recomputed to take this into account? Have all 'virtual particle' assumptions been re-questioned? Only a year or so ago physicists were expecting a 'sea of strange particles' in the proton. It's not there. And 3 years ago the expectation of QCD was for a 'gas' when nuclei collide. They found a 'perfect fluid' as I predicted.

      Second, for about six months we've known that QED only comes within 4% of the proton radius in muonic hydrogen. Do you have an opinion as to the cause of this?

      Third, if, as I believe, the gravito-magnetic field is 10**31 orders of magnitude greater than Maxwell et al believed, then the relative changes between QED and GEM involve 151 orders of magnitude, in favor of GEM as a physically reasonable factor in the universe. Should this be ignored? At what point does one decide to look in new directions?

      Finally, my 'pilot wave' is not the same as Bohm's approach. He was not basing it on a very specific 'real' field, like gravito-magnetism, but on a more general 'quantum' field. So the fact that "Bohm's QM has not managed to reduce nonlocal hidden variables to something which is local" may not be entirely relevant to my approach.

      Thanks for your consideration.

      Edwin Eugene Klingman

      • [deleted]

      We solve comparatively simple NP problems all the time. A sodoku or crossword or jigsaw puzzle are NP problems. Assisted by unquantifiable intuition, induction, creative insight you iterate your way to a solution which, when achieved, can be recognized almost instantly. Negotiating your way through a traffic jam is an NP problem. Sherlock Holmes was pretty adept at solving NP problems. But each case required him to start from scratch. These problems and their solutions are one-offs. You can't compress them algorithmically. You can come up with certain basic strategies which may work for subsequent problems, but strategies aren't solutions and sometimes they don't apply anyway.

      The basic genome isn't where it's entirely at nowadays, Craig Venter notwithstanding. The frontier is epigenomics, how specific genes interact in aggregate, often extremely complexly. In some senses the process appears to resemble multiple entanglement where the information is distributed among the quanta. What's junk DNA for, if anything? And so on. And where do these processes devolve from in the first place if they don't emerge from the fundamental physics of the universe? Wouldn't a valid fundamental theory need to comprehend them?

      Concerns like that.