### Quantum Complexity Theory Student Project Showcase 2!

Saturday, December 22nd, 2012*(Note: The “2!” in the title of this post really does mean “2 factorial,” if you want it to.)*

With the end of the semester upon us, it’s time for a once-every-two-year tradition: showcasing student projects from my 6.845 Quantum Complexity Theory graduate course at MIT. For my previous showcase, in 2010, I chose six projects that I thought were especially outstanding. This year, however, there were so many great projects—and so many, in particular, that could actually be *useful* to people in quantum computing—that I decided simply to open up the showcase to the whole class. I had 17 takers; their project reports and 10-minute presentation slides are below.

Let me mention a few projects that tried to do something new and audacious. Jenny Barry generalizes the notion of Partially Observable Markov Decision Processes (POMDPs) to the quantum case, and uses a recent result of Eisert et al., showing that certain problems in quantum measurement theory are undecidable (like, literally *Turing-undecidable*), to show that goal state reachability for “QOMDPs” is also Turing-undecidable (despite being decidable for classical POMDPs). Matt Falk suggests a novel quantum algorithm for spatial search on the 2D grid, and gives some numerical evidence that the algorithm finds a marked item in O(√n) time (which, if true, would be the optimal bound, beating the previous runtime of O(√(n log n))). Matt Coudron and Henry Yuen set out to prove that the Vazirani-Vidick protocol for quantum randomness expansion is optimal, and achieve some interesting partial results. Mohammad Bavarian (well, jointly with me) asks whether there’s a fast quantum algorithm for PARITY that gets the right answer on just *slightly* more than 50% of the inputs—and shows, rather surprisingly, that this question is closely related to some of the hardest open problems about Boolean functions, like sensitivity versus block sensitivity.

This year, though, I also want to call special attention to the *survey* projects, since some of them resulted in review articles that could be of real use to students and researchers in quantum computing theory. Notably, Adam Bookatz compiled the first list of essentially all known QMA-complete problems, analogous to (but shorter than!) Garey and Johnson’s listing of known NP-complete problems in 1979. Chris Graves surveyed the known quantum fault-tolerance bounds. Finally, three projects took on the task of understanding and explaining some of the most important recent results in quantum complexity theory: Travis Hance on Thomas Vidick and Tsuyoshi Ito’s NEXP in MIP* breakthrough; Emily Stark on Mark Zhandry’s phenomenal results on the security of classical cryptographic constructions against quantum attack; and Max Zimet on Jordan-Lee-Preskill’s major work on simulation of quantum field theories.

(Oops, sorry … did I use words like “important,” “breakthrough,” and “phenomenal” too often in that last sentence, thereby triggering the wrath of the theoretical computer science excitement police? Well then, come over to my apartment and friggin’ arrest me.)

Anyway, thanks so much to all the students for making 6.845 such an awesome class (at least on my end)! Without further ado, here’s the complete project showcase: