Quantum Computing Experimentation with Amazon Braket

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 ...