Macroscopic quantum objects cannot exist if P ≠ NP?

https://medium.com/the-physics-arxiv-blog/the-astounding-link-between-the-p-np-problem-and-the-quantum-nature-of-universe-7ef5eea6fd7a

by sleepysort • 12 years ago

59 74 12 years ago

medium.com

jjgreen• 12 years ago

The Navier-Stokes equations are also hard to solve, that does not stop fluids from obeying them.

sleepysort• 12 years ago

I'm not totally familiar with the Navier-Stokes equations, but from what I've just read (please correct me if I'm wrong!), I think the difficulty of the Navier-Stokes equation is reasoning about the solution set, while with quantum constructions the issue is whether or not a solution exists for some specific macroscopic system.

kazinator2• 12 years ago

Also, how can N bodies orbit each other? Don't they know there is no analytic solution to their problem? Sheesh! (Maybe they are using floating-point?)

raverbashing3• 12 years ago

I agree

For those who never saw the Navier-Stokes equation: http://en.wikipedia.org/wiki/Navier_Stokes#Derivation_and_de...

That's it. It looks simple but it involves Tensor math.

kazinator2• 12 years ago

This hypothesis seems to rest in the flawed idea that quantum processes must unfold as if by a step by step calculation which consumes time, in the ordinary temporal dimension. And so certain complex state changes are impossible simply because they don't have enough time to execute within some predetermined slot, or something like that. Time in the simulation is not the same as time in the simulator. Come on, this is not even basic science as much as basic sci-fi! :)

sambeau• 12 years ago

Surely Schrodinger’s Paradox implies cause and effect?

raverbashing3• 12 years ago

I'm not buying it

1 - P=NP is a mathematical problem. It has nothing to do with Physics. Physics has to do with Mathematics but one should be very careful when extrapolating (range, constraints, etc).

2 - Nature has no problem whatsoever solving complicated equations. Our mathematical models are the ones who suffer to model simple everyday stuff in Physics. Turbulence and Navier-Stokes equations, electromagnetic propagation, the way lightning goes through the air, etc.

swombat• 12 years ago

Unless, of course, our entire reality is running on a very powerful, but not infinitely powerful computer, and the Great Programmers in the Sky decided to cheat by putting in a hack that cuts off quantum behaviour at a larger scale...

Unlikely, but cute...

cstross• 12 years ago

The granularity of the simulation of our reality is the Planck length. This constraint does not apply to the real, underlying, reality within which our simulation is embedded.

nemo1618• 12 years ago

http://www.simulation-argument.com/

sk8ingdom• 12 years ago

Relevant xkcd: http://xkcd.com/224/

denim_chicken• 12 years ago

There is no evidence that nature can globally solve NP-hard problems. At best, nature finds locally optimum solutions to these problems.

trhway3• 12 years ago

There is no evidence that nature can globally solve NP-hard problems.

There is no evidence that nature has NP-hard problems. All the nature is built on local interactions - thus the finite speed of any interactions in the nature.

Note: the only example of non-local optimization (specifically maximizing entropy over time-space existence path of a living object vs. that would be an entropy change associated with the equivalent amount of non-living matter in similar environment) is the life itself.

kang2• 12 years ago

Your comments are non-constructive. This second point was almost religious.

To say that a mathematical problem has nothing to do with physics would not be right, since physics' major theories of today are essentially maths.

raverbashing3• 12 years ago

"To say that a mathematical problem has nothing to do with physics would not be right, since physics' major theories of today are essentially maths."

Physics depends on mathematics, not the opposite.

Math exists regardless of physics.

scott_s5• 12 years ago

For the record: I consider raverbashing's comments constructive. He/she is honestly engaging with the material and other people. The second point is similar to one several people have already made on the thread.

IanCal• 12 years ago

With 2, are you saying there are situations in nature that can solve NP-hard problems in polynomial time? Because if so, we could just use those to solve our hard problems and therefore P=NP.

P=NP is not just statement about difficult problems or big equations, it's a very particular class of problems.

scott_s5• 12 years ago

There are situations in nature where our models are NP-hard. Whether or not this is the same as saying that nature itself performs those computations is, I think, tied into the question of whether or not our Universe is a simulation.

baddox7• 12 years ago

Technically P=NP is just about Turing machines (and thus all Turing complete systems, which includes all the computers humans have produced). As far as I know there is no evidence of real super-Turing systems, but the concept has been theorized.

http://en.wikipedia.org/wiki/Hypercomputation

baddox7• 12 years ago

1 - P=NP is a mathematical problem. It has nothing to do with Physics.

I don't know if I accept that, although it's unclear what exact definitions you're using for those terms. P=NP makes very real claims about the abilities of real physical objects like Turing machines. It's obviously about math as well, but I don't see how that precludes it from being about physical qualities of physical systems.

2 - Nature has no problem whatsoever solving complicated equations.

Solving some complicated equations, no doubt. But I'm not aware of any evidence suggesting that nature can easily solve all complicated equations.

dllthomas5• 12 years ago

"the abilities of real physical objects like Turing machines"

Or at least any physical approximation of theoretical constructs like Turing machines.

nanofortnight• 12 years ago

P=NP is a mathematical problem. It has nothing to do with Physics.

There are some who would disagree with you. It is quite arrogant to assert that computer science has little to do with physical reality when our constraints on computational capabilities are very much embedded in reality.

Take a look at this survey article, for instance: http://www.scottaaronson.com/papers/npcomplete.pdf

todd8• 12 years ago

Thank you for the reference to the Scott Aaronson's paper, and to casual HN readers of this thread, I can't recommend this fascinating and easy to understand presentation enough.

dllthomas5• 12 years ago

"Nobody knows why we don’t observe these kinds of strange superpositions in the macroscopic world."

Yeah, why can't we observe processes that rely on lack of observation?

bcbrown3• 12 years ago

We can observe processes that rely on lack of observation in the microscopic world. Look up the one-slit and two-slit experiments[0]. In the two-slit experiment, we don't observe which slit the photon takes, but we can observe the interference pattern on the screen.

The two-slit experiment works with photons, but not with bullets, or cars, or baseballs.

[0] http://en.wikipedia.org/wiki/Two_slit_experiment

dllthomas5• 12 years ago

Hmm, probably fair.

Iftheshoefits• 12 years ago

I think the explanation for why we don't observe macroscopic quantum phenomena is rather more simple than that, and likely has more to do with the results of a superposition of a large ensemble of possible states than some fairly strained analogy with computation (think of it as something like fourier decomposition of a function).

kipple• 12 years ago

One part I didn't like is towards the beginning the author says: "Nobody knows why we don’t observe these kinds of strange superpositions in the macroscopic world. For some reason, quantum mechanics just doesn’t work on that scale. And therein lies the mystery, one of the greatest in science."

But I thought the reason we dont see macroscopic events exhibiting quantum superposition behavior was because of quanutm decoherence? It's just so hard to get a macroscopic situation that hasnt already been observed and collapsed.

But then the author kinda hints at this point later when he mentions: "Physicists have become increasingly skilled at creating conditions in which ever larger objects demonstrate quantum behaviour."

Am I missing something, or is he blowing the problem (and the impact of Bolotin's computational limit theory) way out of proportion?

bcbrown3• 12 years ago

An interesting assertion. I don't think it's valid to object that this is just about hard-to-solve equations. As I understand the article, this is the argument:

1) It's not possible to directly observe a macroscopic quantum object. This is because the act of observation collapses the wave function.

2) It's possible in theory to describe macroscopic quantum objects in the solutions to Schrodinger's equation

3) That solution for macroscopic systems is NP-hard

4) A physical theory that can neither be observed nor modeled is "nothing more than [a] nontestable empty [abstraction]"

pndmnm• 12 years ago

Interesting and semi-related: http://www.opticsinfobase.org/oe/abstract.cfm?id=140598

Essentially, solving the traveling salesman problem in quadratic time using photon interference -- however, since the photons scale up as N^N, the Schwarzschild radius of the effect means it's not observable in less than exponential time.

Dunnorandom• 12 years ago

For anyone interested, here's Scott Aaronson's response to the paper: http://www.scottaaronson.com/blog/?p=1767#comment-103591

ColinDabritz• 12 years ago

It sounds like the paper is pretty much gibberish from a scientific perspective, which makes sense.

It was, however, an interesting thought for me, and brought up a lot of classic philosophy questions about the nature of our universe, e.g. why would it matter if anyone could calculate it or not? If it was true would it lend evidence to a 'universe is computer-like' model?

Still neat to consider.

awhitty• 12 years ago

I understand that people get a little passionate about their fields of study, but the tone of Aaronson's response is wildly inappropriate. Phrases like "a common novice mistake" and "as if he just emerged from a cave" are unnecessary and entirely condescending. This style of discourse fosters a really awful and exclusive atmosphere, and I wish it wasn't the norm.

I don't know this guy at all, and I'm guessing he's pretty respected in his field, but at the end of the day, he doesn't have to be a jerk to get his point across.

mdxn3• 12 years ago

I can see how it can be read that way, though you should also to look at this from his perspective (or at least my guess as to a possible perspective).

The internet (and the field) is flooded with nonsense papers that don't respect the hard work of others. A lot of them really do come from these "common novice mistakes". The authors are taking very superficial views of complexity theory and physics against the advice of researchers in those fields. This particular one hasn't, but a lot of them have incredibly bad and egotistical attitudes. I think researchers see this as incredibly insulting, ignorant, and a severe lack of humility. People aren't showing enough respect and care to this field.

This wouldn't be such a problem if it didn't happen more often than not. On top of that, these poor findings end up swarming around the media and dilute the field. Look, Aaronson is a well known guy who has spent a lot of time trying to point out and explain these mistakes. Though people, including pseudo-scientists, completely ignore him. They even start fights with him. He and others get spammed with this stuff weekly if not daily. For him, I bet it's simply too much to ignore.

soganess• 12 years ago

I find the dismissive tone and holier and thou attitude that Aaronson has garnered more that bit of notoriety for really detrimental to the growth of both our collective understanding of QM and our understanding of computability. if knowledge is truly power, lording your knowledge over a peer is paramount to oppression. A bit dramatic, of course, but not completely without warrant.

This maybe a bit of a kumbaya, everyone hold hands argument, but I'm going to make it. Its not as if the number of people that have the ambition to collect the wealth of knowledge required to characterize(even incorrectly) any perspective overlap between computation and quantum is exactly a huge working set. I don't consider it reasonable to shit on someone's work so indiscriminately in this space where its rather hard to be right and quite easy to be wrong.

Prima facie, the paper was accepted for publish in a peer reviewed journal (Physical Science International Journal), and. from all the terse looks of it I've encountered, is likely erroneous on a fundamental level. Highlighting this is not meant to imply that peer-review is a good/bad measure of academic muster, but rather an indicator of how complex comprehending and qualifying such theories might be.

My point is, even in its incorrectness, a bravo for thinking so wildly is likely in order.

Disclaimer: I'm a quantum chemist and computer scientist. I'm also not the biggest fan of Scott Aaronson, so I might be harder on him that is likely deserved.

tomp2• 12 years ago

Wait what? What this article is arguing is totally absurd - just because we can't model certain physical objects, they cannot exist?! That's like saying that since we can't model three gravitational objects interacting (i.e. the numerical solutions diverge, therefore to properly model the system, we would require increasing amounts of memory and time), therefore they cannot exist.

I'm not saying that the physical claim is wrong - I'm just saying that the explanation in the article is severely lacking/logically inconsistent.

bcbrown3• 12 years ago

If something can neither be modeled nor observed, in what sense does it exist?

yid• 12 years ago

What does modeling have to do with observability?

jerf• 12 years ago

We observe n-body systems continuously. We are all participants in n-body systems continuously.

scott_s5• 12 years ago

That's not the question. Macroscopic behavior as described by Schrodinger's equation has never been observed. Because of having no observations, we assume it does not exist.

The linked paper is arguing, "Because solving Schrodinger's equation is non-polynomial, and such solutions are infeasible when N is large, then they can't exist." The linked paper is stating that the phenomenon has not been observed, assuming it does not exist, and then trying to explain why.

tomp's point is that we observe systems in our Universe that we can't model efficiently all the time. Hence, the line of argument in the paper doesn't hold up.

SnacksOnAPlane• 12 years ago

I'm a simulationist. I believe that the universe we're experiencing is a simulation made by a far-advanced civilization. So in my reality, if something can't be modeled, it can't exist.

Not saying that this is the truth, just the way I choose to understand things.

mikeash• 12 years ago

What says that the universe containing our simulation is unable to solve NP problems in polynomial time?

tomp2• 12 years ago

Still, until your belief is able to make physical predictions more accurate than other physical theories, it's just that - a belief, which has absolutely no physical validity.

mdxn3• 12 years ago

I think you would have to be assuming that the far-advanced civilization's simulator has the same complexity as the models of computation we can construct. I think that's a huge leap to make. We might not be able to model something due to issues with, let's say, Turing decidability. Unlike us, the advanced civilization's might be able to because their constructable models of computation are strictly more powerful.

drdeca2• 12 years ago

Is a reality where computers can store and process e.g. Actual real numbers, inherently inconsistent?

I'm not sure, but from what I remember from Wikipedia, doesn't that allow for computations that can not be done with turing machines?

Iirc, there are models of computation which are self consistent, and can simulate Turing machines, but are such that it seems impossible to simulate in our universe (or on a Turing machine).

If I am correct in remembering this, and if these machines can simulate things with values from a set with cardinality greater than aleph null, wouldn't the argument that we are likely to be simulations also argue that we are likely to be simulations on a machine in a reality capable of simulating with a more powerful type of computation.

Ok I'm going to say that there are many potential hole in my argument.

But I think it might be possible that machines capable of hyper computation could simulate an infinite number of Turing machines in parallel.

And if it could do that, then it should be able to simulate an infinite number of universes like our own (not like it's own probably though).

And as such, shouldn't any argument that our universe is probably a simulation due to a universe like our own containing a large (but finite) number of simulations of universes like our own, Equally validly argue that our universe is almost certainly a simulation in a universe with greater computational ability than our own?

I acknowledge that this argument has many assumptions behind it, and that many of them could be wrong. I hope this argument doesn't come off as nonsense (preferably just Misinformed)

Also I suppose the large number of simulations might not be your line of reasoning for your beliefs.

Also, I think there's supposed to be a hiarchy(spelling?) of hyper computation, so maybe the surreal numbers would be a better basis for the argument than the reals?

I'm not sure if my line of reasoning makes sense, but I thought I would mention it anyway.

typon• 12 years ago

This is such a poorly written article. I can't even begin to point out the mistakes. I'm sure Scott Aaronson will write a response and strike this down.

Strilanc• 12 years ago

I hope Scott Aaronson blogs about this article, because it espouses several of the wrong-facts he complains about and then cites him.

- Limitations on computers within physics are not limitations on physics itself. Analogously, you can simulate system so simple that a computer can't be made in them without your computer unmaking itself. Relevant: xkcd.com/505

- We do understand why we don't observe superpositions. It all comes down to this thing we call "quantum mechanics", which precisely describes those sorts of situations.

- The article consistently mixes up NP-Hard and NP-Complete.

"And how does the universe decide whether a system is going to be quantum or not?"

Seriously, is this article a satire?

PeterisP• 12 years ago

An interesting point is that limitations on math (i.e., things that would be true regardless of the details of the physical world) would put limitations on any physics simulations - including hypothetical physics simulations done by someone outside of our universe with potentially different physical limitations.

So the point of the article is something like - if phenomenon-X can't be simulated by anyone, no matter how good their computers become; and if our universe is a simulation (which is a possibility), then our universe won't contain phenomenon-X.

TheLoneWolfling2• 12 years ago

The problem is that there is no proof that there is any such thing as something that would be true regardless of the details of the physical world.

wcoenen• 12 years ago

We can't directly observe superpositions (macroscopic or otherwise) because when doing so, we become entangled with the state of the observed object. The only thing special about macroscopic objects is that it is difficult to prevent or postpone their entanglement with the environment.

Think about Schrödingers' gedankenexperiment from the cat's point of view. It finds itself to be either comfortable or dying by toxic fumes; it can't see the superposition because it is inside of that superposition. The same thing happens to any observer trying to look at a quantum superposition.

JulianMorrison2• 12 years ago

Box closed: two cats, one scientist. Box opened: two cats, two scientists, each sees one cat. Entangling yourself with the superposition pulls you into it.

trhway3• 12 years ago

Entangling yourself with the superposition pulls you into it.

following that logic and taking cat as the observer, Mr.Cat PhD, the superposition is that doubles the number of cats (and PhD's :).

Yet it works in the other direction - entangling a cat (a macro-object with macro-state) with superposition had already destroyed the superposition well before box is opened.

> it can't see the superposition because it is inside of that superposition.

it can't see the superposition because the superposition is gone because he got entangled with it.

ctdonath• 12 years ago

This is radiantly insightful. It makes perfect sense to me. The effect of reading it is like drinking a Pan Galactic Gargle Blaster: feeling like my brains were smashed out by a slice of lemon wrapped round a large gold brick.

Yes, in real physics solves vastly complex equations fast. That's not enough to discount the point here. There are limits on physics itself: the particles in a cat (presumably one owned by Schrodenger) are so numerous that for all of them to express, within a reasonable time, superpositioning the effects of a single radioactive atom's unobserved state would require particle interactions occur way faster than Planck time.

Nothing moves faster than light. There are a finite, albeit large, number of particles in the universe. Nothing can be smaller than Planck length, and no particle interaction can occur faster than the time light takes to move one such unit. Upshot: macroscopic superpositionining effects cannot occur because it takes too long for full propagation among particles numbering on the magnitude of Avagadro's number.

There's an upper limit to what can happen, because there's only so much stuff and "happen" can only be so fast.

baddox7• 12 years ago

What’s interesting about NP-hard problems is that they are mathematically equivalent. So a solution for one automatically implies a solution for them all.

That's a mistake. The author is describing NP-complete problems, which are all roughly equivalent (reducible in polynomial time). NP-hard includes all NP-complete problems, but also includes problems much harder than those in NP-complete, including undecidable problems like the halting problem which aren't even in NP.

pcvarmint• 12 years ago

That's a mistake. The author is describing NP-complete problems...

Correct. I think that quote basically killed the whole article for me.

baddox7• 12 years ago

It didn't kill the whole article for me, although it seems to be a consistent misconception rather than an isolated typo. To be fair, the naming convention is pretty tricky, considering NP-hard contains things outside NP.

lfuller• 12 years ago

By this logic, shouldn't the existence of the universe be impossible since simulating it mathematically in its entirety is infeasible?

snake_plissken• 12 years ago

I thought you could observe quantum effects but only when it was the superposition of all the eigenfunctions? You never observe the ones with a low probability density because they are dominated by the others. And also does it matter if you could solve numerically all of the functions for a macroscopic group of particles if in the end all you would care about is the average value (due to Planck's constant and the uncertainty principle)?

agorism• 12 years ago

This is almost the same as the free-will vs determinism problem. Our universe is deterministic, but computing into the future is NP-complete.

TheLoneWolfling2• 12 years ago

An interesting tidbit:

If the smallest proof for something takes up more than ~10^123 bits, or the fastest proof requires more than ~10^120 operations, it cannot be proven in our universe.

Macroscopic quantum objects cannot exist if P ≠ NP?

Related Stories