Qatalyst
Get Started

Integer models

In addition to the Ising and QUBO representations of problems, some of our Dirac devices are also able to treat integer problems. The basic quadratic integer optimization model takes linear and quadratic terms of integer variables Xi(m)∈{0,1,2,...m−1}X^{(m)}_i\in\{0,1,2,...m-1\}, often abbreviated as XiX_i the energy within an integer model is therefore defined as
E=∑ijJijXiXj+∑ihiXi.E=\sum_{ij}J_{ij}X_iX_j+\sum_ih_iX_i.
Where optimal solutions are those which minimize energy. QUBOs are a special case of an integer model where m=2m=2, although in this case the hh terms are redundant since Xi(2)Xi(2)=Xi(2)X^{(2)}_iX^{(2)}_i=X^{(2)}_i. For m>2m>2 however this is no longer true Xi(m>2)Xi(m>2)≠Xi(m>2)X^{(m>2)}_iX^{(m>2)}_i\neq X^{(m>2)}_i, so separate linear terms make the model more expressive.
While mm is fixed in our devices, it is possible to represent a variable of size q<mq<m by implementing the following quadratic constraint
λ(Xi+Xa,i−q+1)2,\lambda (X_i+X_{a,i}-q+1)^2,
if the constraint term λ\lambda is large (and positive) than this constraint will give a large positive contribution to the energy unless Xi+Xa,i=q−1X_i+X_{a,i}=q-1, since the minimum value of Xa,iX_{a,i} is 00, the maximum value of XiX_i which can avoid incurring a penalty is q−1q-1. Where q=2q=2 we recover a QUBO variable from a higher integer model.
Quadratic integer models are natural for expressing integer linear programming problems. The hih_i terms naturally. If we consider such a problem in its standard form (written element wise with matrix and vector multiplication expanded out and considering nn variables):
maximise ∑iciTXi\sum_i c_i^TX_i
subject to ∑iAikXi+sk=bk∀k∈1...n\sum_i A_{ik}X_i+s_k=b_k \quad \forall k \in 1...n
The first maximization can be converted to a minimization negating the elements of cTc^T, and as long as the elements of AA and bb are integers, constraints can be enforced by adding terms of the form
λ(∑iAikXi+∑jXs,j−bk)2\lambda (\sum_iA_{ik}X_i+\sum_jX_{s,j}-b_k)^2
where we ensure that enough Xs,jX_{s,j} slack variables are added to accommodate all possible XiX_i values.
As with Ising models, higher order terms are possible with integer models, for example objective functions of the form:
E=∑ihiXi+∑ijJijXiXj+∑ijkKijkXiXjXk...E=\sum_ih_iX_i+\sum_{ij}J_{ij}X_iX_j+\sum_{ijk}K_{ijk}X_iX_jX_k...
these capabilities are under development, and represent an exciting future direction for this technology.