Some Speculation on Future Computational Physics
There are two broad approaches to physics today. One of these is symbolic – manipulating symbols, often by hand, to extract some hidden structure in a problem that can result in a computationally cheap solution, and often a great deal of deeper understanding. The other is numerical – applying large volumes of often much simpler computations. The numerical approach is generally fairly agnostic to the structure of the problem and may work in places where symbolic pattern matching fails or is just difficult, but can often scale very poorly.
Directly computing quantum mechanical problems is generally exponentially hard, and even the cheaper approximate algorithms often still have nasty time complexities, such as O(n^7) or O(n^11). These are much better than exponential time, but still very impractical even at fairly small scales and may not be sufficiently accurate on account of being approximations. This is not merely a problem of “not enough compute” – these problems scale fast enough that Moore’s Law couldn’t compete even if it were plausible that it could last another few decades without major hurdles. The compute requirements are so high that some Kardashev 12 civilization that can tile the observable universe with thermodynamically-optimal super-GPUs would still find a great deal of hilariously tiny problems that they would struggle to simulate.
However, we are in the very early days of computing. Modern computing as a field has existed for only a little less than a century, and we can be guaranteed that an enormous range of groundbreaking discoveries in computing will remain undiscovered for many centuries or longer.
The symbolic approach to physics is interesting, in that it has yielded centuries of enormous progress, and there are no obvious signs that it is slowing down. The Hamiltonian mechanics formulation of physics has been around for nearly two centuries, and has in recent decades been augmented by significant progress in the field of symplectic geometry, a branch of geometry that studies spaces where transforms preserve the area of shapes. The primary problem with symbolic physics is simply that it was built for a world where compute was expensive.
So allow me to speculate where things may go in the future and where the next orchards of fruit may lie based on some hints we can find today if we know where to look.
Computer Algebra Systems and Scaling Symbolic Physics
Sussman’s classic programming textbook “Structure and Interpretation of Computer Programs” (SICP) is very famous, but far less well-known is the sequel “Structure and Interpretation of Classical Mechanics”, a physics textbook where the equations are replaced by Scheme code. The book also argues that physics traditionally doesn’t “typecheck” and that translating seemingly unambiguous equations into computer code is actually not a trivial task because of the amount of approximations and contextual information that is often left out.
The book centers around a Computer Algebra System that Sussman built himself, which can take physics equations written in Scheme and apply a variety of transformations on them that are useful for physics work. It can of course handle some very complex symbol manipulation simply because of how fast computers are.
It seems to me as though there is a great extent to which computers could automate at least some amount of symbolic physics work in a way that symbolic problems that would be impractically large for humans could be done by machines. Furthermore, we can start asking questions about the nature of this automation. Writing a mass of symbols on a page is one thing, but once it’s represented in a computer you have a more explicitly structured object – a tree or graph or something else of this sort. If the system of equations is viewed as a tree or graph, what might its structure imply? At the very least are there interesting implications for visualization that might not be obvious from historical approaches?
In general, what I expect we will find in the coming decades, if people choose to investigate this further as opposed to shutting their brains off and letting their AI algos go brrr, is that there is a middle ground between symbolic and numerical physics. Or perhaps simply an extrapolation of symbolic physics – rather than focusing on small, simple structures that humans can parse out manually, what kinds of dramatically more complex structures can we extract and operate on if we can throw a few teraflops or petaflops of compute at it?
Certainly, there seems to be some evidence that “AI” bears fruit when applied to physics, but if anything this is evidence for my point – there is structure in physics that computers can extract that is simply too complex for humans to do manually. However, the matrix multiplication that is the foundation of modern machine learning algorithms may be very versatile but it is often not the most efficient method of computing things. With a bit more cleverness, we likely will in time find more conventional mathematics and algorithms that can answer many of the problems that machine learning is starting to answer, but more efficiently and while yielding deeper understanding.
The math behind quantum mechanics is just linear algebra with very large matrices. These matrices also have additional constraints, generally that they are square and that they only encode rotations. Other more specific constraints may exist in more specific scenarios.
At least in the case of quantum computing, which granted is constrained to be easier for humans to reason about than mere random assemblies of particles and forces, the matrices that encode various quantum logic gates are often very sparse, and very symmetric. The operations on them generally include matrix multiplication and kronecker products, both of which lend themselves well to being reduced to simple operations on block matrices, or essentially matrices of matrices.
There are plenty of techniques that can make use of block structures in matrices. As someone who used to be very interested in game development, quadtrees look like a very applicable tool for mapping the various regularities in quantum computing matrices, both for tracking large zero blocks in matrices, as well as tracking when two blocks of a matrix may be identical to or simple transforms of each other, which may yield itself to symbolic simplifications of these giant matrix operations.
To a large extent, this kind of approach would simply be transforming operations on gigantic arrays of numbers into more complex but ultimately cheaper operations on trees that store compressed representations of these arrays. If handed a truly random problem perhaps this may not be much of an advantage, but if there is really so much structure in physics that we can spend centuries making progress through manual symbolic manipulation, then there likely is a great deal of structure that can be exploited in such problems.
Additionally, we should look to tools like SAT solvers and Abstract Interpreters.
SAT
SAT, or the Boolean Satisfiability Problem, as I have discussed many times before, is the classical example of an NP-complete problem. It is in the NP complexity class, which makes it in the worst case a fairly difficult problem, but it is also expressive enough to be able to emulate any other problem in NP, which covers a truly gigantic range of common problems. An algorithm that can efficiently solve SAT problems is in a sense a general-purpose problem-solving algorithm.
Such algorithms have been developed. While SAT was once dismissed as exponentially hard and fundamentally intractable, methods like DPLL and CDCL have shown that reality is far more complex. There are fairly small problems with only a few hundred variables that seem to be intractable, and others with millions of variables which should be unimaginably impossible and yet can be solved in under an hour by a single CPU core. Asking the complexity of a SAT problem is like asking the complexity of an interpreter – it depends entirely on the problem you give it, which can vary extremely wildly. You can hand an interpreter a tiny, infinitely-looping program which takes an infinite time to run, you can hand it a gigantic but well-behaved program that runs fairly quickly, or you can give it anything from a gigantic zoo of other program behaviors. SAT is no different, and real-world problems are very often surprisingly tractable.
In the case of SAT, the original DPLL algorithm worked okay for a long time, but it wasn’t until the development of CDCL in the late 90s that things really kicked off, and today there is a whole zoo of different heuristics and other features bolted onto SAT solvers to assist in solving problems. Much like the aforementioned quantum problems, we can view DPLL as operating on a tree that compresses an impractically large flat array of values for cheaper computation, but the more advanced techniques that developed later and built on top of DPLL were eventually what made these solvers dramatically more practical and useful.
There is actually a surprising amount in common between SAT and quantum mechanics – the former can be viewed as equivalent to simple operations on exponentially-large arrays of boolean possibility values, while the latter is simple operations on exponentially-large arrays of complex probability amplitudes. There certainly are differences, but the general organization of the arrays and the operations on each value are shockingly similar. SAT solving algorithms increasingly pay attention not only to the tree structure that DPLL generates, but also the graph structure of the SAT problem encoded in the interactions of constraints, which is something that should be just as applicable to quantum circuits.
I wouldn’t be surprised if deeper research into this in the coming decades can start to transfer ideas back and forth, and many of these quantum problems become much more tractable with classical methods. And by the time that happens, perhaps we’ll have a few more decades of SAT solver breakthroughs to apply as well.
Abstract Interpretation
Abstract Interpretation is another very interesting case that approaches even less tractable problems. Predicting the behavior of a program statically – as in, without running it – is generally considered undecidable, effectively mathematically impossible. However, this is really only the case sometimes, and there are a great deal of programs in practice that are relatively well-behaved and can be reasoned about. Turing’s original proof about the undecidability of the Halting Problem is, contrary to popular belief, not at all a proof that the halting problem can never be solved, but merely that the total number of states that a computer can be in is greater than the number of states that just happen to encode proofs about whether or not other program states eventually lead to an infinite loop.
Abstract Interpreters approach this problem by attempting to track abstract statespaces of a program. They check whether or not there is some possible input to a program that can result in the program reaching a known bad state, such as a crash. However, rather than running every possible input of the program (which may be practically infinite for many programs), they instead assign each variable some kind of lower-resolution model, such as an interval that encodes known largest possible and lowest possible values. If the program adds two numbers, their minimum and maximum values can be used to easily compute the minimum and maximum of their sum. Other “abstract domains” beyond simple interval arithmetic can track other approximations of state spaces, with the main constraint being that the set of states tracked by the domain should always be a superset of the actual statespace of a variable – if it says that X is between 0 and 10, it should be impossible for X to equal 11 or -23 or 8015, but it is not strictly necessary that X must be capable of equaling 8. There are additionally methods for sound approximations of loops, control flow, memory, and more.
Abstract Interpreters get around the problem of undecidability by occasionally answering “I don’t know” rather than exclusively “yes”or “no”. Their models of variables are sound approximations, but they are still merely approximations. They will occasionally insist that the program may have a bug even when it doesn’t, but they won’t tell you it’s safe when it’s not.
The reason why Abstract Interpreters are interesting for physics is that, like SAT solvers, they provide a library of practical computational methods for attacking incredibly general and practically useful problems that many would dismiss as fundamentally unsolvable. Furthermore, their focus on intervals and other structures seems very useful for physics, and not terribly far off from tools that are already occasionally used. Interval arithmetic is occasionally used in physics, and tools in chaos theory such as Lyapunov exponents share a lot in common with them, but Abstract Interpretation also contains many ideas for taking these methods and doing far more complex things with them that help to give good answers in cases where naive interval arithmetic may simply explode and insist that the result is “somewhere” between negative and positive infinity.
I expect that it will not be trivial to translate these ideas into physics, and frankly there should be a much greater effort to translate these ideas into practical software development tools rather than mere academic projects or niche industrial tools for verifying that planes won’t fall out of the sky.
Overall though, computing is still in its infancy, and efforts to adapt the past few centuries of physics work to the capabilities of modern computers are still very primitive and surface-level. Furthermore, it’s worth remembering that much of physics work historically has not been in applying new mathematics to physics problems, but rather using physics problems to inspire the development of new mathematical tools, which can then be applied elsewhere. We should not be surprised if the deeper investigation of computational physics also leads to serious breakthroughs in the broader field of computer science as well.
This is a relatively short article I threw together in a few hours late at night, with a bunch of rough ideas I’ve had on my mind for a while. I hope you found it interesting, and maybe a few readers might be inspired to start investigating this themselves, it certainly would be helpful and I expect there’s a lot of valuable work waiting to be done.