A Quantum Algorithm for Finding a Hamilton Circuit
Guo Hao, Long Gui-Lu, Yang Sun, Xiu Xiao-Lin · Communications in Theoretical Physics · 2001
A quantum algorithm for solving the classical NP-complete problem — the Hamilton circuit is presented. The algorithm employs the quantum SAT and the quantum search algorithms. The algorithm is square-root faster than classical algorithm, and becomes exponentially faster than classical algorithm if nonlinear quantum mechanical computer is used.