A small cadre of computer scientists and physicists converged on the Simons Institute for the Theory of Computing for four days in February to exchange perspectives on the rich analogy that exists between the fundamental questions of complexity theory and condensed matter physics. The emerging field of quantum Hamiltonian complexity, which sits at the cusp of the two fields, has seen some astonishing developments in recent years, according to Umesh Vazirani of the University of California at Berkeley. Vazirani was one of the organizers of the February workshop, which will be followed by a semester-long program on the subject in Spring 2014.

Complexity theory centers on the famous “satisfiability” problem—believed to be beyond the reach of efficient algorithms—which concerns finding values for a collection of variables that satisfy a given set of constraints. In condensed matter physics, the goal is to understand the properties of the lowest-energy state of a many-body quantum system. One of the major realizations of recent years is that these two foundational problems are intimately related, and that complexity theorists and condensed matter physicists have a lot to learn from each other.

There is, however, one crucial difference between these two problems. While an n-variable system in classical computer science requires only n bits to describe a given state of the system, it takes at least 2ⁿ complex numbers to describe a state in an n-body quantum system. Given this enormous scale, one of the major puzzles of condensed matter physics is why physicists are able to say anything at all about the behavior of such systems, Vazirani said. “One possible explanation is that there’s a little corner of the state space, the easy corner, and that this is where quantum states occurring in Nature sit,” he said. Complexity theory offers a precise language in which to formulate this notion, as well as several more of the defining philosophical problems of quantum mechanics.

The February workshop on quantum Hamiltonian complexity brought together physicists and computer scientists to explore these questions, and also served as a dry run for the upcoming semester-long program on the subject.

Prior to the workshop, Vazirani conducted lengthy discussions with fellow organizer Dorit Aharonov of Hebrew University, as well as with the other organizers, on how to structure the workshop to create true dialogue. As with many other research topics in which theoretical computer science overlaps with other disciplines, progress in quantum Hamiltonian complexity is impeded by a “viscosity” arising from the different languages of the two fields, Vazirani said—a viscosity that the Simons Institute hopes to overcome. “We wanted real engagement at the workshop, not just a bunch of people coming in and giving talks,” Vazirani said.

The organizers decided to keep the workshop small, inviting only 25 of the leading figures in the two fields and scheduling just 14 long talks instead of trying to fit in talks by all the attendees. The organizers also made the key decision that “discussion trumps schedule,” Vazirani said: Attendees could ask as many questions as they liked, even if the resulting conversations pushed a talk beyond its allotted hour. That approach made for a very different atmosphere from that at a traditional conference, Vazirani said. “We discovered that computer scientists and physicists knew a lot about each other’s questions.”

The workshop organizers are mulling over such non-traditional approaches for the semester-long program—for instance, the idea of holding background tutorials not before but after a seminar, when the participants have a sense of what they need to learn about and why. “The Institute provides a forum where you can do something like that, which is exciting,” Vazirani said. “There’s a real potential to reduce the viscosity and greatly speed up progress in the field.”

Related Articles:

Letter from the Director
Fall 2013 Programs
Report: Symposium on Visions of the Theory of Computing, May 2013
Calvin Lab Renovation