Approximating Quadratic Unconstrained Binary Optimization Problems using Graph Convolutional Neural Networks

Approximating Quadratic Unconstrained Binary Optimization Problems using Graph Convolutional Neural Networks

Abstract:

The quantum annealing hardware currently available has not yet reached the stage to successfully compete with ecient heuristics on classical machines, due to limitations in size and connectivity. Confronted with this challenge, the approach to approximate QUBO matrices by removing certain entries before solving them on the quantum hardware has been introduced. This is done to reduce the size and the complexity of the embedding, anticipating benefits with regard to the size of the solvable problems as well as the quality of the solutions.
We will extend this approach by using artificial neural networks to generate suitable approximations based on the structure of the matrix. The proposed model consists of two separate networks, a graph convolutional neural network to compute features for the nodes in the QUBO graph and a second fully connected network to derive a decision, whether the connection between two nodes should be removed from the matrix. A genetic algorithm was employed to train the model, using instances of seven dierent problems. Problem specific phase transitions were taken into account to confront the model with
easy and hard problem instances.
The trained models were subsequently evaluated using classical and quantum solvers, comparing the performance of the approximated matrix with the original matrix, another approximation strategy and classical approaches. The experiments provided satisfying results for certain problems, as the approximated matrices were partially able to produce even better results than the original matrices. In other respects, it became apparent, that this approach is not applicable to all problems.

Author:

Felix Ferdinand Mindt

Advisors:

Claudia Linnhoff-Popien, David Bucher, Sebastian Zielinski

Student Thesis | Published October 2023 | Copyright © QAR-Lab
Direct Inquiries to this work to the Advisors