What Is Optimization?

In an optimization problem, we search for the best of many possible combinations. Optimization problems include scheduling challenges, such as “Should I ship this package on this truck or the next one?” or “What is the most efficient route a traveling salesperson should take to visit different cities?”

Physics can help solve these sorts of problems because we can frame them as energy minimization problems. A fundamental rule of physics is that everything tends to seek a minimum energy state. Objects slide down hills; hot things cool down over time. This behavior is also true in the world of quantum physics. Quantum annealing simply uses quantum physics to find low-energy states of a problem and therefore the optimal or near-optimal combination of elements.

Examples of optimization tasks

Optimization tasks include the following:

• Finding the Maximum Independent Set: In a network, an "independent set" comprises nodes that are mutually disconnected from the others in the network. A "maximum independent set" is simply the largest possible independent set in the network. Finding a set of non-interacting drugs in a database is an example of this optimization task.
• Finding the Maximum Cut: A "cut" is a partition of a network into two subnetworks. Finding the "maximum cut" of the network means to find the cut that results in largest number of connections with an endpoint in each subnetwork. Evaluating communication network redundancy by finding the strongest set of interconnections is an example of this optimization task.
• Graph Coloring: The "graph coloring" problem is to assign colors to elements in a graph, subject to constraints. A common constraint is that no two adjacent elements may have the same color ("vertex coloring"). Coloring a map of the United States so than no two adjacent states have the same color is an example of this optimization task.