Speaker
Description
The Subset Sum Problem (SSP) asks whether there exists a subset of a given set $S$ of integers such that the sum of the elements in the subset corresponds to a predefined target t. The SSP is one of Karp's NP-complete problems and has several real-life applications. In previous works, we have shown that the SSP can be easily mapped onto a Quadratic Unconstrained Binary Optimization (aka QUBO) formulation, opening the doors for experimental solutions based on alternative computing approaches. We present our computational investigations where hard instances of the SSP are solved by the D-Wave quantum annealer, as well as by more recent quantum-inspired digital technologies. We present a study on the encoding limitations inherent in both quantum and digital annealers when applied to the SSP, with the final aim of understanding how approximated integer input values can influence the optimality and the feasibility of the final solutions returned by the annealers.
