Quantum Relaxation for Solving Multiple Knapsack Problems

Monit Sharma, Yan Jin, Hoong Chuin Lau, Rudy Raymond

TL;DR

This paper introduces a hybrid quantum-classical approach to solve the Multiple Knapsack Problem (MKP), a complex constrained optimization challenge common in supply chains. By combining Quantum Random Access Optimization (QRAO)—which packs three classical bits into a single qubit—with classical Linear Relaxation, the researchers successfully tackled real-world-sized problems (100+ variables) that are currently beyond the reach of standard quantum algorithms like QAOA.

What Problem Does This Paper Address?

Most "success stories" in quantum optimization focus on unconstrained problems, like Max-Cut. However, the business world runs on constraints: budgets, capacities, and risk tolerances. The Multiple Knapsack Problem (MKP) is a classic example where you must assign items to multiple "bins" without exceeding their capacities while maximizing profit.

Current Noisy Intermediate-Scale Quantum (NISQ) devices face two major hurdles:

  1. Qubit Scarcity: Standard algorithms like the Quantum Approximate Optimization Algorithm (QAOA) typically require one qubit per classical bit. This makes large problems impossible to fit on today's hardware.
  2. Constraint Handling: Mapping hard constraints (like "don't exceed bin capacity") onto a quantum Hamiltonian is mathematically difficult and often leads to poor performance.

Methods

The authors propose a two-stage hybrid pipeline:

  1. Classical Presolve (Linear Relaxation): Before touching a quantum computer, they solve a "relaxed" version of the problem where variables can be any fraction between 0 and 1 (instead of just 0 or 1). Variables that the classical solver finds to be very close to 0 or 1 are "fixed," significantly shrinking the problem size.
  2. Quantum Optimization (QRAO): The remaining "hard" variables are solved using QRAO. Unlike QAOA, QRAO uses Quantum Random Access Codes (QRAC) to encode up to three classical variables into the $X, Y,$ and $Z$ bases of a single qubit. This provides a 3:1 compression ratio in qubit requirements.
  3. Rounding: Since quantum states are probabilistic, the authors use "Magic Rounding" (a technique to decode the three bits from one qubit simultaneously) to translate the quantum result back into a valid classical solution.

They specifically utilized a Brickwork Ansatz for their variational circuits, finding it superior to other architectures because it handles the complex amplitudes required by QRAO's non-diagonal Hamiltonians.

Datasets

The researchers evaluated their approach on two fronts:

  • Synthetic MKP Instances: 100 randomly generated, non-trivial instances with 2 to 5 bins and 2 to 10 items (up to 20 binary variables).
  • Real-World Procurement Problem: A "Risk-Aware Procurement Optimization" problem involving over 100 variables, modeled after a multinational computer manufacturer's supply chain.

Key Insights and Ideas

  • The Power of Compression: QRAO isn't just a "smaller" version of QAOA; it changes the nature of the Hamiltonian. By using non-diagonal local Hamiltonians, QRAO can leverage quantum entanglement more effectively than the classical-like states often found in QAOA.
  • Complex Amplitudes Matter: The authors discovered that "RealAmplitudes" circuits (which only use real numbers) fail with QRAO. Because the QRAO Hamiltonian is built from $X, Y,$ and $Z$ Pauli operators, the quantum state must be able to explore the complex-valued Hilbert space.
  • Hybrid is Mandatory: The study highlights that for the foreseeable future, quantum computers shouldn't work alone. Using classical Linear Relaxation as a "filter" allows quantum algorithms to focus their limited resources on the most ambiguous parts of the optimization landscape.

Key Results

  • Qubit Efficiency: For a problem that required 20 qubits using QAOA, QRAO achieved comparable or better results using only 7 qubits.
  • Optimality Gap: On the MKP test set, QRAO with Magic Rounding achieved an average optimality gap of 0.065, outperforming QAOA’s gap of 0.092.
  • Scalability: While QAOA struggled to scale due to memory and qubit limits, the QRAO + Linear Relaxation hybrid successfully solved the 100-variable procurement problem with high feasibility (up to 100% in some configurations).

Limitations and Future Work

The authors acknowledge a few areas for improvement:

  • Hardware Noise: Most of the results were obtained via simulators (like Qiskit’s AerSimulator). While QRAO is theorized to be robust against noise, testing on actual NISQ hardware is the next logical step.
  • Static vs. Stochastic: The current model assumes fixed demands and risks. The authors plan to integrate stochastic elements to better reflect the uncertainty of real-world supply chains (e.g., fluctuating demand or shipping delays).
  • Refining the "Fixing" Threshold: The performance of the Linear Relaxation step is sensitive to the threshold ($\delta$) used to fix variables. Finding the "sweet spot" between problem reduction and solution accuracy remains an open challenge.

Summary updated

Abstract

Combinatorial problems are a common challenge in business, requiring finding optimal solutions under specified constraints. While significant progress has been made with variational approaches such as QAOA, most problems addressed are unconstrained (such as Max-Cut). In this study, we investigate a hybrid quantum-classical method for constrained optimization problems, particularly those with knapsack constraints that occur frequently in financial and supply chain applications. Our proposed method relies firstly on relaxations to local quantum Hamiltonians, defined through commutative maps. Drawing inspiration from quantum random access code (QRAC) concepts, particularly Quantum Random Access Optimizer (QRAO), we explore QRAO's potential in solving large constrained optimization problems. We employ classical techniques like Linear Relaxation as a presolve mechanism to handle constraints and cope further with scalability. We compare our approach with QAOA and present the final results for a real-world procurement optimization problem: a significant sized multi-knapsack-constrained problem.
BibTeX
@inproceedings{sharma2024quantum,
  author = {Monit Sharma and Yan Jin and Hoong Chuin Lau and Rudy Raymond},
  title = {{Quantum Relaxation for Solving Multiple Knapsack Problems}},
  booktitle = {QCE},
  year = {2024},
  doi = {10.1109/qce60285.2024.00086},
}

Loading related content...

Figure