{"id":2109,"date":"2014-12-26T01:03:20","date_gmt":"2014-12-26T06:03:20","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=2109"},"modified":"2016-12-11T22:44:31","modified_gmt":"2016-12-12T03:44:31","slug":"quantum-complexity-theory-student-project-showcase-3","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=2109","title":{"rendered":"Quantum Complexity Theory Student Project Showcase 3"},"content":{"rendered":"<p>Merry Christmas (belatedly)! \u00a0This year Quanta Claus has brought us eight\u00a0fascinating final\u00a0project reports from students in my <a href=\"http:\/\/stellar.mit.edu\/S\/course\/6\/fa14\/6.845\/\">6.845 Quantum Complexity Theory<\/a> class, covering everything from interactive proofs to query and communication complexity to quantum algorithms to quantum gates (and one project even includes a web-based\u00a0demo you can try!). \u00a0Continuing in the tradition of the two <a href=\"https:\/\/scottaaronson.blog\/?p=515\">previous<\/a> <a href=\"https:\/\/scottaaronson.blog\/?p=1181\">showcases<\/a>, I&#8217;m sharing the reports here; some of these works might also be posted to the arXiv and\/or submitted to journals. \u00a0Thanks so much to the students who volunteered to participate in the showcase, and to <em>all<\/em> the students for making this such a great class.<\/p>\n<ul>\n<li><a href=\"http:\/\/www.scottaaronson.com\/showcase3\/booth-serena.pdf\">On Applications of the Equilibrium Value Method<\/a>, by Serena Booth. \u00a0A survey about Xiaodi Wu&#8217;s <a href=\"http:\/\/arxiv.org\/abs\/1004.0264\">simpler alternative approach<\/a> to proving QIP=PSPACE, and whether it might also yield a proof of QRG=RG=EXP.<\/li>\n<li><a href=\"http:\/\/www.scottaaronson.com\/showcase3\/dhariwal-prafulla-mayar-vinay.pdf\">Improved Quantum Query Complexity Bounds for Some Graph Problems<\/a>, by Prafulla Dhariwal and Vinay Mayar. \u00a0Building on Lin and Lin&#8217;s <a href=\"http:\/\/arxiv.org\/abs\/1410.0932\">striking recent work<\/a> on &#8220;Vaidman-bomb query complexity,&#8221; obtains some new results about the quantum query complexity of k-source shortest paths and minimum vertex cover in bipartite graphs.<\/li>\n<li><a href=\"http:\/\/www.scottaaronson.com\/showcase3\/epelbaum-daniel.pdf\">On Quantum Sieve Approaches to the Lattice Shortest Vector Problem<\/a>, by Daniel Epelbaum. \u00a0Surveys Greg Kuperberg&#8217;s <a href=\"http:\/\/arxiv.org\/abs\/quant-ph\/0302112\">subexponential-time quantum algorithm<\/a> for the dihedral Hidden Subgroup Problem, as well as Oded Regev&#8217;s <a href=\"http:\/\/arxiv.org\/abs\/cs\/0304005\">reduction<\/a> of the approximate shortest vector problem to dihedral HSP. \u00a0Discusses in detail why these two things, combined, do <em>not<\/em> yield a quantum algorithm for lattice problems that outperforms the best known classical algorithms.<\/li>\n<li><a href=\"http:\/\/www.scottaaronson.com\/showcase3\/kamath-pritish-vasudevan-prashant.pdf\">Approximate Degree of AND-OR Trees<\/a>, by Pritish Kamath and Prashant Vasudevan. \u00a0Discusses the wonderful open problem of proving that every AND-OR tree with N leaves, even a highly-unbalanced one, has approximate degree \u03a9(\u221aN) as a real polynomial. \u00a0(We know from <a href=\"http:\/\/arxiv.org\/abs\/1005.1601\">Reichardt&#8217;s seminal work<\/a> on quantum query complexity that the degree is O(\u221aN).) \u00a0Makes some partial progress on this conjecture&#8212;e.g., resolves it up to a polylog(N) factor for trees of constant depth.<\/li>\n<li><a href=\"http:\/\/www.scottaaronson.com\/showcase3\/koh-dax-liu-ziwen.pdf\">Infinite Separation of Quantum Information and Communication<\/a>, by Dax Koh and Zi-Wen Liu. \u00a0Wrings a further implication out of the <a href=\"http:\/\/arxiv.org\/abs\/1407.8217\">striking recent work<\/a> of Perry, Jain, and Oppenheim, about a communication task with infinite quantum\/classical separation (&#8220;infinite&#8221; meaning that one of them is O(1)&#8212;o(1) actually&#8212;and the other is \u03a9(N)).<\/li>\n<li><a href=\"http:\/\/www.scottaaronson.com\/showcase3\/rheingans-yoo-ross.pdf\">Taming Quantum Amplitudes with Gateset Limitations<\/a>, by Ross Rheingans-Yoo. \u00a0Surveys the issue of doubly-exponentially small probabilities for PostBQP circuits, which I covered recently <a href=\"https:\/\/scottaaronson.blog\/?p=2072\">on this blog<\/a> as well as <a href=\"http:\/\/mathoverflow.net\/questions\/187995\/massive-cancellations\">on MathOverflow<\/a>. \u00a0Takes an initial step toward resolving the problem of whether\u00a0\u03c0 and e are &#8220;tame&#8221; numbers, by using the concept of irrationality coefficients to show that a constant number of\u00a0gates with \u03c0- and e-like amplitudes can be tolerated in a PostBQP circuit.<\/li>\n<li><a href=\"http:\/\/www.scottaaronson.com\/showcase3\/voss-chelsea.pdf\">Tools for Quantum Circuit Synthesis<\/a>, by Chelsea Voss. \u00a0<span style=\"color: #ff0000;\"><a style=\"color: #ff0000;\" href=\"http:\/\/quantummechanic.xvm.mit.edu:8000\/\"><strong>Click here to try Chelsea&#8217;s software!<\/strong><\/a><\/span> \u00a0Discusses the creation of a web-based tool that lets you experiment with synthesizing\u00a0quantum circuits and observing\u00a0their behavior, and also gives you quantum-circuit-synthesis puzzles to solve.<\/li>\n<li><a href=\"http:\/\/www.scottaaronson.com\/showcase3\/xu-charles.pdf\">Complexity of the Quantum Separability Problem and Its Variants<\/a>, by Charles Xu. \u00a0Surveys the problem of deciding whether a quantum state described in various ways is separable or far from separable (and the use of that problem to characterize quantum interactive proof classes), concentrating on <a href=\"http:\/\/arxiv.org\/abs\/1308.5788\">recent work<\/a> by Gutoski, Hayden, Milner, and Wilde.<\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Merry Christmas (belatedly)! \u00a0This year Quanta Claus has brought us eight\u00a0fascinating final\u00a0project reports from students in my 6.845 Quantum Complexity Theory class, covering everything from interactive proofs to query and communication complexity to quantum algorithms to quantum gates (and one project even includes a web-based\u00a0demo you can try!). \u00a0Continuing in the tradition of the two [&hellip;]<\/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_hide_featured_image":false,"_jetpack_featured_image_duplicate_dismissed":0,"_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-2109","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\/2109","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=2109"}],"version-history":[{"count":1,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/2109\/revisions"}],"predecessor-version":[{"id":2110,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/2109\/revisions\/2110"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2109"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2109"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2109"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}