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.
翻译:图形形态学是计算机科学中如此重要的一个问题, 过去几十年来已经对此进行了广泛研究。 众所周知, 它属于NP类, 但不是NP- 完整的。 据认为, 它具有与整数化相似的困难。 1983年L\' aszl\'o Babai 和 Eugene Luks 提出了解决该问题最有名的、 证明有效的算法。 最近, 利用量子计算对这个专题进行了一些研究, 这同时也引领了目前的研究。 事实上, 我们提出了一个量子计算算法, 定义了相对于图形形态形态特征的无变数。 这个量算法能够比迄今为止已知的多数变数者区分更多的非单数图形。 本文中还包含了正确性的证据和一些说明改进程度和原因的提示。