On the Design and Characterization of Set Packing Problem on Quantum Annealers

The beginning of the quantum era has increased the hype around computationally demanding problems and, particularly, NP-complete problems. One of the most famous is the Set Packing, which has several applications in different management contexts. This work presents a solver for Set Packing Problem on quantum annealers exploiting the QUBO model. We introduce a general format to express instances of the Set Packing Problem that enables an automatic characterization, lowering the barriers to adopting quantum annealers. Finally, we compare the performance of two quantum annealer on the Set Packing, namely D-Wave 2000Q and Advantage, highlighting their pros and cons. As key evaluation indicators, this work uses spatial features, such as the number of qubits and maximum chain length, and the execution time required for a reliable problem resolution and its breakdown. In particular, we can scale the solutions to 60 and 150 subsets on 2000Q and Advantage, respectively, with 0 chain breaks. Moreover, our analysis illustrates that 2000Q has lower mean energy required but higher execution times on the same problem complexity.