RT Journal Article
T1 Quantum invariants for the graph isomorphism problem
A1 Cruz Calvo, Hernán Indíbil de la
A1 Pelayo, Fernando L.
A1 Pascual, Vicente
A1 Paulet González, Jose Javier
A1 Cuartero Gómez, Fernando
A1 Llana Díaz, Luis Fernando
A1 Mezzini, Mauro
AB Graph Isomorphism is such an important problem in computer science, that it has been widely studied over the last decades. It is well known that it belongs to NP class, but is not NP-complete. It is thought to be of comparable difficulty to integer factorisation. The best known proved algorithm to solve this problem in general, was proposed by László Babai and Eugene Luks in 1983. Recently, there has been some research in the topic by using quantum computing, that also leads the present piece of research. In fact, we present a quantum computing algorithm that defines an invariant over Graph Isomorphism characterisation. This quantum algorithm is able to distinguish more non-isomorphic graphs than most of the known invariants so far. The proof of correctness and some hints illustrating the extent and reason of the improvement are also included in this paper.
YR 2022
FD 2022-10-07
LK https://hdl.handle.net/20.500.14352/72679
UL https://hdl.handle.net/20.500.14352/72679
LA eng
NO Ministerio de Economía y Competitividad (MINECO)/FEDER
NO Comunidad de Madrid/FEDER
DS Docta Complutense
RD 6 abr 2025