cimod

Overview

cimod is a C++ library for a binary quadratic model. This library provides a binary quadratic model class which contains an Ising model or a quadratic unconstrained binary optimization (QUBO) model. It also provides utilities for constructing a model and transforming to some other interfaces. This library is created based on dimod (https://github.com/dwavesystems/dimod).

Binary quadratic model

A binary quadratic model class can contain an Ising model or a QUBO model.

Ising model

An energy of an Ising model \(E_{\mathrm{Ising}}\) is represented by

\[ E_{\mathrm{Ising}} = \sum_{i} h_i s_i + \sum_{i \neq j} J_{ij} s_i s_j + \delta_{\mathrm{Ising}}, \]

where \(s_i \in \{+1, -1\}\) denotes a spin at the site \(i\), \(h_i\) denotes an external magnetic field parameter, \(J_{ij}\) denotes an interaction parameter and \(\delta_{\mathrm{Ising}}\) denotes an offset. Note that this library assumes that the interaction is not symmetric, i.e., \(J_{ij} \neq J_{ji}\).

QUBO model

An evaluation function of a QUBO model \(E_{\mathrm{QUBO}}\) is represented by

\[ E_{\mathrm{QUBO}} = \sum_{i, j} Q_{ij} x_i x_j + \delta_{\mathrm{QUBO}}, \]

where \(x_i \in \{0, 1\}\) denotes a decision variable, \(Q_{ij}\) denotes a quadratic bias and \(\delta_{\mathrm{QUBO}}\) denotes an offset. Note that this library assumes that the quadratic bias is not symmetric, i.e., \(Q_{ij} \neq Q_{ji}\) if \(i \neq j\).

Binary polynomial model

A binary polynomial model, which can be regarded as an extended model of the binary quadratic model, can handle Ising and HUBO models.

Ising model

An energy of an "extended" Ising model \(E_{\mathrm{Ising}}\) is represented by

\[ E_{\mathrm{Ising}} = \sum_{i} h_i s_i + \sum_{i \neq j} J_{ij} s_i s_j + \sum_{i \neq j \neq k} J_{ijk} s_i s_j s_k + \ldots \]

Here \(s_i \in \{+1, -1\}\) denotes the spin at the site \(i\), \( h_i \) denotes the external magnetic field at the site \( i \), and \(J_{ijk\ldots}\) represents the interaction between the sites. Note that \( i \neq j \neq k \) means \( i \neq j \), \( j \neq k \), and \( i \neq k \). This library assumes that the interaction is not symmetric. For example, \(J_{ij} \neq J_{ji}\) for \( i\neq j\), \(J_{ijk} \neq J_{jik}\) for \( i \neq j \neq k \), and so on.

HUBO model

An energy of an "extended" QUBO model \( E_{\mathrm{HUBO}}\), here we call polynomial unconstrained binary optimization (HUBO), is represented by

\[ E_{\mathrm{HUBO}} = \sum_{i \neq j} Q_{ij} x_i x_j + \sum_{i \neq j \neq k} Q_{ijk} x_i x_j x_k + \ldots \]

Here \( x_i \in \{0, 1\} \) denotes the spin at the site \( i \) and \(Q_{ijk\ldots}\) represents the interaction between the sites. Note that \( i \neq j \neq k \) means \( i \neq j \), \( j \neq k \), and \( i \neq k \). This library assumes that the interaction is not symmetric. For example, \(Q_{ij} \neq Q_{ji}\) for \( i\neq j\), \(Q_{ijk} \neq Q_{jik}\) for \( i \neq j \neq k \), and so on.

Example

#include "../src/binary_quadratic_model.hpp"
#include "../src/binary_polynomial_model.hpp"
 
using namespace cimod;
 
int main() {
 
  // Set linear biases and quadratic biases
  Linear<uint32_t, double> linear{ {1, 1.0}, {2, 2.0}, {3, 3.0}, {4, 4.0} };
  Quadratic<uint32_t, double> quadratic {
       {std::make_pair(1, 2), 12.0}, {std::make_pair(1, 3), 13.0}, {std::make_pair(1, 4), 14.0},
       {std::make_pair(2, 3), 23.0}, {std::make_pair(2, 4), 24.0},
       {std::make_pair(3, 4), 34.0}
   };
 
  // Set variable type
  Vartype vartype = Vartype::BINARY;
 
  // Set offset
  double offset = 0.0;
 
  // Create a BinaryQuadraticModel instance
  BinaryQuadraticModel<uint32_t, double> bqm(linear, quadratic, offset, vartype);
 
  // Print informations of bqm
  bqm.print();
 
  //Set polynomial biases
  Polynomial<uint32_t, double> polynomial {
     //Linear biases
     {{1}, 1.0}, {{2}, 2.0}, {{3}, 3.0},
     //Quadratic biases
     {{1, 2}, 12.0}, {{1, 3}, 13.0}, {{2, 3}, 23.0},
     //Polynomial bias
     {{1, 2, 3}, 123.0}
  };
 
  // Create a BinaryPolynominalModel instance
  BinaryPolynomialModel<uint32_t, double> bpm(polynomial, vartype);
 
  // Print informations of bpm
  bpm.print();
 
  return 0;
}