Aprendizado de Máquina Quântica com Rede Neural Artificial Aplicado ao Problema de Coloração de Grafos

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

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

Resumo

O problema de coloração de grafos consiste em atribuir cores a certos elementos de um grafo, sujeito a determinadas condições. Ao se caracterizar como um problema de otimização combinatória, ele possui aplicabilidade a uma vasta gama de áreas que envolvem particionamento e conflitos, compreendendo escalonamentos e alocações diversas, como, por exemplo, de tarefas, canais, redes, eventos e rotas. O problema considerado, constituído por um grafo com 4 vértices, demonstrou o potencial do aprendizado de máquina quântica com redes neurais artificiais proposto na resolução de um problema de otimização combinatória, o qual obteve resultados superiores em relação àqueles apresentados pela rede neural artificial utilizada, implementada em um computador clássico, com relação ao tempo de processamento e à acurácia da rede neural clássica.

Palavras-chave: Avaliação, Medição e Predição de Desempenho, Computação de Alto Desempenho, Computação em Nuvem, Grade, Aglomerado (Cluster) e Peer-to-Peer

Referências

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.