Until you hit all the quantum weirdness and then it’s all wave functions and probabilities. That maybe comes out of something simple as well.
"Going down" simply means identifying laws that are more universal in that they can underly models of different systems, ideally "any known system". Quantum weirdness isn't significantly harder mathematically than what came before (we don't have an objective measure of how "hard" some piece of math is), it's just harder to relate to everyday experience. It's similar to how we got used to "masses attract each other" or "things just keep moving in a straight line", which seemed ridiculous to most of Newton's contemporaries.
We absolutely have a way to measure how hard a piece of math is: computational complexity. And quantum mecanichs is more computationally complex than newtonian mechanics (while general relativity is significantly harder still than both of them).
Is there a formal version of this claim somewhere? (Beyond theorems about quantum computers)
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).
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.