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

Autor:	Corrente, Giuseppe, Stanzione, Carlo Vincenzo, Stanzione, Vittoria
Rok vydání:	2023
Předmět:	Quantum Physics Computer Science - Data Structures and Algorithms Computer Science - Emerging Technologies F.1.m
Druh dokumentu:	Working Paper
DOI:	10.32604/jqc.2023.044786
Popis:	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. Comment: 18 pages, 3 figures. It will appear in Journal of Quantum Computing, Tech Science Press
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2311.10941 Zobrazit plný text záznamu View this record from Arxiv