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:
- 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.
- 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:
- 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.
- 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.
- 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