QUBO

Let $Q \in \R^{n \times n}$ be an upper triangular matrix of weights. One weight $Q_{ij}$ for each pair of indices $\{i, j\} \subseteq \{1, ..., n\}$ with $i < j$.

Let $f_Q: \{0, 1\}^n \rarr \R$ be a function such that for each $x \in \{0, 1\}^n$

$$ f_Q(x) = x^{T} Qx = \sum_{i=1}^n \sum_{j=1}^n Q_{ij}x_i x_j $$

Weight $Q_{ij}$ contributes to the sum if $x_i$ and $x_j$ are 1.

Task: find a binary vector $x^* \in \{0, 1\}^n$ that minimizes $f_Q$:

• For all $x \in \{0, 1\}^n$, $f_Q(x^*) \leq f_Q(x)$
• Brute force takes exponential time. There are $2^n$ vectors.
• NP-hard problems. Cannot be solved in polynomial time uless $P = NP$.
• In practice, such problems are tackled using heuristics.

Formulating Optimization Problems as QUBO Problems

Traveling Salesman Problem - Definition

Let $\{1, ..., n\}$ be a set of cities.

Let $d_{ij}$ be the distance between cities $i$ and $j$.

Task: find the shortest possible route that visits all of the $n$ cities exactly once and returns to the origin city.

Traveling Salesman Problem — Constrained Formulation

Binary variables:

• $x_{i,t} \texttt{ for } i \in \{1, ..., n\}$ and $t \in \{0,1,..., n-1\}$
• $x_{i,t} = 1$ if city $i$ is visited at time stemp $t$ and $0$ otherwise

Objective function: