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 dicfiult 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 afect the efectiveness of QA. The results indicate interesting correlations and suggest that this is a promising area to investigate further. 1
Quantum Computing is a technology that has the potential to accelerate the solution of several
problems that are dificult to solve on traditional hardware. The adoption of this new paradigm
is however a complex endeavour that requires to tackle several challenges, from the
limitation of current quantum computing devices to the development of compatible mathematical
formulations for the problems we want to solve. Indeed, there have already been eforts to
use Quantum Annealers (QA) for Information Retrieval (IR) and Recommendation Systems
(RS) tasks. QA are special-purpose devices that leverage quantum mechanical efects to solve
Quadratic Unconstrained Binary Optimization (QUBO) problems. This QUBO formulation
has been used to represent problems such as graph partitioning [
While most of current works have focused on finding new problems that can be represented as QUBO, the focus is usually on their pure mathematical representation and does not take into account the physical processes used by the QA. Indeed, depending on certain characteristics of the QUBO problem the QA will be more or less sensitive to noise, furthermore when studying the quantum-mechanical processes analytically one can prove that in certain scenarios QA will fail to find the optimal solution. Clearly in our eforts to advance the use of quantum devices for IR and RS tasks we would like to avoid such scenarios and develop QUBO formulations that not only correctly represent the problem but do so in a way that maximizes the efectiveness of QA.
While in principle one could model and study the QA physical system analytically, the complexity of it grows exponentially in the number of problem variables so it is only possible for very small problems. The goal of this study is to analyse, with an empirical perspective, which are the QUBO problem characteristics that make it more or less dificult to solve on a QA. We consider a selection of diferent types of problems in order to provide a suficiently broad analysis but maintain the focus on IR and RS. We compute features and descriptors of those instances and study how they correlate with the efectiveness of QA. Our experiments indicate that certain characteristics correlate well with cases where the QA is efective or inefective and therefore could be useful to consider when developing new QUBO formulations.
This work is based on the D-Wave Advantage QA, which has 5600 qubits [
min = ∈{0,1} (1) where is the cost function, ∈ {0, 1} is a vector of binary variables and is an × symmetric matrix that defines the function to optimize. In practice several factors can afect the quality of the solution found (noise, how slow the evolution was) but also on the problem itself. The underlying physical system can be represented with a Hamiltonian, which is a 2 × 2 matrix. From quantum mechanics we know that using the eigenvalues of the Hamiltonian one can compute the solution that the QA will find. In theory one could use this approach to study whether a QUBO formulation will be robust to noise or not. Unfortunately, given that the Hamiltonian grows exponentially in the number of variables, it is impractical to compute it for problems of more than 20 variables and this severely limits the ability to study the behaviour of QA for applied problems.
The goal of this study is to assess whether there are characteristics of the problem, i.e., matrix Q, or the structure of the solution space, that impact the efectiveness of QA and that could be used to develop better QUBO formulations.
Most of the characteristics we study are based on the spectral analysis of either the solution space of the problem or on matrix Q. In both cases the way we design the QUBO formulation afects both the solution structure and matrix Q, therefore desirable or undesirable characteristics can inform the development of new QUBO formulations.
Solution Space Features: These features are computed based on the energy distribution
of the entire solution space. Note that computing these features requires to know the energy
of all the 2 possible allocations of the variable . On the energy distribution of the solution
space we compute Shannon Entropy (ℎ) [
QUBO Features: We can consider matrix Q as an adjacency matrix to indicate which
problem variables are connected. This allows to define a complexity measure [
We consider four satisfiable instances of five diferent optimization problems: Max-Cut and Minimum Vertex Cover (which can be applied for community detection), as well as Graph Coloring, Set Partitioning and Number Partitioning problems. These instances have 30-32 variables, which allows to compute the entire solution space and the related features. We selected these problems in order to provide a suficiently ample selection while maintaining a focus on IR an RS tasks. We did not include other existing formulations, such as feature selection, because those depend also on heuristics to compute matrix Q (e.g., Pearson correlation, Mutual Information) which introduces a further confounding factor in the analysis, so, for the purpose of this preliminary study we focused on relevant but simpler and more general problems.
The problem instances are solved with the D-Wave Advantage QA, Simulated Annealing (SA) [12] and Tabu Search (TS) [13] in order to compare the solution obtained with diferent methods. To this end, we want to assess whether: (i) QA finds the global optimum, ( ii) QA finds a suboptimal solution but with an energy within 5% of the global optimum, (iii) QA finds a better solution compared to the other heuristics SA and TS. Then, the instances are clustered with agglomerative hierarchical clustering, based on Euclidean distance and average linkage. Three sets of clusters are considered, identified with the following names: • Solution Space clustering: instances are clustered according to their ℎ, and . • QUBO structural clustering: instances are clustered according to their and . • QUBO spectral clustering: instances are clustered according to their and .
The clusters are validated using the Silhouette Coeficient and, for each cluster, it is computed the conditional probability of obtaining a good solution from the QA on an instance given which cluster it belongs to. We refer to this probability as success rate. We can also compare the content of diferent sets of clusters with the help of Jaccard coeficient.
As a general comment we can observe that all the solvers (QA, SA, TS) are able to find either optimal or at least good solutions for most of the problem instances. This is likely due to the limited size of the instances (30-32 variables) which is due to the need to compute the features on the solution space. An exception to this is the Minimum Vertex Cover which is more challenging to solve for both QA and SA. The analysis of the clusters reveals two observations: • Instances characterized by high values of or are always solved either optimally or well by all the samplers. • Instances characterized by low-average values of tend to obtain worse solutions with QA and SA.
This indicates that there is a relationship between solution space or QUBO features and the performance of the diferent solvers, in particular with respect to QA. The diferent clusters are compared with the Jaccard index to assess whether there are relationships between the clusters that can be obtained using diferent features. In particular, we see that: • High values of correspond to high values of and .
• is related to ℎ.
These results are also corroborated by considering the simple linear correlation between solution space features.
Discussion and Future Works In this work we have studied the impact of some characteristics of the solution space of a problem and its QUBO formulation on how challenging it is to solve it with Quantum Annealing. The aim of the analysis is to inform the future development of new QUBO formulation for IR problems, such as community detection and feature selection. While this is a preliminary study that considers a limited number of instances, it is possible to observe that certain features indeed correlate with the efectiveness of QA: Spectral Flatness ( ), Graph Density () and Graph Spectral Flatness ( ). In particular, for instances characterized by high values of ( ) and () QA is highly efective. We observe also that QA and SA share a similar behaviour, both perform badly for some values of ( ), while TS always performs better than them. Indeed, the need to compute features on the solution space constrains their uses to small problems. It was observed however that ( ) and () are strongly correlated, this means that as a future direction the study could be expanded to focus on features of the QUBO problems that are not based on the solution space and therefore allow to study much larger problems. [12] S. Kirkpatrick, C. D. Gelatt Jr, M. P. Vecchi, Optimization by simulated annealing, science 220 (1983) 671–680. [13] G. Palubeckis, Multistart tabu search strategies for the unconstrained binary quadratic optimization problem, Annals of Operations Research 131 (2004) 259–282.