Appendix: Knapsack BQM Derivation

This Appendix will show a sample expansion of the quadratic unconstrained binary optimization (QUBO) for the Knapsack problem, which we covered in Chapter 11, Single Objective Optimization Use Case. We will start with equation 11.7 (reproduced here for clarity). In this equation, we described the objective and the two constraints in a mathematical form representing a QUBO. Many real-world problems also include objectives and constraints and can be defined in a similar QUBO format. The reason for showing this derivation is to give you an appreciation of how we go from the initial mathematical version to the binary quadratic model (BQM) matrix Mf.

Getting started with the derivation

Here, we will detail the QUBO formulation of the 0/1 knapsack formulation with integer weight constraint taken from Chapter 11:

Splitting the preceding equation into the three equations gives us the following:

We know that xi and yn are binary.

Before we continue, let’s review the expansion of the square of a sum:

Here, ai is a constant:

Since xi is binary,

Thus,

The first sum on the right side of the equation represents the linear terms or the terms on the diagonal of the matrix, while the second sum on the right side is the upper-right quadratic terms.

Now, expanding equation A. 1:

Using equation A. 7, we can expand the first term:

Next, we can expand equation A. 2:

We will now expand each of the three terms on the right side of equation A.11.

The first term in equation A. 11 can be expanded as follows:

The second term in equation A.11 can be simplified to the following:

Note this is going to connect the xi terms with the yn terms.

The last term in equation A. 11 is expanded to the following:

Creating the required matrices

Now that we have expanded the equations, we can look at how each of the expanded terms relates to a portion of the final matrix.

Equation A. 3 does not need expansion. We can create our first matrix Mv from equation A. 3:

Here, we can use C to control the effect of the value of each item if needed.

We will represent the next matrix Myc from equation A. 10 as follows:

Note that basically, this matrix has -1 on the diagonal terms and 2 on the upper right. This matrix implements the constraint that there is only one weight in the solution. We will use the multiplier A to control the effect of this matrix, which will be to penalize any solutions with more than one weight and ensure the constraint is being applied. The constant A in equation A. 10 is going to be ignored since it cannot be implemented in the matrix and becomes an offset to add to the final energy value.

The next three matrices will come from the results of expanding equation A. 2.

First, we represent the matrix BMx from equation A. 12:

We represent the next matrix BMxy from equation A. 13:

And, we represent the final matrix BMy from equation A. 14:

These three matrices ensure that the weight of the items selected in the knapsack equals the weight represented by yn. The value of the multiplier B can be used to ensure this constraint is working properly.

Keep in mind the following:

• We also have an offset of A, which came from equation A. 10.
• Mv and Mx use the same variable xi.
• Mxy uses both xi and yn variables.
• Myc and My use the same variable yn.

This results in the primary BQM matrix equations along with their multipliers as used in the code for Chapter 11:

Equations A. 20, A. 21, and A. 22 can be further consolidated based on the binary variables if desired, as shown here:

Conclusion

We have shown how we take a QUBO formulation of a real-world problem, in this case, a Knapsack problem, and expand the terms to derive our BQM matrix. The matrix can then be sent to the quantum annealer or to a gate-based quantum computer for optimization. You may now return to Chapter 11, Single-Objective Optimization Use Cases and continue to review how matrix Mf is used in finding the solutions for the Knapsack problem.