Physics Envy

There is something cool about physics. Black holes, anti-matter, “God’s particle”: it all sounds so exciting. While our TCS “mental experiments” typically involve restricting the inputs of constant-depth circuits, physicists talk about jumping into black holes while holding a dictionary. Physicists also have a knack for names: notions such as “uncertainty principle” or “monogamy of entanglement” sound so much cooler than “Cauchy-Schwarz Inequality” or “Distributive Law”.

But a deeper reason to envy physicists is that (with certain important exceptions) they often have fairly good intuitions into how their systems of interest behave, even if they can’t always prove them. In contrast, we theoretical computer scientists are more often than not completely “in the dark”. A -step algorithm to compute the mapping can be modeled as applications of some simple local update rule to the initial state . Studying the evolution of systems is the bread-and-butter of physics, but many physical intuitions fail for the progression of an algorithm’s computation. For example, for general algorithms, we do not have a natural sense in which the state of the system after steps is “closer” to than it is to . The intermediate state of a general algorithm is rather non informative. Similarly, we do not have a nice, even conjectural, way to characterize the set of functions that can be computed by steps: the lack of such clean “complexity measures” is strongly related to the natural proofs barrier for proving circuit lower bounds.

But there are some algorithms for which better “physical intuition” exists. Many optimization algorithms have a “potential function” that improves at every step, and other algorithms such as Monte-Carlo Markov-Chain sampling, are inspired by and can be analyzed using physics intuition. These connections have been recently explored, resulting in both new algorithms as well as better understanding of algorithmic techniques for optimization and learning, as well as the regimes in which they apply.
There are also cases where the computer-science intuition can help in analyzing physical systems. Quantum computers are of course one example, but apparently there are other interesting physical systems (maybe even black holes? see also this summer school) which are “disordered” enough that the best way of thinking of them might be to treat them as random circuits of certain complexity. More generally, in recent years physicists have began to view information and computation as an increasingly useful lens through which to understand physics. The “it from qubit” perspective, whereby spacetime emerges from information rather than the other way around, is growing in popularity.
Finally, on a more “meta” level, the task of doing theoretical physics itself can be thought of as a computational problem. In a fascinating talk, physicist Nima Arkani-Hamed discusses the problem of finding a theory of physics as essentially solving an optimization problem in the “space of ideas”. Specifically, it is a non convex problem, and so a local optimum is not necessarily a global one. Arkani-Hamed calls classical physics “the top of a local mountain in the space of ideas”, i.e., a local optimum, while quantum mechanics is the top of a “taller mountain”. The reason it was hard to make the leap to quantum mechanics is exactly because they “they’re not smoothly connected”.

By classical physics being a local optimum, we mean that if you try to “tweak” classical physics by turning (in his words) “knobs, and little wheels, and twiddles”, you will only get a theory that is less beautiful and with less explanatory power. To get to the better theory of quantum mechanics, one needs to make a conceptual jump, rather than a series of small tweaks. Just like classical physics, quantum mechanics itself is a local optimum, for which every small “tweak” will only make it less beautiful and predictive. This is one explanation as to why it has been so difficult to find the grander theory that unifies general relativity and quantum mechanics. As Harkani-Hamed says, to find such a theory “there’s going to have to be a jump of a comparable magnitude, in the jump that people have to make in going from classical to quantum”. In a related point to “it from qubit”, he also says that “many, many of us suspect that the notion of spacetime can’t be fundamental and it has to be replaced by something else.”
Interestingly, in certain settings convex optimization can be applied to explore the “space of ideas”. In particular some works on the “bootstrap method” use semidefinite programming to explore the space of quantum field theories that satisfy certain symmetries. It turns out that sometimes the constraints that one can derive from these symmetries are so powerful, that they completely determine the theory.

A fall seminar

The bottom line is that we’re seeing a more and more interesting exchange of ideas between physics and theoretical computer science. As I’m sure I already demonstrated in some cringe-worthy statements above, I know very little about this interface, but am interested in finding out more.

So, Tselil Schramm and I will be running a graduate seminar this fall. We will be learning together with the seminar participants about some of these connections, and hopefully by the end of the term we will all be a little less ignorant.

Some of the topics we will discuss include:

• Connections between statistical physics and algorithms, understanding the physics predictions for hard and easy regimes via phase transitions.
• Quantum information theory: quantum-inspired classical results, as well as classical algorithms for quantum problems.
• The conformal bootstrap: exploring the space of possible physical theories using semidefinite programming.
• Black holes, bulk/boundary correspondence, and computational complexity.
• Quantum superiority – understanding the current proposals for demonstrating exponential speedups for quantum computers, and the evidence for their classical difficulty.
• Quantum Hamiltonian Complexity – the quantum analog of constraint satisfaction problems, with questions such as the existence of a “Quantum PCP Theorem”.

Each one of these is probably worth a semester course on its own, and is typically presented to people with significant physics background. But we are hoping we can create a “tasting menu” and manage to take away some insights and ideas from each of those areas, even if we can’t cover the whole ground.

Participants in the seminar will not only present papers or surveys, but also write a blog post about them, which I will post here, so stay tuned for more information.