Solving the Hamiltonian Cycle Problem using a Quantum Computer
Anuradha Mahasinghe, Richard Hua, Michael J. Dinneen, Rajni Goyal · Proceedings of the Australasian Computer Science Week Multiconference · 2019
We review existing quantum computational methods for solving the Hamiltonian cycle problem in different computational frameworks such as quantum circuits, quantum walks and adiabatic quantum computation. Then we present a QUBO (quadratic unconstrained binary optimization) formulation, which is suitable for the adiabatic quantum computation for a D-Wave architecture. Further, we derive a physical Hamiltonian from the QUBO formulation and discuss its adequateness in the adiabatic framework. Finally, we discuss the complexity of running the Hamiltonian cycle QUBO on a D-Wave quantum computer, and compare it with existing quantum computational methods.