By Noah Geller, Spring 2021.
In his talk, “The Shapes of Spaces and the Nuclear Force,” [1] physicist Gregory Moore describes the productive exchange of ideas between mathematics and physics as a tennis match. In this analogy, mathematicians develop theories which they pass over to the physicists. The physicists apply those ideas and, in doing so, make mathematical discoveries which they hit back over to the mathematicians. This fruitful exchange between mathematics and physics is as old as either discipline. However, a new discipline is stepping onto the court: computer science.
One surprising way that computer science has affected our understanding of the physical world is in the study of black holes. Leonard Susskind, an esteemed physicist at Stanford University, has shown strong parallels between complexity theory, a branch of computer science, and the behavior of black holes [2]. Complexity theory studies how difficult computational problems are to solve. For example, a complexity theorist might investigate how the amount of computing power required to run an algorithm increases as the amount of data for that algorithm increases.
The relationship between complexity theory and physics is not obvious. However, the advent of quantum computing has brought these fields closer together than ever before. Quantum computing is the study of how we can take advantage of quantum mechanics to build a fundamentally new type of computer. In quantum computing, the bits of classical computers get replaced with the quantum bit, or qubit. In the correspondence between black holes and complexity theory that Leonard Susskind describes, a black hole of entropy S is compared to a quantum circuit with roughly S qubits [2]. Furthermore, the time coordinate of the quantum circuit corresponds to the time coordinate of a special reference frame near a black hole called Rindler Time [2]. This “pattern of similarities” suggests that the connections between physics and complexity extend well beyond the realm of quantum computing [2].
Another deep connection between physics and computer science was discovered last year when a group of computer scientists used complexity theory to solve an open problem in quantum mechanics. Their proof, titled “MIP*=RE,” proved that two types of computational problems are equally difficult. This discovery was not only important to computer scientists, as it also solved significant open questions in quantum mechanics and pure mathematics [3].
In order to understand what MIP* means, imagine you are playing a game with a friend who is so far away that you cannot communicate with them. Your chance of winning this game would normally depend on the rules and any lucky correlations that might exist between your strategies. However, in order to increase your chances of winning, you and your friend are allowed access to entangled quantum systems. When two quantum particles are entangled, even if those particles are far away, knowing the result of a measurement performed on one particle can provide information about a property of the other particle [4]. This allows quantumly entangled systems to be more correlated than classical systems separated by the same distance [4]. If you and your friend are allowed to have entangled quantum systems, then you will be able to take advantage of these stronger correlations and coordinate strategies more effectively.
This type of game—where two players are physically separated but have access to quantumly entangled systems—is aptly called a non-local quantum game. The set of computational problems equivalent to finding the probability of winning this type of game is called MIP*.
Although finding the probability of winning a non-local quantum game seems like a bizarre and esoteric computational exercise, it turns out to be equivalent to a problem in computer science: The Halting Problem. Alan Turing, a foundational figure of the modern theory of computation, constructed a model for a universal computer called a Turing Machine. Although a Turing Machine is more of a mathematical description of computation than a prescription for how to build a physical computer, every algorithm that a physical computer executes has a corresponding Turing Machine that can perform the same computation [5]. Turing proved that, given a Turing Machine, there is no way to determine whether the program will finish or continue to run forever [5]. Therefore, determining whether a given Turing Machine will halt is difficult, if not impossible.
It turns out that there is a large class of computational problems that are equivalent to solving The Halting Problem. This set of problems is called RE [4]. In “MIP*=RE,” a group of theoretical computer scientists proved that the set of problems equivalent to finding the probability of winning a non-local quantum game is the same as RE, the set of problems equivalent to The Halting Problem [3]. The fact that these two categories of problems are equivalent is significant within computer science because a primary goal of complexity theory is to sort the world of computational problems into distinct classes of difficulty.
A byproduct of the result that MIP*=RE is a resolution to a decades old open question in math and physics: The Connes’ Embedding Problem. This problem relates to how well infinite matrices can be approximated by large finite ones and whether two different models of quantum entanglement are equivalent [6]. The fact that the Connes’ Embedding Problem was solved by techniques of theoretical computer science rather than physics or mathematics, opens the door to a future of productive back-and-forth between computer science, mathematics, and physics. Computer scientists have entered the metaphorical tennis game and are here to stay.
[1] Moore, Gregory. 2019. “The Shapes of Spaces and the Nuclear Force.” https://www.youtube.com/watch?v=Xk-vFAw_4no.
[2] Susskind, Leonard. 2018. “Three Lectures on Complexity and Black Holes.” (October). https://arxiv.org/abs/1810.11563.
[3] Ji, Zhengfeng, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen. 2020. “MIP*=RE.” (September). https://arxiv.org/abs/2001.04383.
[4] Yuen, Henry. 2020. “MIP*=RE – Henry Yuen.” youtube.com. https://www.youtube.com/watch?v=6daiUh-qe9w.
[5] S. Barry Cooper, and J. van Leeuwen. 2012. Alan Turing: His Work and Impact. Waltham, MA: Elsevier Science.https://search-ebscohost-com.proxy.uchicago.edu/login.aspx?direct=true&db=e000xna&AN=485001&site=ehost-live&scope=site.
[6] Junge, M., M. Navascues, C. Palazuelos, D. Perez-Garcia, V.B. Scholes, and R.F. Werner. 2011. “Connes’ embedding problem and Tsirelson’s problem.” Journal of Mathematical Physics. https://doi.org/10.1063/1.3514538.