Skip to 0 minutes and 4 secondsGame-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?

Skip to 0 minutes and 54 secondsHow 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?

Generalized search

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.

Share this video:

This video is from the free online course:

Understanding Quantum Computers

Keio University