wp-plugin-hostgator domain was triggered too early. This is usually an indicator for some code in the plugin or theme running too early. Translations should be loaded at the init action or later. Please see Debugging in WordPress for more information. (This message was added in version 6.7.0.) in /home4/scienrds/scienceandnerds/wp-includes/functions.php on line 6114ol-scrapes domain was triggered too early. This is usually an indicator for some code in the plugin or theme running too early. Translations should be loaded at the init action or later. Please see Debugging in WordPress for more information. (This message was added in version 6.7.0.) in /home4/scienrds/scienceandnerds/wp-includes/functions.php on line 6114Source:https:\/\/www.quantamagazine.org\/to-move-fast-quantum-maze-solvers-must-forget-the-past-20230720\/#comments<\/a><\/br> Because the interference has to work out just right, not every computational task is amenable to a quantum speedup, and indeed researchers are still working out<\/a> where quantum algorithms can help, decades after quantum computing was first proposed. But they\u2019ve had some notable successes. In 1994, Peter Shor developed a quantum algorithm<\/a> for factoring large numbers \u2014 a task whose apparent difficulty for classical computers underlies much of modern cryptography. Shor\u2019s algorithm could rapidly factor numbers so large that all known classical algorithms would be practically useless.<\/p>\n In 1996, the computer scientist Lov Grover found a second potentially practical example: a quantum algorithm<\/a> for a very generic search problem, one akin to finding a single item hidden inside one of many identical boxes.<\/p>\n \u201cClassically, what you could do is just randomly try one and see if it\u2019s good, and then try again and see if it\u2019s good, and you keep on trying until you find a good element,\u201d Apers said. This approach takes time proportional to the number of boxes. Multiply that number by 100, and the search will be 100 times slower.<\/p>\n With a quantum algorithm, you can do better. Grover proved that if you set up a superposition of all the boxes, you can exploit interference to practically guarantee that the algorithm will select the right box at the end. The whole process takes time proportional to the square root of the number of boxes: Increasing that number by a factor of 100 only increases the runtime by a factor of 10.<\/p>\n Grover\u2019s algorithm was a remarkably simple illustration of the value of quantum superposition, but the speedup it achieved was relatively modest \u2014 tasks that were far beyond the reach of the best classical algorithms would also stump Grover\u2019s algorithm. Shor\u2019s factoring algorithm had offered a glimpse of a dramatic gulf between the capabilities of quantum and classical computers. Was there a variant of Grover\u2019s search problem that was like factoring \u2014 practically intractable for classical computers yet easy for quantum computers?<\/p>\n In the late 1990s, researchers began exploring this question by reformulating it as a question about graphs \u2014 networks of points, or nodes, connected by lines, called edges. Any search problem can be framed in the language of graph theory, with one node representing the starting point, another node representing the destination, and edges representing the possible choices at each step along the way<\/p>\n Grover\u2019s problem, for example, corresponds to searching a graph in which every node is connected to every other node (because you can open boxes in any order). Different classical algorithms for a given search problem amount to different strategies for exploring the corresponding graph one node at a time, while quantum algorithms can move along multiple edges in superposition.<\/p>\n In 2002, a team of computer scientists finally identified<\/a> a classically intractable search problem that a quantum algorithm could solve easily. They started with a simple graph called a tree, in which each node sprouts two edges leading to two more nodes, which each split into two more branches, and so on. Starting from a single \u201croot\u201d node, a tree graph branches many times before ending in a final layer of nodes called \u201cleaves.\u201d The team imagined taking two identical trees and \u201cwelding\u201d them together by positioning them with the leaves facing each other and then using a random process to connect each leaf on one tree to two leaves on the other. They then posed the following question: Starting at one root of the welded tree graph, can you find your way to the other?<\/p>\n Without a bird\u2019s-eye view of the graph, any classical algorithm that attempts to solve this search problem will get hopelessly lost after reaching the middle layers of the graph \u2014 all the edges look identical, and there\u2019s no way to distinguish those that point forward from those leading backward. An algorithm might stumble upon the exit node accidentally, but the average time it spends wandering around grows exponentially with the number of layers in the tree.<\/p>\n The authors of the 2002 paper proved that a simple quantum algorithm \u2014 a \u201cquantum walk\u201d that spreads through the graph evenly by taking many paths in superposition \u2014 can find its way to the exit much faster. That\u2019s because the symmetric layout of the welded tree graph leads to interference between paths that concentrates flow in the forward direction. The exit node is \u201clike a focus point of the algorithm,\u201d said Alexander Belov<\/a>, a computer scientist at the University of Latvia.<\/p>\n There\u2019s a good chance that this quantum walk algorithm converges on the exit in time that\u2019s merely proportional to the number of layers. That makes it exponentially faster than any classical algorithm \u2014 a speedup comparable to that of Shor\u2019s factoring algorithm. But the interference that causes the quantum speedup also wipes out all record of the paths the algorithm traverses on its way to the exit.<\/p>\n Researchers wondered if there was some way to get the best of both worlds \u2014 a fast algorithm that identifies a path from entrance to exit.<\/p>\n \u201cIf it\u2019s just the basic quantum walk that somehow finds the exit, that\u2019s not going to work,\u201d said Andrew Childs<\/a>, a computer scientist at the University of Maryland, College Park who co-authored the 2002 paper as a graduate student and worked with Coudron on the new result. \u201cBut maybe you could soup it up in some way.\u201d<\/p>\n Among the first to approach the problem was Ansis Rosmanis<\/a>, a computer scientist now at the Nagoya University Graduate School of Mathematics. In a 2010 paper, Rosmanis developed a class of algorithms<\/a> that he dubbed \u201cquantum snake walks,\u201d which supplement the standard quantum walk algorithm with a memory of where they\u2019ve been.<\/p>\n As the standard quantum walk algorithm flows through the graph, its next step depends solely on where it is currently \u2014 how it got there doesn\u2019t matter. In Rosmanis\u2019 snake walks, by contrast, you need to know the past to predict the future. Specifically, the evolution of the snake walk is determined by \u201csnakes,\u201d strings of adjacent nodes that the walk has previously passed through. There are many varieties of snake walks, differing among other respects in how the length of those snakes changes over the course of the walk.<\/p>\n Rosmanis showed that quantum snake walks using superpositions of multiple snakes could still exhibit helpful interference, despite remembering their trajectories, and that some snake walks could in principle find a path to the exit. But he couldn\u2019t find a specific snake walk algorithm that did so quickly, and he also couldn\u2019t prove that such an algorithm didn\u2019t exist. Snake walks, it seemed, were promising, but too slippery to pin down. Rosmanis\u2019 work was the last word on the path-finding problem for nearly a decade.<\/p>\n<\/div>\n <\/br><\/br><\/br><\/p>\n
\nTo Move Fast, Quantum Maze Solvers Must Forget the Past<\/br>
\n2023-07-21 21:58:22<\/br><\/p>\nBranching Out <\/strong><\/h2>\n
Souping It Up<\/strong><\/h2>\n