QIP 2010 – Post 1 – Update
Supposedly there’s something out there called “live blogging” but I haven’t the slightest idea what it’s all about so a collection of posts will have to do. First, let me point out that all the talks are being recorded so I won’t give über-detailed posts since you should be able to get the details from the videos once they are available.
The first talk was by Umesh Vazirani. It was somewhat of an overview and covered a lot of ground. The thing that seemed to get the most response was his discussion of an interesting algorithm for, what amounts to, making optimal choices based on “expert” advice. So, suppose you have n financial advisors who are giving public advice on stock picks. You want to make your buy stock based on the advice of one of these dudes each day. As you move through the year, you keep track of how well each advisor is doing so you get some idea of who’s good and who’s not, giving you a better sense of “who to follow.” The idea is to optimize your choices.
The interesting thing about this algorithm is that it closely resembles an intuitive one that my wife used to kick my ass in a football pool this year. She did a very similar thing using the “experts” from ESPN, CNNSI, etc.
The next couple of talks were interesting. I’ll have a photo of Dan Gottesman soon since he looked an awful lot like Steve Jobs at MacWorld when he gave his talk. Scott Aaronson finished up the session with “freeze-dried” computation – how much computational work can be stored in a quantum state for later retrieval? If quantum states are exponentially large, then possibly a huge amount can be stored, though one still must contend with the Holevo bound. In any case, in investigating this idea, Scott found a new complexity class that he called YQP – Yoda Quantum Polynomial-Time (he decided there needed to be a complexity class beginning with Y – I think we need one beginning with a letter that has an umlaut). In any case, $BQP \subseteq YQP \subseteq QMA \cap BQP/Poly$. Scott also made the point that this stuff is a little bit like cooking – combining a lot of ingredients and sometimes finding new ones to make something interesting. His main tool was something known as the Majority-Certificates Lemma which relates to boosting in computational learning theory.
More to come this afternoon…