Study of the impact of spectral features of QUBO problems on the performance of Quantum Annealers

In recent years, a strong interest has been seen in studying Quantum Annealers (QA) as heuristic solvers of Quadratic Uncostrained Binary Optimization (QUBO) problems. It has been seen that QA effectively solve small QUBO instances, but as the size of instances increases the results of QA are not as good as those with smaller instances. Furthermore, an analytical study of the performance of QA is possible only for small QUBO instances, since it requires the analysis of the time-varying Hamiltonian considered by QA. In this research, we analyze with an empirical perspective the characteristics which make QUBO problems difficult to solve with QA. We consider in our analysis instances of Maximum Cut, Minimum Vertex Cover, Graph Coloring, Set Partitioning and Number Partitioning problems, requiring 30-32 QUBO variables. For all instances we compute several features based on the energy distribution of their solutions and on the spectral representation of the QUBO problem as a graph. Each instance is solved with the D-Wave Advantage QA, Simulated Annealing and Tabu Search. The problem instances are clustered according to their features and the clusters are validated with Silhouette Coefficient. The analysis reveals correlations between the clusters and the ability of QA to solve the instances effectively, opening new research opportunities to develop better QUBO formulations that are easier to solve on QA.

Negli ultimi anni si è assistito a un forte interesse nello studio dei Quantum Annealers (QA) come risolutori euristici di problemi di Quadratic Uncostrained Binary Optimization (QUBO). Si è visto che i QA risolvono efficacemente istanze QUBO di piccole dimensioni, ma all’aumentare delle dimensioni delle istanze i risultati dei QA non sono così buoni come quelli ottenuti con istanze più piccole. Inoltre, uno studio analitico delle prestazioni dei QA è possibile solo per istanze QUBO di piccole dimensioni, poiché richiede l’analisi dell’Hamiltoniano variabile nel tempo considerato dai QA. In questa ricerca analizziamo da un punto di vista empirico le caratteristiche che rendono i problemi QUBO difficili da risolvere con i QA. Nella nostra analisi consideriamo istanze di problemi Maximum Cut, Minimum Vertex Cover, Graph Coloring, Set Partitioning e Number Partitioning, che richiedono 30-32 variabili QUBO. Per tutte le istanze calcoliamo diverse caratteristiche basate sulla distribuzione energetica delle loro soluzioni e sulla rappresentazione spettrale del problema QUBO come un grafo. Ogni istanza viene risolta con il D-Wave Advantage QA, Simulated Annealing e Tabu Search. Le istanze del problema vengono raggruppate in base alle loro caratteristiche e i cluster vengono convalidati con Silhouette Coefficient. L’analisi rivela correlazioni tra i cluster e la capacità di QA di risolvere efficacemente le istanze. Questo risultato apre nuove opportunità di ricerca per sviluppare formulazioni di QUBO migliori e più facili da risolvere con i QA.