Giuseppe Corrente1,2,*, Carlo Vincenzo Stanzione3,4, Vittoria Stanzione5
Journal of Quantum Computing, Vol.5, pp. 55-70, 2023, DOI:10.32604/jqc.2023.044786
Abstract The Hamiltonian cycle problem (HCP), which is an NP-complete problem, consists of having a graph G with 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,… More >
Login
Register
