Quantum invariants for graph isomorphism

Link identifier archive #link-archive-thumb-soap-80481
Quantum invariants for graph isomorphism
Venerdì 5 novembre 2021 alle ore 15:00, presso il Dipartimento di Matematica e Fisica (edificio C - Aula 311) e sulla piattaforma Link identifier #identifier__115421-1Microsoft Teams, si terrà il seminario del prof. Fernando L. Pelayo (Castilla-La Mancha University - Department of Computer Science) di Logica e Informatica Teorica dal titolo: "Quantum invariants for graph isomorphism".

Abstract: Since McKay presented his Nauty algorithm in 1981 to characterize graph isomorphism until the last proposal by Babai in 2015, a huge effort has been devoted to the graph isomorphism problem together with an improvement on their complexities. This problem is assumed to belong to neither P nor NP-Complete Computational Complexity classes. Maybe the most efficient deterministic algorithm on practice currently available is Traces algorithm proposed by McKay & Piperno in 2014. Quantum computing is facing this problem in an almost disruptive and very interesting perspective...

 
Link identifier #identifier__121001-1Link identifier #identifier__119534-2Link identifier #identifier__32235-3Link identifier #identifier__114759-4

This post is also available in: Link identifier #identifier__105343-5enEng