Combinatorial optimization problems
Combinatorial hardness
The problems which our entropy quantum computing devices aim to solve are known as combinatorial optimization problems. These are a class of optimization problems that are hard specifically because there are many potential solutions but no apparent practical way to find the best solution. For such problems, it is easy to check the quality of a potential solution, but there are many potential solutions, such that checking them all would be unreasonable for large instances. In other words, there is a “combinatorial explosion” of potential solutions, and the space of potential ways to solve the problem grows very fast (what this means in detail is discussed here) with the number of variables. Mathematically speaking, such problems can be solved by enumeration; calculating the quality of each potential solution one at a time and comparing it to the best one that has been found previously. However, in practice, this could be infeasible because the number of possible solutions can easily exceed “large” numbers, like the number of atoms in the universe.
A very typical example of a combinatorial optimization problem is the traveling salesperson problem. In the simplest version of this problem, a salesperson must visit a number of cities , return to the city they started, and can do so in any order. The goal of this problem is to choose an order which minimizes the distance traveled. In this example, there are possible routes (since the starting point is fixed), and adding one more city would multiply the number of potential routes by . The factorial function which defines the number of cities explodes quickly, (in fact, faster than exponentially).
For four cities, there will only be potential routes (recall the starting city is fixed), and given a table of the distances between all of the cities, the best route could be calculated by hand. In fact, with the observation that a route will have the same length as one with the order exactly reversed, only three routes would need to be checked. For five cities, routes would need to be checked (using the observation that routes are equivalent to their reverse). This is doable by hand but tedious. For six cities routes would need to be checked, which is probably too many to do by hand, but easy on a computer.
However, we come to a point where a computer would simply take too long to enumerate every option. For cities millions of routes would have to be checked (doable), but for , over a billion times a billion would need to be checked (not feasible). At that point, there are additional mathematical tricks that could be used to find the optimal route without enumerating all of them. They instead use the mathematical structure of the problem to prove that potential solutions that haven’t been checked have to be less optimal than the one found. Such strategies (i.e. algorithms) are very interesting, but not the topic of this tutorial. It is widely believed (although not strictly proven) that no matter how clever a strategy is, the time to find the most optimal route will always blow up with the size of the problem (number of cities in the traveling salesperson setting). This is the famous conjecture, which is detailed and important enough for it to warrant its own page, available here.
It is worth emphasizing that a large solution space is a necessary, but not sufficient, condition for a combinatorial optimization problem to be hard, otherwise one could just check every possibility. There also has to not be any known efficient strategy to solve the problem. Some problems have an exponentially growing number of possible solutions, but there is an efficient way to find the optimal answer. A concrete example here is the shortest path problem, the simplest version is superficially similar to the traveling salesperson problem, but not every city needs to be visited, the shortest route just needs to be found from one city to another with no restrictions on what cities are visited (assuming not all cities are directly connected). While there are still a rapidly growing number of potential paths between two cities, there are famous algorithms that can solve this problem quickly. The difference here is the structure that exists in the shortest path problem is the smaller short paths between closer nodes can be built up to make short paths between more distant nodes, while the traveling salesperson cannot be efficiently broken down into smaller problems in such a way.
Approximate optimization
Assuming that the conjecture is true (as is widely believed), then for large enough problems, we won’t be able to practically find the most optimal solution. While this situation seems to suggest that combinatorial optimization is hopeless at large sizes, there is an important observation to make. A route for a traveling salesperson problem can still be useful without being the single most optimal route. A suboptimal route would be longer than strictly needed, but would still allow the salesperson to visit the necessary cities. A number of algorithms, like the Christofides Algorithm, have a determined upper limit on the sub-optimality of the approximate solution. The task becomes rather to find the best route possible by a deadline (i.e. before the salesperson starts the route). This is where hardware solvers like our entropy quantum computing devices could potentially shine, they search the complicated space of potential solutions quickly and efficiently, finding a better solution for the general case than competing methods in a practical amount of time.