Quadratic unconstrained binary optimization – Wikipedia
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]
Definition[edit]
The set of binary vectors of a fixed length
n>0{displaystyle n>0}Bn{displaystyle mathbb {B} ^{n}}
B={0,1}{displaystyle mathbb {B} =lbrace 0,1rbrace } , where
We are given a real-valued upper triangular matrix
Qij{displaystyle Q_{ij}} , whose entries
i,j∈{1,…,n}{displaystyle i,jin lbrace 1,dots ,nrbrace } define a weight for each pair of indices
We can define a function
that assigns a value to each binary vector through
- fQ(x)=x⊤Qx=∑i=1n∑j=inQijxixj{displaystyle f_{Q}(x)=x^{top }Qx=sum _{i=1}^{n}sum _{j=i}^{n}Q_{ij}x_{i}x_{j}}
Intuitively, the weight
Qij{displaystyle Q_{ij}}xi{displaystyle x_{i}} is added if both
xj{displaystyle x_{j}} and
When
Qii{displaystyle Q_{ii}} , the values
xi=1{displaystyle x_{i}=1} are added if
xixi=xi{displaystyle x_{i}x_{i}=x_{i}} , as
xi∈B{displaystyle x_{i}in mathbb {B} } for all
.
The QUBO problem consists of finding a binary vector
x∗{displaystyle x^{*}}fQ{displaystyle f_{Q}} that is minimal with respect to
, namely
- x∗=argminx∈Bn fQ(x){displaystyle x^{*}={underset {xin mathbb {B} ^{n}}{arg min }}~f_{Q}(x)}
In general,
x∗{displaystyle x^{*}}fQ{displaystyle f_{Q}} is not unique, meaning there may be a set of minimizing vectors with equal value w.r.t.
The complexity of QUBO arises from the number of candidate binary vectors to be evaluated, as
n{displaystyle n} grows exponentially in
.
Sometimes, QUBO is defined as the problem of maximizing
fQ{displaystyle f_{Q}}f−Q=−fQ{displaystyle f_{-Q}=-f_{Q}} , which is equivalent to minimizing
.
Properties[edit]
- Multiplying the coefficients
Qij{displaystyle Q_{ij}} with a positive factor α>0{displaystyle alpha >0} f{displaystyle f} accordingly, leaving the optimum x∗{displaystyle x^{*}} unchanged:
- fαQ(x)=∑i≤j(αQij)xixj=α∑i≤jQijxixj=αfQ(x){displaystyle f_{alpha Q}(x)=sum _{ileq j}(alpha Q_{ij})x_{i}x_{j}=alpha sum _{ileq j}Q_{ij}x_{i}x_{j}=alpha f_{Q}(x)}
- Flipping the sign of all coefficients flips the sign of
f{displaystyle f} ‘s output, making x∗{displaystyle x^{*}} the binary vector that maximizes f−Q{displaystyle f_{-Q}} :
- f−Q(x)=∑i≤j(−Qij)xixj=−∑i≤jQijxixj=−fQ(x){displaystyle f_{-Q}(x)=sum _{ileq j}(-Q_{ij})x_{i}x_{j}=-sum _{ileq j}Q_{ij}x_{i}x_{j}=-f_{Q}(x)}
- If all coefficients are positive, the optimum is trivially
x∗=(0,…,0){displaystyle x^{*}=(0,dots ,0)} . Similarly, if all coefficients are negative, the optimum is x∗=(1,…,1){displaystyle x^{*}=(1,dots ,1)} . - If
∀i≠j: Qij=0{displaystyle forall ineq j:~Q_{ij}=0} , i.e., the bits can be optimized independently, then the corresponding QUBO problem is solvable in O(n){displaystyle {mathcal {O}}(n)} , the optimal variable assignments xi∗{displaystyle x_{i}^{*}} simply being 1 if Qii<0{displaystyle Q_{ii}<0} and 0 otherwise.
Applications[edit]
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.[6]
Cluster Analysis[edit]
A bad cluster assignment.
A good cluster assignment.
Visual representation of a clustering problem with 20 points: Circles of the same color belong to the same cluster. Each circle can be understood as a binary variable in the corresponding QUBO problem.
As an illustrative example of how QUBO can be used to encode an optimization problem, we consider the problem of cluster analysis.
Here, we are given a set of 20 points in 2D space, described by a matrix
We 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 two clusters, we can assign a binary variable
i{displaystyle i} to the point corresponding to the
D{displaystyle D} -th row in
xi=0{displaystyle x_{i}=0} , indicating whether it belongs to the first (
xi=1{displaystyle x_{i}=1} ) or second cluster (
Consequently, we have 20 binary variables, which form a binary vector
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
xixj{displaystyle x_{i}x_{j}} , the values
(1−xi)(1−xj){displaystyle (1-x_{i})(1-x_{j})} or
i{displaystyle i} evaluate to 1 if points
j{displaystyle j} and
Similarly,
(1−xi)xj{displaystyle (1-x_{i})x_{j}} or
Let
i{displaystyle i} denote the Euclidean distance between points
j{displaystyle j} and
In order to define a cost function to minimize, when points
j{displaystyle j} and
dij{displaystyle d_{ij}} are in the same cluster we add their positive distance
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.
The cost function thus comes down to
- f(x)=∑i<jdij(xixj+(1−xi)(1−xj))−dij(xi(1−xj)+(1−xi)xj)=∑i<j[4dijxixj−2dijxi−2dijxj+dij]{displaystyle {begin{aligned}f(x)&=sum _{i
From the second line, the QUBO parameters can be easily found by re-arranging to be:
- Qij={4dijif i≠j−(∑k=1i−1dki+∑ℓ=i+1ndiℓ)if i=j{displaystyle {begin{aligned}Q_{ij}&={begin{cases}4d_{ij}&{text{if }}ineq j\-left(sum limits _{k=1}^{i-1}d_{ki}+sum limits _{ell =i+1}^{n}d_{iell }right)&{text{if }}i=jend{cases}}end{aligned}}}
Using these parameters, the optimal QUBO solution will correspond to an optimal cluster w.r.t. above cost function.
Connection to Ising models[edit]
QUBO is very closely related and computationally equivalent to the Ising model, whose Hamiltonian function is defined as
- H(σ)=−∑⟨i j⟩Jijσiσj−μ∑jhjσj{displaystyle H(sigma )=-sum _{langle i~jrangle }J_{ij}sigma _{i}sigma _{j}-mu sum _{j}h_{j}sigma _{j}}
with real-valued parameters
hj,Jij,μ{displaystyle h_{j},J_{ij},mu }i,j{displaystyle i,j} for all
The spin variables
{−1,+1}{displaystyle lbrace -1,+1rbrace } are binary with values from
B{displaystyle mathbb {B} } instead of
Moreover, in the Ising model the variables are typically arranged in a lattice where only neighboring pairs of variables
Applying the identity
yields an equivalent QUBO problem:[2]
- f(x)=∑⟨i j⟩−Jij(2xi−1)(2xj−1)+∑jμhj(2xj−1)=∑⟨i j⟩−4Jijxixj+2Jijxi+2Jijxj−Jij+∑j2μhjxj−μhjusing xj=xjxj=∑i=1n∑j=1iqijxixj+C{displaystyle {begin{aligned}f(x)&=sum _{langle i~jrangle }-J_{ij}(2x_{i}-1)(2x_{j}-1)+sum _{j}mu h_{j}(2x_{j}-1)\&=sum _{langle i~jrangle }-4J_{ij}x_{i}x_{j}+2J_{ij}x_{i}+2J_{ij}x_{j}-J_{ij}+sum _{j}2mu h_{j}x_{j}-mu h_{j}&&{text{using }}x_{j}=x_{j}x_{j}\&=sum _{i=1}^{n}sum _{j=1}^{i}q_{ij}x_{i}x_{j}+Cend{aligned}}}
where
- Qij={−4Jijif i≠j∑⟨k i⟩2Jki+∑⟨i ℓ⟩2Jiℓ+2μhiif i=jC=−∑⟨i j⟩Jij−∑jμhj{displaystyle {begin{aligned}Q_{ij}&={begin{cases}-4J_{ij}&{text{if }}ineq j\sum _{langle k~irangle }2J_{ki}+sum _{langle i~ell rangle }2J_{iell }+2mu h_{i}&{text{if }}i=jend{cases}}\C&=-sum _{langle i~jrangle }J_{ij}-sum _{j}mu h_{j}end{aligned}}}
As the constant
C{displaystyle C}x∗{displaystyle x^{*}} does not change the position of the optimum
, it can be neglected during optimization and is only important for recovering the original Hamiltonian function value.
References[edit]
- ^ Kochenberger, Gary; Hao, Jin-Kao (2014). “The unconstrained binary quadratic programming problem: a survey” (PDF). Journal of Combinatorial Optimization. 28: 58–81. doi:10.1007/s10878-014-9734-0. S2CID 16808394.
- ^ a b Glover, Fred; Kochenberger, Gary (2019). “A Tutorial on Formulating and Using QUBO Models”. arXiv:1811.11538 [cs.DS].
- ^ Lucas, Andrew (2014). “Ising formulations of many NP problems”. Frontiers in Physics. 2: 5. arXiv:1302.5843. Bibcode:2014FrP…..2….5L. doi:10.3389/fphy.2014.00005.
- ^ Mücke, Sascha; Piatkowski, Nico; Morik, Katharina (2019). “Learning Bit by Bit: Extracting the Essence of Machine Learning” (PDF). LWDA. S2CID 202760166. Archived from the original (PDF) on 2020-02-27.
- ^ Tom Simonite (8 May 2013). “D-Wave’s Quantum Computer Goes to the Races, Wins”. MIT Technology Review. Retrieved 12 May 2013.
- ^ Ratke, Daniel (2021-06-10). “List of QUBO formulations”. Retrieved 2022-12-16.
External links[edit]
- QUBO Benchmark (Benchmark of software packages for the exact solution of QUBOs; part of the well-known Mittelmann benchmark collection)
Recent Comments