论文标题
图形同构问题的量子不变性
Quantum invariants for the graph isomorphism problem
论文作者
论文摘要
图等法是计算机科学中如此重要的问题，在过去几十年中，它已经广泛研究了。众所周知，它属于NP类，但不是NP完整的。被认为与整数分解相当。 1983年，LászlóBabai和Eugene Luks提出了最著名的算法来解决这个问题。 最近，通过使用量子计算，在该主题上进行了一些研究，这也引起了目前的研究。实际上，我们提出了一种量子计算算法，该算法定义了图形同构表征的不变性。该量子算法能够与迄今为止的大多数已知不变式相比，能够区分更多的非同构图。本文还包括正确性的证明和一些提示，说明了改进的程度和原因。
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.
