Atoms Versus Bits

If you are familiar with linear programming representations of these problems, or more specifically, Quadratic Unconstrained Binary Optimization (QUBO) methods, you may have noticed that atoms are not bits. In most QUBO formulations, individual states are represented by a series of bits and often one sees this as an array - the ubiquitous \(x_{ij}\) variables representing bits in a two dimensional array for example.

Let's take a brief conceptual walk from bits to atoms as this should shed some light on solving multivariable and combinatorial problems, integer linear programming, QUBO and even quantum computation to some degree.

Note that in all the following examples, there are many alternatives, details, and possible arguments around formulation that are ignored at the expense of keeping the concepts simple and specifically focused on Amazolve underpinnings. There are a ton of other resources for learning about any and all of these concepts in greater deatil.

TSP With QUBO

Given a traveling salesperson problem (TSP) where the salesperson must visit six different locations and we wish to find the shortest path. Starting with the QUBO, or binary optimization method, we would typically create a two dimensional array where both the vertical and horizontal axes are the six locations - so a 6x6 array:

In each cell of the array there is either a 1 or a 0 signfiying whether the path goes from the row's location to the column's location. The above array thus shows a path from 4 -> 1 -> 2 -> 3 -> 5 -> 0 -> 4, a circular path. Assuming there is function (called cost) which stores or calculates the distances from all locations to each other, then a simple objective function (to be minimized) would be:

\(C = \sum_{ij} x_{ij}cost(i,j)\)

Notes:

• Where there is a 1 in the array, the cost is included in the sum.
• Given a bit can have two states, 0 or 1, and there are \( 6 * 6 = 36 \) elements in the array, then the total number of possible combinations of states within the entire array is \( 2^{36} = 68,719,476,736\). Therefore, any solver algorithm must sift through over 68 billion possible combinations to find the best path.
• Several constraints are required for the QUBO array to work correctly. We must have constraints that mandate that there is only a single 1 in any column or row. Thus, at least two additional constraints must be defined (and calculated as part of solution evaluation).
• In addition to the aforementioned constraints, the objective function calculations increase exponentially based on the number of locations that must be visited.

Seems like a ton of work just to find the correct order of 6 locations!

TSP A Little Better

As you may realize, we don't need 6 bits (rows), to represent a single value from 0-5. In other words, we might think to only use 3 bits where those 3 bits are the binary represenation of locations 0-5. So, bits 000 would be location 0, and 011 would be location 3, on so on. Then, we could make the six columns simply the order in which the locations are visited. This would give us a array like the following:

Notes:

• This is not an actually feasible way to organize a solver atom array as the contraints would be rather strange, but the purpose is to show a reduction in solution space.
• Now that we have 3 rows and 6 columns, the number of possible combinations of bits in this array would be \( 2^{18} = 262,144\). Well that's an enormous improvement! We've taken the possible solution space from over 68 billion to "only" 262,144.

Still, seems like a lot of space to search just to find the order of 6 locations, and this formulation isn't very practical.

TSP On Atoms

Finally, we return to the atom array of the TSP problem:

Assuming again there is function (called cost) which stores or calculates the distances from all locations to each other, then a simple objective function (to be minimized) in this case would be:

\(C = \sum_{t}^{T-1} cost(a_{t},a_{t + 1})\)

Here's the same objective function in Amazolve:

{
  "constraint": {
    "CID": "O1",
    "sumIter": "iterVar",
    "exprFrom": "0",
    "exprTo": "T - 1",
    "iterVars": [ "t" ],
    "exprMain": "cost(At(t), At(t + 1))"
  }
}

Notes:

• One could argue that this is the same as the prior example, we're just not looking at the individual bits anymore. Well, precisely!
• Now, let's suppose that when we create an initial atom array, we specify that:
  • Each atom's location assignment is random and unique.
  • When searching the solution space, only reordering of the atoms is permitted.
• Given the atom array, and the search settings, we now have \( 6! = 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 720 \) possible combinations in the solution space.
• There are no constraints required for maintaining any uniqueness of "bits".
• The number of calculations in the objective function increases linearly (not exponentially) with the number of locations.

Thus, the atom array formulation now reduces the search space to just 720. From 68 billion, to 720!

Why Use Bits?

Great question. It becomes clear that representing the problem optimally can drastically reduce the amount of work the solver has to do in finding a solution. All of the above models will, and do work. In Amazolve, one can use the X() expression function, or the A() expression function - one referring to the bits, one to the atoms. In fact, they can be used within the same problem definition. The X() function just has an extra (technically unnecessary) dimension.

So why would one use bits versus atoms? This is a long answer but the short of it is that it all comes from linear programming (LP) and integer linear programming (ILP). The bit, or \(x_{ij}\), method is easy to translate to an ILP problem where each \(x_{ij}\) is a variable with a coefficient that then forms a tableau that is solved with some form of the simplex method. The problem is that many problems have variables that aren't linearly related. LP uses decimal values for variables and assumes some sort of linear relationship amongst them and the problem space in general. It can slice between variable values to find points within a theoretical simplex (shape) when it is searching for solutions.

ILP adds the requirement that the variables must be integers, not decimals. However, ILP simply relaxes the integer constraint, and will split decimal values (by rounding up or down) into round decimals to create branches within the LP simplex solving process. Thus, this method is called "branch and bound", but is still fundamentally LP.

If you have a scenario where states within the atom array correspond to something like a look-up table, or a distance function, for example, where there is no linear relationship that results from the variables to the output, then on significant sized problems, the LP and ILP methods generally perform no better than other methods.

LP/ILP in Amazolve?

Amazolve is designed such that whatever formulation you choose for the atom array, and however you write constraints within the problem file, future support for realizing (or rendering) the problem into LP and ILP will be available. Amazolve's problem definition syntax is designed to be materialized, or compiled, into many different solver algorithms available now (e.g., ILP, metaheuristic) and in the future (quantum computing).