Open Access

ARTICLE

Comparison among Classical, Probabilistic and Quantum Algorithms for Hamiltonian Cycle Problem

Giuseppe Corrente^1,2,*, Carlo Vincenzo Stanzione^3,4, Vittoria Stanzione⁵

1 Computer Science Department, Università di Torino, Torino, Italy
2 Computer Science Department, ITIS Avogadro Serale, Torino, Italy
3 Computer Engineering Department (DII), Università Degli Studi di Pisa, Pisa, 56122, Italy
4 Justonearth SRL, Roma, 00168, Italy
5 Physics Deparment E.Fermi, Università Degli Studi di Pisa, Pisa, 56127, Italy

* Corresponding Author: Giuseppe Corrente. Email:

Journal of Quantum Computing 2023, 5, 55-70. https://doi.org/10.32604/jqc.2023.044786

Received 09 August 2023; Accepted 02 November 2023; Issue published 14 December 2023

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, 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.

---

Keywords

---