3
$\begingroup$

I am digging into to the workings of the D-wave quantum annealing computers using this documentation. I find it very intuitive and well-explained, but their example of a "simple QUBO problem" does not seem an optimization problem to me as they are just trying to reproduce the XNOR (i.e., they fix the weights based on the kown solution, instead of getting a solution based on weights).

Is there a dead-simple example of a QUBO problem that also has some meaning? Up to 4 qubits for this example are fine, but it must be kind of meaningful.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

I asked a similar question on the Operations Research Stack Exchange. This answer lists about 20 different problems that can be solved by QUBO.

If you want a "dead-simple" example that has some meaning, I personally think that the algorithm for factoring integers using QUBO, is the simplest one to understand, but that is only my opinion.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.