Binary Quadratic Models

The binary quadratic model (BQM) class encodes Ising and quadratic unconstrained binary optimization (QUBO) models used by samplers such as the D-Wave system.

The BQM equation,

\[E(\bf{v}) = \sum_{i=1} a_i v_i + \sum_{i<j} b_{i,j} v_i v_j + c \qquad\qquad v_i \in\{-1,+1\} \text{ or } \{0,1\}\]

can represent both.

The Ising model is an objective function of \(N\) variables \(s=[s_1,...,s_N]\) corresponding to physical Ising spins, where \(h_i\) are the biases and \(J_{i,j}\) the couplings (interactions) between spins.

\[\text{Ising:} \qquad E(\bf{s}) = \sum_{i=1} h_i s_i + \sum_{i<j} J_{i,j} s_i s_j \qquad\qquad s_i\in\{-1,+1\}\]

The QUBO model is an objective function of \(N\) binary variables represented as an upper-diagonal matrix \(Q\), where diagonal terms are the linear coefficients and the nonzero off-diagonal terms the quadratic coefficients.

\[\text{QUBO:} \qquad E(\bf{x}) = \sum_{i\le j} x_i Q_{i,j} x_j \qquad\qquad x_i\in \{0,1\}\]

The dimod.BinaryQuadraticModel class can contain both these models and its methods provide convenient utilities for working with, and interworking between, the two representations of a problem.

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

• Getting Started with the D-Wave System

  Introduces key concepts such as objective functions, Ising models, QUBOs, and graphs, explains how these models are used to represent problems, and provides some simple examples.

• D-Wave Problem-Solving Handbook

  Provides a variety of techniques for, and examples of, reformulating problems as BQMs.

• Solving Problems on a D-Wave System

  Describes and demonstrates the use of BQM in the context of Ocean software.