Take the 2-minute tour ×
Physics Stack Exchange is a question and answer site for active researchers, academics and students of physics. It's 100% free, no registration required.

I just read this article at https://medium.com/the-physics-arxiv-blog/7ef5eea6fd7a about the work of a physicist called Bolotin, that states that P!=NP (from computer science) implies that large quantum mechanical objects are not possible.

The author starts by explaining the Schrodingers cat thought experiment. He then says "Nobody knows why we don’t observe these kinds of strange superpositions in the macroscopic world", which I find strange because you cannot observe a superposition, you either see that the cat is alive or dead.

But then he writes "For some reason, quantum mechanics just doesn’t work on that scale. And therein lies the mystery, one of the greatest in science." I thought that the correspondence principle actually explains nicely why quantum mechanics works very well on a large scale?

The main point of the article is that if you can have a large quantum mechanical system, you would get P=NP, which is believed to be not true by most computer scientists. But isn't that exactly what they try to do with quantum computers?

share|improve this question
i think the guy you quote is confused/misleading about QM. his mysteries and questions have been expressed many times over the last 80 years or so, and, while the dust hasn't entirely settled, have generally been explained. –  innisfree Apr 5 at 11:26
There are theoretical computer scientists that think "every physical process is efficiently computable", related to the original Church-Turing thesis. A quantum computer running Shor's algorithim would be evidence against that, so they are trying to show useful QC's can't be built. –  baldrik Apr 5 at 11:56
@innisfree, I already suspected that, thanks for confirming. –  user1817949 Apr 5 at 15:31
@baldrik thanks for the insight. –  user1817949 Apr 5 at 15:32
You may try to email him a link to this question, and see whether he wants to answer it –  hwlau Apr 5 at 17:14

1 Answer 1

up vote 5 down vote accepted

You are right and the author is wrong.

The problem of P=NP is a pure mathematical problem, which has nothing to do with physics. Even though quantum mechanics (or whatever physical system) can solve all problem in blink of eye, it still does not prove whether P=NP or not. The key point is that all computations are based on physics, but not the reverse. In computer complexity theory, they treat these (existing or imaginary) superpower machine as an Oracle machine, which can give an answer in a single computational step. This formulation allows them to analyze quantum computer.

The claim of non-observable macroscopic quantum effects because of P!=NP is based on the following argument: To prove macroscopic quantum effects, we need to compare the physical system with the simulation results of Schrodinger equation. So, if we can't simulate Schrodinger equation efficiently, then we can't prove any quantum effect. As shown in the paper:

This implies that in the case, in which the problem $\Phi_\Psi$ would be intractable, the deterministic quantum model of a macroscopic system (built around the exact solutions to the system Schrodinger equation) would be without predictive content inasmuch as there would be no practical means to extract the prediction about the system future state from the Schrodinger equation. In this manner, a Schrodinger cat state – as a linear combination of the exact (and orthogonalized) solutions to the system Schrodinger equation – would be predictively contentless and for this reason unavailable for inspection.

The author clearly does not familiarize with quantum mechanics, nor the Schrodinger equation. Schrodinger equation is only a part of QM. He also doesn't understand the particle concept in the Schrodinger equation. A particle is not an atom. This is a basic concept that most physics student should have understand after half dozen courses in QM. The interference of one C$_{60}$ molecule can be described by one particle wavefunction $\Psi(x)$. There is no need to solve a 60-particles wavefunction $\Psi(x_1,...,x_{60})$, which is already extreme hard to solve by current computers.

If a Schrodinger cat state exists, you can always perform a bell-state type measurement, even at the macroscopic level. There is no need to solve Schrodinger equation with large number of variables in wavefunction $\psi(x_1,...,x_{10^{23}})$ to know the result, since the system should be effectively described by a two state system.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.