[Rule] Knapsack to QUBO

[zazabap]

Source: Knapsack
Target: QUBO
Motivation: Enables solving Knapsack on quantum annealers (D-Wave) and via QUBO solvers; the penalty-based formulation embeds the capacity constraint into the quadratic objective.
Reference: Lucas, 2014, Ising formulations of many NP problems; Glover et al., 2019

Reduction Algorithm

Notation:

• Source: $n$ items with weights $w_0, \ldots, w_{n-1}$, values $v_0, \ldots, v_{n-1}$, capacity $C$
• Target: QUBO with $n + B$ binary variables, where $B = \lfloor \log_2 C \rfloor + 1$

Step 1 — Introduce slack variables:

Convert the inequality $\sum_i w_i x_i \leq C$ to equality by adding $B$ slack bits:

$$\sum_{i=0}^{n-1} w_i x_i + \sum_{j=0}^{B-1} 2^j s_j = C$$

The slack bits encode the unused capacity in binary.

Step 2 — Construct QUBO objective:

$$\text{minimize} \quad H = -\sum_{i=0}^{n-1} v_i x_i + P \left( \sum_{i=0}^{n-1} w_i x_i + \sum_{j=0}^{B-1} 2^j s_j - C \right)^2$$

where $P > \sum_i v_i$ is a penalty coefficient ensuring that any infeasible solution has higher cost than any feasible one.

Variable mapping:

• Item variables: $x_0, \ldots, x_{n-1}$ (same as source)
• Slack variables: $s_0, \ldots, s_{B-1}$ (auxiliary, discarded after solving)

Solution extraction: Take the $x_i$ values from the QUBO solution; ignore the slack variables $s_j$.

Size Overhead

Target metric (code name)	Polynomial (using symbols above)
num_vars	$n + B$ where $B = \lfloor \log_2 C \rfloor + 1$

Validation Method

Closed-loop testing: solve Knapsack by brute-force, solve the reduced QUBO, and verify that both give the same optimal value. Verify that the penalty $P$ is large enough by checking that no infeasible QUBO solution has lower cost than the optimal feasible one.

Example

Source instance: $n = 4$ items, capacity $C = 7$.

Item	Weight	Value
0	2	3
1	3	4
2	4	5
3	5	7

QUBO formulation:

• 7 binary variables: $x_0, x_1, x_2, x_3$ (items) + $s_0, s_1, s_2$ (slack, $B = \lfloor\log_2 7\rfloor + 1 = 3$)
• Penalty: $P > 3 + 4 + 5 + 7 = 19$, so set $P = 20$
• Equality constraint: $2x_0 + 3x_1 + 4x_2 + 5x_3 + s_0 + 2s_1 + 4s_2 = 7$

$$H = -(3x_0 + 4x_1 + 5x_2 + 7x_3) + 20(2x_0 + 3x_1 + 4x_2 + 5x_3 + s_0 + 2s_1 + 4s_2 - 7)^2$$

Optimal QUBO solution: $x = (1,0,0,1)$, $s = (0,0,0)$.

• Penalty: $(2 + 5 + 0 - 7)^2 = 0$ (feasible)
• Objective: $H = -10 + 0 = -10$

Suboptimal feasible: $x = (0,1,1,0)$, $s = (0,0,0)$, $H = -9$ (worse).

Infeasible: $x = (1,1,0,1)$, weight $= 10 > 7$, best slack gives penalty $\geq 20 \cdot 9 = 180$, so $H = -14 + 180 = 166$ (rejected).