Solving the Hamiltonian Cycle Problem using a Quantum Computer

Abstract

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.