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.
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.
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.
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?
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.
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...
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.
> 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.
> 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.
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.
>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.
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.
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.
If natures models reduce to our NP-hard models which they would if our models are accurate, that is to say if and only if there is some computation that is NP-hard (which means that it is proven to not have a polynomial time solution unless P=NP) that nature can solve in polynomial time and we have proven that P must equal NP.
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.
Right. "There exists a device that can solve NP problems in P time" is a different statement than "P=NP".
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.
That's a good point. The first sentence of the Wikipedia article says "Hypercomputation or super-Turing computation refers to models of computation that go beyond, or are incomparable to, Turing computability." The "incomparable to" part is sufficiently vague to shoehorn in asymptotic improvements if we want to. :)
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.
'The "incomparable to" part is sufficiently vague to shoehorn in asymptotic improvements if we want to.'
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.
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.
This is overly general. And we need to make a distinction between actual physics (laws of Nature) and our theoretical models of such.
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.
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.
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.
>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.
The cat is pulled into the superposition by interacting with the results of the detector and the poison vial. There are two cats from the "outside", but from each cat's perspective it sees only a single "random" outcome. Superpositions aren't destroyed - you are subsumed within them.
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! :)
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.
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.
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.
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.
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.
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.
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.
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?
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?"
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.
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.
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?)
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.
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]"
> 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.
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.
And the diagram did get the terminology right. The author may need a (better) proofreader, but it wasn't impossible to see what the author meant. They only conflated the names, not the concepts.
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)?
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).
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.
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.
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.