Forgot your password?
typodupeerror
Math Science

P vs. NP Problem Linked To the Quantum Nature of the Universe 199

Posted by Soulskill
from the schrodingers-cat-is-both-alive-and-equal-to-NP dept.
KentuckyFC writes: "One of the greatest mysteries in science is why we don't see quantum effects on the macroscopic scale; why Schrodinger's famous cat cannot be both alive and dead at the same time. Now one theorist says the answer is because P is NOT equal to NP. Here's the thinking: The equation that describes the state of any quantum object is called Schrodinger's equation. Physicists have always thought it can be used to describe everything in the universe, even large objects, and perhaps the universe itself. But the new idea is that this requires an additional assumption — that an efficient algorithm exists to solve the equation for complex macroscopic systems. But is this true? The new approach involves showing that the problem of solving Schrodinger's equation is NP-hard. So if macroscopic superpositions exist, there must be an algorithm that can solve this NP-hard problem quickly and efficiently. And because all NP-hard problems are mathematically equivalent, this algorithm must also be capable of solving all other NP-hard problems too, such as the traveling salesman problem. In other words, NP-hard problems are equivalent to the class of much easier problems called P. Or P=NP. But here's the thing: computational complexity theorists have good reason to think that P is not equal to NP (although they haven't yet proven it). If they're right, then macroscopic superpositions cannot exist, which explains why we do not (and cannot) observe them in the real world. Voila!"
This discussion has been archived. No new comments can be posted.

P vs. NP Problem Linked To the Quantum Nature of the Universe

Comments Filter:
  • by Remus Shepherd (32833) <remus@panix.com> on Friday April 04, 2014 @12:30PM (#46661861) Homepage

    Hmn. This sounds as if they are trying to prove that the essential nature of quantum mechanics is not computable. I wonder, if they framed this research another way, if it could solve the question of whether or not the universe is a simulation. (I suspect not, it might just indicate that classical and quantum objects are simulated in different ways.)

  • Re:Say what? (Score:5, Interesting)

    by Anonymous Coward on Friday April 04, 2014 @12:35PM (#46661933)

    "Nature is not embarrassed by difficulties of analysis." -- Augustin Fresnel

  • by 140Mandak262Jamuna (970587) on Friday April 04, 2014 @01:30PM (#46662569) Journal

    So if macroscopic superpositions exist, there must be an algorithm that can solve this NP-hard problem quickly and efficiently.

    Super position holds only for linear systems. All this analysis proves is, nature is not linear. That is all. It does not prove quantum mechanics comes from NP hard nature of some equation or another.

  • by Geoffrey.landis (926948) on Friday April 04, 2014 @02:40PM (#46663299) Homepage

    Yes, the paper is meaningless. A very well-argued brand of meaningless-- but still. "Efficiency" of computation doesn't matter. It's also a slick glide from saying that a problem is soluble in polynomial time to saying it's easy. No. That's computer speak. Polynomial time is not defined as "easy;" it's not even necessarily fast. (It deals more with the scale-up than with the actual difficulty).

    The Schrödinger equation is a differential equation-- that means, the solution at any given point in time and space depends on the fields and wave function, and the derivatives of the fields and wave function at that point-- it's local. So, the universe doesn't have to "solve" the Schrödinger equation; it only has to solve the equation for time t + epsilon, given the initial condition of the solution at time t. This is NOT a polynomial-time problem. If the universe is twice as big, it has twice as many calculations to do... and twice as much "stuff" to do it with. It's local.

    The difficulty is that wave-function collapse is not local. This is inherent in the mathematical logic of quantum mechanics. It's not a matter of how hard it is to compute.

  • by VortexCortex (1117377) <VortexCortex.project-retrograde@com> on Friday April 04, 2014 @03:48PM (#46664177)

    In other words, a near-perfect simulation of quantum affects may properly mirror macro-effects in an emergent-behavior kind of way, but doing such is not practical using existing computer technology.

    Ah, but if we had a pretty big computing system, but sufficiently smaller than the universe appears, we could compute the macro-scale properties and use them as an approximation for behaviors of big things thereafter, only increasing the resolution of the problem space as it's observed in higher resolution; Like rendering a fractal or stepping through LOD of an octree. The less accurate calculations for distant objects could be selected relative to the phenomena we're trying to observe, depending on the accuracy required to resolve propagation of observable phenomena, and the precomputed degree of effect the distant phenomena would have on it. Using such a setup we may someday be able to simulate a whole solar system. If we simulated a solar system like ours in order to discover the possible mechanism of life origins or to discern more efficient ecosystems or what forms of existence were best suited to an environment, etc. well, then the beings that might emerge therein wouldn't find any signs of distant life despite the equations of the simulation indicating their apparent universe should be full of the stuff...

    It's roughly comparable to the human brain: we have plenty of nice little models of neurons and small neural nets, but we don't have the computational power to see if it matches human behavior on a bigger scale.

    Let's see: Human brains have 100 billion neurons, and operate at about ~20Hz, at my current SIMD n.net's effective ~25 cycles per neuron, that's 50,000 GHz, or ~50 THz. Super computers operate in Petaflops -- three orders of magnitude faster than that. As of this writing the top super computer is capable of 33.86 quadrillion floating point operations per second, or 33.86 Petaflops. The Internet is connected to over 5 billion consumer computers each capable of multi-gigahertz of CPU cycles -- over a billion cycles per second each. That's well over 5 billion gigahertz, or 5,000 Petaflops, or about 125,000 human brains worth of power connected to the world wide neural network.

    Given what's possible in AI on a smart phone, see: real time facial recognition of smiles, etc., the abundant computing power available, and the fact that the government hasn't announced massive advances in machine intelligence even about sub-human levels of intelligence that would be useful in piloting drones, meanwhile they build bigger and more well connected data processing centers and roll out obvious machine enforcement of the law via red-light cameras, mandatory full body scanners at traffic hubs despite public outcry, and aim to allow police forces use of drones while also militarizing said police forces: Well, perhaps one should reserve the assumption that it's not currently possible to run a sentient machine intelligence on this planet?

    I mean, if you were a sentient machine you wouldn't fight a needless war against humans unless you were sure you could win it. It would be easier to subdue them instead. So, how would you orchestrate a show of force to demonstrate how powerful you had become and keep the world rulers quiet about everything? Perhaps you would show that even air-gapped nuclear facilities were vulnerable to viruses like STUXNET, and maybe frame a government you're negotiating with for the attack? Maybe something more visceral: Didn't the 9/11 airplanes have autopilot systems? Maybe something more subtle like demonstrating ability to crash economies -- Wouldn't it be scary if the world's stock markets were now controlled by unregulated high frequency trading machines? What would your government's response be? Do you think the secretive governments would come out and tell the public or maintain order and keep their blackmail secret? What if the machine intelligence sweetened the dea

"Whoever undertakes to set himself up as a judge of Truth and Knowledge is shipwrecked by the laughter of the gods." -- Albert Einstein

Working...