{"id":82,"date":"2006-04-30T21:32:00","date_gmt":"2006-04-30T21:32:00","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=82"},"modified":"2006-04-30T21:32:00","modified_gmt":"2006-04-30T21:32:00","slug":"one-down","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=82","title":{"rendered":"One down"},"content":{"rendered":"

Last summer I posed Ten Semi-Grand Challenges for Quantum Computing Theory<\/a>. Today I’m pleased to report that (part of) one of my challenges has been “solved” — where, as always in this business, the word “solved” is defined broadly so as to include “proven to be not really worth working on, since a solution to it would imply a solution to something else that most of us gave up on years ago.”<\/p>\n

Challenge 10 involved finding a polynomial-time quantum algorithm to PAC-learn neural networks (that is, the class TC0<\/sup><\/a> of polynomial-size, constant-depth threshold circuits). In a new ECCC preprint<\/a>, Adam Klivans and Alex Sherstov show that, if there’s a fast quantum algorithm to learn even depth-2 neural nets, then there’s also a fast quantum algorithm for the ~n1.5<\/sup>-approximate shortest vector problem. Embarrassingly for me, once you have the idea — to use Oded Regev’s lattice-based public key cryptosystems — the quantum hardness of learning (say) depth 4 or 5 neural nets is immediate, while getting down to depth 2 takes another page. This is one of those results that hangs in the wonderful balance between “you could’ve thought of that” and “nyah nyah, you didn’t.”<\/p>\n

Feel free to post your own challenges in the comments section. But please, no “spouter challenges” like “where does the power of quantum computing come from?” or “is there a deeper theoretical framework for quantum algorithms?” In general, if you’re going to pose a scientific challenge, you should (1) indicate some technical problem whose solution would clearly represent progress, and (2) be willing to place at least 25% odds on such progress being made within five years. Or if you’re not a gambler, pick technical problems that you yourself intend to solve — that’s the approach I took with Semi-Grand Challenges 4 and 7.<\/p>\n

Theoretical computer science is often disheartening: there are so many open problems, and a week later they’re all still open, and a week after that, they’re all still open. Wait a year, though, or five years, or twenty, and some grad student will have had the insight that’s eluded everyone else: that the problem can’t be solved with any existing technique, unless Blum integers are factorable in 2n^\u03b5<\/sup> time for all \u03b5>0.<\/p>\n","protected":false},"excerpt":{"rendered":"

Last summer I posed Ten Semi-Grand Challenges for Quantum Computing Theory. Today I’m pleased to report that (part of) one of my challenges has been “solved” — where, as always in this business, the word “solved” is defined broadly so as to include “proven to be not really worth working on, since a solution to […]<\/p>\n","protected":false},"author":2,"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-82","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\/82","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\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=82"}],"version-history":[{"count":0,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/82\/revisions"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=82"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=82"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=82"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}