CQE PI Feature – Anand Natarajan

Where Physics Meets Computer Science

Featured in QSEC newsletter in spring 2022

My research is on quantum complexity theory: the study of the computational power and limitations of quantum computers, and more generally models of computation that use quantum mechanics. More specifically, much of my research focuses on the complexity of proofs: how hard is it, not to solve a computational problem, but to certify to a computationally limited verifier that a hard problem has been solved correctly. In the quantum world, proofs give us a fascinating new lens to study entanglement, which is one of the most characteristic phenomena of quantum mechanics. Quantum proof systems may also be useful in practice, in the likely case that quantum computers become available over the cloud: users will want to certify that their computations were performed correctly by the machine in the cloud. There is also a rich theory around proof complexity and related topics (such as constraint satisfaction problems) in classical computer science, and much of my research focuses on areas in which the quantum picture is strikingly different from the classical one.

My current projects span a few different directions. With Tina Zhang (a student at MIT), 3Honghao Fu (a postdoc at MIT), and John Wright (faculty at UC Berkeley), I have been studying several questions on the complexity of nonlocal games, motivated by my postdoctoral work with John and others on the complexity class MIP*. That work used computational complexity theory to construct an interactive protocol—a game, or a Bell test in the terminology of physics—that could distinguish between two models of quantum mechanics that had hitherto been considered to be equivalent. We are exploring whether the analysis of our protocol can be drastically simplified using tools from classical computer science, and whether the protocol itself can be cast in an especially simple form known as a linear constraint system game. If we succeed, our results could be useful to mathematicians working in group theory, and the theory of operator algebras.

Other directions I am studying, together with Sunny He and Sujit Rao (students at MIT) and Chinmay Nirkhe (a student at UC Berkeley) are focused on quantum proof states that can be efficiently verified by quantum computers. We are interested in understanding the difficulty of physically preparing such proof states, even given access to substantial classical “hints” (such as the ability to query a computationally powerful oracle). We are also working towards understanding when quantum proof states give an advantage over classical proofs (the QMA vs QCMA problem, in complexity jargon), as well as connections between quantum proofs and quantum error correcting codes (problems related to the quantum PCP conjecture).

I first got interested in quantum information as an undergraduate studying physics at Stanford. I had an independent interest in the theory of computation, and reading some lecture notes and blog posts by Scott Aaronson (formerly at MIT, now at UT Austin) convinced me that quantum computing was a field that combined the best parts of fundamental physics and theoretical computer science. Scott’s writings laid out the case that building a quantum computer is not just about breaking codes or designing catalysts, but addresses the fundamental scientific question of what can be efficiently computed in our physical universe. I started my PhD in 2013 with Aram Harrow at the Center for Theoretical Physics at MIT, and over the last 9 years I’ve been thrilled to watch the rapid progress that quantum computing has made, and the surprising ways in which it has intersected other fields. One of my favorite things about our field is that, since it is so young, students can quickly reach the research frontier and start participating as full-fledged members of the community: indeed, many breakthroughs of the last few years were made by graduate students. I personally greatly enjoy working with my collaborators at all levels of seniority and I deeply value the friendships I have made along the way, which have helped to keep me going even during research setbacks.