  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)^2$
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)^2$ 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.
