{"id":515,"date":"2011-01-17T19:32:06","date_gmt":"2011-01-18T00:32:06","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=515"},"modified":"2016-12-10T05:01:09","modified_gmt":"2016-12-10T10:01:09","slug":"quantum-complexity-theory-student-project-showcase","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=515","title":{"rendered":"Quantum Complexity Theory student project showcase!"},"content":{"rendered":"

This fall, for the second time, I taught my 6.845 Quantum Complexity Theory<\/a> graduate course (see here<\/a> for the lecture notes from the first iteration).\u00a0 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!<\/p>\n

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.\u00a0 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.\u00a0 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.\u00a0 So with the students’ kind permission, I decided to pick six outstanding projects for a “blog showcase.”\u00a0 (Obviously, inclusion in this showcase doesn’t preclude the projects being published “for real,” as I hope and expect they will be!)<\/p>\n

Without further ado:<\/p>\n

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

Paul Christiano<\/strong>, Toward Quantum Money Relative to a Classical Oracle<\/a>.\u00a0 In a Complexity’09 paper<\/a> (whose full version, alas, isn’t yet finished), I showed that there exists a “quantum oracle” relative to which quantum money<\/a>, which anyone can verify but no one can efficiently counterfeit, is possible.\u00a0 Here Paul takes the next step, giving a candidate quantum money scheme that only requires a classical<\/em> oracle.\u00a0 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.<\/p>\n

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

Shelby Kimmel<\/strong>, Quantum Adversary (Upper) Bound<\/a>.\u00a0 (Also on the arXiv<\/a>; two closely-related arXiv preprints are Speed from Repetition<\/a> by Shelby, and Super-Polynomial Quantum Speed-ups for Boolean Evaluation Trees with Hidden Structure<\/a> by Shelby along with Bohua Zhan and Avinatan Hassidim.)\u00a0 This work has to be read and understood to be believed—I too was skeptical at first!\u00a0 Basically, Shelby gives an example of a promise problem with a constant-query quantum algorithm—except she has no idea what the algorithm is!\u00a0 She can only prove its existence nonconstructively, by first giving a quantum algorithm for a composed<\/em> version of the problem, and then appealing to Ben Reichardt’s breakthrough characterization<\/a> of quantum query complexity in terms of span programs.\u00a0 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.<\/p>\n

Andy Lutomirski<\/strong>, On the Query Complexity of Counterfeiting Quantum Money<\/a>.\u00a0 Independently of Paul Christiano, here Andy proposes a different<\/em> quantum money scheme using a classical oracle, which again ought to work but is missing only a security proof.\u00a0 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.<\/p>\n

Raluca Ada Popa<\/strong>, Witness-Indistinguishability Against Quantum Adversaries<\/a>.\u00a0 Building on John Watrous’s work on quantum zero-knowledge, here Raluca defines the new notion of quantum witness-indistinguishability<\/em>, and proves many of its basic properties.\u00a0 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.\u00a0 As with so much else in cryptography, even just getting the definitions right is a nontrivial affair!<\/p>\n

<\/p>\n

<\/p>\n","protected":false},"excerpt":{"rendered":"

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).\u00a0 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 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"advanced_seo_description":"","jetpack_seo_html_title":"","jetpack_seo_noindex":false,"jetpack_seo_schema_type":"","_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_feature_clip_id":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"{title}\n\n{excerpt}\n\n{url}","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"_wpas_customize_per_network":false,"jetpack_post_was_ever_published":false},"categories":[5,4],"tags":[],"class_list":["post-515","post","type-post","status-publish","format-standard","hentry","category-complexity","category-quantum"],"jetpack_publicize_connections":[],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/515","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=515"}],"version-history":[{"count":4,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/515\/revisions"}],"predecessor-version":[{"id":3044,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/515\/revisions\/3044"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=515"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=515"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=515"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}