Quantum Complexity Theory student project showcase!
This 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!
Follow
Comment #1 January 18th, 2011 at 9:29 am
“I hope they enjoyed it half as much as I did!”
Exactly half?
Joking aside, this post makes me happy, as I’m a physicist who would like to safari a bit in your field. This certainly shows that the field is approachable. Also, congratulations to your students. I particularly liked the first and third submissions.
Comment #2 January 18th, 2011 at 9:32 am
Should be “I hope they enjoyed it _at least_ half as much as I did.” Unless you mean, at most half as much…
Comment #3 January 18th, 2011 at 10:01 am
Daemon and Sam: OK, clarified. 🙂
Comment #4 January 18th, 2011 at 12:07 pm
As long as they enjoyed it as much as Scott, asymptotically speaking.
Comment #5 January 18th, 2011 at 2:30 pm
“Kahler manifolds, STEM enterprise, etc” — Sidles 🙂
Comment #6 January 18th, 2011 at 7:44 pm
Just out of curiosity, was this year much different than last year’s version? If so, will the lecture notes for this iteration of the course be made available at any point? Thanks!
Comment #7 January 18th, 2011 at 8:26 pm
LOL … Vlad, the *best* thing to post (IMHO) is congratulations to all of Scott’s students for their fine work … and to express also our appreciation and thanks to Scott himself, for his hard work in teaching these students, and also, for taking the trouble to post so thoughtfully about his students’ work.
As for how quantum dynamics really works … well … Scott’s remarks on this subject at the recent TEDxCaltech Feynman’s Vision: the Next 50 Years were excellent. Hopefully all of the TEDxCaltech lectures will appear on youtube pretty soon … those that I was able to catch (about 1/4 of them) were plenty of fun. Good!
Comment #8 January 18th, 2011 at 8:52 pm
Jose: It was sufficiently close to the 2008 version that I didn’t bother to produce a new set of lecture notes.
Comment #9 January 19th, 2011 at 11:40 am
Scott, you suggest that you enjoyed teaching the class. But if given the choice to eschew teaching altogether and forever (but not any of your compensation!) would you elect to do so? Do you gain more from teaching than you would from devoting that time to quiet reflection and study?
Comment #10 January 19th, 2011 at 8:33 pm
Jack Rabbit: As it happens, I was lucky enough to have the choice of a non-teaching position, and I did turn it down in favor of a teaching one. Sure, teaching can be a pain—but if you don’t put yourself in regular contact with students who challenge and annoy you, then not only do you miss out on the daily feeling of accomplishment from imparting wisdom to the young’uns, but your own thinking becomes ossified and senility advances at least ten times faster. It’s a well-known phenomenon. Surely You’re Joking, Mr. Feynman contains probably the most eloquent exposition of it (in the context of Feynman’s explaining why he turned down a non-teaching position at IAS).
Comment #11 January 21st, 2011 at 10:58 pm
Quantum money… hmm. hopefully there is no Quantum inflation…
Comment #12 January 22nd, 2011 at 1:52 pm
(Off topic) Scott, have you seen http://arxiv.org/abs/1011.3944 ? Or indeed the related “story” on slashdot: http://science.slashdot.org/article.pl?sid=11/01/20/1546206 ?
Vladimir Romanov of Vladimir State University claims to have proved P = NP by demonstrating a polynomial time algorithm for 3-SAT.
Comment #13 January 23rd, 2011 at 11:22 am
A T: Yes, he emailed me. I sent him the following response:
I’ll pay attention when you send me the prime factors of the following RSA challenge number:
251959084756578934940271832400483985714292821262040
320277771378360436620207075955562640185258807844069
182906412495150821892985591491761845028084891200728
449926873928072877767359714183472702618963750149718
246911650776133798590957000973304597488084284017974
291006424586918171951187461215151726546322822168699
875491824224336372590851418654620435767984233871847
744479207399342365848238242811981638150106748104516
603773060562016196762561338441436038339044149526344
321901146575444541784240209246165157233507787077498
171257724679629263863563732899121548314381678998850
404453640235273819513786365643912120103971228221207
20357
Best,
Scott
Comment #14 January 23rd, 2011 at 1:48 pm
Supposed proofs of anything this hard are obviously highly unlikely to be correct. BUT: Vladimir appears to have his own State University, so he must be a big deal!
In any event, Vladimir is probably a little winded after the proof, so Scott ought to give him a couple weeks to deal with the software engineering issues of using his method to solve all the NP hard problems compiled in recent decades!
Comment #15 January 23rd, 2011 at 2:19 pm
LOL … say … uhhh … couldn’t Prof. Romanov reasonably issue exactly the same factoring challenge … to the *entire* quantum computing community? 🙂
`Cuz hey … aren’t the projections of the Quantum Information Science and Technology Roadmap (QIST-Roadmap) kind of … well … “Romonovian”? 🙂
For example, in the 2002 QIST Roadmap (LANL document #LA-UR-02-6900) we read:
Hmmmm … so how near *are* we, in 2011, to achieving Feynman’s dream? What are the obstructions in math, science, and engineering? What do we know today, that we didn’t know in 2002?
Scott, although I enjoyed your TEDxCalTech lecture Physics in the 21st Century: Toiling in Feynman’s Shadow very much, isn’t it the case, that both the TEDx lecture, and Shtetl Optimized itself, would reach a very much broader audience if they tackled these practical questions? As Feynman put it:
Opposite to Feynman’s Great Truth, we have Reinhard Selten’s (enormously simpler and cheaper!) Great Truth:
Hmmm … Scott, it would be *very* interesting to hear, from the students in your quantum complexity class, their reaction to the proposition “Quantum computing is for proving theorems, not for computing. The point is that many people (correctly?) perceive that quantum computing students nowadays are learning mainly in Selten-esque theorem-driven environments, rather than a Feynman-esque practicality-driven environments.
What might be especially interesting, useful, and fun for a broad span of QIT students … especially those students who hope for improving employment prospects … would be a thoroughgoing deconstruction of the QIST Roadmap, referenced to the gold standard of STEM roadmaps, namely the International Technology Roadmap for Semiconductors (ITRS-Roadmap).
Such an analysis would balance the Feynman and Selten points-of-view, and (hopefully) provide us with a more viable roadmap for the future of quantum computing.
Comment #16 January 24th, 2011 at 6:29 am
Raoul: Vladimir is a very old and famous city in Russia. Please educate yourself before getting embarrassed next time.
As for the “proof”, he uses only combinatorics and gives only 3 references to old textbooks (without counting one self-reference to an article in Russian), so nothing interesting here until he publishes a SAT solver that beats lots of hard benchmark instances.
Comment #17 January 25th, 2011 at 1:51 am
Yikes! Tough room.
Comment #18 January 25th, 2011 at 6:41 pm
Hi Scott,
Thanks for linking to your lectures, but I note that the “psets” are not available externally; is there any way to get them?
Comment #19 January 26th, 2011 at 11:54 am
Any chance there’s some video of your TEDxCaltech talk somewhere?
Sounds interesting!
Comment #20 January 26th, 2011 at 11:54 am
Noon: Sorry, I haven’t made those publicly available right now. But if people are interested, maybe I’ll set up a “home for retired quantum computing exercises.”
Comment #21 January 26th, 2011 at 2:24 pm
anon: For some reason, the videos aren’t up yet, but I’ll link to them from this blog as soon as they are!
Comment #22 January 26th, 2011 at 8:50 pm
Scott: That would be great; I am trying to “take” the course from afar, and it would be an added bonus to be able to do the assigned problems as well 🙂
Comment #23 January 27th, 2011 at 12:09 pm
On Dick Lipton’s and Ken Regan’s weblog Gödel’s Lost Letter and P=NP there’s presently a vigorous discussion of the topic “Is Factoring Really In BQP? Really?” As it turns out, plenty of people—even very senior and respected researchers—have expressed uncertainty regarding this topic.
Scott has offered to Dick and Ken’s readers the excellent advice (IMHO):
Taking Scott’s advice to heart, I have posed the question on MathOverflow (in a slightly generalized form) as Does BQP^P = BQP ? … and what proof machinery is available?.
It seems to me, that Dick and Ken are absolutely right that everyone benefits when questions like this are answered fully, and that Scott too is right, in reminding us that sites like MathOverFlow are a good place for such discussion … and so I would like to especially invite you, who are Scott’s students, to contribute to answering these questions.
Regarding the mathematical value of these questions, I have no special qualifications to judge .. but regarding their value in engineering and medicine, please let me assure you that good answers to these questions have very great significance.
So thank you Scott, both for teaching & encouraging these fine CS/CT/QIT students, and for your thoughtful suggestions regarding how best to pose these questions! 🙂
Comment #24 January 28th, 2011 at 9:16 am
As a followup to the above, and as a draft of a final answer to the MathOverFlow question “Does BQP^P = BQP ? … and what proof machinery is available?“, here is an engineering perspective on these matters.
Recent advances in automated proof-checking show us that the peer-review proof-checking system used by mathematicians works amazingly well … rigorously correct proofs have been found for every major theorem that has ever been seriously checked (dozens of them, according to Freek Wiedijk’s list). So it is highly unlikely that we will ever discover that quantum factoring is not in BQP, or more generally, that BQP^P is not the same complexity class as BQP.
None-the-less, it is worthwhile to work through the details, for a reason that has been mentioned in several Gödel’s Lost Letter and P=NP posts. Dick Lipton and Ken Regan have called it the “Flaming Arrow Reason.” A “flaming arrow” is a piece of proof machinery that causes the reader to exclaim “Are they allowed to do that?”
The machinery of complexity theory—especially quantum complexity theory—contains many flaming-arrow methods; this is why its conclusions often are received with skepticism. In particular, when we work through the (many!) steps in the reduction of BQP^P to BQP, we find that some steps in the reduction require EXP resources to carry through, or are infeasibly prolifigate in the number of logic gates, or (most unrealistically of all, in engineering eyes) blithely assume that no independent verification or validation of the reduction is needed.
By the rules of complexity theory, these “flaming arrows” are permitted, and once we accept that these arrows are admissible elements of the game, then we are reasonably assured—as assured as we ever can be, of any branch of mathematics—that the main results of both classical and quantum complexity theory are not only valid, but very beautiful.
From a practical point of view, though, some of the “flaming arrows” of complexity theory—particularly quantum complexity theory—have proved to be extraordinarily difficult to realize in working devices. This is a big part of the reason why the Quantum Information Science and Technology (QIST) Roadmaps of 2002 and 2004 have proved to be far too optimistic in the projected rates of progress: so much so, that serious doubts as to whether practical quantum computers can ever be built, have not (as yet) been laid to rest.
In summary, the Great Truths of quantum complexity theory seemingly stand in opposition to the Great Truths of quantum systems engineering. Quantum complexity theory teaches us that robust quantum computation is feasible (in theory) while P-bounded quantum simulation is infeasible … whereas quantum systems engineering teaches us the exact opposite Great Truth, namely, that robust quantum computation are infeasible (in practice) while P-bounded quantum simulation is eminently feasible.
It is greatly to our overall benefit, that once we appreciate that each of these disciplines embraces its own unique set of “flaming arrows,” and we learn how to condition our conclusions upon these “arrows,” then the apparent contradictions disappear. Only then we are ready to greatly accelerate the pace of understanding how quantum dynamical systems work, and applying this understanding in addressing the urgent challenges of the 21st century. Good!
For engineers, this tension among Great Truths is why complexity theory in general, and quantum complexity theory in particular, is such a wonderful field of study, and why we engineers are so grateful for weblogs like Shtetl Optimized and Gödel’s Lost Letter and P=NP. Long may these weblogs prosper, and innoculate our minds with Great Truths! 🙂
Comment #25 January 30th, 2011 at 5:00 pm
Hi Scott, can you comment on John Baez’s recent career change? Does he inspire you to devote at least part of your time and mental energies to tackling ‘practical’ problems whose solution might ‘change the world’?
Comment #26 February 2nd, 2011 at 2:58 pm
As a followup to Scott’s suggestion to post well-posed CS/CT/QIT questions on sites like MathOverflow, I have just posted “Do runtimes for P require EXP resources to upper-bound? … are concrete examples known?“.
It was a tough decision to post on MathOverflow rather than CS Theory. The most fun answer (it seems to me) would be a concrete example … the kind of concrete example that characteristically is given on MathOverflow. But if the answer turns out to be that (provably) no such hard-to-bound algorithms exist in P, then CS Theory should have been the host.
Oh well … as Dick Lipton would say … in either event, answers are *greatly* welcomed from CS cognoscenti of every persuasion.
Comment #27 February 18th, 2011 at 11:34 pm
Amadis: Sorry for the long delay in answering you!
Hi Scott, can you comment on John Baez’s recent career change?
He’s an inspiration to me in his new career, just as he was in his previous one.
Does he inspire you to devote at least part of your time and mental energies to tackling ‘practical’ problems whose solution might ‘change the world’?
I’ve always wanted to “tackle practical problems and change the world.” But outside of teaching, popularizing CS theory to high-school students and others, and raging against doofosity on this blog, I don’t think I’ve found the right area yet—a place where the (bizarre and unusual) skills that I happen to have would make a significant difference.
When nerdy academics try to influence politics, the results have often been counterproductive and borderline-horrifying, as in the case of Chomsky. Granted, I’m not a sophistic, genocide-minimizing loon like Chomsky is—just another left-moderate academic who thinks President Obama’s agenda sounds pretty good, and hopes it won’t be completely thwarted by the obstructionists in Congress or his own administration’s blunders. But that brings up a different problem: namely, how much do I have to say about climate change, renewable energy, nuclear proliferation, etc. etc. that’s at all original?
For years, I’ve daydreamed about helping start a school for gifted kids in math and science (though the term “gifted” is one I’ve never liked—I prefer to call them just nerds). Later in my career, I hope to try it if the opportunity arises. If someone could solve the problem of the repression and social ostracism of nerdy kids, that’s certainly one advance that would change the world.
Comment #28 December 22nd, 2012 at 8:47 pm
[…] 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, […]
Comment #29 December 26th, 2014 at 1:03 am
[…] one project 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 […]
Comment #30 December 22nd, 2015 at 8:52 pm
[…] from 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 #31 May 27th, 2016 at 6:00 pm
[…] chosen five student projects (in no particular order) for a blog showcase (impressed by similar sorts of showcases from Scott […]