@Article{jqc.2023.044786,
AUTHOR = {Giuseppe Corrente, Carlo Vincenzo Stanzione, Vittoria Stanzione},
TITLE = {Comparison among Classical, Probabilistic and Quantum Algorithms for Hamiltonian Cycle Problem},
JOURNAL = {Journal of Quantum Computing},
VOLUME = {5},
YEAR = {2023},
NUMBER = {1},
PAGES = {55--70},
URL = {http://www.techscience.com/jqc/v5n1/54860},
ISSN = {2579-0145},
ABSTRACT = {The Hamiltonian cycle problem (HCP), which is an NP-complete problem, consists of having a graph <i>G</i> with  nodes and <i>m</i> 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.},
DOI = {10.32604/jqc.2023.044786}
}