Below you'll find a brief and simple example. I also recommend that you read A Tutorial on Formulating and Using QUBO Models as it covers the topic in more detail.
Example using switches
So your idiot sibling fancies themselves an electrician, and rewired your house's climate control system while you were out. Lucky for you, there are only two switches and three devices, so you don't actually have to use a quantum computer to figure it out. However, the principle is the same for any number of switches and devices.
Problem: Which switches do you need to flip to produce the maximum amount of heat?
You traced the wiring and found that one switch is wired to a heater producing 2W of heat, the other to a heater producing 3W, and both switches are wired to a cooler that drains 8W of heat when both switches are on.
To solve this problem using a QUBO, first you set it up as a polynomial:
$$
h = 2x_1 + 3x_2 - 8x_1x_2
$$
Our switches are represented as binary variables $x_1$and $x_2$, and $h$ is the total heat in watts.
Next you put the factors into a matrix. The multiplier of each term is placed at the coordinate in the matrix corresponding to its index in $x$, where the origin is top left.
- $2x_1 = 2x_1x_1$, so the $2$ it goes in the top left corner at $(1,1)$. Note that $x_a = x_ax_a$ becuase $x_a$ is in $\{0, 1\}$.
- Similarly, $3x_2 = 3x_2x_2$ so the $3$ goes in the bottom right corner at $(2,2)$.
- For $-8x_1x_2 = -8x_2x_1$ you get the two coordinates $(1,2)$ and $(2,1)$. Divide the $-8$ by two, then put each half at a coordinate. This produces a symmetric QUBO matrix.
This is what our final matrix looks like:
$$
\begin{bmatrix}
2 & -4\\
-4 & 3
\end{bmatrix}
$$
Now you can find your answer by maximizing $y$ in
$$
y = x^tQx
$$
where $x^t$ is $x$ transposed and $Q$ is the QUBO matrix.
Answer: $x_1 = 0, x_2 = 1$, i.e. the first switch should be off and the second switch should be on.
We can put these values into the calculation:
$$
\begin{bmatrix}
0 & 1
\end{bmatrix}
\begin{bmatrix}
2 & -4\\
-4 & 3
\end{bmatrix}
\begin{bmatrix}
0\\
1
\end{bmatrix}
= 3
$$
You can try other combinations of $x$, but you will find that $3$ is indeed the maximum possible value. Obviously this trial and error would be much more time-consuming for larger matrices.
Note that $h = y$ here since we didn't separate out any common factors or offsets when we created our QUBO matrix, but in general you should feed the answer into the polynomial we created instead to obtain the maximal value.
