Discrete Quadratic Models

The discrete quadratic model (DQM) is a polynomial over discrete variables, with all terms of degree two or less, where a discrete variable represents some collection of distinct values, such as {red, green, blue, yellow} or {3.2, 67}, which are called the variable’s cases.

A discrete quadratic model may be defined as

\[H(\bf{d}) = \sum_{i} a_i(\bf{d}_i) + \sum_{i,j} b_{i,j}(\bf{d}_i,\bf{d}_j) + c\]

where \(\bf{d}_i\) are the discrete variables, \(a_i()\) and \(b_{i,j}()\) are real-valued functions, and \(c\) is a constant (offset).

You can represent any DQM with an equivalent model over binary variables by replacing each discrete variable, \(\bf{d}_i\), with a vector of binary variables using one-hot encoding, where exactly one binary variable is True and all others are False: \(\sum_a x_{i,a} = 1 \quad \forall i\).

In particular, a discrete quadratic model for \(N\) discrete variables, \(\bf{d}_i\), each with \(n_i\) cases, is then defined by using a binary variable, \(x_{i,u}\), to indicate whether discrete variable \(\bf{d}_i\) is set to case \(u\). The objective function can be expressed by the equation:

\[E(\bf{x}) = \sum_{i=1}^N \sum_{u=1}^{n_i} a_{i,u} x_{i,u} + \sum_{i=1}^N \sum_{j=i+1}^N \sum_{u=1}^{n_i} \sum_{v=1}^{n_j} b_{i,j,u,v} x_{i,u} x_{j,v} + c\]

Both representations are equivalent over the feasible space; that is, the solutions that meet the one-hot-encoding constraints. The second representation ascribes energies both to the feasible space (satisfying constraints), and an infeasible space (violating constraints). The second representation is used by Ocean tools.

The dimod.DiscreteQuadraticModel class can contain this model and its methods provide convenient utilities for working with representations of a problem.

These models and their use in solving problems on the D-Wave system are described in the following documentation: