Is limited computational capacity a fundamental obstacle?

Question

Statistical physics books often motivate the necessity of statistical/thermodynamic description by impossibility of calculating the trajectories of all the molecules (I speak of "trajectories" but the discussion applies to the quantum case with the obvious adjustments). The bases of the statistical physics were laid about a hundred years ago, when the limited computation abilities seemed indeed to be an insurmountable obstacle. The situation has however changed since then and it is not uncommon to suggest that we could in principle attain enough computational power to predict behavior of any system of interest (with the corollary that such ab initio calculation would render redundant the empirical laws of chemistry, biology, economics, psychology, as was debated in the comments that followed the question on whether physics explains biology.)

One could oppose this view by noting that, at a certain scale, the computer itself, being the part of the Universe, would interfere with such a calculation. This might be compounded by the possible non-linearities, which can result in small fluctuations producing wildly different results. Moreover, we are not free to choose the initial state of our computation, given the trajectory taken by the Universe from the Big Bang till now.

In a sense this limitation is similar to those that gave rise to relativity and quantum mechanics: the observer (the computer in this case) influences the outcome of measurement (computation).

The question, to which I would like to obtain a factual answer is:
Is the above described computational capacity limitation fundamental, or not, or it is impossible to say?

Update
A related question: more specifically focused on molecular physics rather than the general problem of computability.

Update 2
Just in case the comments are removed for some reason, I would like to put here the valuable references given by @ChiralAnomaly:

• S. Aaronson, NP-complete problems and physicsl reality
• S. Aaronson, Limits on efficient computation in physical world
• L. Susskind, Computational complexity and black hole horizons

Update 3
To restate the question differently:
Can we model complex (e.g., biological or social) systems without resorting to intermediate concepts ("emergent properties"), directly in terms of basic physical equations.
(This formulation suggests an answer along the lines of the information loss when replacing detailed description by a higher level concept, and the inevitable noise resulting from such an approximate description, which makes explanations in terms of basic concepts meaningless.)

Update 4
Interesting relevant quote from Kondepudi & Prigogine's book Modern Thermodynamics:

The traditional answer to this question is to emphasize that the systems considered in thermodynamics are so complex (they contain a large number of interacting particles) that we are obliged to introduce approximations. The Second Law of thermodynamics would have its roots in these approximations! Some authors go so far as to state that entropy is only the expression of our ignorance! Here again the recent extension of thermodynamics to situations far from equilibrium is essential. Irreversible processes lead then to new space-time structures. They play therefore a basic constructive role. No life would be possible without irreversible processes (Chapter 19). It seems absurd to suggest that life would be the result of our approximations! We therefore cannot deny the reality of entropy, the very essence of an arrow of time in nature. We are the children of evolution and not its progenitors.

Update 5
In a metaphoric form the problem that we face here was famously described by Jorge Luis Borges in their short story On the Exactitude of Science (the full text is taken from here):

...In that Empire, the Art of Cartography attained such Perfection that the map of a single Province occupied the entirety of a City, and the map of the Empire, the entirety of a Province. In time, those Unconscionable Maps no longer satisfied, and the Cartographers Guilds struck a Map of the Empire whose size was that of the Empire, and which coincided point for point with it. The following Generations, who were not so fond of the Study of Cartography as their Forebears had been, saw that that vast Map was Useless, and not without some Pitilessness was it, that they delivered it up to the Inclemencies of Sun and Winters. In the Deserts of the West, still today, there are Tattered Ruins of that Map, inhabited by Animals and Beggars; in all the Land there is no other Relic of the Disciplines of Geography.
—Suarez Miranda,Viajes de varones prudentes, Libro IV,Cap. XLV, Lerida, 1658

Answer 1

So, let's start with the fundamental vagueness of the question. The reason behind this vagueness is the lack of clear unpacking of what is meant by "computation" or "prediction" or "modelling".

Let's suppose for a second that you actually do have an infinitely powerful computer that is able to simulate the dynamics of any number of fundamental particles. How would you use it to "model" or "predict" or "compute" the things that you want? You'd still have to use the high-level "emergent" concepts to set up the problem in terms of fundamental particles. Then you'd use the machine to predict the future state. Then you'd have to reinterpret this microstate back to the level of "emergent" concepts.

On top of that - you most likely would have an astronomical number of possible ways to set up the same high-level initial problem in terms of microstates. So you'd have to approach the whole thing statistically and your end results will be probabilistic over the high-level concepts.

My point is that it is not really the "computational capacity" that is fundamental here. The issue is with setting up initial conditions and interpreting the results. This focusing on "computational capacity" is based on the flawed assumption that we, humans, are "infinitely smart" to be able to interact with it.

Answer 2

There are several issues here. First there is a question about whether physics is deterministic enough that it can be computed even in principle. The second is how to motivate statistical mechanics.

The first one is somewhat outside the scope of this SE, although the question does show up here from time to time. One can argue that certain quantum events are logically independent of everything else and hence totally random, but then again a computer with the same kind of random number generator can generate indistinguishable dynamics (if not the same). Others lines of inquiry involve the computability of physics, whether there are limits on acquiring information about the world that prevent accurate simulations, whether chaos and other issues cause too rapid divergence. Lots of topics, but they are irrelevant to the core of the question.

One can motivate statistical mechanics as a way of circumventing our limited knowledge of the micro-states and micro-physics, making the simplifying assumption that "it all averages out". One can also note that the laws that emerge from this averaging appear nearly or completely independent of the microphysics if it has the right form. Indeed, historically people started with macroscale thermodynamics, tried to derive it from the kinetic energy of heat, and ended up with a theory that explains not just the macroscale thermodynamics (and deviations from it) but a lot of other things. In this work computational capacity was never really central, but issues of randomness and probability mattered a lot.

In modern statistical mechanics our computational abilities do not play a major role in the theory itself. It deals with how complicated microphysics statistically produces reliable phenomena; one can sometimes simulate microsystems to see this process happening, but this is no replacement for the overall theory.

However, statistical mechanics has a lot of important things to say about what and how we can compute, for example the famous Landauer's principle for the entropic cost of erasing information. Deep down many of these links emerge from quantum thermodynamics where the random microphysics and the physics of quantum information are combined. For example, the no-hiding theorem both explains conservation of quantum information and the Landauer principle.

So the answer to the second issue is that while simulating some of these phenomena is exciting and may help us understand them better, the theory we actually use to predict observable effects does not care about much of the microphysics. If we had magical computers that could calculate properties of interest from detailed microphysics we would likely use them to get data, but they do not give the qualitative understanding we usually aim for.

Answer 3

The question could easily introduce opinion-based answers. To avoid this danger, I'll try to stick to our present knowledge and understanding, avoiding any speculation on the future evolution of the field.

I think that two related assumptions are underlying this question and should be elicited.

The first is that computation always implies the possibility of predicting the behavior of a system. I think that this assumption strongly overlooks what computation is. The physical basis of any simulation is to establish a mapping between the steps of an algorithm and the states of a time-evolving physical system (the computer). Therefore, to have predictions, we need an algorithm sufficiently powerful and a physical system with enough states to describe the system of interest. The typical approach is to find a suitable set of basic building blocks such that a faithful algorithmic description of their behavior is possible. For example, we can start with atoms, interaction laws, and a few prescriptions for their dynamic behavior. Then, we map a starting configuration of atoms into some internal state (bits, qubits, or whatever we can use) of a physical system (the computer), and we start its dynamical evolution mirroring the steps of the algorithm.

It should be clear that his kind of computation is just a way to have the full information on the microscopic states of the system in the cases it is not possible to obtain the same information by direct measurements on the system of interest. The best prediction we may hope to get from this computation is predicting the final microscopic state after some time. Now, the real question is if this kind of prediction is really what we are looking for. I think that the factual answer coming from the present status of Science is negative. The bare detailed knowledge of the microscopic state may be an interesting result but does not provide insight by itself. This observation brings us to the next point.

The second implicit assumption of the question is that Statistical Physics exists only because of our limited computational capabilities. I think the history of Statistical Physics shows that it is a theory designed to extract the emergent phenomena in complex systems. Therefore, it should not be seen as expedient to overcome limited computational abilities but as the scientific way to get insight from a microscopic description by a systematic and controlled coarse-graining process.

For the above reasons, my answer to the question in the title is the following.

Our present limited computational capacity seems to preclude the possibility of direct modeling of arbitrarily complex systems. However, at least for those systems about which we do not need the full information about the initial state, we could model them better and better. Then, a good understanding of the meaning of computation would suggest that there is nothing in the present state of things hampering an asymptotic faithful representation of their behavior. However, the possibility of a faithful mapping of a complex system into another system of the same complexity is completely useless for the advancement of our knowledge. In this sense, present or future limits of computation do not look like a fundamental obstacle. The real limit is in our capacity of making sense of the results. It is a fact that Statistical Physics has been developed mainly for that purpose. If in the future, this branch of Physics or some evolution of it could help, it can only be matter of opinion.

Answer 4

It depends on what meaning you attribute to the term "fundamental". If the physics you describe is a system of discrete classical particles subject to instantaneous impact and binding forces, the computability might be feasible, say for a several trillion particles. So in this case neither the physics is fundamental, nor the incomputability of the system.

If you consider the physics as described by quantum mechanics, it gets more complicated, because already the single-particle Schrödinger equation is a continuum problem in 3+1 dimensions, i.e. fundamentally, you have an infinite number of degrees of freedom (e.g. the wave function for every point in space), even though it still describes a single particle. In order to solve a continuum problem, you will usually approximate this by a discretization scheme (e.g. finite element, finite difference, unperturbed eigen-functions,...), which makes your calculation approximate. If you want more accuracy (for continuum problems this often means being able to represent smaller wavelengths), you have to increase the number of degrees of freedom taken over to the discretized equations. Unless you happen to have an analytic solution anyway (e.g. the hydrogen atom), more required degrees of freedom means more required computational resources. In fact you have to store all of them and you have to touch all of them during computation.

If you consider a multiple-particle Schrödinger equation, you can easily imagine how complicated it gets in 3N dimensions to solve the corresponding continuum problem. Without statistical quantum mechanics you're totally lost even for the most primitive of problems. And yet, at least computational chemistry has developed several methods to manage (whether they are "ab-initio" or semi-empiric/heuristic/approximate) computations of multi-particle systems, at least on the level of a molecule. If ab-inition QM calculations are already being used for systems of molecules, I don't know, but I seriously doubt that they result in much more or even the same information than statistical/thermodynamical calculations.

If that's not enough practical incomputability, I can even go one better: in quantum field theory, the forces are themselves quantized. That is, what is already classically understood as an infinite number of degrees of freedom (the continuous field), gets another level of infinity, in that every one of the plane waves is not only able to oscillate in one mode, but rather infinitely many modes (which represents the number of photons "in this plane wave"). The possible number of photons is not constant, but can change in interactions with matter, from the ground state up to infinitely many photons. And several of these multiple photon states can even exist at the same time (they are each a quantum mechanical harmonic oscillator).

This should illustrate that the distinction between fundamental/theoretical incomputability and practical incomputability is moot. In the end, it all amounts to "practical incomputability" with respect to the number of degrees of freedom you have to carry with your simulation.

Independent of any consideration of spatial degrees of freedom, there is always the problem of solving the equations of motion with sufficient accuracy in time (aka time discretization). You may get away with explaining that you could always refine your time integration to arbitrary accuracy. However, if non-linearity is present (i.e. almost always, at least in classical physics), then the requirements of computational stability (Ljapunov exponents) is usually not satisfied, which leads to what is colloquially labelled as "chaos", i.e. it is incomputable mathematically-fundamentally.

Having said this, computational methods are often used to verify, confirm or even supply statistical statements, for example for quantum field theory, Lattice Gauge Theory is used. Therefore, not the attribute of "fundamentality" is stretched, but rather only the attribute of "accuracy". Think about it that way: if "Chaos" and it's corresponding apparently random influence is omnipresent anyway, there is no need to calculate everything to 100 digit accuracy if all you are interested in are statistical statements anyway.

Answer 5

I don't think that this question can be answered on a "fundamental" level. To judge the computational resources you must have an underlying problem that you are going to compute. But this underlying problem is always limited/based on our current understanding of physics. So, unless we manage to unify all branches of physics into a great grand super equation, we can't know what the resources to solve the problem are going to be. I don't see how you can tackle the computational problem if you haven't solved this problem first. The question is thus not answerable at the moment in my opinion.

And to my knowledge, we don't have equations that allow you to derive all properties of "macroscopic" objects from first principles. Room-temperature superconductors come to mind as a current example, unless i missed new developments.

Answer 6

There is no limitation anywhere close as fundamental as the uncertainty principle or the speed of light to simulating physical systems of any size.

Or, to be more precise, there is no limitation which we are aware of. If there were one, this would most likely constitute a most major physical discovery, comparable to relativity of quantum theory.

Of course, this is to be understood to the extent we know the underlying physical laws - quantum gravity being one prominent exception. But other than that, discovering a fundamental limitation within the assumed domain of validity of the physical theories we know would be of major scientific impact.

In particular, there is no computational limitations - which is the focus of the question - anywhere as fundamental.

Of course, simulating larger and larger systems is growing increasingly complex. This growth in complexity can be better or worse, depending e.g. whether the system is chaotic, or whether we want to describe classical or quantum mechanical systems.

However, there are two main points to be observed about this growth in complexity: Firstly, to some extent it relates to our current understanding of the system. For instance, quantum systems are hard to simulate, yet it turns out there are classes of systems we can solve exactly analytically. Similarly, as it turns out, the naive assumption that in order to simulate a quantum system, one has to store an exponentially large state vector is incorrect, as one can e.g. use Monte Carlo sampling to approximate the path integral term by term, which allows for the simulation of systems whose state vector could never be stored in a computer. Thus, there's plenty of room for improvement, and in particular there might well be plenty of room for improvement we are not aware of as of today.

Yet, there are fundamental obstacles to simulating physical systems as efficiently as we want, which can be formalized using the tools of computational complexity. For instance, it is known that simulating general spin glasses is NP-hard. Thus, unless we believe that P=NP, simulating such systems will take an exponential time (roughly). However, it should be noted that pretty much none of the relevant separations is proven: Even PSPACE, the class containing the simulation of any quantum system, is not known to differ from P (the class which is generally understood as "efficiently solvable").

However, the lack of a proven separation is not my point.

So why am I claiming that a separation in computational complexity is nowhere as fundamental as the speed of light or the uncertainty principle? The latter form a "hard wall" for our attempts to increase speed or precision: There is a hard cutoff we cannot pass. The growth in computational complexity - be it time, space, or the energy needed to carry out the computation - is much more subjective. What should we use as a time cutoff? The time it takes to complete the PhD thesis? The lifetime of a human? The age of the universe? Which you consider "fundamental" is rather subjective. The same is true for energy scales, or space: What exactly you obtain depends on what you consider a "reasonable" investment.

As a comparison, consider that there were no speed of light, but speeding up a mass would require an energy which would grow exponentially with the speed: This would not yield a "hard" speed limit independent of the situation considered - if would really depend on how much energy you are willing to invest, and how large the mass you want to accelerate is. Of course, you could argue that all the energy available in the universe is such a hard cutoff, but this would make such a limit much more subjective, and depending on global properties of the universe. This is in stark contrast to the speed of light or the uncertainty relation, which are limitations known to hold in any scenario locally, without requiring us to take into account the whole universe altogether to make sense of them.

So: For all we know, the computational limitations to simulate arbitrarily large systems lie in the scaling of computing time (and possibly storage space), which I would argue is a much weaker notion of fundamental limitation than the speed of light or the uncertainty relation.

---

Some comments:

I fully agree with Dvij D.C.'s comment that of course, this does not make effective theories superfluous, even if we could fully simulate everything, since the insight gained from an effective theory is often qualitatively different from the one gained from purely numerical study.

Then, it has been shown that there are undecidable questions about physical systems one can ask. Thus, one could argue that these are fundamental limitations to simulating physical systems. But then again, there is no experiment which could answers these undecidable questions, and thus, these are rather statements about the "expressive power" of physical theories than about the ability to simulate processes in nature.

And finally, in simulating quantum mechanical systems, one is obviously limited by the limitations of quantum theory, where the observer takes a special role. Simulating the entire universe quantum mechanically is thus something which, I would argue, is outside the scope of the theory. But again, this is a limitation of the theory, not a fundamental computational limitation.