If you take really seriously the idea, not only that computing is a physical process, but also that any physical process can be considered as some kind of computation - and thus by extension, the rules of computations are the rules of physical law, then there is indeed a lot of wish from quantum mechanics as it stands, but part of this "problem" is indeede shared with classical mechanics and even probability theory if you look at stochastic models.
My personal "interpretation" of QM, that of course hides a large ambition, is that any physical process can be understood as a "physical inference process", and that happens to quite be related to computation ideas, and i am partly symphatetic to the the idea of using a CTD idea as a guiding principles to finding physical law.
Anyway, if you TRY to understand quantum mechanics as it stands today - in these terms - there are several obstables that needs to be solved to make progress.
1) Uncountable numbers.
Most physics is based on calculus and real numbers. So is probability theory. You can surely do inference, in contiuum terms, but it makes the algorithmic descriptions more difficult as you have to first go through the problem of finding the countable structures WITHIN the continuum models that correspond to the physical inferences. This is most probably possible, but is of little help for a physicists, but probably very fun for mathematicians.
2) Coding of the "computational rules"
Quantum mechanics is still constructed via a still not (conceptually) understood quantization procedure, also using the classical placeholders for physics: lagrangians or hamiltonians with extra constraints. Their content is basically put in by hand, rather than be a principal inference from interaction history.
I would say these two things are major issues, that might be a possible meaning of QM not beeing a complete theory from the point of view of computation. But indeed this is shared by classical mechanics.
A possible route to a solution i see is
1) Starting from distinguishable states and limited memory, physics at the microlevel is discrete computation, and continuum physics is emergent at large complexity limit.
2) the computational rules are selected by evolution of law, in the sense of beeing selected for the algoritms of "best computability" given the memory constraints (here i think we can benefit from a discrete correspondences to Ads/CFT which is a dualit of theories with different computation complexity). I think there are interesting links to that here. Computational complexity is proabalby the more interesting part of these dualities.
Once can idenfity constraints here that can be traced to requirements of "inferrability" which in this case is closely related to "computability".
/Fredrik