Hybrid Quantum-Classical Heuristic for the Bin Packing Problem
arXiv:2204.05637 · doi:10.1145/3520304.3533986
Abstract
Optimization problems is one of the most challenging applications of quantum computers, as well as one of the most relevants. As a consequence, it has attracted huge efforts to obtain a speedup over classical algorithms using quantum resources. Up to now, many problems of different nature have been addressed through the perspective of this revolutionary computation paradigm, but there are still many open questions. In this work, a hybrid classical-quantum approach is presented for dealing with the one-dimensional Bin Packing Problem (1dBPP). The algorithm comprises two modules, each one designed for being executed in different computational ecosystems. First, a quantum subroutine seeks a set of feasible bin configurations of the problem at hand. Secondly, a classical computation subroutine builds complete solutions to the problem from the subsets given by the quantum subroutine. Being a hybrid solver, we have called our method H-BPP. To test our algorithm, we have built 18 different 1dBPP instances as a benchmarking set, in which we analyse the fitness, the number of solutions and the performance of the QC subroutine. Based on these figures of merit we verify that H-BPP is a valid technique to address the 1dBPP.
10 pages, 2 figures, 3 tables, submitted to the Genetic and Evolutionary Computation Conference 2022 (GECCO 2022)
References in corpus (6)
- Supplementary information for "Quantum supremacy using a programmable superconducting processor"
- Strong quantum computational advantage using a superconducting quantum processor
- Quantum computing for finance
- The Bitter Truth About Quantum Algorithms in the NISQ Era
- Quantum Computing based Hybrid Solution Strategies for Large-scale Discrete-Continuous Optimization Problems
- Portfolio Optimization with Digitized-Counterdiabatic Quantum Algorithms