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. 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. Embeddings for machine learning models include support-vector machines, clustering and probabilistic graphical models. 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.

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

Alternatively, the linear and quadratic parts can be separated as

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

Intuitively, the weight ${\displaystyle Q_{ij}}$ is added if both ${\displaystyle x_{i}=1}$ and ${\displaystyle x_{j}=1}$. The QUBO problem consists of finding a binary vector ${\displaystyle {\boldsymbol {x}}^{*}}$ that minimizes ${\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}})}$.

In general, ${\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}}}$. The complexity of QUBO arises from the number of candidate binary vectors to be evaluated, as ${\displaystyle \left|\mathbb {B} ^{n}\right|=2^{n}}$ grows exponentially in ${\displaystyle n}$.

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

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