Adiabatic Quantum Computing for the Subset Sum Problem: Preliminary Studies
Cesar Freitas Bernardes, Pedro Belin Castellucci, Douglas Soares Gonçalves, Eduardo I. Duzzioni, Antonio Mucherino · Annals of Computer Science and Information Systems · 2025
The Subset Sum Problem (SSP) is one of those combinatorial problems that are very easy to understand (take a bunch of integer numbers and verify whether there exists a subset of these numbers which sums up to a given target integer), but it can be very difficult to solve.The SSP is actually an NPcomplete problem, but it is "weakly" NP-hard, implying that there are instances of SSP that can be solved in polynomial time.For this particular problem, the instance hardness can be measured by evaluating the so-called "density" index, which basically compares the number of involved integer numbers to the number of bits we need for their binary representation.In our preliminary study on the use of adiabatic quantum computing for the SSP, we investigate the actual feasibility in solving hard instances of the problem.In fact, hard SSP instances are those requiring a large number of bits for the representation of the integers, while the analog nature of the quantum computer does not allow us to ensure highly accurate integer representations.Some preliminary computational experiments performed on D-Wave quantum annealer are presented and compared to standard solvers for classical computers.