A Link Between the P≠NP Problem and the Quantum Nature of Universe

1. Technical nitpick: NP-Hard problems are not 'mathematically equivalent'. I assume the author means to refer to NP-Complete problems here. NP-Hard is a larger complexity class that may include things that are harder than NP and not equivalent at all to the set of NP-Complete problems.

2. The existence of a physical NP-Complete oracle does not imply that P = NP with respect to classical computing. If tomorrow we discover a physical process that solves travelling salesman in linear time, that does not necessarily mean that P = NP, it simply means we now have a physical oracle for solving the problem.

This is the same as with traditional quantum computing. We didn't fold BQP into P when we discovered quantum computing.

First comment by Dunnorandom

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

That we don't observe quantum superposition in the macro-world may have more to do with our senses (or our instruments, both physical and theoretical) than whether it is there or not.

That we can't imagine a computer that can brute-force macroscopic quantum superposition is more a flaw of the imagination. We could imagine a non-brute force solution after all. The problem is we can't imagine it clearly enough to know its details, and actually implement it. Nothing makes the imaginary 10^(-3x10^23) sec per op' computer necessary except for an argument based on it.

Finally: obviously the quantum state of macroscopic objects is being "computed", by themselves as they go about existing. With a bit more of a stretch of the imagination people have suggested the whole universe is a simulation. If that is true, maybe the universe itself doesn't have the resources for a computer that can calculate the quantum superposition of macroscopic objects, but something can, except it's outside the universe and we'll never know it.

I'm not even sure why the universe would have limits on computation. To put it bluntly: the mere existence of the universe/reality is magical, not sure why magic would have any limits in computation power (not saying there isn't any).

Are there other complexity classes that were shown to be non existent in deterministic machines?

A system is quantum if its state has not yet reached consensus. A system is non-quantum if consensus on it has been reached.

Secondly, as noted in several others' comments, there are many problems with the article's basis, namely Bolotin's arXiv preprint, also from 2014.

Thirdly, the medium author originated this sentence (it isn't from Bolotin): "What of the collapse of stars, which are definitely classical objects, into black holes, which may be quantum ones?", which is wholly backwards.

Stars are definitely quantum objects; black holes may be classical ones (at least in contrived circumstances).

When you zoom in closer and closer when examining a star you see more and more evidence of quantum mechanical processes. Even at long distances, the presence and evolution of spectral lines and neutrinos give away QM processes within the star.

Compact massive objects that are extremely unlikely to be black holes give even more evidence of QM processes and behaviours that do not arise in classical mechanics.

Black holes probably have some quantum mechanical process inside preventing the existence of a physical singularity and retaining some imprint of at least the matter that was near the centre of mass at the time of the formation of the event horizon. That is the subject of a great deal of current research.

On the other hand, there is the no-hair conjecture. Under that, we can model a spherically symmetric, stationary, isolated black hole -- this is plausibly approximated in our universe in the extremely distant future from black holes that have been ejected from a galactic cluster and now inhabits its own essentially unshared Hubble volume. "Stationary" here means that it does not move against a reasonable choice of coordinates (e.g., it stays at X=0,Y=0,Z=0 as one varies T under Cartesian 3+1 coordinates on an extended patch of the Hubble volume the black hole occupies).

If no-hair is accurate, the only observables accessible at a reasonable distance outside the horizon of such an idealized (and again, plausibly physical) black hole are reduced to angular momentum (3 components), electric charge, and mass-energy. That's as classical as you can get.

Under a hard interpretation of no hair, there remains other fundamental observables even in the dynamical spacetime just outside the event horizon, and even through the event horizon. It is possible that nature doesn't care for our ideas of unitary evolution or concerns about physical infinitesimals and infinities with respect to lengths and densities, and black holes can be wholly classical all the way down.

Since such black holes may exist, black holes may be classical objects.

Such objects do not reveal what was inside the black hole at the time of its formation. Suppose a critical mass star is about ready to undergo gravitational collapse and we throw in a particle of energy E, which reaches the centre-of-mass just as the horizon forms, or we throw in two particles stacked on top of each other that have energy 1/2 E each that reach the CoM just as the horizon forms. Under no-hair, we cannot even in principle distinguish the resulting black holes from outside the horizon, even in the infinite future. (But if we throw such things into a normal star, or even a neutron star, and if we had sufficient spectrometer resources, then we could tell the difference between the two cases).

There are lots of reasons to think black holes aren't fully classical. No hair black holes might not ever arise (e.g., Hawking, Perry and Strominger 2016 argue that idealized black holes have "soft hair" that are extremely long wavelength photons generated in the spacetime very near the horizon and detertmined by the matter inside the horizon at the time it formed; other hair might exist too (e.g. EPR=ER from Susskind & Maldacena 2013); final black hole evaporation might reveal the difference between the two-particle and one-particle picture in the paragraph above; and many other solutions have been suggested over the past forty-three years since the publication of Misner, Thorne & Wheeler's Gravitation.