Qatalyst
Get Started

Ising Model

The Ising model originated from Physics as a model to describe magnetism, while a poor model for describing most magnets, it was soon discovered that it is a computationally very rich model. Finding the ground state of an Ising model is NP-Hard and mapping to many problems are known. Many quantum computers, including our Dirac-1 family of devices natively treat problems as Ising models.
Ising models are comprised of binary variables1 ZiZ_i which can take 11 or −1-1 values, by convention when mapping from a {0,1}\{0,1\} variable, 00 is mapped to 11 and 11 is mapped to −1-1. The optimality within an Ising model is expressed as energy with respect to an Ising Hamiltonian composed of linear and quadratic terms in Z. The Hamiltonian takes the form:
H=∑ijJijZiZj+∑ihiZi,H=\sum_{ij}J_{ij}Z_iZ_j+\sum_ih_iZ_i,
By convention, the optimal solution is defined as the one which minimises the energy, in other words which minimises the value of HH. Unlike a QUBO which is defined by a single matrix QQ, an Ising model with nn variables is defined by an n×nn \times n square matrix JJ and a vector hh of length nn. To reduce the number of variables passed, when submitting to a Dirac device, the hh vector is prepended to the JJ matrix and submitted as a (n+1)×n(n+1)\times n matrix.
The Dirac device natively treats the problem in an Ising format, and this may be an important consideration for dynamic range. The Ising model as expressive as the QUBO model, and in fact a simple translation exists in both directions, to transform a QUBO (E=∑ijQijxixjE=\sum_{ij}Q_{ij}x_ix_j) to an Ising model, one takes
xi→12(1−Zi),x_i\rightarrow\frac{1}{2}(1-Z_i),
and likewise a translation in the other direction takes the form
Zi→1−2xi.Z_i\rightarrow 1-2 x_i.
Translating in either direction leaves an irrelevant constant offset, which adds to all terms and thus does not change which collection of values corresponds to the optimum. It is worth noting that since both of these translations take linear terms to linear terms, a QUBO term will never translate to an Ising term with more than two ZZ elements, and likewise a quadratic Ising will translate into a QUBO which is by definition quadratic in xx.
It is natural to define Ising models with higher-than-quadratic terms
H=∑ihiZi+∑ijJijZiZj+∑ijkKijkZiZjZk...H=\sum_ih_iZ_i+\sum_{ij}J_{ij}Z_iZ_j+\sum_{ijk}K_{ijk}Z_iZ_jZ_k...
and while technically such terms can be expressed in terms of quadratic Ising models, this comes at the cost of introducting extra variables and it may be advantageous to implement these terms directly, this is a direction of furture research at QCI. Another extension is to higher than binary variables.
(1) Strictly speaking the definition is more complicated and physics-y, but this is a definition which works for our purposes. Technically the Hamiltonian is an operator and we are finding the state which minimises its exception value. Explaining all of these details would effectively amount to an introductory course in quantum physics, for this reason we instead treat ZiZ_i as variables rather than operators, which results in HH being a function of variables, rather than a quantum mechanical operator.