  The Hamiltonian cycle problem (HCP), which is an NP-complete problem,
consists of having a graph G with n nodes and m edges and finding the path that
connects each node exactly once. In this paper we compare some algorithms to
solve a Hamiltonian cycle problem, using different models of computations and
especially the probabilistic and quantum ones. Starting from the classical
probabilistic approach of random walks, we take a step to the quantum direction
by involving an ad hoc designed Quantum Turing Machine (QTM), which can be a
useful conceptual project tool for quantum algorithms. Introducing several
constraints to the graphs, our analysis leads to not-exponential speedup
improvements to the best-known algorithms. In particular, the results are based
on bounded degree graphs (graphs with nodes having a maximum number of edges)
and graphs with the right limited number of nodes and edges to allow them to
outperform the other algorithms.
