Does the structure of the QUBO problem afect the efectiveness of quantum annealing? An empirical perspective

Abstract

In recent years there has been a significant interest in exploring the potential of Quantum Annealers (QA) as heuristic solvers of Quadratic Unconstrained Binary Optimization (QUBO) problems. Some problems are more dificult to solve on QA and understanding why is not straightforward, because an analytical study of the underlying physical system is intractable for large QUBO problems. This work consists in an empirical analysis of the features making a QUBO problem dificult to solve on QA, based on clusters of QUBO instances identified with Hierarchical Clustering. The analysis reveals correlations between specific values of the features and the ability of QA to solve efectively the instances. These initial results open new research opportunities to inform the development of new AI methods supporting quantum computation (e.g., for minor embedding or error mitigation) that are better tailored to the characteristics of the problem, as well as to develop better QUBO formulations for known problems in order to improve the quality of the solutions found by QA. 1 htp:/ceur-ws.org CEUR Workshop Proceedings (CEUR-WS.org) ISN1613-073

Keywords

• quantum computing
• quantum annealing
• optimization

-

CEUR ceur-ws.org

1. Introduction

Quantum Annealers (QA) are heuristic solvers of Quadratic Unconstrained Binary Optimization (QUBO) problems. It is known that some problems are more dificult to solve efectively with QA compared to other ones. However, it’s challenging to study analytically the Hamiltonian for large QUBO problems and it is often not clear how to use these findings to develop new general QUBO formulations that are easier to solve on QA. Furthermore, AI techniques based on the characteristics of QUBO problems able to support QA, such as for minor embedding or error mitigation, are lacking, since the characteristics which represent the dificulty of a QUBO problem are unknown.

In this work, we study with an empirical perspective the characteristics making a QUBO problem dificult to solve on QA, in particular when it requires too many qubits for the analytical study of the Hamiltonian, trying to answer to the question: does the structure of a QUBO problem afects the efectiveness of QA? 1These results have been presented at the 12th Adiabatic Quantum Computing Conference (AQC 2023), June CEUR Workshop Proceedings In this study we consider instances of the Maximum Cut, Minimum Vertex Cover, Graph Coloring, Set Partitioning, Number Partitioning problems [ 1 ]. Each instance has 30-32 QUBO variables, corresponding to 100-150 qubits on the physical embedding of QA. 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. In particular, the Spectral Flatness measures the uniformity of the spectrum of the distribution of the solutions of a QUBO instance [ 2 ]; the Graph Spectral Flatness measures the uniformity of the spectrum of a signal on a graph [ 3 ], when both the signal and the graph are related to the same QUBO instance.

All instances are solved with the D-Wave Advantage QA and also with Simulated Annealing and Tabu Search, considered as baseline methods. Instances are then clustered on the base of their features and the clusters are validated with Silhouette Coeficient. In order to corroborate the obtained results, we also include four test instances related to the Feature Selection problem [ 4 ] and check to which cluster they are closest to, according to the computed features.

3. Results and Discussion

The analysis reveals correlations between the clusters and the ability of QA to solve the instances efectively. In particular, we see that instances characterized by high levels of Spectral Flatness are solved optimally by QA. Furthermore, we see also that instances which have low levels of Graph Spectral Flatness are solved optimally too by the QA.

All these findings are corroborated by the test instances we have considered, confirming the relationship between the quality of the solution found by the QA and the structure of the QUBO problem. These initial results open new research opportunities to inform the development of new AI methods supporting quantum computation that are better tailored to the characteristics of the problem, as well as to develop better QUBO formulations for known problems in order to improve the quality of the solutions found by QA.

References

[1] Glover , F. , Kochenberger , G. , Du , Y. , Quantum bridge analytics i: a tutorial on formulating and using qubo models ., 4OR 17 ( 4 ) ( 2019 ) 335 - 371 .

[2] B. Boashash , G. Azemi, N. Ali Khan , Principles of time-frequency feature extraction for change detection in non-stationary signals: Applications to newborn eeg abnormality detection , Pattern Recognition 48 ( 2015 ) 616 - 627 .

[3] A. Ortega , Introduction to Graph Signal Processing, Cambridge University Press, 2022 .

[4] M. Ferrari Dacrema , F. Moroni , R. Nembrini , N. Ferro , G. Faggioli, P. Cremonesi , Towards feature selection for ranking and classification exploiting quantum annealers , in: SIGIR '22: The 45th International ACM SIGIR Conference on Research and Development in Information Retrieval , Madrid, Spain, July 11 - 15 , 2022 , ACM, 2022 , pp. 2814 - 2824 .