The knapsack problem is a binary optimization problem: choose a subset of items with given weights and values so that total value is as large as possible without exceeding a fixed capacity. Each item has a binary decision variable: 1 includes it, and 0 excludes it. With n items, there are 2^n possible selections, so even simple item-by-item choices grow quickly into a large search space. section 2.1.1 section 2.1.2
Figure 2.1 The knapsack problem is a binary optimization problem where the optimal solution is the collection of items with the highest value that does not exceed the weight limit.
The diagram captures the constraint and objective: keep total weight within the limit while selecting the highest-value feasible collection. section 2.1.1
Model a selection as a binary string with one position per item. The total value and total weight are linear functions of those binary variables: each included item contributes its value to one total and its weight to the other. This representation makes every candidate selection directly comparable against both the capacity constraint and the value objective. section 2.1.1 section 2.3.1
Three-item capacity example
For capacity 4, use items with (value, weight) pairs (2, 3), (3, 2), and (1, 1). The eight binary selections include 101, with value 3 and weight 4, and 110, with value 4 and weight 3. Selection 110 is optimal: it includes items 1 and 2, stays within capacity, and beats every other feasible selection. section 2.1.2 section 2.3.2
A quantum representation uses a selection register with one qubit per item, plus registers for the selection’s total value and total weight. A measured selection bit of 1 means its corresponding item is included. The value and weight registers encode the two linear functions for every selection, forming a state that associates each binary key with its computed totals. section 2.3.1 section 10.1.2
Figure 10.5 Three registers encoding an item selection, its total value, and its total weight for solving the knapsack problem
The three-register layout makes the representation explicit: one register identifies a selection, while two others hold its associated value and weight. section 10.1.2
A quantum search-oriented solution separates the problem into reusable parts:
- Encode one qubit per item so binary outcomes represent candidate selections. section 2.3.1
- Compute value and weight from the selection bits as linear functions, using controlled phase rotations and an inverse quantum Fourier transform for the function encoding. section 10.1.2
- Recognize selections meeting a maximum weight and minimum value with an oracle, then use amplitude amplification to raise the probability of measuring desired outcomes. section 2.3.2
A practical interface accepts parallel value and weight lists plus a maximum weight. For the three-item example, the search begins with capacity 4 and a minimum value equal to the best single item’s value, 3. Raising the minimum value to 4 isolates the optimal feasible selection, while quantum measurement returns outcomes according to their resulting probabilities. section 2.3.2 section 2.3.2
The same encoding can be implemented as a quantum circuit by placing selection and output registers into equal superposition, applying controlled phase rotations for each coefficient-term pair, and applying the inverse quantum Fourier transform to the output register. Grid-state visualizations then show that each selection aligns with its computed value or weight. section 10.1.2 section 10.1.2
