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?

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.

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.

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.

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.

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.