Binary Quadratic Model

namespace cimod

Typedefs

template<typename IndexType, typename FloatType>
using Linear = std::unordered_map<IndexType, FloatType>

Type alias for linear bias.

Template Parameters:

IndexType –

template<typename IndexType, typename FloatType>
using Quadratic = std::unordered_map<std::pair<IndexType, IndexType>, FloatType, pair_hash>

Type alias for quadratic bias.

Template Parameters:

IndexType –

template<typename IndexType, typename FloatType>
using Adjacency = std::unordered_map<IndexType, std::unordered_map<IndexType, FloatType>>

Type alias for adjacency list.

Template Parameters:

IndexType –

struct Dense

struct Sparse

template<typename IndexType, typename FloatType, typename DataType>
class BinaryQuadraticModel

Class for dense binary quadratic model.

Template Parameters:

• IndexType – index type. type must be hashable and comparable.

• FloatType –

• IndexType –

Public Types

using DenseMatrix = Eigen::Matrix<FloatType, Eigen::Dynamic, Eigen::Dynamic, Eigen::RowMajor>

Eigen Matrix if DataType is Dense , Matrix is equal to Eigen::Matrix if DataType is Sparse, Matrix is equal to Eigen::SparseMatrix.

using SparseMatrix = Eigen::SparseMatrix<FloatType, Eigen::RowMajor>

using SpIter = typename SparseMatrix::InnerIterator

using Matrix = std::conditional_t<std::is_same_v<DataType, Dense>, DenseMatrix, SparseMatrix>

using Vector = Eigen::Matrix<FloatType, Eigen::Dynamic, 1>

using json = nlohmann::json

Public Functions

inline BinaryQuadraticModel(const Linear<IndexType, FloatType> &linear, const Quadratic<IndexType, FloatType> &quadratic, const FloatType &offset, const Vartype vartype)

BinaryQuadraticModel constructor.

Parameters:

• linear –

• quadratic –

• offset –

• vartype –

inline BinaryQuadraticModel(const Linear<IndexType, FloatType> &linear, const Quadratic<IndexType, FloatType> &quadratic, const Vartype vartype)

BinaryQuadraticModel constructor.

Parameters:

• linear –

• quadratic –

• vartype –

inline BinaryQuadraticModel(const Eigen::Ref<const DenseMatrix> &mat, const std::vector<IndexType> &labels_vec, const FloatType &offset, const Vartype vartype, bool fix_format = true)

BinaryQuadraticModel constructor (with matrix);.

Parameters:

• mat –

• labels_vec –

• offset –

• vartype –

inline BinaryQuadraticModel(const Eigen::Ref<const DenseMatrix> &mat, const std::vector<IndexType> &labels_vec, const Vartype vartype, bool fix_format = true)

BinaryQuadraticModel constructor (with matrix);.

Parameters:

• mat –

• labels_vec –

• vartype –

inline BinaryQuadraticModel(const SparseMatrix &mat, const std::vector<IndexType> &labels_vec, const FloatType &offset, const Vartype vartype)

BinaryQuadraticModel constructor (with sparse matrix); this constructor is for developers.

Parameters:

• mat –

• labels_vec –

• offset –

• vartype –

inline BinaryQuadraticModel(const SparseMatrix &mat, const std::vector<IndexType> &labels_vec, const Vartype vartype)

BinaryQuadraticModel constructor (with sparse matrix); this constructor is for developers.

Parameters:

• mat –

• labels_vec –

• vartype –

BinaryQuadraticModel(const BinaryQuadraticModel&) = default

inline size_t get_num_variables() const

get the number of variables

Returns:

The number of variables.

inline size_t length() const

Return the number of variables.

Deprecated:

use get_num_variables instead.

Returns:

The number of variables.

inline bool contains(const IndexType &v) const

Return true if the variable contains v.

Parameters:

v –

Returns:

Return true if the variable contains v.

inline FloatType get_linear(IndexType label_i) const

Get the element of linear object.

Returns:

A linear bias.

inline Linear<IndexType, FloatType> get_linear() const

Get linear object.

Returns:

A linear object

inline FloatType get_quadratic(IndexType label_i, IndexType label_j) const

Get the element of quadratic object.

Returns:

A quadratic bias.

inline Quadratic<IndexType, FloatType> get_quadratic() const

Get uadratic object.

Returns:

A quadratic object.

inline FloatType get_offset() const

Get the offset.

Returns:

An offset.

inline Vartype get_vartype() const

Get the vartype object.

Returns:

Type of the model.

inline const std::vector<IndexType> &get_variables() const

Get variables.

Returns:

variables

inline BinaryQuadraticModel<IndexType, FloatType, DataType> empty(Vartype vartype)

Create an empty BinaryQuadraticModel.

Returns:

empty object

inline void add_variable(const IndexType &v, const FloatType &bias)

Add variable v and/or its bias to a binary quadratic model.

Parameters:

• v –

• bias –

inline void add_variables_from(const Linear<IndexType, FloatType> &linear)

Add variables and/or linear biases to a binary quadratic model.

Parameters:

linear –

inline void add_interaction(const IndexType &u, const IndexType &v, const FloatType &bias)

Add an interaction and/or quadratic bias to a binary quadratic model.

Parameters:

• u –

• v –

• bias –

inline void add_interactions_from(const Quadratic<IndexType, FloatType> &quadratic)

Add interactions and/or quadratic biases to a binary quadratic model.

Parameters:

quadratic –

inline void remove_variable(const IndexType &v)

Remove variable v and all its interactions from a binary quadratic model.

Parameters:

v –

inline void remove_variables_from(const std::vector<IndexType> &variables)

Remove specified variables and all of their interactions from a binary quadratic model.

Parameters:

variables –

inline void remove_interaction(const IndexType &u, const IndexType &v)

Remove interaction of variables u, v from a binary quadratic model.

Parameters:

• u –

• v –

inline void remove_interactions_from(const std::vector<std::pair<IndexType, IndexType>> &interactions)

Remove all specified interactions from the binary quadratic model.

Parameters:

interactions –

inline void add_offset(const FloatType &offset)

Add specified value to the offset of a binary quadratic model.

Parameters:

offset –

inline void remove_offset()

Set the binary quadratic model’s offset to zero.

inline void scale(const FloatType &scalar, const std::vector<IndexType> &ignored_variables = {}, const std::vector<std::pair<IndexType, IndexType>> &ignored_interactions = {}, const bool ignored_offset = false)

Multiply by the specified scalar all the biases and offset of a binary quadratic model.

Parameters:

• scalar –

• ignored_variables –

• ignored_interactions –

• ignored_offset –

inline void normalize(const std::pair<FloatType, FloatType> &bias_range = {1.0, 1.0}, const bool use_quadratic_range = false, const std::pair<FloatType, FloatType> &quadratic_range = {1.0, 1.0}, const std::vector<IndexType> &ignored_variables = {}, const std::vector<std::pair<IndexType, IndexType>> &ignored_interactions = {}, const bool ignored_offset = false)

Normalizes the biases of the binary quadratic model such that they fall in the provided range(s), and adjusts the offset appropriately.

Parameters:

• bias_range –

• use_quadratic_range –

• quadratic_range –

• ignored_variables –

• ignored_interactions –

• ignored_offset –

inline void fix_variable(const IndexType &v, const int32_t &value)

Fix the value of a variable and remove it from a binary quadratic model.

Parameters:

• v –

• value –

inline void fix_variables(const std::vector<std::pair<IndexType, int32_t>> &fixed)

Fix the value of the variables and remove it from a binary quadratic model.

Parameters:

fixed –

inline void flip_variable(const IndexType &v)

Flip variable v in a binary quadratic model.

Parameters:

v –

inline void change_vartype(const Vartype &vartype)

**

Create a binary quadratic model with the specified vartype. This function does not return any object.

Parameters:

vartype –

inline BinaryQuadraticModel<IndexType, FloatType, DataType> change_vartype(const Vartype &vartype, bool inplace)

Create a binary quadratic model with the specified vartype. This function generates and returns a new object.

Parameters:

• vartype –

• inplace – if set true, the current object is converted.

Returns:

created object

inline FloatType energy(const Sample<IndexType> &sample) const

Determine the energy of the specified sample of a binary quadratic model.

Parameters:

sample –

Returns:

An energy with respect to the sample.

inline std::vector<FloatType> energies(const std::vector<Sample<IndexType>> &samples_like) const

Determine the energies of the given samples.

Parameters:

samples_like –

Returns:

A vector including energies with respect to the samples.

inline std::tuple<Quadratic<IndexType, FloatType>, FloatType> to_qubo()

Convert a binary quadratic model to QUBO format.

Returns:

A tuple including a quadratic bias and an offset.

inline std::tuple<Linear<IndexType, FloatType>, Quadratic<IndexType, FloatType>, FloatType> to_ising()

Convert a binary quadratic model to Ising format.

Returns:

A tuple including a linear bias, a quadratic bias and an offset.

inline Matrix interaction_matrix() const

generate (Dense or Sparse) interaction matrix with given list of indices The generated matrix will be the following triangular matrix:

$$\begin{pmatrix} J_{0,0} & J_{0,1} & \cdots & J_{0,N-1} & h_{0}\\ 0 & J_{1,1} & \cdots & J_{1,N-1} & h_{1}\\ \vdots & \vdots & \vdots & \vdots & \vdots \\ 0 & 0 & \cdots & J_{N-1,N-1} & h_{N-1}\\ 0 & 0 & \cdots & 0 & 1 \\ \end{pmatrix}$$

Parameters:

indices –

Returns:

corresponding interaction matrix (Eigen)

template<typename T = DataType>
inline json to_serializable(dispatch_t<T, Dense> = nullptr) const

Convert the binary quadratic model to a dense-version serializable object.

Returns:

An object that can be serialized (nlohmann::json)

template<typename T = DataType>
inline json to_serializable(dispatch_t<T, Sparse> = nullptr) const

Convert the binary quadratic model to a serializable object.

Returns:

An object that can be serialized (nlohmann::json)

Public Static Functions

static inline BinaryQuadraticModel<IndexType, FloatType, DataType> from_qubo(const Quadratic<IndexType, FloatType> &Q, FloatType offset = 0.0)

Create a binary quadratic model from a QUBO model.

Parameters:

• Q –

• offset –

Returns:

Binary quadratic model with vartype set to .Vartype.BINARY.

static inline BinaryQuadraticModel<IndexType, FloatType, DataType> from_ising(const Linear<IndexType, FloatType> &linear, const Quadratic<IndexType, FloatType> &quadratic, FloatType offset = 0.0)

Create a binary quadratic model from an Ising problem.

Parameters:

• linear –

• quadratic –

• offset –

Returns:

Binary quadratic model with vartype set to .Vartype.SPIN.

template<typename IndexType_serial = IndexType, typename FloatType_serial = FloatType, typename T = DataType>
static inline BinaryQuadraticModel<IndexType_serial, FloatType_serial, DataType> from_serializable(const json &input, dispatch_t<T, Dense> = nullptr)

Create a BinaryQuadraticModel instance from a serializable object.

Template Parameters:

• IndexType_serial –

• FloatType_serial –

Parameters:

input –

Returns:

BinaryQuadraticModel<IndexType_serial, FloatType_serial>

template<typename IndexType_serial = IndexType, typename FloatType_serial = FloatType, typename T = DataType>
static inline BinaryQuadraticModel<IndexType_serial, FloatType_serial, DataType> from_serializable(const json &input, dispatch_t<T, Sparse> = nullptr)

Create a BinaryQuadraticModel instance from a serializable object.

Template Parameters:

• IndexType_serial –

• FloatType_serial –

Parameters:

input –

Returns:

BinaryQuadraticModel<IndexType_serial, FloatType_serial>

Protected Functions

inline void _set_label_to_idx()

set _label_to_idx from _idx_to_label

template<typename T = DataType>
inline FloatType &_quadmat_get(size_t i, size_t j, dispatch_t<T, Dense> = nullptr)

access elements for dense matrix

Template Parameters:

T –

Parameters:

• i –

• j –

• dispatch_t –

Returns:

template<typename T = DataType>
inline FloatType _quadmat_get(size_t i, size_t j, dispatch_t<T, Dense> = nullptr) const

access elements for dense matrix

Template Parameters:

T –

Parameters:

• i –

• j –

• dispatch_t –

Returns:

template<typename T = DataType>
inline FloatType &_quadmat_get(size_t i, size_t j, dispatch_t<T, Sparse> = nullptr)

access elements for sparse matrix

Template Parameters:

T –

Parameters:

• i –

• j –

• dispatch_t –

Returns:

template<typename T = DataType>
inline FloatType _quadmat_get(size_t i, size_t j, dispatch_t<T, Sparse> = nullptr) const

access elements for sparse matrix

Template Parameters:

T –

Parameters:

• i –

• j –

• dispatch_t –

Returns:

inline FloatType &_mat(IndexType label_i, IndexType label_j)

get reference of _quadmat(i,j)

Parameters:

• label_i –

• label_j –

Returns:

reference of _quadmat(i,j)

inline FloatType &_mat(IndexType label_i)

get reference of _quadmat(i,i)

Parameters:

label_i –

Returns:

reference of _quadmat(i,i)

inline FloatType _mat(IndexType label_i, IndexType label_j) const

get reference of _quadmat(i,j)

Parameters:

• label_i –

• label_j –

Returns:

reference of _quadmat(i,j)

inline FloatType _mat(IndexType label_i) const

get reference of _quadmat(i,i)

Parameters:

label_i –

Returns:

reference of _quadmat(i,i)

template<typename T = DataType>
inline FloatType _max_linear(dispatch_t<T, Dense> = nullptr) const

calculate maximum element in linear term for dense graph

Returns:

template<typename T = DataType>
inline FloatType _max_quadratic(dispatch_t<T, Dense> = nullptr) const

calculate maximum element in quadratic term for dense graph

Returns:

template<typename T = DataType>
inline FloatType _min_linear(dispatch_t<T, Dense> = nullptr) const

calculate minimum element in linear term for dense graph

Returns:

template<typename T = DataType>
inline FloatType _min_quadratic(dispatch_t<T, Dense> = nullptr) const

calculate minimum element in quadratic term for dense graph

Returns:

template<typename T = DataType>
inline FloatType _max_linear(dispatch_t<T, Sparse> = nullptr) const

calculate maximum element in linear term for dense graph

Returns:

template<typename T = DataType>
inline FloatType _max_quadratic(dispatch_t<T, Sparse> = nullptr) const

calculate maximum element in quadratic term for dense graph

Returns:

template<typename T = DataType>
inline FloatType _min_linear(dispatch_t<T, Sparse> = nullptr) const

calculate minimum element in linear term for dense graph

Returns:

template<typename T = DataType>
inline FloatType _min_quadratic(dispatch_t<T, Sparse> = nullptr) const

calculate minimum element in quadratic term for dense graph

Returns:

template<typename T = DataType>
inline void _insert_label_into_mat(IndexType label_i, dispatch_t<T, Dense> = nullptr)

insert row and column that corresponds to added label into _quadmat for dense matrix

Parameters:

label_i –

template<typename T = DataType>
inline void _insert_label_into_mat(IndexType label_i, dispatch_t<T, Sparse> = nullptr)

insert row and column that corresponds to added label into _quadmat for sparse matrix

Parameters:

label_i –

template<typename T = DataType>
inline void _delete_label_from_mat(IndexType label_i, dispatch_t<T, Dense> = nullptr)

delete row and column that corresponds to existing label from _quadmat for dense matrix

Parameters:

label_i –

template<typename T = DataType>
inline void _delete_label_from_mat(IndexType label_i, dispatch_t<T, Sparse> = nullptr)

delete row and column that corresponds to existing label from _quadmat for sparse matrix

Parameters:

label_i –

inline void _add_new_label(IndexType label_i)

add new label if label_i already exists, this process is skipped.

Parameters:

label_i –

inline void _delete_label(IndexType label_i, bool force_delete = true)

delete label if label_i does not exist, this process is skipped.

Parameters:

• label_i –

• force_delete – if true, delete label whenever there exists corresponding nonzero elements in the matrix. otherwise, delete label only if there are no corresponding nonzero elements in the matrix.

template<typename T = DataType>
inline void _initialize_quadmat(const Linear<IndexType, FloatType> &linear, const Quadratic<IndexType, FloatType> &quadratic, dispatch_t<T, Dense> = nullptr)

initialize matrix with linear and quadratic dicts (for dense matrix)

Parameters:

• linear –

• quadratic –

template<typename T = DataType>
inline void _initialize_quadmat(const Linear<IndexType, FloatType> &linear, const Quadratic<IndexType, FloatType> &quadratic, dispatch_t<T, Sparse> = nullptr)

initialize matrix with linear and quadratic dicts (for sparse matrix)

Parameters:

• linear –

• quadratic –

template<typename T = DataType>
inline void _add_triangular_elements(const DenseMatrix &mat, bool fix_format, dispatch_t<T, Dense> = nullptr)

add non-diagonal elements to upper triangular components for dense matrix

Template Parameters:

T –

Parameters:

• mat –

• fix_format –

template<typename T = DataType>
inline void _add_triangular_elements(const DenseMatrix &mat, bool fix_format, dispatch_t<T, Sparse> = nullptr)

add non-diagonal elements to upper triangular components for sparse matrix

Template Parameters:

T –

Parameters:

• mat –

• fix_format –

inline void _initialize_quadmat(const DenseMatrix &mat, const std::vector<IndexType> &labels_vec, bool fix_format)

initialize matrix with matrix and labels the form of matrix is assumed to be the following two forms:

$$\begin{pmatrix} J_{0,0} & J_{0,1} & \cdots & J_{0,N-1} & h_{0}\\ J_{1,0} & J_{1,1} & \cdots & J_{1,N-1} & h_{1}\\ \vdots & \vdots & \vdots & \vdots & \vdots \\ J_{N-1,0} & J_{N-1,1} & \cdots & J_{N-1,N-1} & h_{N-1}\\ h_{0} & h_{1} & \cdots & h_{N-1} & 1 \\ \end{pmatrix}$$

or

$$\begin{pmatrix} h_{0} & J_{0,1} & \cdots & J_{0,N-1}\\ J_{1,0} & h_{1} & \cdots & J_{1,N-1}\\ \vdots & \vdots & \vdots & \vdots\\ J_{N-1,0} & J_{N-1,1} & \cdots & h_{N-1}\\ \end{pmatrix}$$

if fix_format is set to false, the following shape is assumed:

$$\begin{pmatrix} J_{0,0} & J_{0,1} & \cdots & J_{0,N-1} & h_{0}\\ 0 & J_{1,1} & \cdots & J_{1,N-1} & h_{1}\\ \vdots & \vdots & \vdots & \vdots & \vdots \\ 0 & 0 & \cdots & J_{N-1,N-1} & h_{N-1}\\ 0 & 0 & \cdots & 0 & 1 \\ \end{pmatrix}$$

Parameters:

• mat –

• labels –

• fix_format –

inline Linear<IndexType, FloatType> _generate_linear() const

template<typename T = DataType>
inline Quadratic<IndexType, FloatType> _generate_quadratic(dispatch_t<T, Dense> = nullptr) const

template<typename T = DataType>
inline Quadratic<IndexType, FloatType> _generate_quadratic(dispatch_t<T, Sparse> = nullptr) const

inline void _initialize_quadmat(const SparseMatrix &mat, const std::vector<IndexType> &labels_vec)

initialize matrix with matrix and labels the form of matrix is assumed to be the following form:

$$\begin{pmatrix} J_{0,0} & J_{0,1} & \cdots & J_{0,N-1} & h_{0}\\ 0 & J_{1,1} & \cdots & J_{1,N-1} & h_{1}\\ \vdots & \vdots & \vdots & \vdots & \vdots \\ 0 & 0 & \cdots & J_{N-1,N-1} & h_{N-1}\\ 0 & 0 & \cdots & 0 & 1 \\ \end{pmatrix}$$

Parameters:

• mat –

• labels_vec –

template<typename T = DataType>
inline void _spin_to_binary(dispatch_t<T, Dense> = nullptr)

change internal variable from Ising to QUBO ones for dense matrix The following conversion is applied:

$$\mathrm{offset} += \sum_{i<j} J_{ij} - \sum_{i}h_{i}$$

$$Q_ii += -2\left(\sum_{j}J_{ji}+\sum_{j}J_{ij}\right) + 2h_{i}$$

$$Q_{ij} = 4J_{ij}$$

template<typename T = DataType>
inline void _spin_to_binary(dispatch_t<T, Sparse> = nullptr)

change internal variable from Ising to QUBO ones for sparse matrix The following conversion is applied:

$$\mathrm{offset} += \sum_{i<j} J_{ij} - \sum_{i}h_{i}$$

$$Q_ii += -2\left(\sum_{j}J_{ji}+\sum_{j}J_{ij}\right) + 2h_{i}$$

$$Q_{ij} = 4J_{ij}$$

template<typename T = DataType>
inline void _binary_to_spin(dispatch_t<T, Dense> = nullptr)

change internal variable from QUBO to Ising ones for dense matrix The following conversion is applied:

$$\mathrm{offset} += \frac{1}{4}\sum_{i<j} Q_{ij} + \frac{1}{2}\sum_{i}Q_{ii}$$

$$h_i += \frac{1}{4}\left(\sum_{j}Q_{ji}+\sum_{j}Q_{ij}\right) + \frac{1}{2}Q_{ii}$$

$$J_{ij} = \frac{1}{4}Q_{ij}$$

template<typename T = DataType>
inline void _binary_to_spin(dispatch_t<T, Sparse> = nullptr)

change internal variable from QUBO to Ising ones for sparse matrix The following conversion is applied:

$$\mathrm{offset} += \frac{1}{4}\sum_{i<j} Q_{ij} + \frac{1}{2}\sum_{i}Q_{ii}$$

$$h_i += \frac{1}{4}\left(\sum_{j}Q_{ji}+\sum_{j}Q_{ij}\right) + \frac{1}{2}Q_{ii}$$

$$J_{ij} = \frac{1}{4}Q_{ij}$$

Protected Attributes

Matrix _quadmat

quadratic dense-type matrix The stored matrix has the following triangular form:

$$\begin{pmatrix} J_{0,0} & J_{0,1} & \cdots & J_{0,N-1} & h_{0}\\ 0 & J_{1,1} & \cdots & J_{1,N-1} & h_{1}\\ \vdots & \vdots & \vdots & \vdots & \vdots \\ 0 & 0 & \cdots & J_{N-1,N-1} & h_{N-1}\\ 0 & 0 & \cdots & 0 & 1 \\ \end{pmatrix}$$

std::vector<IndexType> _idx_to_label

vector for converting index to label the list is asssumed to be sorted

std::unordered_map<IndexType, size_t> _label_to_idx

dict for converting label to index

FloatType m_offset

The energy offset associated with the model.

Vartype m_vartype = Vartype::NONE

The model’s type.

Private Types

template<typename T, typename U>
using dispatch_t = std::enable_if_t<std::is_same_v<T, U>, std::nullptr_t>

template type for dispatch used for SFINAE

Template Parameters:

• T –

• U –