Quantum Complexity Theory Student Project Showcase 2!
(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:
Follow
Comment #1 December 23rd, 2012 at 2:20 am
[…] (Dec2012): The Aaronson-Arkhipov paper have led to several exciting experimental works. See this post over the […]
Comment #2 December 23rd, 2012 at 7:45 am
Dear Scott,
these are great projects! How long did the students have to make them? It’s impressive they could do it just as a final project for a class.
In another unrelated topic, do you know the new blog on quantum computation:
http://schroedingersrat.blogspot.com.br/ ?
I think the Shtetl should watch his back, as it might loose all the polemic and heated debates to the Rat!
Comment #3 December 23rd, 2012 at 9:38 am
Rat’s reader #2: The students had little under two months to do these projects. Crazy, right?
Thanks for the link — I hadn’t seen that blog! I chuckled a few times reading it; the total lack of concern about things you say online coming back to bite you later did remind me a little of the early days of Shtetl-Optimized. (Though I don’t think I’d ever describe a legitimate research paper as “a piece of shit,” even if I thought it was overhyped. I thought that “did she [the author] turn you down again?” was a perfectly justified response.) Anyway, I’m more than happy to turn this sort of discussion over to Schödinger’s Rat — please, have at it over there! 🙂
Comment #4 December 24th, 2012 at 10:06 am
Fantastic! Is this something that is likely to run for many years? If so, maybe think about collecting them all in one place. Over the years it would make quite an interesting compendium.
Comment #5 December 24th, 2012 at 1:27 pm
I tried reading Falk’s paper but found it was not self contained. What’s up with that!?
Happy Holidays Scott!
-B
Comment #6 December 24th, 2012 at 1:31 pm
and also, what’s a good place to read about Grover’s algorithm, other than his paper? -B
Comment #7 December 24th, 2012 at 1:31 pm
Joe: Yes! I’ve been teaching this course at MIT every other year since I started, and I plan to continue doing so (assuming minor details like my getting tenure). And I’ll continue doing this showcase each time. You’re right, maybe I should make it cumulative.
Comment #8 December 24th, 2012 at 2:58 pm
Bob: Happy Holidays to you too. Yes, some of the project reports do require some background to understand: for Matt’s, for example, not only would you want to learn Grover’s algorithm first, you’d also want to read up on the quantum spatial search problem (e.g., my paper with Ambainis, and the subsequent papers on quantum walk algorithms). That’s just an inevitable consequence of trying to do something new, as Matt is.
Regarding Grover’s algorithm, there are tons of decent expositions on the web: Wikipedia, Umesh Vazirani’s lecture notes, my lecture notes are a few places to start, and Google will give you plenty more.
Comment #9 December 25th, 2012 at 11:57 pm
Impressive roaster, want to second Joe F’s suggestion making this cumulative would be great (maybe using something like F’Books timeline – e.g. without actually having a F’book account you can nevertheless set up a page there, and I found the t-line feature is actually quite handy to keep track of posts – other than that I stay away from that time and privacy sucking site).
Comment #10 December 26th, 2012 at 12:06 am
Forgot the http in my earlier comment. Anyhow, a much prettier example than FB’s poor man’s design would be something custom build with this jquery plug-in.
Would be much more appropriate for such shiny, high caliber projects.
Comment #11 December 26th, 2012 at 12:09 am
What is it with my inability to produce links today? Too much eggnog?
Comment #12 December 26th, 2012 at 10:59 pm
Are the students planning on uploading some of these to the arXiv?
Comment #13 December 27th, 2012 at 8:44 am
Noon #12: Yes, I’ve encouraged them to, and I believe some will.
Comment #14 December 28th, 2012 at 2:25 am
Will the next installment be called ““Quantum Complexity Theory Student Project Showcase 3!!”?
Comment #15 December 28th, 2012 at 10:30 am
The BQC one is really good, but it gives an incorrect history. According to it, we took observations from the ABE paper to turn them into a complete protocol, but this is incorrect. In fact, our original protocol predates the ABE paper (ours appeared on the arxiv several months before the ABE paper), but was published after their preprint appeared. As I understand it their work was independent of ours.
Comment #16 December 28th, 2012 at 11:14 am
Joe: Thanks for catching that! I confess I hadn’t even noticed that in the paper; otherwise I would’ve said something to Charles.
Comment #17 December 28th, 2012 at 11:58 am
I feel embarrassed for mentioning it, but I didn’t want to say nothing either.
Comment #18 December 28th, 2012 at 12:12 pm
Scott,
are you part of the new “online lectures are awesome” revolution at MIT and other universities? If so, where can I find your lectures? I want to put together a quantum computing 101 web site where I can start collecting basic material and gradually build up to advanced lectures and notes.
Thanks for the pointers to papers and lecture notes.
-B
Comment #19 December 28th, 2012 at 7:06 pm
Bob #18: I’ve always put my lecture notes online; you can find all them linked to from scottaaronson.com. But no, I haven’t yet taught a course through MIT’s MITx/EdX initiative (or coursera or Udacity).
Several other theoretical computer scientists have done MOOCs, including Umesh Vazirani and Ryan Williams. I expect that their offerings were phenomenal, and indeed that they already cover a non-negligible fraction of what I’d want to cover.
For me, the issues are that
(1) I don’t have time,
(2) MITx is still getting its act together, and has a long waitlist for faculty interested in doing online courses, and
(3) even if I had time, and even if MITx were ready, I’d still need to think a great deal about the questions of how to adapt my teaching style to the format of 7-minute “chunks” (which doesn’t fit it well at all), how to do automatic grading, and how to maintain the course.
Despite all these issues, it’s possible that I’ll do 6.045x (i.e., an online version of my undergrad computability & complexity course) in, say, Spring of 2014.
Comment #20 December 31st, 2012 at 1:31 pm
[…] but this feels more like a homework assignment for a graduate course. Wait, I take that back: Scott’s students’ homework is much more interesting and […]
Comment #21 January 8th, 2013 at 12:51 pm
I just finished reading the Quantum POMDP paper; it is very impressive. However, I have one minor quibble. In the definition of QOMDPs, Ms. Barry allows for an arbitrary reward function $R: S x \cal{A} \rightarrow \mathbb{R}$. I do not think that is allowable; specifically, such a function is not an observable. (Yes, I know you are not actually told the reward you are to receive; nonetheless, if it exists, at some point you are performing measurements that do not commute with your superoperators.) I think in order for this to make sense, your reward functions should be restricted to the domain $\cal{A} x \Omega$.
Comment #22 December 23rd, 2015 at 4:30 pm
[…] my graduate class. (For the previous project showcases from Quantum Complexity Theory, see here, here, and here. Also see here for the showcase from Philosophy and Theoretical Computer […]
Comment #23 December 11th, 2016 at 10:44 pm
[…] even includes a web-based demo you can try!). Continuing in the tradition of the two previous showcases, I’m sharing the reports here; some of these works might also be posted to the arXiv and/or […]