QAOA for 0/1 Knapsack Problem

What You'll Learn:

• How to map a constrained optimization problem to an unconstrained QUBO formulation
• How penalty terms enforce constraints in variational quantum algorithms
• How QAOA encodes value maximization and weight constraints into a single cost Hamiltonian
• How to tune the penalty parameter P for the right balance between feasibility and exploration

Level: Intermediate | Time: 30 minutes | Qubits: 4 | Framework: Qiskit

Prerequisites

• QAOA MaxCut — QAOA fundamentals, cost/mixer operators, parameter optimization
• Bell State — entanglement basics
• Grover's Search — quantum search over bitstrings

The Idea

Imagine you're packing a backpack for a hike. You have four items — a water bottle, snacks, a first-aid kit, and a camera — each with a different value to you and a different weight. Your backpack has a weight limit. Which items do you pack to maximize value without breaking the strap?

That's the 0/1 Knapsack problem: given n items with values and weights, select a subset to maximize total value without exceeding a weight capacity C. It's NP-hard and appears everywhere from logistics to portfolio selection.

The key challenge versus MaxCut: Knapsack has a constraint (weight limit). QAOA needs unconstrained objectives, so we use the QUBO (Quadratic Unconstrained Binary Optimization) trick: fold the constraint into the objective as a quadratic penalty. The penalty parameter P controls how strongly we enforce the weight limit.

How It Works

The Problem

Given 4 items, select a subset maximizing value within weight capacity:

CODECopy
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 (exactly at capacity)

The QUBO Formulation

We convert the constrained problem to an unconstrained one:

CODECopy
Minimize: -Σ vᵢxᵢ + P × (Σ wᵢxᵢ - C)²
           ├─ value ─┤   ├─ penalty ────────┤

The penalty term (Σ wᵢxᵢ - C)² expands into linear and quadratic terms:

CODECopy
P × [Σᵢ wᵢ²xᵢ + 2Σᵢ<ⱼ wᵢwⱼxᵢxⱼ - 2C Σᵢ wᵢxᵢ + C²]
     ├─ linear ─┤   ├─ quadratic ────┤   ├─ linear ─┤   const

Since xᵢ ∈ {0,1} and xᵢ² = xᵢ, every term maps to single-qubit (RZ) or two-qubit (RZZ) rotations.

The QAOA Circuit

CODECopy
     ┌───┐ ┌──────────┐ ┌─────────────────┐ ┌──────────┐ ┌─────────┐
q_0: ┤ H ├─┤ RZ(value)├─┤ RZZ(penalty,0-1)├─┤ RZ(pen.) ├─┤ RX(2β) ├── measure
     ├───┤ ├──────────┤ ├─────────────────┤ ├──────────┤ ├─────────┤
q_1: ┤ H ├─┤ RZ(value)├─┤ RZZ(penalty,0-2)├─┤ RZ(pen.) ├─┤ RX(2β) ├── measure
     ├───┤ ├──────────┤ ├─────────────────┤ ├──────────┤ ├─────────┤
q_2: ┤ H ├─┤ RZ(value)├─┤ RZZ(penalty,1-2)├─┤ RZ(pen.) ├─┤ RX(2β) ├── measure
     ├───┤ ├──────────┤ ├─────────────────┤ ├──────────┤ ├─────────┤
q_3: ┤ H ├─┤ RZ(value)├─┤ RZZ(penalty,...) ├─┤ RZ(pen.) ├─┤ RX(2β) ├── measure
     └───┘ └──────────┘ └─────────────────┘ └──────────┘ └─────────┘
           ├─── Cost (value + penalty) ──────────────────┤├─ Mixer ─┤

Note: The cost layer has three sub-parts (value RZ, penalty RZZ, penalty RZ), whereas MaxCut has only one (RZZ per edge). This reflects the richer structure of constrained problems.

Step 1: Uniform Superposition

All qubits start in |+⟩ — equal probability over all 2⁴ = 16 possible item subsets.

Step 2: Cost Operator (Value Terms)

Apply RZ(-γ * vᵢ) on each qubit i. This rewards including high-value items by adding a phase proportional to their value. Items with higher value get stronger rotations.

Step 3: Cost Operator (Penalty Terms)

Quadratic: Apply RZZ(γ * P * wᵢ * wⱼ) on each pair (i,j). This penalizes selecting two heavy items together — the heavier the pair, the stronger the penalty.

Linear: Apply RZ(γ * P * wᵢ(wᵢ - 2C)) on each qubit. This penalizes individual items based on how their weight compares to twice the capacity, completing the QUBO encoding.

Step 4: Mixer Operator

Apply RX(2β) on each qubit. Same as MaxCut — toggles between including/excluding items to explore neighboring solutions.

Step 5: Measure and Optimize

Measure all qubits → decode item selection → check feasibility → compute value. Classically optimize γ and β to maximize expected value of feasible solutions.

PYTHONCopy
from circuit import run_circuit, optimize_qaoa

# Default parameters
result = run_circuit()
print(f"Best value: {result['best_value_found']}")
print(f"Feasibility rate: {result['feasibility_rate']:.1%}")

# Optimize parameters
opt = optimize_qaoa(p=1, max_iterations=50, seed=42)
print(f"Optimized ratio: {opt['approximation_ratio']:.1%}")

The Math

Cost Hamiltonian

The QUBO objective as a quantum operator:

H_cost = -Σᵢ vᵢ(1 - Zᵢ)/2 + P × (Σᵢ wᵢ(1 - Zᵢ)/2 - C)²

Using the substitution xᵢ = (1 - Zᵢ)/2, the binary variables map to qubit operators. The expanded form has:

• Linear terms → single-qubit RZ rotations
• Quadratic terms → two-qubit RZZ rotations
• Constant terms → global phase (physically irrelevant)

Mixer Hamiltonian

B = Σᵢ Xᵢ

Standard transverse field mixer, identical to MaxCut. Drives transitions between item subsets.

QAOA State

After p layers:

|γ, β⟩ = exp(-iβ_p B) exp(-iγ_p H_cost) ... exp(-iβ₁ B) exp(-iγ₁ H_cost) |+⟩^n

The expected feasible value ⟨γ,β|H_value|γ,β⟩ (restricted to feasible subspace) is maximized over the 2p parameters.

Penalty Parameter P

Rule of thumb: P ≈ max(vᵢ) ensures that violating the constraint is always worse than dropping the most valuable item. This circuit defaults to P = 25 (= max of item values).

Expected Output

Running the Circuit

PYTHONCopy
from circuit import (
    run_circuit, optimize_qaoa, verify_qaoa,
    compute_exact_solution, evaluate_solution,
)

# Exact solution
exact = compute_exact_solution()
print(f"Optimal: value={exact['optimal_value']}, items={exact['optimal_items']}")

# QAOA with defaults
result = run_circuit(shots=2048)
print(f"Best value: {result['best_value_found']}")
print(f"Feasibility: {result['feasibility_rate']:.1%}")
print(f"Ratio: {result['approximation_ratio']:.1%}")

# Optimize
opt = optimize_qaoa(p=1, shots=2048, seed=42)
print(f"Optimized ratio: {opt['approximation_ratio']:.1%}")

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

# Evaluate a specific solution
sol = evaluate_solution("0110", [10, 15, 20, 25], [5, 8, 10, 12], 18)
print(f"Items {sol['items']}: value={sol['value']}, weight={sol['weight']}")

# Verification
v = verify_qaoa()
for check in v["checks"]:
    print(f"[{'PASS' if check['passed'] else 'FAIL'}] {check['name']}")

Try It Yourself

1. Tune the penalty: Run with penalty=5 (too low) and penalty=100 (too high). How does feasibility rate and best value change? Find the sweet spot.

2. Increase p: Run with p=2 (optimize_qaoa(p=2)). Does the approximation ratio improve? How many more optimizer iterations are needed?

3. Greedy comparison: Implement a greedy algorithm (sort by value/weight ratio, pick until full). Compare its solution to QAOA's. For this small instance, does greedy find the optimal?

4. Scale up: Create a 6-item instance and run QAOA. How does the O(n²) RZZ connectivity affect circuit depth? At what point does noise dominate on a real device?

5. Visualize the landscape: Plot expected value as a function of γ ∈ [0, π] and β ∈ [0, π/2] for p=1. Compare the landscape to MaxCut — is it smoother or more rugged?

What's Next

• TSP — QAOA with multi-qubit encoding (permutation constraints)
• Portfolio Optimization — QAOA for financial asset selection (continuous-weight knapsack variant)
• VQE H₂ Ground State — Another variational algorithm, for quantum chemistry

Applications

Connection to Resource Allocation

The Knapsack problem is the simplest model of resource allocation under constraints — a pattern that appears across industries. Every time you have a fixed budget (money, weight, time, bandwidth) and a menu of options with different costs and benefits, you're solving a knapsack variant.

The QUBO formulation used here generalizes to multi-constraint problems by adding more penalty terms. Real-world quantum advantage for these problems requires hundreds of qubits with low error rates, but the QAOA framework and QUBO mapping transfer directly from this 4-qubit example to production-scale instances.

References

• Lucas, A. (2014). "Ising formulations of many NP problems." Frontiers in Physics 2, 5. DOI: 10.3389/fphy.2014.00005
• Farhi, E., Goldstone, J., Gutmann, S. (2014). "A Quantum Approximate Optimization Algorithm." arXiv: 1411.4028
• Glover, F. et al. (2019). "A Tutorial on Formulating and Using QUBO Models." arXiv: 1811.11538