Many introductory computer science programs will cover the traveling salesman problem as an example of an NP-hard problem that becomes too complex for a classical computer to solve when the number of cities involved gets too high. The problem is posed as follows: “Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city and returns to the origin city?” It turns out that the simplest algorithm to perform an exhaustive search for the best route will examine (n-1)!/2 possibilities where n is the total number of cities.
This problem is often mentioned as a good example of a case where a quantum computer can beat a classical computer in finding the best route a lot quicker. In fact, a paper was posted about this last year that showed a quadratic speedup in computation time with a quantum algorithm that was simulated in IBM’s quantum experience.
Although this problem is largely theoretical since sales people never seem to worry about minimizing their expenses, a real world example of this was recently described by BMW. Consider an automobile manufacturing line with a welding robot that welds seams on dozens of different spots of a car assembly as it goes by. In these situations every second of delay needs to be minimized in order to maximize productivity. And it is imperative to figure out the best order to perform the welds to minimize the robot’s travel time and achieve maximum throughput. It turns out that this is the same problem as the traveling salesman problem.
We had previously written how some smart companies are now creating small groups of researchers to look at problems within their companies and seeing how they might be solved on a future quantum computer. It is a process that some people are calling getting “quantum ready”. For more details on how BMW is doing this, you can view a recently article that they posted about their efforts here.