[staunton]

Computational complexity is defined for programs with respect to a parameter in the limit where that parameter is large. What's the objectively correct parameter for this comparison that every theory of physics has, after you convert it to a program in the objectively correct way, which you supposedly have?

[tsimionescu]

The purpose of a physical theory is ultimately to derive a prediction of how a physical system will evolve after some time, within a given precision of measurement. The prediction can then be compared to a real measurement of the real system (or several, in the case of statistical predictions).

So, we can represent a physical theory as some algorithm A(init_condition, time, precision) = final_condition. Let's call the Newtonian model N and the quantum mechanical model QM.

My claim (which I think is completely uncontroversial) is that for the same init_condition, time, precision, you will need more computational steps to arrive at the same final_condition using QM than using N. This is the very definition of computational complexity.

If you want instead to compute the asymptotic complexity, we can take either time, precision, or some combination of the two, to be the parameter in respect to witch we compute complexity as a function.

Overall, this fact is quite uncontroversial since it is widely assumed that a classical computer requires an exponential amount of time to simulate a quantum computer running the same algorithm, for some algorithms such as Shor's. This is of course not yet proven, but it is widely considered very likely to be true. In fact, if it turns out to be false, it is quite likely that it will also turn out quantum mechanics is in fact reducible to classical mechanics (since the difference in computational speed is due to the special features of quantum mechanics as compared to classical, particularly the complex probability values that it arrives at).

[staunton]

There is usually no obvious way to convert the initial condition of an arbitrary quantum system to that for a classical system. The other way around, there is some consensus what the quantization of standard classical systems should be, but to define this transition in general is, again, not straightforward. Also, you obviously don't arrive at the same final condition for two different theories, otherwise they would be equivalent.

To talk about "number of computational steps" (which I have never seen referred to as "definition of computational complexity") you need to specify a computational model. The number and the comparison between two programs will depend upon it and you can get whatever result you want by choice of the model.

The conversion of theory -> model -> program is also not at all straightforward. The complexity strongly depends on the conversion. If you specify "best possible conversion" for model to program (which is probably the easiest part of the huge amount of things you need to define), you cannot prove anything about it anymore.

The complexity difference between asymptotic classical and quantum calculations is usually determined by its scaling in the "size of state space". Why do you focus on time and precision? I don't know for sure but it seems reasonable to me that the complexity with respect to those two might actually be the same for common system models. Regardless, you have to choose some parameters and you provided no arguments that this choice is in any way objective.

> In fact, if it turns out to be false, it is quite likely that it will also turn out quantum mechanics is in fact reducible to classical mechanics

Strongly disagree for any reasonable notion of "reducible". Quantum theory is different from classical in many qualitative and experimentally accessible ways (e.g. Bell inequalities). Computational complexity isn't everything.

To end, I want to further contest your defining complexity of a theory according to "length of computation to get model prediction". An interesting alternative would be "length of theory specification under optimal compression " (i.e., "Kolmogorov complexity of a theory"). This notion obviously also isn't rigorously defined yet but I think it's about as hard to definine as your notion. Neither of them seems obviously the "right one" to me in this context.