Towards Improved QUBO Formulations of IR Tasks for Quantum Annealers

In recent years the interest in applying Quantum Computing to Information Retrieval and Recommendation Systems task has increased and several papers have proposed formulations of relevant tasks that can be solved with quantum devices (community detection, feature selection etc.), usually focusing on Quantum Annealers (QA), a special purpose device able to solve combinatorial optimization problems. However, most research only focuses on the mathematical aspect of the formulation, without accounting for the underlying physical processes of the quantum device. Indeed, theoretical studies indicate that certain characteristics make a problem difficult to solve on QA, but it is not clear how to use this knowledge to inform the development of better problem formulations that are equivalent but easier to solve on QA. This work presents a preliminary study which approaches this issue with an empirical perspective. We consider several problems both general and related to IR and Recommendation tasks to assess whether we can identify characteristics of the problem formulation or the solution space that affect the effectiveness of QA. The results indicate interesting correlations and suggest that this is a promising area to investigate further.