Quantum Machine Learning with Neural Network Artificial Applied to Graph Coloring Problem

• Flávia Janine R. Béo UFABC
• Karla Vittori UFABC

DOI: https://doi.org/10.5753/eradsp.2021.16701

Abstract

The problem of coloring graphs is to assign colors to certain elements of a graph, subject to certain conditions. When characterized as a combinatorial optimization problem, it has applicability to a wide range of areas that involve partitioning and conflicts, comprising different scheduling and allocations, such as, for example, tasks, channels, networks, events and routes. The considered problem, constituted by a graph with 4 vertices, demonstrated the potential of quantum machine learning with artificial neural networks proposed in the resolution of a combinatorial optimization problem, which obtained superior results in relation to those presented by the classic artificial neural network, implemented in a classic computer, with respect to the processing time and the accuracy of the considered neural network.

Keywords: Performance measurements, evaluation and prediction, High-Performance Computing, Clouds, Grids, Clusters, and Peer-to-Peer Computing

References

Bergholm, V., Vartiainen, J. J., Möttönen, M., and Salomaa, M. M. (2005). Quantum circuits with uniformly controlled one-qubit gates. Physical Review A, 71(5):052330.

Campbell, E., Khurana, A., and Montanaro, A. (2019). Applying quantum algorithms to constraint satisfaction problems. Quantum, 3:167.

Jeswal, S. and Chakraverty, S. (2019). Recent developments and applications in quantum neural network: a review. Archives of Computational Methods in Engineering, 26(4):793–807.

Prates, M., Avelar, P. H., Lemos, H., Lamb, L. C., and Vardi, M. Y. (2019). Learning to solve np-complete problems: A graph neural network for decision tsp. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 4731–4738.

Sutton, R. S. and Barto, A. G. (2011). Reinforcement learning: An introduction.