First, Boston was cold. Actually it wasn’t too much colder than Santa Fe, but the extra wetness and windiness made it feel much colder. Except one strange night, where, after embibing some refreshments at the “Miracle of Science” bar (this is M.I.T. you know), the walk home at midnight was filled with a strong, probably 55 degree breeze. Very strange.
There were a lot of good talks at QIP, but, like any conference, the talks do not fully make up the content of the conference. I had a good time talking to various people about the hidden subgroup problem and I am more optimistic about the problem than I have been in a long time. Expect a lot of good work to be reported in the next six months.
My favorite talk of the conference was probably Oded Regev’s talk on a new public-key cryptosystem. While previous lattice based public-key cryptosystems (like the one by Ajtai and Dwork and an improvement of this system by Oded himself) were based on a problem called the unique shortest vector in a lattice problem, breaking the new cryptosystem is based on the hardness of the shortest vector problem. The funny thing is that it is based not on the classical hardness of the shortest vector problem, but is based on the quantum hardness of the shortest vector problem. One intersting offshoot of this is that there is a learning problem whose solution will lead to a quantum algorithm for certain shortest vector in a lattice problems.
Another very interesting and entertaining talk was given by Scott Aaronson (quantum computing’s younger clown.) Scott talked about a model of quantum computation in which you get to postselect on the measurement outcome. In other words, you get to perform a quantum measurement and, instead of getting one of say two outcomes, you get to always assume that you got only one of the two possible outcomes. Postselection is, as far as we know, not possible, but you know computer scientists: always talking about crazy complexity classes whose practical value is dubious. But just because there is no practical value doesn’t mean that this craziness cannot lead to some astoundingly nice results. And this is exactly what Scott was able to show. In particular he showed that the model of quantum computation with postselection, postBQP, is exactly equal to the complexity class PP. The class PP (called, unfortunately, “probabilistic polynomial time”) is the class of problems solvable by a non-deterministic Turing machine such that if the answer is yes then at least 1/2 of the paths accept and if the answer is no then less than 1/2 of the computational paths accept. A comparison with NP is that in NP, the answer is yes if at least one of the paths accept and if the answer is no then none of the paths accept. One of the trickier properties to establish about PP is that it is closed under intersection. This was done by Beigel, Reingold, and Spielman in 1991. What is really cute about Scott’s result is that he is able to obtain this proof in a very very simple way from the fact that postBQP=PP. The technique also produces a lot of other previous results in a nice clean manner. Amazing how a quantum model of computation, with a crazy extra assumption (postselection) can make things so much clearer!
QIP 2006 will be held in Paris and QIP 2007 will be held in Brisbane, Australia.
O brave new quantum world!