Abstract
I use QAOA to solve the Hamiltonian Circle problem. First, inspired by Lucas, I define the QUBO form of Hamiltonian Cycle and transform it to a quantum circuit by embedding the problem of n vertices to an encoding of (n-1)² qubits. Then, I calcluate the spectrum of the cost hamiltonian for both triangle case and square case and justify my definition. I also write a python program to generate the cost hamiltonian automatically for finding the hamiltonian cycle in an arbitrary graph. I test the correctess of the hamailtonian by analyze their energy spectrums. Since the (n-1)² embedding limit my simulation of graph size to be less than 5, I decide to test the correctness, only for small and simple graph in this project. I implement the QAOA algorithm using qiskit and run the simulation for the triangle case and the square case, which are easy to test the correctness, both with and without noise. A very interesting result I got is that for the square case, the QAOA get much better result on a noisy simulator than a noiseless simulator. The explanation for this phenomena require further investigation, perhaps quantum noise can actually be helpful, rather than harmful in the annealing algorithms. I also use two different kinds of mixer, R_x mixer and R_y circuit to run the simulation. It turns out that R_x mixer performs much better than R_y mixer in this problem.