Skip main navigation

New offer! Get 30% off one whole year of Unlimited learning. Subscribe for just £249.99 £174.99. New subscribers only T&Cs apply

Find out more

Generalized search

In this video, Rodney Van Meter explains why Lov Grover's quantum search algorithm helps us solve problems like chess and go.
3.9
Game-playing programs, even in the field of classical computers, have evolved considerably, as evidenced by the rise of old Deep Blue in the 1990s, several current shogi programs, and recently Alpha Go. These games are hard because the number of possible games grows exponentially with the number of choices at each turn. If we apply quantum computers to these kinds of games, it seems that you’ll be able to find the most advantageous move by calculating all the possibilities. In fact, however, there are many unresolved issues. Search and optimization problems pervade our economy and society. How can a factory minimize the amount of raw material it uses?
53.9
How can a trip planner such as the mapping applications from major IT companies like Google and Apple pick the best route, given a start and end point and some constraints? In a lot of real-world problems, you know what the answer is, or at least what the answer looks like, but not how to get it. Chess is a good example. In chess, you move your pieces around until it is impossible for your opponent’s king to escape being captured. It’s pretty easy to see when you have checkmated your opponent, but it’s not easy to see the sequence of moves that takes you there.
91.7
The most straightforward way to figure out how to win is to test the entire set of possible moves you can make, followed by all of your opponent’s possible responses, and your replies, and so forth. This is called the brute force approach. How many candidate moves you have to consider at each step is called the branching factor, and each step is called a ply. In chess, white has twenty possible first moves, and black has twenty possible responses, so there are 20×20=400 possible combinations in the first two plies. This number grows exponentially. If there are b branches and you need to check k plies, then you have b^k total possibilities.
136.6
For complete chess games, that gives you maybe 10^120 possible sequences to test, far too many for a human or even a supercomputer to check individually. So, humans and computers both use heuristics to take a good guess at a possible solution, dramatically reducing the number of moves they have to test. This makes the computation possible, but it doesn’t guarantee that you’ll find the optimal solution. Heuristics also require that the problem have a certain amount of structure, so that you can guide your choices toward a good, if not perfect, answer.
173.4
In chess, for example, capturing an opponent’s piece gives you an advantage, so it makes sense for a program to spend more time looking at cases where it’s likely that you will capture a piece, to see if they lead to a win. Grover’s algorithm is a quantum algorithm for searching these kinds of spaces. It gives you its best benefit on problems with no visible structure. If testing one possible solution tells you yes or no, but doesn’t give you any help in making a good choice for the next candidate to test, then it may be a good candidate for solving using Grover’s algorithm. The speedup using a quantum computer, however, isn’t as large as it is for factoring.
221.8
We only reduce the number of times we need to run our testing routine to the square root of the original number. For chess, then, instead of 10^120, we would have √(10^120 )=10^60, which is still too large a number to actually test. So, we have to be careful when picking problems to solve using Grover’s algorithm.

Computer scientist Lov Grover found a quantum algorithm, or perhaps more correctly an algorithmic framework, that allows quantum computing to be applied to almost any problem. It is commonly applied to search problems, where we are looking for a path across town or a trying to identify an input value for a function that will give us a particular output value. Small-data problems with high branching factors, like solving chess, shogi or go, are good candidates.

汎用検索

計算機科学者である、Lov Grover は、量子計算をほとんど全ての問題に応用できる、ある量子アルゴリズム(より正確にはアルゴリズムの枠組み)を発見しました。通常はある入力に応じて、特定の道順を出力する、探索問題に応用されます。チェス、将棋、囲碁といった、高い負荷分散を必要とする小規模データの問題がその一例です。

This article is from the free online

Understanding Quantum Computers

Created by
FutureLearn - Learning For Life

Reach your personal and professional goals

Unlock access to hundreds of expert online courses and degrees from top universities and educators to gain accredited qualifications and professional CV-building certificates.

Join over 18 million learners to launch, switch or build upon your career, all at your own pace, across a wide range of topic areas.

Start Learning now