The Quantum Pontiff

At QIP, I was struck by something odd about the invited speakers. First, of course, was their age. The group of speakers was much younger than in previous years. Many of the speakers are from the second generation of the quantum information science revolution (we must compete with string theory, no?) But then it struck me: most of the speakers have spent a considerable length of time at the Institute for Quantum Information at Caltech. In fact 12 of the 22 invited speakers are IQI alumni in some manner. Now that’s a pretty amazing track record for a single institute.

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.

Nothing like a little shameless self-promotion: quant-ph 0501044

Optimal measurements for the dihedral hidden subgroup problem
Dave Bacon, Andrew Childs, and Wim van Dam
We consider the dihedral hidden subgroup problem as the problem of distinguishing hidden subgroup states. We show that the optimal measurement for solving this problem is the so-called pretty good measurement. We then prove that the success probability of this measurement exhibits a sharp threshold as a function of the density nu=k/log N, where k is the number of copies of the hidden subgroup state and 2N is the order of the dihedral group. In particular, for nu<1 the optimal measurement (and hence any measurement) identifies the hidden subgroup with a probability that is exponentially small in log N, while for nu>1 the optimal measurement identifies the hidden subgroup with a probability of order unity. Thus the dihedral group provides an example of a group G for which Omega(log|G|) hidden subgroup states are necessary to solve the hidden subgroup problem. We also consider the optimal measurement for determining a single bit of the answer, and show that it exhibits the same threshold. Finally, we consider implementing the optimal measurement by a quantum circuit, and thereby establish further connections between the dihedral hidden subgroup problem and average case subset sum problems. In particular, we show that an efficient quantum algorithm for a restricted version of the optimal measurement would imply an efficient quantum algorithm for the subset sum problem, and conversely, that the ability to quantum sample from subset sum solutions allows one to implement the optimal measurement.