Quadratic unconstrained binary optimization

Quadratic unconstrained binary optimization (QUBO), also known as unconstrained binary quadratic programming (UBQP), is a combinatorial optimization problem with a wide range of applications from finance and economics to machine learning.^[1] QUBO is an NP hard problem, and for many classical problems from theoretical computer science, like maximum cut, graph coloring and the partition problem, embeddings into QUBO have been formulated.^{[2] [3]} Embeddings for machine learning models include support-vector machines, clustering and probabilistic graphical models.^[4] Moreover, due to its close connection to Ising models, QUBO constitutes a central problem class for adiabatic quantum computation, where it is solved through a physical process called quantum annealing.^[5]

Let ${\displaystyle \mathbb {B} =\lbrace 0,1\rbrace }${\displaystyle \mathbb {B} =\lbrace 0,1\rbrace } the set of binary digits (or bits), then ${\displaystyle \mathbb {B} ^{n}}${\displaystyle \mathbb {B} ^{n}} is the set of binary vectors of fixed length ${\displaystyle n\in \mathbb {N} }${\displaystyle n\in \mathbb {N} }. Given a symmetric or upper triangular matrix ${\displaystyle {\boldsymbol {Q}}\in \mathbb {R} ^{n\times n}}${\displaystyle {\boldsymbol {Q}}\in \mathbb {R} ^{n\times n}}, whose entries ${\displaystyle Q_{ij}}${\displaystyle Q_{ij}} define a weight for each pair of indices ${\displaystyle i,j\in \lbrace 1,\dots ,n\rbrace }${\displaystyle i,j\in \lbrace 1,\dots ,n\rbrace }, we can define the function ${\displaystyle f_{\boldsymbol {Q}}:\mathbb {B} ^{n}\rightarrow \mathbb {R} }${\displaystyle f_{\boldsymbol {Q}}:\mathbb {B} ^{n}\rightarrow \mathbb {R} } that assigns a value to each binary vector ${\displaystyle {\boldsymbol {x}}}${\displaystyle {\boldsymbol {x}}} through

${\displaystyle f_{\boldsymbol {Q}}({\boldsymbol {x}})={\boldsymbol {x}}^{\intercal }{\boldsymbol {Qx}}=\sum _{i=1}^{n}\sum _{j=1}^{n}Q_{ij}x_{i}x_{j}.}${\displaystyle f_{\boldsymbol {Q}}({\boldsymbol {x}})={\boldsymbol {x}}^{\intercal }{\boldsymbol {Qx}}=\sum _{i=1}^{n}\sum _{j=1}^{n}Q_{ij}x_{i}x_{j}.}

Alternatively, the linear and quadratic parts can be separated as

${\displaystyle f_{{\boldsymbol {Q}}',{\boldsymbol {q}}}({\boldsymbol {x}})={\boldsymbol {x}}^{\intercal }{\boldsymbol {Q}}'{\boldsymbol {x}}+{\boldsymbol {q}}^{\intercal }{\boldsymbol {x}},}${\displaystyle f_{{\boldsymbol {Q}}',{\boldsymbol {q}}}({\boldsymbol {x}})={\boldsymbol {x}}^{\intercal }{\boldsymbol {Q}}'{\boldsymbol {x}}+{\boldsymbol {q}}^{\intercal }{\boldsymbol {x}},}

where ${\displaystyle {\boldsymbol {Q}}'\in \mathbb {R} ^{n\times n}}${\displaystyle {\boldsymbol {Q}}'\in \mathbb {R} ^{n\times n}} and ${\displaystyle {\boldsymbol {q}}\in \mathbb {R} ^{n}}${\displaystyle {\boldsymbol {q}}\in \mathbb {R} ^{n}}. This is equivalent to the previous definition through ${\displaystyle {\boldsymbol {Q}}={\boldsymbol {Q}}'+\operatorname {diag} [{\boldsymbol {q}}]}${\displaystyle {\boldsymbol {Q}}={\boldsymbol {Q}}'+\operatorname {diag} [{\boldsymbol {q}}]} using the diag operator, exploiting that ${\displaystyle x=x\cdot x}${\displaystyle x=x\cdot x} for all binary values ${\displaystyle x}${\displaystyle x}.

Intuitively, the weight ${\displaystyle Q_{ij}}${\displaystyle Q_{ij}} is added if both ${\displaystyle x_{i}=1}${\displaystyle x_{i}=1} and ${\displaystyle x_{j}=1}${\displaystyle x_{j}=1}. The QUBO problem consists of finding a binary vector ${\displaystyle {\boldsymbol {x}}^{*}}${\displaystyle {\boldsymbol {x}}^{*}} that minimizes ${\displaystyle f_{\boldsymbol {Q}}}${\displaystyle f_{\boldsymbol {Q}}}, i.e., ${\displaystyle \forall {\boldsymbol {x}}\in \mathbb {B} ^{n}:~f_{\boldsymbol {Q}}({\boldsymbol {x}}^{*})\leq f_{\boldsymbol {Q}}({\boldsymbol {x}})}${\displaystyle \forall {\boldsymbol {x}}\in \mathbb {B} ^{n}:~f_{\boldsymbol {Q}}({\boldsymbol {x}}^{*})\leq f_{\boldsymbol {Q}}({\boldsymbol {x}})}.

In general, ${\displaystyle {\boldsymbol {x}}^{*}}${\displaystyle {\boldsymbol {x}}^{*}} is not unique, meaning there may be a set of minimizing vectors with equal value w.r.t. ${\displaystyle f_{\boldsymbol {Q}}}${\displaystyle f_{\boldsymbol {Q}}}. The complexity of QUBO arises from the number of candidate binary vectors to be evaluated, as ${\displaystyle \left|\mathbb {B} ^{n}\right|=2^{n}}${\displaystyle \left|\mathbb {B} ^{n}\right|=2^{n}} grows exponentially in ${\displaystyle n}${\displaystyle n}.

Sometimes, QUBO is defined as the problem of maximizing ${\displaystyle f_{\boldsymbol {Q}}}${\displaystyle f_{\boldsymbol {Q}}}, which is equivalent to minimizing ${\displaystyle f_{-{\boldsymbol {Q}}}=-f_{\boldsymbol {Q}}}${\displaystyle f_{-{\boldsymbol {Q}}}=-f_{\boldsymbol {Q}}}.

QUBO is scale invariant for positive factors ${\displaystyle \alpha >0}${\displaystyle \alpha >0}, which leave the optimum ${\displaystyle {\boldsymbol {x}}^{*}}${\displaystyle {\boldsymbol {x}}^{*}} unchanged:

${\displaystyle f_{\alpha {\boldsymbol {Q}}}({\boldsymbol {x}})={\boldsymbol {x}}^{\intercal }(\alpha {\boldsymbol {Q}}){\boldsymbol {x}}=\alpha ({\boldsymbol {x}}^{\intercal }{\boldsymbol {Qx}})=\alpha f_{\boldsymbol {Q}}({\boldsymbol {x}})}${\displaystyle f_{\alpha {\boldsymbol {Q}}}({\boldsymbol {x}})={\boldsymbol {x}}^{\intercal }(\alpha {\boldsymbol {Q}}){\boldsymbol {x}}=\alpha ({\boldsymbol {x}}^{\intercal }{\boldsymbol {Qx}})=\alpha f_{\boldsymbol {Q}}({\boldsymbol {x}})}.

In its general form, QUBO is NP-hard and cannot be solved efficiently by any polynomial-time algorithm.^[6] However, there are polynomially-solvable special cases, where ${\displaystyle {\boldsymbol {Q}}}${\displaystyle {\boldsymbol {Q}}} has certain properties,^[7] for example:

• If all coefficients are positive, the optimum is trivially ${\displaystyle {\boldsymbol {x}}^{*}=(0,\dots ,0)^{\intercal }}${\displaystyle {\boldsymbol {x}}^{*}=(0,\dots ,0)^{\intercal }}. Similarly, if all coefficients are negative, the optimum is ${\displaystyle {\boldsymbol {x}}^{*}=(1,\dots ,1)^{\intercal }}${\displaystyle {\boldsymbol {x}}^{*}=(1,\dots ,1)^{\intercal }}.
• If ${\displaystyle {\boldsymbol {Q}}}${\displaystyle {\boldsymbol {Q}}} is diagonal, the bits can be optimized independently, and the problem is solvable in ${\displaystyle {\mathcal {O}}(n)}${\displaystyle {\mathcal {O}}(n)}. The optimal variable assignments are simply ${\displaystyle x_{i}^{*}=1}${\displaystyle x_{i}^{*}=1} if ${\displaystyle Q_{ii}<0}${\displaystyle Q_{ii}<0}, and ${\displaystyle x_{i}^{*}=0}${\displaystyle x_{i}^{*}=0} otherwise.
• If all off-diagonal elements of ${\displaystyle {\boldsymbol {Q}}}${\displaystyle {\boldsymbol {Q}}} are non-positive, the corresponding QUBO problem is solvable in polynomial time.^[8]

QUBO can be solved using integer linear programming solvers like CPLEX or Gurobi Optimizer. This is possible since QUBO can be reformulated as a linear constrained binary optimization problem. To achieve this, substitute the product ${\displaystyle x_{i}x_{j}}${\displaystyle x_{i}x_{j}} by an additional binary variable ${\displaystyle z_{ij}\in \mathbb {B} }${\displaystyle z_{ij}\in \mathbb {B} } and add the constraints ${\displaystyle x_{i}\geq z_{ij}}${\displaystyle x_{i}\geq z_{ij}}, ${\displaystyle x_{j}\geq z_{ij}}${\displaystyle x_{j}\geq z_{ij}} and ${\displaystyle x_{i}+x_{j}-1\leq z_{ij}}${\displaystyle x_{i}+x_{j}-1\leq z_{ij}}. Note that ${\displaystyle z_{ij}}${\displaystyle z_{ij}} can also be relaxed to continuous variables within the bounds zero and one.

QUBO is a structurally simple, yet computationally hard optimization problem. It can be used to encode a wide range of optimization problems from various scientific areas.^[9]

Given a graph ${\displaystyle G=(V,E)}${\displaystyle G=(V,E)} with vertex set ${\displaystyle V=\lbrace 1,\dots ,n\rbrace }${\displaystyle V=\lbrace 1,\dots ,n\rbrace } and edges ${\displaystyle E\subseteq V\times V}${\displaystyle E\subseteq V\times V}, the maximum cut (max-cut) problem consists of finding two subsets ${\displaystyle S,T\subseteq V}${\displaystyle S,T\subseteq V} with ${\displaystyle T=V\setminus S}${\displaystyle T=V\setminus S}, such that the number of edges between ${\displaystyle S}${\displaystyle S} and ${\displaystyle T}${\displaystyle T} is maximized.

The more general weighted max-cut problem assumes edge weights ${\displaystyle w_{ij}\geq 0~\forall i,j\in V}${\displaystyle w_{ij}\geq 0~\forall i,j\in V}, with ${\displaystyle (i,j)\notin E\Rightarrow w_{ij}=0}${\displaystyle (i,j)\notin E\Rightarrow w_{ij}=0}, and asks for a partition ${\displaystyle S,T\subseteq V}${\displaystyle S,T\subseteq V} that maximizes the sum of edge weights between ${\displaystyle S}${\displaystyle S} and ${\displaystyle T}${\displaystyle T}, i.e.,

${\displaystyle \max _{S\subseteq V}\sum _{i\in S,j\notin S}w_{ij}.}${\displaystyle \max _{S\subseteq V}\sum _{i\in S,j\notin S}w_{ij}.}

By setting ${\displaystyle w_{ij}=1}${\displaystyle w_{ij}=1} for all ${\displaystyle (i,j)\in E}${\displaystyle (i,j)\in E} this becomes equivalent to the original max-cut problem above, which is why we focus on this more general form in the following.

For every vertex in ${\displaystyle i\in V}${\displaystyle i\in V} we introduce a binary variable ${\displaystyle x_{i}}${\displaystyle x_{i}} with the interpretation ${\displaystyle x_{i}=0}${\displaystyle x_{i}=0} if ${\displaystyle i\in S}${\displaystyle i\in S} and ${\displaystyle x_{i}=1}${\displaystyle x_{i}=1} if ${\displaystyle i\in T}${\displaystyle i\in T}. As ${\displaystyle T=V\setminus S}${\displaystyle T=V\setminus S}, every ${\displaystyle i}${\displaystyle i} is in exactly one set, meaning there is a 1:1 correspondence between binary vectors ${\displaystyle {\boldsymbol {x}}\in \mathbb {B} ^{n}}${\displaystyle {\boldsymbol {x}}\in \mathbb {B} ^{n}} and partitions of ${\displaystyle V}${\displaystyle V} into two subsets.

We observe that, for any ${\displaystyle i,j\in V}${\displaystyle i,j\in V}, the expression ${\displaystyle x_{i}(1-x_{j})+(1-x_{i})x_{j}}${\displaystyle x_{i}(1-x_{j})+(1-x_{i})x_{j}} evaluates to 1 if and only if ${\displaystyle i}${\displaystyle i} and ${\displaystyle j}${\displaystyle j} are in different subsets, equivalent to logical XOR. Let ${\displaystyle {\boldsymbol {W}}\in \mathbb {R} _{+}^{n\times n}}${\displaystyle {\boldsymbol {W}}\in \mathbb {R} _{+}^{n\times n}} with ${\displaystyle W_{ij}=w_{ij}~\forall i,j\in V}${\displaystyle W_{ij}=w_{ij}~\forall i,j\in V}. By extending above expression to matrix-vector form we find that

${\displaystyle {\boldsymbol {x}}^{\intercal }{\boldsymbol {W}}({\boldsymbol {1}}-{\boldsymbol {x}})+({\boldsymbol {1}}-{\boldsymbol {x}})^{\intercal }{\boldsymbol {Wx}}=-2{\boldsymbol {x}}^{\intercal }{\boldsymbol {Wx}}+({\boldsymbol {W1}}+{\boldsymbol {W}}^{\intercal }{\boldsymbol {1}})^{\intercal }{\boldsymbol {x}}}${\displaystyle {\boldsymbol {x}}^{\intercal }{\boldsymbol {W}}({\boldsymbol {1}}-{\boldsymbol {x}})+({\boldsymbol {1}}-{\boldsymbol {x}})^{\intercal }{\boldsymbol {Wx}}=-2{\boldsymbol {x}}^{\intercal }{\boldsymbol {Wx}}+({\boldsymbol {W1}}+{\boldsymbol {W}}^{\intercal }{\boldsymbol {1}})^{\intercal }{\boldsymbol {x}}}

is the sum of weights of all edges between ${\displaystyle S}${\displaystyle S} and ${\displaystyle T}${\displaystyle T}, where ${\displaystyle {\boldsymbol {1}}=(1,1,\dots ,1)^{\intercal }\in \mathbb {R} ^{n}}${\displaystyle {\boldsymbol {1}}=(1,1,\dots ,1)^{\intercal }\in \mathbb {R} ^{n}}. As this is a quadratic function over ${\displaystyle {\boldsymbol {x}}}${\displaystyle {\boldsymbol {x}}}, it is a QUBO problem whose parameter matrix we can read from above expression as

${\displaystyle {\boldsymbol {Q}}=2{\boldsymbol {W}}-\operatorname {diag} [{\boldsymbol {W1}}+{\boldsymbol {W}}^{\intercal }{\boldsymbol {1}}],}${\displaystyle {\boldsymbol {Q}}=2{\boldsymbol {W}}-\operatorname {diag} [{\boldsymbol {W1}}+{\boldsymbol {W}}^{\intercal }{\boldsymbol {1}}],}

after flipping the sign to make it a minimization problem.

Next, we consider the problem of cluster analysis, where we are given a set of ${\displaystyle N}${\displaystyle N} points in ${\displaystyle d}${\displaystyle d}-dimensional space and want to assign each point to one of two classes or clusters, such that points in the same cluster are similar to each other. For this example we set ${\displaystyle N=20}${\displaystyle N=20} and ${\displaystyle d=2}${\displaystyle d=2}. The data is given as a matrix ${\displaystyle {\boldsymbol {X}}\in \mathbb {R} ^{20\times 2}}${\displaystyle {\boldsymbol {X}}\in \mathbb {R} ^{20\times 2}}, where each row contains two cartesian coordinates. For two clusters, we can assign a binary variable ${\displaystyle x_{i}\in \mathbb {B} }${\displaystyle x_{i}\in \mathbb {B} } to the point corresponding to the ${\displaystyle i}${\displaystyle i}-th row in ${\displaystyle {\boldsymbol {X}}}${\displaystyle {\boldsymbol {X}}}, indicating whether it belongs to the first (${\displaystyle x_{i}=0}${\displaystyle x_{i}=0}) or second cluster (${\displaystyle x_{i}=1}${\displaystyle x_{i}=1}). Consequently, we have 20 binary variables, which form a binary vector ${\displaystyle {\boldsymbol {x}}\in \mathbb {B} ^{20}}${\displaystyle {\boldsymbol {x}}\in \mathbb {B} ^{20}} that corresponds to a cluster assignment of all points (see figure).

One way to derive a clustering is to consider the pairwise distances between points. Given a cluster assignment ${\displaystyle {\boldsymbol {x}}}${\displaystyle {\boldsymbol {x}}}, the expression ${\displaystyle x_{i}x_{j}+(1-x_{i})(1-x_{j})}${\displaystyle x_{i}x_{j}+(1-x_{i})(1-x_{j})} evaluates to 1 if points ${\displaystyle i}${\displaystyle i} and ${\displaystyle j}${\displaystyle j} are in the same cluster. Similarly, ${\displaystyle x_{i}(1-x_{j})+(1-x_{i})x_{j}=1}${\displaystyle x_{i}(1-x_{j})+(1-x_{i})x_{j}=1} indicates that they are in different clusters. Let ${\displaystyle d_{ij}>0}${\displaystyle d_{ij}>0} denote the Euclidean distance between the points ${\displaystyle i}${\displaystyle i} and ${\displaystyle j}${\displaystyle j}, i.e.,

${\displaystyle d_{ij}={\sqrt {{\boldsymbol {X}}_{i}^{\intercal }{\boldsymbol {X}}_{j}}}}${\displaystyle d_{ij}={\sqrt {{\boldsymbol {X}}_{i}^{\intercal }{\boldsymbol {X}}_{j}}}},

where ${\displaystyle {\boldsymbol {X}}_{i}}${\displaystyle {\boldsymbol {X}}_{i}} is the ${\displaystyle i}${\displaystyle i}-th row of ${\displaystyle {\boldsymbol {X}}}${\displaystyle {\boldsymbol {X}}}.

In order to define a cost function to minimize, when points ${\displaystyle i}${\displaystyle i} and ${\displaystyle j}${\displaystyle j} are in the same cluster we add their positive distance ${\displaystyle d_{ij}}${\displaystyle d_{ij}}, and subtract it when they are in different clusters. This way, an optimal solution tends to place points which are far apart into different clusters, and points that are close into the same cluster.

Let ${\displaystyle {\boldsymbol {D}}\in \mathbb {R} ^{N\times N}}${\displaystyle {\boldsymbol {D}}\in \mathbb {R} ^{N\times N}} with ${\displaystyle D_{ij}=d_{ij}/2}${\displaystyle D_{ij}=d_{ij}/2} for all ${\displaystyle i,j\in \lbrace 1,\dots ,n\rbrace }${\displaystyle i,j\in \lbrace 1,\dots ,n\rbrace }. Given an assignment ${\displaystyle {\boldsymbol {x}}\in \mathbb {B} ^{N}}${\displaystyle {\boldsymbol {x}}\in \mathbb {B} ^{N}}, such a cost function is given by

${\displaystyle {\begin{aligned}f({\boldsymbol {x}})&={\boldsymbol {x}}^{\intercal }{\boldsymbol {Dx}}-{\boldsymbol {x}}^{\intercal }{\boldsymbol {D}}({\boldsymbol {1}}-{\boldsymbol {x}})-({\boldsymbol {1}}-{\boldsymbol {x}})^{\intercal }{\boldsymbol {Dx}}+({\boldsymbol {1}}-{\boldsymbol {x}})^{\intercal }{\boldsymbol {D}}({\boldsymbol {1}}-{\boldsymbol {x}})\\&=4{\boldsymbol {x}}^{\intercal }{\boldsymbol {D}}{\boldsymbol {x}}-4{\boldsymbol {1}}^{\intercal }{\boldsymbol {D}}{\boldsymbol {x}}+{\boldsymbol {1}}^{\intercal }{\boldsymbol {D1}},\end{aligned}}}${\displaystyle {\begin{aligned}f({\boldsymbol {x}})&={\boldsymbol {x}}^{\intercal }{\boldsymbol {Dx}}-{\boldsymbol {x}}^{\intercal }{\boldsymbol {D}}({\boldsymbol {1}}-{\boldsymbol {x}})-({\boldsymbol {1}}-{\boldsymbol {x}})^{\intercal }{\boldsymbol {Dx}}+({\boldsymbol {1}}-{\boldsymbol {x}})^{\intercal }{\boldsymbol {D}}({\boldsymbol {1}}-{\boldsymbol {x}})\\&=4{\boldsymbol {x}}^{\intercal }{\boldsymbol {D}}{\boldsymbol {x}}-4{\boldsymbol {1}}^{\intercal }{\boldsymbol {D}}{\boldsymbol {x}}+{\boldsymbol {1}}^{\intercal }{\boldsymbol {D1}},\end{aligned}}}

where ${\displaystyle {\boldsymbol {1}}=(1,1,\dots ,1)^{\intercal }\in \mathbb {R} ^{N}}${\displaystyle {\boldsymbol {1}}=(1,1,\dots ,1)^{\intercal }\in \mathbb {R} ^{N}}.

From the second line we can see that this expression can be re-arranged to a QUBO problem by defining

${\displaystyle {\boldsymbol {Q}}=4{\boldsymbol {D}}-4\operatorname {diag} [{\boldsymbol {D1}}]}${\displaystyle {\boldsymbol {Q}}=4{\boldsymbol {D}}-4\operatorname {diag} [{\boldsymbol {D1}}]}

and ignoring the constant term ${\displaystyle {\boldsymbol {1}}^{\intercal }{\boldsymbol {D1}}}${\displaystyle {\boldsymbol {1}}^{\intercal }{\boldsymbol {D1}}}. Using these parameters, a binary vector minimizing this QUBO instance ${\displaystyle {\boldsymbol {Q}}}${\displaystyle {\boldsymbol {Q}}} will correspond to an optimal cluster assignment w.r.t. above cost function.

QUBO is very closely related and computationally equivalent to the Ising model, whose Hamiltonian function is defined as

${\displaystyle H({\boldsymbol {\sigma }})={\boldsymbol {\sigma }}^{\intercal }{\boldsymbol {J}}{\boldsymbol {\sigma }}+{\boldsymbol {h}}^{\intercal }{\boldsymbol {\sigma }}=\sum _{i,j}J_{ij}\sigma _{i}\sigma _{j}+\sum _{j}h_{j}\sigma _{j}}${\displaystyle H({\boldsymbol {\sigma }})={\boldsymbol {\sigma }}^{\intercal }{\boldsymbol {J}}{\boldsymbol {\sigma }}+{\boldsymbol {h}}^{\intercal }{\boldsymbol {\sigma }}=\sum _{i,j}J_{ij}\sigma _{i}\sigma _{j}+\sum _{j}h_{j}\sigma _{j}}

with real-valued parameters ${\displaystyle h_{j},J_{ij}}${\displaystyle h_{j},J_{ij}} for all ${\displaystyle i,j}${\displaystyle i,j}. The spin variables ${\displaystyle \sigma _{j}}${\displaystyle \sigma _{j}} are binary with values from ${\displaystyle \lbrace -1,+1\rbrace }${\displaystyle \lbrace -1,+1\rbrace } instead of ${\displaystyle \mathbb {B} }${\displaystyle \mathbb {B} }. Note that this formulation is simplified, since, in a physics context, ${\displaystyle \sigma _{i}}${\displaystyle \sigma _{i}} are typically Pauli operators, which are complex-valued matrices of size ${\displaystyle 2^{n}\times 2^{n}}${\displaystyle 2^{n}\times 2^{n}}, whereas here we treat them as binary variables. Many formulations of the Ising model Hamiltonian further assume that the variables are arranged in a lattice, where only neighboring pairs of variables ${\displaystyle \langle i~j\rangle }${\displaystyle \langle i~j\rangle } can have non-zero coefficients; here, we simply assume that ${\displaystyle J_{ij}=0}${\displaystyle J_{ij}=0} if ${\displaystyle i}${\displaystyle i} and ${\displaystyle j}${\displaystyle j} are not neighbors.

Applying the identity ${\displaystyle \sigma =1-2x}${\displaystyle \sigma =1-2x} yields an equivalent QUBO problem ^[10]

${\displaystyle {\begin{aligned}&{\boldsymbol {\sigma }}^{\intercal }{\boldsymbol {J}}{\boldsymbol {\sigma }}+{\boldsymbol {h}}^{\intercal }{\boldsymbol {\sigma }}\\&=({\boldsymbol {1}}-2{\boldsymbol {x}})^{\intercal }{\boldsymbol {J}}({\boldsymbol {1}}-2{\boldsymbol {x}})+{\boldsymbol {h}}^{\intercal }({\boldsymbol {1}}-2{\boldsymbol {x}})\\&=4{\boldsymbol {x}}^{\intercal }{\boldsymbol {J}}{\boldsymbol {x}}-4{\boldsymbol {1}}^{\intercal }{\boldsymbol {Jx}}+{\boldsymbol {1}}^{\intercal }{\boldsymbol {J1}}-2{\boldsymbol {h}}^{\intercal }{\boldsymbol {x}}+{\boldsymbol {h}}^{\intercal }{\boldsymbol {1}}\\&={\boldsymbol {x}}^{\intercal }(4{\boldsymbol {J}}){\boldsymbol {x}}-(4{\boldsymbol {J}}^{\intercal }{\boldsymbol {1}}+2{\boldsymbol {h}})^{\intercal }{\boldsymbol {x}}+\underbrace {{\boldsymbol {1}}^{\intercal }{\boldsymbol {J1}}+{\boldsymbol {h}}^{\intercal }{\boldsymbol {1}}} _{\text{const.}},\end{aligned}}}${\displaystyle {\begin{aligned}&{\boldsymbol {\sigma }}^{\intercal }{\boldsymbol {J}}{\boldsymbol {\sigma }}+{\boldsymbol {h}}^{\intercal }{\boldsymbol {\sigma }}\\&=({\boldsymbol {1}}-2{\boldsymbol {x}})^{\intercal }{\boldsymbol {J}}({\boldsymbol {1}}-2{\boldsymbol {x}})+{\boldsymbol {h}}^{\intercal }({\boldsymbol {1}}-2{\boldsymbol {x}})\\&=4{\boldsymbol {x}}^{\intercal }{\boldsymbol {J}}{\boldsymbol {x}}-4{\boldsymbol {1}}^{\intercal }{\boldsymbol {Jx}}+{\boldsymbol {1}}^{\intercal }{\boldsymbol {J1}}-2{\boldsymbol {h}}^{\intercal }{\boldsymbol {x}}+{\boldsymbol {h}}^{\intercal }{\boldsymbol {1}}\\&={\boldsymbol {x}}^{\intercal }(4{\boldsymbol {J}}){\boldsymbol {x}}-(4{\boldsymbol {J}}^{\intercal }{\boldsymbol {1}}+2{\boldsymbol {h}})^{\intercal }{\boldsymbol {x}}+\underbrace {{\boldsymbol {1}}^{\intercal }{\boldsymbol {J1}}+{\boldsymbol {h}}^{\intercal }{\boldsymbol {1}}} _{\text{const.}},\end{aligned}}}

whose weight matrix ${\displaystyle {\boldsymbol {Q}}}${\displaystyle {\boldsymbol {Q}}} is given by

${\displaystyle {\boldsymbol {Q}}=4{\boldsymbol {J}}-\operatorname {diag} [4{\boldsymbol {J}}^{\intercal }{\boldsymbol {1}}+2{\boldsymbol {h}}],}${\displaystyle {\boldsymbol {Q}}=4{\boldsymbol {J}}-\operatorname {diag} [4{\boldsymbol {J}}^{\intercal }{\boldsymbol {1}}+2{\boldsymbol {h}}],}

again ignoring the constant term, which does not affect the minization. Using the identity ${\displaystyle x=(1-\sigma )/2}${\displaystyle x=(1-\sigma )/2}, a QUBO problem with matrix ${\displaystyle {\boldsymbol {Q}}}${\displaystyle {\boldsymbol {Q}}} can be converted to an equivalent Ising model using the same technique, yielding

${\displaystyle {\begin{aligned}{\boldsymbol {J}}&={\boldsymbol {Q}}/4,&{\boldsymbol {h}}&=-({\boldsymbol {Q1}}+{\boldsymbol {Q}}^{\intercal }{\boldsymbol {1}})/4,\end{aligned}}}${\displaystyle {\begin{aligned}{\boldsymbol {J}}&={\boldsymbol {Q}}/4,&{\boldsymbol {h}}&=-({\boldsymbol {Q1}}+{\boldsymbol {Q}}^{\intercal }{\boldsymbol {1}})/4,\end{aligned}}}

and a constant offset of ${\displaystyle {\boldsymbol {1}}^{\intercal }{\boldsymbol {Q1}}/4}${\displaystyle {\boldsymbol {1}}^{\intercal }{\boldsymbol {Q1}}/4}.^[10]

• QUBO Benchmark (Benchmark of software packages for the exact solution of QUBOs; part of the well-known Mittelmann benchmark collection)
• Endre Boros, Peter L Hammer & Gabriel Tavares (April 2007). "Local search heuristics for Quadratic Unconstrained Binary Optimization (QUBO)". Journal of Heuristics. 13 (2). Association for Computing Machinery: 99–132. doi:10.1007/s10732-007-9009-3. S2CID 32887708 . Retrieved 12 May 2013.
• Di Wang & Robert Kleinberg (November 2009). "Analyzing quadratic unconstrained binary optimization problems via multicommodity flows". Discrete Applied Mathematics. 157 (18). Elsevier: 3746–3753. doi:10.1016/j.dam.200907009. PMC 2808708 . PMID 20161596.
• Hiroshima University and NTT DATA Group Corporation : "QUBO++ with ABS2 GPU QUBO Solver" # Software.

• Machine learning algorithms

• Articles with short description
• Short description matches Wikidata