Discrete particles vs. continuous wave functions is a red herring, I think. It's true that in a simulation of QM one would have to approximate amplitudes up to some finite precision (and approximate infinite dimensional Hilbert spaces using finite dimensional Hilbert spaces). But this is not a problem that is unique to QM. Simulating classical mechanics also requires approximating the positions and momenta of particles to finite precision.

You are right, though, that computing quantum mechanics is harder than computing classical mechanics. This is true even if we completely discretize both theories. The length of a vector representing the state of a classical system is linear in the size of the system, but the length of a vector representing the state of a quantum system is exponential in the size of the system.

Continuous wave functions seems to be far harder than discrete particles.

True, but consider that discrete particles are a special case of continuous wave functions: The case where the phase-space distribution is a delta function or some very good approximation to it. If you limit your quantum mechanics to cases that classical mechanics can describe well, then you are operating, in effect, on delta functions, and this simplifies the math immensely.

The apparent simplicity of classical mechanics comes from looking only at these special cases; quantum mechanics deals with more general situations, so it is unavoidably more complex. But if you made a quantum-mechanics program to predict only classical situations, it would not necessarily be more complex than the corresponding program using the laws of Newton, who is not forgotten.

I presume that you refer to the difference between point particles and fields. The wave function in QM is essentially a classical field), where for every point in space you have a set of numbers describing the quantum state. This state evolved in time according to the time-dependent Schrodinger equation, until "something classical" happens, at which point you have to throw dice to pick one of the preferred states (also known as the wave-function collapse or the MWI world split).

The part of QM which is just the evolution of the Schrodinger equation is computationally equivalent to that of modeling diffusion or heat flow: the equation structure is very similar, with complex numbers instead of reals. The "measurement" part (calculating an outcome) is nearly trivial, just pick one of the outcomes (or one of the worlds, if you are a fan of MWI), according to the Born rule.

While it is true that there are many shortcuts to solving the Schrodinger equation numerically, and a set of these shortcuts is what tends to be studied in most QM courses, there is no substitution for numerical evolution in a general case.

Quantum computing is a rather different beast from the regular quantum physics, just like classical computing is different from classical physics: computing is an abstraction level on top, it lets you think only about the parts of the problem that are relevant, and not worry about the underlying details. Quantum computing is no more about quantum mechanics than the classical computer science is about the physics of silicon gates.

One final piont. It is a general observation that understanding of any scientific topic is greatly enhanced by teaching it, and teaching it to an ultimate idiot savant, a computer, is bound to probe your understanding of the topic extensively. So, if you want to learn QM, get your hands dirty with one of the computational projects like this one, and if you want to learn quantum computing, write a simulation of the Schor's algorithm or something similar.

There are a variety of ways of measuring how complex something is. Three of them seem relevant here. The first is, given a sequence a_i of integers, what is the smallest classical Turing machine which on input i outputs a_i. This is really tough in general, and quickly leads to unsolvability issues. In general, the simpler question "what is the smallest Turing machine which outputs string S" is called the Kolmogorov complexity of S and is essentially undecidable in the general case. One can look at empirical Kolmogorov complexity and ask the same question about smallest known. This turns out to be not that useful as I understand it.

More effective methods look not at the Turing machine's size but how much tape space or how much time it takes up. You may have heard of this sort of thing in the context of P?= NP. In this context, the set of function problems which can be performed by a quantum computer reliably in polynomial time is BQP. We do have specific problems that seem to be in BQP that cannot be performed in reasonable time on a classical computer in polynomial time. Although this has not been formally proven, recent work by Scott Aaaronson leads one to suspect the stronger statement that BQP includes problems which are outside what is called the polynomial hierarchy, which is a much broader computational framework. If this is the case, then quantum computing must be very hard.

Note that when talking about BQP one is getting essentially a single bit of information out, so it can always be performed with finite resources (in fact in PSPACE and thus bounded by exponential time). If one wants to predict more behavior of the system then you need do need a lot more resources and it seemed potentially infinite resources to fully predict basic behavior.

Classical physics isn't exactly computable, because some systems are critically dependent on their initial conditions, and an exact specification of the initial conditions requires an infinite amount of information (unlimited precision real number).

It all depends on your system. If you're computing the fully quantum system of a spin glass on a regular grid using an Ising Hamiltonian or something like that, it can be computed far more straightforwardly than most fully classical systems of a similar number of particles.

It also depends on the approximations you're making. You mention the ideal gas law, but that doesn't apply to gases sufficiently far from thermal equilibrium, or even mechanical equilibrium. If you pop a balloon in outer space, the gases will self-sort by momentum, and thus cool faster than the ideal gas law over their volume would suggest.

So, each time we learn new physics that isn't clever approximation, new effects are being added. They will necessarily add computational complexity, unless they allow new, different approximations to be made which more than make up for that new complexity.