The graph isomorphism problem is about deciding whether two graphs are actually the same even if they look different in their graphical or adjacency matrix representation. The problem has important applications, especially in the field of computer science, chemistry and bio-informatics. Moreover, the problem of graph isomorphism has remarkable properties in terms of its complexity, it is not known to be in class P, and also not known to be class NP-complete. These properties make the problem a perfect candidate for the development of a new efficient quantum algorithm. In this direction, we have put some efforts into investigating this question. This paper gives an overview and importance of graph isomorphism problem, discusses the complexity properties and the essentials for quantum computations such as quantum parallelism and superposition, quantum Fourier Transforms, Fourier sampling. An insight into two important approaches for the quantum computations; the Hidden subgroup approach and hidden shift approach have been discussed. However, more emphasis has been on graph isomorphism and its relation to Hidden subgroup problems. In all, we have given a quantum framework for graph isomorphism problem.
www.acadjournal.com
