Quantum-inspired Evolutionary Optimizer on NVIDIA GPUs Accelerates Large-scale 01 Knapsack Problem Solutions

Combinatorial optimization problems, notoriously difficult for classical computers, increasingly demand innovative solutions, and researchers are now exploring the potential of quantum-inspired algorithms. Aman Mittal, Kasturi Venkata Sai Srikanth, and Ferdin Sagai Don Bosco, all from BosonQ Psi Corporation, lead a team that investigates a new approach, the Quantum Inspired Evolutionary Optimizer (QIEO), and its performance on modern NVIDIA GPUs. This work systematically assesses how QIEO scales with increasingly complex problems, specifically the 01 Knapsack problem, and demonstrates significant speedups through careful exploitation of the GPU’s parallel processing capabilities. The team’s findings reveal that strategic memory management and kernel configuration are critical for achieving optimal performance, offering valuable insights for the future development of large-scale metaheuristic algorithms and their implementation on parallel hardware.

The study systematically investigates how to best configure the QIEO on a GPU to maximise performance and scalability, focusing on the impact of key parameters including population size, gene count, and memory configuration. Results demonstrate that GPU acceleration dramatically speeds up the QIEO, enabling it to tackle problem instances far beyond the reach of traditional CPU implementations. Crucially, the choice of memory access, constant, global, or pinned, significantly impacts performance, with constant memory proving best for smaller problems and global/pinned memory essential for larger scales.

Optimal performance also relies on smaller thread-blocks and efficient use of the GPU’s processing units. Scientists systematically evaluated the performance and scalability of this approach when applied to large-scale 0/1 Knapsack problems, demonstrating substantial speedups through optimised memory management and thread configuration within the CUDA framework. The study meticulously analysed various problem sizes, kernel launch configurations, and memory models, including constant, shared, global, and pinned memory, to pinpoint optimal strategies for maximising throughput and efficiency. The core computational complexity of QIEO was analysed, revealing that each generation involves Quantum Information Processing, Fitness Evaluation, and Classical Information Processing, all influenced by population size, problem dimensionality, and the cost of evaluating functions. Researchers determined that the aggregate per-generation time complexity and space complexity are directly related to these factors.

Results demonstrate that GPU acceleration substantially improves the scalability and speed of QIEO, allowing efficient exploration of search spaces that would be impractical using traditional CPU implementations. Extensive experimentation with varying population sizes, gene counts, and memory configurations reveals the critical importance of memory hierarchy in achieving optimal performance. The research highlights that constant memory access consistently delivers the best efficiency for smaller to moderate problem sizes, while global memory, used with careful tiling strategies, effectively handles larger-scale problems. Thread-block configuration and kernel launch parameters also significantly influence performance, with smaller blocks and efficient use of the GPU’s processing units proving essential for maximising parallelism and minimising execution time. The authors acknowledge limitations in strong scaling due to hardware resource saturation and communication overheads at extreme population sizes, suggesting a need for dynamic resource allocation and algorithmic innovations for future exa-scale systems.