In the previous story, titled Some jobs will take everything you give them, I described what I called “undoubtedly the lowest point of my career.” So I decided, for the sake of balance I suppose, to share a story about one of the high points. If it comes across as though I’m boasting or blowing my own horn, please forgive me, that’s not my intention. Naturally one risks putting their own work in too positive a light with a story about a career high point.
As a graduate student, I worked on topics in quantum computing that included quantum cellular automata, quantum finite automata, and space-bounded quantum computation, which were very much off-the-beaten-path in quantum computing at that time. I was definitely interested in those things (and still am), but a big part of choosing to work on them was that others hadn’t so much, and that gave a student like me a fighting chance to contribute and discover something new. I was able to publish papers on this work, and would get invited to speak at quantum computing workshops from time to time, but I wanted to do something somehow more relevant and of broader interest. Then, when I graduated and began working as a postdoc at the Université de Montréal in 1998, I started thinking about quantum interactive proof systems. This turned out to be a topic that would give me a lot to think about for the two decades that followed.
In theoretical computer science, interactive proof systems are an abstract computational model involving an interaction between a hypothetical prover and a verifier. The prover and verifier have different goals: the prover’s goal is to convince the verifier that some given statement is true (whether or not it actually is true), while the verifier’s goal is to check the validity of the prover’s argument — and to not be fooled into believing the statement is true if it happens to be false. You could say that the practical importance of this model is open to debate, but there is no questioning its importance in theoretical terms. It has played a truly salient role in the development of complexity theory, and it’s also important in theoretical cryptography. To be clear, these are claims about the classical version of this model, whereas I was working on the quantum version of it, which previously hadn’t really been studied at all.
I discovered something interesting: ordinary (meaning classical) interactive proof systems could be parallelized by making the model quantum, in the sense that long conversations between a classical prover and verifier could be crunched down to just three quantum messages by a quantum interactive proof system. There is no way to do this in a purely classical way unless something unexpected in complexity theory happens: the so-called polynomial-time hierarchy collapses. This is all to say that this was a bonafide interesting result that illustrated a new way to take advantage of quantum information. For the first time, I felt like my work had relevance. This was in the fall of 1998.
In January 1999, I travelled to DePaul University for the AQIP ’99 (Algorithms in Quantum Information Processing) workshop. The “A” for algorithms was later shed, and the workshop became the premier conference on the theory of quantum computing known as QIP — which is coincidentally the name of the complexity class associated with quantum interactive proof systems that I now had something to say about. I was not invited to speak at the workshop, and did not plan to speak, but I did bring some printed copies of the new paper about quantum interactive proof systems that I’d recently finished. I shared it with several people, and the organizers kindly squeezed in an extra talk slot for me to present it toward the end of the workshop. This would not likely happen now because QIP has become much more formal and competitive, but back then there wasn’t a program committee and talks were by invitation, so it wasn’t so unusual.
One of the people I shared my paper with was Alexei Kitaev — a name that anyone who works in quantum computing recognizes immediately. He was already a legend, even back then, and this was the first time I’d met him. He was giving a talk on the QMA-completeness of the local Hamiltonian problem at the workshop, which is now a cornerstone result in quantum complexity theory. I was really excited to hear about this result, which wasn’t directly about quantum interactive proof systems but was closely related, so I was pretty sure he would be interested in my new work. I gave him a copy of my paper and we talked for a bit, in a short conversation that a few others joined and left in a typical coffee break sort of fashion.
The next morning brought another coffee break, and I was milling around trying not to look awkward when Kitaev came up to me appearing kind of tired but excited. He’d been looking for me! He explained that he was very tired because he’d stayed up all night studying my paper, and he said that it was a beautiful result. I’m not exactly sure how much of it sunk in at that moment and how much of it I came to appreciate later — but when I look back now it seems like it came out of a dream. One of the greatest minds of our time decided to stay up all night studying my work, and found beauty therein.
Now, there really isn’t much point in reading that old paper any longer. Shortly after the workshop, Kitaev invited me to come to Caltech to work with him for a couple of weeks, and in that short time we were able to prove a great deal more about quantum interactive proof systems than I had on my own, completely subsuming my original result in the process. (No problem at all, I still published the paper, as just about any academic researcher would have.) It turned out that not only could classical interactive proof systems be parallelized through quantum information, but so could quantum ones, which is a more general result. And that was just one of several new things we proved. Among the other things was an upper bound on the computational power of quantum interactive proof systems that, to my knowledge, was one of the very first times semidefinite programming was introduced into quantum computing.
I was both awed and humbled by the power of Kitaev’s brain, but not in a negative way. By witnessing greatness, those of us who are more ordinary are offered a glimpse of that to which we may aspire.