### Quantum Complexity Theory student project showcase!

Monday, January 17th, 2011This fall, for the second time, I taught my 6.845 Quantum Complexity Theory graduate course (see here for the lecture notes from the first iteration). Thanks so much to the students for making the course a success—I hope they enjoyed it at least half as much as I did!

A central part of 6.845 is the course project, which can be either a literature survey or original research in quantum complexity, and which can be done either individually or in pairs. The majority of the students chose to do original research—which surprised me, given how little time was available and how inherently unpredictable theorizing is. Yet all the projects ended up being good, and some ended up being spectacular—initiating new topics, making progress on open problems that I’d worked on without success, etc. So with the students’ kind permission, I decided to pick six outstanding projects for a “blog showcase.” (Obviously, inclusion in this showcase doesn’t preclude the projects being published “for real,” as I hope and expect they will be!)

Without further ado:

**Alessandro Chiesa and Michael Forbes**, A Note on QMA With Multiple Provers. Here Ale and Michael improve previous QMA(k) protocols for NP-complete problems due to Aaronson-Beigi-Drucker-Fefferman-Shor and Beigi—boosting the success probability by polynomial factors and showing how to verify a much wider range of problems than just 3SAT and 3-Coloring.

**Paul Christiano**, Toward Quantum Money Relative to a Classical Oracle. In a Complexity’09 paper (whose full version, alas, isn’t yet finished), I showed that there exists a “quantum oracle” relative to which quantum money, which anyone can verify but no one can efficiently counterfeit, is possible. Here Paul takes the next step, giving a candidate quantum money scheme that only requires a *classical* oracle. Unfortunately, there’s still a gap in the security proof for this scheme, but I’m optimistic that with new ideas the gap can be filled.

**Alan Deckelbaum**, Quantum Correlated Equilibria in Classical Complete Information Games. In this innovative paper, Alan defines a new concept of *quantum correlated equilibria* in quantum game theory (see here for the definition of *classical* correlated equilibria, due to Aumann), and studies its basic properties. In particular, he proves the nontrivial result that there exist equilibria that can be realized using classical correlation, but that *can’t* be realized using pure-state entanglement without one or more players having incentive to deviate. See here for some independent related work by Shengyu Zhang.

**Shelby Kimmel**, Quantum Adversary (Upper) Bound. (Also on the arXiv; two closely-related arXiv preprints are Speed from Repetition by Shelby, and Super-Polynomial Quantum Speed-ups for Boolean Evaluation Trees with Hidden Structure by Shelby along with Bohua Zhan and Avinatan Hassidim.) This work has to be read and understood to be believed—I too was skeptical at first! Basically, Shelby gives an example of a promise problem with a constant-query quantum algorithm—except she has no idea what the algorithm is! She can only prove its existence nonconstructively, by first giving a quantum algorithm for a *composed* version of the problem, and then appealing to Ben Reichardt’s breakthrough characterization of quantum query complexity in terms of span programs. For a special case of the problem, she’s able to give an explicit O(1)-query quantum algorithm by using the Haar wavelet transform.

**Andy Lutomirski**, On the Query Complexity of Counterfeiting Quantum Money. Independently of Paul Christiano, here Andy proposes a *different* quantum money scheme using a classical oracle, which again ought to work but is missing only a security proof. Along the way, Andy also proposes a beautiful new query complexity problem—the “Separate Components Problem”—which cries out for a quantum lower bound, and might also lead to a classical oracle separation between QMA and QCMA.

**Raluca Ada Popa**, Witness-Indistinguishability Against Quantum Adversaries. Building on John Watrous’s work on quantum zero-knowledge, here Raluca defines the new notion of *quantum witness-indistinguishability*, and proves many of its basic properties. For example, she shows that if quantum computationally-concealing commitment schemes exist, then all of NP has witness-indistinguishable proofs that are computationally secure against quantum adversaries. As with so much else in cryptography, even just getting the definitions right is a nontrivial affair!