mathematical physics - What do theoretical physicists need from computer scientists?

I recently co-authored a paper (not online yet unfortunately) with some chemists that essentially provided answers to the question, "What do chemists need from computer scientists?" This included the solution of theoretical problems, like combinatorial enumeration and the sampling of certain classes of graphs; and practical programming problems, like open-source implementations of algorithms that are currently only implemented in expensive software packages.

This motivates me to ask: what about this field? Are there theoretical issues of combinatorics, algorithm analysis, that physics needs a theoretical computer scientist to solve? Or how about creation of practical tools that would allow a theoretical physicist to do a better job: "If only I had a program that would solve this type of problem for me!"

Intended as community wiki.

Answer

I think perhaps some of the other answers are taking computer science to be synonymous with computation. I guess that this is perhaps not what you mean, but rather theoretical computer science. There is obviously a huge overlap with quantum information processing of which I think you are already well aware, so I will ignore that.

Much of physics (including quantum physics) is continuous, so the type of mathematics used in tends more towards continuous maths (solving PDEs, finding geodesics, etc.) as compared to the discrete structures studied in theoretical computer science. As such, there isn't so much of an overlap. Statistical mechanics tends to be more concerned with discrete structures, so there is more of an overlap there.

One huge area of overlap is actually in terms of computational physics, where people are concerned with computing certain properties of physical systems. In particular, simulating physical systems is a huge area of research, and there is a lot of focus on finding efficient algorithms for simulation of physical systems. In particular, finding quantum ground states and simulating quantum dynamics are the ones I have most direct experience of. There has been quite a lot of progress both in terms of proving hardness results (for example Scott Aarosnson's recent paper on the hardness of simulating linear optics, the QMA-completeness of finding quantum ground states even of quite restricted systems, simulating commuting operators etc.) as well as efficient algorithms (for example match gates, or the Gottesman-Knill theorem).