Macroscopic quantum objects cannot exist if P ≠ NP?
medium.com
medium.com
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.
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.
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.
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.
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.
Unlikely, but cute...
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.
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.
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.
No
Physics depends on mathematics, not the opposite.
Math exists regardless of physics.
Yes. Our theoretical models of the laws of physics are usually formal and axiomatic systems of logic (basically mathematics).
Yes. We understand and describe it using mathematical constructions we know of.
However, the laws of Nature do govern what kinds of models of computation are realizable (theoretically and physically). Limits on computability influence the design and sophistication of logic and mathematics. A good model of computation that we choose for this is some variant of a Turing machine. If this is true for our brains as well, then there is a limit on how sophisticated and powerful mathematics can be from our perspectives. In other words, the laws of Nature are dictating how good of a system of mathematics we come up with can be from a logical standpoint.
P=NP is not just statement about difficult problems or big equations, it's a very particular class of problems.
Regarding "Hypercomputation" in particular, I've typically encountered it in the context of "solving problems a TM can't solve" rather than "solving problems a TM can solve but asymptotically faster" - is it actually used for both? A skim of the article didn't clarify.
Of course, an Zeno machine, or a machine that can solve the halting problem, could also certainly solve problems a TM can solve but asymptotically faster.
I totally agree, which is part of why the article didn't clear it up.
"Of course, an Zeno machine, or a machine that can solve the halting problem, could also certainly solve problems a TM can solve but asymptotically faster."
A Zeno machine, for sure. It is not immediately clear to me that this necessarily holds for anything that can solve the halting problem - what about a TM plus a halting problem oracle that would tell you in 2^(size of TM) whether a TM halts?
Of course the real question is whether asymptotically faster is enough to be "hypercomputation". Necessity is also interesting, but not the same thing.
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.
Or at least any physical approximation of theoretical constructs like Turing machines.
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
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.
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.
in a given Universe there is only one cat. A human observer just doesn't know what the state of the cat in his Universe. The cat knows.
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.
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.
Not saying that this is the truth, just the way I choose to understand things.
Thank you for doing that.
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.
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.
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?
- 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?
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.
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.
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.
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]"
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.
Correct. I think that quote basically killed the whole article for me.
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.
Yeah, why can't we observe processes that rely on lack of observation?
The two-slit experiment works with photons, but not with bullets, or cars, or baseballs.