  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\'aszl\'o 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.

Computational Complexity