Quantum reduction of the Hamiltonian path problem to period-finding
Blind Review · 2022
This paper reduces the undirected Hamiltonian path existence problem into a period-finding problem, though in sense of quantum reduction and with help of computational basis-based quantum Fourier transform. An undirected graph is encoded into complex-valued function p(t) of natural-valued variable t by frequency assignments to vertices and walks. g(t) is then constructed from p(t) by a unitary operation such that its period depends on whether Hamiltonian paths exist or not.