QUBO transformation using Eigenvalue Decomposition
This work addresses combinatorial optimization for quantum annealing applications, but it appears incremental as it builds on existing QUBO methods with a specific enhancement.
The paper tackles the problem of improving the search process for Quadratic Unconstrained Binary Optimization (QUBO) problems by using eigenvalue decomposition to guide the search based on dominant eigenvalues and eigenvectors, resulting in significant performance improvements on benchmark datasets with dominant eigenvalues.
Quadratic Unconstrained Binary Optimization (QUBO) is a general-purpose modeling framework for combinatorial optimization problems and is a requirement for quantum annealers. This paper utilizes the eigenvalue decomposition of the underlying Q matrix to alter and improve the search process by extracting the information from dominant eigenvalues and eigenvectors to implicitly guide the search towards promising areas of the solution landscape. Computational results on benchmark datasets illustrate the efficacy of our routine demonstrating significant performance improvements on problems with dominant eigenvalues.