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.


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).

  • $\begingroup$ The mainstream models are discrete but there are other models that deal with continuous. A good old example is here. Also there is an interesting interaction on questions related to random k-SAT. $\endgroup$ – Kaveh Sep 20 '11 at 15:54
  • 1
    $\begingroup$ @Kaveh: Yes, I know. I simply meant at a high level the mathematics tends to be different. $\endgroup$ – Joe Fitzsimons Sep 20 '11 at 16:19
  • $\begingroup$ While I certainly like this answer, I don't find any indication in the question that Aaron is intending for it to be mostly directed towards the area of theoretical computer science; he even asks about "creation of practical tools". Of course the questioner is a theoretical computer scientist, but from what I can tell the question is equally about all branches of computer science. $\endgroup$ – Logan M Sep 21 '11 at 5:23
  • $\begingroup$ @Logan: He specifically says "Are there theoretical issues of combinatorics, algorithm analysis, that physics needs a theoretical computer scientist to solve?" $\endgroup$ – Joe Fitzsimons Sep 21 '11 at 5:33
  • $\begingroup$ @Joe: Yes, but in the very next sentence he asks about practical problems, which was to me an indication that he was looking for answers from both the theoretical and applied points of view. Also, to clarify, I was not taking computation and computer science as synonymous, but I do have to admit I don't know much about what theoretical computer science consists of beyond, say, Hopcroft & Ullman. The theoretical computer scientists here do research in things like biological computing, which is, as far as I can tell, not what most people mean when they talk about theoretical computer science. $\endgroup$ – Logan M Sep 21 '11 at 5:39

EDIT: This answer is specifically from the perspective of very computationally oriented fields like theoretical plasma physics.

Most physicists can program, and in fact many are rather good programmers. It would be difficult to work in modern physics without being able to program. Unfortunately, many are also not terribly good programmers (I've read many a fortran code where goto was the primary method of flow control).

Having faster algorithms is always desirable, and hence algorithm analysis is useful. However, in many cases, the algorithm speed is not the limiting factor, so it isn't as useful as one might hope. More on that later.

One thing that I did in high school at a lab was essentially develop GUIs for existing programs. In theoretical plasma physics, there are a large number of codes that one runs to get some idea of what is going on in the reactor. Developing a GUI for this isn't as trivial as you might think; integrating parameter input, data visualisation, and connecting the codes in a nice way actually requires some knowledge of what's going on physically. This is more directed toward programmers than computer scientists, but it should still be useful.

Another area in which computational physics will need to go is in the direction of data-driven theories. Computer scientists know this better as machine learning. I'll just give you an example of a project I did, again in plasma physics. When calculating the turbulent transport for stellarators, the gold standard are so-called gyrokinetic simulations. These can go for 100 million CPU hours or more and generate huge amounts of data. My advisor (I was an intern at the time) suggested we explore the output of the files with neural networks. The idea was to train a neural network using as many gyrokinetic simulations as possible, and then see what it could do. We expected it probably wouldn't be able to do much of anything.

All the existing neural network packages, both commercial and free, were not sufficient for what we needed. There are built-in symmetries and approximate symmetries to the system, which are often non-obvious. Translating this into a way for a neural network to work wasn't easy. I ended up writing the code entirely myself, just slapping in as much of the physics as I could. It worked surprisingly well, and both my advisor and I thought this would be a very interesting direction in the future. Unfortunately, going beyond that was beyond my programming ability, and would probably require an expert in neural networks who knew a lot of plasma physics.

I don't expect one could manufacture a neural network code that would be useful to a broad area of disciplines. If there were a way to build symmetries into the code that the network would have to follow, that would be extremely useful for data-driven theory. I'd guess though that each one would probably have to be manufactured individually. This is an area in which theoretical (computational) physicists and computer scientists can and should probably collaborate on more. Neural networks obviously aren't the only thing either; I'd imagine that in fields like computational plasma physics, data driven theory would see a huge boom if we could use machine-learning with some of the physics built in.

I should probably add that what I was attempting to do was not, strictly speaking, data-driven theory, but rather simulation-driven theory. True data-driven theory would use experimental data, but this is by far the costlier option (given that each configuration corresponds to building a 1 billion USD+ stellarator). It was essentially a proof-of-concept project.

As for algorithm speed, in the case of plasma physics the limiting factor isn't necessarily being able to do the simulations. Even the most costly simulations we're interested in can be done reasonably on supercomputers today. So-called "full" simulations would require some $10^{30}$ more computation, which is unlikely to ever be feasible. The region inbetween has so-far proven to be rather chaotic, and it doesn't seem that the answers improve a huge amount by just randomly throwing more gridpoints at the problem. We need to first understand what is happening on the small scales, and then we can apply this. There are a number of techniques to do such computations, such as the aforementioned gyrokinetic simulations, but these are essentially just our best guess and only approximately match with experiment.

In a stellarator, the turbulent transport depends critically on the geometry of the reactor geometry, and as such there is essentially an infinite-dimensional parameter space to explore. At least to study this parameter space perturbatively, the best direction seems to be hybridized data/simulation driven theory development using machine learning. Having faster codes would help, but it isn't clear that they'd get us fundamentally to the right physics; rather, the problem seems to be that we're not sure how to develop such algorithms to get what we want from them. Admittedly, this was several years ago, and I've not kept up with the literature, and there were only a few people pursuing this direction, so I don't know if it's still open.

  • $\begingroup$ Alright, I must admit that this doesn't exactly fit your comment on Michael's post, but I think it's a start. $\endgroup$ – Logan M Sep 20 '11 at 15:00
  • 2
    $\begingroup$ I think you can generalize your answer to machine learning ideas and not just neural networks. $\endgroup$ – Kaveh_kh Sep 20 '11 at 15:16
  • $\begingroup$ Since I've retracted my post, just to clearify what Logan Maingi meant by "comment on Michael's post": I posted an example with a very general need for computer science, but the question is for an explicit Problem/Example in TP that requires CS $\endgroup$ – Michael Sep 20 '11 at 16:54
  • $\begingroup$ I mentioned machine learning in a broader context, see for instance the last sentence. I can't claim to be knowledgeable of anything in the field except a little bit on neural networks, which is why the answer almost exclusively discusses them. I would agree that there is much beyond neural networks to be gained, but I don't know quite what it is. $\endgroup$ – Logan M Sep 20 '11 at 17:32
  • 6
    $\begingroup$ I have to disagree. It is exactly the algorithms that run on supercomputers that you need to speed up. (I'm not saying that theoretical computer scientists can help, but saying "we can always just run things on faster computers" is definitely the wrong attitude.) At some point, I saw an analysis of the speed-up in solving linear programs over a period of some decades. There was a factor of a several million that came from faster machines. There was a significantly larger factor that came from improvement of algorithms. And people would still like to solve linear programs faster. $\endgroup$ – Peter Shor Sep 21 '11 at 4:05

Disclaimer: I am not very familiar with the numerical analysis literature, so it is quite possible that the problems I will mention are already solved.

Perhaps this is a more banal suggestion, but I think that better software for doing numerical differential (and in some cases, algebraic) geometry would be amazing. This probably seems 'obvious' and to many people, this might be already be a solved CS problem, but I'd rather illustrate this issue with an example.

I once had to consider some 10-dimensional metric $ds_{10} = ds_{S^5} + ds_{M}$ and solve an simplified eigenvalue problem: What is the lowest eigenvalue of the Laplace-Beltrami operator associated to $ds_{10}$. The physical relevance of the problem turned out to be that we could use a dipole-like approximation that only depends on the lowest non-zero eigenvalue. After spending a few weeks on analytically trying to find this eigenvalue, I decided to try to do this numerically. My advisor had convinced me that the numerical tools to do this would be out there and that it should be a straightforward problem. Unfortunately, three months later, I realized that there were few open source/commerical programs that could do this task and moreover, there were few algorithms developed to approximate slightly higher dimensional (non-linear) PDEs. I do believe that the numerical methods do exist (I've spoken to a few numerical analysts at Courant who said they believed that this problem was solved, but stopped short of providing me with references to algorithms).

I think that while theoretical physicists are often times trained to solve for things only analytically, it would be nice to gain some intuition from the numerical solutions. Moreover, there are a lot of algorithms from mathematicians like Robert Ghrist for computing important invariants like Morse Homology and I think it would be great if we could find the right balance between computer science and physics in order to implement such techniques. I have some background in CS and with parallel programming and I still feel that the two sides (CS, theoretical physics) are so disconnected that it is hard for such solutions to be implemented.

  • $\begingroup$ Thanks very much. This is exactly the kind of thing I was looking for. $\endgroup$ – Aaron Sterling Oct 14 '11 at 1:31

My old advisor, a physicist working in cs, wrote a paper showing that spacetimes are categorically equivalent to interval domains. His name is Panangaden. Domains are useful in cs as a semantics for programming languages. In causal approaches to quantum gravity (which I take as a general place to have unique forms of novel, relevant physics) time looks way more like logical clocks, which we see in the analysis of distributed and concurrent computer system analysis. Some aspects of cs are useful for the newest stuff being done in physics like the categorical quantum mechanics.

  • 1
    $\begingroup$ Prakash is something of a special case, as he has a significant background in physics. $\endgroup$ – Joe Fitzsimons Oct 10 '11 at 8:00

Mathematics is to physics what masturbation is to sex - Richard Feynman. This means physics are about real-world interactions versus plain abstract concepts. The same can be said of science versus engineering: science develops abstract tools that engineers use to represent real-world computation models.

Computer science is not a science but an engineering discipline. It's not even about computers; it's about modelling computations. The computer is the medium binding thoughts to physics in the form of programs.

The most obvious skill a physicist would benefit from computer science is the knowledge of algorithms and data structures. Algorithms are general descriptions of how to carry on a specific task. Those tasks can be accomplished using many algorithms. It's all a matter of solving the task the most concise, simple and efficient way. Knowledge of algorithms helps select the right algorithm for the right data structure. Data structures are ways of storing data. Examples include lists, arrays, numbers, strings, vectors, matrices, even functions (if the language used allows functions to be used as data to be passed around). Category theory is about math, physics, data types etc. It's all linked together. I suggest physicists learn Haskell to make the link themselves.

In sum, being better at solving real-word problems is what skill computer science has to give. Programming will make any scientist solve problems at the speed of an electron while making it easier to review thoughts and models.

Programming is hands-on so what are you waiting for? Get your fingers running!

  • 6
    $\begingroup$ I've downvoted this because I consider it unhelpful, and not a real answer. $\endgroup$ – Aaron Sterling Jan 20 '12 at 20:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy