Philosophy

dwave-optimization and the Leap™ service’s quantum-classical hybrid nonlinear solver incorporate features and design principals from each of the following areas:

Quantum Optimization

Quantum computing has the potential to help solve some of the most complex technical, scientific, national defense, and commercial problems that organizations face.

A fundamental rule of physics is that everything tends to seek a minimum-energy state: objects slide down hills; hot things cool down. This behavior is also true in the world of quantum physics. Quantum annealing processors naturally return low-energy states. Quantum annealing uses quantum physics to find low-energy states and therefore the optimal or near-optimal combination of elements for a given problem.

To learn more about solving optimization problems with quantum computers, see Get Started with Quantum Computing.

(Mixed-Integer) Linear Programming

Much of the mathematical optimization done today is done with linear programming solvers and techniques.

Users familiar with linear programming techniques will find many concepts in dwave-optimization familiar: objective functions; continuous, linear, and binary variables; constraints; and feasible regions are all concepts found in linear programming.

However, unlike linear solvers, dwave-optimization allows nonlinear relationships among variables, constraints, and intermediate values such as the objective value.

Lists, Sets, and Other Combinatorial Variables

While many optimization problems can be expressed using only scalar variable types (continuous, integer, and binary), it is often beneficial to use combinatorial structures.

The following example contrasts a classic mixed integer linear programming (MILP) formulation using scalar variables with one that uses a list variable.

Example: Traveling Salesperson

The goal of the traveling salesperson problem (TSP) is, for a given a list of cities and distances between each pair of cities, to find the shortest possible route that visits each city exactly once and returns to the city of origin.

When restricted to scalar variables, a common mixed-integer linear programming formulation for solving a TSP with \(N\) cities uses \(N^2\) binary variables and \(2N\) constraints.

MILP formulation details

Let

\[\begin{split}x_{it} = \begin{cases} 1 \text{ if the salesperson is in city } i \text{ at time } t \\ 0 \text{ otherwise} \\ \end{cases}\end{split}\]

If \(d_{i,j}\) gives the distance from city \(i\) to city \(j\) then the objective is to minimize the total tour length

\[\sum_{st} \sum_{ij} x_{is} x_{jt} d_{ij}\]

subject to constraints that the salesperson cannot be in two cities at the same time, nor any city twice

\[\begin{split}\sum_i x_{it} = 1 \text{ } \forall t \\ \sum_t x_{it} = 1 \text{ } \forall i\end{split}\]

Note that the solution to this problem is defined by an ordered list of cities. For example, a three-city TSP has these possible solutions: (0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), and (2, 1, 0). Therefore, rather than working with scalars, you can define a list() variable as any permutation of the integers from \([0..N)\), significantly reducing the number of problem variables. Another advantage of this approach is that the problem is unconstrained!

Formulation with a list variable

Let \(x\) be a list variable of length \(N\) with \(x_t\) giving the city the salesperson visits at time \(t\).

If \(d_{i,j}\) gives the distance from city \(i\) to city \(j\) then the objective is to minimize the total tour length

\[\sum_t d_{x_t, x_{t+1}}\]

In the sum, let \(x_N = x_0\) for convenience.

See also

traveling_salesperson() A generator encoding this formulation.

Compare the MILP and the list formulations by the number of constraints and the size of their search space.

	MILP		Nonlinear
# of Cities	Variable Domain Size	# of Constraints	Variable Domain Size	# of Constraints
N	\(2^{N^2}\)	\(2N\)	\(N!\)	0
5	33554432	10	120	0
10	1267650600228229401496703205376	20	3628800	0

By using the list formulation, the search space is much smaller and the solver is more likely to find an optimal solution.

Tensor Programming

NumPy is the most popular scientific computing library in Python. The NumPy library contains data structures for multidimensional arrays. To learn more, see NumPy’s excellent introduction to arrays.

Working with arrays can be beneficial for readability and for performance. Consider calculating the dot product of two lists of numbers a and b. This can be accomplished in Python with

a = [...]
b = [...]
value = sum(u * v for u, v in zip(a, b))

But it is more readable and more performant when expressed with array operations

a = np.asarray([...])
b = np.asarray([...])

value = (a * b).sum()  # or even np.dot(a, b)

dwave-optimization can be thought of as a framework for symbolically encoding operations over multidimensional arrays. It therefore inherits much of its API from NumPy. With dwave-optimization the dot-product example can be expressed as

model = dwave.optimization.Model()

a = model.constant([...])
b = model.constant([...])

value = (a * b).sum()