QAOA for 0/1 Knapsack Problem

Overview

The knapsack problem is a classic optimization problem: given a set of items with values and weights, select items to maximize total value without exceeding a weight capacity.

The Problem

Given:

n items with values v₁, v₂, ..., vₙ
Item weights w₁, w₂, ..., wₙ
Knapsack capacity C

Find: Selection x ∈ {0,1}ⁿ that maximizes Σ vᵢxᵢ subject to Σ wᵢxᵢ ≤ C

CODE
Example:
Item 0: value=10, weight=5
Item 1: value=15, weight=8
Item 2: value=20, weight=10
Item 3: value=25, weight=12
Capacity: 18

Optimal: Items {1,2} → value=35, weight=18 ✓

Encoding

Each qubit represents one item:

|1⟩ = Include item
|0⟩ = Exclude item

Qubit	Item	Value	Weight
q₀	0	10	5
q₁	1	15	8
q₂	2	20	10
q₃	3	25	12

QUBO Formulation

The knapsack becomes a QUBO (Quadratic Unconstrained Binary Optimization):

CODE
min: -Σ vᵢxᵢ + P × (Σ wᵢxᵢ - C)²

where P is the penalty for violating capacity.

Running the Circuit

PYTHON
from circuit import run_circuit

# Custom knapsack instance
values = [5, 10, 15, 20]
weights = [2, 4, 6, 8]
capacity = 10

result = run_circuit(values=values, weights=weights, capacity=capacity)
print(f"Best selection: {result['best_solution']['items']}")
print(f"Total value: {result['best_solution']['value']}")

Expected Output

Metric	Value
Best value	35
Best items	[1, 2]
Weight used	18/18
Feasible	Yes

Penalty Parameter

P value	Effect
Too low	May select infeasible solutions
Too high	Over-penalizes, reduces exploration
Optimal	Balance between feasibility and value

Rule of thumb: P ≈ max(values)

Applications

Resource allocation: Budget planning
Loading problems: Container packing
Project selection: Portfolio of projects
Cutting stock: Minimize waste

Variants

Variant	Description
0/1 Knapsack	Each item selected at most once
Bounded	Multiple copies available
Unbounded	Unlimited copies
Multi-dimensional	Multiple constraints

QAOA for Knapsack