But was a √N running time achievable? Until last week, we knew of no quantum algorithm that did even slightly better than the classical bound of N 0.753.Īnd now it’s time to eat some crow: I didn’t believe there was such a quantum algorithm. Then, in 1995, Santha showed that it was optimal even for randomized algorithms with error.Īlright, 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 √N of the N leaf vertices. (Here 0.753 ≈ log 2(1+√33)-2.) On the other hand, they also showed that this running time was optimal for randomized algorithms with no error. Then you don’t care what happens if you make any other move from that position.īased on this idea (which AI types call alpha-beta pruning), in 1986 Saks and Wigderson gave a randomized algorithm to find an optimal move in the ant game, after examining (on average) only N 0.753 of the N leaf vertices. For example, suppose that at some position where it’s your turn to move, you discover a move that always lets you win. It’s clear that you generally don’t have to examine all the positions. Then we want to know: how many board positions would a computer have to evaluate, in order to play the game perfectly? The boots and sugar cubes correspond to losing and winning board positions. The goal here is to model games of alternation like chess and go, abstracting away the details. 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? But more generally, we can imagine a tree d levels deep, with an arbitrary sequence of N=2 d boots and sugar cubes at the leaf vertices. In the above example, it’s not hard to see that you’re the one with a winning strategy. If the ant ends up at a sugar cube, you win the game if it ends up at a boot, your friend wins. 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. This solves a problem that I worked on as an undergrad nine years ago (!), and that many a tyro had unsuccessfully tackled since.Īlright, so suppose we’ve got this ant at the root of a complete binary tree: 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.įarhi, Goldstone, and Gutmann - the feared MIT trio - announced a quantum algorithm for evaluating NAND trees in O(√N) time.
0 kommentar(er)
