As many of you might know already, Berkeley recently won the competition for the establishment of a Simons Institute for the Theory of Computing. The institute is initially funded for 10 years and will mostly be running semester-long programs in the same vein as MSRI, also in Berkeley, does in the mathematical sciences. The Institute will be housed in Calvin hall on the Berkeley campus; the first two programs (real analysis and big data) will start next Fall. In the Spring of 2014 two new programs will take over, in quantum Hamiltonian complexity and evolutionary biology. One of the most appealing aspects of the new institute is the interdisciplinary range of these programs; indeed one of the goals of the Simons institute is to promote the theory of computing as a lens on the sciences at large, a viewpoint that has been pushed forward by the theory group in Berkeley for some time now. One of the first events held by the institute will be a symposium on “Visions for the Theory of Computing”, which, if it is as successful as the last conference organized in the same vein at Berkeley, promises to be quite exciting.
I’m in Berkeley this week for a “preparatory meeting” for next Spring’s workshop on quantum Hamiltonian complexity. Calvin hall is still undergoing renovation so the three-and-a-half day workshop is taking place in the beautiful Berkeley men’s Faculty club (yes, Berkeley has both a men’s and a woman’s faculty clubs…both now co-ed of course ). A smallish wooden structure dating back to the early 1900s, the club is hidden under the trees along a creek right in the heart of campus and offers an unexpected retreat from the surrounding hustle and bustle.
Why a preparatory meeting, almost a full year before the start of the actual semester? Whatever the original motivation, judging from the first day of talks it looks like it’s going to turn out to be an excellent idea. The point I think is to bring together a subset of participants ahead of time and plant the seeds for some of the topics and ideas that will be explored during the semester. Although it may sound long, a semester is actually a pretty short period in which to do real research. This is especially true given the interdisciplinary nature of this particular semester, which Dick Karp, the Simons Institute director, qualified as “most esoteric” in his introductory speech this morning (then of course, Karp himself is no stranger to “esoteric” topics, having followed an impressive research career from being one of the inventors of the theory of NP-completeness to doing work in computational biology before its time). Many physicists will participate in the workshop, and although we all share an interest in the same fundamental problems there tends to be discrepancies in language, to say the least. What makes the area so rich though is that there is quite a fruitful discussion going on, with the computer scientists trying to put their hands on the actual problems faced by the physicists, themselves doing their best to communicate the diverse range of valuable intuition gained through their long experience with the systems whose complexity the thematic semester aims to characterize. As we experienced first-hand today, this intuition can be very diverse…making the problems all the more interesting!
The workshop has four days of talks, very roughly organized as follows. The first day had talks relating to interactive proofs and the possibility for checking quantum mechanics through classical interaction as well as the quantum PCP conjecture. The second day will be devoted to properties of ground states of local Hamiltonians: area law, the efficiency of numerical methods such as DMRG, etc. On Thursday we will hear about topological properties of quantum mechanical systems. Finally on the last day we will end with a bang (as the workshop organizer Umesh Vazirani put it) by looking into the computational power of theories that attempt to extend quantum mechanics, such as quantum gravity and quantum field theories. Quite a program
I hope to discuss today’s talks (and the ones coming up) in more detail soon; they were excellent. There were some very interesting discussions in the afternoon as to the validity of the quantum PCP conjecture. A number of partial results have been obtained recently pointing in both directions: that the conjecture may be valid, but if so the hard instances (local Hamiltonians) must have a particular structure, different from that of instances that arise in Dinur’s proof of the classical PCP theorem. Whether true or not, one thing is clear, which is that the quantum PCP conjecture has already well earned its prefix: motivated by a real quantum mechanical problem, it will require more than just an adaptation of classical TCS techniques to solve — the kind of quantum beast I like!