[Ono-Sendai]

Well, I would say QM is an approximation of some better and more accurate theory. In my view, multi-particle quantum mechanics is pretty clearly a kind of gross hack - using a very large dimensional space so you can write down a linear theory - instead of using a smaller dimensional space with non-linear interactions. Quantum computing assumes the very large dimensional space is actually real. So we'll see if that is the case.

[Viliam1234]

How would you explain the fact that the experiments with current quantum computers support the theory?

[tsimionescu]

Well, the status of the experiments is unclear - since the Google paper was published, the state of the art in classical spoofing of the same result has improved by about 10,000 times, and the results obtained by Google in 300s have been obtained by a classical computer in 1s or so. Note that the classical computer was much much larger, so there is still a huge difference in number of operations executed that still gives a notion of quantum supremacy. It is harder though to be sure now that the result will stand compared to when it was first announced.

It should also be noted that there is no prood right that any of the known quantum algorithms give an exponential speedup over the best possible classical algorithms. In particular, integer factoring (that Shor's algorithm solves) is believed by many to have a yet undiscovered polynomial-time classical algorithm.

Separately, it should be remembered that quantum mechanics has large difficulties when applied on classical scales in reproducing classical observations. This is an inherent problem, since QM is an almost linear theory, while there are many extremely well confirmed non-linear processes in classical and relativistic physics. The only possible source of that nonlinearity from QM is also the least well understood aspect of the theory - Born rule (measurement postulate, wave function collapse).

For example, if you try to use QM to describe the motion of a double-pendulum, you will get a completely wrong result, even if applying the Born rule at the end to get a single definite result with some probability. You instead have to add multiple intermediate applications of the Born rule to get the non-linear behavior that is observed in practice.

[bawolff]

> It should also be noted that there is no prood right that any of the known quantum algorithms give an exponential speedup over the best possible classical algorithms.

True, but we also can't even prove P!=NP, which seems (intuitively) like it should be much easier than proving that there exists an exponential speedup with quantum algorithms. I feel like this statement mostly just says we have a far way to go in understanding the relations between complexity classes. Its not like we have proven all the "obvious" separations between complexity classes and qunatum stuff is just a stubborn hold out.

[tsimionescu]

Oh, absolutely, I didn't mean to imply that this should be easy. It's just important to note in these discussions what we do know for sure and what is still debatable.

My point was that one way of accounting for a belief that QCs are not fundamentally exponentially faster than classical computers despite the experiments we've seen from Google is to believe that we will find classical equivalents of every quantum algorithm that shows such a speedup. While few believe this in the community, and for good reasons, it is not proven to be a silly belief yet.

By the way, I will also mention that if P=NP (not that anyone thinks this is remotely likely), that would also imply that quantum computers have no exponential advantage over classical ones.