{"id":207,"date":"2007-02-23T00:07:25","date_gmt":"2007-02-23T08:07:25","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=207"},"modified":"2021-10-12T20:39:50","modified_gmt":"2021-10-13T01:39:50","slug":"nand-now-for-something-different","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=207","title":{"rendered":"NAND now for something completely different"},"content":{"rendered":"

There was a real<\/em> breakthrough in quantum algorithms last week — though you wouldn’t have known about it from reading Slashdot, Yahoo News, The Economist<\/em>, or (for that matter) this blog.<\/p>\n

Farhi, Goldstone, and Gutmann — the feared MIT trio — announced a quantum algorithm for evaluating NAND trees<\/a> in O(\u221aN) time. This solves a problem that I worked on as an undergrad nine years ago (!), and that many a tyro had unsuccessfully tackled since.<\/p>\n

Alright, so suppose we’ve got this ant at the root of a complete binary tree:<\/p>\n

<\/p>\n

You and your friend take turns moving the ant: first you can move it either down-and-left or down-and-right, then your friend can make the same choice, then you, etc. If the ant ends up at a sugar cube, you win the game; if it ends up at a boot, your friend wins. (Your friend is an exterminator.)<\/p>\n

In the above example, it’s not hard to see that you’re the one with a winning strategy. But more generally, we can imagine a tree d levels deep, with an arbitrary sequence of N=2d<\/sup> boots and sugar cubes at the leaf vertices. Then the question is: how many of the leaf vertices do you have to examine, in order to decide whether you or your friend has the win?<\/p>\n

The goal here is to model games of alternation<\/em> like chess and go, abstracting away the details. The boots and sugar cubes correspond to losing and winning board positions. Then we want to know: how many board positions would a computer have to evaluate, in order to play the game perfectly?<\/p>\n

It’s clear that you generally don’t have to examine all<\/em> the positions. For example, suppose that at some position where it’s your turn to move, you discover a move that always lets you win. Then you don’t care<\/em> what happens if you make any other move from that position.<\/p>\n

Based on this idea (which AI types call alpha-beta pruning<\/a>), in 1986 Saks and Wigderson<\/a> gave a randomized algorithm to find an optimal move in the ant game, after examining (on average) only N0.753<\/sup> of the N leaf vertices. (Here 0.753 \u2248 log2<\/sub>(1+\u221a33)-2.) On the other hand, they also showed that this running time was optimal for randomized algorithms with no error. Then, in 1995, Santha<\/a> showed that it was optimal even for randomized algorithms with error.<\/p>\n

Alright, but what about the quantum case? It was observed early on (by a simple reduction from the PARITY problem) that any quantum algorithm for playing the ant game would have to examine at least \u221aN of the N leaf vertices. But was a \u221aN running time achievable? Until last week, we knew of no quantum algorithm that did even slightly<\/em> better than the classical bound of N0.753<\/sup>.<\/p>\n

And now it’s time to eat some crow: I didn’t believe there was<\/em> such a quantum algorithm. I thought N0.753<\/sup> was optimal. In my defense, though, this was never really a very serious<\/em> belief, in contrast to (say) my belief that quantum computers can’t solve NP-complete problems in polynomial time. Really<\/em> I only claimed N0.753<\/sup> was optimal to try and goad people into proving me wrong. And today, I’m pleased to report that my strategy was successful.<\/p>\n

Last Wednesday, Farhi, Goldstone, and Gutmann put out a preprint<\/a> showing how to find an optimal move for the ant game in time O(\u221a(N log N)). However, their algorithm only worked in the “Hamiltonian oracle model,” a fanciful idealization preferred by physicists in which time is (get this) continuous rather than discrete. Two days later, Childs, Cleve, Jordan, and Yeung<\/a> showed how to port the algorithm to the ordinary discrete model, except that there the running time goes up to N1\/2+\u03b5<\/sup> for any \u03b5>0. Then, just yesterday, Farhi, Goldstone, and Gutmann improved the running time in the Hamiltonian oracle model to the optimal O(\u221aN). One hopes and expects that further improvements in the discrete model are forthcoming.<\/p>\n

Another obvious question is whether any<\/em> game tree can be evaluated in O(\u221aN) time, not just the complete binary tree used in the ant game. Since the complete binary tree was previously considered the “hardest” case, the natural conjecture would be yes.<\/p>\n

Years ago, David Deutsch gave an interview<\/a> in which he illustrated Grover’s algorithm using chess. I emailed Deutsch to point out that this was a bad example: at the time, we we had no idea how to get a Grover speedup for games of alternation with small branching factor. Deutsch dutifully posted a correction. Now I guess I’ll have to email him again, to tell him one can<\/em> get a “Grover” speedup for games like chess after all.<\/p>\n

I put “Grover” in quotes because, even though the Farhi-Goldstone-Gutmann algorithm achieves a square-root speedup, it doesn’t actually look anything like Grover’s algorithm. Instead it’s based on a quantum walk (reminiscent of this<\/a> paper), which is analyzed using tools from scattering theory. Apparently, physics occasionally does<\/em> come in handy for quantum computing.<\/p>\n

All in all, this business with NAND trees has only confirmed my core belief about theoretical computer science: that there are no miracles, except when there are.<\/p>\n","protected":false},"excerpt":{"rendered":"

There was a real breakthrough in quantum algorithms last week — though you wouldn’t have known about it from reading Slashdot, Yahoo News, The Economist, or (for that matter) this blog. Farhi, Goldstone, and Gutmann — the feared MIT trio — announced a quantum algorithm for evaluating NAND trees in O(\u221aN) time. This solves a […]<\/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_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-207","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\/207","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=207"}],"version-history":[{"count":1,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/207\/revisions"}],"predecessor-version":[{"id":5985,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/207\/revisions\/5985"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=207"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=207"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=207"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}