My last post on Church-Turing Noise aroused some reaction. In order to clarify further my uncomplimentary remarks about complexity theorists let me elaborate (a little).
I can see I will need to write a longer paper on this, but first let me tell a simple story.
Firstly, here is a PDF of the paper describing how quantum dynamics is a special case of classical dynamics: The Schroedinger equation from three postulates.
To put this in context, it was my (successful) attempt to re-axiomatize the non-relativistic quantum dynamics in a form suitable for considering non-linear generalizations. Very few physicists and, so far as I know, zero complexity theorists know of this result.
This is why it is extremely popular to preface each new quantum computing article with a statement of what quantum computers can do which classical computers cannot. The linked article above demonstrates that this language is too imprecise.
Using the above mathematical result it is obvious that any quantum computer (non-relativistic) can be simulated by a classical computer.
However, since it is also trivially obvious that the said quantum computer has an integrable dynamics, any non-integrable system cannot be simulated by the quantum computer. This is what I mean when I say classical computers can do things quantum computers cannot.
It would seem that the people in complexity theory simply do not know this.
They have assumed (wrongly) that because quantum dynamics contains non-commuting operators, and Hilbert spaces, and complex numbers, and many other neat things that it cannot possibly be less general than classical dynamics.
Well, they are wrong.
How come nobody seems to know this?
I think there is a simple reason.
Physicists have taught themselves day-in and day-out that the quantum theory is new and special and different and just so much better!
Well, yes, it is. The predictions differ and the scope is larger. I do not dispute that.
However, what they do not appreciate is that the underlying mathematical scheme is less general. This is where the complexity theory zoo gets interesting.
Guess what?
Not only does classical dynamics (in the abstract form above) fully contain quantum dynamics but a particular version of generalized quantum dynamics (an infinite-dimensional non-linear variety) fully contains classical dynamics!
Presently we have a bunch of complexity theorists delighting each-other with new theorems about how useless classical computers are.
What they have failed to comprehend is that mathematics (and Nature) are stranger still.
When you do the complexity theory properly then there is an infinite regress of one system containing another.
Linear QM is contained with CM in finite-dimensional form.
However CM is fully contained within Non-linear QM in infinite-dimensional form.
That means you can embed Linear QM within CM inside Non-linear QM.
(inside… ad-infinitum).
How about that for a cute trick?
Confused? You should be.
Conclusion: Complexity theorists do not know diddly squat about this topic.
So, where do I stand on this?
I developed the new axioms because I believe Nature follows a Non-linear dynamics.
If that is true, then an actual real physical computer in the REAL WORLD could do things that the complexity class studied right now (linear quantum computers) could not do. One of those things is to faithfully simulate dynamical chaos.
Over to all those super-smart complexity theorists to make their butterfly collection.
As part of that, the people involved will need to stop conflating two concepts.
The speed of execution is different from the scope of execution.
These are, I think, two different concepts.
One speaks to the physical and the other to the mathematical.
I suspect this is the ultimate reason for the above disagreement.