Applying Quantum Algorithm to Speed Up the Solution of Hamiltonian Cycle Problems
C. Vidya Raj, M. S. Shivakumar · 2007
Quantum computing is an important field of research that applies concepts of quantum physics to building more efficient computers. Although only rudimentary quantum computers have been built so far, many researchers believe that quantum computing has great potential and the quantum computers can efficiently perform some tasks which are otherwise not feasible on a classical computer, The Hamiltonian cycle problem is to determine whether a given graph has a Hamiltonian cycle or not. This problem belongs to the class of NP-complete problems, widely believed to intractable or hard on classical computers. Design of faster-than-classical quantum algorithms for important algorithmic problems has been an interesting intellectual adventure and achievement all along and their existence keeps being one of the key stimuli to those trying to overcome enormous technology problems to build (powerful) quantum computers. In this paper, we have used undirected graphs with varied number of vertices and we have shown how to determine the existence of a Hamiltonian cycle in a given graph. We have also illustrated how quantum search can be applied to obtain the solution of the Hamiltonian cycle problem much faster than the classical approach.